摘 要:探討基于孤立點挖掘的異常檢測的可行性，將基于2k-距離的孤立點挖掘方法應(yīng)用到入侵檢測中，并針對該方法無法很好地處理符號型屬性數(shù)據(jù)的問題，采用編碼映射方法對符號型數(shù)據(jù)進行處理，同時利用主成分分析來實現(xiàn)對編碼映射后擴展的屬性進行降維。詳細闡述了具體實現(xiàn)方案，并通過仿真實驗驗證了該方法的可行性。

關(guān)鍵詞: 入侵檢測; 孤立點; 2k-距離; 編碼映射; 主成分分析

中圖分類號:TP391 文獻標識碼:A

文章編號:1004-373X(2010)11-0114-03

Intrusion Detection Method Based on Outlier Mining

YANG Cheng-cheng1， HUANG Bin2

(1. Chang’an University， Xi’an 710021， China; 2. Putian University， Putian 351100，China)

Abstract: The feasibility of the anomaly detection based on the outlier mining is discussed. The anomaly detection method is presented. The outlier detection method based on similar coefficient sum is applied to the intrusion detection. In order to overcome the poor ability of outlier detection techniques，the code mapping method is adopted to process sign type data. The dimension reduction of the mixed attribute expanded after code mappingwas realized by the principal components analysis (PCA). The feasibility of the method was verified with a simulation experiment.

Keywords: intrusion detection; outlier detection; 2k-distance; code mapping; principal component analysis

0 引 言

孤立點挖掘[1]是數(shù)據(jù)挖掘技術(shù)中一個重要的研究方向，其任務(wù)是從大量復(fù)雜的數(shù)據(jù)中挖掘出存在于小部分異常數(shù)據(jù)中的新穎的、與常規(guī)數(shù)據(jù)模式顯著不同的數(shù)據(jù)模式。在統(tǒng)計學(xué)上，孤立點挖掘與聚類分析雖然在一定程度上是相似的，但兩者還是有著本質(zhì)的區(qū)別:聚類的目的在于尋找性質(zhì)相同或相近的記錄，并歸為一個類，而孤立點挖掘的目的則是尋找那些與所有類別性質(zhì)都不一樣的記錄。孤立點挖掘的往往是夾雜在大量高維數(shù)據(jù)中的異常數(shù)據(jù)，這些異常數(shù)據(jù)產(chǎn)生的行為可能帶來較嚴重的后果，例如網(wǎng)絡(luò)入侵中異常數(shù)據(jù)產(chǎn)生的行為會使得網(wǎng)絡(luò)中的終端不能工作、且發(fā)生數(shù)據(jù)丟失和程序被改變等情況。

本文嘗試將孤立點挖掘算法應(yīng)用于入侵檢測[2-3]中，將基于2k-距離的孤立點挖掘算法應(yīng)用到入侵檢測中。采用KDD99數(shù)據(jù)集[4]作為實驗數(shù)據(jù)來分析該方案的可行性和檢測性能。由于現(xiàn)有的孤立點挖掘方法大多是針對數(shù)值屬性的，而在入侵檢測中，數(shù)據(jù)包含著數(shù)字屬性和符號屬性，因此本文在數(shù)據(jù)預(yù)處理上采用對符號型屬性進行編碼映射與主成分分析相結(jié)合的方法，從而較好地解決了孤立點挖掘處理混合型的屬性問題。

1 基于2k-距離的孤立點算法[5]

基于2k-距離的孤立點算法主要思想:首先計算數(shù)據(jù)集中每個對象p與所有其他對象之間的距離，選出離它最近k對象的距離，再從中選出最大的距離作為該點的k-距離，然后找出對象p的所有k距離鄰居和所有2k距離鄰居。下一步計算兩個鄰居范圍內(nèi)的數(shù)據(jù)對象個數(shù)之比的反比值DKC，最后，選出n個具有最大DKC值的對象作為孤立點。

定義1 對象p的k-距離，記做k-distance(p)

對于任何一個正數(shù)k，對象p的k-距離，即k-distance(p)，被定義為d(p，o)。d(p，o)指的是p 與o 之間的歐氏距離，在對象p 與對象o 之間必須滿足下面的條件。

(1) 至少有k個對象。o′∈D\\\\{p}，滿足d(p，o′) ≤d(p，o);

(2) 至多有k-1個對象。o′∈D\\\\{p}，滿足d(p，o′)

定義2 對象p的k-距離半徑鄰居，記作rkNB(p)

設(shè)數(shù)據(jù)集中的對象p，定義對象p的k-距離半徑鄰居為以p為圓心，以k-distance為半徑的圓內(nèi)所有數(shù)據(jù)對象，即:rkNB(p)=|q∈ DB|dist(p，q)≤k-distance，q≠pl

定義3 對象p的2k-距離半徑鄰居，記做r2kNB(p)

設(shè)數(shù)據(jù)集中的對象p，定義對象p的2k-距離半徑鄰居為以p為圓心，以2k-distance為半徑的圓內(nèi)所有數(shù)據(jù)對象，即:r2kNB(p)=|q∈DB|dist(p，q)≤2k-distance，q≠pl。

定義4 對象p的DKC值，記作DKC(p)

設(shè)數(shù)據(jù)集中的對象p，定義對象p的DKC值為兩個圓內(nèi)數(shù)據(jù)對象個數(shù)之比的反比值，即:

DKC(p)=r2kNB(p)rkNB(p)

DKC值表明了這樣一個事實:高的DKC值說明對象p周圍是一個稀疏的區(qū)域，這個對象很可能是一個孤立點;低的DKC值說明該對象周圍是一個密集的區(qū)域，它不可能是孤立點。

2 基于孤立點挖掘的入侵檢測算法

2.1 設(shè)計方案

基于2k-距離算法的形式化描述如下:

Inputs: Data objects，int k n

Outputs: outlier

(1) Compute all distances from p and select the first k-minninum distance from p

(2) select the max of the k-mininum distance as k-distance(p)

(3) Find k-distance neighborhoods of each object p

(4) Find 2k-distance neighborhoods of each object p

(5) Compute tdk of p tdk(p)=r2kNB(p)rkNB(p)

(6) select the top n with max tdk(p) as outlier

基于孤立點挖掘的入侵檢測算法的步驟如下:

(1) 計算數(shù)據(jù)集中所有對象到對象p的距離，并選出其中最小的k個距離。

(2) 計算對象p的k-距離。

(3) 計算對象p的k-距離半徑內(nèi)的鄰居數(shù)目。

(4) 計算對象p的2k-距離半徑內(nèi)的鄰居數(shù)目。

(5) 計算對象p的DKC值。

(6) 計算出前n個最大DKC值的對象作為孤立點。

2.2 數(shù)據(jù)預(yù)處理

本文采用的數(shù)據(jù)集來自于KDD Cup 1999，該數(shù)據(jù)集包含了4大類入侵類型，即Probe，R2L，U2R和DoS。在分析過程中，從KDD99數(shù)據(jù)集中選取5個子數(shù)據(jù)集，每個包含10 000個正常記錄和200個入侵記錄，其中前4個子集中各含一類攻擊，第5個子集中的入侵為混合型。這樣處理的目的是:一方面可以檢測孤立點挖掘?qū)Σ煌愋偷娜肭值臋z測效果;另一方面，由于每個數(shù)據(jù)子集中，入侵的數(shù)量遠遠小于正常的連接記錄數(shù)量，從而使得實驗?zāi)茌^為真實地反映網(wǎng)絡(luò)行為中正常和異常行為的統(tǒng)計分布。

2.2.1 特征選取

KDD 數(shù)據(jù)集中不是每個屬性都對檢測結(jié)果有貢獻，Srinivas Mukkamala等人利用支持向量機方法，并通過實驗指出在KDD Cup 1999數(shù)據(jù)集中有13個屬性最為重要，這13個屬性是duration，srcbytes，dstbytes，urgent，count，srvcount，samesrvrate，dsthostcount，dsthostsrvcount，dsthostsamesrvrate，dsthostsamesrcportrate，protocoltype和service，其中既包含了數(shù)值型屬性，也包含了符號型屬性。這里也采用該特征選取方案。

2.2.2 混合型屬性處理方案

在進行相似度計算之前需要對數(shù)據(jù)的屬性值進行標準化[1]，因為屬性值之間采用不同的度量單位，其差別可能很大，因而對數(shù)據(jù)間距離的影響也不同，為了消除這種差別，必須采用一些規(guī)范化的方法。

(1) 標準化。令:

xy′ij=xij-xjsj， (i=1，2，…，n;j=1，2，…，n)

式中:xj=1n∑ni=1xij，sj=1n-1∑ni=1(xij-xj)2，xj和sj分別是U的第j維一個特征屬性的均值和標準偏差。經(jīng)過標準化變換后，各特征屬性的均值為0，方差為1，但是xy′ij的取值范圍很可能不在[0，1]區(qū)間，通過下面的正規(guī)化變換就可以把各個特征屬性的取值范圍落在[0，1]這個區(qū)間。

(2) 正規(guī)化。正規(guī)化變換的公式如下:

x′ij=xij-min1≤i≤n(xij)max1≤i≤n(xij)-min1≤i≤n(xij)，

i=1，2，…，n;j=1，2，…，n

式中:分母相是數(shù)據(jù)矩陣第j列數(shù)據(jù)的極差，經(jīng)過變換后，各變量的最小值為0，極差均為1，并且各特征屬性的基點相同，變化范圍也相等。

KDD數(shù)據(jù)集中不僅有數(shù)值型屬性，還有符號型屬性，對符號型屬性處理的方法是對其進行編碼映射，其做法如下:對于有m種不同取值的符號屬性，用m比特對其進行編碼，當(dāng)且僅當(dāng)屬性取值為第i種值時，其碼字中的第i比特為1，其余比特為0。例如，對屬性protocoltype，有icmp，tcp，udp這3種取值，對每個取值可以做如表1所示編碼。

表1 對符號屬性的編碼映射

碼字100010001

ProtocoltypeIcmpTcpUdp

編碼映射實際上是將原始的具有多種取值的符號類型屬性轉(zhuǎn)換為多個具有布爾取值的新屬性。與直接數(shù)值映射法相比，編碼映射保留了符號類型屬性不同取值之間的本質(zhì)特征，不會對學(xué)習(xí)算法造成誤導(dǎo)。但對于取值可能很多的符號類型特征來說，要完成編碼需要的比特位數(shù)也會很長。比如對于Service屬性來說，其可能取值達六七十種。對如此多的可能取值做編碼會帶來輸入矢量過大的問題。因此，本文在編碼映射基礎(chǔ)上引入了主成分分析(PCA)來達到降維[7]。經(jīng)過PCA變換后，通常取2～3個主成分已經(jīng)足夠包含或者代表原有數(shù)據(jù)集的全部信息，因此可以利用足夠代表原有數(shù)據(jù)全部信息的主成分來對原數(shù)據(jù)進行縮減。通過PCA分析，找出在權(quán)值上發(fā)生較大變化的變量項，保留這些屬性作為PCA處理后新生成數(shù)據(jù)集的主干屬性，從而得到一個全新的數(shù)據(jù)集，新生成的數(shù)據(jù)集較原先數(shù)據(jù)集在維度上大大降低，并能代表原先數(shù)據(jù)集的全部信息。

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

在實驗中選取2.2.1節(jié)中的13個主要屬性，對11個數(shù)值型屬性進行標準化，并對符號型屬性service和protocoltype進行編碼映射后，再對其進行主成分分析，以得到一個新的數(shù)據(jù)集，最后使用基于相似度的孤立點挖掘算法對這個新數(shù)據(jù)集進行異常檢測的結(jié)果如表2所示。

表2 基于2k-距離的孤立點挖掘?qū)嶒灲Y(jié)果

n

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

檢測率誤檢率檢測率誤檢率檢測率誤檢率檢測率誤檢率正常記錄異常記錄

18100%3.57%54.1%4.20%38.1%5.52%100%4.18%10 000200

19100%2.14%54.1%2.46%28.6%4.49%100%2.34%10 000200

20100%1.02%50%1.23%19.1%3.58%100%1.63%10 000200

210037.5%0.20%14.3%2.04%95%010 000200

220037.5%04.76%1.43%0010 000200

從實驗結(jié)果可以看出，在n=20時，對四類攻擊的檢測率與誤檢率達到最好。當(dāng)取n=20時，對第5個數(shù)據(jù)樣本中混合攻擊的檢測率與誤檢率分別為90%和1.63%。此外，對于第5個混合攻擊類型數(shù)據(jù)樣本使用k-Means聚類方法進行異常檢測實驗，其中符號型屬性同樣采用本文的方法處理，通過聚類分析后得到的檢測率與誤檢率分別為85.03%和3.01%。通過對比可知，在異常檢測上，2k-距離比k-Means無論是在檢測率，還是在誤檢率上效果都更好。

從上面給出的實驗結(jié)果可以看出，孤立點挖掘技術(shù)對DoS和Probe入侵攻擊的檢測都取得了很高的檢測率，但是對R2L和U2R入侵的檢測效果不理想。這與估計的基本一致。經(jīng)過分析主要有兩個原因:

(1) R2L，U2R攻擊，不像DoS和Probe那樣在短時間內(nèi)對一些主機發(fā)出很多連接，相反R2L和U2R攻擊嵌入到包中，正常情況下只存在于一個連接中，故無法對其進行足夠的特征刻畫，需要尋找其他更有效的刻畫特征;

(2) Probe類和DoS類攻擊種類相對來說比較固定，而R2L，U2R類攻擊種類比較多，且有很多U2R入侵是偽裝合法用戶身份進行攻擊的，這就使得其特征與正常數(shù)據(jù)包比較類似，造成了算法檢測的困難。而在KDD99的競賽中，冠軍方法對于這兩種類型的入侵連接數(shù)據(jù)的檢測率為13.2%和8.4%，這證明本文的方法是有其優(yōu)越性的。

4 結(jié) 語

分析了基于孤立點挖掘的異常檢測的可行性，將基于2k-距離的孤立點挖掘方法應(yīng)用到入侵檢測中，給出了該檢測方法的流程和混合型屬性的數(shù)據(jù)預(yù)處理方案，并通過在KDD99實驗數(shù)據(jù)集進行孤立點挖掘仿真實驗，證明該方法能夠取得較高的檢測率與較低的誤檢率，尤其是對DoS和Probe入侵攻擊的檢測都取得了令人滿意的檢測結(jié)果。

實驗結(jié)果表明，孤立點挖掘技術(shù)可以用來完成異常檢測工作，而且當(dāng)異常數(shù)據(jù)要遠小于正常數(shù)據(jù)時，其檢測結(jié)果要優(yōu)于基于聚類的異常檢測技術(shù)，而在一般情況下，網(wǎng)絡(luò)數(shù)據(jù)中異常和正常行為的統(tǒng)計分布基本符合孤立點挖掘的使用條件。當(dāng)然，目前基于孤立點挖掘的異常檢測技術(shù)還不能象諸如基于神經(jīng)網(wǎng)絡(luò)的異常檢測技術(shù)那樣完成實時在線檢測，但這并不妨礙該技術(shù)在異常檢測中的應(yīng)用，比如做離線安全分析。如何進一步提高基于孤立點挖掘的異常檢測性能指標，以及如何將基于孤立點挖掘應(yīng)用到實際入侵檢測中去將是下一步的主要研究方向。

參考文獻

[1]HAN J， KAMBER M. Data mining: concepts and techniques[M]. San Fransisco: Morgan Kaufmann Publishers， 2000.

[2]羅敏，王麗娜.基于無監(jiān)督聚類的入侵檢測方法[J].電子學(xué)報，2003，31(11):1712-1716.

[3]PORTNOY L， ESKIN E， STOLFO S. Intrusion detection with unlabeled data using clustering\\//ACM. Proceedings of ACM CSS Workshop on Data Mining Applied to Security (DMSA-2001). Philadelphia:ACM CSS， 2001: 156-166.

[4]BRUGGER Terry. KDD99 Cup dataset[DB/OL].\\. Http://kdd.ics.uci.edu/ databases/kd- dcup99/kddcup99.html.1999 .

[5]姜靈敏.基于相似系數(shù)和檢測孤立點的聚類算法[J].計算機工程，2003(7):183-185.

[6]MUKKAMALA S， JANOSKI G， SUNG AH. Intrusion detection using support vector machines and neural networks\\. Proc. of the IEEE Int′l Joint Conf. on Neural Networks，2002:1702-1707.

[7]DUDA R O， HART P E， STORK D G. Pattern classification\\. 2nd edition， Beijing: China Machine Press， 2004.