一種基于孤立點挖掘的入侵檢測技術

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

關鍵詞: 入侵檢測; 孤立點; 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]是數據挖掘技術中一個重要的研究方向，其任務是從大量復雜的數據中挖掘出存在于小部分異常數據中的新穎的、與常規數據模式顯著不同的數據模式。在統計學上，孤立點挖掘與聚類分析雖然在一定程度上是相似的，但兩者還是有著本質的區別:聚類的目的在于尋找性質相同或相近的記錄，并歸為一個類，而孤立點挖掘的目的則是尋找那些與所有類別性質都不一樣的記錄。孤立點挖掘的往往是夾雜在大量高維數據中的異常數據，這些異常數據產生的行為可能帶來較嚴重的后果，例如網絡入侵中異常數據產生的行為會使得網絡中的終端不能工作、且發生數據丟失和程序被改變等情況。

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

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

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

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

對于任何一個正數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)

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

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

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

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

設數據集中的對象p，定義對象p的DKC值為兩個圓內數據對象個數之比的反比值，即:

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

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

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

2.1 設計方案

基于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) 計算數據集中所有對象到對象p的距離，并選出其中最小的k個距離。

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

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

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

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

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

2.2 數據預處理

本文采用的數據集來自于KDD Cup 1999，該數據集包含了4大類入侵類型，即Probe，R2L，U2R和DoS。在分析過程中，從KDD99數據集中選取5個子數據集，每個包含10 000個正常記錄和200個入侵記錄，其中前4個子集中各含一類攻擊，第5個子集中的入侵為混合型。這樣處理的目的是:一方面可以檢測孤立點挖掘對不同類型的入侵的檢測效果;另一方面，由于每個數據子集中，入侵的數量遠遠小于正常的連接記錄數量，從而使得實驗能較為真實地反映網絡行為中正常和異常行為的統計分布。

2.2.1 特征選取

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

2.2.2 混合型屬性處理方案

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

(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維一個特征屬性的均值和標準偏差。經過標準化變換后，各特征屬性的均值為0，方差為1，但是xy′ij的取值范圍很可能不在[0，1]區間，通過下面的正規化變換就可以把各個特征屬性的取值范圍落在[0，1]這個區間。

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

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

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

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

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

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

碼字100010001

ProtocoltypeIcmpTcpUdp

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

3 實驗結果與分析

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

表2 基于2k-距離的孤立點挖掘實驗結果

n

DoSR2LU2RProbe數據集

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

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

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

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

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

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

4 結 語

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

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

參考文獻

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

[2]羅敏，王麗娜.基于無監督聚類的入侵檢測方法[J].電子學報，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]姜靈敏.基于相似系數和檢測孤立點的聚類算法[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.