基于隨機森林的網絡攻擊檢測方法

王 浩

(北方工業大學計算機學院，北京 100144)

基于隨機森林的網絡攻擊檢測方法

王 浩

(北方工業大學計算機學院，北京 100144)

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

攻擊檢測；數據不平衡；隨機森林；CUP99

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

0 引言

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

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

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

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

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

1 隨機森林算法

1.1 采樣過程

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

1.2 Bagging算法

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

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

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

泛化誤差為：

1.3 隨機森林算法

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

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

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

2 在網絡攻擊檢測中應用隨機森林算法

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

2.1 數據采集與分析

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

2.2 數據預處理

我們取用cup99的10%的數據集，為了適應隨機森林算法，需要對數據集進行預處理。首先需要對字符屬性進行轉換，轉換成數字格式。其次需要對回歸屬性值進行離散化，由于隨機森林是基于樹的算法，而ID3只支持離散型變量，C4.5和CART不適合23種類別的分類的問題，故需要手動進行離散化。

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

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

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

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

3 實驗結果及分析

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

3.2 實驗結果及分析

隨機森林，Wenka Lee的算法，BP神經網絡，SVM算法在KDD CUP99數據集[14][15]中關于網絡攻擊識別的結果由表1可以看出。

3.1 實驗設置

表1 幾個算法的準確率比較

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

4 結束語

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

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

[2] 滕少華. 基于對象監控的分布式協同入侵檢測[D]. 廣東工業大學, 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-)，男，研究生，主要研究方向為計算機網絡。