張 珍,萬(wàn)世昌

摘 要:為了進(jìn)一步提高網(wǎng)絡(luò)入侵檢測(cè)技術(shù)的檢測(cè)率,降低誤報(bào)率和漏報(bào)率。針對(duì)普通聚類算法存在的聚類結(jié)果對(duì)隨機(jī)選取初始聚類中心敏感、分類結(jié)果不穩(wěn)定,從而造成的檢測(cè)率低、漏報(bào)和誤報(bào)率高的特點(diǎn)。提出一種基于動(dòng)態(tài)聚類算法的網(wǎng)絡(luò)入侵檢測(cè)模型,實(shí)驗(yàn)結(jié)果表明通過(guò)在K-均值聚類算法的基礎(chǔ)上增加動(dòng)態(tài)迭代調(diào)整聚類中心,使聚類結(jié)果更穩(wěn)定更準(zhǔn)確。與K-均值聚類等算法相比提高了網(wǎng)絡(luò)入侵檢測(cè)的性能,從而表明該算法的可行性、有效性。

關(guān)鍵詞:聚類;聚類中心;距離;迭代;入侵檢測(cè)

中圖分類號(hào):TP393文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)20-085-03

Application of Dynamic Clustering Algorithm in Network Intrusion Detection

ZHANG Zhen,WANG Shichang

(School of Computer Science,Shaanxi Normal University,Xi′an,710062,China)

Abstract:In order to improve the detection rate,lower false alarm rate and missing rate,further.A network intrusion detection model that combines a dynamic clustering algorithm and intrusion detection technology is proposed.The general clustering algorithm is sensitive of the initial cluster center using,and it can make the classification results of instability,resulting in the detection rate is low,and failing to report the characteristics of a high false alarm rate.A model of network intrusion detection based on dynamic clustering algorithm is introduced.Experimental results show that the dynamic clustering results are more stable and more accurate by adding dynamic iteration to adjust the basis of cluster center.To a certain extent,the performance of network intrusion detection is improved,the feasibility and effectiveness of the algorithm are demonstrated.

Keywords:clustering;cluster center;distance;iterative;intrusion detection

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展,網(wǎng)絡(luò)規(guī)模隨之不斷擴(kuò)大,計(jì)算機(jī)已從獨(dú)立的主機(jī)發(fā)展到互聯(lián)的、開(kāi)放式的系統(tǒng),這為人們的信息交流和資源共享帶來(lái)了極大的便利,但同時(shí)網(wǎng)絡(luò)環(huán)境也變得越來(lái)越復(fù)雜[1]。隨著Internet大范圍的開(kāi)放以及金融領(lǐng)域的接入,越來(lái)越多的系統(tǒng)遭到入侵攻擊的威脅,網(wǎng)絡(luò)安全也面臨越來(lái)越嚴(yán)重的威脅,這些威脅大多是通過(guò)挖掘操作系統(tǒng)和應(yīng)用服務(wù)程序的弱點(diǎn)來(lái)實(shí)現(xiàn)的。

過(guò)去,防范網(wǎng)絡(luò)安全攻擊最常用的方法是使用防火墻,但防火墻技術(shù)有它自身的局限性[2]。防火墻本身會(huì)有各種漏洞和后門、不能阻止內(nèi)部攻擊、一般不能提供實(shí)時(shí)的入侵檢測(cè)等,在這種情況下,單純以防火墻技術(shù)來(lái)防范網(wǎng)絡(luò)攻擊已暴露出明顯的不足和局限。

入侵檢測(cè)系統(tǒng)[3,4]是在防火墻和信息加密等網(wǎng)絡(luò)安全保障技術(shù)之后發(fā)展起來(lái)的新一代網(wǎng)絡(luò)安全防護(hù)系統(tǒng)。它是一種能夠動(dòng)態(tài)監(jiān)控和防御計(jì)算機(jī)和網(wǎng)絡(luò)系統(tǒng)入侵行為的安全機(jī)制,是對(duì)企圖入侵、正在進(jìn)行的入侵或已經(jīng)發(fā)生的入侵的識(shí)別過(guò)程。它主要通過(guò)監(jiān)控網(wǎng)絡(luò)和系統(tǒng)的狀態(tài)和使用情況,檢測(cè)系統(tǒng)用戶的越權(quán)使用和系統(tǒng)外部的入侵者對(duì)系統(tǒng)的非法入侵。

隨著近幾年入侵檢測(cè)技術(shù)的不斷發(fā)展,入侵檢測(cè)的技術(shù)也不斷的成熟和完善,出現(xiàn)了一系列的入侵檢測(cè)方法,如基于數(shù)據(jù)挖掘技術(shù)的;基于數(shù)據(jù)融合技術(shù)的等網(wǎng)絡(luò)入侵檢測(cè)方法。但入侵檢測(cè)的性能還有待進(jìn)一步提高,很多學(xué)者也提出了改進(jìn)的辦法[4-7],如基本免疫模型的入侵檢測(cè)技術(shù)、基于支持向量基的入侵檢測(cè)技術(shù)等。

在此針對(duì)傳統(tǒng)的基于K-均值聚類算法[8]的入侵檢測(cè)技術(shù)存在對(duì)初始聚類中心敏感,分類結(jié)果不穩(wěn)定等特點(diǎn)提出了一種動(dòng)態(tài)聚類算法。

1 聚類算法

聚類法[9]是模式識(shí)別中一種常用的方法,它是利用某種相似性度量,把一個(gè)未知類別的樣本劃分為若干有意義的子集,要求相似度高的樣本盡量歸為一類,而不相似的或相似度較小的樣本盡量不在同一類中,把聚類法應(yīng)用于網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)中,可以將網(wǎng)絡(luò)流量樣本集中的正常流量和異常流量區(qū)分開(kāi)來(lái)。

1.1 聚類的基本要素

(1) 定義數(shù)據(jù)之間的相似度;

(2) 聚類有效性函數(shù)(停止判別條件);

① 在聚類算法的不同階段會(huì)得到不同的類別劃分結(jié)果,可以通過(guò)聚類有效性函數(shù)來(lái)判斷多個(gè)劃分結(jié)果中哪個(gè)是有效的;

② 使用有效性函數(shù)作為算法停止的判別條件,當(dāng)類別劃分結(jié)果達(dá)到聚類有效性函數(shù)時(shí)即可停止算法運(yùn)行;

(3) 類別劃分策略(算法);

通過(guò)何種類別劃分方式使類別劃分結(jié)果達(dá)到有效性函數(shù)。

1.2 聚類有效性函數(shù)

(1)最小誤差(Jj)[9-11]

C個(gè)類別,待聚類數(shù)據(jù)x,zj為類別Ci的中心:

zj=∑x∈Cix/Ci,Jj=∑x∈wj(k)‖x-zj‖2

式中:Jj越小聚類結(jié)果越好。Jj衡量屬于不同類別的數(shù)據(jù)與類別中心的誤差和。

(2) 最小方差(Si)

Si=1n2∑x∈Ci ∑x′∈Ci‖x-x′‖2

Si衡量同一類別內(nèi)數(shù)據(jù)的平均誤差和。

2 動(dòng)態(tài)聚類算法

K-均值的聚類算法具有聚類速度快的優(yōu)點(diǎn),但對(duì)初始參數(shù)敏感;容易陷入局部最優(yōu);為了解決上述問(wèn)題,本文采用動(dòng)態(tài)聚類算法對(duì)數(shù)據(jù)進(jìn)行聚類分析。

2.1 動(dòng)態(tài)聚類算法的特點(diǎn)

動(dòng)態(tài)聚類算法具有兩方面的特點(diǎn):

(1) 算法要求的類別數(shù)為C,即把已知的N個(gè)模式集[11]劃分為C類。這里C頝可以變動(dòng),劃分方法通常對(duì)模式矩陣或模式向量進(jìn)行運(yùn)算并產(chǎn)生一個(gè)單一劃分;這樣就減弱了對(duì)初始參數(shù)的敏感性。

(2) 算法允許模式樣本集從一個(gè)聚合類移到另一個(gè)聚合類,使初始的不準(zhǔn)確劃分逐步得到改進(jìn),大多數(shù)劃分方法是一些準(zhǔn)則函數(shù)取極值的劃分。這樣可以避免局面最優(yōu)化。

動(dòng)態(tài)聚類法爭(zhēng)取采用最優(yōu)的劃分,減少計(jì)算量。

2.2 動(dòng)態(tài)聚類算法的步驟

本文的動(dòng)態(tài)聚類劃分采用最常用的均方差準(zhǔn)則,動(dòng)態(tài)聚類法操作主要包括下面幾個(gè)步驟:

(1) 初始化聚類中心或建立第一次劃分;

(2) 修改聚合類成員,重新分配模式至聚合類內(nèi);

(3) 刪除和合并聚合類并認(rèn)定遠(yuǎn)離點(diǎn);

(4) 當(dāng)誤差小于一門限或迭代的數(shù)目超出預(yù)先設(shè)置的數(shù)時(shí)停止。

3 基于動(dòng)態(tài)聚類算法的入侵檢測(cè)

從上面介紹的動(dòng)態(tài)聚類算法的步驟可知,動(dòng)態(tài)聚類算法[10]需要兩個(gè)參數(shù),一個(gè)是聚類中心z和聚類數(shù)目C,聚類數(shù)目C要遠(yuǎn)小于聚類樣本總個(gè)數(shù)n,選擇樣本集中的C個(gè)作為基于動(dòng)態(tài)聚類算法的入侵檢測(cè)的聚類原型,然后分別求各樣本到聚類中心的距離,根據(jù)每次迭代求得的距離更新聚類原型模式直至聚類原型不在變動(dòng)。該算法的目標(biāo)是能使聚類域w中的所有樣本x到聚類中心的距離的平方和最小。即使Jj=∑x∈wj(k)‖x-zj‖2為最小且Si=1n2∑x∈Ci∑x′∈Ci‖x-x′‖2盡量小。

3.1 動(dòng)態(tài)聚類算法的步驟

算法具體步驟:

(1) 選C個(gè)初始聚類中心:z1(1),z2(1),…,zc(1), 這里括號(hào)內(nèi)的“1”標(biāo)明是第一次迭代。

(2) 計(jì)算所有樣本與聚類中心的距離‖x-zj(k)‖,j=1,2,…,C,并按最小距離原則進(jìn)行分類;即Dj(k)=min‖x-zj(k)‖,j=1,2,…,C,則x∈wj(k)。

(3) 重新計(jì)算各個(gè)類的新的聚類中心向量:zj(k+1)=1Nj∑x∈wj(k)x, (j=1,2,…,C),式Nj中為第j個(gè)聚類域wj中所包含的樣本個(gè)數(shù)。以均值向量作為新的聚類中心,可使聚類準(zhǔn)則函數(shù)Jj最小,有Jj=∑x∈wj(k)x-zj(k+1)2,j=1,2,…,C。

(4) 計(jì)算最小方差

Si=1n2∑x∈Ci∑x′∈Ci‖x-x′‖2

式中:Si衡量同一類別內(nèi)數(shù)據(jù)的平均誤差和;

(5) 若zj(k+1)≠zj(k),則轉(zhuǎn)至步驟(2);若zj(k+1)=zj(k)算法收斂。

3.2 動(dòng)態(tài)聚類算法目標(biāo)

這種聚類算法在實(shí)際中要試探不同的C值及選擇不同的聚類中心起始值,或者對(duì)C=1,2,…分別使用該算法,準(zhǔn)則函數(shù)JC將隨C值增大而單調(diào)的減小。通過(guò)迭代算法達(dá)到了較好的聚類效果。

該算法的目標(biāo)是根據(jù)每次迭代求得的距離更新聚類原型模式直至聚類原型不再變動(dòng)。即使聚類域w中的所有樣本x到聚類中心的距離的平方和最小且平方差盡量小。

4 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

為了證明本文算法的有效性,實(shí)驗(yàn)中采用了不同的檢測(cè)數(shù)據(jù)[12],包括正常數(shù)據(jù)、Probe攻擊數(shù)據(jù)、Dos攻擊數(shù)據(jù)、U2R攻擊數(shù)據(jù)、R2L攻擊數(shù)據(jù)等。實(shí)驗(yàn)環(huán)境采用操作系統(tǒng)Windows vistal,Intel Pentium CPU 24 GHz,內(nèi)存4 GB,程序執(zhí)行環(huán)境采用Matlab 7.0。

4.2 實(shí)驗(yàn)分析

將收集到的全部數(shù)據(jù)進(jìn)行實(shí)驗(yàn),經(jīng)過(guò)數(shù)據(jù)預(yù)處理得到訓(xùn)練數(shù)據(jù)8 760條,測(cè)試數(shù)據(jù)4 532條,進(jìn)行基于動(dòng)態(tài)聚類的入侵檢測(cè)算法的處理,通過(guò)多次測(cè)試,得到如表1所示的實(shí)驗(yàn)結(jié)果。

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

數(shù)目類型檢測(cè)率漏報(bào)率誤報(bào)率

正常數(shù)據(jù)73.263.2110.45

Probe攻擊62.175.4211.09

Dos攻擊58.984.058.11

U2R攻擊79.352.9812.53

R2L攻擊68.573.0910.78

從以上的數(shù)據(jù)統(tǒng)計(jì)可以看出,通過(guò)基于動(dòng)態(tài)聚類算法的檢測(cè)方法進(jìn)行網(wǎng)絡(luò)入侵檢測(cè),算法在檢測(cè)率和錯(cuò)檢率上得到了改進(jìn),滿足了系統(tǒng)的安全檢測(cè)需求。

但由于聚類中心多次迭代的原因,可能使檢測(cè)的時(shí)間增長(zhǎng),并且在實(shí)驗(yàn)結(jié)果中體現(xiàn)出某個(gè)類別的檢測(cè)率偏低而錯(cuò)檢率偏高。但是從其他攻擊方式的檢測(cè)率和錯(cuò)檢率來(lái)看,算法的效率和有效性還是得到了很大的改進(jìn)。

圖1 幾種入侵檢測(cè)方法的性能比較

為了進(jìn)一步檢驗(yàn)算法的有效性,同其他入侵檢測(cè)方法進(jìn)行了對(duì)比實(shí)驗(yàn),得到如下實(shí)驗(yàn)結(jié)果。依次為[13]基于數(shù)據(jù)挖掘方法(DM )、K-均值方法(KM)、 支持向量機(jī)方法(SVM )和基于動(dòng)態(tài)聚類算法的檢查率。

通過(guò)對(duì)比的實(shí)驗(yàn)結(jié)果可以看出,基于動(dòng)態(tài)聚類的算法較其他入侵檢測(cè)方法在檢測(cè)率方面有了一些提高。采用基于支持向量機(jī)和數(shù)據(jù)挖掘的檢測(cè)方法的訓(xùn)練速度和運(yùn)算量都比較大,而采用K-均值方法容易造成局部?jī)?yōu)化等原因,使得它們的檢查效率低于基于動(dòng)態(tài)聚類算法的效率,這也充分證明了動(dòng)態(tài)聚類算法應(yīng)用于系統(tǒng)入侵檢測(cè)的有效性。

5 結(jié) 語(yǔ)

本文在介紹了動(dòng)態(tài)聚類算法并將此方法用于網(wǎng)絡(luò)入侵檢測(cè)。通過(guò)實(shí)驗(yàn)和與其他方法的對(duì)比實(shí)驗(yàn)說(shuō)明了該方法用于網(wǎng)絡(luò)入侵檢測(cè)的有效性,可以在一定程度上提高了檢測(cè)效率,降低錯(cuò)報(bào)率和誤報(bào)率。所以可將動(dòng)態(tài)聚類算法有效得用于網(wǎng)絡(luò)入侵檢測(cè)。

參考文獻(xiàn)

[1]Ajith Abraham,Ravi Jain.Soft Computing Models for Network Intrusion Detection Systems[J].Computational Intelligence,2005(4):191-207.

[2]Can Longzheng,Yu Shmgsheng,Wang Xiaofeng,et al.Network-based Anomaly Intrusion Detection with Numeric-and-Nominal with Data[J].Journal of Shanghai University(English Edition),2006,10(5):415-420.

[3]Sang Kyun Noh,Yong Min Kim,Dong Kook Kim,et al.Network Anomaly Detection Based on Clustering of Sequence Patterns[J].Computer Science,2006(3981):349-358.

[4]蘇璞睿,馮登國(guó).基于進(jìn)程行為的異常檢測(cè)模型[J].電子學(xué)報(bào),2006,34(10):1 809-1 811.

[5]羅守山.入侵檢測(cè)[M].北京:北京郵電大學(xué)出版社,2003.

[6]張超,霍紅衛(wèi),錢秀檳,等.入侵檢測(cè)系統(tǒng)概述[J].計(jì)算機(jī)工程與應(yīng)用,2004(3):116-179.

[7]伊靜,劉培玉.入侵檢測(cè)中模式匹配算法的研究[J].計(jì)算機(jī)應(yīng)用與軟件,2005,22(1):112-114.

[8]Huy Anh Nguyen,Deokjai Choi.Application of Data Mining to Network Intrusion Detection:Classifier Selection Model[J].Lecture Notes in Computer Science,2008(5):399-408.

[9]朱永宣.基于模式識(shí)別的入侵檢測(cè)關(guān)鍵技術(shù)研究[M]。 北京郵電大學(xué),2006(9):4-18.

[10]舒寧,馬洪超,孫和利.模式識(shí)別的理論與方法[M].武漢:武漢大學(xué)出版社,2004.

[11]曹謝東.模糊信息處理及應(yīng)用[M].北京:科學(xué)出版社,2003.

[12]趙曦濱,井然哲,顧明.基于粗糙集的自適應(yīng)入侵檢測(cè)方法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2008,48(7):1 165-1 168.