聚類分析算法在入侵檢測中的應(yīng)用研究

耿 風(fēng)

（黃河水利職業(yè)技術(shù)學(xué)院，河南 開封 475004）

0 引言

網(wǎng)絡(luò)安全是現(xiàn)代社會穩(wěn)定的重要組成部分。 入侵檢測作為一種積極主動的安全防護技術(shù)，提供了對內(nèi)部攻擊、外部攻擊和誤操作的實時保護[1]，可以在網(wǎng)絡(luò)系統(tǒng)受到危害之前攔截和響應(yīng)入侵，成為防火墻的合理補充。 但是，現(xiàn)有的大多數(shù)實用入侵檢測系統(tǒng)只是將收集到的網(wǎng)絡(luò)數(shù)據(jù)與已有的攻擊模式庫進行比較，從而發(fā)現(xiàn)違背安全策略的行為。 這種模式匹配的方法對于已知的入侵攻擊檢測效率很高，但對于一些未知攻擊卻無法準確地檢測。

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中提取或挖掘有用的知識，高度自動化地分析原有的數(shù)據(jù)，做出歸納性的推理，從中挖掘出潛在的模式，并預(yù)測出對象的行為[2]。 將數(shù)據(jù)挖掘技術(shù)用于入侵檢測，把入侵檢測看成是一個數(shù)據(jù)分析過程，通過提取出用戶的行特征、總結(jié)入侵行為的規(guī)律，對于未知的入侵攻擊行為進行檢測，可以提高入侵檢測系統(tǒng)的準確性、擴展性和自適應(yīng)性。 數(shù)據(jù)挖掘有多種模型和算法，應(yīng)用到入侵檢測中的數(shù)據(jù)挖掘算法主要集中在關(guān)聯(lián)規(guī)則算法、序列模式算法、分類算法和聚類分析算法，每種算法都有不同的適用范圍。 本文主要研究了K-means 算法、 基于相似度的聚類算法和蟻群聚類算法，并將其應(yīng)用到入侵檢測系統(tǒng)中，通過測試數(shù)據(jù)進行實驗測試、對算法進行比較，提出將聚類算法融合的思想。

1 聚類分析算法概述

聚類分析是一種無監(jiān)督的學(xué)習(xí)方法。 它將一些未知模式分成若干類，若特征向量之間的距離在一定誤差范圍內(nèi)相等，則認為它們是同一類型。 通過聚類分析，能發(fā)現(xiàn)新型的和未知的入侵類型。 目前，可以應(yīng)用到入侵檢測的聚類算法有很多，這里主要介紹K-means 算法、基于相似度的聚類算法和蟻群聚類算法。

1.1 K-means算法概述

K-means 算法是一種基于劃分的算法。 若給定包含n 個數(shù)據(jù)對象的數(shù)據(jù)集和所要形成的聚類個數(shù)k，K-means 算法將對象集合劃分為k 個子集（k≤n)，每一個子集均代表一個聚類，聚類的結(jié)果就由k 個聚類中心來表達。 基于給定的聚類目標函數(shù)，算法采用迭代更新的方法，每一次迭代過程都是向目標函數(shù)值減小的方向進行的，最終使目標函數(shù)值取得極小值，達到較優(yōu)的聚類效果。 這時，同一聚類中的對象是“相似”的，而不同聚類中的對象是“不相似”的。

1.2 基于相似度的聚類算法概述

基于相似度的聚類算法是一種無指導(dǎo)的學(xué)習(xí)過程，它根據(jù)聚類間的相似度來判斷兩個類之間的相似或相異程度，以“距離”作為相似度與相異度的度量標準[3]。 數(shù)據(jù)聚類的輸入數(shù)據(jù)是一個數(shù)據(jù)集（包含了大量的數(shù)據(jù)）， 每個數(shù)據(jù)用一個n 維向量X(x1，x2，x3，…，xn)來表示，數(shù)據(jù)的每一個屬性值用xi表示(i=1,2,…,n)。 該算法聚類的輸出是一個簇間具有最大相異度、簇內(nèi)具有最大相似度的若干個聚類。

1.3 蟻群聚類算法概述

蟻群聚類算法是由模擬真實螞蟻覓食過程而提出的[4]。 蟻群在尋找食物的過程中，每個螞蟻通過感知信息素的存在和強度，傾向于向信息素濃度大的方向移動，使得整個蟻群的集體行為構(gòu)成了信息素的正反饋過程，從而找到較好路徑。 即某一路徑經(jīng)過的螞蟻越多，則積累的信息素就越多，強度就越大，該路徑在下一時間內(nèi)被其他螞蟻選擇的概率也越大。 目前，蟻群算法已在組合優(yōu)化問題求解，以及電力、通信、化工、交通、機器人、冶金等多個領(lǐng)域中得到應(yīng)用，都表現(xiàn)出了令人滿意的性能。

2 聚類分析算法在在入侵檢測中的應(yīng)用

2.1 K－means算法在入侵檢測中的應(yīng)用

K-means 算法具有較小的計算復(fù)雜度和良好的擴展性，還可以滿足網(wǎng)絡(luò)入侵檢測對于實時性的要求。 應(yīng)用K-means 算法進行入侵檢測的步驟為：收集連接記錄，并對其進行標準化后，獲得進行聚類分析的數(shù)據(jù)集；利用K-means 聚類算法，對該數(shù)據(jù)集進行分類， 區(qū)分出哪些是正常的連接記錄，哪些是異常的連接記錄[5]。 其算法可描述如下：

1）輸入。輸入聚類個數(shù)k、包含n 個數(shù)據(jù)的數(shù)據(jù)集、閾值α。

2）輸出。 標記為正常或異常的k 個聚類。

3）計算方法。

（1）任意選取k 個數(shù)據(jù)作為初始的聚類中心；

（2）do

{以數(shù)據(jù)與聚類中心值的距離最近為標準，將每個數(shù)據(jù)劃分到一個聚類；

更新聚類的中心值，即重新計算每個聚類中所有數(shù)據(jù)的平均值；}

（3）while(劃分不再發(fā)生變化)；

（4）do

if(聚類中的數(shù)據(jù)個數(shù)＞=) 標記為正常；

else 標記為異常：

（5）while(所有聚類標記結(jié)束)；

2.2 基于相似度的聚類算法在入侵檢測中的應(yīng)用

基于相似度的聚類分析方法主要是：以給定的水平值為標準，對某一時刻收集到的原始數(shù)據(jù)進行分類，并根據(jù)分類結(jié)果，把新的檢測數(shù)據(jù)關(guān)聯(lián)到與其相似度最大的簇中（如果原始數(shù)據(jù)值與聚類結(jié)果存在很大的差異，那么這個新的異常數(shù)據(jù)就可能在聚類計算中產(chǎn)生新的簇）。 在此基礎(chǔ)上，判斷是否有入侵行為發(fā)生。 其算法描述如下：

1）輸入。 原始數(shù)據(jù)集、相似度水平值α。

2）輸出。 標記為正?；虍惓５膋 個聚類

3）計算方法。

（1）隨機抽樣產(chǎn)生n 個原始數(shù)據(jù)，初始化n 個聚類；

（2）do

{計算n 個聚類兩兩之間的相似度，不必考慮距離方向，將相似度值表示為n 階下的三角矩陣；

比較得出最大相似度simmax；

if（simmax＞=）合并相似度最大的兩簇；

n=n-1；}

（3）while（simmax＜）；

（4）do

if（聚類中的數(shù)據(jù)個數(shù)＞=）標記為正常；

else 標記為異常；

（5）while（所有聚類標記結(jié)束）；

2.3 蟻群聚類算法在入侵檢測中的應(yīng)用

在基于蟻群聚類的入侵檢測算法中，可將數(shù)據(jù)實例視為不同屬性的螞蟻，將聚類中心看作螞蟻所要尋找的“食物源”。 即將數(shù)據(jù)聚類過程看成一種螞蟻尋找食物源的過程。 蟻群聚類方法最大的特點是：不需設(shè)定最終產(chǎn)生的聚類數(shù)目；聚類中心是動態(tài)變化的；可以發(fā)現(xiàn)任意形狀的聚類。 該算法實質(zhì)上是K-means 算法和基于螞蟻覓食原理的蟻群聚類算法的有機結(jié)合，是對K-means 算法的一個改進。蟻群聚類算法在入侵檢測中應(yīng)用的算法可描述如下：

1）輸入。 聚類個數(shù)k、預(yù)設(shè)聚類半徑R、初始概率P0、初始統(tǒng)計誤差、閾值α。

2）輸出。 標記為正?；虍惓５膋 個聚類。

3）計算方法。

（1）初始化聚類中心，任取不同的數(shù)據(jù)賦予Cj；

（2）do

{取不同于Cj 且未被標識過的Xi；

計算Pij；

if（Pij≥P0）標識Xi 并歸到Cj；}

（3）while(所有數(shù)據(jù)均被處理)；

（4）計算εj，ε0；

（5）if（＞=）更新Cj 和ij 并返回2；

（6）do

if（聚類中的數(shù)據(jù)個數(shù)＞=）標記為正常；

else 標記為異常；

（7）while(所有聚類標記結(jié)束)；

3 實驗測試與結(jié)果分析

通過仿真實驗來檢驗3 種聚類算法在入侵檢測中的檢測效果。

3.1 測試條件

從KDD Cupl999 網(wǎng)絡(luò)數(shù)據(jù)集中隨機選取3 組數(shù)據(jù)樣本集（包含Normal、Probe、DoS、R2L、U2R5 種類型）， 每個數(shù)據(jù)集中有2 000 個正常連接、100 個異常連接，而且使異常連接的種類盡可能平均。 實驗平臺的主要部件為CPU 為酷睿2.8GHz、 內(nèi)存容量2GB、Windows XP 操作系統(tǒng)、Visual C++語言環(huán)境。

3.2 測試結(jié)果分析

3 種聚類算法的入侵檢測結(jié)果如表1 所示。

表1 三種聚類算法的檢測結(jié)果Table 1 Three kinds of clustering algorithm testing results

檢測率和誤報率是衡量入侵檢測系統(tǒng)的主要標準，一個好的系統(tǒng)應(yīng)該使檢測率盡可能大，而誤報率則盡可能小[6]。 由表1 可知，3 種算法對于未知入侵行為的檢測都是可行和有效的，但3 種檢測方法相比，基于相似度的聚類算法的檢測率和誤報率都優(yōu)于K-means 算法，而蟻群算法則更優(yōu)。

4 結(jié)語

實際上，由于攻擊方法的多樣性及檢測環(huán)境的多變性，單一使用某種算法來進行入侵檢測并不能達到良好效果， 因為各種算法都有一定的局限性。因此，可以嘗試將多種聚類算法融合起來，協(xié)同進行入侵檢測，使各種算法都能發(fā)揮自身優(yōu)勢，將它們應(yīng)用到適合自身特點的步驟當(dāng)中，使其能互相配合、綜合發(fā)揮作用，提高入侵檢測系統(tǒng)的可行性、實時性、有效性及其穩(wěn)定性。

[1] 唐正軍，李建華. 入侵檢測技術(shù)[M]. 北京：清華出版社，2004：26-30.

[2] HAN JIAWEI，KAMBER M. 數(shù) 據(jù) 挖 掘 概 念 與 技 術(shù)[M].范明，孟小峰，譯.北京：機械工業(yè)出版社，2001：85-92.

[3] 劉學(xué)誠，李云. 基于聚類算法的入侵檢測研究[J]. 計算機與數(shù)字工程，2007(9)：101-103.

[4] 張惟皎，劉春煌，尹曉峰. 蟻群算法在數(shù)據(jù)挖掘中應(yīng)用研究[J]. 計算機工程與應(yīng)用，2004，40(28): 171-173.

[5] 李洋. K-means 聚類算法在入侵檢測中的應(yīng)用[J]. 計算機工程，2007，33(14)，154-156.

[6] 張巍. 基于數(shù)據(jù)挖掘技術(shù)的智能化入侵檢測模型[J]. 計算機工程，2005，31(8):134-136.