Luận văn Phương pháp tối ưu đàn kiến để giải bài toán phát hiện xâm nhập

u, nghiên cứu và hoàn thiện luận văn. Thầy với nhiều năm nghiên cứu trong lĩnh vực tối ưu hóa, với nhiều đề xuất, công trình được công nhận. Nghiên cứu chuyên sâu về tối ưu hóa đàn kiến của thầy đã giúp tôi hiểu rõ những khó khăn trong trong quá trình nghiên cứu tìm ra hướng giải quyết bài toán của mình. Thầy cũng đưa ra những góp ý bổ ích, quý báu giúp cho tôi có thể hoàn thành quyển luận văn này. Tôi cũng xin được gửi lời cảm ơn sâu sắc đến TS.Trần Ngọc Hà người đã giúp đỡ tôi trong quá trình viết luận văn và thực nghiệm chương trình. Cuối cùng tôi xin được bày tỏ lòng biết ơn tới các thầy cô trường Đại học Công nghệ đã tham gia giảng dạy và chia sẻ những kinh nghiệm quý báu cho tôi trong suốt quá trình học. Tôi xin cảm ơn tới các thầy và các anh chị đã thường xuyên giúp đỡ, trao đổi, góp ý về những vấn đề khoa học liên quan tới luận văn. Hà Nội, tháng 7 năm 2020 HỌC VIÊN ĐÀO VĂN HẢI 2 LỜI CAM ĐOAN Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới sự hướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn và TS. Trần Ngọc Hà. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được liệt kê tại mục tài liệu tham khảo. Hà Nội, tháng 7 năm 2020 HỌC VIÊN ĐÀO VĂN HẢI 3 MỤC LỤC LỜI CẢM ƠN ....................................................................................................... 1 LỜI CAM ĐOAN .................................................................................................. 2 DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ....................................................... 6 DANH SÁCH CÁC BẢNG .................................................................................. 7 DANH SÁCH HÌNH VẼ ...................................................................................... 8 MỞ ĐẦU ............................................................................................................... 9 CHƯƠNG 1: GIỚI THIỆU VỀ PHÁT HIỆN XÂM NHẬP MẠNG ................. 11 1.1. Giới thiệu ................................................................................................ 11 1.2. Xâm nhập ................................................................................................ 11 1.2.1. Khái niệm ...................................................................................... 11 1.2.2. Các kiểu xâm nhập phổ biến ......................................................... 11 1.2.3. Các cách ngăn chặn xâm nhập truyền thống ................................. 12 1.3. Hệ thống phát hiện xâm nhập mạng ....................................................... 13 1.3.1. Phân loại hệ thống phát hiện xâm nhập mạng .............................. 13 1.4. Các cách tiếp cận cơ bản trong bài toán phát hiện xâm nhập ................ 15 1.4.1. Cách tiếp cận dựa vào luật ............................................................ 15 1.4.2. Cách tiếp cận dựa vào thống kê .................................................... 16 1.5. Bài toán phát hiện xâm nhập trong hệ thống mạng nội bộ ..................... 16 1.5.1. Mô tả bài toán ................................................................................ 16 1.5.2. Đề xuất hướng giải quyết .............................................................. 16 CHƯƠNG 2: GIỚI THIỆU BÀI TOÁN TỐI ƯU HÓA TỔ HỢP VÀ PHƯƠNG PHÁP TỐI ƯU HÓA ĐÀN KIẾN ...................................................................... 18 2.1. Giới thiệu bài toán tối ưu tổ hợp .............................................................. 18 2.2. Bài toán người chào hàng ......................................................................... 19 2.3. Các cách tiếp cận giải quyết bài toán tối ưu tổ hợp ................................. 19 2.3.1. Tiếp cận truyền thống ........................................................................ 19 2.3.2. Tiếp cận dựa trên thực nghiệm .......................................................... 20 2.4. Phương pháp tối ưu đàn kiến .................................................................... 20 4 2.4.1. Kiến tự nhiên ..................................................................................... 20 2.4.2. Kiến nhân tạo (Artificial Ant) ........................................................... 22 2.4.3. Phương pháp tối ưu đàn kiến ............................................................. 23 2.4.4. Mô tả thuật toán ACO tổng quát ....................................................... 23 2.4.5. Các hệ kiến ......................................................................................... 26 2.4.5.1. Hệ kiến AS ...................................................................................... 26 2.4.5.2. Hệ kiến ACS ................................................................................... 26 2.4.5.3. Hệ kiến Max-Min ........................................................................... 29 2.4.5.4. Hệ kiến Max-Min trơn .................................................................... 29 CHƯƠNG 3: SỬ DỤNG PHƯƠNG PHÁP TỐI ƯU HÓA ĐÀN KIẾN TRONG BÀI TOÁN PHÁT HIỆN XÂM NHẬP ............................................................. 31 3.1. Thuật toán DACS3-FS ............................................................................. 31 3.1.1. Đồ thị và cấu trúc ............................................................................... 32 3.1.2. Xác suất chuyển tiếp .......................................................................... 32 3.1.3. Vết mùi và thông tin heuristic ........................................................... 33 3.1.4. Quy tắc cập nhật vết mùi ................................................................... 33 3.1.5. Lược đồ chung ................................................................................... 35 3.2. Thuật toán SMMAS-FS ............................................................................ 37 3.2.1. Quy tắc cập nhật vết mùi ................................................................... 37 3.2.2. Lược đồ thuật toán ............................................................................. 38 3.2.3. Lựa chọn lời giải tốt nhất ................................................................... 39 3.3. Áp dụng trong bài toán phát hiện xâm nhập ............................................ 39 CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM, SO SÁNH, ĐÁNH GIÁ ............... 40 4.1. Tiến hành thực nghiệm ............................................................................. 40 4.1.1. Dữ liệu đầu vào .................................................................................. 40 4.1.2. Cấu hình sử dụng thực nghiệm .......................................................... 42 4.1.3. Các tham số đầu vào .......................................................................... 42 4.2. Kết quả chạy thực nghiệm ........................................................................ 42 4.2.1. So so sánh với thuật toán DACS3-FS ............................................... 42 5 4.2.2. Thử với các thực nghiệm khác .......................................................... 44 4.3. Nhận xét .................................................................................................... 45 4.4. Hướng nghiên cứu tiếp theo ..................................................................... 45 KẾT LUẬN ......................................................................................................... 46 TÀI LIỆU THAM KHẢO ................................................................................... 47 6 DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ 1 ACO Ant Colony Optimization (Tối ưu hóa đàn kiến) 2 AS Ant System (Hệ kiến AS) 3 ACS Ant Colony System (Hệ kiến ACS) 4 MMAS Max-Min Ant System (Hệ kiến MMAS) 5 SMMAS Smooth-Max Min Ant System (Hệ kiến MMAS trơn) 6 TSP Travelling Salesman Problem (Bài toán người chào hàng) 7 TƯTH Tối ưu tổ hợp 8 IDS Intrusion Detection System 9 DoS Denial of Service (Tấn công từ chối dịch vụ) 10 U2R User to Root (Tấn công chiếm quyền điều khiển) 11 U2L Remote to Local (Tấn công điều khiển từ xa) 12 IDS Intrusion Detection Systems (Hệ thống phát hiện xâm nhập) 13 SVM Support Vector Machine (Phân lớp SVM) 14 𝜏𝑚𝑎𝑥 Cận trên của vết mùi 15 𝜏𝑚𝑖𝑛 Cận dưới của vết mùi 16 𝜏0 Vết mùi được khởi tạo ban đầu 17 𝜏𝑖𝑗 Vết mùi trên cạnh (i,j) 18 3-LAS Hệ kiến 3 mức 7 DANH SÁCH CÁC BẢNG Hình 2.1: Hành vi của mỗi con kiến trong tự nhiên ............................................ 21 Hình 2.2: Thực nghiệm trên cây cầu đôi ............................................................. 21 Hình 2.3: Thí nghiệm bổ sung ............................................................................. 22 Hình 2.4: Lựa chọn đỉnh đi tiếp theo .................................................................. 24 Hình 3.1: Đồ thị cấu trúc lựa chọn đặc trưng ...................................................... 32 Hình 3.2: Lược đồ chung thuật toán DACS3-FS ................................................ 35 Bảng 4.1: Các kiểu tấn công trong bộ dữ liệu Kdd99 (10%) .............................. 40 Bảng 4.2: Thuộc tính bộ dữ liệu Kdd99 .............................................................. 41 Bảng 4.3: Tham số đầu vào thuật toán SMMAS-FS .......................................... 42 Bảng 4.4: Các đặc trưng được chọn bằng các phương pháp lựa chọn đặc trưng khác nhau ............................................................................................................. 43 Bảng 4.5: Bảng so sánh tỷ lệ chính xác bộ phân lớp .......................................... 43 Bảng 4.6: Bảng so sánh các phương pháp phân lớp ........................................... 45 8 DANH SÁCH HÌNH VẼ Hình 2.1: Hành vi của mỗi con kiến trong tự nhiên ............................................ 21 Hình 2.2: Thực nghiệm trên cây cầu đôi ............................................................. 21 Hình 2.3: Thí nghiệm bổ sung ............................................................................. 22 Hình 2.4: Lựa chọn đỉnh đi tiếp theo .................................................................. 24 Hình 3.1: Đồ thị cấu trúc lựa chọn đặc trưng ...................................................... 32 Hình 3.2: Lược đồ chung thuật toán DACS3-FS ................................................ 35 Hình 4.1: Biểu đồ so sánh tỷ lệ chính xác giữa các phương pháp44 Hình 4.2: Biểu đồ so sánh tỷ lệ chính xác và số đặc trưng được lựa chọn..44 9 MỞ ĐẦU Ngày nay cùng với sự phát triển của Internet ngày một mở rộng, vấn đề tin tặc đánh cắp thông tin đang ngày càng phổ biến. Đặc biệt với các thông tin quan trọng và nhạy cảm thì việc phân loại phát hiện được các loại xâm nhập là nhiệm vụ cần thiết. Hệ thống phát hiện xâm nhập mạng (IDS) là một hệ thống giám sát, theo dõi, thu thập thông tin nhằm đưa ra các cảnh báo, biện pháp phát hiện xâm nhập mạng. IDS có nhiều cách tiếp cận nhưng đơn giản và phổ biến nhất vẫn là dựa vào thống kê. Bài toán phát hiện xâm nhập trên tập các thông tin thực chất là bài toán phân lớp và đưa ra dự đoán về sự xâm nhập khi gặp các thông tin mới. Một trong những vấn đề của các thuật toán phân lớp đó là việc xử lý dữ liệu đầu vào, các thông tin dư thừa dẫn đến việc tỷ lệ phát hiện bất thường không chính xác, kết quả phân lớp thấp. Có thể cải thiện vấn đề dữ liệu đầu vào bằng các thuật toán lựa chọn đặc trưng. Thuật toán ACO là một thuật toán tốt sử dụng trong bài toán tối ưu hóa tổ hợp. Mô phỏng cách tìm đường đi của các con kiến, thuật toán ACO sử dụng kết hợp thông tin heuristic và học tăng cường thông qua vết mùi tạo nên nhờ các con kiến di chuyển để giải bài toán tìm đường đi trong đồ thị cấu trúc. Việc sử dụng thuật toán ACO để phát hiện xâm nhập đã được nhiều tác giả đề xuất trong đó có nhóm tác giả Mehdi Hosseinzadeh Aghdam và Peyman Kabiri với đề xuất sử dụng ACO-based Method năm 2016 [18]. Tiếp theo nhóm tác giả Helmi Md Rais và Tahir Mehmood với đề xuất thuật toán DACS3-FS năm 2018 đề xuất việc cập nhật vết mùi với ba cấp độ. Trên cơ sở các thuật toán đã có tôi xin đề xuất một cải tiến nữa cho thuật toán ACO dùng cho phát hiện xâm nhập là dùng quy tắc cập nhật vết mùi mới mà ở đây là sử dụng phương pháp SMMAS. Phương pháp này giảm nhược điểm của phương pháp MMAS là để vết mùi tiến dần về 𝜏min sau một số bước giảm tính khám phá. Cũng như nhược điểm của các đề xuất thuật toán trên là phải tính toán, cập nhật vết mùi nhiều lần làm tăng thời gian chạy thuật toán. Trong luận văn này tôi sẽ trình bày lại các phương pháp lựa chọn đặc tính bằng phương pháp ACO. Khảo cứu phương pháp DACS3-FS được Helmi Md Rais và cộng sự đề xuất năm 2018 được coi là tối ưu cho bài toán này. Sử dụng ý tưởng của nhóm tác giả [8] đề xuất phương pháp cập nhật vết mùi mới cho bài toán. Và chứng minh quy tắc cập nhật vết mùi mới do nhóm tác giả [17] đề xuất năm 2012 có hiệu quả hơn so với phương pháp trên. 10 Ngoài phần kết luận, cấu trúc của luận văn bao gồm: Chương 1: Giới thiệu về phát hiện xâm nhập các khái niệm và các hướng tiếp cận của bài toán phát hiện xâm nhập. Chương 2: Giới thiệu tối ưu hóa tổ hợp và bài toán tối ưu hóa đàn kiến, cách tiếp cận, các phương pháp tối ưu hóa đàn kiến Chương 3: Trình bày thuật toán DACS3-FS, phương pháp xây dựng đồ thị cấu trúc, cập nhật mùi. Đề xuất cải tiến thuật toán bằng phương pháp cập nhật vết mùi mới SMMAS. Chương 4: Tiến hành thực nghiệm trên bộ dữ liệu chuẩn, thống kê, đánh giá kết quả thu được và so sánh giữa hai cách giải quyết bài toán ở trên. Đề xuất một số cải tiến như tìm kiếm địa phương và cập nhật lại vết mùi. 11 CHƯƠNG 1: GIỚI THIỆU VỀ PHÁT HIỆN XÂM NHẬP MẠNG 1.1. Giới thiệu Internet đã trở thành một phần của cuộc sống hiện đại và ngày càng có vai trò quan trọng đối với con người, chúng ta có thể thấy được internet đã và đang chi phối hầu như mọi lĩnh vực của cuộc sống từ kinh tế, giải trí đến giáo dục và đào tạo Đặc biệt ngày nay, internet được sử dụng như một thành phần quan trọng trong các mô hình kinh doanh, trong đó cả doanh nghiệp và khách hàng đều sử dụng các dịch vụ, ứng dụng, website, thư điện tử, trong các hoạt động của mình. Vì vậy, vấn đề an toàn thông tin khi sử dụng môi trường internet cần phải được đặc biệt quan tâm. Phát hiện xâm nhập mạng là một vấn đề lớn cần nghiên cứu cho cả mạng doanh nghiệp và cá nhân Việc triển khai và quản lý hệ thống thông tin yêu cầu nhiều cơ chế bảo vệ chặt chẽ, an toàn. Để một hệ thống an toàn ngoài việc hệ thống cần trang bị những công cụ đủ mạnh và có người quản trị mạng am hiểu về phương thức xử lý các cuộc tấn công thì cũng cần những hệ thống hỗ trợ cho việc phát hiện xâm nhập giúp phòng ngừa các cuộc tấn công, đảm bảo an toàn cho hệ thống. Bảo mật thông tin môi trường mạng gồm nhiều lĩnh vực nhưng trong đó có bốn hướng chính là: An toàn phía máy chủ, an toàn phía máy khách, bảo mật trên đường truyền, phát hiện xâm nhập. Trong đó phát hiện xâm nhập (intrusion detection) là một lĩnh vực được nhiều sự quan tâm và đầu tư nghiên cứu, các giải pháp giúp tối ưu hóa việc phát hiện xâm nhập được đưa ra nhằm cải tiến giúp việc phát hiện xâm nhập chính xác và nhanh chóng hơn. Vì thế trong luận văn này, tôi tập trung vào việc đưa ra cải tiến giúp việc phát hiện xâm nhập hiệu quả hơn nhưng trước hết tôi xin đưa ra các giới thiệu để người đọc hiểu rõ hơn về các định nghĩa tôi sẽ nêu trong bài viết. 1.2. Xâm nhập 1.2.1. Khái niệm Vào năm 1999 Kendall có đưa ra một định nghĩa như sau: “Tấn công hay còn gọi là xâm nhập mạng là những hoạt động có chủ đích, lợi dụng các tổn thương của hệ thống thông tin nhằm phá vỡ tính sẵn sàng, tính toàn vẹn và tính bảo mật của hệ thống”. Và đó có thể là một định nghĩa gần đúng nhất của tấn công hay xâm nhập mạng 1.2.2. Các kiểu xâm nhập phổ biến 12 Trong thực tế có rất nhiều kiểu tấn công mạng khác nhau nhưng thường sẽ được phân thành các nhóm chính như sau: tấn công kiểu từ chối dịch vụ, tấn công kiểu thăm dò, tấn công kiểu chiếm quyền điều khiển, tấn công từ xa a) Tấn công từ chối dịch vụ Tấn công từ chối dịch vụ DoS là một kiểu tấn công cơ bản bằng cách gửi một loạt thông tin đến máy chủ hệ thống khiến nó bị quá tải không thể cung cấp dịch vụ, làm gián đoạn hệ thống hoặc làm tê liệt hệ thống. b) Tấn công thăm dò Kiểu tấn công thăm dò (Probe), tin tặc quét mạng hoặc máy tính để tìm ra các lỗ hổng giống như theo dõi, giám sát hệ thống. Phương thức phổ biến là việc quét và theo dõi các cổng dịch vụ đang mở của máy tính ở đây sẽ có các thông tin như IP, MAC, thông tin về tường lửa Các kiểu tấn công thăm dò như: Sniffing, Ping Sweep, Portsweep Satan, Ví dụ: Sniffer là một dạng tấn công nghe lén trên hệ thống mạng dựa trên những đặc điểm của cơ chế TCP/IP. Ban đầu đây là một kỹ thuật bảo mật, được phát triển nhằm giúp các nhà quản trị mạng khai thác mạng hiệu quả hơn và có thể kiểm tra các dữ liệu ra vào mạng cũng như các dữ liệu trong mạng. Sau này, phương thức này được lợi dụng để lấy cắp mật khẩu và các thông tin khác. c) Tấn công U2R Đơn giản là việc tin tặc tìm cách để truy cập được vào hệ thống với quyền cao nhất một cách bất hợp pháp. Kiểu tấn công này ít gặp hơn so với hai kiểu trên. Nhưng đây cũng là một kiểu tấn công nguy hiểm vì khi có quyền cao nhất tin tặc có thể phá hoại hệ thống. Trong bộ dữ liệu KDD99 mà tôi sẽ dùng để thực nghiệm trong luận văn có đề cập đến một kiểu tấn công U2R là: buffer_overflow, loadmodule, perl, rootkit. d) Tấn công R2L Đây là kiểu tấn điều khiển máy tính từ xa. Từ việc khai thác các lỗ hổng bảo mật tin tặc gửi các gói tin đến máy tính trong hệ thống mạng rồi tìm cách truy cập trái phép hệ thống với tư cách là người dùng trong hệ thống mạng đó. Cách tấn công phổ biến của loại này là đoán mật khẩu thông qua phương pháp từ điển, FTP Write 1.2.3. Các cách ngăn chặn xâm nhập truyền thống Các biện pháp cũ hay dùng phổ biến như: tường lửa (firewall), mã hóa, xác thực, quyền truy cập, 13 a) Tường lửa (Firewall) Tường lửa có thể là phần mềm hoặc phần cứng được thiết kế để ngăn chặn hoặc cho phép những truy cập dựa trên các tiêu chuẩn, tập luật được lưu trên hệ thống. Nó cũng có thể mã hóa, giải mã hay ủy quyền cho các giao dịch giữa các miền bảo mật khác nhau. Một số loại tường lửa như: bộ lọc gói (Packet Filtering), cổng ứng dụng (Application Gateway), cổng mức mạch (Circuit Level Gate) Tường lửa có một số điểm yếu như: - Chỉ có tác dụng với các cuộc tấn công bên ngoài mạng. - Không diệt được virus hay mã độc. - Không chống được các cuộc tấn công mà không đi qua tường lửa. b) Mã hóa dữ liệu (Encoding) Mã hóa dữ liệu là phương pháp bảo vệ thông tin dữ liệu bằng cách chuyển dữ liệu từ dạng thông thường sang dạng khác nhưng vẫn có thể giải mã tức là đưa dữ liệu về dạng ban đầu được bằng một hình thức giải mã. Trong quá trình truyền tin dữ liệu có thể bị ăn trộm bởi tin tặc nhưng chúng chỉ lấy được gói tin mã hóa và không biết cách giải mã việc này giúp dữ liệu an toàn. Việc mã hóa và giải mã được thực hiện bởi một bộ mã hóa giải mã thích hợp. c) Xác thực (Authentication) Xác thực là việc xem xét người dùng đang truy cập có phải là người dùng đã được khai báo trong hệ thống không. d) Quyền truy cập (Permission) Đây coi như là mức bảo vệ cuối cùng, mỗi một người dùng sẽ được cấp các quyền khác nhau đối với hệ thống hoặc đơn giản là một chức năng. Hệ thống sẽ kiểm tra người dùng hiện tại có được khai báo sử dụng chức năng đó không từ đó từ chối những người cố ý truy cập hệ thống hoặc sử dụng chức năng khi chưa được phép. 1.3. Hệ thống phát hiện xâm nhập mạng Hệ thống phát hiện xâm nhập mạng (Intrusion Detection System) là một hệ thống (có thể là thiết bị phần cứng hay phần mềm) nhằm giám sát lưu lượng mạng theo dõi, thu thập thông tin để phát hiện xâm nhập mạng và đưa ra cảnh báo.. 1.3.1. Phân loại hệ thống phát hiện xâm nhập mạng Hệ thống phát hiện xâm nhập được phân loại dựa trên cách thức thu thập thông tin hoặc phương pháp phân tích. 14 Ta có thể phân loại thành hai dạng hệ thống phát hiện ở mức mạng NIDS (Network -based IDS) và hệ thống phát hiện xâm nhập ở mức máy chủ HIDS (Host – based IDS)  Network – based IDS (Hệ thống phát hiện xâm nhập ở mức mạng) NIDS hoạt động độc lập, kiểm tra các luồng thông tin, truy cập vào luồng thông tin trên mạng bằng cách kết nối vào các Hub, Switch được cấu hình Port mirroring hoặc Network tap để bắt các gói tin, phân tích nội dung các gói tin từ đó phát hiện các cuộc tấn công và đưa ra các cảnh báo. Port mirroring được sử dụng để gửi một bản sao của tất cả các gói tin trên mạng khi nó đi qua cổng của Switch tới một thiết bị giám sát mạng trên cổng khác của Switch đó. Nó thường được dùng trong các thiết bị mạng cần giám sát luồng trên mạng, ví dụ như hệ thống IDS, Port Analyzer (SPAN) Hình 1.1 Hệ thống phát hiện xâm nhập NIDS Nhược điểm của hệ thống NIDS là giới hạn băng thông và có thể xảy ra hiện tượng tắc nghẽn cổ chai khi lưu lượng mạng hoạt động ở mức cao.  Host – based IDS (Hệ thống phát hiện xâm nhập máy trạm chủ) HIDS là một phần mềm chạy trên các trạm hoặc máy chủ có chức năng giám sát tất cả các hoạt động trên máy đó. HIDS có thể được cài cục bộ trên một máy tính và nó linh hoạt hơn so với NIDS. HIDS phân tích thông tin thu được trong nội bộ hệ thống cung cấp một cơ chế phân tích toàn diện các hoạt động và phát hiện một cách chính xác các thành phần tấn công. 15 1.4. Các cách tiếp cận cơ bản trong bài toán phát hiện xâm nhập Có nhiều cách tiếp cập phổ biến cho bài toán phát hiện xâm nhập nhưng trong giới hạn luận văn tôi sẽ nêu một số các cách tiếp cận phổ biến như: phát hiện xâm nhập dựa vào luật, dựa vào phân tích thống kê. 1.4.1. Cách tiếp cận dựa vào luật Phát hiện xâm nhập dựa vào luật (rule-based) là một trong những phương pháp khá phổ biến và được sử dụng nhiều, việc phát hiện sẽ dựa vào các dấu hiệu xâm nhập. Phát hiện xâm nhập dựa tập luật thường được thực hiện như sau: Bước 1: Hệ thống lựa chọn ra những tập luật mà theo luật đó là những dấu hiệu của việc xâm nhập, những dữ liệu này được thu thập từ nhiều cuộc tấn công trước đó. Bước 2: Xây dựng cơ sở dữ liệu các luật với các kiểu xâm nhập khác nhau theo dạng if-then như sau: if {condition} then {atc} Trong đó: condition: các dấu hiệu (đặc trưng) liên quan tới các kiểu xâm nhập như: duration, protocol, source port, destination port, service,... atc: kiểu tấn công. Bước 3: Sử dụng các thuật toán so khớp để tìm ra các bộ dữ liệu phù hợp với tập luật. Ví dụ:  Luật quy định các kiểu tấn công dos. if(duration = “0:0:1” and protocol = “finger” and source_port = 18982 and destination_port = 79 and source_ip = “9.9.9.9” and destination_ip = “172.16.112.50” and service =“private”) then (attack name = “dos”).  Luật quy định các kiểu tấn công probe. if(duration = “0:0:1” and protocol = “telnet” and source_port = 18982 and destination_port = 79 and source_ip = “9.9.9.9” and destination_ip = “172.16.112.50” and service =“fpt”) then (attack name = “probe”). Ưu điểm của cách tiếp cận này là dễ cài đặt và đơn giản trong việc sử dụng. Khi hệ thống mạng đứng trước những nguy cơ tấn công mới, người quan trị sẽ cập nhật bổ sung tập luật mới vào hệ thống. Phương pháp này có tỷ lệ phát hiện 16 sai thấp vì các tập luật đã được lựa chọn kỹ và thuật toán chỉ có nhiệm vụ so sánh chỉ ra thông tin nào phù hợp với tập luật đó. Tuy nhiên, bên cạnh đó cách tiếp cận này cũng có nhiều nhược điểm điển hình là việc đứng trước một nguy cơ tấn công mới mà không có trong tập luật hệ thống sẽ không phát hiện được. Các cuộc tấn công của tin tặc luôn thay đổi việc cập nhật các tập luật liên tục vào hệ thống gây mất thời gian của người quản trị. 1.4.2. Cách tiếp cận dựa vào thống kê Phát hiện xâm nhập dựa vào thống kê là một trong những phương pháp phát hiện xâm nhập dựa trên sự bất thường của dữ liệu. Hệ thống sẽ thống kê bằng cách quan sát các hoạt động của đối tượng tạo lưu lại những hành vì hoạt động của đối tượng, khi có các dữ liệu bất thường hệ thống sẽ đưa ra cảnh báo hoặc ngăn chặn. Việc phát hiện bất thường dựa trên thống kế cơ bản là bài toán phân lớp dữ liệu sử dụng các thuật toán phân lớp từ đó có thể đưa ra dự đoán đối với các dữ liệu mới, các cuộc tấn công mới. 1.5. Bài toán phát hiện xâm nhập trong hệ thống mạng nội bộ 1.5.1. Mô tả bài toán Trong một mạng nội bộ một công ty cần một hệ thống phát hiện xâm nhập đưa ra các cảnh báo hoặc biệt pháp khi phát hiện có sự xâm nhập. Bộ phận quản trị mạng trong công ty thường xuyên quản lý giám sát lưu lượng mạng và các thông tin mạng bằng các kiểm tra các báo cáo gói tin được gửi trong giao thức mạng. Công việc kiểm tra thông tin mạng bình thường rất khó để phân biệt được trạng thái bị xâm nhập hoặc không. Cần một hệ thống phát hiện xâm nhập từ các gói tin được nhận hoặc gửi đi trong mạng. Đối tượng xâm nhập là một đối tượng nằm ngoài mạng cố gắng xâm nhập và hệ thống để đánh cắp thông tin hoặc có hành vi phá hoại, cũng có thể là người có tài khoản truy cập vào hệ thống nhưng có những hành vì truy cập vào tài liệu không thuộc thẩm quyền, phá hoại hệ thống Ý tưởng sử dụng một hệ thống phát hiện xâm nhập có chức năng nhận và đánh giá các gói tin nhận hoặc gửi trong mạng nội bộ công ty. Đưa ra cảnh báo nếu gói tin đó có biểu hiện của việc xâm nhập. 1.5.2. Đề xuất hướng giải quyết Xây dựng một hệ thống phát hiện xâm nhập. Khi các gói tin được kiểm tra, nội dung các gói tin sẽ được đưa vào hệ thống để phân lớp, kết quả trả về sẽ thuộc hai trạng thái: xâm nhập hoặc không xâm nhập. Khi trạng là xâm nhập hệ thống sẽ gửi thông tin địa chỉ ip người dùng trong 17 mạng và đưa ra cảnh báo cho quản trị viên hoặc có các biện pháp ngăn chặn kịp thời. a. Dữ liệu đầu vào Dữ liệu đầu là những thông tin thu thập được từ việc bắt các gói tin trong dữ liệu lưu lượng mạng. Những thông tin dùng trong việc xác định một kết nối là xâm nhập hay không xâm nhập có thể là: Duration, Protocol_type, Service, Flag, Srv_count, Num_root Dữ liệu này có thể được lấy thông ứng dụng thu thập lưu lượng mạng như: TCPDUMP... b. Cách xác định phân lớp dữ liệu Việc xác định xem một bộ dữ liệu có là xâm nhập hay không xâm nhập dựa trên các hành vi đã biết trong thực tế. Khi tiến hành xây dựng hệ thống phát hiện xâm nhập ta sử dụng các bộ dữ liệu đang được dán nhãn và công bố để tiến hành huấn luyện (như bộ dữ liệu KDD99 được luận văn sử dụng trong phần thực nghiệm). 18 CHƯƠNG 2: GIỚI THIỆU BÀI TOÁN TỐI ƯU HÓA TỔ HỢP VÀ PHƯƠNG PHÁP TỐI ƯU HÓA ĐÀN KIẾN 2.1. Giới thiệu bài toán tối ưu tổ hợp Các bài toán tiêu biểu của lớp bài toán tối ưu tổ hợp có thể kể ra như: bài toán người giao hàng, bài toán lập thời khóa biểu, bài toán lập lịch sản xuất Đây là các bài toán trong thực tế để giải các bài toán dạng này ta cần mô hình hóa chúng để có thể mô phỏng trên máy tính, từ đó có thể tìm ra lời giải tối ưu. Đặc điểm chung nhất với mỗi bài toán là đều chứa n thành phần C={c1,cn} và hàm mục tiêu f. Các bài toán ứng dụng với bộ (S, f, Ω), trong đó S là tập hữu hạn các trạng thái (phương án), f là hàm mục tiêu xác định trên S và Ω là tập các ràng buộc. Mỗi phương án 𝑠 ∈ 𝑆 thỏa mãn các ràng buộc Ω gọi là phương án chấp nhận được. Mục tiêu của chúng ta là tìm ra s* phương án tối ưu đối với hàm mục tiêu f, nói cách khác chính là tìm phương án s* sao cho f(s*) ≤ f(s) với mọi 𝑠 ∈ 𝑆. Đối với bài toán này ta có 3 cách giải quyết đó là: vét cạn, kỹ thuật ăn tham hoặc phương pháp tối ưu trong lĩnh vực NP-hard. Các thuộc tính của tập S, C và Ω như sau: 1. Ký hiệu X là tập các vector trên C có độ dài không quá h: X={ui ∀i≤k≤h}. Khi đó, mỗi phương án s trong S được xác định nhờ ít nhất một vector trong X. 2. Tồn tại tập con X* của X và ánh xạ 𝜑 từ X* lên S sao cho 𝜑−1(𝑠) không rỗng với mọi 𝑠 ∈ 𝑆, trong đó tập X* có thể xây dựng được từ tập con C0 nào đó của C nhờ thủ tục mở rộng tuần tự dưới dây. 3. Từ C0 ta mở rộng tuần tự thành X* như sau: i. Ta xem x0 = là mở rộng được với mọi u0∈C0 ii. Giả sử xk = là mở rộng được và chưa thuộc X*. Từ tập ràng buộc Ω, xác định tập con J(xk) của C, sao cho với mọi uk+1∈ J(xk) thì xk+1= là mở rộng được. iii. Áp dụng thủ tục mở rộng từ các phần tử u0∈C0 cho phép ta xây dựng được mọi phần tử của X*. Ta thấy mỗi bài toán TƯTH được xem là một bài toán cực trị hàm có h biến, trong đó mỗi biến nhận giá trị trong tập hữu hạn C kể cả giá trị rỗng. Nói một cách khác là bài toán tìm kiếm trong không gian vector độ dài không quá h trong đồ thị đầy đủ có các đỉnh có nhãn trong tập C. 19 2.2. Bài toán người chào hàng Bài toán người chào hàng (Traveling Salesman Problem - TSP) là một bài toán NP-hard thuộc thể loại tối ưu hóa rời rạc hay tổ hợp. Đây là bài toán TƯTH điển hình, được nghiên cứu và xem như là bài toán chuẩn để đánh giá về hiệu quả lời giải các bài toán TƯTH. Có thể phát biểu bài toán đơn giản như sau: Cho trước một danh sách thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất đi qua tất cả cách thành phố trong danh sách với điều kiện mỗi thành phố chi được đi qua một lần. Có thể thấy đây chính là bài toán tìm chu trình Hamilton với đồ thị đầy đủ có trọng số 𝐺 = (𝑉, 𝐸), với V là tập các đỉnh với nhãn là các thành phố trong C, E là t