Tóm tắt Luận án 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

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 4thự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 s′ là tiền tố của s nếu s′ = 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) = ⋃ 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 5d ∈ Σ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(CHUNKp(S, r)) = L(CHUNK(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. 61.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. 7Chươ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ủ 8Algorithm 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: flag = true 17: i = 1 18: while (i ≤ `− r + 1) and (flag = true) do 19: if (Ti is positive tree) and (s ∗ does not match Ti) then 20: flag = false; 21: if (Ti is negative tree) and (s ∗ matches Ti) then 22: flag = false 23: i=i+1 24: if flag = false then 25: output “s∗ is non-self” 26: else 27: output “s∗ is self” 9tụ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 ` r Bộ nhớ (%) Thời gian (%) 1000 50 12 0 0 2000 30 15 2.5 5 2000 40 17 25.9 42.7 2000 50 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 NSA PNSA Giảm(%) 5 727 706 2.89 10 33,461 31,609 5.53 15 1,342,517 1,154,427 14.01 20 9,428,132 6,157,766 34.68 25 18,997,102 11,298,739 40.52 30 29,668,240 17,080,784 42.42 35 42,596,987 24,072,401 43.48 40 58,546,497 32,841,794 43.90 45 79,034,135 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); (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 n′ and an edge (n, n′) 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 16: if there exists a s′ ∈ Ti where s[i− k + 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 s′ is reachable 19: for all s′ ∈ Ti where s[i− k + 1...|s|] is prefix of it do 20: if |s| − i+ k < r then 21: D2 = D2 ⋃{(s[|s|] + s′, i− 1, i)} 22: else 23: D2 = D2 ⋃{(s′, i, i)} 24: delete every node n ∈ Ti from which only nodes in the s′ is reachable 25: else 26: D1 = D1 ⋃{(s, k, j)} 27: for all s′ ∈ Ti do 28: D2 = D2 ⋃{(s′, i, i)} 29: D = D2 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 Kích thước (bit) Thời gian (phút) r-chunk rcbvl r-chunk rcbvl Case 1 49 10 119,571 10,000 206,810 42,704 1 0.2 49 8 79,571 50,000 31,672 8,096 0.8 0.18 Case 2 30 12 25,000 25,000 367,092 79,222 4.1 0.75 30 14 40,000 10,000 2,324,056 392,815 8.65 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 Thuật toán Huấn luyện Phát hiện r-chunk Stibor et al. (2004) (2r + |S|)(`− r + 1) |D|` Elberfeld, Textor (2009) r2|S|(`− r) |S|`2r Elberfeld, Textor (2011) |S|`r ` Luận án này |S|` ` r-contiguous D’haeseleer et al. (1996) (linear) (2r + |S|)(`− r) |D|` D’haeseleer et al. (1996) (greedy) 2r|S|(`− r) |D|` Wierzchon´ (2000) 2r(|D|(`− r) + |S|) |D|` Elberfeld, Textor 2009) |S|3`3r3 |S|2`3r3 Elberfeld, Textor (2011) |S|`r ` Luận án này |S|`+ (2r −K).`) `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]] = NULL 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]! = NULL)&&(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] = NULL 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) . create an acyclic directed graph G presenting a NSA 3: if s∗ ∈ L(G) then 4: output ”s∗ is self” 5: else 6: output ”s∗ is nonself” 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) ∩ Σ` = CONT (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]] = NULL 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] = NULL) 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]] = NULL 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] = NULL 30: P1 = 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: So sánh Chunk-NSA với NSA bởi Textor. r Thử nghiệm 1 Thử nghiệm 2 a b c b/c d e d/e 10 1330 454 2.9 1490 482 3.1 11 1395 439 3.2 1633 472 3.5 12 1564 454 3.4 637 360 4.5 13 1767 435 4.1 2134 453 4.7 14 1771 418 4.2 2276 451 5.0 15 2092 486 4.3 2793 450 6.2 16 1985 437 4.5 3086 365 8.5 17 2071 391 5.3 4079 427 9.6 18 2249 410 5.5 4509 422 10.7 19 2345 375 6.3 5312 470 11.3 20 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. 19 Algorithm 5.3 Thuật toán PSA2 phát hiện s ∈ Σ` là self hay nonself 1: procedure Detection(N , A, s, `, r) 2: SelfTreesGeneration(N , `, r) 3: NonselfTreesGeneration(A, `, r) 4: d1 = d2 = d3 = 0 5: Create a string sr as ring representation of s 6: for i = 1, ..., ` do 7: s′ = sr[i . . . i+ r − 1] 8: if s′ /∈ TNi then 9: d1 = d1 + 1 10: if s′ /∈ TAi then 11: d2 = d2 + 1 12: if Leaf(s′, TNi) < Leaf(s ′, TAi).t1 then 13: d3 = d3 + 1 14: if d1 > t2 then output s is nonself 15: else if d2 > t3 then output s is self 16: else if d3.t4 > ` then output s is nonself 17: else output s is self 5.2 Thử nghiệm 5.2.1 Cơ sở dữ liệu Chúng tôi sử dụng hai bộ dữ liệu thử nghiệm là NetFlow và TU. Tương tự như các công bố trước, chúng tôi sử dụng 4 đặc trưng của NetFlow cho thử nghiệm 1, 5, 6, và 7; 7 đặc đặc trưng của NetFlow cho thử nghiệm 2 và 3; 4 đặc trưng của UT cho thử nghiệm 4. Bảng 5.1: Các đặc trưng cho NIDS. Thử nghiệm Cơ sở dữ liệu Đặc trưng 1 NetFlow Packets, Octets, Duration, Flags 2, 3 NetFlow Packets, Octets, Duration, Scr_port, Dst_port, Flags, IP protocol 4 UT Packets, Octets, Duration, Flags 5, 6, 7 NetFlow Packets, Octets, Duration, Flags 5.2.2 Tiền xử lý dữ liệu Phương pháp tiền xử lý cho các tính năng của tập dữ liệu huấn luyện bao gồm hai bước. Bước đầu tiên là chuyển đổi tất cả các thuộc tính thành chuỗi nhị phân. Sau bước này, tất cả các thuộc tính của cả dữ liệu bình thường và bất thường đều ở dạng nhị phân. Bước thứ hai là để ghép những các chuỗi nhị phân biểu diễn các thuộc tính lại với nhau. Sau bước này, tập dữ liệu huấn luyện chứa các xâu nhị phân độ dài như nhau. Trong giai đoạn phát hiện, mỗi thuộc tính trong dữ liệu cần phát hiện sẽ được chuyển đổi thành 20 một chuỗi nhị phân sử dụng ánh xạ của dữ liệu huấn luyện. Nếu một giá trị thuộc tính không có trong phạm vi tương ứng với miền giá trị của dữ liệu huấn luyện, thì dạng biểu diễn nhị phân của nó sẽ được chọn ngẫu nhiên. Ví dụ 5.1. Cho tập dữ liệu huấn luyện gồm các flow hai thuộc tính là S = {N,A}, với N = {n1 = (1; 8);n2 = (0.5; 6)} và A = {a1 = (1; 9); a2 = (1; 6), a3 = (0.5; 9)}. Phạm vi của thuộc tính đầu tiên và thứ hai tương ứng là {0.5; 1} và {6; 8;9}. Do đó, chúng ta sử dụng một bit (hai bit) để mã hóa thuộc tính đầu tiên (thứ hai). Một ánh xạ các dãy số {0.5;1} và {6; 8; 9} được chuyển đổi tương ứng thành xâu nhị phân {0; 1} và {00; 01; 10}. Cuối cùng, tập huấn luyện chứa các xâu có độ dài 3. S = {N,A}, với N = {n1 = 101;n2 = 000} và A = {a1 = 110; a2 = 100, a3 = 010}. Giả sử một flow s = (2; 8) là một bộ dữ liệu test. Thuộc tính thứ nhất (2 /∈ {0.5; 1}) được mã hóa một cách ngẫu nhiên một trong hai giá trị 0 hoặc 1. Trong khi đó, thuộc tính thứ hai (8 ∈ {6; 8; 9}) nên được mã hóa thành 01. Cuối cùng, dạng nhị phâ