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

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

0 引言

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

1 基于引力的聚類方法GCA

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

（1）初始時，簇集合為空，讀入一個新的對象；

（2）以這個對象構造一個新簇；

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

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

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

（6）保存每個簇的摘要信息及引力閾值r，結束。

2 增強的基于GCA的入侵檢測方法

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

圖1 簇的大小與異常簇的判定的關系

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

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

2.2 增強的基于 GCA的入侵檢測方法的主要思想

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

2.3 增強的基于GCA的入侵檢測算法

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

2.3.1 合并算法

第三步：查找出最小差異度Spq對應的那兩個簇Cp與

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

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

2.3.2 標記算法

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

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

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

2.3.3 檢測算法

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

3 實驗結果

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

表1 文獻[2]與增強的基于GCA的入侵檢測方法檢測結果對照表

4 總結

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

[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)仿真學報.2005.

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