耿 風(fēng)

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

0 引言

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

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

1 聚類(lèi)分析算法概述

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

1.1 K-means算法概述

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

1.2 基于相似度的聚類(lèi)算法概述

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

1.3 蟻群聚類(lèi)算法概述

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

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

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

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

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

2）輸出。 標(biāo)記為正?；虍惓５膋 個(gè)聚類(lèi)。

3）計(jì)算方法。

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

（2）do

{以數(shù)據(jù)與聚類(lèi)中心值的距離最近為標(biāo)準(zhǔn)，將每個(gè)數(shù)據(jù)劃分到一個(gè)聚類(lèi)；

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

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

（4）do

if(聚類(lèi)中的數(shù)據(jù)個(gè)數(shù)＞=) 標(biāo)記為正常；

else 標(biāo)記為異常：

（5）while(所有聚類(lèi)標(biāo)記結(jié)束)；

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

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

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

2）輸出。 標(biāo)記為正常或異常的k 個(gè)聚類(lèi)

3）計(jì)算方法。

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

（2）do

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

比較得出最大相似度simmax；

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

n=n-1；}

（3）while（simmax＜）；

（4）do

if（聚類(lèi)中的數(shù)據(jù)個(gè)數(shù)＞=）標(biāo)記為正常；

else 標(biāo)記為異常；

（5）while（所有聚類(lèi)標(biāo)記結(jié)束）；

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

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

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

2）輸出。 標(biāo)記為正常或異常的k 個(gè)聚類(lèi)。

3）計(jì)算方法。

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

（2）do

{取不同于Cj 且未被標(biāo)識(shí)過(guò)的Xi；

計(jì)算Pij；

if（Pij≥P0）標(biāo)識(shí)Xi 并歸到Cj；}

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

（4）計(jì)算εj，ε0；

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

（6）do

if（聚類(lèi)中的數(shù)據(jù)個(gè)數(shù)＞=）標(biāo)記為正常；

else 標(biāo)記為異常；

（7）while(所有聚類(lèi)標(biāo)記結(jié)束)；

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

通過(guò)仿真實(shí)驗(yàn)來(lái)檢驗(yàn)3 種聚類(lèi)算法在入侵檢測(cè)中的檢測(cè)效果。

3.1 測(cè)試條件

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

3.2 測(cè)試結(jié)果分析

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

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

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

4 結(jié)語(yǔ)

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

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

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

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

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

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

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