Luận án tiến sĩ về kỹ thuật so khớp trong phát hiện xâm nhập và giả mạo trên mạng

Luận án tiến sĩ kỹ thuật phân tích phát triển một số kỹ thuật so khớp ứng dụng trong quá trình phát hiện xâm nhập và giả mạo trên mạng, xây dựng cơ sở lý luận, kiểm chứng thực

• Tác giả: Lê Đăng Nguyên
• Người hướng dẫn: PGS. Lê Trọng Vĩnh
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Cơ sở toán học cho Tin học
• Đề tài: Kỹ Thuật So Khớp Trong Phát Hiện Xâm Nhập Và Giả Mạo Mạng
• Loại tài liệu: luận án tiến sĩ toán học
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ SO KHỚP
• 1.1. So khớp chuỗi
• 1.2. Bài toán so khớp chuỗi
• 1.3. Các thuật toán so khớp chính xác cổ điển
• 1.4. Các thuật toán so khớp chính xác dựa trên mô hình Automat
• 1.5. Các thuật toán so khớp chính xác dựa trên bảng băm
• 1.6. Các thuật toán so khớp gần đúng
• 1.7. Một số nghiên cứu liên quan về ứng dụng thuật toán so khớp trong phát hiện xâm nhập mạng
• 1.8. So khớp đồ thị
• 1.9. Một số định nghĩa và ký hiệu
• 1.10. Bài toán so khớp đồ thị
• 1.11. Một số nghiên cứu liên quan về so khớp đồ thị
• 1.12. Kết chương
• 2. CHƯƠNG 2: ỨNG DỤNG SO KHỚP MẪU TRONG QUÁ TRÌNH PHÁT HIỆN XÂM NHẬP MẠNG
• 2.1. Xâm nhập mạng
• 2.2. Một số kỹ thuật xâm nhập trái phép
• 2.3. Một số giải pháp kỹ thuật ngăn chặn xâm nhập
• 2.4. Hệ thống phát hiện xâm nhập trái phép
• 2.5. Một số nghiên cứu liên quan đến hệ thống phát hiện xâm nhập
• 2.6. Thuật toán Aho-Corasick
• 2.7. Một số nghiên cứu liên quan
• 2.8. Cải tiến thuật toán AC bằng kỹ thuật nén dòng và bảng chỉ số
• 2.9. Biểu diễn không gian lưu trữ và tối ưu hóa bằng kỹ thuật nén dòng
• 2.10. Cải tiến giai đoạn tiền xử lý của AC
• 2.11. Thực nghiệm và đánh giá
• 2.12. Thuật toán đề xuất mới xây dựng biểu đồ hướng cấu trúc các mẫu kết hợp với danh sách liên kết
• 2.13. Giai đoạn tiền xử lý
• 2.14. Giai đoạn tìm kiếm
• 2.15. Thuật toán đề xuất
• 2.16. Kết chương
• 3. CHƯƠNG 3: ỨNG DỤNG SO KHỚP ĐỒ THỊ TRONG QUÁ TRÌNH PHÁT HIỆN CÁC TRANG WEB GIẢ MẠO
• 3.1. Giả mạo trên mạng
• 3.2. Một số kỹ thuật giả mạo
• 3.3. Một số nghiên cứu liên quan đến giả mạo Web
• 3.4. Một số nghiên cứu liên quan về so khớp đồ thị
• 3.4.1. Tìm đẳng cấu đồ thị và đẳng cấu đồ thị con. Thuật toán SI - COBRA cho bài toán so khớp đồ thị gán nhãn
• 3.4.2. Thuật toán Simple Tree Matching
• 3.4.3. Thuật toán Partial Tree Alignment
• 3.4.4. Thuật toán NET
• 3.4.5. Thuật toán di truyền
• 3.4.5.1. Giải thuật di truyền cho bài toán so khớp đồ thị
• 3.4.5.2. Giải thuật di truyền
• 3.4.5.3. Kết quả mô phỏng với giải thuật di truyền
• 3.5. Thuật toán đề xuất về ứng dụng so khớp đồ thị vào so khớp DOM-tree
• 3.5.1. Khái niệm cây DOM
• 3.5.2. Xây dựng cây DOM từ trang Web
• 3.5.3. Phát hiện giả mạo dựa trên cây DOM
• 3.6. Kết chương
• Các kết quả của luận án
• Hướng phát triển luận án
• DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về phát hiện xâm nhập và giả mạo mạng

Trong bối cảnh an ninh mạng ngày càng trở nên quan trọng, việc phát hiện xâm nhập mạng và giả mạo mạng là một trong những thách thức lớn nhất đối với các tổ chức. Hệ thống phát hiện xâm nhập (IDS) có vai trò quan trọng trong việc bảo vệ tài nguyên thông tin. Các hệ thống này phân tích và theo dõi lưu lượng mạng để phát hiện các hành vi bất thường. Theo báo cáo, thiệt hại do tội phạm mạng gây ra đã lên tới hàng trăm tỷ USD. Điều này cho thấy sự cần thiết phải phát triển các kỹ thuật phát hiện hiệu quả hơn. Việc áp dụng kỹ thuật so khớp vào hệ thống IDS giúp nhận diện các mẫu tấn công một cách nhanh chóng và chính xác. Các nghiên cứu đã chỉ ra rằng việc cải tiến thuật toán so khớp có thể nâng cao hiệu suất phát hiện xâm nhập, từ đó bảo vệ tốt hơn cho hệ thống.

1.1. Hệ thống phát hiện xâm nhập

Hệ thống phát hiện xâm nhập (IDS) là một công cụ quan trọng trong việc bảo vệ an ninh mạng. IDS có khả năng phân tích lưu lượng mạng và phát hiện các hành vi xâm nhập trái phép. Các hệ thống này thường sử dụng các thuật toán so khớp để so sánh lưu lượng mạng với các mẫu tấn công đã biết. Việc phát hiện kịp thời giúp ngăn chặn các cuộc tấn công trước khi chúng gây ra thiệt hại. Các nghiên cứu gần đây đã chỉ ra rằng việc cải tiến các thuật toán so khớp có thể giúp nâng cao hiệu suất của IDS, từ đó tăng cường khả năng bảo vệ cho hệ thống mạng.

II. Kỹ thuật so khớp trong phát hiện giả mạo

Giả mạo trên mạng, đặc biệt là giả mạo web, đã trở thành một vấn đề nghiêm trọng trong an ninh mạng. Các kỹ thuật giả mạo ngày càng tinh vi, khiến cho việc phát hiện trở nên khó khăn hơn. Việc áp dụng kỹ thuật so khớp vào phát hiện giả mạo web cho phép so sánh cấu trúc của các trang web để xác định tính hợp lệ. Các thuật toán như K-mean và Naïve Bayes đã được sử dụng để phát hiện các trang web giả mạo. Hệ thống phát hiện giả mạo cần phải nhanh chóng và chính xác để bảo vệ người dùng khỏi các mối đe dọa. Việc sử dụng cây DOM để so sánh các trang web là một phương pháp hiệu quả, giúp phát hiện các trang giả mạo một cách nhanh chóng.

2.1. Phát hiện giả mạo web

Phát hiện giả mạo web là một trong những thách thức lớn trong an ninh mạng hiện nay. Các trang web giả mạo thường có cấu trúc tương tự như trang web hợp lệ, điều này làm cho việc phát hiện trở nên khó khăn. Việc áp dụng kỹ thuật so khớp vào việc so sánh cấu trúc của các trang web giúp phát hiện các trang giả mạo một cách hiệu quả. Các nghiên cứu đã chỉ ra rằng việc sử dụng cây DOM để so sánh có thể giúp phát hiện nhanh chóng các trang web giả mạo. Điều này không chỉ bảo vệ người dùng mà còn giúp duy trì uy tín của các tổ chức trên mạng.

III. Ứng dụng thực tiễn của kỹ thuật so khớp

Kỹ thuật so khớp không chỉ có ứng dụng trong phát hiện xâm nhập và giả mạo mà còn có thể được áp dụng trong nhiều lĩnh vực khác nhau. Việc phát triển các thuật toán so khớp mới có thể giúp cải thiện hiệu suất của các hệ thống bảo mật. Các nghiên cứu đã chỉ ra rằng việc tối ưu hóa các thuật toán so khớp có thể giúp giảm thời gian xử lý và tăng cường khả năng phát hiện. Điều này có ý nghĩa quan trọng trong việc bảo vệ thông tin và tài nguyên của các tổ chức. Hệ thống phát hiện xâm nhập và giả mạo cần phải được cải tiến liên tục để đối phó với các mối đe dọa ngày càng tinh vi.

3.1. Tương lai của kỹ thuật so khớp

Tương lai của kỹ thuật so khớp trong an ninh mạng rất hứa hẹn. Với sự phát triển của công nghệ, các thuật toán so khớp sẽ ngày càng trở nên tinh vi hơn. Việc áp dụng trí tuệ nhân tạo và học máy vào các thuật toán so khớp có thể giúp nâng cao khả năng phát hiện và ngăn chặn các cuộc tấn công. Các nghiên cứu hiện tại đang tập trung vào việc phát triển các phương pháp mới để cải thiện hiệu suất của hệ thống phát hiện xâm nhập và giả mạo. Điều này không chỉ giúp bảo vệ thông tin mà còn góp phần nâng cao an ninh mạng toàn cầu.

Nội dung chính

Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của các dịch vụ trực tuyến và thương mại điện tử, vấn đề an toàn thông tin và an ninh mạng ngày càng trở nên cấp thiết. Theo các báo cáo an ninh mạng được trích dẫn trong văn bản, thiệt hại kinh tế toàn cầu do tội phạm mạng gây ra trong năm 2012 đã lên tới 388 tỷ USD (tăng mạnh so với mức 114 tỷ USD năm 2011). Năm 2013 ghi nhận các đợt tấn công từ chối dịch vụ phân tán (DDoS) với lưu lượng đạt mốc 300 Gbps, tiệm cận tổng băng thông Internet của Việt Nam tại thời điểm đó (khoảng 361 Gbps). Tại Việt Nam, quốc gia đứng thứ 18 trong 20 nước có lượng người dùng Internet lớn nhất thế giới và xếp thứ 11 toàn cầu về nguy cơ bị tấn công mạng, số lượng các vụ tấn công có chủ đích gia tăng từ 77 cuộc mỗi ngày lên 82 cuộc mỗi ngày. Bên cạnh xâm nhập mạng, vấn nạn lừa đảo và giả mạo (phishing/fake web) cũng gia tăng liên tục với tốc độ khoảng 50% mỗi năm theo thống kê của Tổ chức Chống lừa đảo Quốc tế (APWG).

Trong các hệ thống phát hiện và ngăn chặn xâm nhập mạng (IDS/IPS), kỹ thuật so khớp mẫu (pattern matching) đóng vai trò trung tâm để kiểm tra nội dung gói tin nhằm đối sánh với các dấu hiệu nhận dạng tấn công đã biết. Tuy nhiên, khi kích thước tập luật và số lượng mẫu tấn công gia tăng nhanh chóng, các thuật toán so khớp mẫu truyền thống tích hợp trong các hệ thống mã nguồn mở như Snort bộc lộ hạn chế lớn về suy giảm hiệu năng xử lý và gia tăng thời gian thực thi. Mặt khác, đối với bài toán phát hiện website giả mạo, các giải pháp so sánh cấu trúc dựa trên mô hình đối tượng tài liệu (Document Object Model - DOM) đòi hỏi các thuật toán so khớp đồ thị và so khớp cây hiệu quả, do cây DOM là một dạng cấu trúc đồ thị đặc biệt. Khoảng trống nghiên cứu đặt ra là cần cải tiến các thuật toán so khớp đa mẫu nhằm giảm thiểu không gian bộ nhớ và thời gian tính toán trên hệ thống phát hiện xâm nhập, đồng thời phát triển giải thuật so khớp đồ thị phục vụ nhận dạng website giả mạo.

Mục tiêu nghiên cứu

Luận án xác định hai nhóm mục tiêu nghiên cứu chính:

1. Nghiên cứu về hệ thống phát hiện xâm nhập: Phát triển và ứng dụng các thuật toán so khớp mẫu vào việc xây dựng hệ thống phát hiện xâm nhập mạng.
   • (i) Phân tích, đánh giá hiệu năng và thời gian thực hiện của các thuật toán so khớp mẫu hiện có trên hệ thống Snort.
   • (ii) Đưa ra các cải tiến cho thuật toán so khớp đa mẫu Aho-Corasick (AC) bằng kỹ thuật nén dòng và bảng chỉ số nhằm nâng cao hiệu quả sử dụng bộ nhớ và tốc độ xử lý.
   • (iii) Đề xuất thuật toán so khớp đa mẫu mới dựa trên việc xây dựng biểu đồ hướng cấu trúc các mẫu kết hợp với danh sách liên kết để giảm thời gian so khớp đồng thời nhiều mẫu.
2. Nghiên cứu về giả mạo Web: Phát triển các thuật toán so khớp đồ thị và ứng dụng vào bài toán phát hiện các trang web giả mạo.
   • (i) Đưa ra thuật toán mới dựa trên giải thuật di truyền (Genetic Algorithm - GA) để so khớp đồ thị không chính xác, áp dụng cho các lớp đồ thị vô hướng, có hướng, có trọng số và gán nhãn.
   • (ii) Ứng dụng giải thuật so khớp đồ thị vào việc so sánh cấu trúc cây DOM (DOM-Tree) giữa các trang web để nhận diện website giả mạo.

Đối tượng và phạm vi nghiên cứu

• Đối tượng nghiên cứu: Các thuật toán so khớp chuỗi (đơn mẫu, đa mẫu, chính xác, xấp xỉ); các thuật toán so khớp đồ thị (đẳng cấu đồ thị, đẳng cấu đồ thị con, so khớp đồ thị thuộc tính/không chính xác); hệ thống phát hiện xâm nhập mạng (kiến trúc NIDS, HIDS, tập luật Snort); cấu trúc cây DOM của các trang web HTML/XML.
• Phạm vi nghiên cứu: Tối ưu hóa thuật toán so khớp chuỗi trên hệ thống phát hiện xâm nhập Snort với các tập luật chuẩn; giải thuật di truyền cho bài toán so khớp đồ thị với các tập đỉnh có quy mô khác nhau (dưới 10 đỉnh, từ 10 đến 20 đỉnh, và trên 20 đỉnh); so khớp cây DOM kết hợp dấu hiệu hiển thị trực quan (visual cue) để phát hiện web lừa đảo.

---

Tổng quan tài liệu và vị trí của luận án

Luận án đã hệ thống hóa các công trình nghiên cứu trong và ngoài nước liên quan đến hai trục nội dung chính:

Các hướng nghiên cứu về so khớp chuỗi và lọc gói tin

• So khớp đơn mẫu cổ điển: Thuật toán Brute Force với độ phức tạp $O(n \cdot m)$; thuật toán Knuth-Morris-Pratt (KMP, 1972) dựa trên tiền tố và mảng Next; thuật toán Boyer-Moore (BM, 1977) kiểm tra từ phải sang trái kết hợp hai cơ chế dịch chuyển Good-suffix và Bad-character; thuật toán Boyer-Moore-Horspool (BMH, 1980) sử dụng thủ tục tìm ký tự đầu tiên (SFC) và quét ký tự tần suất thấp nhất (SLFC); thuật toán Apostolico-Giancarlo (1986); thuật toán Quick Search (1990) dùng bảng qsBC; các biến thể Boyer-Moore-Smith (1991), Colussi (1991), Raita (1992), Turbo-BM (1994), Berry-Ravindran (1999).
• So khớp dựa trên mô hình Automat và bảng băm: Thuật toán Automaton Matcher (1974); thuật toán Aho-Corasick (AC, 1975) mở rộng KMP cho tập đa mẫu sử dụng mô hình tự động hữu hạn với ba hàm Goto, Failure, Output; thuật toán Commentz-Walter (CW, 1979) kết hợp BM và AC; Backward Dawg Matching (BDM, 1998); Backward Oracle Matching (BOM, 1999); thuật toán Karp-Rabin (1987) dựa trên hàm băm; thuật toán Wu-Manber (WM, 1994) sử dụng các bảng SHIFT, HASH và PREFIX; thuật toán Multi-Phase Dynamic Hash (MDH) của Zhou mở rộng từ WM; thuật toán Character Index Aho-Corasick (CIAC, 2005); thuật toán Recursive Shift Indexing (RSI, 2005) của Bo Xu, Xin Zhou và Jun Li.
• Kỹ thuật xử lý song song và lọc gói: Kỹ thuật Bit-Parallelism của Baeza-Yates và Gonnet (2010); thuật toán BRSS của Abdulwahab và cộng sự; giải pháp lọc Exscind của Aldwairi và Alansari (2011) kết hợp bộ lọc Bloom; cơ chế Wu-Manber song song của Kharbutli và cộng sự (2011) với các kỹ thuật Shared Position và Trace Distribution; thuật toán TFD của Zhenlong Yuan và cộng sự (2013) dùng cho lọc URL lớn tốc độ cao; các mô hình bộ lọc gói tin gồm CSPF, BPF, MPF, PATHFINDER, DPF và BPF+.

Các hướng nghiên cứu về so khớp đồ thị và phát hiện website giả mạo

• Kỹ thuật phát hiện website giả mạo: Thuật toán TF-IDF kết hợp công cụ tìm kiếm trong hệ thống Cantina (Đại học Carnegie Mellon); bộ lọc Bayesian phát hiện lừa đảo zero-day (Đại học Iowa); phương pháp so sánh độ tương đồng hiển thị hình ảnh của các nhóm tác giả Hồng Kông; giải pháp kết hợp thuật toán K-means và Naïve Bayes của Kranti và cộng sự.
• Kỹ thuật so khớp đồ thị: Tiếp cận dựa trên đồ thị khoảng cách (Graph Edit Distance - GED); đồ thị đặc trưng (Graph kernels) trong không gian Hilbert; đồ thị nhúng (Graph embedding); thuật toán SI-COBRA (2005) của Olmos, Gonzalez và Osorio sử dụng chuỗi mã tuyến tính để tìm đẳng cấu đồ thị con; cây quyết định của Messmer và Bunke (1998, 1999); mô hình mạng nơ-ron của Hopfield và Huang (1998, 1999), Riviere (2000), Lee và Liu (2002); kỹ thuật phân cụm đồ thị của Sanfeliu và cộng sự (2000), Carcassoni và Hancock (2001); các giải thuật so khớp cây như Simple Tree Matching (STM), Partial Tree Alignment và NET.

Khoảng trống nghiên cứu được lựa chọn giải quyết

Luận án tập trung xử lý vấn đề quá tải bộ nhớ và suy giảm tốc độ của thuật toán Aho-Corasick khi tích hợp trong hệ thống Snort, đồng thời giải quyết bài toán so khớp đồ thị phức tạp áp dụng vào việc đối sánh cấu trúc cây DOM để nhận dạng trang web giả mạo mà các phương pháp so sánh văn bản hay lọc danh sách đen chưa tối ưu.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

• Lý thuyết so khớp chuỗi: Cho bảng chữ cái hữu hạn $\Sigma$, đoạn văn bản $T[1..n]$ và mẫu $P[1..m]$. So khớp chuỗi là bài toán xác định các vị trí xuất hiện của $P$ trong $T$. Hệ thống phân loại dựa trên: số lượng mẫu (đơn mẫu, đa mẫu); thứ tự duyệt (tiền tố, hậu tố, thừa số); độ chính xác (chính xác, gần đúng dùng khoảng cách Hamming hoặc Levenshtein).
• Lý thuyết đồ thị và bài toán đẳng cấu:
  • Định nghĩa đồ thị gán nhãn: $G = {V, E, L_V, L_E, \alpha, \beta}$, trong đó $V$ là tập đỉnh, $E$ là tập cạnh, $L_V, L_E$ là tập nhãn của đỉnh và cạnh, $\alpha: V \to L_V$ và $\beta: E \to L_E$ là các hàm gán nhãn.
  • Ma trận kề và ma trận hoán vị: Ma trận kề $M = (m_{i,j}){n \times n}$. Ma trận hoán vị $P = (p{i,j}){n \times n}$ thỏa mãn $p{i,j} \in {0,1}$ và tổng mỗi hàng, mỗi cột đều bằng 1.
  • Đẳng cấu đồ thị: Hai đồ thị $G_M$ và $G_D$ với hai ma trận kề $M_1, M_2$ đẳng cấu với nhau khi và chỉ khi tồn tại ma trận hoán vị $P$ sao cho: $$M_2 = P \cdot M_1 \cdot P^T$$
  • Đẳng cấu đồ thị con: Tồn tại ma trận hoán vị $P$ sao cho: $$M_1 = S_{m,m}(P \cdot M_2 \cdot P^T)$$ với $S_{m,m}(M)$ là ma trận thu được sau khi xóa các hàng và cột từ $m+1$ đến $n$.
• Mô hình đối tượng tài liệu (DOM): Chuẩn của W3C biểu diễn cấu trúc phân cấp của trang HTML/XML dưới dạng cây (DOM-Tree), cho phép ánh xạ các thành phần giao diện và nội dung thành các nút và quan hệ cha-con.

Phương pháp nghiên cứu

• Phương pháp giải tích và tối ưu thuật toán: Thiết kế cấu trúc dữ liệu nén mảng CSR (Compressed Sparse Row) và lập bảng chỉ số trạng thái nhằm tối ưu hóa hàm chuyển đổi trạng thái của mô hình tự động hữu hạn; xây dựng thuật toán danh sách liên kết con trỏ cho cấu trúc mẫu.
• Phương pháp toán học phỏng sinh học: Thiết lập giải thuật di truyền (GA) với không gian tìm kiếm là các ma trận hoán vị/chuỗi mã hóa đỉnh, định nghĩa hàm thích nghi (fitness function) dựa trên số lượng cạnh và nhãn tương ứng được bảo toàn giữa hai đồ thị.
• Phương pháp thực nghiệm định lượng:
  • Cài đặt, đo đạc thời gian thực thi và dung lượng bộ nhớ tiêu thụ trên hệ thống phát hiện xâm nhập mã nguồn mở Snort với các bộ luật chuẩn.
  • Mô phỏng so khớp đồ thị trên ba nhóm quy mô số đỉnh ($|V| < 10$, $10 \le |V| \le 20$, $|V| > 20$) với ba loại đồ thị: vô hướng, có trọng số và gán nhãn.
  • Đo lường tỷ lệ phát hiện đúng/sai trên tập dữ liệu cây DOM của các website thật và website giả mạo.

---

Nội dung chính theo từng chương

Chương 1: TỔNG QUAN VỀ SO KHỚP

Chương này trình bày hệ thống lý thuyết toàn diện về các bài toán so khớp chuỗi và so khớp đồ thị, bao gồm:

1. Phân loại thuật toán so khớp chuỗi:
   • So khớp chính xác cổ điển: Phân tích chi tiết cơ chế hoạt động, bảng dịch chuyển và độ phức tạp của Brute Force, KMP, Boyer-Moore, Boyer-Moore-Horspool, Apostolico-Giancarlo và Quick Search.
   • So khớp dựa trên mô hình Automat và bảng băm: Phân tích cấu trúc ba hàm Goto, Failure, Output trong thuật toán Aho-Corasick; cơ chế kết hợp giữa BM và AC trong thuật toán Commentz-Walter; kỹ thuật băm khối $b$ ký tự trong thuật toán Wu-Manber.
   • So khớp xấp xỉ: Phân loại các tiếp cận theo quy hoạch động, phương pháp đếm, mô hình automat không tất định, xử lý song song bit và phương pháp lọc.
2. Kỹ thuật lọc gói tin trong mạng: Phân tích cơ chế và hạn chế của các bộ lọc gói tin mạng: CSPF (dựa trên cây logic), BPF (dựa trên đồ thị dòng điều khiển CFG), MPF (tối ưu cho xử lý cổng cuối), PATHFINDER (biểu diễn dạng ô/đường), DPF (sinh mã động) và BPF+ (loại bỏ thuộc tính dư thừa bằng thuật toán luồng dữ liệu).
3. Lý thuyết so khớp đồ thị:
   • Thiết lập hệ thống định nghĩa hình học từ Định nghĩa 1.1 đến 1.9 về đồ thị vô hướng, có hướng, có trọng số, đồ thị gán nhãn, ma trận kề, ma trận hoán vị, đẳng cấu đồ thị và đẳng cấu đồ thị con.
   • Phân loại hai nhánh bài toán: so khớp đồ thị chính xác (đẳng cấu đồ thị, đẳng cấu đồ thị con) và so khớp đồ thị không chính xác (so khớp đồ thị thuộc tính, so khớp đồ thị con thuộc tính).
   • Hệ thống hóa các phương pháp giải: đồ thị khoảng cách (GED), hàm đặc trưng (Graph kernels), đồ thị nhúng, giải thuật di truyền, cây quyết định (Messmer và Bunke), mạng nơ-ron và kỹ thuật phân cụm.

---

Chương 2: ỨNG DỤNG SO KHỚP MẪU TRONG QUÁ TRÌNH PHÁT HIỆN XÂM NHẬP MẠNG

Chương 2 tập trung vào việc nghiên cứu hiện tượng xâm nhập mạng, phân tích kiến trúc IDS/Snort và đề xuất các giải pháp cải tiến thuật toán so khớp đa mẫu:

1. Kỹ thuật xâm nhập mạng và kiến trúc hệ thống bảo vệ

• Các hình thức tấn công:
  • Tấn công thăm dò: Sniffing (nghe lén chủ động qua đầu độc ARP, DHCP, DNS; nghe lén bị động qua Hub), Ping Sweep (ICMP Echo Request/Reply), Port Scanning (Nmap quét TCP/UDP).
  • Tấn công thâm nhập: Truy cập trái phép, thao túng dữ liệu, cửa sau (backdoor), tấn công trung gian (Man-in-the-Middle), leo thang đặc quyền.
  • Tấn công từ chối dịch vụ: DoS cổ điển (SYN flood, Smurf, UDP flood), DDoS và DRDoS.
  • Tấn công sử dụng mã độc: Bom logic, Trojan horse, Sâu máy tính (Worm), Xác chết (Zombies/Botnet).
• Hệ thống phát hiện xâm nhập: Phân biệt hệ thống phát hiện xâm nhập mạng (NIDS), trạm chủ (HIDS) và phân tích cấu trúc xử lý gói tin của hệ thống mã nguồn mở Snort.

2. Các cải tiến thuật toán đề xuất trong chương

• Cải tiến thuật toán Aho-Corasick bằng kỹ thuật nén dòng và bảng chỉ số:
  • Tối ưu hóa hàm chuyển trạng thái Goto bằng kỹ thuật nén ma trận thưa theo hàng (CSR - Compressed Sparse Row), giúp loại bỏ các phần tử rỗng (giá trị 0) trong ma trận trạng thái của DFA.
  • Nén hàm thất bại (Failure function) thông qua bảng chỉ số, giảm thiểu các nút trạng thái dư thừa và thu hẹp không gian bộ nhớ lưu trữ mô hình automat.
• Thuật toán đề xuất mới xây dựng biểu đồ hướng kết hợp danh sách liên kết:
  • Giai đoạn tiền xử lý: Xây dựng biểu đồ hướng cấu trúc của tập mẫu kết hợp với cấu trúc danh sách liên kết con trỏ.
  • Giai đoạn tìm kiếm: Duyệt gói tin dựa trên cấu trúc con trỏ liên kết, giảm thiểu các phép so sánh trùng lặp và tăng tốc độ tìm kiếm đồng thời đa mẫu.

3. Bảng số liệu thực nghiệm trong chương

Luận án tiến hành đo đạc thực nghiệm trên hệ thống Snort với các tập luật chuẩn, so sánh thuật toán AC gốc, AC tối ưu (AC-OPT), thuật toán Commentz-Walter (CW), thuật toán Wu-Manber (WM) và thuật toán đề xuất mới:

Phương pháp / Thuật toán	Cấu trúc tối ưu hóa	Mục tiêu cải thiện	Nền tảng kiểm nghiệm
AC cải tiến (CSR & Bảng chỉ số)	Nén ma trận Goto bằng CSR, nén hàm Failure bằng bảng chỉ số	Giảm dung lượng bộ nhớ không gian trạng thái	Snort (Tập luật chuẩn)
Thuật toán đề xuất mới	Biểu đồ hướng cấu trúc mẫu kết hợp danh sách liên kết con trỏ	Giảm thời gian tìm kiếm và so khớp đa mẫu	Snort (Tập luật chuẩn)

---

Chương 3: ỨNG DỤNG SO KHỚP ĐỒ THỊ TRONG QUÁ TRÌNH PHÁT HIỆN CÁC TRANG WEB GIẢ MẠO

Chương 3 giải quyết bài toán phát hiện website giả mạo bằng phương pháp so khớp cấu trúc trang web dựa trên lý thuyết đồ thị và cây DOM:

1. Kỹ thuật giả mạo Web và các tiếp cận phát hiện

• Phân tích các kỹ thuật lừa đảo trực tuyến (Phishing) và các phương pháp phát hiện hiện có: TF-IDF (Cantina), lọc Bayesian, phân tích độ tương đồng hình ảnh, visual cue, mô hình phân cụm K-means và Naïve Bayes.
• Phân tích sự tương đồng về mặt cấu trúc giữa trang web gốc và trang web giả mạo thông qua việc ánh xạ mã nguồn HTML/XML thành cây DOM (DOM-Tree).

2. Giải thuật di truyền cho bài toán so khớp đồ thị

• Luận án xây dựng giải thuật di truyền (GA) để tìm nghiệm xấp xỉ tối ưu cho bài toán so khớp đồ thị không chính xác:
  • Mã hóa cá thể biểu diễn ánh xạ giữa các tập đỉnh của hai đồ thị.
  • Thiết lập hàm thích nghi (fitness function) phản ánh mức độ trùng khớp về cấu trúc cạnh, trọng số và nhãn giữa đồ thị mẫu ($G_M$) và đồ thị dữ liệu ($G_D$).
  • Thực hiện các toán tử di truyền (chọn lọc, lai ghép, đột biến) để tiến hóa quần thể qua các thế hệ.
• Kết quả mô phỏng giải thuật di truyền: Thực nghiệm đánh giá độ thích nghi qua các thế hệ trên 3 nhóm đồ thị với các quy mô đỉnh khác nhau:
  • Đồ thị vô hướng: tập đỉnh $<10$, từ $10-20$, và $>20$ đỉnh.
  • Đồ thị có trọng số: tập đỉnh $<10$, từ $10-20$, và $>20$ đỉnh.
  • Đồ thị gán nhãn: tập đỉnh $<10$, từ $10-20$, và $>20$ đỉnh.

3. Thuật toán so khớp DOM-Tree và phát hiện web giả mạo

• Xây dựng cây DOM từ tài liệu HTML, chuẩn hóa và trích xuất các thuộc tính visual cue (thẻ hiển thị, bảng, vị trí đối tượng).
• Áp dụng thuật toán so khớp đồ thị/cây để tính toán độ tương đồng giữa cây DOM của trang web bị nghi ngờ và cây DOM của trang web chuẩn.
• Đánh giá hiệu năng và độ chính xác so với thuật toán Simple Tree Matching (STM):

Phương pháp so khớp cây / đồ thị	Đối tượng cấu trúc	Tiêu chí đánh giá thực nghiệm
Giải thuật di truyền (GA)	Đồ thị vô hướng, có trọng số, gán nhãn ($<10$, $10-20$, $>20$ đỉnh)	Độ thích nghi qua các thế hệ, tốc độ hội tụ
So khớp DOM-Tree (GA đề xuất vs. STM)	Cây DOM trang web kết hợp visual cue	Tỷ lệ % phát hiện đúng, tỷ lệ phát hiện sai theo các ngưỡng

---

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả khoa học và đóng góp cụ thể sau:

1. Về mặt lý thuyết và thuật toán so khớp chuỗi:
   • Đề xuất giải pháp cải tiến thuật toán Aho-Corasick thông qua việc tích hợp kỹ thuật nén dòng CSR cho ma trận chuyển trạng thái hàm Goto và bảng chỉ số cho hàm Failure, giúp tối ưu hóa không gian trạng thái của mô hình tự động hữu hạn.
   • Xây dựng thuật toán so khớp đa mẫu mới dựa trên mô hình biểu đồ hướng kết hợp danh sách liên kết con trỏ, cho phép tối ưu hóa giai đoạn tiền xử lý và rút ngắn thời gian tìm kiếm khi số lượng mẫu tăng cao.
2. Về mặt lý thuyết và thuật toán so khớp đồ thị:
   • Xây dựng giải thuật di truyền cải tiến cho bài toán so khớp đồ thị không chính xác, có khả năng áp dụng đồng thời cho nhiều lớp đồ thị khác nhau (đồ thị vô hướng, đồ thị có hướng, đồ thị có trọng số và đồ thị gán nhãn).
   • Đưa ra mô hình so khớp cây DOM dựa trên giải thuật so khớp đồ thị kết hợp các thuộc tính visual cue, phục vụ nhận dạng website lừa đảo với độ chính xác cao.
3. Về mặt thực tiễn và ứng dụng:
   • Cài đặt và tích hợp thử nghiệm thành công các thuật toán so khớp chuỗi cải tiến vào hệ thống phát hiện xâm nhập Snort, kiểm nghiệm hiệu năng thực tế trên các tập luật tấn công mạng chuẩn.
   • Cung cấp giải pháp kỹ thuật có khả năng hỗ trợ phát hiện các website giả mạo dựa trên đối sánh cấu trúc DOM tự động.

---

Hạn chế và hướng nghiên cứu tiếp

Dựa trên phạm vi và nội dung trình bày trong luận án, một số hạn chế và hướng mở rộng được xác định gồm:

• Hạn chế:
  • Cấu trúc nén của thuật toán Aho-Corasick và biểu đồ danh sách liên kết phụ thuộc vào đặc tính phân bố ký tự của tập luật; khi tập luật có cấu trúc biến đổi phức tạp, chi phí khởi tạo ban đầu có thể tăng.
  • Việc áp dụng giải thuật di truyền cho bài toán so khớp đồ thị gặp thách thức về thời gian hội tụ khi số lượng đỉnh đồ thị tăng lên quy mô rất lớn (trên 20 đỉnh đòi hỏi số thế hệ tiến hóa nhiều hơn).
  • Cấu trúc cây DOM của các trang web hiện đại ngày càng phức tạp do sử dụng nhiều mã script động, đòi hỏi quá trình trích xuất cây phải liên tục cập nhật theo thời gian thực.
• Hướng nghiên cứu tiếp:
  • Tiếp tục tối ưu hóa thuật toán so khớp đa mẫu đề xuất để có thể triển khai trên các thiết bị phần cứng chuyên dụng hoặc xử lý song song trên card đồ họa (GPU).
  • Mở rộng giải thuật di truyền song song để tăng tốc độ so khớp các đồ thị quy mô lớn.
  • Nâng cao năng lực của mô hình phát hiện web giả mạo bằng cách kết hợp cây DOM với các đặc trưng ngữ nghĩa và kỹ thuật học máy.

---

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu phục vụ cho các nhóm đối tượng:

• Nghiên cứu sinh, học viên cao học và giảng viên: Chuyên ngành Cơ sở toán học cho Tin học, Khoa học Máy tính, Toán ứng dụng và An toàn thông tin; đặc biệt có giá trị tham khảo về phương pháp luận nghiên cứu lý thuyết đồ thị ứng dụng, các mô hình automat hữu hạn và giải thuật di truyền.
• Kỹ sư an toàn thông tin và phát triển phần mềm: Các chuyên gia nghiên cứu và phát triển hệ thống phát hiện xâm nhập mạng (NIDS/IPS), tường lửa lọc gói tin tốc độ cao và các công cụ bảo mật web dựa trên phân tích cấu trúc dữ liệu.
• Các phần nội dung đáng tham khảo:
  • Chương 1: Tài liệu tổng hợp toàn diện các thuật toán so khớp chuỗi cổ điển và hiện đại, kèm theo hệ thống định nghĩa toán học chuẩn tắc về đẳng cấu đồ thị.
  • Chương 2: Kỹ thuật tối ưu hóa không gian trạng thái automat và phương pháp tích hợp thuật toán vào hệ thống Snort.
  • Chương 3: Thiết kế giải thuật di truyền cho bài toán so khớp đồ thị gán nhãn và phương pháp xây dựng, so khớp cây DOM.

---

Câu hỏi thường gặp

1. Luận án giải quyết vấn đề gì trong hệ thống phát hiện xâm nhập mạng Snort?

Luận án giải quyết vấn đề suy giảm hiệu năng và gia tăng thời gian thực thi của Snort khi số lượng mẫu nhận dạng tấn công tăng lên. Tác giả đề xuất hai giải pháp: cải tiến thuật toán Aho-Corasick bằng kỹ thuật nén dòng CSR và bảng chỉ số để tiết kiệm bộ nhớ; đồng thời phát triển thuật toán so khớp mới sử dụng biểu đồ hướng kết hợp danh sách liên kết con trỏ để tăng tốc độ so khớp đồng thời đa mẫu.

2. Hai đồ thị được coi là đẳng cấu với nhau khi thỏa mãn điều kiện toán học nào trong luận án?

Theo Định nghĩa 1.8 của luận án, cho hai đồ thị $G_M$ và $G_D$ với hai ma trận kề tương ứng $M_1$ và $M_2$, hai đồ thị này được gọi là đẳng cấu với nhau nếu tồn tại một ma trận hoán vị $P$ sao cho: $$M_2 = P \cdot M_1 \cdot P^T$$ Ma trận hoán vị $P$ đóng vai trò là một hàm song ánh ánh xạ các đỉnh của đồ thị $G_M$ vào $G_D$ và ngược lại.

3. Giải thuật di truyền (GA) được tác giả ứng dụng cho những lớp đồ thị nào và trên những quy mô nào?

Giải thuật di truyền được thiết kế để giải quyết bài toán so khớp đồ thị không chính xác trên ba lớp đồ thị: đồ thị vô hướng, đồ thị có trọng số và đồ thị gán nhãn. Quá trình mô phỏng thực nghiệm được tiến hành trên 3 nhóm quy mô số đỉnh: nhóm có số đỉnh nhỏ hơn 10 ($|V| < 10$), nhóm có số đỉnh từ 10 đến 20 ($10 \le |V| \le 20$), và nhóm có số đỉnh lớn hơn 20 ($|V| > 20$).

4. Tại sao việc phát hiện website giả mạo lại được chuyển về bài toán so khớp cây DOM và so khớp đồ thị?

Do trang web giả mạo có mục đích đánh lừa người dùng nên thường có cấu trúc và giao diện tương tự trang web gốc. Cấu trúc tài liệu HTML/XML của trang web được chuẩn hóa theo mô hình đối tượng tài liệu (DOM) dưới dạng cây phân cấp (DOM-Tree). Vì cây là một dạng đặc biệt của đồ thị, việc so sánh độ tương đồng giữa website thật và website nghi ngờ được chuyển đổi thành bài toán so khớp cây DOM và so khớp đồ thị kết hợp các dấu hiệu trực quan (visual cue).

5. Thuật toán Aho-Corasick nguyên bản gồm những hàm nào và tác giả đã cải tiến những hàm nào?

Thuật toán Aho-Corasick nguyên bản sử dụng mô hình tự động hữu hạn dựa trên sự kết hợp của 3 hàm: hàm chuyển trạng thái (Goto function), hàm thất bại (Failure function) và hàm đầu ra (Output function). Tác giả đã cải tiến hàm Goto bằng kỹ thuật nén dòng CSR (Compressed Sparse Row) và cải tiến hàm Failure bằng bảng chỉ số nhằm tối ưu hóa không gian trạng thái lưu trữ.

---

Kết luận

Luận án tiến sĩ "Phát triển một số kỹ thuật so khớp ứng dụng trong quá trình phát hiện xâm nhập và giả mạo trên mạng" của tác giả Lê Đăng Nguyên đã giải quyết hai bài toán kỹ thuật cốt lõi trong an ninh thông tin: tối ưu hóa tốc độ và không gian bộ nhớ của thuật toán so khớp đa mẫu trên hệ thống phát hiện xâm nhập mạng Snort, đồng thời phát triển giải thuật di truyền so khớp đồ thị ứng dụng vào đối sánh cây DOM để phát hiện website lừa đảo. Bằng việc kết hợp chặt chẽ giữa lý thuyết cơ sở toán học (mô hình tự động hữu hạn, lý thuyết đồ thị, giải thuật tiến hóa) và cài đặt thực nghiệm định lượng, công trình đã đóng góp các thuật toán cải tiến có tính ứng dụng thực tiễn cao trong lĩnh vực giám sát an ninh mạng và bảo mật web.

Trích đoạn nội dung tài liệu

Chương 1 trình bày tổng quan về so khớp chuỗi và so khớp đồ thị cùng các ứng dụng. Trong đó, luận án tập trung giới thiệu các thuật toán so khớp đơn mẫu và đa mẫu, so khớp chính xác và không chính xác được áp dụng trong việc phát hiện xâm nhập mạng; - Chương 2 giới thiệu về các kỹ thuật xâm nhập mạng. Luận án đã phân tích, đánh giá một số hướng tiếp cận liên quan đến hệ thống phát hiện xâm nhập mạng để thấy được ưu, nhược điểm của từng giải pháp. Từ đó xác định được mục tiếp, cách tiếp cận của luận án là.

Luận án đã trình bày hai cải tiến thuật toán bằng kĩ thuật nén dòng và bảng chỉ số, và đưa ra thuật toán mới dựa trên kĩ thuật con trỏ được ứng dụng trong hệ thống phát hiện xâm nhập mạng. 4 z - Chương 3 luận án giới thiệu về các kỹ thuật giả mạo trang web. Từ đó đề xuất ứng dụng thuật toán di truyền trong việc so khớp đồ thị, ứng dụng việc so khớp đồ thị trong so sánh cây DOM để phát hiện giả mạo trong mạng. Cuối luận án là phần kết luận và hướng phát triển của luận án.

Danh mục các tài liệu tham chiếu, trích dẫn và tham khảo của luận án, cùng danh sách các tài liệu do nghiên cứu sinh công bố cùng tập thể cán bộ nghiên cứu, giáo viên hướng dẫn, được liệt kê cuối luận án. TỔNG QUAN VỀ SO KHỚP Trong bối cảnh tiến trình hội nhập, vấn đề an ninh mạng và bảo mật dữ liệu đang trở nên rất được quan tâm. Khi cơ sở hạ tầng và các công nghệ mạng đã đáp ứng tốt các yêu cầu về băng thông, chất lượng dịch vụ, đồng thời thực trạng tấn công trên mạng đang ngày một gia tăng thì vấn đề bảo mật càng được chú trọng hơn. Không chỉ các nhà cung cấp dịch vụ Internet, các cơ quan chính phủ mà các doanh nghiệp, tổ chức cũng có ý thức hơn về an toàn thông tin.

Triển khai các ứng dụng và dịch vụ trên Internet cần có các cơ chế bảo vệ chặt chẽ, an toàn, nhằm góp phần duy trì tính bền vững cho hệ thống thông tin của doanh nghiệp đó. Tất cả chúng ta đều hiểu rằng giá trị thông tin của doanh nghiệp là tài sản vô giá. Không chỉ thuần túy về mặt vật chất, những giá trị khác không thể đo đếm được như uy tín của họ với khách hàng sẽ ra sao, nếu những thông tin giao dịch với khách hàng bị đánh cắp, rồi sau đó bị lợi dụng với những mục đích khác nhau,… Các thông tin và các dịch vụ này làm cho mạng máy tính trở thành mục tiêu hấp dẫn cho sự lạm dụng và tổn thương đến cộng đồng người sử dụng. Thêm nữa, giả mạo trên mạng là một loại tội phạm kỹ thuật xã hội đáng chú ý trên mạng.

Giả mạo được báo cáo là vấn nạn Web lần đầu tiên vào năm 2001 của hiệp hội bảo vệ khách hàng, hiệp hội thương mại liên bang của Mỹ và ngày nay nhóm làm việc chống giả mạo APWG đã đưa ra cảnh báo những trang Web giả đang tăng khoảng 50% mỗi năm. Vì thế, bên cạnh việc phát triển các dịch vụ và ứng dụng trên mạng, an ninh thông tin và an toàn hệ thống là một vấn đề hết sức quan trọng cần được quan tâm nghiên cứu thường xuyên. Vấn đề an ninh thông tin và an toàn hệ thống bao gồm rất nhiều chủ đề, tuy nhiên luận án này chỉ tập trung nghiên cứu chính về các thuật toán so khớp ứng dụng trong phát hiện xâm nhập mạng và sự giả mạo trên mạng. So khớp chuỗi 1.

Bài toán so khớp chuỗi So khớp chuỗi (hay đối sánh chuỗi) là việc so sánh một hoặc một vài chuỗi (thường được gọi là mẫu hoặc pattern) với văn bản để tìm nơi và số lần xuất hiện của 6 z chuỗi đó trong văn bản. Gọi Y là tập các dữ liệu và X là một mẫu. So khớp mẫu (Pattern Matching) là tìm ra tất cả các lần xuất hiện của mẫu X trong tập dữ liệu Y. Trong [7], bài toán so khớp mẫu được mô tả như sau: Cho một bảng chữ cái Σ là một tập hữu hạn các ký tự, một mẫu P (P [1.m]) độ dài m và một chuỗi ký tự T (T [1.

Bài toán đặt ra là cần tìm các vị trí xuất hiện của P trong T hoặc P có khớp với một chuỗi con của T hay không? Gọi Σ là một tập hữu hạn các ký tự. Thông thường, các ký tự của cả mẫu tìm kiếm và đoạn văn bản gốc đều nằm trong Σ. Tập Σ tùy từng ứng dụng cụ thể có thể là bảng chữ cái tiếng Anh từ A đến Z thông thường, cũng có thể là một tập nhị phân chỉ gồm hai phần tử 0 và 1 (Σ = {0,1}) hay có thể là tập các ký tự DNA trong sinh học (Σ = {A,C,G,T}). Phương pháp đầu tiên và đơn giản nhất có thể nghĩ đến ngay là lần lượt xét từng vị trí i trong xâu ký tự gốc từ 1 đến n-m+1, so sánh T[i…(i+m-1)] với P[1.m] bằng cách xét từng cặp ký tự một và đưa ra kết quả tìm kiếm.

Dễ thấy độ phức tạp của thuật toán là O(n*m) Các thuật toán so khớp thường sử dụng cơ chế cửa sổ trượt (một khung có kích thước bằng với kích thước của mẫu cần tìm) để so sánh các ký tự của mẫu trong cửa sổ với các ký tự trong văn bản. Tất cả các thuật toán so khớp chuỗi đều có hai giai đoạn là: tiền xử lý và tìm kiếm. Việc đánh giá các thuật toán được thực hiện dựa trên dung lượng bộ nhớ sử dụng và tốc độ so khớp. Các thuật toán so khớp được phân loại theo cách tiếp cận xây dựng thuật toán và số lượng mẫu.

Các thuật toán so khớp chuỗi có thể phân loại theo nhiều tiêu chí: Dựa trên số lượng mẫu, chúng ta có hai loại: so khớp đơn mẫu (single pattern) và so khớp đa mẫu (multiple patterns). Các thuật toán so khớp đơn mẫu chỉ tiến hành so sánh lần lượt từng mẫu P trên văn bản T, còn so khớp đa mẫu cho phép so sánh cùng lúc nhiều mẫu Pi (i=1. Các thuật toán so khớp đã mẫu thường là những cải tiến của so khớp đơn mẫu nhằm nâng cao hiệu quả so khớp. Dựa trên cơ sở thứ tự so sánh: thuật toán so khớp chuỗi có thể được thực hiện theo các thứ tự sau: từ trái sang phải, từ phải sang trái, so sánh tại vị trí cụ thể và so sánh không theo thứ tự nhất định.

7 z Dựa trên độ chính xác của kết quả so khớp: các thuật toán so khớp được chia thành hai loại: so khớp chính xác (Extract String Matching) và so khớp gần đúng (Approximate String Matching). So khớp chính xác là khẳng định mẫu P có xuất hiện ở trong chuỗi T hay không? Còn thuật toán so khớp xấp xỉ chỉ đánh giá sự tương đồng của mẫu P so với mẫu T dựa trên một hàm đo khoảng cách nào đó. Đa số các thuật toán so khớp không chính xác sử dụng khoảng cách Hamming hay khoảng cách Levenshtein với k vị trí khác biệt được thiết lập trước [65]. Dựa trên cơ sở thiết kế thuật toán: Các thuật toán so khớp được chia thành ba loại: - So khớp dựa trên tiền tố (prefix) - So khớp dựa trên hậu tố (suffix) và - So khớp dựa trên các nhân tố (factor).

Chuỗi văn bản T Mẫu P Cửa sổ trượt Hình 1. So khớp dựa trên tiền tố Quá trình so khớp của thuật toán so khớp dựa trên tiền tố được thực hiện bằng cách tìm kiếm từ đầu cửa sổ trượt, tất cả các ký tự trong văn bản T đều được đọc và kiểm tra, nếu không khớp thì dịch chuyển sang ký tự tiếp theo. Đây là chiến lược đơn giản nhất nhưng số lượng phép so sánh lớn nên tốc độ thực hiện chậm (xem Hình 1. Thuật toán so khớp dựa trên hậu tố thực hiện bằng cách tìm kiếm từ cuối cửa sổ trượt, chúng ta không đọc tất cả các ký tự liên tiếp trong văn bản T mà dịch hay bỏ qua các ký tự dựa vào kết quả so sánh các ký tự ở cuối cửa sổ (xem Hình 1.

Đây là cơ sở để giảm số lượng phép so sánh và giảm độ phức tạp của thuật toán. 8 z Chuỗi văn bản T Mẫu P Cửa sổ trượt Hình 1. So khớp dựa trên hậu tố Thuật toán so khớp dựa trên thừa số thực hiện bằng cách tìm kiếm từ cuối cửa sổ trượt, chúng ta không đọc tất cả các ký tự liên tiếp trong văn bản T mà so sánh từng ký tự đặc biệt để đoán nhận tập nhân tố (các mẫu con) của mẫu P ban đầu (Hình 1. Chuỗi vănbản T Mẫu P Cửa sổ trượt Hình 1.

So khớp dựa trên các nhân tố Dựa trên sự thay đổi của mẫu và văn bản: chúng ta có ba loại: - So khớp mẫu thay đổi, văn bản cố định - So khớp mẫu cố định, văn bản thay đổi - So khớp mẫu thay đổi, văn bản thay đổi. Để đánh giá hiệu năng của thuật toán đối sánh chuỗi, chúng ta có thể dựa trên những tiêu chí sau: - Số lần tìm kiếm, duyệt trên mẫu và văn bản - Độ phức tạp thời gian - Tiêu chuẩn được lựa chọn để đối sánh - Số mẫu được so khớp - Kỹ thuật biểu diễn mẫu 1.2 Các thuật toán so khớp chính xác cổ điển 9 z Các kỹ thuật so khớp chính xác cổ điển được xây dựng dựa trên số ký tự được so sánh. Sự khác biệt của các thuật toán là quá trình tính toán xác định số ký tự được dịch chuyển sau mỗi lần so sánh. Việc so sánh có thể được tiến hành từ trái qua phải hay từ phải qua trái, vị trí ký tự so sánh có thể là dựa trên tiền tố, hậu tố,.

Các thuật toán so khớp điển hình có thể kể đến gồm: Thuật toán Brute Force [7]: đây là thuật toán đầu tiên và đơn giản nhất được biết đến. Thuật toán Brute Force kiểm tra tất cả các vị trí trong văn bản giữa 0 và n - m, có xuất hiện của mẫu P hay không. Sau đó, sau mỗi lần so sánh sẽ dịch chuyển mẫu đúng một vị trí sang bên phải. Thuật toán Brute Force không yêu cầu giai đoạn tiền xử lý và một không gian thêm liên tục thêm vào mẫu và các văn bản.

Trong giai đoạn tìm kiếm so sánh ký tự văn bản có thể được thực hiện theo thứ tự. Độ phức tạp của giai đoạn tìm kiếm này là O(m  n) .