Luận án 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

Nội dung tài liệu: Luận án 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

1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________________ Lê Đăng Nguyên 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 Chuyªn ngµnh : Cơ sở toán học cho Tin học M· sè: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2015
2. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN _______________________ Lê Đăng Nguyên 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 Chuyªn ngµnh : Cơ sở toán học cho Tin học M· sè: 62 46 01 10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS.TS. Lê Trọng Vĩnh 2. PGS.TS. Đỗ Trung Tuấn Hà Nội - 2015
3. LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận án này là trung thực và chưa từng được ai côngbốtrong bất kỳ công trình nghiên cứu nào khác. Tác giả luận án Lê Đăng Nguyên i
4. LỜI CẢM ƠN Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới PGS.TS. Lê Trọng Vĩnh, PGS.TS Đỗ Trung Tuấn đã tận tâm hướng dẫn và giúp đỡ tác giả trong suốt quá trình thực hiện luận án này. Tác giả cũng xin gửi lời cảm ơn đến các thầygiáo, cô giáo trong bộ môn Tin học, khoa Toán - Cơ - Tin học, trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã góp ý quý báu giúp đỡ tác giả trong quá trình nghiên cứu thực hiện luận án. Tác giả cũng xin chân thành cảm ơn tất cả các thầy, các cô trong Ban Chủ nhiệm Khoa Toán - Cơ - Tin học, trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, Ban Giám hiệu trường Đại học Hải Phòng, Phòng Đào tạo, Khoa Công nghệ Thông tin, trường Đại học Hải Phòng cùng toàn thể các anh chị emđồng nghiệp, bạn bè đã luôn động viên, tạo mọi điều kiện thuận lợi để giúp đỡ tácgiả hoàn thành luận án. Cuối cùng, tác giả xin bày tỏ lòng biết ơn vô hạn đến bố mẹ anhchịvà gia đình đã hết lòng ủng hộ, động viên, chia sẻ những khó khăn thuận lợi cùng tácgiả trong suốt quá trình thực hiện luận án. Tác giả Lê Đăng Nguyên ii
5. MỤC LỤC LỜI CAM ĐOAN ........................................................................................................i LỜI CẢM ƠN ............................................................................................................ ii MỤC LỤC ................................................................................................................. iii DANH MỤC CÁC HÌNH VẼ....................................................................................vi DANH MỤC CÁC BẢNG ...................................................................................... viii DANH MỤC CÁC TỪ VIẾT TẮT ...........................................................................ix LỜI NÓI ĐẦU ............................................................................................................ 1 CHƯƠNG 1. TỔNG QUAN VỀ SO KHỚP .............................................................. 6 1.1. So khớp chuỗi .............................................................................................. 6 1.1.1. Bài toán so khớp chuỗi ................................................................... 6 1.1.2 Các thuật toán so khớp chính xác cổ điển ....................................... 9 1.1.3 Các thuật toán so khớp chính xác dựa trên mô hình Automat ...... 13 1.1.4 Các thuật toán so khớp chính xác dựa trên bảng băm ................... 14 1.1.5 Các thuật toán so khớp gần đúng ................................................... 16 1.1.6 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 ................................................................................. 17 1.2. So khớp đồ thị ............................................................................................ 26 1.2.1. Một số định nghĩa và ký hiệu ....................................................... 26 1.2.2. Bài toán so khớp đồ thị ................................................................. 28 1.2.3 Một số nghiên cứu liên quan về so khớp đồ thị ............................. 29 1.3. Kết chương ................................................................................................. 33 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 ................................................................................................ 34 2.1. Xâm nhập mạng ......................................................................................... 34 iii
6. 2.1.1. Một số kỹ thuật xâm nhập trái phép ............................................. 35 2.1.2. Một số giải pháp kỹ thuật ngăn chặn xâm nhập ........................... 38 2.1.3. Hệ thống phát hiện xâm nhập trái phép ........................................ 39 2.1.4. Một số nghiên cứu liên quan đến hệ thống phát hiện xâm nhập .. 44 2.2 Thuật toán Aho-Corasick ............................................................................ 48 2.3. Một số nghiên cứu liên quan ...................................................................... 54 2.4. Cải tiến thuật toán AC bằng kỹ thuật nén dòng và bảng chỉ số ................. 56 2.4.1. Biểu diễn không gian lưu trữ và tối ưu hóa bằng kỹ thuật nén dòng56 2.4.2. Cải tiến giai đoạn tiền xử lý của AC ............................................ 58 2.4.3. Thực nghiệm và đánh giá ............................................................. 62 2.5. 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 ................................................................................................ 64 2.5.1. Giai đoạn tiền xử lý ...................................................................... 64 2.5.2. Giai đoạn tìm kiếm ....................................................................... 66 2.5.3. Thuật toán đề xuất ........................................................................ 69 2.6. Kết chương ................................................................................................. 72 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 ..................................................................... 73 3.1. Giả mạo trên mạng ..................................................................................... 73 3.1.1. Giới thiệu ...................................................................................... 73 3.1.2. Một số kỹ thuật giả mạo ............................................................... 73 3.1.3. Một số nghiên cứu liên quan đến giả mạo Web ........................... 75 3.2. Một số nghiên cứu liên quan về so khớp đồ thị ......................................... 77 3.2.1 Tìm đẳng cấu đồ thị và đẳng cấu đồ thị con. ................................. 77 3.2.2. Thuật toán SI - COBRA cho bài toán so khớp đồ thị gán nhãn. .. 80 3.2.3 Thuật toán Simple Tree Matching ................................................. 83 iv
7. 3.2.4 Thuật toán Partial Tree Alignment ................................................ 87 3.2.5 Thuật toán NET ............................................................................. 89 3.2.6 Thuật toán di truyền ....................................................................... 92 3.3. Giải thuật di truyền cho bài toán so khớp đồ thị ........................................ 94 3.3.1. Giải thuật di truyền ....................................................................... 94 3.3.2. Kết quả mô phỏng với giải thuật di truyền ................................... 99 3.4 Thuật toán đề xuất về ứng dụng so khớp đồ thị vào so khớp DOM-tree . 107 3.4.1 Khái niệm cây DOM .................................................................... 107 3.4.2 Xây dựng cây DOM từ trang Web .............................................. 108 3.4.3. Phát hiện giả mạo dựa trên cây DOM ........................................ 111 3.5. Kết chương ............................................................................................... 114 KẾT LUẬN ............................................................................................................. 115 Các kết quả của luận án ........................................................................ 115 Hướng phát triển luận án ...................................................................... 116 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN ÁN .... 117 TÀI LIỆU THAM KHẢO ....................................................................................... 118 v
8. DANH MỤC CÁC HÌNH VẼ Hình 1.1. So khớp dựa trên tiền tố ......................................................................................... 8 Hình 1.2. So khớp dựa trên hậu tố ......................................................................................... 9 Hình 1.3. So khớp dựa trên thừa số ....................................................................................... 9 Hình 2.1. Kiến trúc hệ thống phát hiện xâm nhập mạng ..................................................... 40 Hình 2.2. Hệ thống phát hiện đột nhập cho mạng NIDS ..................................................... 41 Hình 2.3. Hệ thống phát hiện đột nhập cho trạm chủ - HIDS ............................................. 42 Hình 2.4. Kiến trúc hệ thống Snort ...................................................................................... 44 Hình 2.5 Quá trình so sánh của thuật toán KMP ................................................................. 49 Hình 2.6 Xây dựng mảng Next ứng với mẫu P = “aabaaa“ ................................................. 49 Hình 2.7 Xây dựng mô hình otomat cho tập mẫu P = {her, their, eye, iris, he, is} ............. 53 Hình 2.8. Không gian trạng thái của AC với tập mẫu P ...................................................... 57 Hình 2.9. Không gian trạng thái của thuật toán AC gốc ...................................................... 60 Hình 2.10. Không gian trạng thái của thuật toán AC sau khi tối ưu .................................... 61 Hình 2.11. So sánh không gian bộ nhớ của thuật toán AC với các cách tiếp cận lưu trữ trạng thái khác nhau. ............................................................................................................ 63 Hình 2.12. Kết quả của giai đoạn tiền xử lý của thuật toán AC .......................................... 64 Hình 2.13. Kết quả giai đoạn tiền xử lý của thuật toán CW ................................................ 65 Hình 2.14. Kết quả giai đoạn tiền xử lý của thuật toán WM ............................................... 66 Hình 2.15. Kết quả giai đoạn tiền xử lý trong thuật toán của chúng tôi .............................. 66 Hình 2.16. Giai đoạn tìm kiếm của thuật toán CW và WM ................................................ 68 Hình 2.17. Giai đoạn tìm kiếm và so khớp trong thuật toán chúng tôi đề xuất ................... 69 Hình 2.18. So sánh về thời gian thực hiện khi cố định số lượng mẫu ................................. 71 Hình 2.19. So sánh về bộ nhớ sử dụng khi cố định số lượng mẫu ...................................... 71 Hình 3.1. Minh họa về các vector hàng - cột biểu diễn ma trận kề của một đồ thị G. ........ 77 Hình 3.2. Đồ thị GM và GD. ................................................................................................. 78 Hình 3.3. Cây quyết định biểu diễn tất cả các ma trận kề của đồ thị GD. ............................ 78 Hình 3.4. Cây quyết định biểu diễn hai đồ thị GM và GD .................................................... 80 Hình 3.5. Mô phỏng thuật toán tìm đồ thị đẳng cấu dựa vào danh sách các mã. ................ 81 Hình 3.6 Ví dụ về chiến lược tìm kiếm theo chiều rộng, chiều sâu sử dụng mã LVEV. ....... 83 Hình 3.7. Ví dụ về phép ánh xạ giữa 2 cây .......................................................................... 84 vi
9. Hình 3.8. Ví dụ về thuật toán Simple Tree Matching .......................................................... 86 Hình 3.9. Quá trình mở rộng cây ......................................................................................... 88 Hình 3.10. Quá trình so khớp các nút của thuật toán NET .................................................. 91 Hình 3.11 Thực nghiệm với đồ thị vô hướng có số đỉnh nhỏ hơn 10 ................................ 100 Hình 3.12 Đồ thị con tương ứng của cá thể. ...................................................................... 100 Hình 3.13 Thực nghiệm với đồ thị vô hướng có số đỉnh lớn hơn 10 và nhỏ hơn 20 ......... 101 Hình 3.14 Thực nghiệm với đồ thị vô hướng có số đỉnh lớn hơn 20................................. 101 Hình 3.15 Thực nghiệm với đồ thị vô hướng có trọng số nhỏ hơn 10 đỉnh ...................... 102 Hình 3.16 Thực nghiệm với đồ thị vô hướng có trọng số từ 10 đến 20 đỉnh .................... 103 Hình 3.17 Thực nghiệm với đồ thị vô hướng có trọng số lớn hơn 20 đỉnh ....................... 104 Hình 3.18 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh nhỏ hơn 10 .......... 105 Hình 3.19 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh từ 10 đến 20 ........ 106 Hình 3.20 Thực nghiệm với đồ thị vô hướng có gán nhãn với số đỉnh lớn hơn 20 ........... 106 Hình 3.20. Ví dụ cây DOM của một trang HTML ............................................................ 108 Hình 3.21 Ví dụ minh họa về sử dụng visual cue .............................................................. 110 Hình 3.22 Ví dụ minh họa về biểu diễn các đối tượng trang Web dưới dạng DOM-Tree 110 Hình 3.23 Biểu diễn 2 trang web thật và giả mạo dưới dạng cây DOM............................ 112 vii
10. DANH MỤC CÁC BẢNG Bảng 2.1. Nén ma trận chuyển hàm Goto với CSR ............................................................. 57 Bảng 2.2. Nén hàm failure của AC dùng bảng chỉ số .......................................................... 57 Bảng 2.3. Thống kê không gian trạng thái thực nghiệm trên Snort với các tập luật chuẩn . 63 Bảng 3.1. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 100 Bảng 3.2. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 101 Bảng 3.3. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20 .......................... 102 Bảng 3.4. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 103 Bảng 3.5. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 103 Bảng 3.6. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20 .......................... 104 Bảng 3.7. Kết quả độ thích nghi ở một số thế hệ với số đỉnh nhỏ hơn 10 ......................... 105 Bảng 3.8. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 10 nhỏ hơn 20 ...... 106 Bảng 3.9. Kết quả độ thích nghi ở một số thế hệ với số đỉnh lớn hơn 20 .......................... 107 Bảng 3.10. Kết quả so sánh giữa GA và STM (%) ............................................................ 113 Bảng 3.11. Tỷ lệ % phát hiện đúng, sai với các ngưỡng khác nhau .................................. 114 viii