基于三角剖分的否定選擇算法

汪宏海,婁金霞,柴爭義

(1.浙江省文化和旅游發展研究院,浙江 杭州 311231;2.浙江旅游職業學院,浙江 杭州 311231;3.天津工業大學計算機科學與軟件學院,天津 300387)

0 引言

隨著互聯網技術的飛速發展,網絡作為日常生活中不可或缺的一部分,其安全問題變得越來越重要,如何進行網絡異常數據的檢測和識別,是網絡安全中的關鍵問題[1]。網絡異常數據檢測算法對網絡數據進行檢測和定位,將正常數據和異常數據分離?；诿庖邫C制的否定選擇算法(Negative Selection Algorithm,NSA)[2]是一種非常有效的網絡異常檢測算法。V-detector算法是典型的否定選擇算法[3],由于其具有較好的性能,得到了研究者的廣泛關注。然而,V-detector算法面對復雜的網絡數據問題,由于檢測器的生成過程是隨機的,會使得檢測器生成過程耗時長,不利于在線檢測的快速實現。因此,本文提出了一種基于Delaunay三角剖分的否定選擇算法,即在檢測器的生成階段使用三角剖分對檢測器中心點進行定位,直接生成成熟檢測器,算法以快速生成檢測器為主要目標,降低檢測個數,從而降低檢測器生成時的資源消耗。

1 相關工作

1.1 研究背景

在眾多網絡異常數據檢測方法中,人工免疫是入侵檢測系統中極為重要的一種檢測方法。人工免疫系統具備生物免疫系統的特性,擁有自我調節、免疫記憶、多樣生成和適應環境等特點,是一個能夠重復循環的檢測過程,通過調整變量來滿足大部分網絡檢測的要求。否定選擇算法是人工免疫系統中重要的算法之一,尤其是ZHOU等[3]提出的可以改變半徑的V-detector否定選擇算法,加快了檢測器的生成速度,也提高了效率,將隨機生成點作為檢測器中心點,然后進行判定。SAURABH等[4]提出了基于混沌映射參數的否定選擇算法,提高了否定選擇算法的覆蓋率。史樂[5]提出使用可以覆蓋自我區域的檢測器來減少自我樣本,從而提高了生成檢測器的效率。王韞燁等[6]設計了多組隨機種子編碼的方式來表示自體和不同檢測器的生成序列。CHEN等[7]設計了一種用高斯混合模型代替傳統檢測器生成過程的高效檢測器。ZHANG等[8]設計了一種根據候選檢測器與自體狀態空間的距離,通過聚類優化檢測器生成過程的檢測器。NAILA等[9]設計了一種基于抗原空間三角覆蓋的實值負選擇算法。ABID等[10]設計了一種具有相關特征子集的基于負選擇算法的網絡異常檢測方法。總體來說,否定選擇算法的本質其實是圍繞檢測器的生成,目的是減少產生檢測器的個數,使覆蓋率達到更高。

1.2 否定選擇算法

否定選擇算法是基于人工免疫系統的一種人工免疫系統算法,主要通過人體的模擬過程來設計算法。否定選擇算法也稱為負選擇算法,用于識別非自體以達到識別數據的目的。在該算法過程中,檢測器的生成尤為重要,檢測器是一組與任何自身樣本數據即測試數據都不匹配的檢測器集,檢測器的生成通常會伴隨著很多的算法。NSA將系統分為自體和非自體兩個部分,隨機生成大量具有識別功能的候選檢測器,使這些候選檢測器和自體部分中每一個自體進行識別與學習,得到自體的相關信息,經過識別后的檢測器得到自體的信息,然后成為成熟的檢測器,將其留下,隨后參加非體和自體的識別[7]。NSA的所有成熟檢測器在生成過程中,學習了自體的信息,因此所有的成熟檢測器都不會與自體識別。將一個需要被檢測的未知狀態空間與所有的檢測器進行匹配,如果存在匹配,則這空間就是一個非自體區域,如果不匹配,則是一個自體區域。

否定選擇算法采用了隨機生成的方式,對檢測器的初始點進行生成,在測試區域內自我生成一個點,然后判斷該點是否為自我點或非自我點,因為是隨機生成,所以可能會導致生成點在自我點上,會造成一些誤差。

1.3 V-detector否定選擇算法

V-detector否定選擇算法是基于否定選擇算法的一種可變半徑的否定選擇算法,可以調整每個檢測器的半徑達到最接近自體的范圍,從而使生成的檢測器能夠最大化地覆蓋非自體范圍[11]。該算法的檢測器生成時間比NSA的檢測器生成時間更短,在成熟檢測器集生成之前,每個候選檢測器都將對所有自體狀態空間進行識別,在將所有自體狀態空間都匹配后,若發現不存在匹配,則需要把該候選檢測器加到已成熟檢測器集合中進行匹配。如果都不能夠匹配,則需要把該檢測器定義為成熟檢測器,放入成熟檢測器集合,否則如果上述某一步驟產生了相反結果,則除去該檢測器[8]。同時會對當前成熟檢測器覆蓋率記錄數P進行加1操作,每次匹配若出現未匹配自體特征空間卻與任一成熟檢測器匹配,則P都會加1,當P值達到了提前設定的數值1/(1-p),其中p為期望覆蓋率,就代表生成了相同于P個成熟檢測器匹配的檢測器,則根據Monte Carlo的理論,結束檢測器生成過程。

2 基于三角剖分的否定選擇算法

2.1 算法的改進思想

基于三角剖分的否定選擇算法,在原有的V-detector否定選擇算法的基礎上,將V-detector否定選擇算法中隨機生成的思想除去,改為三角分配,也就是利用三角剖分[9,12]來確定檢測器中心位置,這樣能夠有效減少在實驗中因為隨機性帶來的誤判?；谌瞧史值姆穸ㄟx擇算法,計算抗原空間里的自體與非自體的分布情況,根據三角剖分所確定的外接圓圓心直接確定探測器的位置,然后通過外接圓的自身半徑確定覆蓋面積。這樣就可以用少量的檢測器覆蓋足夠大的范圍。另外,通過完整的自體測試以及由生成的檢測器直接確定為成熟檢測器的特點,縮短了檢測器生成時間。

三角剖分算法通過引入“三角分配”的概念,將所有自我點事先分配到位,這些點統稱為中心點,利用這些點,可以確定超級三角形以及它的外接圓,這樣就免去了隨機生成這個環節,大大縮短了生成成熟檢測器的時間,且檢測器的生成會更加簡單。基于三角剖分的否定選擇算法在生成的檢測器區域中不包含自我部分,也就是說,自我數據沒有被算法覆蓋,算法只覆蓋非我部分,這樣能夠捕捉到大部分的非我部分,加強算法精度。算法開始時就帶入了自我點進行計算,可以大大減少檢測器的數量,避免與其他否定選擇算法使用同樣的隨機生成,進一步提高了檢測器的生成效率[13]。

2.2 算法的基本流程

算法的主要步驟如下:

Step1 將訓練數據集帶入一個[0,1]的n維空間;

Step2 使用Delaunay三角剖分算法對待測數據進行拓撲運算,生成一組簡單的三角形,將每一個點插入到三角剖分所產生的三角網中;

Step3 使用Delaunay三角剖分算法,得到與每個三角形對應的外接圓,將外接圓保存;

Step4 考慮檢測器的覆蓋范圍必須排除自體狀態空間,將每個外界圓用其自己的半徑減去自體狀態空間的半徑,中心點仍是外界圓的中心;

Step5 最后檢測所生成圓的覆蓋范圍是否在算法指定的參數之內,如果在,則這個圓就是成熟的檢測器。

基于三角剖分的否定選擇算法的偽碼如下:

Input:輸入測試集V;

Output:檢測器集合A;

初始化檢測器集合A;

初始化頂點列表;

得到自體半徑R;

檢測器半徑r = 0;

創建索引列表(indices = new Array(V.length));(索引列表中的值為0,1,2,…,頂點長減去1);

基于V中的頂點x坐標對indices進行sort;(分類后的索引值順序為頂點坐標從小到大排列);

確定超級三角形;

將超級三角形保存到未確定的三角形列表Tt;

將超級三角形push確定的三角形列表T;

遍歷整個indices順序中每個V的點;

初始化邊緩存數組EB;

遍歷Tt中的每一個三角形;

計算該三角形的圓心和半徑Br;

保存外接圓于外接圓集B和半徑Br;

If(如果該點在外接圓的右側){

則該三角形為Delaunay三角形,保存到確定三角形列表中;

并在Tt中除去;}

If(如果該點在外接圓外){

則該三角形為不確定;}

If(如果該點在外接圓內){

則該三角形不為Delauny三角形;

將三邊保存至EB;

在Tt中除去該三角形;}

對EB去重;

將EB的邊與當前的點進行組合,將形成的三角形保存到Tt中將確定T和Tt形列表合并;

去除超級三角形;

計算r = Br-R;

If(r<0||rrmax){

則將該檢測器除去;}

Else {

則將檢測器保存至A;}

END

基于Delaunay三角剖分的否定選擇算法檢測器過程可用如下四個圖進行描述,其中,圖1為自體數據,圖2為Delaunay三角形構成的三角網,圖3為三角網的外接圓,圖4為最終檢測器。

圖1 自體數據

圖2 Delaunay三角形構成的三角網

圖3 三角網的外接圓

圖4 最終檢測器

3 實驗結果

3.1 數據集

實驗采用JAVA語言進行編程,運行在個人主機上,CPU主頻為2.3 GHz,內存為4 G。實驗采用PENTAGRAM-MID、STRIPE-MID、RING-MID、TRIANGLE-MID、CROSS-MID五種數據集,每個數據集都包含了1 000個二維數據,特征閾值均為2,且采用特征閾值的方式進行特征子集的選擇,從而實現了檢測器生成辨認自體與非自體的區別。這五種數據集均由網絡異常數據檢測得到,隨機生成且覆蓋面積廣,可用于處理網絡數據檢測和算法可行性問題[14]。

3.2 對比算法

為了驗證基于Delaunay三角剖分的否定選擇算法的優越性,將其與V-detector算法以及改進的V-detector算法進行比較,在五個數據集上對這三種否定選擇算法進行測試。測試結果分別取最大值和最小值,然后計算其平均值,得到檢測率和虛警率[10]。三種算法的覆蓋率均設置為99%,自體閾值能自我改變。自體閾值隨機取,本實驗分別采用0.025、0.01、0.04三種取值。實驗結果如圖5至圖9所示(V型表示V-detector算法,改進V型表示改進V-detector算法)。

圖5 PENTAGRAM-MID測試集的測試結果

圖6 RING-MID測試集的測試結果

圖7 STRIPE-MID測試集的測試結果

圖8 TRIANGLE-MID測試集的測試結果

圖9 CROSS-MID測試集的測試結果

從圖5到圖9可以看出,在預期覆蓋率為99%的情況下,面對不同的數據集,基于三角剖分的否定選擇算法的檢測率始終高于其他兩種算法,這體現了基于三角剖分的否定選擇算法在生成檢測器性能方面的優勢,其誤差始終保持在0,也就是算法在去除隨機生成后,利用三角剖分的計算幾何方法,使檢測器生成的點固定,不會生成在自體范圍內,這也是虛警率始終高于其他兩種算法的原因。同時,基于三角剖分的否定選擇算法的檢測率幾乎都比V-detector算法高,這是因為通過三角剖分算法實行的覆蓋方式,使檢測率在任何環境或者條件下都能穩定,體現了三角剖分算法的高效率。

當自體閾值(兩自體之間的距離)不斷增大時,其他算法會因為自體閾值而變得越來越不能完全檢測,而基于三角剖分的否定選擇算法的運行幾乎不會受到影響,檢測率仍然能與V-detector算法的檢測率相同,甚至更高,體現了三角剖分算法對檢測器檢測率的影響,表明三角剖分算法更加高效且穩定。

4 結語

本文提出了基于Delaunay三角剖分的否定選擇算法,通過計算幾何中的三角剖分,對數據進行三角分析,形成三角網,根據三角網中每條邊不重疊、不交叉的特性,以及外接圓的性質,給出了一種更合理的檢測器生成方式。通過實驗數據可知,基于Delaunay三角剖分的否定選擇算法,只需要較少的檢測器就可以覆蓋非自體空間,因三角剖分的特性避免了生成過多的檢測器,而且跳過了檢測器自身的自容性測試,大大地提高了生成檢測器的效率,在性能上遠高出其他否定算法,其誤報率也遠低于其他算法。