基于特征選擇的兩級混合入侵檢測方法

江澤濤，周譚盛子+，胡 碩，時 晨

(1.桂林電子科技大學 計算機與信息安全學院 廣西圖像圖形處理智能處理高校重點實驗室， 廣西 桂林 541004；2.桂林電子科技大學 計算機與信息安全學院 廣西可信軟件重點 實驗室，廣西 桂林 541004；3.南昌航空大學 信息工程學院，江西 南昌 330063)

0 引 言

隨著科學技術的發展，互聯網已經滲透到人們生活及工作的各方面。網絡的快速在提供便利的同時也誘發了一系列問題，如何保障用戶數據信息的安全性成為當下亟待研究和解決的重點。入侵檢測作為構成網絡系統和主動防御體系的重要理論和手段而備受關注。

近年來，機器學習在入侵檢測中得到了廣泛的應用。閆義涵[1]為了克服傳統的K-Means算法在很大程度上依賴于k值的問題，提出了一種改進的K-Means算法，通過層次聚類思想動態地確定k值，使用基于聚類中心位置變化的方法進行入侵檢測。歐陽麗[2]針對當前隨機森林算法在檢測精度方面的不足，提出了基于果蠅優化的和聚類優化的隨機森林算法，利用較少的基分類器改善了算法的精度。Guo等[3]將異常檢測和誤用檢測進行級聯，并引入了K近鄰算法，能有效識別未知攻擊類型，有效降低了算法的誤報率。隨著深度學習在圖像處理方面的廣泛應用，其有效性也越來越被入侵檢測相關研究人員認可。張玉清等[4]總結了近年來深度學習在網絡空間安全上的應用，并從分類算法、特征提取和學習效果等方面進行了分析，突出了深度學習在入侵檢測技術應用上的問題與機遇。張思聰等[5]為了進一步提高檢測準確率，提出了一種基于深度卷積神經網絡(deep convolutional neural network，DCNN)的入侵檢測方法，通過學習有效特征并結合Softmax分類器得到最終分類結果。此外，基于特征選擇的算法的研究也越來越成熟。Akashdeep等[6]利用信息增益和相關性作為特征約簡的依據，以人工神經網絡(ANN)作為分類器，減少了訓練時間。Nathan等[7]提出了非對稱深度自編碼器，對不含標簽的數據采用無監督學習的方法獲得了源數據中具有代表性的特征進而提高了入侵檢測算法的分類精度。以上的成果雖然都在一定程度上取得了較好檢測性能，但對未知類型的攻擊檢測仍然存在漏報情況。

針對上述情況，本文提出了一種以特征選擇為基礎的混合入侵檢測方法。與其它方法相比，其創新之處在于：①結合Fisher分和超圖屬性提出了一種新的特征選擇方法；②提出了一種改進的K-Means聚類方法，構建了一種新的兩級混合入侵檢測模型。實驗結果表明，本文所提方法達到了更高的準確率和檢測率，實現了更低的誤報率。

1 相關知識

1.1 Fisher分

已有的很多入侵檢測方法都有以下的不足之處：算法的性能受數據傾斜和分布的影響較大，同時在計算過程中會有很多冗余的特征維度，這都會增加算法的綜合復雜度，同時也會使算法的檢測性能受到了不同程度的影響。特征選擇則是在所有原始維度范圍對眾多特征屬性進行統一處理，在結果中篩選掉那些相關性不高的冗余特征，并在此基礎上完成對原始數據的降維擇優，擇出對原始數據表征效果代表性最佳的最小特征子集[8]。特征選擇可分為過濾式、包裹式和嵌入式3種。本文采用獨立于分類器的過濾式特征選擇方法，這類方法通常選擇和類別相關度大的特征子集。過濾式特征選擇方法常用于對原始數據的預處理，該類方法能夠較好過濾非關鍵性特征，盡可能的保留相關性較高的主體結構特征，最終降低特征集屬性的維度。Fisher分[9]被看作是過濾模式中一種重要概念，其主要處理目標是在最大化不同類別下的樣本之間的距離的同時最小化同一種類別中的樣本之間的距離，而Fisher分的計算取值則是計算兩者的比值。由此可以得出特征的Fisher分值與特征的分類決策能力之間呈正相關的關系。以FSi表示第i維特征的Fisher分值，則Fisher分的計算公式如下所示

(1)

1.2 超 圖

超圖作為圖論中的重要延伸概念，其相比其它類簡單圖模型，能夠表征更加復雜的多元關系以及實體之間的復雜交互關系。在入侵檢測方法中可以使用超圖模型較好表示數據中各實體對象之間的所屬關系[10]。對于超圖H={V,E}， 其中，頂點V={v1,v2,…,vm}， 超邊E={E1，E2,…,En}。 超圖結構如圖1所示。

圖1 超圖結構

對于給定的一個超圖H={V,E}， 若E={E1,E2,E3}，V={v1,v2,v3,v4,v5,v6,v7,v8}， 其中E1={v1,v2,v3,v4}，E2={v3,v4,v5,v6}，E3={v3,v7,v8}， 則超邊E1與E2的交集為 {v3,v4}， 超邊E1、E2與E3的交集為 {v3}。 若一個超圖H存在Helly屬性，其中，H={V,E}， 頂點V={v1,v2,…,vm}， 超邊E={E1,E2,…,En}， 則需要滿足Ei∩Ej≠?(i≠j且i,j∈n)， 如圖2所示。

圖2 超圖Helly屬性

圖2(a)表示任意一對超邊都有相同的交集，在超圖H={V,E} 中,E={E1,E2,E3}，V={v1,v2,v3,v4,v5,v6,v7}，E1={v1,v2,v3}，E2={v3,v4,v5}，E3={v3,v6,v7}， 利用Helly屬性可以得到頂點v3是超邊 {E1,E2,E3} 的共同交點，即E1∩E2={v3}，E1∩E3={v3}，E2∩E3={v3}。

圖2(b)是含三角形的超圖，在超圖H={V,E}，E={E1,E2,E3}，V={v1,v2,v3,v4,v5,v6}，E1={v1,v2,v3}，E2={v3,v4,v5}，E3={v1,v5,v6}，E1∩E2={v3}，E1∩E3={v1}，E2∩E3={v5}， 即 {v3}∩{v1}∩{v5}=?。如果圖中任意一對超邊之間不存在任何相同交集，則此圖不具有Helly屬性。

1.3 隨機森林算法

隨機森林是由多棵樹型分類器組成的集合，最終分類結果由基礎樹型分類器投票產生，其基礎樹型分類器通常采用沒有剪枝的CART決策樹。本文采用基于信息增益的隨機森林算法。在過濾式特征選擇方法中使用基于信息增益理論的方法度量每一個特征維度對檢測分類的貢獻度大小，將貢獻度較低的特征作為冗余特征去除掉。與之相對應的是，誤分類的概率與特征的信息增益之間是一個樸素的負相關關系。

樣本S的熵可通過下列公式計算

(2)

其中，S為數據集，K為類別數，Si為第k類樣本數， |S| 為總樣本數。

特征屬性A對數據集S的條件熵公式如下所示

(3)

對S進行劃分，得到n個子集，劃分依據為A的取值，劃分后的樣本子集為S1,S2,…,Sn， |Si| 為第i個子集Si的樣本數， |S| 為總樣本數，K為類別數， |Sik|為子集Si中類Ck的樣本數。

特征屬性A的信息增益公式如下所示

IG(A)=H(S)-H(S|A)

(4)

基于信息增益的隨機森林的算法主要分為6個主要步驟：

(1)對包含K個決策樹的隨機森林中的每一棵決策樹進行n次有放回的隨機抽取，得到的抽取樣本記為D={(x1,y1),(x2,y2),…,(xn,yn)}，xi表示第i個樣本的特征集，yi表示第i個樣本的所屬類，隨后從n個樣本對中隨機選取j個樣本構成特征子集A(a1,a2,…,aj)；

(2)對決策樹中樣本進行多輪分類，如果分類結果相同就結束此輪分類計算，并將當前分類結果作為此次分類的最終類別，否則執行步驟(3)；

(3)采用信息增益最大的屬性進行劃分，信息增益最大的屬性記為ai， 隨后將ai從特征子集A中刪除；

(4)對每個子節點分別執行步驟(2)并循環重復當前步驟；

(5)若全部特征屬性都用于劃分時，最后節點處的樣本屬于不同的類別，則此時當前節點的類別為該節點中的數量最多的類別；

(6)在測試階段，利用K棵決策樹分別對樣本進行分類，樣本的最終類別由所有決策樹投票決定。

由式(2)～式(4)可知，通過對樣本特征屬性的信息增益進行計算和篩選，決策樹能很好的區分屬于正常操作類別的數據和部分屬于非法攻擊操作數據，因此，基于信息增益的隨機森林算法對攻擊數據檢測率較高，但是此類方式的誤報率也處于較高水平，本文設計級聯分類器體系，并將此方法作為第一級分類器組件，期望能夠提高對部分異常數據的檢測率。

1.4 K均值(K-Means)算法

K-Means算法是典型的基于劃分的聚類方法，其目的在于將數據集劃分為若干個子集且分別代表一個類別。其核心步驟是對每個點計算到各個預定義的已知類別的中心位置的歐氏距離，并將此距離結果作為劃分其所屬類別的依據，并同步更新所屬類別的中心位置，重復上述步驟直至中心收斂為止。其中，兩個n維樣本xi與yj之間的歐式距離公式如下所示

(5)

(6)

其中， |Ck| 為第k類簇類的樣本數，xi為Ck中的樣本。

為了克服傳統K-Means算法初始聚類中心k值選取的隨機性，本文采用基于密集度的K-Means++算法，與傳統的K-Means++不同的之處在于：該方法引入了密度閾值的概念，以此來避免K-Means++算法在選取初始中心位置時的隨機現象，這樣就可以在決策初始聚類中心時受到更少來自部分離群孤立數據點的不利影響。

基于密集度的K-Means++算法的具體步驟如下：

(1)輸入聚類數k距離閾值ε和密集度閾值α；

(2)根據式(5)的定義計算k個距離較遠的樣本與其附近的α個不同樣本數據點之間的距離，如果能夠滿足d(xi,xj)≤ε， 則可將所選取的k個樣本作為初始中心位置，否則的話重復上述操作選取更遠的另外k個樣本。直到找到的k個樣本能夠滿足步驟(2)中介紹的式子；

(3)計算每個樣本到各個簇類中心的位置的歐氏距離并選擇距離最近的簇類，當前樣本隨后加入到此簇類中去，更新簇類中心位置；

(4)分類過程終止的條件是聚類中心趨于穩定，其它情況則重復流程(3)的操作。

聚類算法大都是以距離計算為核心思想的分類方法，其中基于密集度的K-Means++方法在入侵檢測問題中能夠有效將剩下的攻擊數據和正常數據分類到不同的簇類中去，從而就能夠提高分類器的全局檢測率且降低誤報率。

2 基于特征選擇的兩級混合入侵檢測方法

2.1 基于超圖的特征選擇方法

互聯網的迅速發展使得信息的存儲和處理變得異常困難，近年來，機器學習方法的注入為入侵檢測技術帶來了新的生命力，但是大數據的數據結構和數據類型更加多元和復雜，從而使得對數據的處理也更加復雜，而基于特征選擇思想的理論和方法就是想要從大量復雜冗余的海量數據中提取出具有更多實際意義的業務信息。通過刪除一些冗余和不相關的特征屬性選擇出最小特征子集用于表征原始數據。本文根據特征屬性對類別的區分程度，生成最小特征子集，從而實現特征擇優。利用Fisher分值可以從數值上直觀準確地對比不同的特征維度對分類能力的影響。另外，由于本文對入侵檢測數據集進行五分類研究，所以引入超圖著重分析滿足Helly屬性的特征。本文提出的方法，主要包括3個步驟：①對原訓練數據中的各個特征進行Fisher分值計算，并篩選掉對數據分類的影響不明顯的特征屬性；②將特征與樣本的關系用超圖表示；③最優特征子集的選擇則使用超圖中的Helly屬性進行處理。數據中的類別對應超邊，數據特征對應超圖中的頂點。其算法流程為如下所述：

輸入：S={S1,S2,…,Sn} /*訓練集中的n個樣本*/

F={FS1,FS2,…,FSl} /*訓練集中的樣本特征，l表示特征維數*/

C={C1,C2,…,Ck} /*訓練集中的k個類別*/

輸出：f={f1,f2,…,fm} /*特征子集維度m*/

Begin

{

for j=2 to k

{

for i=1 tol

//求每一維特征的Fisher分值

descend order (FSi)

//降序排列Fisher分值

for i=1 to 20

Cj={FSi} //取前20個特征

}

ifCi∩Cj=FSq(i,j∈k,i≠j) //利用超圖的Helly屬性選擇最優特征子集

f={FSq}

}

End

2.2 基于特征選擇的兩級混合入侵檢測方法

基于信息增益的隨機森林算法分析了各個特征屬性對最終分類結果的影響，而基于密集度的K-Means++算法則是從密集度和距離兩個層面考慮，方法整個過程劃分為兩個不同級別的分類器，其中第一級分類器在對攻擊數據的識別上有較高準確率，所以其能夠以很高的準確率識別部分攻擊樣本。第二級分類器以改進的K-Means算法為基礎對第一級分類器無法準確分類的剩下數據進行第二級分類，此方法能夠在提高對入侵數據的檢測率的同時很好控制對正常數據的誤報概率值。具體步驟如下：特征擇優階段：①首先在訓練階段計算訓練數據集各個類別中每一維特征的Fisher分值并按降序排列；②其次在各個類別中選擇Fisher分值排在前20的特征并添加到特征子集FSsub中；③最后對FSsub進行復篩，對具備Helly屬性的特征添加到最優特征子集f中；檢測階段：①先以隨機森林作為第一級分類器，這一級的分類結果得出的攻擊樣本直接作為最終的分類結果；②以基于密集度的K-Means++算法作為第二級分類器，其處理對象是第一級分類器中無法準確分類為攻擊樣本的剩余數據，得到的分類結果將作為最終的檢測結果。結合第一級分類器的部分分類結果，得到最終的全部分類結果。圖3表示的是此文提出的級聯分類器的算法流程圖。對本文算法的實驗結果的描述和分析將會在第3節作詳細描述，最終實驗結果表明本文的算法的性能要比僅僅采用隨機森林分類模型或K-Means算法的單一分類檢測模型要好。

圖3 基于特征選擇的兩級混合入侵檢測算法流程

3 實驗與分析

3.1 實驗設置

3.1.1 實驗數據

KDD CUP’99數據集來自麻省理工學院林肯實驗室，在業內目前被廣泛用于對入侵檢測問題研究[11]。該數據集中的每個樣本有42個維度的特征數據。屬性分類及個數參見文獻[12]中表2-1。該數據集主要包括4種類型的攻擊：Dos(拒絕服務攻擊)、Probe(端口監視或掃描)、R2L(遠程主機的未授權訪問)及U2R(未授權的本地超級用戶特權訪問)。本文采用10%的KDD CUP’99數據集作為訓練集，該數據集包含了494 021條數據記錄，其攻擊類型參見文獻[12]中表2-2。為了檢驗模型的泛化性能，采用KDD CUP’99 Corrected數據集作為測試集，該數據集包含了311 029條數據記錄，其中包括了17種新型攻擊類型，詳情參見文獻[12]中表2-3。各類別在訓練集和測試集中的數目參見文獻[12]中表2-4。

3.1.2 數據預處理

KDD CUP’99數據集中每條連接記錄的41個特征屬性有38個數字型特征屬性和3個字符型特征屬性構成，數據預處理階段主要是對原數據中的字符型數據進行數值化轉換，隨后對每個維度的數據進行數學上的歸一化處理，所采用的歸一化算法如式(7)所示

(7)

3.2 實驗結果與分析

一個好的入侵檢測系統是能夠在檢測率和誤報率之間達到很好的權衡的。因此，本文選取了準確率(accuracy，ACC)、精確率(precision，PRE)、檢測率(detection rate，DR)、誤報率(false alarm rate，FAR)4個指標用于衡量算法的性能。計算公式如下所示

(8)

(9)

(10)

(11)

其中，TP為正確識別的正樣本數，FP為錯誤識別的正樣本數，TN為正確識別的負樣本數，FN為錯誤識別的負樣本數。

將本文提出的入侵檢測模型與現有的分類模型在準確率和精確率上進行比較，實驗結果見表1。

由表1可以看出隨機森林算法對檢測數據中的真實攻擊類型的檢測準確率都很穩定，但是在全面性上有明顯的不足，但是在正常樣本和U2R攻擊類型的精確率有明顯的不足，經分析這其中的根本原因在于該算法對這兩個特定類型樣本的識別率較低；樸素貝葉斯算法在正常樣本及各類攻擊中性能都不突出；支持向量機算法對Dos和U2L類攻擊的檢測性能尤為突出；K-Means算法全局結果與其它算法相比都有明顯差距，這種結果產生的原因在于K-Means 方法受聚類中心選取的隨機性的影響較大。文獻[14]以算術殘差法及超圖得到的特征子集為基礎，并用概率神經網絡對樣本進行分類，結果表明其對正常樣本及Dos類攻擊的檢測準確率較優。本文提出的入侵檢測模型通過刪除冗余特征得到對原始數據特征表征效果較好的最小特征子集，使用基于信息增益的隨機森林算法進行分類過濾，能夠準確過濾出部分真實異常的數據，但是我們發現測試數據集當中存在一些屬于新出現類型的攻擊數據，對于這種情況下數據，僅僅依靠隨機森林算法的分類器的結果漏報率會比較高，基于對此種情況改進的考慮，使用基于密集度概念的K-Means++算法進行二級分類，實驗結果表明，本文提出的級聯后的分類器在保證很高的檢測準確率的同時，對正常樣本的檢測精度也有了很大的提升。

表1 分類器性能對比(一)

就檢測率和誤報率方面，將本文提出的入侵檢測方法與其它方法進行比較，實驗結果見表2。

表2 分類器性能對比(二)

由表2可以看出Guo等[3]選取KNN作為分類器，先對測試集進行異常檢測，然后分別利用異常檢測和誤用檢測對攻擊樣本和正常樣本進行檢測，其實驗結果表明該方法的檢測準確率不是很好。張思聰等[5]提出的DCNN方法在檢測率指標和誤報率指標上都能夠達到較為均衡的全局穩定性。Nathan等[7]利用非對稱深度自編碼器進行入侵檢測問題研究，其算法結果的檢測率有較好的表現，但是誤報率方面存在明顯的缺陷。Kuang等[13]利用核主成分分析進行特征降維，采用多級支持向量機作為分類器，并使用遺傳算法的思想理念進行參數的策略優化，除了算法復雜度得到改善以外，其計算結果表明該模型的分類綜合性能明顯優于傳統的支持向量機算法。Raman等[14]在特征選擇思想的基礎上，引入概率神經網絡對樣本進行分類，結果表明該模型并未在檢測率和誤報率之間達到很好的平衡。本文在基于Fisher分和超圖的Helly屬性的特征選擇基礎上，先后利用隨機森林算法和K-Means聚類進行分類可以達到更高的檢測率和更低的誤報率，優于現有的入侵檢測方法。

4 結束語

本文提出了一種基于特征選擇的兩級混合的入侵檢測方法。為了有效降低算法的訓練時間，引入了特征選擇，先計算各類別攻擊的Fisher分值，再利用超圖的Helly屬性確定最優特征子集。先用隨機森林作為第一階段的分類器，對測試集進行預測，隨后用改進的K-Means作為第二階段的分類器，針對第一階段預測得到的正常樣本進行二次檢測。結果表明，本文提出的方法在準確率、檢測率及誤報率方面均好于其它模型，是一種可行的入侵檢測方法。