Tài liệu 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

ĐẠ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 ĐẠ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 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ông bố 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 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ầy giá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ác giả 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ẹ anh chị 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ác giả trong suốt quá trình thực hiện luận án. Tác giả Lê Đăng Nguyên ii 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 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 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 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 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 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 DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Ý nghĩa AC Thuật toán Aho-Corasick AC-BM Aho-Corasick Boyer-Moore ACMS Aho-Corasick with Magic states String matching AC-OPT Thuật toán Aho-Corasick – OPT AC-RDF Thuật toán Aho-Corasick – RDF APWG Anti Phishing Working Group ARP Address Resolution Protocol ASCII American Standard Code for Information Interchange BDM Thuật toán Backward Dawg Matching BM Thuật toán Boyer-Moore BMH Thuật toán Boyer-Moore Horspool BO Back - Office BOM Thuật toán Backward Oracle Matching CIAC Character Index Aho-Corasick CW Thuật toán Commentz-Walter DDOS Distributed Denial Of Service DFA Deterministic Finite Automata DHCP Dynamic Host Configuration Protocol DNS Domain Name Service DOM Document Object Model DoS Denial Of Service DRDoS Distributed Reflection DoS GA Genetic Algorithms HIDS Host – based IDS HP Honey Pots HTML HyperText Markup Language ix IDS Intrusion Detection System IP Internet Protocol IRC Internet Relay Chat KMP Thuật toán Knuth-Morris-Pratt KR Thuật toán Karp-Rabin MAC Medium Address Control MDH Thuật toán Multi-Phase Dynamic Hash NFA Non-Deterministic Finite Automata NIDS Network - based Intrusion Detection System NIPS Network - based Intrusion Prevention System PCA Principle Component Analysis PMT Possible matching patterns RSI Thuật toán Recursive Shift Indexing SBMH Setwise Boyer Moore Horspool SBOM Set Backward Oracle Matching SMB Server Message Block SMTP Simple Mail Transfer Protocol SNMP Simple Network Management Protocol STM Simple Tree Matching SVD Singular Value Decomposition TCP/IP Transmission Control Protocol / Internet protocol TCP/UDP Transmission Control Protocol / User Datagram Protocol TF-IDF Term Frequency – Inverse Document Frequency URL Uniform Resource Locator WM Thuật toán Wu và Manner XML eXtensible Markup Language Worm Sâu, một loại virus máy tính x LỜI NÓI ĐẦU Triển khai các ứng dụng và dịch vụ trên Internet là nhu cầu của rất nhiều ngành kinh tế. Nhiều dịch vụ trực tuyến được phát triển mạnh mẽ trong thương mại điện tử, thanh toán trực tuyến, kinh doanh, tài chính, công nghiệp, an ninh, y tế,…cho phép người sử dụng truy cập, khai thác và chia sẻ thông tin mọi lúc mọi nơi. Song song với những tiến bộ và lợi ích mang lại, Internet cũng là không gian rộng mở cho kẻ xấu lợi dụng thực hiện những vụ tấn công, truy cập trái phép vào các hệ thống máy tính và mạng của người dùng. Theo báo cáo của các cơ quan an ninh mạng quốc tế, trong các năm gần đây, chỉ trong năm 2012, thiệt hại về kinh tế do tội phạm mạng gây ra lên tới 388 tỷ USD so với năm 2011 là 114 tỷ USD. Đặc biệt, số vụ tấn công mạng vào các hệ thống cơ sở hạ tầng trọng yếu của nhiều quốc gia ngày càng gia tăng và không chỉ các thiết bị kết nối Internet truyền thống, các thiết bị dân dụng như tivi thông minh, máy in,… cũng trở thành mục tiêu tấn công mạng. Bên cạnh các yếu tố đe dọa an ninh truyền thống, nguy cơ chiến tranh mạng đang trở nên hiện hữu. Đặc biệt đã có nhiều cuộc tấn công trực tiếp vào các cơ quan trọng yếu của chính phủ, lấy đi nhiều tài liệu mật. Các thông tin này hoặc bị công bố bừa bãi trên mạng gây bất lợi về mặt chính trị, tâm lý xã hội hoặc bị sử dụng vào các mục đích chống lại chính phủ. Mặt khác, nhiều cuộc tấn công vào ngân hàng trộm cắp từ các tài khoản lên tới hàng trăm tỷ USD hay tấn công vào các công ty doanh nghiệp để đánh cắp các bí mật kinh doanh, các bí quyết công nghệ mới gây ra các tổn hại lớn gấp bội. Năm 2013 là năm nghi nhận các đợt tấn công DDoS với quy mô lớn nhất trong lịch sử (tháng 3/2013 với lưu lượng có lúc lên đến 300Gbps – trong khi lượng Internet ở Việt Nam vào khoảng 361 Gbps) và cũng là năm chứng kiến vấn đề an ninh mạng trở nên căng thẳng giữa các cường quốc với sự kiện PRISM, Ed Snowden. Đối với Việt Nam, là quốc gia đứng vị trí 18/20 quốc gia có số người sử dụng Internet đông nhất trên thế giới và đứng thứ 11 trên toàn cầu về các nguy cơ tấn công mạng. Số vụ tấn công chủ đích gia tăng từ 77 cuộc mỗi ngày lên 82 cuộc mỗi ngày. 1 Hệ thống phát hiện xâm nhập mạng (Intrusion Detection System) có nhiệm vụ phân tích các thông tin, theo dõi, phát hiện và ngăn chặn sự xâm nhập trái phép tài nguyên làm tổn hại đến tính bảo mật, tính toàn vẹn và tính sẵn sàng của hệ thống. Có nhiều cách tiếp cận khác nhau trong việc phát triển hệ thống IDS. Trong số đó, so khớp mẫu là một kỹ thuật được sử dụng phổ biến trong các hệ thống phát hiện và ngăn chặn xâm nhập mạng. Việc phát hiện các nguy cơ tiềm ẩn trong hệ thống phát hiện xâm nhập mạng được thực hiện bằng cách so khớp nội dung gói tin với các mẫu đã biết. Với sự đa dạng về số lượng các đợt tấn công, hình thức tấn công thì việc thu thập đầy đủ các mẫu làm cho kích thước tập mẫu ngày càng tăng nhanh. Có rất nhiều thuật toán so khớp mẫu [7][19] đã được sử dụng trong hệ thống phát hiện xâm nhập Snort [4][5]. Tuy nhiên, các thuật toán này vẫn tồn tài một số vấn đề như hiệu năng giảm và tiêu tốn nhiều thời gian thực hiện khi số lượng các mẫu tăng lên. Do vậy, việc nghiên cứu cải tiến hay đề xuất các thuật toán so khớp mới đáp ứng việc so khớp đồng thời nhiều mẫu trong các hệ thống phát hiện xâm nhập là một nhu cầu cấp thiết và đây là mục tiêu thứ nhất của luận án này. Một vấn đề khác cũng liên quan đến an toàn đó là vấn đề giả mạo (phishing hay fake) nói chung và giả mạo web nói riêng. Giả mạo và phát tán 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 (Anti Phishing Working Group) đã đưa ra thông số những trang web giả đang tăng khoảng 50% mỗi năm. Cũng giống như xâm nhập mạng, nhiệm vụ đầu tiên là phải nhận biết (phát hiện) được các cuộc xâm nhập, việc đầu tiên để ngăn chặn và xóa bỏ các trang web giả mạo là phát hiện ra chúng. Có rất nhiều các cách tiếp cận khác nhau để phát hiện các trang web giả mạo. Các tác giả trong [17] sử dụng thuật toán TF-IDF (Term Frequency / Inverse Document Frequency) để xác định những từ khóa của một trang web, những từ khóa này được đưa vào một máy tìm kiếm chẳng hạn Google và lấy ra nhóm những URL trên cùng. Nếu trang web bị nghi ngờ nằm trong nhóm đó thì trang nay được coi là hợp lệ, ngược lại nó sẽ bị cho là lừa đảo vì hầu hết các trang lừa đảo không có thứ hạng cao trong các kết quả của máy tìm kiếm. Thuật toán này được ứng dụng trong 2 giải pháp Cantina [46] được phát triển bởi các nhà nghiên cứu của Đại học Carnegie Mellon với việc sử dụng năm từ khóa có tần suất xuất hiện cao nhất trong trang. Nhóm các nhà nghiên cứu thuộc Đại học Iowa [47] sử dụng là thuật toán lọc Bayesian. Lợi thế chính của thuật toán này là có khả năng phát hiện được những đối tượng chưa từng nhìn thấy trước đó. Việc sử dụng phép lọc Bayesian là một giải pháp hứa hẹn cho việc phát hiện lừa đảo 0 ngày (zero-day) vì nó có thể phát hiện những trang web lừa đảo mới và không dựa trên một danh sách đen. Một số tác giả ở Hồng Kông [48] quan tâm đến thuật toán phát hiện sự giống nhau của hai trang web về mặt hình ảnh. Hướng tiếp cận này kiểm tra sự hiển thị tương đồng của một trang web và so sánh những đặc trưng hiển thị của nó với một trang web hợp lệ. Trong nghiên cứu mới nhất của mình, Kranti và các đồng nghiệp đã đề xuất một giải pháp chống giả mạo mới bằng cách sử dụng hai thuật toán K-mean và Naïve Bayes [49]. Một đặc tính nổi bật nhất của trang web giả mạo là nó phải tương tự như trang web gốc. Điều này có nghĩa là hai trang web gốc và web giả mạo có cấu trúc giống nhau. Mặt khác, DOM là tên gọi tắt của Document Object Model - Mô hình đối tượng tài liệu - là một chuẩn được định nghĩa bởi W3C [22] dùng để truy xuất và thao tác trên các tài liệu có cấu trúc dạng HTML hay XML bằng các ngôn ngữ lập trình như Javascript, PHP, Python,... Do vậy, để so sánh hai trang web với nhau chúng ta có thể so sánh hai DOM-Tree tương ứng của chúng. Vì vậy mục tiêu thứ hai của luận án là nghiên cứu các phương pháp để so sánh nhanh nhất và hiệu quả nhất xem hai DOMTree có giống nhau hay không, tổng quát hơi là sẽ nghiên cứu việc so khớp hai đồ thị với nhau vì “cây” chỉ là một dạng đặc biệt của đồ thị rồi áp dụng các kết quả của việc so khớp đồ thị vào so khớp hai DOM-Tree với nhau. Liên quan đến việc giải quyết vấn đề nêu trên, luận án hướng đến hai mục tiêu chính như sau: (1) Nghiên cứu về hệ thống phát hiện xâm nhập. Phát triển và áp dụng các thuật toán so khớp mẫu vào việc xây dựng các hệ thống phát hiện xâm nhập. (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 việc phát hiện các trang Web giả mạo. Với mục tiêu (1), luận án sẽ: 3 (i) Phân tích đánh giá về hiệu năng cũng như thời gian thực hiện các thuật toán so khớp mẫu hiện có trên hệ thống phát hiện thâm nhập Snort; (ii) Đưa ra các cải tiến cho thuật toán so khớp đa mẫu Aho-Corasick bằng cách sử dụng kỹ thuật nén dòng và bảng chỉ số nhằm nâng cao hiệu quả của thuật toán, các phân tích và so sánh thực tế nhằm kiểm nghiệm lý thuyết cũng đã được thực hiện trên hệ thống Snort; (iii) Đề xuất một thuật toán so khớp đa mẫu mới bằng cách xây dựng biểu đồ của các mẫu kết hợp với danh sách liên kết làm giảm thời gian thực hiện việc so khớp đồng thời đa mẫu. Việc cài đặt thực nghiệm của thuật toán so sánh với một số thuật toán đã tồn tại cũng đã triển khai trên hệ thống Snort. Với mục tiêu (2), do cây là một dạng đặc biệt của đồ thị, vì vậy với mục tiêu thứ hai, luận án nghiên cứu bài toán tổng quát hơn đó là so khớp đồ thị. Với mục tiêu này, các kết quả của luận án đạt được là: (i) Đưa ra thuật toán mới dựa trên thuật toán di truyền để so khớp các đồ thị không chính xác, thuật toán mới có thể áp dụng đối với lớp đồ thị vô hướng, có hướng, có trọng số hay gán nhãn. (ii) Áp dụng việc so khớp đồ thị vào việc so khớp các DOM-Tree để phát hiện các trang Web giả mạo. Với các mục tiêu của luận án như trên, ngoài phần mở đầu, luận án được tổ chức thành ba chương như sau. - 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 - 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. 5 CHƯƠNG 1. 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. 1.1. So khớp chuỗi 1.1.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 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..n]) độ dài n (trong đó m< - Xem thêm -