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

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

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

0 引言

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

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

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

1 仿射傳播聚類

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

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

構(gòu)造相似度矩陣為:

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

為了找到合適的聚類中心需要從樣本中收集相關(guān)信息，包括吸引度(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)直到滿足迭代終止條件，輸出聚類結(jié)果。R(i，k)與 A(i，k)的迭代計算公式為:

信息更新公式為:

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

AP算法主要步驟如下 :

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

步驟2 迭代過程:

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

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

③檢查是否滿足迭代終止條件:是否達到最大迭代次數(shù)，或聚類中心經(jīng)過一次循環(huán)后不再變化。否則轉(zhuǎn)至①。

步驟3 判斷得到的聚類中心個數(shù)是否滿足要求，否則調(diào)整p值，重復(fù)迭代過程直至滿足要求，輸出聚類結(jié)果。

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

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

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

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

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

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

3 實驗結(jié)果

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

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

采用檢測率(Detection Rate，DR)和誤檢率(False Positive Rate，F(xiàn)PR)兩個指標來評價入侵檢測方法的檢測性能。檢測率DR表示被正確檢測的入侵記錄數(shù)占總?cè)肭钟涗洈?shù)的比例，誤檢率FPR表示正常記錄被檢測為入侵行為的總數(shù)占正常記錄總數(shù)的比例。

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

對原始數(shù)據(jù)進行標準化處理的步驟如下:

①計算平均絕對偏差S:

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

②計算標準化的數(shù)據(jù):

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

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

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

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

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

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

4 結(jié)束語

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

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

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

［3］肖立中，邵志清，馬漢華，等.網(wǎng)絡(luò)入侵檢測中的自動決定聚類數(shù)算法［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算法在網(wǎng)絡(luò)異常檢測中的應(yīng)用［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］李文華.基于聚類分析的網(wǎng)絡(luò)入侵檢測模型［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］肖 宇，于 劍.基于近鄰傳播算法的半監(jiān)督聚類［J］.軟件學報，2008，19(11):2803 －2813.

［10］羅 敏，王麗娜，張煥國.基于無監(jiān)督聚類的入侵檢測方法［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.