動態(tài)聚類算法在網(wǎng)絡(luò)入侵檢測中的應(yīng)用

張 珍,萬世昌

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

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

中圖分類號:TP393文獻標識碼:A

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

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

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

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

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

1 聚類算法

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

1.1 聚類的基本要素

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

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

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

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

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

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

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

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

C個類別,待聚類數(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 動態(tài)聚類算法

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

2.1 動態(tài)聚類算法的特點

動態(tài)聚類算法具有兩方面的特點:

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

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

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

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

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

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

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

(3) 刪除和合并聚合類并認定遠離點;

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

3 基于動態(tài)聚類算法的入侵檢測

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

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

算法具體步驟:

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

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

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

(4) 計算最小方差

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 動態(tài)聚類算法目標

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

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

4 實驗環(huán)境與實驗分析

4.1 實驗環(huán)境

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

4.2 實驗分析

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

表1 實驗結(jié)果

數(shù)目類型檢測率漏報率誤報率

正常數(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)計可以看出,通過基于動態(tài)聚類算法的檢測方法進行網(wǎng)絡(luò)入侵檢測,算法在檢測率和錯檢率上得到了改進,滿足了系統(tǒng)的安全檢測需求。

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

圖1 幾種入侵檢測方法的性能比較

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

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

5 結(jié) 語

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

參考文獻

[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]蘇璞睿,馮登國.基于進程行為的異常檢測模型[J].電子學(xué)報,2006,34(10):1 809-1 811.

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

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

[7]伊靜,劉培玉.入侵檢測中模式匹配算法的研究[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]朱永宣.基于模式識別的入侵檢測關(guān)鍵技術(shù)研究[M]。 北京郵電大學(xué),2006(9):4-18.

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

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

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