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) .