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

汪宏海,婁金霞,柴爭(zhēng)義

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

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展,網(wǎng)絡(luò)作為日常生活中不可或缺的一部分,其安全問題變得越來(lái)越重要,如何進(jìn)行網(wǎng)絡(luò)異常數(shù)據(jù)的檢測(cè)和識(shí)別,是網(wǎng)絡(luò)安全中的關(guān)鍵問題[1]。網(wǎng)絡(luò)異常數(shù)據(jù)檢測(cè)算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行檢測(cè)和定位,將正常數(shù)據(jù)和異常數(shù)據(jù)分離。基于免疫機(jī)制的否定選擇算法(Negative Selection Algorithm,NSA)[2]是一種非常有效的網(wǎng)絡(luò)異常檢測(cè)算法。V-detector算法是典型的否定選擇算法[3],由于其具有較好的性能,得到了研究者的廣泛關(guān)注。然而,V-detector算法面對(duì)復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)問題,由于檢測(cè)器的生成過程是隨機(jī)的,會(huì)使得檢測(cè)器生成過程耗時(shí)長(zhǎng),不利于在線檢測(cè)的快速實(shí)現(xiàn)。因此,本文提出了一種基于Delaunay三角剖分的否定選擇算法,即在檢測(cè)器的生成階段使用三角剖分對(duì)檢測(cè)器中心點(diǎn)進(jìn)行定位,直接生成成熟檢測(cè)器,算法以快速生成檢測(cè)器為主要目標(biāo),降低檢測(cè)個(gè)數(shù),從而降低檢測(cè)器生成時(shí)的資源消耗。

1 相關(guān)工作

1.1 研究背景

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

1.2 否定選擇算法

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

否定選擇算法采用了隨機(jī)生成的方式,對(duì)檢測(cè)器的初始點(diǎn)進(jìn)行生成,在測(cè)試區(qū)域內(nèi)自我生成一個(gè)點(diǎn),然后判斷該點(diǎn)是否為自我點(diǎn)或非自我點(diǎn),因?yàn)槭请S機(jī)生成,所以可能會(huì)導(dǎo)致生成點(diǎn)在自我點(diǎn)上,會(huì)造成一些誤差。

1.3 V-detector否定選擇算法

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

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

2.1 算法的改進(jìn)思想

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

三角剖分算法通過引入“三角分配”的概念,將所有自我點(diǎn)事先分配到位,這些點(diǎn)統(tǒng)稱為中心點(diǎn),利用這些點(diǎn),可以確定超級(jí)三角形以及它的外接圓,這樣就免去了隨機(jī)生成這個(gè)環(huán)節(jié),大大縮短了生成成熟檢測(cè)器的時(shí)間,且檢測(cè)器的生成會(huì)更加簡(jiǎn)單?；谌瞧史值姆穸ㄟx擇算法在生成的檢測(cè)器區(qū)域中不包含自我部分,也就是說,自我數(shù)據(jù)沒有被算法覆蓋,算法只覆蓋非我部分,這樣能夠捕捉到大部分的非我部分,加強(qiáng)算法精度。算法開始時(shí)就帶入了自我點(diǎn)進(jìn)行計(jì)算,可以大大減少檢測(cè)器的數(shù)量,避免與其他否定選擇算法使用同樣的隨機(jī)生成,進(jìn)一步提高了檢測(cè)器的生成效率[13]。

2.2 算法的基本流程

算法的主要步驟如下:

Step1 將訓(xùn)練數(shù)據(jù)集帶入一個(gè)[0,1]的n維空間;

Step2 使用Delaunay三角剖分算法對(duì)待測(cè)數(shù)據(jù)進(jìn)行拓?fù)溥\(yùn)算,生成一組簡(jiǎn)單的三角形,將每一個(gè)點(diǎn)插入到三角剖分所產(chǎn)生的三角網(wǎng)中;

Step3 使用Delaunay三角剖分算法,得到與每個(gè)三角形對(duì)應(yīng)的外接圓,將外接圓保存;

Step4 考慮檢測(cè)器的覆蓋范圍必須排除自體狀態(tài)空間,將每個(gè)外界圓用其自己的半徑減去自體狀態(tài)空間的半徑,中心點(diǎn)仍是外界圓的中心;

Step5 最后檢測(cè)所生成圓的覆蓋范圍是否在算法指定的參數(shù)之內(nèi),如果在,則這個(gè)圓就是成熟的檢測(cè)器。

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

Input:輸入測(cè)試集V;

Output:檢測(cè)器集合A;

初始化檢測(cè)器集合A;

初始化頂點(diǎn)列表;

得到自體半徑R;

檢測(cè)器半徑r = 0;

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

基于V中的頂點(diǎn)x坐標(biāo)對(duì)indices進(jìn)行sort;(分類后的索引值順序?yàn)轫旤c(diǎn)坐標(biāo)從小到大排列);

確定超級(jí)三角形;

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

將超級(jí)三角形push確定的三角形列表T;

遍歷整個(gè)indices順序中每個(gè)V的點(diǎn);

初始化邊緩存數(shù)組EB;

遍歷Tt中的每一個(gè)三角形;

計(jì)算該三角形的圓心和半徑Br;

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

If(如果該點(diǎn)在外接圓的右側(cè)){

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

并在Tt中除去;}

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

則該三角形為不確定;}

If(如果該點(diǎn)在外接圓內(nèi)){

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

將三邊保存至EB;

在Tt中除去該三角形;}

對(duì)EB去重;

將EB的邊與當(dāng)前的點(diǎn)進(jìn)行組合,將形成的三角形保存到Tt中將確定T和Tt形列表合并;

去除超級(jí)三角形;

計(jì)算r = Br-R;

If(r<0||rrmax){

則將該檢測(cè)器除去;}

Else {

則將檢測(cè)器保存至A;}

END

基于Delaunay三角剖分的否定選擇算法檢測(cè)器過程可用如下四個(gè)圖進(jìn)行描述,其中,圖1為自體數(shù)據(jù),圖2為Delaunay三角形構(gòu)成的三角網(wǎng),圖3為三角網(wǎng)的外接圓,圖4為最終檢測(cè)器。

圖1 自體數(shù)據(jù)

圖2 Delaunay三角形構(gòu)成的三角網(wǎng)

圖3 三角網(wǎng)的外接圓

圖4 最終檢測(cè)器

3 實(shí)驗(yàn)結(jié)果

3.1 數(shù)據(jù)集

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

3.2 對(duì)比算法

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

圖5 PENTAGRAM-MID測(cè)試集的測(cè)試結(jié)果

圖6 RING-MID測(cè)試集的測(cè)試結(jié)果

圖7 STRIPE-MID測(cè)試集的測(cè)試結(jié)果

圖8 TRIANGLE-MID測(cè)試集的測(cè)試結(jié)果

圖9 CROSS-MID測(cè)試集的測(cè)試結(jié)果

從圖5到圖9可以看出,在預(yù)期覆蓋率為99%的情況下,面對(duì)不同的數(shù)據(jù)集,基于三角剖分的否定選擇算法的檢測(cè)率始終高于其他兩種算法,這體現(xiàn)了基于三角剖分的否定選擇算法在生成檢測(cè)器性能方面的優(yōu)勢(shì),其誤差始終保持在0,也就是算法在去除隨機(jī)生成后,利用三角剖分的計(jì)算幾何方法,使檢測(cè)器生成的點(diǎn)固定,不會(huì)生成在自體范圍內(nèi),這也是虛警率始終高于其他兩種算法的原因。同時(shí),基于三角剖分的否定選擇算法的檢測(cè)率幾乎都比V-detector算法高,這是因?yàn)橥ㄟ^三角剖分算法實(shí)行的覆蓋方式,使檢測(cè)率在任何環(huán)境或者條件下都能穩(wěn)定,體現(xiàn)了三角剖分算法的高效率。

當(dāng)自體閾值(兩自體之間的距離)不斷增大時(shí),其他算法會(huì)因?yàn)樽泽w閾值而變得越來(lái)越不能完全檢測(cè),而基于三角剖分的否定選擇算法的運(yùn)行幾乎不會(huì)受到影響,檢測(cè)率仍然能與V-detector算法的檢測(cè)率相同,甚至更高,體現(xiàn)了三角剖分算法對(duì)檢測(cè)器檢測(cè)率的影響,表明三角剖分算法更加高效且穩(wěn)定。

4 結(jié)語(yǔ)

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