王 浩

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

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

王 浩

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

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

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

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

0 引言

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

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

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

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

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

1 隨機(jī)森林算法

1.1 采樣過程

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

1.2 Bagging算法

Baggin[9]是一種并行式的集成算法。通過多次的采樣過程，我們得到了T個含有m個樣本的數(shù)據(jù)集，針對每一個數(shù)據(jù)集，訓(xùn)練出一個基學(xué)習(xí)器模型，通過投票的方式選出最佳的投票結(jié)果，這可以當(dāng)做是最終預(yù)測的類別。每個基學(xué)習(xí)器都是弱學(xué)習(xí)算法，但是投票后的準(zhǔn)確率將得到大幅度提高。如果出現(xiàn)投票一致的情況，最簡單的方式是隨機(jī)選取一個，也可以選用置信度來決定最終的結(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)的水平上，是一個比較高效的算法。

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

泛化誤差為：

1.3 隨機(jī)森林算法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果及分析

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

3.2 實驗結(jié)果及分析

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

3.1 實驗設(shè)置

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

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

4 結(jié)束語

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

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

[2] 滕少華. 基于對象監(jiān)控的分布式協(xié)同入侵檢測[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-)，男，研究生，主要研究方向為計算機(jī)網(wǎng)絡(luò)。