一種基于仿射傳播聚類的入侵檢測方法

程夢駒，趙 龍，陶洪波，趙成林

(北京郵電大學信息與通信工程學院，北京 100876)

0 引言

隨著計算機網絡的普及，網絡入侵所帶來的危害越來越嚴重。入侵檢測系統是一種主動的安全防護系統，通過監視網絡流量或主機狀態來發現入侵行為并做出響應［1］。入侵檢測技術主要分為誤用檢測(Misuse Detection)和異常檢測(Anomaly Detection)［2］。誤用檢測是指利用已知系統和網絡的弱點攻擊模式來檢測入侵，它對已知的入侵行為有很好的檢測效果，而對新的入侵模式無效;異常檢測是指利用定量的方式來描述可接受的網絡行為，通過分析用戶行為與正常行為的偏差來判斷是否為入侵行為，它能夠檢測新的入侵模式，但是存在誤檢率較高的問題［3］。

基于異常檢測的入侵檢測系統需要處理大量的網絡審計數據，而隨著數據挖掘技術的發展，數據挖掘中的聚類方法因其能高效處理海量數據的優勢而得到廣泛應用。由此建立的入侵檢測系統依賴于對訓練集中數據樣本的學習，所以保證該數據集的潔凈性對建立一個有效的入侵檢測系統極其重要［4］。但實際上，要為系統的訓練收集一個潔凈的數據集代價較高，因此無監督的聚類方法成為首選［5］。

在以往的入侵檢測中采用的無監督聚類方法大多需要預先設置初始聚類中心和數目，如K均值(k-means)和模糊C 均值(Fuzzy c-means，FCM)等聚類算法［3，6］，如果初始聚類中心選擇不當，容易陷入局部極值，得不到準確的聚類結果，導致檢測率低和誤檢率高［7］。下面采用能夠自動決定聚類中心和數目的仿射傳播聚類算法對訓練集進行聚類分析，可以得到準確的聚類結果。通過對KDD CUP99數據集的仿真實驗來測試該方法的檢測性能，并與傳統方法的檢測性能進行比較。

1 仿射傳播聚類

仿射傳播(Affinity Propagation，AP)聚類［8］是由Frey等人提出的一種快速有效的新型聚類算法。AP算法與其他聚類算法最大的不同之處在于它能夠自動決定聚類中心和數目。AP算法將每個樣本點都看作潛在的聚類中心，通過樣本之間傳遞實時信息迭代競爭成為聚類中心。

首先根據訓練數據構造樣本之間的相似度矩陣作為算法的輸入，一般使用歐氏距離作為樣本間相似度的計算方法［6］，樣本間距離越小則相似度越大。假設訓練數據集為 X={x1，x2，…，xN}，共有N個樣本點，每個樣本點有m個屬性，則任意2個樣本點i和k之間的相似度為:

構造相似度矩陣為:

式中，p為偏向參數，表示各樣本點成為聚類中心的可能性大小，一般取相同值。p值的大小在迭代中表現為競爭的激烈程度［6］，最終會影響聚類中心的數目。如果p越大，則競爭越激烈，各樣本點成為聚類中心的可能性也越大，最后聚類中心的數目越多。

為了找到合適的聚類中心需要從樣本中收集相關信息，包括吸引度(Responsibility)和歸屬度(Availability)［6］，分別用 R(i，k)和 A(i，k)表示。R(i，k)反映樣本點k對樣本點i的吸引程度，即樣本點k作為樣本點i的聚類中心的適合程度;A(i，k)反映樣本點i選擇樣本點k為聚類中心的適合程度。若R(i，k)與 A(i，k)之和越大，則樣本點 k成為聚類中心的可能性越大。在算法迭代過程中，不斷更新所有樣本點的R(i，k)和A(i，k)直到滿足迭代終止條件，輸出聚類結果。R(i，k)與 A(i，k)的迭代計算公式為:

信息更新公式為:

式中，λ為阻尼系數，取值范圍為(0，1)，其值越大迭代越慢，但聚類精度越高。為避免發生振蕩［5］，λ一般設置為0.9。

AP算法主要步驟如下 :

步驟1 初始化:根據式(1)和式(2)計算相似度矩陣 S，設置參數 p和 λ，p取 S的中值median(S)，初始化 R0(i，k)=A0(i，k)=0。

步驟2 迭代過程:

① 根據式(3)、式(4)和式(7)更新 R(i，k)，根據式(5)、式(6)和式(8)更新 A(i，k);

②尋找聚類中心:對于樣本點i，若樣本點k使得 R(i，k)+A(i，k)最大，則樣本點 k 即樣本點 i的聚類中心;

③檢查是否滿足迭代終止條件:是否達到最大迭代次數，或聚類中心經過一次循環后不再變化。否則轉至①。

步驟3 判斷得到的聚類中心個數是否滿足要求，否則調整p值，重復迭代過程直至滿足要求，輸出聚類結果。

2 一種基于仿射傳播聚類的入侵檢測方法

在實際的網絡環境中，正常的網絡行為在數量上遠遠大于異常行為(包括入侵行為和用戶誤操作)。基于無監督聚類的異常檢測通常是基于以下2個事實［10］:一是正常的網絡行為在數量上遠大于網絡入侵行為;二是入侵行為在某些特征屬性上與正常的網絡行為具有不同之處。由于入侵行為模式不同于正常行為，而且數量上占總的網絡連接數的比例較小，因此在大量的網絡連接數據中表現異常并可被檢測出來。

入侵檢測模型具體包含以下幾個部分［11］:數據收集模塊、數據預處理模塊、聚類分析模塊、標類模塊和檢測模塊，如圖1所示。

圖1 基于異常檢測的入侵檢測模型

在實際應用中收集的網絡數據可能包含非數值型的特征屬性，且不同的特征屬性有不同的度量標準，如果不同特征取值的數量級相差較大則會造成大數量特征掩蓋小數量特征，影響聚類的準確性。因此需要對原始數據進行預處理，包括非數值型特征的數值化和特征值的標準化處理。

對訓練數據的聚類結果中，入侵行為類中的樣本數要小于正常行為類中的樣本數，將樣本數小于閾值α的類標記為入侵，樣本數大于閾值α的類標記為正常。在完成標記后，利用標記結果對新樣本進行檢測，在不斷完善和更新聚類結果的同時檢測入侵行為。計算新樣本到各聚類的歐氏距離，選擇距離最近的聚類，根據其標記結果判定該樣本是正常行為還是入侵行為。

3 實驗結果

為了測試提出的基于仿射傳播聚類的入侵檢測方法的檢測效果，使用目前在入侵檢測研究領域廣泛使用的KDD CUP99數據集進行仿真實驗。

數據集來源于MIT林肯實驗室1998DARPA入侵檢測評估數據集，共包含490多萬條網絡連接數據，每一條連接數據包含41個特征，其中7個離散型特征，34個連續型特征。數據集中的入侵數據共分為 4大類:DOS攻擊、U2R攻擊、R2L攻擊和PROBE攻擊，細分為39小類。

采用檢測率(Detection Rate，DR)和誤檢率(False Positive Rate，FPR)兩個指標來評價入侵檢測方法的檢測性能。檢測率DR表示被正確檢測的入侵記錄數占總入侵記錄數的比例，誤檢率FPR表示正常記錄被檢測為入侵行為的總數占正常記錄總數的比例。

首先按比例θ從KDDCUP9910%數據集中隨機選取入侵數據和正常數據混合組成訓練集和測試集進行實驗。在實際網絡環境中，入侵行為數占總的網絡連接數的比例約為1%左右［12］，所以實驗中θ取1%。

對原始數據進行標準化處理的步驟如下:

①計算平均絕對偏差S:

式中，Sf為數據集X第f個特征屬性的平均絕對誤差;xif為數據xi的第f個屬性值;mf為數據集 X的第f個屬性的均值。

②計算標準化的數據:

式中，Yif即數據xi標準化后的第f個屬性值。

在檢測過程中，存在2個影響檢測結果的參數:AP聚類算法的偏向參數p和標記閾值α。偏向參數p影響聚類的數目，若聚類分析模塊輸出聚類數目過多，則訓練樣本中的正常記錄分布比較分散，可能導致標記錯誤，使誤檢率上升，因此須控制聚類數目在較小水平。標記閾值α影響標記結果，若α值偏大，則越多的類被標記為異常，能夠提高檢測率，但是可能有較小的正常類被錯誤標記而造成誤檢率上升;相反若α值偏小，則能降低誤檢率，但是檢測率也會下降。

從實驗結果表 1和表 2可以看出，當 p=0.5median(S)時算法具有較好的檢測效果。取p=0.5median(S)時的實驗結果與其他檢測方法進行對比，這里選取了k-means算法、Y-means算法、一類SVM算法和一種改進的k-means算法［12］與本文使用的方法進行對比，檢測率DR和誤檢率FPR的ROC曲線如圖2所示。由對比結果可以看出，當FPR小于2%時，基于AP的方法具有較好的檢測效果，當FPR大于2%時，基于AP的方法能夠有效提高檢測率。

表1 p和α取不同值時的檢測率DR (%)

表2 p和α取不同值時的誤檢率FPR (%)

圖2 不同算法的ROC曲線對比

4 結束語

研究了一種基于無監督聚類的入侵檢測方法，采用能夠自動決定聚類中心和數目的AP算法，不需要進行人工設置初始聚類中心和數目，避免了可能因初始聚類中心選擇不當而造成檢測率低下的問題。對KDD CUP99數據集的仿真實驗結果表明，該方法有良好的檢測性能，與其他方法相比能夠有效提高檢測率。 ■

［1］田俊峰，張 喆，趙衛東.基于誤用和異常技術相結合的入侵檢測系統的設計與研究［J］.電子與信息學報，2006，28(11):2162 －2166.

［2］程玉青，梅登華，陳龍飛.基于數據挖掘的入侵檢測系統模型［J］.計算機技術與發展，2009，19(12):123 －126.

［3］肖立中，邵志清，馬漢華，等.網絡入侵檢測中的自動決定聚類數算法［J］.軟件學報，2008，19(8):2140－2148.

［4］ESKIN E，ARNOLD A，PRERAU M，et al.A Geometric Framework for Unsupervised Anomaly Detection:Detecting Intrusions in Unlabeled Data［C］∥Applications of Data Mining in Computer Security.Boston:Kluwer Academic Publisher，2002:77 －101.

［5］劉 濤，馬曉宇，胡 景.一種 K-MEANS算法在網絡異常檢測中的應用［J］.微電子學與計算機，2012，29(5):42－45.

［6］ZHANG H，SONG K.Research and Experiment on Affinity Propagation Clustering Algorithm［C］∥Hohhot:2011 Second International Conference on Mechanic Automation and Control Engineering(MACE)，2011:5996 －5999.

［7］李文華.基于聚類分析的網絡入侵檢測模型［J］.Computer Engineering，2011，37(17):96 －98.

［8］FREY B J，DUECK D.Clustering by Passing Messages between Data Points［J］.Science，2007，315(5814):972－976.

［9］肖 宇，于 劍.基于近鄰傳播算法的半監督聚類［J］.軟件學報，2008，19(11):2803 －2813.

［10］羅 敏，王麗娜，張煥國.基于無監督聚類的入侵檢測方法［J］.電子學報，2003，31(11):1713 －1716.

［11］WANG S.Research of Intrusion Detection Based on an Improved K-means Algorithm［C］∥Shenzhen:2011 Second International Conference on Innovations in Bio-inspired Computing and Applications(IBICA)，2011:274－276.

［12］ZHONG Y，YAMAKI H，TAKAKURA H.A Grid-based Clustering for Low-overhead Anomaly Intrusion Detection［C］∥Milan:20115th International Conference on Network and System Security(NSS)，2011:17－24.