基于隨機(jī)森林的網(wǎng)絡(luò)攻擊檢測(cè)方法

王 浩

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144)

基于隨機(jī)森林的網(wǎng)絡(luò)攻擊檢測(cè)方法

王 浩

(北方工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京 100144)

網(wǎng)絡(luò)攻擊檢測(cè)是網(wǎng)絡(luò)領(lǐng)域的一個(gè)重要的應(yīng)用，目前在這領(lǐng)域內(nèi)的檢測(cè)方法有很多，但是已有的檢測(cè)機(jī)制存在著錯(cuò)誤率高以及無法處理數(shù)據(jù)不平衡等問題。通過分析網(wǎng)絡(luò)攻擊數(shù)據(jù)，設(shè)計(jì)了基于隨機(jī)森林的網(wǎng)絡(luò)入侵檢測(cè)算法，并把這個(gè)算法用于網(wǎng)絡(luò)連接信息數(shù)據(jù)的檢測(cè)和異常發(fā)現(xiàn)。通過對(duì)CUP99數(shù)據(jù)的測(cè)試集進(jìn)行試驗(yàn)，基于隨機(jī)森林的算法能夠提高識(shí)別效率，有效的解決數(shù)據(jù)不平衡帶來的問題，具有很好的分類效果。

攻擊檢測(cè)；數(shù)據(jù)不平衡；隨機(jī)森林；CUP99

本文著錄格式：王浩. 基于隨機(jī)森林的網(wǎng)絡(luò)攻擊檢測(cè)方法[J]. 軟件，2016，37（11）：60-63

0 引言

網(wǎng)絡(luò)攻擊檢測(cè)是維持一個(gè)系統(tǒng)安全非常重要的一方面。網(wǎng)絡(luò)攻擊檢測(cè)的目的就是要發(fā)現(xiàn)網(wǎng)絡(luò)中的異常數(shù)據(jù)，維持系統(tǒng)的完整性，機(jī)密性和資源的可用性[1]。在信息化時(shí)代，攻擊檢測(cè)是對(duì)網(wǎng)絡(luò)數(shù)據(jù)的分析來找出入侵的數(shù)據(jù)，也就是那些未經(jīng)允許的連接訪問，試圖去破壞或者惡意使用信息資源的行為。

目前的入侵檢測(cè)分為兩類：誤用檢測(cè)和異常檢測(cè)。誤用檢測(cè)是事先對(duì)已經(jīng)獲取的入侵?jǐn)?shù)據(jù)進(jìn)行分析，提取其中的攻擊規(guī)則和模式，然后在檢測(cè)的過程中將新的數(shù)據(jù)與已有的攻擊規(guī)則和模式進(jìn)行匹配，如果匹配，則說明發(fā)生了攻擊行為。異常檢測(cè)是檢測(cè)數(shù)據(jù)與正常情況下數(shù)據(jù)的相似度，如果不符合以往正常情況下的數(shù)據(jù)行為，那么可以認(rèn)為發(fā)生了攻擊行為[2]。異常檢測(cè)不僅能夠發(fā)現(xiàn)已知的攻擊行為，也能發(fā)現(xiàn)未知的攻擊行為。

到目前未知，學(xué)術(shù)界出現(xiàn)了很多檢測(cè)網(wǎng)絡(luò)攻擊的方法，有運(yùn)用概率來計(jì)算的方法[3]，基于數(shù)據(jù)挖掘方法[4]，基于人工神經(jīng)網(wǎng)絡(luò)的方法[5]，以模糊數(shù)學(xué)為理論的方法[6]等，但是通過單一的方法構(gòu)建分類器，在準(zhǔn)確率上存在缺陷，精度無法保證正常的使用，并且容易出現(xiàn)過擬合的問題。為了解決單一分類器存在的問題，許多學(xué)者提出了集成方法，通過組合多個(gè)分類器來提高檢測(cè)的精度。目前使用最多的就是bagging和boosting的方法。Bagging采用自助采樣（bootstrap）對(duì)訓(xùn)練集進(jìn)行抽樣，每個(gè)個(gè)體分類器所采用的訓(xùn)練樣本都是從訓(xùn)練集中按等概率抽取的，因此Bagging的各子網(wǎng)能夠很好的覆蓋訓(xùn)練樣本空間，從而有著良好的穩(wěn)定性。Boosting方法中，基分類器串行工作，后續(xù)的單分類器著重對(duì)前面的錯(cuò)誤分類樣本進(jìn)行處理，直到得到一個(gè)準(zhǔn)確

率比較高的分類器組合，由于Boosting算法可能會(huì)將噪聲樣本或分類邊界樣本的權(quán)重過分累積，因此Boosting很不穩(wěn)定。

隨機(jī)森林算法（RFA）[7]由Leo Breiman第一次在2001年的文章中提出，它是Bagging的一個(gè)擴(kuò)展的變體。隨機(jī)森林以決策樹為基學(xué)習(xí)器來構(gòu)建Bagging集成，并且在決策樹的訓(xùn)練過程中引入了隨機(jī)屬性的選擇。由于出色的分類效果，隨機(jī)森林已經(jīng)在諸多領(lǐng)域得到了應(yīng)用。本文在第二節(jié)中詳細(xì)介紹了隨機(jī)森林算法的具體過程。第三節(jié)針對(duì)cup99數(shù)據(jù)集多分類情況下的數(shù)據(jù)不平衡問題，將sampling的處理進(jìn)行改進(jìn)，并應(yīng)用到隨機(jī)森林算法得到檢測(cè)網(wǎng)絡(luò)入侵的模型并進(jìn)行交叉驗(yàn)證。

1 隨機(jī)森林算法

1.1 采樣過程

隨機(jī)森林中采用自助采樣（bootstrap sampling）[8]的方法，給定包含m個(gè)樣本的數(shù)據(jù)集D，隨機(jī)從中選取一個(gè)樣本，然后再將此樣本放回，下次采樣的時(shí)候可能再次取得此樣本。這樣有放回的取m次后，我們得到包含跟原樣本數(shù)量一致的數(shù)據(jù)集，在此數(shù)據(jù)集中一些樣本可能會(huì)重復(fù)出現(xiàn)，可以做一個(gè)估計(jì)，大約有的樣本在所有的采樣中都沒有被采到,取極限可以得到，自助采樣使得原始數(shù)據(jù)集中36.8%的數(shù)據(jù)沒有出現(xiàn)在采樣后的數(shù)據(jù)集，這樣我們可以使用數(shù)量為m的采樣數(shù)據(jù)集來進(jìn)行訓(xùn)練，同時(shí)其中有大約1/3的數(shù)據(jù)來進(jìn)行測(cè)試，通常稱這種測(cè)試為“包外估計(jì)”（out-ofbag estimate）。

1.2 Bagging算法

Baggin[9]是一種并行式的集成算法。通過多次的采樣過程，我們得到了T個(gè)含有m個(gè)樣本的數(shù)據(jù)集，針對(duì)每一個(gè)數(shù)據(jù)集，訓(xùn)練出一個(gè)基學(xué)習(xí)器模型，通過投票的方式選出最佳的投票結(jié)果，這可以當(dāng)做是最終預(yù)測(cè)的類別。每個(gè)基學(xué)習(xí)器都是弱學(xué)習(xí)算法，但是投票后的準(zhǔn)確率將得到大幅度提高。如果出現(xiàn)投票一致的情況，最簡(jiǎn)單的方式是隨機(jī)選取一個(gè)，也可以選用置信度來決定最終的結(jié)果。本文主要在數(shù)據(jù)的預(yù)處理階段進(jìn)行bagging，下一節(jié)可以看到在此階段的優(yōu)化過程。Bagging的算法描述如下：

假定基學(xué)習(xí)器的算法復(fù)雜度為O(m)，則bagging的算法復(fù)雜度為T(O(m))+O(s)，其中O(s)為投票過程的復(fù)雜度，由于相比O(m)小很多故可以忽略，因此算法的復(fù)雜度維持在O(m)的水平上，是一個(gè)比較高效的算法。

通過自助采樣，我們得到的訓(xùn)練集只有原數(shù)據(jù)集D的63.2%的樣本，剩余的36.8%的數(shù)據(jù)集可以用作包外估計(jì)[10]。令Dt(x)為訓(xùn)練集，Hoob(x)為包外估計(jì)的預(yù)測(cè)，并且僅使用D-Dt(x)的數(shù)據(jù)來進(jìn)行估計(jì)，則

泛化誤差為：

1.3 隨機(jī)森林算法

隨機(jī)森林[7]算法是以bagging算法為基礎(chǔ)，加入了特征上的隨機(jī)性。算法以決策樹為基訓(xùn)練器，在決策樹的訓(xùn)練過程中加入了特征上的隨機(jī)選擇。

首先，按照自助采樣的方式取得與原數(shù)據(jù)集數(shù)量一致的m個(gè)樣本作為訓(xùn)練集，假定當(dāng)前一共有d個(gè)特征屬性，對(duì)于每一個(gè)決策樹，隨機(jī)選取k＜d個(gè)屬性作為單個(gè)決策樹的特征集合。對(duì)于每個(gè)基學(xué)習(xí)器，即單棵決策樹，在k個(gè)屬性中尋找能夠在訓(xùn)練集中表現(xiàn)最優(yōu)的屬性進(jìn)行分裂。參數(shù)k控制了特征的隨機(jī)性，k=d時(shí)跟普通的決策樹一樣，k=1時(shí)是隨機(jī)選取一個(gè)屬性，建議選擇k=log2d[7]。

新數(shù)據(jù)獲取后，將數(shù)據(jù)帶入訓(xùn)練好的森林模型中，預(yù)測(cè)基于每一棵決策樹的預(yù)測(cè)結(jié)果，通常有多種方式可以進(jìn)行投票。假定單棵樹hi要對(duì)多類別進(jìn)行預(yù)測(cè)，我們將hi在樣本x的預(yù)測(cè)表示為一個(gè)N維向量其中代表h在c類別上的預(yù)測(cè)值，投票法的表示為ij

2 在網(wǎng)絡(luò)攻擊檢測(cè)中應(yīng)用隨機(jī)森林算法

網(wǎng)絡(luò)攻擊檢測(cè)的目的是識(shí)別網(wǎng)絡(luò)中的異常流量，從而及時(shí)的發(fā)現(xiàn)攻擊行為，針對(duì)流量的特征，分析出攻擊的方式，進(jìn)而采取對(duì)應(yīng)的解決方案。目前大多數(shù)的異常流量檢測(cè)是基于規(guī)則的識(shí)別技術(shù)，下面提出使用隨機(jī)森林的方法來識(shí)別，這種方式和基于規(guī)則的方法相比，可以減少專家的參與，避免隨著網(wǎng)絡(luò)復(fù)雜度的升級(jí)而造成的規(guī)則的爆炸性增長(zhǎng)。同基于聚類的方法相比，樹類型的算法在性能上有著明顯的優(yōu)勢(shì)，在不需要進(jìn)行向量相似性對(duì)比的情況下就能檢測(cè)出攻擊類型。

2.1 數(shù)據(jù)采集與分析

數(shù)據(jù)來源于網(wǎng)絡(luò)，需要網(wǎng)絡(luò)設(shè)備在網(wǎng)絡(luò)連接過程中采集網(wǎng)絡(luò)數(shù)據(jù)包的特性，每個(gè)樣本描述一個(gè)階段內(nèi)的數(shù)據(jù)包屬性。包括協(xié)議類型，連接長(zhǎng)度，源到目的的數(shù)據(jù)字節(jié)數(shù)，目的到源的數(shù)據(jù)字節(jié)數(shù)，錯(cuò)誤段的數(shù)量，連接的狀態(tài)等等。在這里我們選用KDD CUP99數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)集，該數(shù)據(jù)集取自真是的網(wǎng)絡(luò)環(huán)境，是美國(guó)國(guó)防部為了進(jìn)行入侵檢測(cè)研究而收集的數(shù)據(jù)集，是學(xué)術(shù)界關(guān)于攻擊檢測(cè)用的最多的數(shù)據(jù)集。它包含了500多萬(wàn)的連接數(shù)據(jù)，訓(xùn)練集囊括了主流的23種攻擊行為，除了一些基本的屬性，例如持續(xù)時(shí)間、協(xié)議類型、傳輸?shù)淖止?jié)數(shù)等，還添加了2 s內(nèi)時(shí)間窗的統(tǒng)計(jì)屬性，統(tǒng)計(jì)和當(dāng)前連接有相同目的主機(jī)的連接特征以及有相同服務(wù)的主機(jī)的連接特征.

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

我們?nèi)∮胏up99的10%的數(shù)據(jù)集，為了適應(yīng)隨機(jī)森林算法，需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理。首先需要對(duì)字符屬性進(jìn)行轉(zhuǎn)換，轉(zhuǎn)換成數(shù)字格式。其次需要對(duì)回歸屬性值進(jìn)行離散化，由于隨機(jī)森林是基于樹的算法，而ID3只支持離散型變量，C4.5和CART不適合23種類別的分類的問題，故需要手動(dòng)進(jìn)行離散化。

同時(shí)，我們觀察數(shù)據(jù)可以發(fā)現(xiàn)，數(shù)據(jù)集存在著嚴(yán)重的不平衡問題，現(xiàn)在關(guān)于數(shù)據(jù)集的不平衡性的研究中，主要從數(shù)據(jù)集和算法兩個(gè)方面進(jìn)行解決。數(shù)據(jù)集的改進(jìn)是對(duì)數(shù)據(jù)集的分布進(jìn)行改變，然后對(duì)改進(jìn)后的數(shù)據(jù)集進(jìn)行模型擬合，sampling方法被證明是處理不平衡數(shù)據(jù)問題的一個(gè)有效的方法[11]。算法方面進(jìn)行解決是對(duì)算法進(jìn)行優(yōu)化，增大劣勢(shì)類別的權(quán)重。

從數(shù)據(jù)集的方面解決的方法為過采樣和欠采樣，針對(duì)稀有類別的樣本進(jìn)行重復(fù)的抽取，同時(shí)需要減少優(yōu)勢(shì)類別的數(shù)量，傳統(tǒng)的方法采用隨機(jī)向上向下采樣法（Random Oversampling/Random Undersampling），Over sampling就是在原數(shù)據(jù)集D中劣勢(shì)類別mini里面隨機(jī)選取樣本集合添加到數(shù)據(jù)集中，,其中n和m分別代表劣勢(shì)類別和優(yōu)勢(shì)類別的種類。Undersampling就是選取優(yōu)勢(shì)類別maxj里隨機(jī)選取的樣本集合為剩下的即為新的數(shù)據(jù)集，但是單純的重復(fù)劣勢(shì)類別容易產(chǎn)生過擬合的問題[12]，去除已有優(yōu)勢(shì)類別的數(shù)據(jù)也會(huì)丟失掉許多有用的信息。

因此采用改進(jìn)的SMOTE（Synthetic Minority Oversampling Technique）。SMOTE本質(zhì)上是一個(gè)優(yōu)化過的oversampling算法[13]。原算法是對(duì)于每一個(gè)計(jì)算xi的K個(gè)近鄰，然后隨機(jī)選取其中的一個(gè)近鄰xt合成新的數(shù)據(jù)其中σ是 [0,1]中的隨機(jī)數(shù)。SMOTE是對(duì)簡(jiǎn)單的過采樣算法的優(yōu)化，避免了單純的復(fù)制劣勢(shì)類別，減小了過擬合。

SMOTE算法由于是對(duì)原數(shù)據(jù)集的操作，因此可能選定的近鄰與當(dāng)前點(diǎn)的類別存在不同。改進(jìn)后的算法是只對(duì)劣勢(shì)類別進(jìn)行處理，選取k∈[1,n]，其中n是劣勢(shì)類別的數(shù)量，直接對(duì)于k個(gè)數(shù)據(jù)取平均，這樣新得到的數(shù)據(jù)是對(duì)原數(shù)據(jù)的輕微擾動(dòng)，并且能夠保證新數(shù)據(jù)在原有的數(shù)據(jù)簇中，能夠有效的減小過擬合的問題。

3 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文提出算法的普適性和有效性，選取KDD cup99數(shù)據(jù)集的10%作為訓(xùn)練集，correct文件作為驗(yàn)證集，并與經(jīng)典的SVM等算法進(jìn)行比較。隨機(jī)森林工具包使用scikit-learn，本文實(shí)驗(yàn)環(huán)境為Intel(R) Pentium(R) CPU P6100 @ 2.00 GHZ，內(nèi)存2 G，32位Win7操作系統(tǒng)，Ipython notebook編程。

3.2 實(shí)驗(yàn)結(jié)果及分析

隨機(jī)森林，Wenka Lee的算法，BP神經(jīng)網(wǎng)絡(luò)，SVM算法在KDD CUP99數(shù)據(jù)集[14][15]中關(guān)于網(wǎng)絡(luò)攻擊識(shí)別的結(jié)果由表1可以看出。

3.1 實(shí)驗(yàn)設(shè)置

表1 幾個(gè)算法的準(zhǔn)確率比較

從表中我們可以看出，隨機(jī)森林算法在準(zhǔn)確度和檢測(cè)全面性方面達(dá)到了一個(gè)比較平衡的狀態(tài)，需要犧牲一部分的準(zhǔn)確度來提高分類效果比較差的U2R類別。傳統(tǒng)的幾個(gè)算法，對(duì)于類別之間的不平衡是無法處理的，在U2R中的識(shí)別效率非常低。隨機(jī)森林的算法相比其他算法在幾個(gè)類別的識(shí)別中，雖然Prob，Dos，R2L三類的識(shí)別率不如SVM的準(zhǔn)確率高，但是在U2R中準(zhǔn)確率是明顯提升的，這說明對(duì)于數(shù)據(jù)不平衡問題有了小程度的提升，而且，準(zhǔn)確度的降低并不是特別的明顯，可用度有一定程度的提升。

4 結(jié)束語(yǔ)

本文通過改進(jìn)隨機(jī)森林當(dāng)中的bagging方法，改變?cè)袛?shù)據(jù)集中數(shù)據(jù)的分布，并將其應(yīng)用到CUP99數(shù)據(jù)集。基于這個(gè)算法，在數(shù)據(jù)集中試驗(yàn)表明，雖然改進(jìn)后的算法在其他三個(gè)類別中的準(zhǔn)確度降低，但是能一定程度的改善原來的數(shù)據(jù)不平衡性的問題。接下來的工作聚焦到1）算法的改進(jìn)，對(duì)隨機(jī)森林算法的防止過擬合部分進(jìn)行研究，并通過交叉驗(yàn)證的方式優(yōu)化參數(shù)。2）特征工程，對(duì)于無用的特征進(jìn)行篩選，防止無用特征影響分類結(jié)果。

[1] Denning D E. An Intrusion-Detection Model[J]. IEEE Transactions on Software Engineering, 1987, 13(2)∶ 222-232.

[2] 滕少華. 基于對(duì)象監(jiān)控的分布式協(xié)同入侵檢測(cè)[D]. 廣東工業(yè)大學(xué), 2008.

[3] Licks V, Jordan R. Geometric Attacks on Image Watermarking Systems[J]. Multimedia IEEE, 2005, 12(3)∶ 68-78.

[4] Kutter M, Bhattacharjee S K, Ebrahimi T. Towards second generation watermarking schemes[C]// International Conference on Image Processing, 1999. ICIP 99. Proceedings. 1999∶320-323 vol.1.

[5] Bas P, Chassery J M, Macq B. Geometrically invariant watermarking using feature points.[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 2002, 11(9)∶ 1014-28.

[6] Tang C W, Hang H M. A Feature-Based Robust Digital Image Watermarking Scheme[J]. Signal Processing IEEE Transactions on, 2003, 51(4)∶ 950-959.

[7] Breiman L. Random Forests[J]. Machine Learning, 2001, 45(1)∶ 5-32.

[8] Efron B B, Tibshirani R J. An Introduction to the Bootstrap (ISBN 0412042312[J]. 2010.

[9] Breiman L. Bagging Predictors[J]. Machine Learning, 1996, 24(2)∶ 123-140.

[10] Wolpert D H, Macready W G. An Efficient Method To Estimate Bagging‘s Generalization Error[J]. Machine Learning, 1999, 35(1)∶41-55.

[11] Estabrooks A, Jo T, Japkowicz N. A Multiple Resampling Method for Learning from Imbalanced Data Sets[J]. Computational Intelligence, 2004, 20(1)∶ 18-36.

[12] Holte R, Acker L, Porter B. Concept Learning and the Problem of Small Disjuncts[M]. University of Texas at Austin, 1995.

[13] Chawla N V, Bowyer K W, Hall L O, et al. SMOTE∶synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2011, 16(1)∶ 321-357.

[14] Lee W, Stolfo S J, Mok K W. A data mining framework for building intrusion detection models[J]. Proceedings of the IEEE Symposium on Security & Privacy, 1999∶ 120-132.

[15] Mukkamala S, Sung A H, Abraham A. Intrusion Detection Using Ensemble of Soft Computing Paradigms[M]// Intelligent Systems Design and Applications. Springer Berlin Heidelberg, 2003∶ 239-248.

An Intrusion Detection Method Based on Random Forests Algorithm

WANG Hao
(College of Computer Sciences, North China University of Technology, Beijing, China, 100144)

Network intrusion detection is one of the important application in network area. At present, there are various detection approaches in this area. However, some problems are found in the existing algorithms, including high error rate and failure processing of data imbalance. After analyzing the network intrusion data, we design an intrusion detection algorithm based on random forests and apply it to detection of network connection information data and anomaly find. The experiment on CUP99 dataset proves that this algorithm improves identification efficiency, effectively solves the problem of data imbalance, and shows a better classification effect.

Intrusion detection; Class imbalance; Random forests; CUP99

TP393.08

A

10.3969/j.issn.1003-6970.2016.11.014

王浩(1992-)，男，研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。