付雙勝 張明軍 劉棣華 魯曉帆

長(zhǎng)春工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 吉林 130012

0 引言

近年來(lái)，將聚類(lèi)分析方法應(yīng)用于入侵檢測(cè)方面的研究變得非?；钴S，它也是一個(gè)極富挑戰(zhàn)性的研究領(lǐng)域。我們把物理或抽象對(duì)象的集合分組成為類(lèi)似的對(duì)象組成的多個(gè)類(lèi)或簇的過(guò)程叫做聚類(lèi)。由聚類(lèi)所生成的簇是一組數(shù)據(jù)對(duì)象的集合，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。聚類(lèi)分析是一種探查數(shù)據(jù)結(jié)構(gòu)的工具，其核心是聚類(lèi)。聚類(lèi)分析也是一項(xiàng)基本分析技術(shù)，屬于非監(jiān)督學(xué)習(xí)技術(shù)，不需要以先驗(yàn)標(biāo)識(shí)符來(lái)標(biāo)定數(shù)據(jù)類(lèi)別標(biāo)號(hào)的假定。因此基于聚類(lèi)的入侵檢測(cè)技術(shù)就是一種無(wú)監(jiān)督的檢測(cè)技術(shù)，其優(yōu)點(diǎn)是它可以在未標(biāo)記的數(shù)據(jù)上訓(xùn)練并檢測(cè)入侵，而且能有效的檢測(cè)出未知入侵。當(dāng)前無(wú)監(jiān)督的檢測(cè)技術(shù)主要存在以下不足：①在聚類(lèi)過(guò)程中只考慮元素與類(lèi)之間的距離，而沒(méi)有考慮類(lèi)大小產(chǎn)生的影響；②檢測(cè)結(jié)果對(duì)參數(shù)較敏感，參數(shù)選擇往往憑經(jīng)驗(yàn)確定，沒(méi)有一般的原則；③“元素個(gè)數(shù)越少的簇越可能是異常簇”的假設(shè)不盡合理。針對(duì)上述問(wèn)題，文獻(xiàn)[2]提出的基于引力的聚類(lèi)方法GCA的入侵檢測(cè)技術(shù)，盡管該技術(shù)在時(shí)間復(fù)雜度以及檢測(cè)的準(zhǔn)確性等明顯優(yōu)于其他一些檢測(cè)方法，但是它的誤報(bào)率相對(duì)來(lái)說(shuō)還是有點(diǎn)偏高，本文在文獻(xiàn)[2]的基礎(chǔ)上提出一種增強(qiáng)的基于GCA的入侵檢測(cè)方法，有效地降低了檢測(cè)的誤報(bào)率。

1 基于引力的聚類(lèi)方法GCA

將萬(wàn)有引力的思想引入聚類(lèi)分析，文獻(xiàn)[2]提出了基于引力的聚類(lèi)算法GCA，將聚類(lèi)過(guò)程看成對(duì)象被已有類(lèi)吸引的過(guò)程，對(duì)象依次被吸入到對(duì)其引力最大的簇中或產(chǎn)生一個(gè)新的簇。具體的算法描述如下：

（1）初始時(shí)，簇集合為空，讀入一個(gè)新的對(duì)象；

（2）以這個(gè)對(duì)象構(gòu)造一個(gè)新簇；

（3）若已到數(shù)據(jù)庫(kù)末尾，則轉(zhuǎn)(6)，否則讀入新對(duì)象，計(jì)算每個(gè)已有簇對(duì)它的引力，并選擇最大的引力；

（4）若最大引力小于給定的引力閾值r，轉(zhuǎn)(2)；

（5）否則將該對(duì)象并入具有最大引力的簇中，并更新該簇的各分類(lèi)屬性值的統(tǒng)計(jì)頻度急數(shù)值屬性的質(zhì)心，轉(zhuǎn)(3)；

（6）保存每個(gè)簇的摘要信息及引力閾值r，結(jié)束。

2 增強(qiáng)的基于GCA的入侵檢測(cè)方法

2.1 “元素越少的簇越可能是異常簇”的假設(shè)不盡合理的原因及改良方法

圖1 簇的大小與異常簇的判定的關(guān)系

如圖1所示，設(shè)簇C1包含1200個(gè)對(duì)象，簇C2包含1000個(gè)對(duì)象，簇C3包含100個(gè)對(duì)象，簇C4包含40個(gè)對(duì)象。按簇的大小作為判定簇是否為異常的依據(jù)，則簇C4較簇C3異常程度大，但是直觀(guān)地看簇 C3偏離整個(gè)數(shù)據(jù)集的程度較簇C4要大，簇C3較簇C4更應(yīng)該判定為異常類(lèi)。所以說(shuō)“元素個(gè)數(shù)越少的簇越可能是異常簇”的假設(shè)不盡合理。

在給簇作標(biāo)記時(shí)，倘若按照“元素個(gè)數(shù)越少的簇越可能是異常簇”的原則，原本是正常數(shù)據(jù)的簇C4就會(huì)標(biāo)記為異常，而本來(lái)是異常數(shù)據(jù)的簇 C3可能標(biāo)記為正常，這就導(dǎo)致誤報(bào)率大大提高。針對(duì)這個(gè)不合理性，本文提出了一個(gè)合并算法，按照一定規(guī)則把像簇C4那樣的小簇合并到像簇C1或簇C2這樣的大簇中，合并后就變成簇 C3的元素最少了，把它標(biāo)記為異常即可，這樣標(biāo)記更趨于合理，從而達(dá)到降低檢測(cè)誤報(bào)率的目的。

2.2 增強(qiáng)的基于 GCA的入侵檢測(cè)方法的主要思想

對(duì)訓(xùn)練集先用基于引力的聚類(lèi)方法 GCA進(jìn)行聚類(lèi)，聚類(lèi)后會(huì)得到一定數(shù)目的簇，在這個(gè)基礎(chǔ)上依據(jù)凝聚層次聚類(lèi)算法的思想對(duì)這些簇進(jìn)行合并，根據(jù)簇間的差異度，使用整體相似度作為聚類(lèi)質(zhì)量評(píng)價(jià)標(biāo)準(zhǔn)來(lái)決定是否要合并相似的兩個(gè)簇，合并后能使簇中心更集中，簇內(nèi)對(duì)象更緊密。再根據(jù)標(biāo)記算法標(biāo)記出聚類(lèi)結(jié)果中哪些簇屬于正常簇，哪些屬于入侵簇，最后用檢測(cè)算法對(duì)測(cè)試集數(shù)據(jù)進(jìn)行檢測(cè)。

2.3 增強(qiáng)的基于GCA的入侵檢測(cè)算法

本文提出的增強(qiáng)的基于 GCA的入侵檢測(cè)算法主要由GCA聚類(lèi)、合并算法、標(biāo)記算法與檢測(cè)入侵四部分組成。GCA聚類(lèi)在前面已有闡述，這里將后面三個(gè)部分作個(gè)簡(jiǎn)單的描述。

2.3.1 合并算法

第三步：查找出最小差異度Spq對(duì)應(yīng)的那兩個(gè)簇Cp與

第四步：計(jì)算出Cp、Cq、Cp∪Cq的整體相似度

第五步：若ovs(Cp∪Cq)≤ovs(CP)或者ovs(Cp∪Cq)≤ovs(Cq)，則合并簇Cp與Cq，計(jì)算新的合并簇Cp∪Cq的數(shù)值屬性中心與分類(lèi)屬性頻度，更新聚類(lèi)差異度，轉(zhuǎn)到第二步；否則，在差異度排序序列中查找出Spq后繼的那個(gè)差異度Spq+1，并找出對(duì)應(yīng)的那兩個(gè)簇Cg與Ch(1≤g≤k,1≤h≤k)，轉(zhuǎn)到第四步；若差異度Spq已經(jīng)是排序序列的最后一個(gè)，則算法結(jié)束。

2.3.2 標(biāo)記算法

根據(jù)文獻(xiàn)[4]定義的大簇和小簇的概念，再依據(jù)數(shù)據(jù)集中正常的數(shù)據(jù)數(shù)量要遠(yuǎn)大于異常數(shù)據(jù)的數(shù)據(jù)量的假設(shè)，本文給出了如下標(biāo)記算法：

（1）計(jì)算各簇Ci的成員個(gè)數(shù)，其中i=1～k，調(diào)用Quick排序算法將按降序排列。

（2）設(shè)置參數(shù)α的值。

2.3.3 檢測(cè)算法

檢測(cè)算法主要分為兩步，第一步，計(jì)算待檢測(cè)的數(shù)據(jù)包與訓(xùn)練過(guò)程中建立的所有簇之間的距離。并找出最小距離。第二步，若最小距離大于R，則判定該數(shù)據(jù)包為未知攻擊，其中 R為新的簇半徑(通常利用聚類(lèi)結(jié)果計(jì)算出所有數(shù)據(jù)點(diǎn)到所有簇的距離的平均值，將該平均值設(shè)為新的簇半徑R)，否則找出待檢測(cè)的數(shù)據(jù)包與訓(xùn)練建立的簇之間的距離最小的那個(gè)簇所屬的標(biāo)記，若標(biāo)記為正常，則待檢測(cè)的數(shù)據(jù)包是正常數(shù)據(jù)，若標(biāo)記為異常，則待檢測(cè)的數(shù)據(jù)包是異常數(shù)據(jù)。

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

使用KDDCUP99 15%的子集來(lái)測(cè)試算法的性能，將這個(gè)子集隨機(jī)的分為P1，P2兩個(gè)子集，其中P1含487052條記錄(normal占 96.2%)，P2 含 247948 條記錄(normal占 97.8%)，其中 P2中包含 P1中沒(méi)有出現(xiàn)過(guò)的 loadmodule、perl、warezmaster等攻擊類(lèi)型。用P1作訓(xùn)練集，P2做測(cè)試集進(jìn)行檢測(cè)，實(shí)驗(yàn)結(jié)果表明，增強(qiáng)的基于 GCA的入侵檢測(cè)方法與文獻(xiàn)[2]總的檢測(cè)率相當(dāng)，誤報(bào)率下降明顯，并對(duì)未知攻擊的檢測(cè)率有所提高。表1是文獻(xiàn)[2]與本文方法檢測(cè)結(jié)果對(duì)照表。

表1 文獻(xiàn)[2]與增強(qiáng)的基于GCA的入侵檢測(cè)方法檢測(cè)結(jié)果對(duì)照表

4 總結(jié)

這種增強(qiáng)的基于 GCA的入侵檢測(cè)方法在降低誤報(bào)率等檢測(cè)性能有了相當(dāng)大的提高，而且該檢測(cè)模型是可以增量更新的，便于擴(kuò)展。但是閾值的確定要依靠抽樣計(jì)算獲得，雖然給出了確定閾值的方法，但比較麻煩，還有合并算法中整體相似性度量的準(zhǔn)確性都需要我們進(jìn)一步的探索。

[1] Kim,Bentley.Immune Memory and Gene Library Evolution in the Dynamic Clonal Selection Algorithm[J].Journal of Genetic Programming and Evolvable Machines.2004.

[2] 蔣盛益,李慶華.基于引力的入侵檢測(cè)方法[J].系統(tǒng)仿真學(xué)報(bào).2005.

[3] 曹元大.入侵檢測(cè)技術(shù)[M]第 1版.北京：人民郵電出版社.2007.

[4] Zengyou He,Xiaofei Xu,Shengchun Deng.Discovering Cluster Based Local Outliers[J].Pattern Recognition Letters. 2003.

[5] Minho Kim,R.S.Ramakrishna.Projected Clustering for Categorical Datasets[J].Pattern Recognition Letters.2006.