徐　超,王　芳,黃樹成

(江蘇科技大學(xué)計算機科學(xué)與工程學(xué)院,江蘇鎮(zhèn)江　212003)

?

基于聚類分析的入侵檢測算法*

徐超,王芳,黃樹成

(江蘇科技大學(xué)計算機科學(xué)與工程學(xué)院,江蘇鎮(zhèn)江212003)

摘要:聚類技術(shù)在入侵檢測中被廣泛研究,但是傳統(tǒng)的K-means算法對初始值敏感,無法取得理想的效果;層次聚類算法時間復(fù)雜度高,性能較差。針對這些問題,設(shè)計了一種改進的K-means算法:算法優(yōu)化孤立點和噪聲處理能力,根據(jù)有效性指標(biāo)獲得最優(yōu)K值,在此基礎(chǔ)上,動態(tài)選取初始聚類中心進行聚類,可以取得較好的聚類效果。采用數(shù)據(jù)集KDD Cup99將改進的算法應(yīng)用于入侵檢測,進行仿真實驗。實驗結(jié)果表明,改進的算法有效地提高了檢測率和降低了誤檢率,與現(xiàn)有算法相比具有一定的優(yōu)勢。

關(guān)鍵詞:聚類;K-means算法;入侵檢測

修回日期： 2015-11-12

王芳(1971-),女,副教授。

黃樹成(1969-),男,副教授。

作為網(wǎng)絡(luò)與信息安全領(lǐng)域的一項重要技術(shù),入侵檢測(Instrusion Detection,ID)已經(jīng)成為網(wǎng)絡(luò)安全體系的一個重要組成部分。通過分析從網(wǎng)絡(luò)和計算機系統(tǒng)中關(guān)鍵點搜集的數(shù)據(jù),檢測出可疑的訪問、資源請求等可疑活動,從而發(fā)現(xiàn)是否有攻擊存在,以保證系統(tǒng)資源的機密性、完整性和可用性[1]。誤用檢測和異常檢測是現(xiàn)有的入侵檢測系統(tǒng)常用的檢測方法。誤用檢測用已知的入侵方法匹配并識別攻擊;異常檢測則將那些已經(jīng)明顯偏離用戶正常使用系統(tǒng)方式的行為表示成異常行為。

數(shù)據(jù)挖掘能從海量審計數(shù)據(jù)中挖掘出正常和異常行為模式,這大大減少了人工分析和編碼所帶來的繁重工作,更提高了入侵檢測系統(tǒng)的工作效率,因而,近幾年數(shù)據(jù)挖掘技術(shù)被廣泛應(yīng)用于入侵檢測領(lǐng)域。傳統(tǒng)的基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)完全依賴數(shù)據(jù)挖掘算法對已標(biāo)記過的數(shù)據(jù)樣本的學(xué)習(xí),劃分聚類中的K-means算法和層次聚類算法是較為常見的兩種聚類方法。K-means算法能快速確定K個劃分使得平方誤差最小,具有較高的運算率,但K-means算法對初始值較為敏感,初始聚類中心的隨機選擇也可能會造成聚類陷入局部最優(yōu)。而層次聚類方法比較符合數(shù)據(jù)的特性[2],聚類的質(zhì)量比較高,但是時間復(fù)雜度較高。根據(jù)兩種聚類方法各自在處理數(shù)據(jù)上的優(yōu)缺點,學(xué)術(shù)界采用基于兩種算法有機結(jié)合的混合算法,以達到既能降低聚類時間又能提高聚類質(zhì)量的效果。如文獻[5]中提出了一種改進的混合聚類算法H-K,解決了K-means算法中初始聚類中心選擇的隨機性和先驗性的問題,但該算法對非球狀簇的聚類效果較差,且時間復(fù)雜度較高[3]。因此,根據(jù)該算法的特點與不足,本文結(jié)合現(xiàn)有算法及有效性指標(biāo)提出了一種改進算法。該算法首先針對K-means算法需事先提供聚類數(shù)K值以及初始聚類中心敏感進行改進,然后在聚類后期采用層次算法進行精細凝聚以提高聚類的質(zhì)量,最后將改進的算法應(yīng)用于入侵檢測系統(tǒng)。實驗表明，改進的算法具有較高的檢測率和較低的誤檢率。

1入侵檢測系統(tǒng)

入侵檢測是對入侵行為的檢查,通過收集網(wǎng)絡(luò)和系統(tǒng)的網(wǎng)絡(luò)行為、安全日志、審計數(shù)據(jù)等若干關(guān)鍵點信息,分析檢測是否有違反安全策略的行為和被攻擊的跡象。入侵檢測提供了對內(nèi)部攻擊、外部攻擊和誤操作的實時保護,可以在網(wǎng)絡(luò)系統(tǒng)受到危害前攔截和響應(yīng)入侵。

圖1　入侵檢測通用模型

入侵檢測系統(tǒng)(IDS)是用來檢測系統(tǒng)或網(wǎng)絡(luò)以發(fā)現(xiàn)可能入侵或攻擊的系統(tǒng),通過對網(wǎng)絡(luò)傳輸進行實時檢測,檢查待定的系統(tǒng)漏洞、攻擊模式、存在缺陷的系統(tǒng)或用戶的行為模式,在發(fā)現(xiàn)可疑入侵時發(fā)出警告或攔截,是一種積極主動的安全防護技術(shù)。人們對IDS進行標(biāo)準(zhǔn)化,CIDF[6]闡述了一個IDS通用模型,將IDS分成四個組件,組件之間的交互數(shù)據(jù)使用通用入侵檢測對象(簡稱gido)格式,模型如圖1所示。

2聚類綜述

2.1基本概念

“物以類聚,人以群分”,聚類(clustering)是數(shù)據(jù)挖掘的一種重要算法,是根據(jù)數(shù)據(jù)的內(nèi)在相似性將未標(biāo)記的數(shù)據(jù)集劃分為多個類別,使類別內(nèi)的數(shù)據(jù)相似度較大,而類別間的數(shù)據(jù)相似度較小。即聚類是將數(shù)據(jù)集劃分為多個類或簇,使得數(shù)據(jù)樣本具有較高相似度的為一簇,且不同簇中的數(shù)據(jù)樣本不具備相似性。聚類的過程大致如圖2所示。

圖2　聚類過程圖

2.2聚類算法分類

聚類算法的選擇取決于數(shù)據(jù)的類型、目的以及具體的應(yīng)用,目前,并沒有一種算法達到普適的效果。現(xiàn)有聚類算法大致分為劃分式聚類算法、層次聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法、基于模型的聚類算法以及基于譜圖理論的譜聚類算法等[4]。

劃分式聚類算法是最基本的聚類算法,最常用的是K-means算法,其基本思想是:首先從N個數(shù)據(jù)對象中隨機選擇K個數(shù)據(jù)對象作為初始聚類中心,而對于余下的每個對象,根據(jù)其與各個聚類中心的距離或相似度,分別將它們分配給與其最相似的聚類;然后重新計算每個聚類的平均值,尋求新的聚類中心。這個過程不斷重復(fù),直到各個聚類中心不再變化或標(biāo)準(zhǔn)測度函數(shù)開始收斂。

層次聚類方法可分為凝聚層次聚類和分裂層次聚類。其中凝聚是一種自底向上合并的方法,基本思想是:首先把每個數(shù)據(jù)對象作為不同的簇,然后不斷使用基于簇的代表點的方法對最相似的兩個簇進行合并,直到簇的數(shù)目達到了用戶指定的閾值。

3算法的改進

3.1K-means算法的缺點

K-means算法對大型數(shù)據(jù)集的處理效率非常高,當(dāng)樣本分布呈現(xiàn)類內(nèi)團聚時,聚類效果更好。K-means算法以確定聚類數(shù)K和選取的初始聚類中心為前提,使得各樣本對象到其所判屬的聚類中心距離平方之和最小。但是,K-means算法存在著一定的缺陷:1)易受孤立點和噪聲的影響。算法對于數(shù)據(jù)集中的孤立點和噪聲比較敏感,對聚類結(jié)果可能會產(chǎn)生較大的影響;2)事先需給出K值,K值的選取難以界定;3)隨機選取的K個樣本作為聚類中心,對于一些結(jié)構(gòu)較為復(fù)雜的數(shù)據(jù)集來說,聚類結(jié)果可能不穩(wěn)定,產(chǎn)生錯誤的聚類結(jié)果。

3.2優(yōu)化孤立點和噪聲的處理能力

K-means算法會因為噪聲和孤立點的存在,而導(dǎo)致差異較大的聚類結(jié)果,從而影響算法的執(zhí)行效率和準(zhǔn)確度。在這里,對算法進行了改進,對數(shù)據(jù)集進行初始劃分,降低噪聲和孤立點的影響。

定義1設(shè)X為數(shù)據(jù)集,X={x1,x2,…,xn},假設(shè)n個樣本數(shù)據(jù)被聚類成S類,聚類中心個數(shù)為K,定義數(shù)據(jù)xi到其它樣本數(shù)據(jù)的距離和為

(1)

其中，‖·‖2表示平方歐氏距離。

定義2設(shè)X為數(shù)據(jù)集,X={x1,x2,…,xn},假設(shè)n個樣本數(shù)據(jù)被聚類成S類,聚類中心個數(shù)為K,定義數(shù)據(jù)集X中距離和的均值為

(2)

算法(簡稱優(yōu)化算法A)描述如下:

1) 計算每兩個數(shù)據(jù)之間的歐氏距離,得到距離矩陣D,再依次計算各個數(shù)據(jù)的距離和SumDist(xi)以及數(shù)據(jù)集的距離和的均值avgS;

2) 去除距離和SumDist(xi)大于均值avgS的點,即去除孤立點和噪音數(shù)據(jù),從而得到一個新的樣本數(shù)據(jù)集X′及距離矩陣D′;

3) 將步驟2)得到的結(jié)果構(gòu)造最小生成樹,按權(quán)值降序排列,刪掉K-1個分支,從而得到K個子簇。

4) 計算各子簇的數(shù)據(jù)的算術(shù)均值作為K個初始聚類的聚類中心。

算法分析:實驗證明,利用該算法得到的初始聚類中心較為接近迭代聚類的收斂聚類中心,且數(shù)據(jù)點盡可能地分散,刪掉了孤立點和噪音的影響,取得了較好的劃分聚類結(jié)果。

3.3K值的確定

K-means算法事先需要給出聚類數(shù)K值,但K值的選取估計,不準(zhǔn)確的K值會影響最終的聚類效果。在這里,為了有效地選取更為合適的K值,提出了一種K值有效性指標(biāo)[7],用以評估聚類結(jié)果以及確定K值。

定義3設(shè)X為數(shù)據(jù)集,X={x1,x2,…,xn},假設(shè)其中的k個樣本數(shù)據(jù)被聚類劃分成類Si,Si={s1,s2,…,sk},定義類內(nèi)距離Bet(Si)為類Si中任意兩個數(shù)據(jù)x,y的距離平方和:

(3)

定義4設(shè)X為數(shù)據(jù)集,X={x1,x2,…,xn},假設(shè)其中的k個樣本數(shù)據(jù)被聚類劃分成類Si,Si={s1,s2,…,sk},定義類間距離Wit(Si,Sj)為類Si到其他類Sj的距離:

(4)

其中，k、p分別為類Si和類Sj中的數(shù)據(jù)對象個數(shù),x、y分別為類Si和類Sj中的數(shù)據(jù)對象。

定義5設(shè)X為數(shù)據(jù)集,X={x1,x2,…,xn},假設(shè)其中的k個樣本數(shù)據(jù)被聚類劃分成類Si,Si={s1,s2,…,sk},定義BW(S)為K值有效性指標(biāo):

(5)

K值有效性指標(biāo)反映了聚類結(jié)構(gòu)的類內(nèi)緊密性和類間分離性,從類內(nèi)緊密的角度上看,樣本的類內(nèi)距離Bet(Si)越小越好,從類間遠離的角度上看,樣本離近鄰聚類的距離,即類間距離Wit(Si,Sj)越大越好,使用線性組合方式平衡二者的關(guān)系,當(dāng)BW(S)最小時,類內(nèi)緊密和類間遠離達到一個平衡值,對應(yīng)的就是最優(yōu)聚類的劃分,此時的K值就是最優(yōu)聚類數(shù)。

3.4基于最優(yōu)聚類數(shù)的K-means算法改進

通過去除孤立點和噪聲的影響的處理優(yōu)化以及K值的確定,下面將上述的改進方法進行有機結(jié)合得到一種改進的K-means算法,其基本思想是:首先由K值的有效性指標(biāo)確定K值,算法過程中運用到優(yōu)化算法A來進行初始聚類優(yōu)化,然后再迭代計算出K個聚類中心,最后調(diào)用層次算法進行精細凝聚檢驗。其算法的主要步驟如下:

2) FOR K=Kminto Kmax,調(diào)用優(yōu)化算法A,得到初始聚類劃分S,及所有K值集合,計算每個數(shù)據(jù)對象到每個聚類中心的聚類,并將它賦給離它最近的類;

3) 利用聚類結(jié)果,計算各個K值的有效性指標(biāo)BW(S),比較有效性指標(biāo)值,BW(S)達到最小時,所對應(yīng)的K值即為最優(yōu)聚類數(shù),該值所對應(yīng)的聚類劃分就是初始聚類中心;

4) 重復(fù)步驟3),將每個數(shù)據(jù)對象賦給與它距離最小的類,聚類出子簇,重新計算每個簇的平均值,直到滿足終止條件;

5) 調(diào)用層次凝聚算法進行精細凝聚,利用整體相似度合并子簇,評價合并前后的聚類質(zhì)量,聚類質(zhì)量下降則取消合并;

6) 直到收斂不再發(fā)生變化。

4實驗研究與分析

4.1入侵檢測模型

入侵檢測是檢測系統(tǒng)及時發(fā)現(xiàn)違反安全準(zhǔn)則的入侵行為并報警采取相應(yīng)的防護手段的行為。入侵檢測系統(tǒng)分為訓(xùn)練部分和異常行為檢測部分[8]。

訓(xùn)練部分是:將訓(xùn)練數(shù)據(jù)輸入到系統(tǒng)中,系統(tǒng)自動生成聚類結(jié)果,再對聚類結(jié)果進行分析標(biāo)示。

異常行為檢測部分:將需再檢測的數(shù)據(jù)對象先進行標(biāo)準(zhǔn)化處理,用改進的K-means算法生成正常行為模式庫,即計算處理后的數(shù)據(jù)到各個聚類中心的距離,賦給離它最近的聚類中,若這個聚類標(biāo)識為正常類,則該數(shù)據(jù)對象為正常數(shù)據(jù),否則為異常數(shù)據(jù)。這樣有效地提高了系統(tǒng)的檢測率,降低了誤報率,實現(xiàn)了一個高效的入侵檢測系統(tǒng)。

基于聚類分析的入侵檢測模型如圖3所示。

圖3　基于聚類分析的入侵檢測系統(tǒng)模型

本文采用經(jīng)典的KDD Cup99數(shù)據(jù)集作為網(wǎng)絡(luò)數(shù)據(jù)進行驗證,選取Snort入侵檢測系統(tǒng)為基礎(chǔ),經(jīng)過預(yù)處理模塊使數(shù)據(jù)標(biāo)準(zhǔn)化,將其轉(zhuǎn)化成合適的數(shù)據(jù)格式,并對數(shù)據(jù)進行除噪等操作,使用改進的K-means算法進行聚類,將包含大量數(shù)據(jù)的類標(biāo)識為一個正常行為類,而包含小量數(shù)據(jù)的類則為異常類。然后將異常類作為未知數(shù)據(jù)傳給Snort入侵檢測[9]分析模塊,利用其規(guī)則庫對未知數(shù)據(jù)進行再檢測,對異常數(shù)據(jù)進行告警,而將未匹配的數(shù)據(jù)歸到正常行為類中。該模型提高了入侵檢測系統(tǒng)的檢測速率。

4.2實驗結(jié)果與分析

為了測試基于改進的劃分算法的入侵檢測系統(tǒng)的性能,本文實驗采用KDD Cup99數(shù)據(jù)集中的kddcup-data-10percent數(shù)據(jù)包對檢測算法和入侵檢測模型進行了仿真實驗,并對結(jié)果做出相應(yīng)的分析。

入侵檢測的性能可以用檢測率(Detection Rate,DR)和誤報率(False Positive Rate,FPR)進行描述:

(6)

(7)

數(shù)據(jù)預(yù)處理:kddcup-data-10percent數(shù)據(jù)集是KDD Cup99的10%抽樣,每條數(shù)據(jù)由41個特征屬性和一個決策屬性構(gòu)成[10],決策屬性是每條數(shù)據(jù)的所屬類別,在測試時僅作為判斷條件。數(shù)據(jù)集中包含有符號型的數(shù)據(jù)屬性,不適合本文的聚類測試,且實驗所使用的Matlab平臺不識別字符,所以需進行數(shù)據(jù)預(yù)處理,將數(shù)據(jù)位經(jīng)過數(shù)值化和歸一化后,才可用來測試。

每次實驗時,根據(jù)數(shù)據(jù)集中的種類比例分配,隨機選取了8324條數(shù)據(jù),其中,正常數(shù)據(jù)為6992條,異常數(shù)據(jù)為1332條,標(biāo)記為數(shù)據(jù)集D。多次測試得到一個平均記錄,如表1所示。

表1　入侵檢測結(jié)果

經(jīng)式(6)和式(7)計算可知,改進前后的入侵檢測系統(tǒng)的檢測率和誤檢率如表2所示。

表2　實驗測試對照表

由上述實驗數(shù)據(jù)表明,采用了基于改進的K-means算法的入侵檢測系統(tǒng)是有效而且可行的,本文的入侵檢測系統(tǒng)提高了檢測率,降低了誤報率,優(yōu)于傳統(tǒng)的入侵檢測系統(tǒng)。

5結(jié)束語

入侵檢測技術(shù)是計算機網(wǎng)絡(luò)安全的重要保障,本文提出了一種基于改進的K-means算法,設(shè)計了入侵檢測系統(tǒng)。針對傳統(tǒng)K-means算法的不足之處,采用有效性指標(biāo)來確定K值的選取,并動態(tài)地獲取初始聚類中心,進行了孤立點和噪音的刪除處理,降低其影響,降低了聚類的迭代次數(shù),有效地提高了聚類效果。基于改進的劃分算法的入侵檢測模型運用了傳統(tǒng)的Snort入侵檢測模型,結(jié)合改進的K-means算法進行異常行為檢測,提高了入侵檢測系統(tǒng)的性能。

經(jīng)測試證明本文所提出的改進的K-means算法在入侵檢測方面具有可行性和有效性,優(yōu)于傳統(tǒng)的入侵檢測系統(tǒng)。

參考文獻:

[1]謝卓.基于聚類學(xué)習(xí)算法的網(wǎng)絡(luò)入侵檢測研究[J].現(xiàn)代電子技術(shù)，2012,35(2):80-93.

[2]ALMEIDA J,BARBOSA L,PAIS A,et al.Improving hierarchical cluster analysis:a new method with outlier detection and automatic clusterint[J].Chemometrics and Intelligent Laboratory Systems,2007,87(2):208-217.

[3]郝洪星,朱玉全,陳耿,李米娜.基于劃分和層次的混合動態(tài)聚類算法[J]. 計算機應(yīng)用研究,2011(1):3-4.

[4]Kamber M.數(shù)據(jù)挖掘:概念與技術(shù)[M].韓家煒,譯.北京:機械工業(yè)出版社,2012:338-467.

[5]LIN Cheng-ru,CHEN M S.Combining partitional and hierarchical algorithms for rubust and efficient data clustering with cohesionself-merging[J].IEEE Trans on knowledge and Data Engineering,2005,17(2): 145-159.

[6]周繼軍,蔡毅.網(wǎng)絡(luò)與信息安全基礎(chǔ)[M].北京:清華大學(xué)出版社,2008：205-207.

[7]周世兵.聚類分析中的最佳聚類數(shù)確定方法研究及應(yīng)用[D].無錫：江南大學(xué)博士學(xué)位論文,2011.

[8]夏戰(zhàn)國,萬玲,蔡世玉,孫鵬輝.一種面向入侵檢測的半監(jiān)督聚類算法[J].山東大學(xué)學(xué)報(工學(xué)版),2012(6):2-4.

[9]傅濤,孫亞民.基于PSO的K-means算法及其在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[J].計算機科學(xué),2011,38(5):54-56.

[10]袁利永,王基一.一種改進的半監(jiān)督K-means聚類算法:研究綜述[J].計算機工程與科學(xué)，2011(6):1-3.

Intrusion Detection Based on Improved Partitioning Algorithm

XU Chao, WANG Fang, HUANG Shu-cheng

(School of Computer Science and Engineering, Jiangsu University of Science and Technology, Zhenjiang 212003, China)

Abstract:Clustering technique has been extensive researched in intrusion detection, but the traditional k-means algorithm is sensitive to initial values,unable to obtain the ideal effect. Hierarchical clustering algorithm time complexity is high and poor performance. To solve these problems,an improved K-means algorithm is presented in this paper. Outlier and noise processing capacity are optimized. The initial clustering center are selected dynamically, according to optimal K values which is obtained by the effectiveness indicator. The KDD Cup99 datasets is applied to conduct simulation experiment on the application of the improved algorithm in intrusion detection. The experiments show that the detection rate is improved effectively and the false positive rate is reduced. The improved algorithm than the existing algorithm has certain advantages.

Key words:clustering; K-means algorithm; intrusion detection

作者簡介：徐超(1990-),女,江蘇贛榆人,碩士研究生,研究方向為數(shù)據(jù)挖掘。

*基金項目：國家自然科學(xué)基金(61572498)

收稿日期：2015-10-30

中圖分類號:TP311.13

文獻標(biāo)志碼:A

DOI:10.3969/j.issn.1673-3819.2016.01.013

文章編號：1673-3819(2016)01-0057-04