一種增強(qiáng)的基于GCA的入侵檢測方法

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

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

0 引言

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

1 基于引力的聚類方法GCA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1 合并算法

第三步：查找出最小差異度Spq對應(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ù)值屬性中心與分類屬性頻度，更新聚類差異度，轉(zhuǎn)到第二步；否則，在差異度排序序列中查找出Spq后繼的那個(gè)差異度Spq+1，并找出對應(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 檢測算法

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

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

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

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

4 總結(jié)

這種增強(qiáng)的基于 GCA的入侵檢測方法在降低誤報(bào)率等檢測性能有了相當(dāng)大的提高，而且該檢測模型是可以增量更新的，便于擴(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] 蔣盛益,李慶華.基于引力的入侵檢測方法[J].系統(tǒng)仿真學(xué)報(bào).2005.

[3] 曹元大.入侵檢測技術(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.