基于改進決策樹的入侵檢測算法

平寒

(山東職業(yè)學(xué)院信息工程系，山東濟南250100)

假如有預(yù)謀的、潛在的、未經(jīng)授權(quán)的操作信息和訪問信息造成系統(tǒng)無法使用或者使系統(tǒng)不可靠，那么發(fā)覺這樣的企圖或行為被定義為入侵檢測［1］。在入侵檢測系統(tǒng)中使用數(shù)據(jù)挖掘技術(shù)已越來越普遍［2］，而基于決策樹的數(shù)據(jù)挖掘技術(shù)，其分類檢測模型具有高效、分類準確率高和易于理解等優(yōu)點，因而備受歡迎。但該技術(shù)也存在缺點［3］，一是算法效率低;二是訓(xùn)練集的選取問題，如果超出內(nèi)存容量將無法運行。

本文嘗試使用基于多變量綜合策略剪枝算法，使算法效率有所提高，同時提高訓(xùn)練集選取的有效性。

1 基于改進決策樹的入侵檢測算法的設(shè)計

1.1 信息增益ID3算法

ID3算法以信息論為基礎(chǔ)，采用劃分后的樣本集的不確定性作為衡量劃分優(yōu)劣的標準，利用信息熵和信息增益度進行度量。信息增益度越大，不確定性越小。因此，信息增益ID3算法的設(shè)計首先要計算每個屬性的信息增益，然后選取信息增益最大的屬性作為測試屬性。

信息增益度ID3算法［4－5］描述的公式如下:

在決策樹分類中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣本劃分為n個不同的類C1，C2，…，Cn，這些類的大小分別標記為|C1|，|C2|，…，|Cn|。則任意樣本 S屬于類 Ci的概率［1－2］為

其中，∑是屬性A的所有可能的值，Sv是屬性A有v值的S子集;|Sv|是Sv中元素的個數(shù);|S|是S中元素的個數(shù)［4－5］。

Gain(S，A)是屬性A在集合S上的信息增益。若Gain(S，A)越大，則表明選擇測試屬性對分類提供的信息就會越多［4－5］。

1.2 獨立性檢驗算法［6］

卡方獨立性檢驗用于確定兩個分類變量之間是否存在關(guān)系，而本文要研究的是兩種算法結(jié)果的關(guān)系比較，因此本文在獨立性檢驗之中選擇卡方檢驗。卡方檢驗計算公式［6］為

其中，nik代表第i個屬性的第k個屬性值;ni，nk為這一行或列中屬性取值的和，表示的是該屬性與決策屬性的相關(guān)性。

1.3 獨立性檢驗與信息熵相結(jié)合的分類算法

具體的算法［7］如下:

其中，G(xi)為分類選擇屬性，Gain(xi)表示信息增益的大小。

對所有屬性都運用上式，最后選擇分類選擇屬性G(xi)最大的那個屬性進行分裂。改進的決策樹算法偽代碼如下:

剛剛生成的決策樹由于分類過細，會出現(xiàn)過度擬合現(xiàn)象，使檢測結(jié)果下降，而目前避免過度擬合的主要的方法是對決策樹進行剪枝。

2 實驗與性能分析

2.1 KDD CUP99數(shù)據(jù)集的介紹

本次實驗的數(shù)據(jù)集采用的是KDD CUP99入侵檢測數(shù)據(jù)集，該數(shù)據(jù)集為入侵檢測系統(tǒng)提供統(tǒng)一的性能評價基準，可以仿真各種用戶的類型、模擬各種不同的網(wǎng)絡(luò)流量及攻擊手段，使之就像一個真實存在的網(wǎng)絡(luò)環(huán)境。

每一個網(wǎng)絡(luò)連接被標記為Attack(異常)或Normal(正常)，Attack(異常)類型被細劃為四個大類，共39種攻擊類型。其中17種Unknown(未知)攻擊類型出現(xiàn)在KDD CUP99(測試數(shù)據(jù))集中;22種攻擊類型出現(xiàn)在訓(xùn)練數(shù)據(jù)集當中。

2.2 實驗與分析

本算法在Windows 7操作系統(tǒng)實驗平臺、Microsoft Visual Stdio C++6.0環(huán)境下實現(xiàn)基于KDD CUP99數(shù)據(jù)集、采用信息增益與卡方檢驗方法結(jié)合的入侵檢測。算法實現(xiàn)主要包括數(shù)據(jù)集讀入用規(guī)格化、采用信息增益結(jié)合卡方檢驗方法訓(xùn)練生成決策樹、采用后剪枝算法對生成的決策樹進行剪枝、測試。

本實驗對數(shù)據(jù)集的處理采用的是數(shù)據(jù)文件的形式。實驗數(shù)據(jù)來自KDD CUP99數(shù)據(jù)集中的kddcup.data，其大小約為 743 MB，為了使用方便，我們使用 KDD CUP99自帶的 10%的數(shù)據(jù)集 kddcup.data_10_percent，本文隨機從中提取了6 080個數(shù)據(jù)。

本文所使用的測試集來自KDD CUP99中的數(shù)據(jù)集corrected，我們從中提取測試子集，共提取7 009條數(shù)據(jù)，其中1 009條為攻擊數(shù)據(jù)。

2.3 訓(xùn)練過程

具體訓(xùn)練過程如下:

(1)生成一個決策樹結(jié)點，分析當前工作數(shù)據(jù)表和屬性列表，如果當前決策屬性只有一個值，則該結(jié)點為葉結(jié)點，其分類為當前屬性列表中決策屬性的值。

(2)如果當前屬性列表中只有決策屬性，則該結(jié)點也是葉結(jié)點，其分類為當前工作數(shù)據(jù)表中占多數(shù)的決策屬性值。

(3)否則，該結(jié)點為中間結(jié)點，對工作數(shù)據(jù)表計算每個屬性的卡方值和信息增益值，然后選擇卡方值與信息增益值之和最大的屬性作為最佳分類屬性，最后以最佳分類屬性標記該結(jié)點。

(4)為最佳分類屬性的每個值劃分數(shù)據(jù)子集、生成一個新的決策樹結(jié)點，并生成對應(yīng)每個最佳屬性值的子工作表和子屬性列表，新生成的結(jié)點作為該結(jié)點的子結(jié)點。

(5)遞歸調(diào)用此過程，最終生成決策樹。

具體訓(xùn)練結(jié)果如圖1所示。

其中屬性數(shù)42是由41個基本屬性和1個決策屬性所構(gòu)成。

訓(xùn)練結(jié)果成功地計算出信息增益與卡方值的大小，并以此作為分類建樹的標準，成功地建樹分類，從結(jié)果看，完成了建樹的目的，并為測試做了準備。

圖1 訓(xùn)練過程Fig.1 The training process

2.4 測試過程

當數(shù)據(jù)訓(xùn)練結(jié)束之后，我們將測試數(shù)據(jù)集導(dǎo)入，具體測試過程如下:

程序在讀入測試數(shù)據(jù)集后立刻對測試數(shù)據(jù)集進行預(yù)處理，首先經(jīng)過對數(shù)據(jù)集各個數(shù)據(jù)的完整性檢查清除無效記錄，然后將決策樹根結(jié)點的屬性值與測試數(shù)據(jù)數(shù)組相應(yīng)的屬性值比較決定進入下一個分枝，判斷該節(jié)點是否是葉節(jié)點，如果該結(jié)點是葉結(jié)點，則將該結(jié)點的分類值與該記錄的分類值比較;再連續(xù)的進行此類比較，當全部記錄比較完成后生成統(tǒng)計數(shù)據(jù)，包括檢出率、誤檢率等數(shù)據(jù)。而后，對上述數(shù)據(jù)進行統(tǒng)計分析。將統(tǒng)計信息通過對話框顯示出來。

測試集讀入后屬性輸出結(jié)果如圖2所示，檢測結(jié)果輸出如圖3所示。

圖2 測試集讀入后屬性輸出結(jié)果Fig.2 Attribute output result after test set reading

圖3 檢測結(jié)果輸出Fig.3 Detection results output

對數(shù)據(jù)集2和數(shù)據(jù)集3的操作同理。經(jīng)過整理，數(shù)據(jù)集1，2，3的測試結(jié)果如表1所示。

表1 數(shù)據(jù)集1，2，3的測試結(jié)果Table 1 Test results of data set 1，2 and 3

為了對比，將只使用信息熵增益方法的決策樹成樹算法與本文算法相比較，得到結(jié)果如表2所示。

表2 傳統(tǒng)算法與本文算法結(jié)果比較Table 2 Result comparison between traditional algorithm and the presented algorithm

由表1和表2可知，本文算法一共檢出846次攻擊，而只基于信息增益算法只檢出783次攻擊，特別是在本算法面對U2R攻擊時，本算法的檢出率比只基于信息增益的方法提高了1倍多，檢測性能更是有了質(zhì)的提高。

2.5 決策樹的剪枝［8］

(1)用訓(xùn)練數(shù)據(jù)集和某一測試數(shù)據(jù)集對生成的決策樹進行測試，取得測試統(tǒng)計數(shù)據(jù)，計算未剪枝決策樹的預(yù)期分類錯誤率PT值;

(2)遍歷決策樹，一次剪掉找到的一個葉結(jié)點，如果剪掉葉結(jié)點后，結(jié)點t的子結(jié)點全部已剪掉，則t為葉結(jié)點，t的分類屬性為其數(shù)據(jù)集中占多數(shù)的決策屬性值，計算剪掉一個葉結(jié)點后的決策樹預(yù)期分類錯誤率PC;

(3)如果 PT≥PC，則結(jié)束，生成剪枝后的決策樹，否則PT=Max(PC)，遞歸完成剪枝過程。

進行剪枝之后的測試集1的檢測結(jié)果如圖4所示。

與未剪枝前的決策樹處理結(jié)果(圖3)對比我們可以看到，由于存在著過度擬合現(xiàn)象，導(dǎo)致未剪枝的決策樹的性能比已剪枝的決策樹較差，特別是在誤報率方面，采用本綜合策略剪枝算法生成的決樹與未剪枝決策樹相比有了較大提升。而且對決策樹的剪枝還可以大規(guī)模降低整棵樹的復(fù)雜性，使所生成決策樹的可用性和性能得到提高。

圖4 進行剪枝之后的測試集1的檢測結(jié)果Fig.4 Test results of test set 1 after pruning

2.6 面對未知攻擊時的判斷能力

在訓(xùn)練集不變的情況下，更改測試集，測試集中的攻擊類型是之前決策樹不曾遇見過的，為了貫徹這一思想，我們選取在訓(xùn)練集kddcup.data_10_percent數(shù)據(jù)集中從未出現(xiàn)的一些攻擊類型組成測試集。對未知攻擊的測試結(jié)果如圖5所示。

圖5所示的檢出率實際上是攻擊類型的誤檢率，因為這些數(shù)據(jù)的攻擊類型從未在訓(xùn)練集中出現(xiàn)，所以我們希望得到的結(jié)果是Uknown，而不是上面任何一個具體分類結(jié)果，而真正檢測錯誤的數(shù)據(jù)只有檢測結(jié)果為Normal那些數(shù)據(jù)，由此我們可得到，本文所述算法對上述未知攻擊數(shù)據(jù)集的檢測率為0.919。

由實驗結(jié)果可知，由于訓(xùn)練集所包含攻擊類型的不完整，本文決策樹在面對未知攻擊時并不能準確地對各類攻擊進行十分準確的分類，有一些數(shù)據(jù)在攻擊類型的判斷上出現(xiàn)了錯誤，但是可以看到，如果就檢出未知攻擊能力這一點來說，本算法繼承了異常檢測算法對未知攻擊的高分辨能力，對未知攻擊的檢測率還是相對不錯的。

圖5 對未知攻擊的測試結(jié)果Fig.5 Test results of unknown attacks

3 結(jié)論

本算法對原有單純基于信息熵增益算法進行了改進。實驗證明，該算法可以對已知攻擊進行判斷，取得了較好的預(yù)期效果。本算法不但在檢測率和誤檢率上與原算法相比有了較大提高，而且通過結(jié)合綜合策略的剪枝算法避免了過度擬合對檢測結(jié)果的影響，同時對現(xiàn)有的檢測進行了優(yōu)化，使檢測結(jié)果得到提升。另外，本算法還可以對未知的攻擊進行鑒別，解決了常規(guī)算法在異常檢測中的誤報率偏高的問題。從結(jié)果來看，本算法與原有算法相比在入侵檢測的性能上得到了大幅度的提高，達到了實驗?zāi)康?，得到了預(yù)期的結(jié)果。

［1］JANES P，ANDERSON W.Computer security threat monitoring and surveillance［EB/OL］.［2014 －02 －10］.http://www.docin.com/p －567457508.html.

［2］LEE W，STOLFO S J，MOK K W.Mining audit data to build intrusion detection models［C］//Proc Conf Knowledge Discovery and Data Mining(KDD＇98)，1998:66 －72.

［3］LIU H，HUSSAIN F，TAN C L.Discretization:An enabling technique［J］.Data Mining and Knowledge Discovery，2002，6(4):393－423.

［4］孫超利，張繼福 . 基于屬性-值對的信息增益優(yōu)化算法［J］.太原科技大學(xué)學(xué)報，2005，26(3):199－202.

［5］張春麗，張磊.一種基于修正信息增益的ID3算法［J］.計算機工程與科學(xué)，2008，30(11):46－47.

［6］葉慈南，曹偉麗.應(yīng)用數(shù)理統(tǒng)計［M］.北京:機械工業(yè)出版社，2009.

［7］孔祥南，黎銘，姜遠，等.一種針對弱標記的直推式多標記分類方法［J］.計算機研究與發(fā)展，2010，47(8):1392－1399.

［8］鐘慧玲，章夢，石永強，等.基于剪枝策略的改進TDCALT算法［J］，同濟大學(xué)學(xué)報:自然科學(xué)版，2012，40(8):1197－1203.