Tài liệu Cải tiến một số thuật toán trong miễn dịch nhân tạo cho phát hiện xâm nhập mạng tt

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ……..….***………… NGUYỄN VĂN TRƯỜNG CẢI TIẾN MỘT SỐ THUẬT TOÁN TRONG MIỄN DỊCH NHÂN TẠO CHO PHÁT HIỆN XÂM NHẬP MẠNG Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2019 Công trình được hoàn thành tại: Học viện Khoa học và Công nghệ Viện Hàn lâm Khoa học và Công nghệ Việt Nam Người hướng dẫn khoa học 1: PGS. TS Nguyễn Xuân Hoài Người hướng dẫn khoa học 2: PGS. TS Lương Chi Mai Phản biện 1: … Phản biện 2: … Phản biện 3: …. Luận án sẽ được bảo vệ trước Hội đồng chấm luận án tiến sĩ, họp tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam vào hồi … giờ ..’, ngày … tháng … năm 201…. Có thể tìm hiểu luận án tại: - Thư viện Học viện Khoa học và Công nghệ - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦU Tính cấp thiết của luận án Mạng máy tính phải đối mặt với rất nhiều tấn công. Để đảm bảo an toàn, cần thiết phải có hệ thống kiểm soát an ninh, chẳng hạn như hệ thống phát hiện xâm nhập (Intrusion Detection Systems, IDS). Tuy vậy, việc phát hiện xâm nhập lại phải đối phó với rất nhiều vấn đề như lưu lượng mạng lớn, phân bố dữ liệu không cân bằng, khó nhận biết ranh giới giữa hành vi bình thường và hành vi bất thường, và yêu cầu thích nghi thường xuyên với môi trường thay đổi. Hệ quả là các nhà nghiên cứu đã nỗ lực sử dụng nhiều phương pháp khác nhau để xây dựng các hệ IDS tin cậy. Một trong những phương pháp dựa trên trí tuệ tính toán cho phát hiện xâm nhập nổi trội gần đây là hệ miễn dịch nhân tạo (AIS), có nguồn gốc từ hệ miễn dịch sinh học. Thuật toán chọn lọc âm tính (NSA) của AIS, được sử dụng nhiều trong các IDSs. Dù cho đã có những ứng dụng thành công, nhưng NSA có một vài điểm yếu: 1-Tỉ lệ lỗi dương tính và lỗi âm tính còn cao, 2-Thời gian huấn luyện và kiểm tra còn cao, 3-Có mối quan hệ theo hàm mũ giữa kích thước dữ liệu huấn luyện và số lượng bộ dò có thể được sinh ra cho kiểm tra, 4- Khó phân biệt được hai khái niệm “dữ liệu bình thường” với “dữ liệu bất thường” trong môi trường mạng. Để giải quyết được những hạn chế ấy, các xu hướng nghiên cứu gần đây tập trung theo hướng giải quyết vấn đề cấu trúc phức tạp của bộ dò miễn dịch, phương pháp so khớp và các hệ AIS lai. Mục đích nghiên cứu Do việc biểu diễn dữ liệu là một nhân tố quan trọng ảnh hưởng đến thời gian huấn luyện và kiểm tra, nên đề tài luận án hướng đến sinh tập bộ dò đầy đủ và thu gọn. Luận án nghiên cứu các thuật toán tối ưu để sinh bộ dò theo nghĩa tốc độ thực hiện nhanh cả về huấn luyện và kiểm tra. Nghiên cứu và đề xuất mô hình hệ phát hiện xâm nhập mạng dựa trên hệ miễn dịch nhân tạo để phát hiện tấn công, cả loại đã biết và chưa biết. Hệ thống được xây dựng này có sử dụng hệ miễn dịch nhân tạo kết hợp với thống kê dựa trên dữ liệu định dạng flow. Mô tả bài toán Luận án tập trung nghiên cứu ba bài toán: Bài toán 1: Tìm dạng biểu diễn thu gọn 2 cho dữ liệu nhằm không chỉ cực tiểu hóa bộ nhớ lưu trữ dữ liệu mà còn giảm thời gian phát hiện. Bài toán 2: Đề xuất thuật toán giảm thời gian huấn luyện so với các công trình đã công bố. Bài toán 3: Cải tiến hiệu suất phát hiện theo hướng giảm lỗi cảnh báo sai trong khi vẫn giữ được tỉ lệ phát hiện và độ chính xác cao nhất có thể. Vấn đế tìm ra một thuật toán tối ưu có thể vừa giảm được độ phức tạp thời gian, bộ nhớ vừa có hiệu suất phát hiện tốt nhất là không khả thi. Những khía cạnh đó luôn mâu thuẫn với nhau. Do vậy, trong mỗi chương chúng tôi chỉ tập trung giải quyết một bài toán tương đối độc lập. Bài toán phát hiện xâm nhập trong luận án có thể được phát biểu không hình thức như sau: Cho trước tập hữu hạn các luồng mạng S có gắn nhãn là self (bình thường) hay nonself (bất thường). Mục tiêu là xây dựng mô hình phân lớp trên S có khả năng phân lớp một luồng không gắn nhãn s. Tổng quan về luận án Chương đầu tiên giới thiệu kiến thức nền tảng cần thiết cho các giải thuật sẽ được trình bày ở các chương kế tiếp. Chương 2 trình bày về kết hợp thuật toán chọn lọc. Kỹ thuật đưa ra nhằm giảm bộ nhớ lưu trữ các bộ dò trong giai đoạn huấn luyện. Do bộ nhớ này giảm, nên hệ quả tất yếu là thời gian kiểm tra cũng giảm đi. Cấu trúc cây được sử dụng để cải thiện độ phức tạp thời gian và bộ nhớ. Tập bộ dò đầy đủ và không dư thừa là cần thiết để đạt được khả năng bao phủ chấp nhận được của bộ phân lớp cho seft và nonself. Một thuật toán sinh tập bộ dò như vậy được đề xuất trong chương 3. Chương 4 bao gồm hai thuật toán chọn lọc cho huấn luyện nhanh. Các thuật toán tối ưu có thể sinh tập bộ dò trong thời gian tuyến tính với kích thước dữ liệu huấn luyện. Về mặt thời gian phát hiện, thuật toán thứ nhất và thuật toán thứ hai có độ phức tạp lần lượt là tuyến tính và đa thức. Chương 5 giới thiệu về một cách tiếp cận lai của thuật toán chọn lọc với thống kê. Tần suất của dữ liệu seft và nonself được lưu trong lá của cấu trúc cây biểu diễn bộ dò. Phương pháp này đóng vai trò quan trọng trong cải tiến hiệu suất của thuật toán. Cách tiếp cận lai này có thể được coi như kỹ thuật phân loại hai lớp được huấn luyện dựa trên dữ liệu thuộc cả hai loại là seft và nonself. 3 Chương 1 KIẾN THỨC CHUẨN BỊ 1.1 Hệ miễn dịch người Hệ miễn dịch con người là một kiến trúc bảo vệ nhiều tầng, bao gồm tầng vật lý, tầng sinh lý và hệ miễn dịch (thích nghi và bẩm sinh). Hệ miễn dịch thích nghi có khả năng nhận diện các tác nhân gây bệnh, và ghi nhớ chúng để tăng khả năng phản hồi về sau. Nó chính là nguồn gốc ý tưởng của hệ miễn dịch nhân tạo. 1.2 Các thuật toán chọn lọc Cách tiếp cận chọn lọc âm tính dựa trên phân biệt giữa self và nonself trong các hệ thống sinh học. Tính chất này của chọn lọc âm tính được các nhà nghiên cứu về an ninh máy tính và an ninh mạng quan tâm. Một khảo sát trong sáu năm 2008-2013 cho thấy thuật toán chọn lọc âm tính (NSA) phổ biến hơn các cách tiếp cận khác của AIS về số lượng bài đăng tải trong lĩnh vực an ninh mạng và phát hiện bất thường. 1.2.1 Thuật toán chọn lọc âm tính NSA cổ điển gồm hai giai đoạn: sinh tập bộ dò và phát hiện. Trong giai đoạn sinh tập bộ dò, các ứng cử cho bộ dò được sinh ra ngẫu nhiên rồi thực hiện khớp với các mẫu dữ liệu self từ tập S (biểu diễn các thành phần của hệ thống). Ứng cử viên nào khớp với ít nhất một phần tử của S thì bị loại bỏ, số còn lại được lưu trong tập bộ dò D. Trong giai đoạn phát hiện, tập các bộ dò được sử dụng để phân biệt self (thành phần hệ thống) với nonself (ngoại lai, bất thường). Nếu một đối tượng khớp với bất kì một phần tử nào đó của tập bộ dò D, thì nó được coi là nonself. 1.2.2 Thuật toán chọn lọc dương tính Thuật toán chọn lọc dương tính (PSA) cổ điển cũng gồm hai giai đoạn: sinh tập bộ dò và phát hiện. Trong giai đoạn sinh, các ứng cử cho bộ dò được sinh ra ngẫu nhiên rồi 4 thực hiện khớp với các mẫu dữ liệu self từ tập S . Ứng cử viên nào không khớp với bất kỳ phần tử của S thì bị loại bỏ, số còn lại được lưu trong tập bộ dò D. Trong giai đoạn phát hiện, tập các bộ dò được sử dụng để phân biệt self với nonself. Nếu một đối tượng khớp với bất kì một phần tử nào đó của tập bộ dò D, thì nó được coi là self. 1.3 Thuật ngữ và định nghĩa cơ bản 1.3.1 Xâu, xâu con và ngôn ngữ Bảng chữ cái Σ là tập hữu hạn, khác rỗng các kí hiệu. Một xâu s ∈ Σ∗ là một chuỗi các kí hiệu thuộc Σ, độ dài của nó được kí hiệu là |s|. Một xâu được gọi là rỗng nếu nó có độ dài là 0. Cho trước chỉ số i ∈ {1, . . . , |s|}, thì s[i] là kí hiệu tại ví trí i trong s. Cho trước hai chỉ số i và j , nếu j ≥ i, thì s[i . . . j] là xâu con của s có độ dài j − i + 1. Nếu j < i, thì s[i . . . j] là xâu rỗng. Một xâu s0 là tiền tố của s nếu s0 = s[1 . . . j], 1 ≤ j ≤ |s|. Một tập xâu S ⊆ Σ∗ được gọi là ngôn ngữ. Với hai chỉ số i và j , ta định nghĩa S[i . . . j] = {s[i . . . j]|s ∈ S}. 1.3.2 Cây tiền tố, DAG tiền tố Một cây tiền tố T là một cây có gốc với nhãn của cạnh thuộc Σ, mỗi nút trong cây có nhiều nhất một cạnh đi ra có nhãn là σ , σ ∈ Σ. Với một xâu s, ta viết s ∈ T nếu có một đường từ gốc của T tới một lá sao cho s dãy các kí tự trong s là nhãn của đường này. Cấu trúc cây tiền tố được sử dụng trong thuật toán sinh tập bộ dò rcbvl. Một tiền tố DAG G là một đồ thị có hướng không chu trình với cung có nhãn từ tập Σ. Mỗi nút có nhiều nhất một cung đi ra có nhãn là σ , σ ∈ Σ. Với một xâu s, ta viết s ∈ G nếu có một đường từ gốc của G tới một lá sao cho s dãy các kí tự trong s là nhãn của đường này. Ta kí hiệu L(G) = S n is root of G L(G, n). Chú ý là mỗi đồ thị tiền tố G có thể được chuyển về dạng otomat. 1.3.3 Bộ dò Cho trước bảng chữ cái Σ khác rỗng, gồm các kí hiệu, bộ dò dương tính và bộ dò âm tính r-chunk, bộ dò r-liên tục và bộ dò rcbvl được định nghĩa như sau: Định nghĩa 1.1 (Bộ dò dương tính r-chunk). Cho trước tập self S , một bộ (d, i) gồm xâu d ∈ Σr , r ≤ `, và một số nguyên i ∈ {1...` − r + 1} được gọi là bộ dò dương tính r-chunk nếu tồn tại xâu s ∈ S thỏa mãn d khớp với s[i . . . i + r − 1]. Định nghĩa 1.2 (Bộ dò âm tính r-chunk). Cho trước tập self S , một bộ (d, i) gồm xâu 5 d ∈ Σr , r ≤ `, và một số nguyên i ∈ {1...` − r + 1} được gọi là bộ dò âm tính r-chunk nếu d không khớp được với bất kỳ s[i . . . i + r − 1], s ∈ S . Mặc dù cách tiếp cận được đề xuất trong các chương sau có thể cài đặt với bất kỳ bảng chữ cái hữu hạn nào, nhưng để tiện theo dõi trong các ví dụ tôi chỉ sử dụng chữ cái nhị phân, Σ = {0, 1}. Định nghĩa 1.3 (Phát hiện dựa trên chọn lọc âm tính). Nếu một phần tử so khớp được với ` − r + 1 bộ dò dương tính r-chunk: (dij , i), i = 1, . . . , ` − r + 1, thì nó là self, ngược lại nó là non-self. Định lý 1.1. Khả năng phát hiện của tập bộ dò dương tính và tập bộ dò âm tính là như nhau. L(CHU N Kp (S, r)) = L(CHU N K(S, r)) Định nghĩa 1.4 (Bộ dò rcbvl). Cho trước số nguyên dương r, một tập S các xâu self độ dài `. Bộ (d, i, j) gồm một xâu d ∈ Σk , 1 ≤ k ≤ `, một số nguyên i ∈ {1, ..., ` − r + 1} và một số nguyên j ∈ {i, ..., ` − r + 1} được gọi là bộ dò rcbvl nếu d không xuất hiện trong s, s ∈ S. Nói cách khác, (d, i, j) là bộ dò rcbvl nếu tồn tại (j − i + 1) bộ dò r-chunk (d1 , i),..., (dj−i+1 , j) thỏa mã điều kiện dk [2..r] = dk+1 [1..r − 1], k = 1, ..., j − i. 1.3.4 Biểu diễn dạng vòng của dữ liệu Phần lớn các ứng dụng dựa trên AIS dùng hai loại biểu diễn dữ liệu: xâu và vectơ giá trị thực. Cả hai loại này được biểu diễn bởi cấu trúc tuyến tính của các ký hiệu hoặc số. Điều này dẫn đến có thể bỏ sót thông tin biên (đầu và cuối) của những cấu trúc này. Do vậy, ta có thể sử dụng cấu trúc vòng tròn thay vì tuyến tính để đạt độ chính xác phân lớp cao hơn. Một cách làm đơn giản để xây dựng cấu trúc vòng đối với xâu là lấy phần đầu xâu kết nối vào cuối xâu. Cho trước tập các xâu S ⊂ Σ` , kí hiệu Sr ⊂ Σ`+r−1 gồm tất cả các biểu diễn vòng tròn của mọi xâu trong S . 1.3.5 Cây tần suất Cho tập D gồm các xâu có độ dài bằng nhau, một cây T trên D ký hiệu TD là một cây có hướng bắt đầu từ gốc với các cạnh có nhãn trong tập Σ. Mỗi nút có ít nhất một cung ra có nhãn là σ . Với một xâu s, chúng tôi coi s ∈ T nếu tồn tại một đường đi từ gốc của T đến một lá sao cho s chứa các nhãn trên đường đi này. Mỗi lá được kết hợp với một số nguyên đó là tần số của xâu s ∈ D và s là dãy nhãn trên đường đi kết thúc bởi lá này. 6 1.4 Tập dữ liệu Trong luận án, tôi chỉ tập trung nghiên cứu dữ liệu dạng flow bởi các lý do: 1 - Cho phép phát hiện một số tấn công đặc biệt, như DDoS hay RDP Brute Force, một cách hiệu quả và nhanh hơn cách tiếp cận dựa trên gói tin vì chỉ cần phân tích lượng thông tin ít hơn so với phân tích gói tin. 2 - Cách phương pháp phát hiện bất thường dựa trên flow chỉ xử lý header của các gói tin và vì vậy giảm được dữ liệu và thời gian xử lý, phù hợp với phát hiện tốc độ cao trong các mạng cỡ lớn. Nó giải được vấn đề cân bằng tải trong điều kiện gia tăng sử dụng mạng. Tập dữ liệu DARPA-Lincoln: Tập dữ liệu này được thu thập bởi phòng thí nghiệm Lincoln (MIT), với mục đích dùng cho đánh giá hiệu suất của các công nghệ phát hiện xâm nhập khác nhau. Tập dữ liệu UT: Tập dữ liệu này được thu thập thông qua kiểm soát máy chủ dạng honeypot đặt tại trường Đại học Twente (Hà Lan). Cơ sở dữ liệu này bao gồm các loại như lưu lượng nguy hiểm, lưu lượng chưa biết và lưu lượng hiệu ứng phụ. Mỗi flow trong cơ sở dữ liệu có 12 trường: Source IP, Destination IP, Source Port, Destination Port, Packets, Octets, Start Time, End Time, Flags, and Proto. Tập dữ liệu Netflow: Cơ sở dữ liệu này thuộc về một địa chỉ IP và cổng cụ thể nhận nhiều tấn công nhất. Nó chứa 129,571 lưu lượng (gồm cả các tấn công) đến và tới các nạn nhân. Mỗi flow trong cơ sở dữ liệu có 10 trường: Source IP, Destination IP, Source Port, Destination Port, Packets, Octets, Start Time, End Time, Flags, and Proto. 7 Chương 2 KẾT HỢP CHỌN LỌC ÂM TÍNH VÀ CHỌN LỌC DƯƠNG TÍNH 2.1 Thuật toán chọn lọc âm tính mới Đầu tiên, chúng tôi xây dựng ` − r + 1 cây nhị phân (gọi là cây dương tính) tương ứng với ` − r + 1 tập bộ dò dương tính r-chunk Dpi , i = 1, . . . , ` − r + 1. Sau đó, tất các các cây con đầy đủ của các cây trên sẽ được loại bỏ để tìm ra được tập bộ dò tối thiểu cho bộ dò dương tính r-chunk mà vẫn giữ nguyên được khả năng phát hiện. Cuối cùng, với mỗi cây dương tính thứ i, chúng tôi quyết định xem có nên chuyển đổi sang cây âm tính hay không, với cây âm tính là tập bộ dò r-chunk Dni . Quyết định này phụ thuộc vào cây nào là nhỏ gọn hơn. Khi quá trình thực hiện này kết thúc, chúng ta sẽ có ` − r + 1 cây nhị phân nhỏ nhất trong đó một số cây thuộc loại dương tính và số khác thuộc loại âm tính. Phương pháp so khớp r-chunk trên cây nhị phân được tiến hành như sau: xâu s cho trước sẽ được so khớp với cây nhị phân dương tính (âm tính) thứ i khi s[i . . . i + k] là một đường đi từ gốc đến lá i = 1, . . . , ` − r + 1, k < r. Giai đoạn phát hiện có thể được thực hiện bằng cách duyệt các cây nhị phân nhỏ gọn nhất từng bước một: một xâu s được kết luận là nonself nếu nó khớp được với một cây nhị phân âm tính hoặc không khớp với tất cả các cây nhị phân dương tính, và s được kết luận là self trong trường hợp ngược lại. Từ mô tả của thuật toán PNSA, nó sẽ mất |S|(` − r + 1).r bước để xây dựng ra tất các các cây cần thiết và trong trường hợp tồi nhất cần (` − r + 1).r bước để so khớp 1 xâu và kết luận nó là self hay nonself. Độ phức tạp thời gian này tương đương với độ phức tạp của các thuật toán NSA (PSA) phổ biến. Định lý 2.1 (Độ phức tạp bộ nhớ PNSA). Cho một tập self S và một số nguyên `, thủ 8 Algorithm 2.1 Thuật toán chọn lọc dương tính-âm tính 1: procedure PNSA(S, `, r, D) 2: for i = 1, ..., ` − r + 1 do 3: Create an empty prefix tree Ti 4: for s ∈ S do 5: insert every s[i . . . i + r − 1] into Ti 6: for internal node n ∈ Ti do 7: if n is root of complete binary subtree then 8: delete this subtree 9: if (number of leaves of Ti ) > (number of nodes of Ti that have only one child) then 10: for every internal node ∈ Ti do 11: if it has only one child then 12: if the child is a leaf then 13: delete the child 14: create the other child for it 15: Mark Ti as a negative tree 16: f lag = true 17: i=1 18: while (i ≤ ` − r + 1) and (f lag = true) do 19: if (Ti is positive tree) and (s∗ does not match Ti ) then 20: f lag = false; 21: if (Ti is negative tree) and (s∗ matches Ti ) then 22: f lag = false 23: i=i+1 24: if f lag = false then 25: output “s∗ is non-self” 26: else 27: output “s∗ is self” 9 tục PNSA xây dựng cây bộ dò (cây nhị phân) giảm được nhiều nhất là (` − r + 1).2r−2 nút so với cây bộ dò được tạo bởi chỉ một thuật toán PSA hay NSA, r ∈ {2, . . . , ` − r + 1}. 2.2 Thử nghiệm Tiếp theo, chúng tôi thử nghiệm các tác động có thể có của việc giảm độ phức tạp quản lý bộ dò trong PNSA trên thực tế phát hiện (trung bình) thời gian phức tạp trong so sánh với NSA (PSA). Bảng 2.1 cho thấy kết quả bộ nhớ lưu trữ và thời gian thực hiện của PNSA so với NSA trên một số bộ S , ` và r. Bảng 2.1: So sánh mức độ giảm về thời gian và bộ nhớ. S 1000 2000 2000 2000 ` 50 30 40 50 r Bộ nhớ (%) Thời gian (%) 12 0 0 15 2.5 5 17 25.9 42.7 20 36.3 50 Chúng tôi tiến hành một thử nghiệm khác bằng cách chọn ` = 40, |S| = 20,000 (S là tập các xâu nhị phân được sinh ngẫu nhiên độ dài `) và giá trị r khác nhau (15 đến 40). Sau đó, ` − r + 1 cây được tạo sử dụng NSA và ` − r + 1 cây khác được tạo bằng PNSA. Tiếp theo cả hai tập bộ dò được sử dụng để phát hiện mọi xâu s ∈ S . Thử nghiệm này được xây dựng trên bộ dữ liệu Netflow. Tỉ lệ các nút được giảm thể hiện ở cột cuối cùng. Bảng 2.2: So sánh nút giảm trên dữ liệu Netflow. r 5 10 15 20 25 30 35 40 45 NSA 727 33,461 1,342,517 9,428,132 18,997,102 29,668,240 42,596,987 58,546,497 79,034,135 PNSA Giảm(%) 706 2.89 31,609 5.53 1,154,427 14.01 6,157,766 34.68 11,298,739 40.52 17,080,784 42.42 24,072,401 43.48 32,841,794 43.90 44,194,012 44.08 10 Chương 3 SINH TẬP BỘ DÒ THU GỌN 3.1 Thuật toán NSA mới Cho một tập khác rỗng S gồm các xâu self độ dài ` và một số nguyên r ∈ {1, . . . , ` − r + 1}, trong phần này trình bày một thuật toán NSA mới dựa trên luật so khớp rcbvl. Một số cây tiền tố được sử dụng đầu tiên để tạo ra các bộ dò hoàn hảo từ tập S và sau đó tập này được sử dụng để phân biệt nếu một mẫu mới là self hoặc non-self. Thuật toán 2 đã tóm tắt bước đầu tiên của thuật toán NSA. Từ mô tả của thuật toán cho thấy cần |S|.(` − r + 1).r bước để tạo (` − r + 1) cây tiền tố và |D|.(` − r + 1).2r bước để tạo tập bộ dò D. Ví dụ 3.1. Cho ` = 5, r = 3 và tập self S = {s1 = 010101, s2 = 111010, s3 = 101101, s4 = 100011, s5 = 010111}. Từ các bước trong thuật toán 2 xây dựng một tập bộ dò đầy đủ (0001,1,2), (00100,1,4), (100,4,4), (011110,1,4), (11000,1,3) như sau: Bước đầu tập D được tạo như sau: (00,1,1), (011,1,1), (110,1,1). Sau mỗi bước lặp (dòng 13-29) tính lại tập D và D1 như sau: Vòng lặp i=2: D = {(0001,1,2); (0010,1,2); (0111,1,2); (1100,1,2)} và D1 = ∅. Vòng lặp i=3: D = {(00100,1,3); (01111,1,3); (11000,1,3)} và D1 = {(0001,1,2)}. Vòng lặp i=4: D = {(00100,1,4); (011110,1,4)} và D1 = {(0001,1,2); S (11000,1,3); (100,4,4)}. Và bước cuối cùng D = D D1 trong dòng 30, cuối cùng tập bộ dò đầy đủ là {(0001,1,2), (00100,1,4), (100,4,4), (011110,1,4), (11000,1,3)} Để phát hiện mỗi xâu s là self hay nonself, chúng tôi chỉ đơn giản là kiểm tra quá trình khớp theo luận rcbvl giữa xâu s với mỗi bộ dò trong tập D. Nếu khớp thì s là nonself, ngược lại thì s được kết luận là self. 11 Algorithm 3.1 Thuật toán sinh tập bộ dò rcbvl 1: procedure GenerationDetectors(S, `, r, D) 2: for i = 1, ..., ` − r + 1 do Create an empty prefix tree Ti 3: for all s ∈ S do 4: for i = 1, ..., ` − r + 1 do 5: insert every s[i . . . i + r − 1] into Ti 6: for i = 1, ..., ` − r + 1 do 7: for all non-leaf node n ∈ Ti and all σ ∈ Σ do 8: if no edge with label σ starts at n then 9: create a new leaf n0 and an edge (n, n0 ) labeled with σ. 10: delete every node n ∈ Ti from which none of the newly created leaves is reachable. 11: D1 = ∅ 12: D = { (s, 1, 1)|s ∈ T1 } 13: for i = 2, ..., ` − r + 1 do 14: D2 = ∅ 15: for all (s, k, j) ∈ D do 0 16: if there exists S a s ∈ T0 i where s[i − k0 + 1...|s|] is prefix of it then 17: D2 = D2 {(s + s [|s| − j + k...|s |], k, i)} 18: delete every node n ∈ Ti from which only nodes in the s0 is reachable 19: for all s0 ∈ Ti where s[i − k + 1...|s|] is prefix of it do 20: if |s| − i + kS < r then 21: D2 = D2 {(s[|s|] + s0 , i − 1, i)} 22: else S 23: D2 = D2 {(s0 , i, i)} 24: delete every node n ∈ Ti from which only nodes in the s0 is reachable 25: else S 26: D1 = D1 {(s, k, j)} 27: for all s0 ∈ TSi do 28: D2 = D2 {(s0 , i, i)} 29: D = D2 S 30: D = D D1 12 3.2 Thử nghiệm CSDL NetFlow được sử dụng trong thử nghiệm 1, trong đó một bộ dữ liệu ngẫu nhiên được sử dụng trong thử nghiệm 2. Dữ liệu NetFlow được chuyển sang xâu nhị phân thông qua hai bước. Bước một là ánh xạ mỗi thuộc tính sang dạng nhị phân. Sau bước này, tất cả các thuộc tính dạng xâu được xây dựng cho dữ liệu cả loại bình thường và bất thường. Bước 2 là nối các thuộc tính này lại. Sau bước này, tập dữ liệu chứa các xâu nhị phân có độ dài 49. Quá trình phân chia tập dữ liệu huấn luyện và kiểm tra cũng như giá trị r, ` cho 4 thử nghiệm được mô tả như trong bảng 3.1. Bảng 3.1: Phân bố của dữ liệu, tham số cho thử nghiệm cùng các kết quả. ` r Huấn luyện Kiểm tra 49 10 49 8 119,571 79,571 10,000 50,000 30 12 30 14 25,000 40,000 25,000 10,000 Kích thước (bit) Thời gian r-chunk rcbvl r-chunk Case 1 206,810 42,704 1 31,672 8,096 0.8 Case 2 367,092 79,222 4.1 2,324,056 392,815 8.65 (phút) rcbvl 0.2 0.18 0.75 1.4 Kết quả trong bảng 3.1 cho thấy thuật toán chúng tôi đề xuất giảm cả về kích thước của tập bộ dò và thời gian phân lớp dữ liệu so sánh với thuật toán tốt nhất đã công bố. 13 Chương 4 THUẬT TOÁN CHỌN LỌC NHANH 4.1 Thuật toán chọn lọc âm tính nhanh dựa trên bộ dò loại r-chunk Bảng 4.1 trình bày kết quả so sánh thu giữa thuật toán đề xuất với các thuật toán dựa trên bộ dò loại r-chunk đã công bố về mặt thời gian. Mọi thử nghiệm được tiến hành trên dữ liệu nhị phân. Tham số K = min{|S[i..i + r − 1]|, i = 1, . . . , ` − r + 1}. Tham số |D|, số lượng bộ dò mong muốn, chỉ thích hợp với các thuật toán sinh bộ dò tường minh. Thuật toán của chúng tôi và thuật toán đưa ra bởi Textor đạt được kết quả tương ứng với trường hợp sinh lượng bộ dò tối đa. Chúng tôi đề xuất thuật toán NSA cho phép cải thiện hiệu xuất đáng kể trong giai đoạn huấn luyện so với thuật toán hiệu quả đưa ra bởi Textor. Chúng tôi sử dụng các kí hiệu sau: Một mảng Q, với Q[s][c] là một con trỏ được sử dụng để tạo nút mới trong cây, s ∈ Σr−1 , và c ∈ Σ; Một mảng P với P[i] là một cấu trúc gồm hai trường, 1 con trỏ P[i].end và 1 xâu P[i].str ∈ Σr−1 . Bảng 4.1: So sánh thời gian chạy của các thuật toán đề xuất với các thuật toán đã công bố. Luật so khớp r-chunk r-contiguous Thuật toán Huấn luyện Stibor et al. (2004) (2r + |S|)(` − r + 1) Elberfeld, Textor (2009) r2 |S|(` − r) Elberfeld, Textor (2011) |S|`r Luận án này |S|` r D’haeseleer et al. (1996) (linear) (2 + |S|)(` − r) D’haeseleer et al. (1996) (greedy) 2r |S|(` − r) r Wierzchoń (2000) 2 (|D|(` − r) + |S|) Elberfeld, Textor 2009) |S|3 `3 r3 Elberfeld, Textor (2011) |S|`r Luận án này |S|` + (2r − K).`) Phát hiện |D|` |S|`2 r ` ` |D|` |D|` |D|` |S|2 `3 r3 ` `r Ví dụ 4.1. Đặt ` = 5, r = 3. Tập self S gồm 7 xâu như sau S = {s1 = 01111, s2 = 00111, 14 Algorithm 4.1 Thuật toán sinh tập bộ dò dương tính r-chunk 1: procedure GenerationPositiveDetectors(S, `, r, G) 2: Construct T1 , P and Q initially 3: for i = r + 1, ..., ` do 4: for j = 1, ..., n do 5: if Q[P [j].str][sj [i]] = N U LL then 6: Q[P [j].str][sj [i] = new() . create new end node pointed by Q[P [j].str][sj [i] 7: for j = 1, ..., n do 8: p = P [j].end . p and P [j].end point to the same end node of the tree 9: for c ∈ σ do 10: if (Q[P [j].str][c]! = N U LL)&&(edge starts from p with label c does not exist) then 11: Create the edge starts from p with label c 12: P[j].end=the end note of the edge starts from p with label sj [i] 13: for j = 1, ..., n do 14: for c ∈ Σ do 15: Q[P [j].str][c] = N U LL 16: P [j].str = P [j].str[2...r − 1] + sj [i] s3 = 10000, s4 = 10001, s5 = 10010, s6 = 10110, s7 = 11111} Algorithm 4.2 Thuật toán sinh tập bộ dò âm tính r-chunk 1: procedure GenerationNegativeDetectors(S, `, r, G) 2: GenerationPositiveDetectors(S, `, r, G) . create an acyclic directed graph G on prefix trees 3: Create a special node . this node is considered an accept state in corresponding automaton 4: for every node n ∈ G do 5: if n is a root of a complete sub tree then 6: delete the tree root n, except for n 7: else 8: create new edge from n to the special node Thuật toán 4.3 là tóm tắt thuật toán đề xuất Chunk-NSA. Trong thuật toán này, chúng tôi sử dụng một tập self S , một số nguyên r ∈ {1, . . . , ` − r + 1}, mỗi xâu s∗ được phát hiện bởi một mô hình tiền tố DAG G. Chunk-NSA sẽ phát hiện s∗ là self hay nonself. Định lý 4.1. Cho S ⊆ Σ` và r ∈ {1, . . . , `}, thuật toán Chunk-NSA xây dựng cây tiền tố DAG G với L(G) ⊆ S trong thời gian O(|S|.`.|Σ|) và kiểm tra s∗ ∈ L(G) trong thời gian O(`). 4.2 Thuật toán chọn lọc âm tính nhanh dựa trên bộ dò loại r-contiguous 15 Algorithm 4.3 Thuật toán chọn lọc âm tính nhanh 1: procedure Chunk-NSA(s∗ , S, `, r, G) 2: GenerationNegativeDetectors(S, `, r, G) presenting a NSA 3: if s∗ ∈ L(G) then 4: output ”s∗ is self” 5: else 6: output ”s∗ is nonself” . create an acyclic directed graph G Hai mảng P và Q được sử dụng với ý nghĩa tương tự như trong phần trước. Ngoài ra, chúng tôi sử dụng hai tập hợp con trỏ P1 và P2 cho bộ dò r- chunk. Chúng sẽ hoán đổi vai trò lẫn nhau ở cuối mỗi bước lặp. Định lý 4.2. Tồn tại một thuật toán mà cho trước tập S ⊆ Σ` và r ∈ {1, . . . , `}, xây dựng otomat hữu hạn M với L(M ) ∩ Σ` = CON T (S, r) trong thời gian O(|S|.`.|Σ| + (Σr − K).`), với K= min{|S[i..i + r − 1]|, i = 1, . . . , ` − r + 1}. 4.3 Thử nghiệm Tôi tôi sử dụng cơ sở dữ liệu NetFlow và một bộ dữ liệu ngẫu nhiên để dùng trong thử nghiệm 1 và thử nghiệm 2 tương ứng. Trong Bảng 4.2, thời gian chạy của NSA đề xuất bởi Textor (2011) trong thử nghiệm 1 và thử nghiệm 2 tương ứng trong các cột b và d. Thời gian chạy của thuật toán đề xuất Chunk-NSA trong thử nghiệm 1 và thử nghiệm 2 tương ứng trong cột c và e. Kết quả thời gian huấn luyện cho thấy thuật toán đề xuất có thời gian huấn luyện gần như không phụ thuộc vào giá trị ngưỡng so khớp r. Ngoài ra, tỉ lệ thời gian so khớp giữa thuật toán của Textor và thuật toán đề xuất tăng dần và tiệm cận với r. 16 Algorithm 4.4 Thuật toán sinh tập bộ dò loại r-contiguous 1: procedure Cont-NSA(S, r, G) Input: A set of self strings S ⊆ Σ` , a matching threshold r ∈ {1, . . . , `}. Output: An automaton G presenting negative r-contiguous detectors set. 2: G = P1 = ∅ 3: for s ∈ Σr \ S[1 . . . r] do 4: insert s into G and create p.end that points to the leaf node in path s 5: p.str = s[2 . . . r] 6: P1 = P1 ∪ {p} 7: for i = r + 1, ..., ` do 8: for j = 1, ..., |S| do 9: if Q[P [j].str][sj [i]] = N U LL then 10: Q[P [j].str][sj [i]] = new() 11: P2 = ∅ 12: for each p ∈ P1 do 13: for c ∈ Σ do 14: if (Q[p.str][c] = N U LL) then 15: Q[p.str][c] = new() 16: p.str = p.str[2...r − 1] + c 17: p.end = Q[p.str][c] 18: P2 = P2 ∪ {p} 19: else 20: if Q[p.str][c] is newly created in this inner for loop then 21: p.str = p.str[2...r − 1] + c 22: p.end = Q[p.str][c] 23: P2 = P2 ∪ {p} 24: for j = 1, ..., |S| do 25: Q[P [j].str][sj [i]] = N U LL 26: P [j].str = P [j].str[2...r − 1] + sj [i] 27: for each p ∈ P1 do 28: for c ∈ Σ do 29: Q[p.str][c] = N U LL 30: P 1 = P2 31: for each node n ∈ G do 32: if n is not reachable to a leaf node ∈ P1 then 33: delete n 34: turn G into an automaton 17 Bảng 4.2: r a 10 11 12 13 14 15 16 17 18 19 20 So sánh Chunk-NSA với NSA bởi Textor. Thử nghiệm 1 Thử nghiệm 2 b c b/c d e d/e 1330 454 2.9 1490 482 3.1 1395 439 3.2 1633 472 3.5 1564 454 3.4 637 360 4.5 1767 435 4.1 2134 453 4.7 1771 418 4.2 2276 451 5.0 2092 486 4.3 2793 450 6.2 1985 437 4.5 3086 365 8.5 2071 391 5.3 4079 427 9.6 2249 410 5.5 4509 422 10.7 2345 375 6.3 5312 470 11.3 2859 359 7.0 6796 437 15.6 18 Chương 5 HỆ MIỄN DỊCH NHÂN TẠO LAI CHO AN NINH MẠNG 5.1 Thuật toán lai chọn lọc dương tính bộ dò r-chunk Cho trước `, r, và tập dữ liệu bình thường N ⊂ Σ` , tập dữ liệu bất thường A ⊂ Σ` . Thuật toán 5.1 và 5.3 tạo ra các cây self và cây nonself tương ứng. Một đối tượng dữ liệu mới s ∈ Σ` được phát hiện là self hay nonself bởi thuật toán 5.3.. Algorithm 5.1 Thuật toán sinh các cây self 1: procedure SelfTreesGeneration(N , `, r) 2: for i = 1, ..., ` do 3: Create an empty tree TNi 4: for all s ∈ Nr do 5: for i = 1, ..., ` do 6: insert every s[i . . . i + r − 1] into TNi Algorithm 5.2 Thuật toán sinh các cây nonself 1: procedure NonselfTreesGeneration(A, `, r) 2: for i = 1, ..., ` do 3: Create an empty tree TAi 4: for all s ∈ Ar do 5: for i = 1, ..., ` do 6: insert every s[i . . . i + r − 1] into TAi Trong thuật toán 5.3, Leaf(s, T ) là hàm trả về tần suất tương ứng với xâu s ∈ Σr , giá trị này nằm ở lá của cây trên đường đi s. Các tham số d1 và d2 tương ứng tính tổng tần suất của s trong cây self N và trong cây nonself A. Bốn tham số t1 , t2 , t3 , t4 được sử dụng trong thuật toán PSA2 nhằm điều chỉnh hiệu suất phát hiện.