一種基于肯定選擇的異常檢測方法

范九倫， 蘇　晗

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

一種基于肯定選擇的異常檢測方法

范九倫， 蘇晗

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

摘要:對肯定選擇算法進(jìn)行優(yōu)化，以提高異常檢測的檢測率。對網(wǎng)絡(luò)中的正常行為特征進(jìn)行K均值聚類，以各類的中心作為檢測器并加入成熟檢測器集合;使用肯定選擇方法將檢測到的異常行為特征進(jìn)行K均值聚類，產(chǎn)生新的檢測器且加入到成熟檢測器集合中;檢測器的檢測順序隨著檢測器與測試數(shù)據(jù)匹配次數(shù)的增加而優(yōu)先，再根據(jù)二次免疫理論將成熟檢測器集合中檢測順序優(yōu)先的檢測器加入到記憶檢測器集合。分別使用優(yōu)化后的方法和基于集群概率的檢測方法對abalone數(shù)據(jù)集進(jìn)行檢測，結(jié)果顯示，優(yōu)化后的方法在測試數(shù)據(jù)為200時(shí)，檢測率可提高1.8%，整體檢測性能較優(yōu)。

關(guān)鍵詞:人工免疫；入侵檢測；肯定選擇；聚類

入侵檢測系統(tǒng)(IntrusionDetectionSystem,IDS)的作用是加強(qiáng)信息網(wǎng)絡(luò)和通信系統(tǒng)的安全性,衡量其性能的指標(biāo)有檢測率、誤警率和檢測速率[1]。

按照檢測原理，入侵檢測系統(tǒng)可分為誤用檢測和異常檢測兩類[2]：誤用檢測根據(jù)已知的攻擊建立初始特征庫，當(dāng)發(fā)現(xiàn)用戶的行為特征與特征庫的記錄相匹配時(shí)，認(rèn)為遭受入侵行為；異常檢測先建立正常行為特征的數(shù)據(jù)庫，對系統(tǒng)和應(yīng)用程序的行為特征和正常行為特征相比較，當(dāng)與正常行為有明顯的偏差時(shí)認(rèn)為該行為是入侵。誤用檢測系統(tǒng)與異常檢測系統(tǒng)相比，誤警率的低，但不能檢測出新的入侵行為，而異常檢測卻可以。誤用檢測需要指定已知入侵行為先驗(yàn)的特征數(shù)據(jù)庫，而異常檢測只需知道正常行為的一些信息。

生物免疫系統(tǒng)(BiologyImmuneSystem,BIS)是高度復(fù)雜、自組織和具有動(dòng)態(tài)平衡能力的分布式系統(tǒng)，能夠區(qū)分自體和非自體，抵御和消除外來的病毒入侵，維持生物體正常生命活動(dòng)的穩(wěn)定[3]。基于由此演化而來的人工免疫系統(tǒng)(ArtificialImmuneSystem,AIS)，人們得出許多入侵檢測方法。

基于B細(xì)胞生成原理的否定選擇算法(NegativeSelectionAlgorithm,NSA)[4]，是基于免疫系統(tǒng)的主要檢測方法之一。否定選擇算法中基于二進(jìn)制的方法得到廣泛應(yīng)用，但是二進(jìn)制具有空間局限性，無法適應(yīng)復(fù)雜網(wǎng)絡(luò)環(huán)境。若用實(shí)值形式反映空間結(jié)構(gòu)，用歐幾里德距離描述檢測器[5]，那么，由于檢測器的半徑難以估計(jì)，檢測器對非自體集的覆蓋重復(fù)率高，必然導(dǎo)致檢測效率不高。高維實(shí)值空間下的檢測器分布優(yōu)化算法[6]可提高對非自體空間的覆蓋率，但卻不能很好地解決檢測器間存在重復(fù)的問題。

基于肯定選擇原理的肯定選擇算法(positiveselectionalgorithm,NSA)[7]，訓(xùn)練自體樣本產(chǎn)生檢測器，無需通過學(xué)習(xí)產(chǎn)生檢測器，只需利用自我集合即可產(chǎn)生檢測器。有實(shí)驗(yàn)表明[8]，該方法在分類檢測方面優(yōu)于否定選擇算法，但當(dāng)自我樣本數(shù)量較多時(shí)，運(yùn)算時(shí)間呈指數(shù)增長，時(shí)間復(fù)雜度很大。

本文將給出一種實(shí)值聚類肯定算法(realvalueclusteredpositiveselectionalgorithm,RVCPS)，對自體集聚類得到初始檢測器，讓檢測器的檢測順序動(dòng)態(tài)變化，根據(jù)二次免疫理論，選擇性能較優(yōu)的檢測器，加入記憶檢測器集合，以提高檢測效率。

1基于RVCPS算法的異常檢測

1.1檢測器的生成

檢測器是整個(gè)入侵檢測的核心，檢測器的好壞直接決定了入侵檢測系統(tǒng)的性能。基于人工免疫的入侵檢測系統(tǒng)很難完整定義自體集和非自體集，這是因?yàn)椋泽w集包含很多子集合，每個(gè)子集合都是自體集的一部分，各子集之間的行為特征都不相同，它們代表著不同類型的正常行為特征[9]。考慮到聚類算法可將一個(gè)數(shù)據(jù)集劃分為若干個(gè)類，其中相似數(shù)據(jù)劃歸為一類，差別較大數(shù)據(jù)劃入不同類，從而使每類數(shù)據(jù)具有相似特征，各類數(shù)據(jù)具有較大差異，現(xiàn)對自體集進(jìn)行聚類產(chǎn)生檢測器。

定義1(形態(tài)空間)一個(gè)n維的形態(tài)空間A，包含所有的正常行為特征和所有的異常行為特征。

集合S的每個(gè)元素都是一個(gè)n維向量，每一維代表了不同的行為特征。

實(shí)值肯定選擇算法將所有狀態(tài)定義在n維空間，由于各維屬性都有不同衡量標(biāo)準(zhǔn)，需要對原始數(shù)據(jù)正規(guī)化處理[10]。利用公式

將各屬性值映射到區(qū)間[0,1]。

采用K均值聚類算法對自體集合進(jìn)行聚類，每類代表一個(gè)檢測器。用類中心和半徑描述該檢測器，這樣，每個(gè)檢測器就是一個(gè)超球體[11]。對接近某檢測器的待檢測數(shù)據(jù)，若其與檢測器中心的歐氏距離小于超球體半徑，則認(rèn)為此數(shù)據(jù)與檢測器匹配，標(biāo)記為“自我”，否則，轉(zhuǎn)入下一檢測器，繼續(xù)進(jìn)行匹配判斷。

1.2優(yōu)先檢測器

對于下一檢測器的定義，現(xiàn)行檢測機(jī)制大都隨機(jī)指定，或按設(shè)定好的序列選取。實(shí)際上，用戶打開一個(gè)或者多個(gè)應(yīng)用后，在一段時(shí)間內(nèi)會持續(xù)使用這些應(yīng)用，該段時(shí)間可分為許多很短的時(shí)隙，在每個(gè)時(shí)隙中，應(yīng)用程序所產(chǎn)生的行為特征幾乎一樣，因此，短時(shí)間內(nèi)得到的待檢測樣本大多具有相同行為特征。基于計(jì)算機(jī)應(yīng)用程序的這一特征，對每個(gè)檢測器設(shè)置動(dòng)態(tài)的優(yōu)先級，優(yōu)先級最高的檢測器第一個(gè)開始檢測。通過檢測器的優(yōu)先級機(jī)制，可以減少時(shí)間復(fù)雜度，提高檢測效率。

定義3(匹配次數(shù))記檢測器的匹配次數(shù)為c，其初始值為0。檢測器匹配到一個(gè)待測數(shù)據(jù)后，匹配次數(shù)c值加1。

假設(shè)待檢測樣本集合為

T={t1,t2,…,tN},

K個(gè)檢測器的初始優(yōu)先級順序?yàn)閐1,d2,…,dK。從n=1開始，若待測樣本tn與第1個(gè)檢測器匹配，則對檢測器的優(yōu)先級順序不作調(diào)整；若待測樣本tn未能與前k個(gè)檢測器匹配，而與第k+1個(gè)檢測器匹配，則調(diào)整檢測器優(yōu)先級順序，即交換第k和第k+1個(gè)檢測器的位置，讓后者成為優(yōu)先級更高的檢測器。

1.3異常檢測器

如果待檢測樣本是異常行為的樣本，它會首先計(jì)算和優(yōu)先級最高檢測器之間的歐氏距離，結(jié)果自然是不會被這個(gè)檢測器匹配，也不會被后面的任何一個(gè)檢測器所匹配，這個(gè)待測樣本最后會被標(biāo)記為“異常”。

當(dāng)檢測進(jìn)行一段時(shí)間后，被標(biāo)記為異常的樣本會越來越多。設(shè)定一個(gè)閾值M，當(dāng)被標(biāo)記的異常樣本數(shù)量大于該閾值M，且檢測器集合中檢測數(shù)量k小于檢測器集合容量K時(shí)，將這些異常樣本采用與自體集合相同的聚類算法進(jìn)行分類，并選取其中k′(k′≤K-k)個(gè)類加入檢測器集合。此時(shí),檢測器集合中既包含自我檢測器,又包含異常檢測器，且自我檢測器和異常檢測器具有不同標(biāo)簽。如此可使檢測器具備學(xué)習(xí)性，能夠檢測到新的異常類型。當(dāng)待測數(shù)據(jù)與異常檢測器匹配時(shí)則認(rèn)為此數(shù)據(jù)為異常。

檢測器子模塊可描述如下。

If(檢測器集合不為空)

檢測器按照優(yōu)先級順序依次與待測數(shù)據(jù)進(jìn)行匹配；

If(匹配)

{查看該檢測器標(biāo)簽，并標(biāo)記該待測數(shù)據(jù)；

該檢測器匹配次數(shù)值++；

該檢測器優(yōu)先級++；

}

Else將待測數(shù)據(jù)標(biāo)記為異常；

End

1.4記憶檢測器

生物免疫系統(tǒng)遭受初次外來病原入侵后，免疫系統(tǒng)能夠發(fā)揮記憶效應(yīng)，作出二次免疫應(yīng)答，當(dāng)再次遭受同樣的病原入侵時(shí)，即可快速高效地產(chǎn)生大量抗體，將抗原清除[12]。在入侵檢測中利用二次免疫的機(jī)理可以快速檢測到異常。

將檢測器集合中匹配次數(shù)c大于閾值H的檢測器激活,加入記憶檢測器集合，并將匹配次數(shù)c清零。每次檢測開始讓待測數(shù)據(jù)和記憶檢測器相匹配，每匹配一次，匹配次數(shù)c加1，一段時(shí)間后檢查各檢測器的c值，將c值為0的記憶檢測器刪除，以保證記憶檢測器集合中都是精英集合器。

記憶檢測器子模塊可描述如下。

If(記憶檢測器集合不為空)

記憶檢測器按優(yōu)先級順序依次與待測數(shù)據(jù)匹配；

If(匹配)

{

查看該檢測器標(biāo)簽，并標(biāo)記該待測數(shù)據(jù)；

該檢測器匹配次數(shù)值++；

該檢測器優(yōu)先級++；

}

Else將待測數(shù)據(jù)交給檢測器集合進(jìn)行匹配；

End

2實(shí)驗(yàn)結(jié)果及分析

使用abalone數(shù)據(jù)集作為測試數(shù)據(jù)集，測試性能通過檢測率(Detectionrate,DR)和誤警率(Falsealarmrate,FA)兩大指標(biāo)體現(xiàn)。

以TP代表判定為異常的異常數(shù)據(jù)個(gè)數(shù)，TN代表判定為正常的正常數(shù)據(jù)個(gè)數(shù)，F(xiàn)P代表判定為異常的正常數(shù)據(jù)個(gè)數(shù)，F(xiàn)N代表判定為正常的異常數(shù)據(jù)個(gè)數(shù)。分別定義檢測率和誤警率為

abalone數(shù)據(jù)集每條數(shù)據(jù)都有9個(gè)屬性，選取其中7個(gè)屬性，共4 178個(gè)數(shù)據(jù)進(jìn)行測試。將abalone數(shù)據(jù)集中標(biāo)記為F和M的數(shù)據(jù)認(rèn)為是正常數(shù)據(jù)，標(biāo)記為I的認(rèn)為是異常數(shù)據(jù)。利用其中2 300個(gè)正常數(shù)據(jù)作為自體集，進(jìn)行K均值聚類，生成初始檢測器。將自體集合分為80個(gè)小類,檢測器集合最大容量設(shè)為100。在檢測階段，選取300個(gè)異常數(shù)據(jù)和700個(gè)正常數(shù)據(jù)進(jìn)行測試，所得結(jié)果如圖1所示。

圖1　abalone數(shù)據(jù)集檢測率和誤警率

由圖2可見，檢測器半徑是影響檢測器性能的主要因素，檢測器的半徑越小檢測率越高，但相應(yīng)的誤警率也較高。在半徑較小的時(shí)候，測試數(shù)據(jù)與聚類中心點(diǎn)的歐氏距離幾乎都比半徑大，造成很多的正常數(shù)據(jù)被檢測器標(biāo)記為異常數(shù)據(jù)，造成誤判，使得誤警率較大。實(shí)驗(yàn)顯示，對于abalone數(shù)據(jù)集而言，當(dāng)檢測器的半徑為0.18時(shí)檢測的性能最佳。

基于集群概率的檢測方法(clusteredprobabilisticartificialimmune,CPAI)[13]，借用肯定選擇算法，通過對自體集聚類，并計(jì)算概率密度函數(shù)來檢測異常。選擇abalone數(shù)據(jù)集，設(shè)置10組實(shí)驗(yàn)，每組測試數(shù)據(jù)中正常數(shù)據(jù)與異常數(shù)據(jù)比例為7∶3,檢測器半徑設(shè)為0.18，對比RVCPS算法與CPAI算法的檢測率，結(jié)果如圖2所示。

圖2　RVCPS算法與CPAI算法檢測率對比

參與對比的兩種檢測方法都具有較高檢測率，但相比而言，RVCPS算法要高于CPAI算法。另外，兩種算法的檢測率都會隨著測試數(shù)據(jù)量的增加而減小，這主要是由于，檢測器是自體集聚類所產(chǎn)生，當(dāng)測試數(shù)據(jù)越來越多時(shí)候，在肯定選擇過程中沒有出現(xiàn)的正常數(shù)據(jù)越來越多，檢測器不能完全的識別這些正常數(shù)據(jù)，從而引起檢測率隨測試樣本數(shù)量的變化。

3結(jié)語

給出一種基于實(shí)值聚類的肯定選擇，通過自體集聚類產(chǎn)生檢測器，引入優(yōu)先級和二次免疫的概念，可提高檢測器生成效率和檢測效率。將異常檢測器加入到檢測器集合，可使檢測器具備多樣性和檢測未知異常的能力，同時(shí)避免否定選擇算法隨機(jī)選擇樣本所帶來的弊端。實(shí)驗(yàn)顯示，所給方法是一種有效的異常檢測方法。檢測器半徑的選擇是影響所給方法性能的重要因素，仍需尋求找到最佳半徑的有效方法。

參考文獻(xiàn)

[1]張玲,白中英,羅守山,等.基于粗糙集和人工免疫的集成入侵檢測模型[J/OL].通信學(xué)報(bào),2013,34(9):166-176[2015-10-10].http://mall.cnki.net/magazine/article/TXXB201309020.htm.

[2]蘆天亮,鄭康鋒,傅蓉蓉,等.基于陰性選擇算法的異常檢測系統(tǒng)黑洞覆蓋優(yōu)化[J/OL].通信學(xué)報(bào),2013,34(1):128-135[2015-10-10].http://mall.cnki.net/magazine/article/TXXB201301014.htm.

[3]金章贊,廖明宏,肖剛.否定選擇算法綜述[J/OL].通信學(xué)報(bào),2013,34(1):159-170[2015-10-10].http://mall.cnki.net/magazine/article/TXXB201301017.htm.

[4]FORRESTS,PERELSONAS,ALLENL,etal.Self-nonselfdis-criminationinacomputer[C/OL]//ProceedingsofIEEESymposiumonResearchinSecurityandPrivacy.USACALosAlamitos:IEEE,1994:202-212[2015-10-10].http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.453.1098.

[5]GONZALEZFA,DASGUPTAD.Anomalydetectionusingreal-valuednegativeselection[J/OL].GeneticProgrammingandEvolvableMachines,2003,4(4):383-403[2015-10-10].http://d.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ029895553.

[6]劉海龍,張鳳斌,席亮.免疫入侵檢測高維實(shí)值檢測器分布優(yōu)化算法[J/OL].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2012,52(10):1415-1419[2015-10-10].http://mall.cnki.net/magazine/Article/QHXB201210016.htm.

[7]STIBORT,MOHRP,TIMMISJ,etal.Isnegativeselectionappropriateforanomalydetection[C/OL〗//GECCO’05Proceedingsofthe7thannualconferenceonGeneticandevolutionarycomputation.NewYork:ACM, 2005:321-328[2015-10-10].http://dx.doi.org/10.1145/1068009.1068061.

[8]洪征,吳禮發(fā).基于陽性選擇的蠕蟲檢測系統(tǒng)[J/OL].軟件學(xué)報(bào),2010,21(4):816-826[2015-10-10].http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201004022.htm.

[9]MOHAMMADIM,AKBARIA,RAAHEMIB,etal.Afastanomalydetectionsystemusingprobabilisticartificialimmunealgorithmcapableoflearningnewattacks[J/OL].EvolutionaryIntelligence, 2014,6(3):135-156[2015-10-10].http://link.springer.com/article/10.1007/s12065-013-0101-3.

[10] 羅敏,王麗娜,張煥國.基于無監(jiān)督聚類的入侵檢測方法[J/OL].電子學(xué)報(bào),2003,31(11):1713-1717[2015-10-10].http://mall.cnki.net/magazine/article/DZXU200311027.htm.

[11]GONZALEZFA,DASGUPTAD.Anomalydetectionusingreal-valuednegativeselection[J/OL].GeneticProgrammingandEvolvableMachines, 2003,4(4):383-403[2015-10-10].http://d.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ029895553.DOI:10.1023/A:1026195112518.

[12] 蘆天亮,鄭康鋒,劉穎卿 ,等.基于動(dòng)態(tài)克隆選擇算法的病毒檢測模型[J/OL].北京郵電大學(xué)學(xué)報(bào),2013,36(3):39-43[2015-10-10].http://www.cnki.com.cn/Article/CJFDTotal-BJYD201303010.htm.

[13] 高煒,曹銳.一種基于集群概率的網(wǎng)絡(luò)入侵檢測算法[J/OL].電子技術(shù)與軟件工程,2015(8):231-234[2015-10-10].http://www.cnki.com.cn/Article/CJFDTotal-DZRU201508169.htm.

[責(zé)任編輯:瑞金]

Ananomalydetectionmethodbasedonpositiveselectionalgorithm

FANJiulun,SUHan

(SchoolofCommunicationandInformationEngineering,Xi’anUniversityofPostsandTelecommunications,Xi’an710121,China)

Abstract:The traditional positive selection algorithm is optimized to improve the detection rate of anomaly detection. In the method, k-means clustering algorithm is applied on normal behaviors in the network, each class center is regarded as a detector, and the detectors are added to the mature detector set. The positive selection method is used to get a k-means clustering of the detected abnormal behavior characteristics, and the produced detectors are also added to the mature detector set. The priority of the detector in detection sequence is preferred, if the matching times of the the detector and the test data increase. According to the secondary immune theory, the detectors with high priority are added to the memory detector set. The optimization method and clustered probabilistic artificial immune method are used to detect the abalone data sets, and experiments results show that, the optimization method performs well in generral, and when the test data is 200, its detection rate increases by 1.8%.

Keywords:artificial immune, intrusion detection, positive selection, clustering

doi:10.13682/j.issn.2095-6533.2016.02.002

收稿日期：2015-11-30

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61340040；61202183；61102095)

作者簡介：范九倫(1964-)，男，博士，教授，博士生導(dǎo)師，從事模式識別和信息安全研究。E-mail: jiulunf@163.com 蘇晗(1990-)，男，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。E-mail: suhanarppp@163.com

中圖分類號：TN915.08

文獻(xiàn)標(biāo)識碼：A

文章編號：2095-6533(2016)02-0012-05