基于特征分組聚類的異常入侵檢測系統研究

何發鎂,馬慧珍,王旭仁,馮安然

(1.北京理工大學 圖書館,北京 100081; 2.中國科學院信息工程研究所 中國科學院網絡測評技術重點實驗室,北京 100093;3.首都師范大學 信息工程學院,北京 100048)

0 概述

入侵檢測主要分為誤用檢測和異常檢測兩類。誤用檢測通過與已知攻擊進行對比來識別異常或潛在的行為,其對已知的攻擊具有很好的檢測效果,但是難以檢測新的或不常見的入侵。異常入侵檢測采用機器學習和統計學的方法,對網絡傳感器收集來的信息或審計日志進行分析處理,在檢測出異常行為或惡意攻擊時能及時分類處理以達到保障網絡空間安全的目的。隨著信息傳播速度的不斷提升,網絡傳輸產生了大量數據,如果不能及時處理這些數據,將會給網絡空間安全帶來未知的威脅。網絡傳感器收集信息得來的數據擁有眾多屬性,如何在眾多屬性中提取出有用信息以提高檢測率,成為亟需解決的問題。

聚類分析是數據挖掘、模式識別等領域的重要研究內容之一,其將數據集中相似的樣本盡可能劃分為相同的簇,將相異的樣本盡可能劃分為不同的簇。在入侵檢測研究領域,K-means聚類被廣泛應用[1-3],k的取值與初始聚類中心的選擇對聚類結果具有重大影響。文獻[4]通過設置簇半徑L來解決k的取值和初始聚類中心選擇問題,但是L的取值又成了一個新的問題。文獻[5]通過改進Seeded K-means算法中種子集初始聚類中心的選擇來嘗試解決由此產生的隨機性和盲目性問題,但其并未取得良好效果,原因是種子集本身存在隨機性和盲目性。文獻[6]通過改進K-means算法來解決初始聚類中心選擇問題,但其相當于運行2次K-means算法,效率較低。文獻[7-8]通過K-means聚類與其他算法相組合的方式,來解決由于k值與初始聚類中心選擇導致的聚類結果不穩定問題。文獻[9]提出K-means與ID3決策樹相結合的方法,其有效地避免了K-means聚類存在的強制分配與類優勢問題。文獻[10]使用Self-Organizing Map對數據進行初步聚類,得到聚類中心并作為 K-means的初始聚類中心,然后重新定義簇的邊界。文獻[11-12]使用K-means將數據聚為k個簇,然后利用Naive Bayes分別對每個簇進行分類處理。文獻[13]采用EM(Expectation Maximization)算法獲得簇數目k,然后使用K-means將數據聚成k個簇,該方法解決了k過大過小的問題。文獻[14]使用K-means將數據聚成k個簇,對每個簇的數據利用Fuzzy Neural Network進行處理,然后每個數據用k+1維的向量表示,其中,第k+1個數值由簇中數據的隸屬度表示,從而達到降維的目的,隨后采用SVM進行分類處理。文獻[15]提出M-LHSVM-ELM(Multi-Level Hybrid Support Vector Machine and Extreme Learning Machine)算法,其將數據聚成k個簇,用k個聚類中心點代替原來的數據,對新得到的數據采用多層SVM和ELM混合的方法進行分類處理,從而縮短模型訓練的時間。文獻[16]提出神經模糊分類(Neural Fuzzy Classifier,NFC)方法,該方法融合了神經網絡和模糊理論。

上述研究通過改進K-means算法以及組合算法,來避免由于k值和初始聚類中心選擇導致的聚類結果不穩定問題,但是由于數據分布不均勻,在數據處理過程中未能識別出數據中存在的微小差異,導致對數據量少的攻擊的檢測率不高。文獻[17]通過特征取值分組來更好地描述同類表情中不同特征取值作用間的差異。本文提出一種基于K-means的特征分組聚類方法,以描述網絡數據中存在的差異并降低數據維度。初始聚類中心選擇不穩定導致的聚類效果不佳和依賴問題由C4.5算法來解決,從而提高對異常入侵和數據量少的攻擊的檢測率。

1 相關算法

1.1 K-means算法

設訓練數據集S是由m個數據對象組成的集合,每個對象由n個屬性組成。將S分成k個不相交的簇C1,C2,…,Ck,其中,ci(i=1,2,…,k)為簇Ci數據的平均值,即聚類中心。在本文中,K-means算法對于數據對象之間的相似度度量采用歐氏距離,歐式距離越小,相似度越大;反之,歐式距離越大,相似度越小。 歐氏距離的計算方法如式(1)所示。K-means算法常采用誤差和準則函數作為聚類準則函數,其定義如式(2)所示:

(1)

(2)

其中,mi是簇Ci中的數據對象個數,xi是簇Ci中的數據對象,J是所有數據對象的誤差和。聚類準則函數的作用是盡可能使簇內數據相似度最大,簇間數據相似度最小,從而使聚類算法獲得最佳的聚類結果。K-means算法的處理流程如算法1所示。

算法1K-means算法

輸入簇的數目k,包含m個對象的數據集S

輸出k個簇的集合

從S中任意選擇k個對象作為初始簇中心;

repeat

根據式(1)計算d,將每個對象分配到最相似的簇;

更新簇均值,重新計算每個簇的均值ci;

until準則函數收斂

1.2 決策樹

決策樹在分類問題中構建的模型以樹形結構呈現。文獻[18]將信息論中的熵引入決策樹研究領域,利用熵計算數據對象各特征對類標簽的影響程度,以此尋找最優特征構建決策樹。C4.5使用信息增益比作為構建決策樹過程中子節點選擇時最優屬性劃分的評估標準[19]。設訓練數據集為S,m為總的訓練樣本個數,F={f1,f2,…,fn}為特征集合,每個數據由n個特征組成。假設有p個類,第i個類包含mi個訓練樣本。訓練樣本集S的經驗熵為:

(3)

特征fk(k=1,2,…,n)有v個不同的取值{ρ1,ρ2,…,ρv},根據特征fk的取值將樣本集S分為v個子集{S1,S2,…,Sv},Sj是特征fk取值為ρj的樣本集合,特征fk的經驗條件熵為:

(4)

其中,mij是Sj第i類的樣本個數。特征fk的信息增益為:

Gain(fk)=H(m1,m2,…,mp)-E(fk)

(5)

特征fk的信息增益比為:

(6)

2 基于特征分組聚類的入侵檢測系統

2.1 入侵檢測模型

本文將基于特征分組聚類的K-means算法和決策樹C4.5算法相結合,提出一種KBFG-C4.5(K-means Based on Feature Grouping Plus C4.5)入侵檢測系統,以對數據進行分析處理。其中,基于K-means算法的特征分組聚類記為KBFG。首先對數據進行預處理,按照一定標準對特征實現分組;然后使用K-means算法對每個分組內的數據進行聚類,則分組內的所有特征由聚類后的標簽所替代,實現了低層高維數據向高層抽象數據的轉化,這樣可以更好地區分出數據相似特征中存在的微小差異,同時降低維度,方便數據進一步處理;接著對高層抽象數據使用C4.5算法訓練分類模型;最后進行測試,驗證模型的有效性。本文KBFG-C4.5入侵檢測系統的具體流程如圖1所示。

圖1 KBFG-C4.5入侵檢測系統模型Fig.1 KBFG-C4.5 intrusion detection system model

2.2 特征分組策略

相似特征進行較好的分組,會更好地提取高層抽象數據,提高分類模型的準確率;反之,不合適的特征分組會提高模型訓練的時間復雜度,降低模型的準確率。本文提出2種特征分組方式:

1)基于先驗知識的特征分組方法,例如將圖片的特征按照顏色、形狀和光亮度進行分組。

2)均勻分組策略,例如將一個n維的特征分成l組,則每組包含?n/l」個特征。

2.3 特征分組聚類算法KBFG

假設數據集S={x1,x2,…,xm},其特征集合為F={f1,f2,…,fn},每條數據由n個特征組成?，F將特征集合F依據某種標準進行分組,分為l個屬性集,l

算法2KBFG算法

輸入樣本集S,特征分組數據集St對應的聚類數目kt,1≤t≤l

輸出特征分組數據集的簇集合C={C1,C2,…,Ct},St對應的簇集合Ct,1≤t≤l

for i=1∶l

從Si中任意選擇ki個樣本作為初始簇聚類中心{ci,1,ci,2,…,ci,ki};

end

for i=1∶l

repeat

用ni表示第i個分組的特征數目,將xj分組數據(xj,1,xj,2,…,xj,ni)根據式(1)計算d

將(xj,1,xj,2,…,xj,ni)標記為最小的d所對應的類別λ,更新簇集合Ci,λ=Ci,λ∪{( xj,1, xj,2,…,xj,ni)}

重新計算簇Ci,λ的聚類中心:

until準則函數收斂

end

使用KBFG算法對每個樣本數據按照分組進行聚類,執行完畢后,針對樣本集S內的樣本數據x,依次將x中第i個分組的ni個特征值由該分組聚類后的標簽λ所替代,1≤i≤l。此時樣本x的特征值由原來的n個變為l個,實現了低層高維數據向高層抽象數據的轉化。有3種特殊情況,具體如下:

1)當l=1時,KBFG算法退化為K-means算法,KBFG-C4.5模型不再適用。

2)當l=n時,KBFG算法對樣本集S內的樣本數據x的所有特征進行聚類處理,雖然沒有降低特征的維數,但是每個特征的特征值進行了聚類抽象,實現了特征值從低層到高層數據的轉換,KBFG-C4.5模型適用。

3)當l<

在KBFG算法中,特征分組數據集St對應的聚類數目kt(1≤t≤l)的值需要通過反復實驗,根據KBFG-C4.5模型檢測評估效果來確定。

3 實驗數據特征分組與評估標準

3.1 數據集及特征分組選擇

本文使用 kddcup99 數據集[20]進行實驗。該數據集的每條數據由 41 個屬性和1個類標簽組成,數據記錄格式如下:

0,udp,private,SF,105,146,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1,0,0,255,254,1,0.01,0,0,0,0,0,0,Normal

基于先驗知識將特征分為 4 個組:TCP 連接的基本特征(第1個～第9個特征),TCP 連接的內容特征(第10個～第22個特征),基于時間的網絡流量統計特征(第23個～第31個特征),基于主機的網絡流量統計特征(第32個～第41個特征)。

3.2 數據預處理

將數據集中的標稱屬性值進行數值化[21]。假設一個標稱屬性包含m個值,則將該標稱屬性值變為m維向量。例如,數據集“protocol type”的特征值包括tcp、udp、icmp,則將特征值變為(1,0,0)。

數據中各特征的取值范圍不同,其中,取值較大的特征將會降低取值較小特征在計算過程中所起的作用,即“大數吃小數”現象。因此,本文對數據進行歸一化處理。將特征的取值轉化為0到1區間內的值,如式(7)所示:

(7)

其中,Nmin和Nmax分別為特征值的最小值和最大值。

3.3 數據集劃分

kddcup99數據集包括訓練與測試數據集,總共包含38種攻擊,分為4種主要類型:拒絕服務攻擊(DoS),遠程攻擊(R2L),本地用戶非法提升權限的攻擊(U2R),網絡刺探(Probe),其余為正常網絡連接數據(Normal)。數據集的數據分布如表1所示。

表1 實驗數據分布Table 1 Distribution of experimental data

本文實驗使用 10%的訓練數據,共494 021個連接數據,其中,包含97 278個正常連接(Normal),攻擊連接數據包含22種攻擊類型;10%的測試集包含311 029個連接數據,Normal有60 593個,攻擊連接數據包含 14種在訓練數據集中不存在的新攻擊類型。數據集中攻擊數據分布如表2所示。

表2 攻擊數據分布Table 2 Distribution of attacking data

3.4 評估方法

為了衡量KBFG-C4.5方法的分類效果,本文采用 DR(Detection Rate)、FPR(False Positive Rate)作為評估標準進行分析。將實驗數據分為正常類和攻擊類,一個性能良好的入侵檢測系統將具有高DR值和低FPR 值。DR和FPR的計算公式分別如下:

其中,TP表示將攻擊類預測為攻擊類的數量,FN表示將攻擊類預測為正常類的數量,FP表示將正常類預測為攻擊類的數量,TN表示將正常類預測為正常類的數量。

4 實驗結果與分析

本文仿真使用一臺處理器為Intel?CoreTMi7-4790 CPU @ 3.60 GHz 、內存8.00 GB的64位Windows 7旗艦版的臺式機,用weka工具輔助。

首先對實驗數據進行預處理,預處理包含2個部分,即標稱屬性值數值化和所有數據歸一化;然后依據數據的特征類型將數據分離成4個新的數據集,即l=4,如圖2所示;接著對處理后的數據使用算法2進行降維,將數據轉化為圖2中用簇號表示的一條數據,如圖中C1,6表示該樣本第一個特征分組數據經過KBFG算法被聚到簇6中,以此類推;最后使用C4.5算法對高層抽象之后的數據進行分類,輸出結果。

圖2 數據屬性分組示例Fig.2 Example of data attributes grouping

4.1 KBFG分組聚類參數確定

在KBFG算法中,各分組的聚類數目kt(1≤t≤l)的取值由人工確定。通過反復實驗,約定所有分組的聚類數目相等,即k1=k2=…=kt=…=kl=k。當k=5,6,7,8,9,10時,圖3所示為KBFG-C4.5模型對攻擊類連接數據的檢測率情況。從圖3可以看出,當k=10時KBFG-C4.5模型檢測率DDR=0.997 3,對比k=9時降低 0.003 0。當k=5,6,7,8,9,10時,圖4所示為KBFG-C4.5模型對5種連接數據的檢測率情況。從圖4可以看出,當k=10時,R2L的DDR=0.330 9,對比k=9時降低約0.030 0,當k=10時,DoS的DDR=0.999 3,對比k=9時提高約0.030 0。Normal、U2R、Probe 的DDR在k=10、k=9時均無明顯變化。

圖3 KBFG-C4.5模型對攻擊類連接數據的檢測率情況Fig.3 Detection rate of KBFG-C4.5 model for attackingconnection data

圖4 KBFG-C4.5模型對5種連接數據的檢測率情況Fig.4 Detection rate of KBFG-C4.5 model for fiveconnection data

當k=5,6,7,8,9,10時,圖5所示為KBFG-C4.5模型對正常類連接數據的誤檢率情況。從圖5可以看出,當k=10時,誤檢率FFPR=0。綜合上述實驗結果,本文最終取k=10。

圖5 KBFG-C4.5模型對正常類連接數據的誤檢率情況Fig.5 False detection rate of KBFG-C4.5 model for normalconnection data

當k=10時,KBFG降維前后數據量對比如表3所示。從表3可以看出,降維后,訓練集數據量約縮減87.9%,測試集數據量約縮減85.8%,即KBFG方法能夠大幅降低網絡數據量。

表3 KBFG降維前后數據量對比Table 3 Comparison of data volume before and after KBFG dimensionality reduction MB

4.2 KBFG-C4.5模型檢測能力測試

4.1節的實驗結果證實當k=10時KBFG-C4.5模型具有較好的檢測效果。為更進一步地證明KBFG-C4.5模型的有效性,從訓練集與測試集中抽取部分數據進行實驗,數據詳情見表4、表5,從中可以看出,訓練集與測試集中的攻擊類型僅有“ipsweep”一類相同,其余均不同。此次抽樣實驗將數據分為五大類,實驗參數k=10,抽樣實驗結果如表6所示。由表6可以看出,Normal的檢測準確率達到0.997,DoS、Probe、R2L、U2R的檢測準確率均達到1.000,說明KBFG-C4.5模型可以檢測出新的攻擊類且能夠正確分類。

表4 訓練集抽樣數據分布Table 4 Sample data distribution of training sets

表5 測試集抽樣數據分布Table 5 Sample data distribution of test sets

表6 抽樣實驗混淆矩陣Table 6 Confusion matrix of sampling experiments

4.3 結果對比

通過以上實驗可知,當k=10時,模型效果最佳。表7、表8是k=10時本文KBFG-C4.5模型與其他模型的對比結果。從表7可知,KBFG-C4.5模型的DR為99.73%,比M-LHSVM-ELM高出4.56個百分點、比NFC高出4.53個百分點、比C4.5高出8.54個百分點,而KBFG-C4.5的FPR=0,其他3種模型的FPR雖然很低,但仍然高于KBFG-C4.5。從表8可知,KBFG-C4.5模型對于Normal、DoS、U2R、Probe的檢測率均最優,分別為100%、99.93%、24.12%、100%,均高于其他3種模型。通過以上分析可知,KBFG-C4.5模型由于使用了分組聚類的思想,能夠在入侵檢測問題上取得良好效果。

表7 4種模型檢測率與誤檢率對比Table 7 Comparison of detection rates and false detection rates of four models %

表8 4種模型對各類攻擊的檢測率對比Table 8 Comparison of detection rates of four models for various attacks %

5 結束語

本文提出一種基于特征分組聚類的KBFG-C4.5算法,以對網絡數據進行檢測分析。基于分組聚類思想的KBFG算法能夠弱化K-means算法初始聚類中心選擇對異常檢測效果的影響,較大限度地降低數據維度并提高入侵檢測率。實驗結果表明,KBFG-C4.5算法具有較高的檢測率與較低的誤檢率。但是,本文算法對于U2R、R2L攻擊的檢測率未取得很大提升,下一步將分析多種特征分組策略對入侵檢測模型的影響并構建一個性能更優的決策函數,以提高模型對U2R、R2L攻擊的檢測率。