王韞燁,孔 珊

(鄭州師范學(xué)院 信息科學(xué)與技術(shù)學(xué)院,鄭州 450044)

0 概述

異常檢測是在網(wǎng)絡(luò)和大數(shù)據(jù)安全分析中廣泛使用的關(guān)鍵技術(shù)。由于異常檢測系統(tǒng)與人體免疫系統(tǒng)有著高度的相似性,基于免疫機制的否定選擇算法在異常檢測中得到了深入應(yīng)用并取得良好的效果[1],成為解決異常檢測問題的主要算法之一。檢測器的生成是否定選擇算法中的重點部分,對檢測效率和準(zhǔn)確度具有重要影響[2]。因此,設(shè)計高效的檢測器生成算法是否定選擇算法研究的關(guān)鍵和熱點[3]。

否定選擇算法一般用字符串(含二進(jìn)制字符串)和實值表示[4]。實值否定選擇算法將自體與檢測器的各項屬性值表示為n維[0,1]實數(shù)范圍([0,1]n)內(nèi)的超立方體,更適合對現(xiàn)實問題進(jìn)行描述,因而得到廣泛應(yīng)用[5]。由于半徑固定的實值否定選擇算法存在許多黑洞區(qū)域無法被檢測器覆蓋和檢測,文獻(xiàn)[6]提出V-detector算法,該算法是一種半徑可變的實值否定選擇算法,可以顯著提高算法的檢測率,為實值否定選擇算法中最具代表性的算法,眾多后續(xù)研究與應(yīng)用都基于該算法展開[7-16]。

文獻(xiàn)[7]提出改進(jìn)的否定選擇算法,該算法增加了檢測器的覆蓋半徑。文獻(xiàn)[8]通過二次否定過程提高了檢測器生成性能。文獻(xiàn)[9]基于自體分布由遠(yuǎn)及近分層次產(chǎn)生檢測器,優(yōu)化了否定選擇算法的性能。文獻(xiàn)[10]在小型樣本空間中分離自體與非自體空間,提高了檢測器的檢測效率。文獻(xiàn)[11]通過分析抗原空間的密度,提升了實值否定選擇算法的性能。文獻(xiàn)[12]采用基于子空間密度搜索的改進(jìn)否定選擇算法提高了空間覆蓋率。文獻(xiàn)[13]對否定選擇算法性能參數(shù)進(jìn)行分析，指出各參數(shù)對檢測性能的影響。文獻(xiàn)[14]將主動學(xué)習(xí)和否定選擇算法進(jìn)行集成后應(yīng)用于垃圾郵件分類，增加了垃圾郵件分類準(zhǔn)確性。文獻(xiàn)[15]將改進(jìn)的否定選擇算法用于故障檢測，提升了檢測率。文獻(xiàn)[16]用否定選擇算法生成測試數(shù)據(jù)，有效提高了測試數(shù)據(jù)路徑覆蓋率。

上述否定選擇算法均取得了較好的效果,顯著提高了檢測器的生成效率。但采用否定選擇算法對數(shù)據(jù)進(jìn)行異常檢測時,需要對所有的檢測器進(jìn)行距離計算,這降低了檢測效率,增加了檢測時間,不利于快速檢測。

本文提出一種基于檢測器集層次聚類的否定選擇算法,對檢測器集進(jìn)行從上到下的層次聚類處理,只計算待檢測數(shù)據(jù)與聚類中心檢測器之間的距離,以減少計算時間和能耗,對未被檢測器匹配的數(shù)據(jù)進(jìn)行分類,并分別從檢測率、誤檢率及檢測時間等方面將本文否定選擇算法與V-detector算法和免疫實值否定選擇算法進(jìn)行對比分析。

1 算法關(guān)鍵技術(shù)

1.1 否定選擇算法的檢測過程

否定選擇算法的檢測過程由兩個階段構(gòu)成:一是訓(xùn)練階段,即檢測器的生成階段;二是檢測階段,即將待測數(shù)據(jù)通過檢測器按照是否正常進(jìn)行分類的階段[17]。

在檢測階段,待檢測數(shù)據(jù)需要與檢測器進(jìn)行匹配,因此,需要匹配的檢測器數(shù)量越少,對數(shù)據(jù)做出異常檢測的判斷就越快。

V-detector算法及其改進(jìn)算法檢測階段的過程為[6-11]:對任一需要檢測的數(shù)據(jù),計算其與所有檢測器的距離,若待檢測數(shù)據(jù)被任一檢測器覆蓋,則該待檢測數(shù)據(jù)被標(biāo)記為異常,否則該待檢測數(shù)據(jù)被標(biāo)記為正常。對于n維空間中待檢測數(shù)據(jù)t=(ct,rt)而言,將其與檢測器d=(cd,rd)之間距離記為dis=(t,d),其中ct為待檢測數(shù)據(jù)的中點,rt為待檢測數(shù)據(jù)的半徑,cd為檢測器的中點,rd為檢測器的半徑。為判斷待檢測數(shù)據(jù)是否異常,需要計算各待檢測數(shù)據(jù)ti(ti∈t)與所有的檢測器di(di∈d)之間的距離,其計算公式如下:

dis(ct,cd)=

(1)

若dis(ct,cd)

由否定選擇算法的檢測過程可以看出,該過程計算會耗費較多的計算時間,這不利于該算法的廣泛應(yīng)用。

1.2 改進(jìn)的否定選擇算法

本文在上述否定選擇算法的基礎(chǔ)上進(jìn)行改進(jìn),改進(jìn)后算法的主要思想為:對檢測器集D進(jìn)行從上到下的層次聚類處理,只計算待檢測數(shù)據(jù)t與聚類中心檢測器C之間的距離,不再計算待檢測數(shù)據(jù)t與所有聚類成員檢測器集D之間的距離,減少了計算時間和能耗。

1.3 檢測器集的層次聚類

本文設(shè)計的檢測器層次聚類過程為:

1)對否定選擇過程生成的成熟檢測器集D進(jìn)行層次聚類處理,每層生成的聚類中心構(gòu)成新的檢測器集C。

2)對于每個檢測集T中的數(shù)據(jù)t=(ct,rt),分別計算其與檢測器集C中每個檢測器Ci的距離,從而判斷該待檢測數(shù)據(jù)是否正常并進(jìn)行分類。其中,ct為待檢測數(shù)據(jù)的坐標(biāo),cc為檢測器Ci的坐標(biāo),rci為檢測器Ci的半徑。具體的判斷方法為:若dis(ct,cc)

在二維實值空間[0,1]2進(jìn)行仿真驗證如下:

由上述可見,層次聚類方法中聚類半徑逐漸減半,從而使得檢測更精確,在減少檢測時間的同時提高了檢測率。

1.4 孔洞數(shù)據(jù)的判定

在二維實值空間[0,1]2中,孔洞區(qū)是指沒有被任何檢測器覆蓋的檢測區(qū)域[18]。對于處于孔洞區(qū)的待檢測(分類)數(shù)據(jù),可以通過否定選擇算法將其分類為正常數(shù)據(jù)。然而未被檢測器覆蓋的區(qū)域有可能存在異常數(shù)據(jù)并導(dǎo)致分類錯誤,造成算法誤檢率升高[19]。在改進(jìn)后的否定選擇算法中,不再將待檢測數(shù)據(jù)簡單標(biāo)識為正常數(shù)據(jù),其性質(zhì)由檢測器與自體集的位置共同定量決定,即待檢測數(shù)據(jù)的異常性由該數(shù)據(jù)到最近檢測器的歐氏距離和最近自體的歐氏距離共同判定,分別表示為:

Dis1=min dis(t,ci),ci∈C

(2)

Dis2=min dis(t,si),si∈S

(3)

其中,Dis1為待分類數(shù)據(jù)t到檢測器集合C中所有檢測器ci的最短距離,Dis2為待分類數(shù)據(jù)t到自體集合S中所有自體si的最短距離。若Dis1>aDis2,則該待檢測數(shù)據(jù)為正常數(shù)據(jù),否則為異常數(shù)據(jù)。大量實驗研究結(jié)果表明,a的取值為自體半徑rs的20倍[18]。

2 算法流程

改進(jìn)后否定選擇算法的檢驗過程分為檢測器生成階段與異常檢測階段,該算法的基本步驟如下:

1)使用文獻(xiàn)[6]中V-detector算法生成成熟檢測器集D。

2)對檢測器集D進(jìn)行層次聚類處理,得到檢測器集C。

3)輸入數(shù)據(jù)集T進(jìn)行異常檢測(計算T中數(shù)據(jù)和檢測器集C中檢測器之間的距離。

4)進(jìn)行異常檢測判斷:如果被檢測數(shù)據(jù)與檢測器集C中的任一檢測器匹配,則為異常數(shù)據(jù),直接進(jìn)行第6步;如果被檢測數(shù)據(jù)未與檢測器集C中的任一檢測器匹配,進(jìn)行第5步。

5)如果被檢測數(shù)據(jù)未與檢測器集C中的任一檢測器匹配,則認(rèn)為其處于孔洞區(qū),需進(jìn)一步測試以判定其是否為正常數(shù)據(jù)并進(jìn)行標(biāo)識。

6)算法結(jié)束。

3 實驗結(jié)果與分析

在Windows 10環(huán)境下,使用JAVA對本算法進(jìn)行編程實現(xiàn)。實驗數(shù)據(jù)集為廣泛使用的人造二維數(shù)據(jù)集,對實驗結(jié)果以五角星形自體集為例進(jìn)行分析,并與經(jīng)典的V-detector算法[6]和免疫實值否定選擇算法[9]結(jié)果進(jìn)行對比。參數(shù)取值與所對比的文獻(xiàn)保持一致:數(shù)據(jù)取自二維實值空間[0,1]2,訓(xùn)練數(shù)據(jù)集容量為1 000個,測試數(shù)據(jù)集容量為1 000個,目標(biāo)覆蓋率分別為90%、95%和99%。分別從檢測率、誤檢率及檢測時間三方面對實驗結(jié)果進(jìn)行分析。

選擇實驗?zāi)繕?biāo)覆蓋率為95%,自體半徑的取值區(qū)間為[0.01,0.30](每隔0.05取一個值),每個自體半徑進(jìn)行100次實驗并取結(jié)果的平均值。

由圖1可以看出,3種不同算法的檢測率均隨著自體半徑的增大而降低,本文否定選擇算法的檢測率降幅比其他兩種算法更小。這是因為孔洞區(qū)數(shù)據(jù)隨著自體半徑的增大而增加,本文否定選擇算法由于對孔洞區(qū)數(shù)據(jù)的異常性進(jìn)行了判定,提高了孔洞區(qū)數(shù)據(jù)檢測的準(zhǔn)確性,從而提升了算法的檢測率。

圖1 檢測率隨自體半徑變化曲線

由圖2可以看出,3種不同算法的誤檢率均隨著自體半徑的增大而降低,本文否定選擇算法誤檢率的降幅比其他兩種算法的更大。這是因為孔洞區(qū)數(shù)據(jù)隨著自體半徑的增大而增加,在V-detector算法和免疫實值否定選擇算法中,孔洞區(qū)數(shù)據(jù)(部分?jǐn)?shù)據(jù)可能為異常數(shù)據(jù))全部被定義為正常數(shù)據(jù),而本文否定選擇算法對孔洞區(qū)數(shù)據(jù)異常性進(jìn)行了判定,有效降低了算法的誤檢率。

圖2 誤檢率隨自體半徑變化曲線

由圖1和圖2可知,檢測性能與自體半徑密切相關(guān),隨著自體半徑的增大,算法的檢測率和誤檢率均降低。因此,需根據(jù)實際問題選擇適合的自體半徑來調(diào)整算法的檢測性能。

由圖3和圖4可以看出,當(dāng)自體半徑為0.2時,3種算法的檢測率和誤檢率均隨著目標(biāo)覆蓋率的增大而增加;和其他兩種算法相比,本文否定選擇算法的檢測率更高且誤檢率更低;當(dāng)目標(biāo)覆蓋率為99%時,3種算法的檢測性能較接近,這是因為當(dāng)目標(biāo)覆蓋率為99%時,所需成熟檢測器的數(shù)量顯著增加,對非自體區(qū)域的覆蓋增大,處于孔洞區(qū)域的數(shù)據(jù)減少,此時本文否定選擇算法的優(yōu)勢不明顯。

圖3 檢測率隨期望覆蓋率變化曲線

圖4 誤檢率隨期望覆蓋率變化曲線

由表1可以看出,V-Detector算法在采用不同形狀檢測器時檢測時間均最長,免疫實值否定選擇算法的次之,本文、否定選擇算法最短;當(dāng)檢測器形狀為環(huán)形時,本文否定選擇算法的檢測時間最短。這是因為V-Detector算法由于需要計算各待檢測數(shù)據(jù)與檢測器集D中所有檢測器之間的距離以判斷數(shù)據(jù)是否異常,因而所需的檢測時間最長。

表1 不同算法的檢測時間結(jié)果對比

免疫實值否定選擇算法采用了檢測器分級生成方式,在同樣的檢測率下,需要的檢測器數(shù)量減少,因而所需的檢測時間比V-Detector算法要短。本文否定選擇算法由于用聚類中心檢測器C代替檢測器集D進(jìn)行距離計算(C的數(shù)量遠(yuǎn)小于D),因而所需的檢測時間最短。圓形檢測器與環(huán)形自體集的形狀較相似,匹配度較高,此時孔洞區(qū)待檢測數(shù)據(jù)較少,因而檢測時間最短。

4 結(jié)束語

為提高異常檢測的效率,本文提出一種基于檢測器集層次聚類的否定選擇算法,通過對檢測器集進(jìn)行層次聚類,以聚類中心檢測器代替初始檢測器集進(jìn)行距離計算,減少計算時間并對未被檢測器覆蓋的孔洞區(qū)域?qū)傩赃M(jìn)行進(jìn)一步判斷。實驗結(jié)果表明,本文否定選擇算法較V-detector算法和免疫實值否定選擇算法所需時間大幅減少,檢測效率提高且誤檢率降低。下一步將在本文算法的基礎(chǔ)上對聚類中心集和檢測器集的數(shù)量關(guān)系進(jìn)行研究。