何發(fā)鎂,馬慧珍,王旭仁,馮安然

(1.北京理工大學(xué) 圖書館,北京 100081; 2.中國科學(xué)院信息工程研究所 中國科學(xué)院網(wǎng)絡(luò)測評技術(shù)重點(diǎn)實(shí)驗室,北京 100093;3.首都師范大學(xué) 信息工程學(xué)院,北京 100048)

0 概述

入侵檢測主要分為誤用檢測和異常檢測兩類。誤用檢測通過與已知攻擊進(jìn)行對比來識別異?；驖撛诘男袨?其對已知的攻擊具有很好的檢測效果,但是難以檢測新的或不常見的入侵。異常入侵檢測采用機(jī)器學(xué)習(xí)和統(tǒng)計學(xué)的方法,對網(wǎng)絡(luò)傳感器收集來的信息或?qū)徲嬋罩具M(jìn)行分析處理,在檢測出異常行為或惡意攻擊時能及時分類處理以達(dá)到保障網(wǎng)絡(luò)空間安全的目的。隨著信息傳播速度的不斷提升,網(wǎng)絡(luò)傳輸產(chǎn)生了大量數(shù)據(jù),如果不能及時處理這些數(shù)據(jù),將會給網(wǎng)絡(luò)空間安全帶來未知的威脅。網(wǎng)絡(luò)傳感器收集信息得來的數(shù)據(jù)擁有眾多屬性,如何在眾多屬性中提取出有用信息以提高檢測率,成為亟需解決的問題。

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

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

1 相關(guān)算法

1.1 K-means算法

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

(1)

(2)

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

算法1K-means算法

輸入簇的數(shù)目k,包含m個對象的數(shù)據(jù)集S

輸出k個簇的集合

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

repeat

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

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

until準(zhǔn)則函數(shù)收斂

1.2 決策樹

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

(3)

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

(4)

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

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

(5)

特征fk的信息增益比為:

(6)

2 基于特征分組聚類的入侵檢測系統(tǒng)

2.1 入侵檢測模型

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

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

2.2 特征分組策略

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

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

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

2.3 特征分組聚類算法KBFG

假設(shè)數(shù)據(jù)集S={x1,x2,…,xm},其特征集合為F={f1,f2,…,fn},每條數(shù)據(jù)由n個特征組成?，F(xiàn)將特征集合F依據(jù)某種標(biāo)準(zhǔn)進(jìn)行分組,分為l個屬性集,l

算法2KBFG算法

輸入樣本集S,特征分組數(shù)據(jù)集St對應(yīng)的聚類數(shù)目kt,1≤t≤l

輸出特征分組數(shù)據(jù)集的簇集合C={C1,C2,…,Ct},St對應(yīng)的簇集合Ct,1≤t≤l

for i=1∶l

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

end

for i=1∶l

repeat

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

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

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

until準(zhǔn)則函數(shù)收斂

end

使用KBFG算法對每個樣本數(shù)據(jù)按照分組進(jìn)行聚類,執(zhí)行完畢后,針對樣本集S內(nèi)的樣本數(shù)據(jù)x,依次將x中第i個分組的ni個特征值由該分組聚類后的標(biāo)簽λ所替代,1≤i≤l。此時樣本x的特征值由原來的n個變?yōu)閘個,實(shí)現(xiàn)了低層高維數(shù)據(jù)向高層抽象數(shù)據(jù)的轉(zhuǎn)化。有3種特殊情況,具體如下:

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

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

3)當(dāng)l<

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

3 實(shí)驗數(shù)據(jù)特征分組與評估標(biāo)準(zhǔn)

3.1 數(shù)據(jù)集及特征分組選擇

本文使用 kddcup99 數(shù)據(jù)集[20]進(jìn)行實(shí)驗。該數(shù)據(jù)集的每條數(shù)據(jù)由 41 個屬性和1個類標(biāo)簽組成,數(shù)據(jù)記錄格式如下:

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 連接的內(nèi)容特征(第10個～第22個特征),基于時間的網(wǎng)絡(luò)流量統(tǒng)計特征(第23個～第31個特征),基于主機(jī)的網(wǎng)絡(luò)流量統(tǒng)計特征(第32個～第41個特征)。

3.2 數(shù)據(jù)預(yù)處理

將數(shù)據(jù)集中的標(biāo)稱屬性值進(jìn)行數(shù)值化[21]。假設(shè)一個標(biāo)稱屬性包含m個值,則將該標(biāo)稱屬性值變?yōu)閙維向量。例如,數(shù)據(jù)集“protocol type”的特征值包括tcp、udp、icmp,則將特征值變?yōu)?1,0,0)。

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

(7)

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

3.3 數(shù)據(jù)集劃分

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

表1 實(shí)驗數(shù)據(jù)分布Table 1 Distribution of experimental data

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

表2 攻擊數(shù)據(jù)分布Table 2 Distribution of attacking data

3.4 評估方法

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

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

4 實(shí)驗結(jié)果與分析

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

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

圖2 數(shù)據(jù)屬性分組示例Fig.2 Example of data attributes grouping

4.1 KBFG分組聚類參數(shù)確定

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

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

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

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

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

當(dāng)k=10時,KBFG降維前后數(shù)據(jù)量對比如表3所示。從表3可以看出,降維后,訓(xùn)練集數(shù)據(jù)量約縮減87.9%,測試集數(shù)據(jù)量約縮減85.8%,即KBFG方法能夠大幅降低網(wǎng)絡(luò)數(shù)據(jù)量。

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

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

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

表4 訓(xùn)練集抽樣數(shù)據(jù)分布Table 4 Sample data distribution of training sets

表5 測試集抽樣數(shù)據(jù)分布Table 5 Sample data distribution of test sets

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

4.3 結(jié)果對比

通過以上實(shí)驗可知,當(dāng)k=10時,模型效果最佳。表7、表8是k=10時本文KBFG-C4.5模型與其他模型的對比結(jié)果。從表7可知,KBFG-C4.5模型的DR為99.73%,比M-LHSVM-ELM高出4.56個百分點(diǎn)、比NFC高出4.53個百分點(diǎn)、比C4.5高出8.54個百分點(diǎn),而KBFG-C4.5的FPR=0,其他3種模型的FPR雖然很低,但仍然高于KBFG-C4.5。從表8可知,KBFG-C4.5模型對于Normal、DoS、U2R、Probe的檢測率均最優(yōu),分別為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 結(jié)束語

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