平寒

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

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

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

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

1.1 信息增益ID3算法

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

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

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

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

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

1.2 獨(dú)立性檢驗(yàn)算法［6］

卡方獨(dú)立性檢驗(yàn)用于確定兩個(gè)分類(lèi)變量之間是否存在關(guān)系，而本文要研究的是兩種算法結(jié)果的關(guān)系比較，因此本文在獨(dú)立性檢驗(yàn)之中選擇卡方檢驗(yàn)?？ǚ綑z驗(yàn)計(jì)算公式［6］為

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

1.3 獨(dú)立性檢驗(yàn)與信息熵相結(jié)合的分類(lèi)算法

具體的算法［7］如下:

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

對(duì)所有屬性都運(yùn)用上式，最后選擇分類(lèi)選擇屬性G(xi)最大的那個(gè)屬性進(jìn)行分裂。改進(jìn)的決策樹(shù)算法偽代碼如下:

剛剛生成的決策樹(shù)由于分類(lèi)過(guò)細(xì)，會(huì)出現(xiàn)過(guò)度擬合現(xiàn)象，使檢測(cè)結(jié)果下降，而目前避免過(guò)度擬合的主要的方法是對(duì)決策樹(shù)進(jìn)行剪枝。

2 實(shí)驗(yàn)與性能分析

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

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

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

2.2 實(shí)驗(yàn)與分析

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

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

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

2.3 訓(xùn)練過(guò)程

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

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

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

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

(4)為最佳分類(lèi)屬性的每個(gè)值劃分?jǐn)?shù)據(jù)子集、生成一個(gè)新的決策樹(shù)結(jié)點(diǎn)，并生成對(duì)應(yīng)每個(gè)最佳屬性值的子工作表和子屬性列表，新生成的結(jié)點(diǎn)作為該結(jié)點(diǎn)的子結(jié)點(diǎn)。

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

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

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

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

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

2.4 測(cè)試過(guò)程

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

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

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

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

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

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

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

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

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

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

2.5 決策樹(shù)的剪枝［8］

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

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

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

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

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

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

2.6 面對(duì)未知攻擊時(shí)的判斷能力

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

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

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

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

3 結(jié)論

本算法對(duì)原有單純基于信息熵增益算法進(jìn)行了改進(jìn)。實(shí)驗(yàn)證明，該算法可以對(duì)已知攻擊進(jìn)行判斷，取得了較好的預(yù)期效果。本算法不但在檢測(cè)率和誤檢率上與原算法相比有了較大提高，而且通過(guò)結(jié)合綜合策略的剪枝算法避免了過(guò)度擬合對(duì)檢測(cè)結(jié)果的影響，同時(shí)對(duì)現(xiàn)有的檢測(cè)進(jìn)行了優(yōu)化，使檢測(cè)結(jié)果得到提升。另外，本算法還可以對(duì)未知的攻擊進(jìn)行鑒別，解決了常規(guī)算法在異常檢測(cè)中的誤報(bào)率偏高的問(wèn)題。從結(jié)果來(lái)看，本算法與原有算法相比在入侵檢測(cè)的性能上得到了大幅度的提高，達(dá)到了實(shí)驗(yàn)?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］孫超利，張繼福 . 基于屬性-值對(duì)的信息增益優(yōu)化算法［J］.太原科技大學(xué)學(xué)報(bào)，2005，26(3):199－202.

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

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

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

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