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

程夢(mèng)駒，趙 龍，陶洪波，趙成林

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

0 引言

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

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

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

1 仿射傳播聚類

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

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

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

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

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

信息更新公式為:

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

AP算法主要步驟如下 :

步驟1 初始化:根據(jù)式(1)和式(2)計(jì)算相似度矩陣 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);

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

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

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

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

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

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

圖1 基于異常檢測(cè)的入侵檢測(cè)模型

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

對(duì)原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理的步驟如下:

①計(jì)算平均絕對(duì)偏差S:

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

②計(jì)算標(biāo)準(zhǔn)化的數(shù)據(jù):

式中，Yif即數(shù)據(jù)xi標(biāo)準(zhǔn)化后的第f個(gè)屬性值。

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

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

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

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

圖2 不同算法的ROC曲線對(duì)比

4 結(jié)束語

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

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

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

［3］肖立中，邵志清，馬漢華，等.網(wǎng)絡(luò)入侵檢測(cè)中的自動(dòng)決定聚類數(shù)算法［J］.軟件學(xué)報(bào)，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ò)異常檢測(cè)中的應(yīng)用［J］.微電子學(xué)與計(jì)算機(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ò)入侵檢測(cè)模型［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］.軟件學(xué)報(bào)，2008，19(11):2803 －2813.

［10］羅 敏，王麗娜，張煥國.基于無監(jiān)督聚類的入侵檢測(cè)方法［J］.電子學(xué)報(bào)，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.