基于隨機森林和加權K均值聚類的網絡入侵檢測系統

任曉芳，趙德群，秦健勇

?

基于隨機森林和加權K均值聚類的網絡入侵檢測系統

任曉芳，趙德群，秦健勇

摘 要：目前，許多誤用檢測系統無法檢測未知攻擊，而異常檢測系統雖然能夠精確檢測未知攻擊，但具有較高的誤報警率。為此，提出了一種基于隨機森林和加權 K均值聚類算法的混合入侵檢測系統。首先，利用隨機森林算法從訓練集中建立入侵模型，構建誤用檢測模型，通過網絡連接的特征匹配來檢測已知攻擊。然后，利用加權 K均值算法構建異常檢測模塊，根據隨機森林算法獲得的特征，將不確定性攻擊的網絡連接數據進行聚類，進而實現未知攻擊的檢測。在KDD'99數據庫中的實驗表明，該系統具有較高的檢測率和較低的誤報警率。

關鍵詞：入侵檢測系統；隨機森林；加權K-均值聚類；誤用檢測；異常檢測

0　引言

當前計算機網絡盡管具有多重安全策略，譬如，訪問控制、加密以及防火墻的應用，然而，網絡安全的漏洞還是與日俱增。因此，迫切需要智能的入侵檢測系統（Intrusion Detection System，IDS）來自動地檢測新型的入侵行為[1]。

目前，主要有兩種入侵檢測方法：誤用檢測和異常檢測[2]。誤用檢測只能檢測出數據中已知的入侵模式，無法檢測新出現的入侵行為，且需要實時的更新數據庫[3]。異常檢測系統能夠檢測出新的入侵行為，但通常具有較高的誤報警率[4,5]。為了解決誤用檢測和異常檢測的這些缺點，則需要采用混合入侵檢測的技術。為此，文獻[6]提出一種基于增量式神經網絡的入侵檢測系統，解決了神經網絡離線訓練所帶來的問題，對在線檢測過程中新出現的攻擊類型進行增量式學習，實現對入侵檢測模型的動態擴展。文獻[7]提出了一種非監督異常檢測框架，其利用集群估算、K-鄰近和支持向量機（SVM）進行入侵檢測。然而，該系統所需的特征維數很高，計算效率低。文獻[8]提出一種基于隨機森林算法的入侵檢測系統，其首先使用基于Snort 的誤用檢測組件過濾掉網絡數據中的已知攻擊，然后將數據被送入基于隨機森林算法的異常檢測組件對新型攻擊進行檢測。然而，該系統中，由于入侵檢測審計數據具有較多不相關屬性，隨機森林選擇屬性時易出現過度隨機現象，導致誤報警率較高。

為此，本文提出一種基于隨機森林和加權 K均值算法的混合入侵檢測系統。首先，利用隨機森林算法從訓練集中構建誤用檢測模型，通過網絡連接的特征匹配來檢測已知攻擊。然后，利用加權 K均值算法構建異常檢測模塊，根據隨機森林算法獲得的特征，對未知攻擊進行檢測。實驗結果表明，本文系統具有較高的檢測率和較低的誤報警率。

1　提出的混合入侵檢測總體框架

提出的混合入侵檢測框架由兩個階段組成：在線階段和離線階段。

在線階段為誤用檢測部分，主要通過比較網絡連接數據來產生入侵模式，如果檢測到有任何入侵，將會產生誤用預警，同時將這個攻擊的特征傳遞到異常檢測部分，進行攻擊類型識別。如果連接特征不匹配任何攻擊，那么將這種連接作為不確定數據，其可能是一種新型的攻擊，然后，將其傳遞到異常檢測部分的數據預處理器和合并組件，用于核實它是否為入侵還是正常連接。

離線階段利用訓練數據集構建入侵模式，用于在線階段中的誤用檢測。這種模式構建器也會輸出異常檢測部分中隨機森林算法計算出的特征的重要度值。離線部分也包含了異常檢測部分所有的分量，其合并來自誤用檢測部分中不確定數據與選取的隨機攻擊，并利用這種數據來創建異常檢測數據庫。隨后，利用加權k-均值算法作為一種數據挖掘聚類算法,用于聚合連接數據并將其存儲到異常檢測數據庫中。

異常檢測器分量用來根據已知入侵的數量來排序集群，從而確定異常的和正常的集群。最終，當異常預警系統分量檢測到異常群集時，就會產生了一次警報，并把這些異常連接傳遞到誤用檢測部分的訓練數據庫，添加到入侵模式中。提出的混合入侵檢測框架如圖1所示：

圖1　提出的混合入侵檢測框架

2　基于隨機森林算法的誤用檢測

2.1 隨機森林算法

隨機森林算法是一種分類算法，由一批樹狀結構的分類器組成，每個樹狀結構對每個輸入值進行逐個單元的表決，其決策結果是通過類似多數投票法來確定的，從而選出最常見的類別。其中，其基礎分類器通常采用無剪裁的決策樹[9]。

隨機森林的執行過程為：

（1）選取訓練集。RF算法抽取訓練集方法與Bagging中的方法類似，即如果需要構建 K個基礎分類器，則對數據集作K次抽樣（每次抽樣均為隨機且不放回）。

（2）構建RF模型。假設訓練數據集中具有M個屬性，從M個屬性中隨機抽取F個屬性作分類屬性集。然后，采用CART方法構建單棵決策樹（基礎分類器），不限制每棵決策樹的生成，且不進行任何剪枝。

（3）投票。RF集群分類器采取多數投票法來進行決策，利用所構建的 K棵決策樹將對某條數據進行分類，最后進行投票，將得票最多的作為RF的最終輸出結果。對于得票數相同的情況，通常從中隨機選取一個作為最終結果。

隨機森林算法中，通過采用2次隨機過程來提高算法性能：1）為單棵決策樹隨機選取訓練數據，且不做任何剪枝，這樣能夠一定程度上避免單棵樹出現過擬合現象；2）對整體而言，隨機地選取屬性子集來構建決策樹，一定程度上提升了決策樹的抗噪性能[10]。

鄰近度是隨機森林算法中最實用的工具之一，隨機森林使用鄰近度來發現離群點。當隨機森林被構建完成后，數據集中的所有樣例被分別送入森林中的每棵樹。如果樣例k和n在一顆樹中被劃分到同一個葉節點，說明它們的鄰近度為1。最后，需要把鄰近度除以森林中樹的總數以進行標準化，離群點的計算如下所述。

規定，class(k) = j 表示樣例k屬于類j，prox(n，k)代表n和k的鄰近度。則第j類的樣本n的平均鄰近度為公式（1）：

上式中，k為類j中除了n剩余的樣例。定義原始離群值為公式（2）：

公式（2）中，N表示數據集中樣例的總數。如果平均鄰近度很小的話，將得到一個很大的原始離群值，所以需要對它進行一些處理。首先，在每個分類中，分別計算原始離群值的中值和絕對偏差。然后，用每個原始離群值減去中值，再把得到的結果除以絕對偏差，這樣就得到了最終的離群值。如果樣例的離群值相對較大而鄰近度很小，此樣例就被視為離群點。

2.2 誤用檢測

采用隨機森林算法作為數據挖掘分類算法，來進行誤用檢測，其基本結構如圖2所示：

圖2　誤用檢測方法框架

隨機森林算法的操作分為兩個階段：訓練階段和檢測階段。訓練階段用來離線構建基于訓練數據集的入侵和正常模式；檢測階段基于訓練階段產生模式在線檢測網絡入侵。

訓練階段中，將一個標記過的訓練數據集經過一些預處理后輸入到隨機森林中，從而構造檢測所需要的入侵模式。在線階段中，網絡感應器捕獲網絡封包，經過一些預處理后基于訓練產生的模式將其轉換為網絡特征數據庫。然后，利用誤用檢測器對網絡特征數據庫進行分類，分類為正常或入侵狀態。如果發現入侵，預警系統就會發出警報。

3　基于加權K-均值算法的異常檢測

3.1 加權K-均值算法

K-均值[11]算法是一種簡單的迭代方法，其使用歐幾里得度量來量化點之間的距離，從而把一個數據集劃分成特定數目K的集群。首先，其隨機挑選一個K點作為起始時K集群的“質心”，然后，算法迭代以下兩步直到收斂：

第一步：把每個點分配到離它最近的質心。

第二步：移動每個質心到所分配點的均值上。

假定，一個數據集I擁有N個對象、具有M個特征的集合V和一個實體特征矩陣，其中yiv為當i∈I時特征的值。算法將數據集I劃分為K個集群，其中，為一個集群。每個集群都通過質心來表示，然后，將到每個集群質心間距離之和作為判斷標準[12]為公式（3）：

加權k-均值是k-均值算法的一種變型，其包含了所有數據特征的權重。因此，判斷公式（1）修改為公式（4）：

K-均值算法假定所有的特征對輸出類別都有相同的作用，但是，根據本文誤用檢測實驗表明，隨機森林算法能夠產生特征重要性的值，反映了所有特征對于輸出類標簽的正確性上的作用比例。因此，選出這些特征重要度值，并通過標準化來使其滿足總和相同的條件，當β=1時，將公式（2）的值標準化來代替權重矢量wv。

3.2 異常檢測

提出的異常檢測方法如圖3所示：

圖3　異常檢測方法框架

采用 K-均值算法作為一種數據挖掘聚類算法來檢測新型入侵。首先，捕捉網絡連接數據并進行預處理，將其轉換為一個異常檢測數據集。然后，使用 K-均值算法把數據集劃分成均等的集群。最后，利用異常檢測器判定集群為異常或正常。當檢測出異常集群時，系統就會發出異常預警。

4　實驗及分析

4.1 誤用檢測器性能實驗

首先，對基于隨機森林算法的誤用檢測器進行性能測試，用來確定最優算法參數。利用KDD'99數據集作為訓練和測試數據集，數據集包括正常連接和4個主要的入侵類別[13]：Probe（探測和掃描），DoS（拒絕服務攻擊），U2R（非法獲得超級用戶權限）以及R2L（來自遠程的非授權訪問）。實驗中，選取4,898,431個連接數據作為訓練集，選取311,029個連接數據作為測試集。訓練集和測試集中的各種類型數據量如表1所示：

表1　訓練和測試數據集中的各種連接類型的總數

隨機森林算法中，有兩個重要參數會顯著影響算法的性能：1）用于分割每個樹狀節點的隨機特征的數目（Mtry）；2）生長在森林中樹的數目（Jbt）。為了獲得較低的錯誤率，通過構建具有不同Mtry和 Jbt值的森林進行實驗，比較獲得的檢測率，以此來優化參數。其中，在不同Jbt值下的實驗結果如圖4所示。

圖4　在森林中不同樹數量下的錯誤率

實驗結果表明，當設置Mtry=21，Jbt=20時，算法的性能最好。此時，算法獲得的最低錯誤率為7.27%，假陽性率為0.54%，檢測率為91.23%。

4.2 異常檢測性能實驗

然后，對基于加權 K-均值的異常檢測器進行性能評估實驗。基于KDD'99數據庫，構建了4數據集，每個數據集都是從10%的KDD'99數據集共計30，000個連接中隨機選取。每個數據集中的入侵連接注入百分比為 1%，2%，5% 和10%。

將本文方案與文獻[7]和文獻[8]方案進行比較，文獻[7]提出了一種非監督異常檢測框架，其利用集群估算、K-鄰近和支持向量機（SVM）進行入侵檢測。文獻[8]也提出了一種非監督異常檢測框架，其使用了隨機森林算法構建異常檢測器。在不同的入侵連接比例下，進行實驗，結果如表2所示。

表2　本文方法和文獻[7,8]中方法的比較

結果表明，本文方法比文獻[7,8]方法獲得了較高的檢測率和較低的假陽性率，特別在具有5%和10%入侵數據的數據集中的性能提升最為明顯，此時本文檢測率都達到了98%以上，而假陽性率都在4%以下。

5　總結

本文研究了基于數據挖掘的網絡入侵檢測系統，利用兩種數據挖掘技術實現誤用、異常和混合入侵檢測。首先，利用隨機森林算法對訪問數據進行挖掘分類，將捕捉到的網絡連接進行分類，構建入侵模式，用于誤用檢測。然而，誤用檢測的主要缺陷是在沒有得到訓練之前，它不能檢測新型的入侵。為此，本文利用加權 K-均值算法構建一種非監督異常檢測模型，通過把捕捉的網絡連接分為特定數目的集群，根據他們的特征來檢測異常集群。然而，異常檢測的主要缺陷是較高的假陽性率。所以，本文將隨機森林算法和加權k-均值算法相結合，構建一個混合入侵檢測模型。通過隨機森林算法來計算特征的重要度值，用于誤用檢測來提升異常檢測分量的檢測率。在KDD'99數據庫中的實驗表明，本文混合入侵檢測模型獲得了較高的檢測率和較低的假陽性率。

在未來的工作中，將考慮采用流數據挖掘技術來提高檢查速度。此外，將在真實網絡中進行更多的實驗，進一步驗證本文檢測模型的效率。

參考文獻

[1] 肖寅東, 王厚軍, 田書林. 高速網絡入侵檢測系統中包頭解析方法[J]. 儀器儀表學報, 2012, 33(6):1414-1419.

[2] 高苗粉, 秦勇, 李勇,等. 網絡入侵檢測系統自體集檢測中的概率匹配高效尋優機制[J]. 計算機應用, 2013, 33(1):156-159.

[3] Elngar A A, El A M D A, Ghaleb F F M. A Real-Time Anomaly Network Intrusion Detection System with High Accuracy[J]. Information Sciences Letters, 2013，35(3):49-56.

[4] Subaira. A S, Anitha. P. A Survey: Network Intrusion Detection System based on Data Mining Techniques[J]. International Journal of Computer Science & Mobile Computing, 2013, 2(10):174-185.

[5] 龔尚福, 趙春蘭, 厙向陽. 基于 R-SVM 的網絡入侵檢測系統[J]. 計算機工程與設計, 2012, 33(10):3777-3782.

[6] 趙建華, 李偉華. 有監督SOM神經網絡在入侵檢測中的應用[J]. 計算機工程, 2012, 38(12):110-111.

[7] Hsieh C F, Cheng K F, Huang Y F, et al. An Intrusion Detection System for Ad Hoc Networks with Multi-attacks Based on a Support Vector Machine and Rough Set Theory[J]. Journal of Convergence Information Technology, 2013，26(5):269-281.

[8] Hong H U, Chen Y P. Research on Hybrid Intrusion Detection System Based on Random Forest Algorithm[J]. Journal of Xian University of Arts & Science, 2013，37(8):28-39.

[9] 姚登舉, 楊靜, 詹曉娟. 基于隨機森林的特征選擇算法[J]. 吉林大學學報：工學版, 2014, 44(1):137-141.

[10] Pal B. Support Vector Machine and Random Forest Modeling for Intrusion Detection System (IDS)[J]. Journal of Intelligent Learning Systems & Applications, 2014, 6(1):45-52.

[11] 傅濤, 孫亞民. 基于PSO的k-means算法及其在網絡入侵檢測中的應用[J]. 計算機科學, 2011, 38(5):54-55.

[12] Yan-Qun X U, Zhang B, Qin X T. Clustering Intrusion Detection Model Based on Grey Fuzzy K-mean Clustering[J]. Journal of Chongqing Normal University, 2013, 30(1):81-83.

[13] Koc L, Mazzuchi T A, Sarkani S. A network intrusion detection system based on a Hidden Na?ve Bayes multiclass classifier[J]. Expert Systems with Applications, 2012, 39(18):492–500.

中圖分類號：TP393

文獻標志碼：A

文章編號：1007-757X(2016)07-0021-04

收稿日期：（2015.12.30）

基金項目：新疆維吾爾自治區自然科學基金項目（2013211A031）；新疆工程學院人文基金項目（2014xgy311612）

作者簡介：任曉芳（1979-），女，新疆工學院，計算機工程系，碩士，講師，研究領域：網絡安全、算法設計等，烏魯木齊，830023趙德群（1964-），男，新疆工學院，計算機工程系，碩士，副教授，研究領域：網絡安全、物聯網等，烏魯木齊，830023秦健勇（1978-），男，新疆工學院，計算機工程系，碩士，講師，研究領域：網絡安全、智能算法等，烏魯木齊，830023

Network Intrusion Detection System Based on Random Forests and K-means Clustering Algorithm

Ren Xiaofang, Zhao Dequn, Qin Jianyong
(Xinjiang Institute of Engineering, Department of Computer Engineering, Urumqi 830023, China)

Abstract:Currently， a lot of misuse detection system can’t detect unknown attack, while the anomaly detection system can detect unknown attacks accurately, but has a high false alarm rate. A hybrid intrusion detection system based on random forest and weighted K-means clustering algorithm is proposed. Firstly, it uses the random forest algorithm to set up the intrusion model from the training set, construct the misuse detection model, and detect the known attacks by the feature matching of the network connection. Then, the anomaly detection module is constructed by using the weighted K-means algorithm, and the network connection data of the non deterministic attacks are clustered according to the characteristics obtained by the random forest algorithm. Experiments on KDD'99 database show that the system has high detection rate and low false alarm rate.

Key words:Intrusion Detection System; Random Forests; Weighted k-means Clustering; Misuse Detection; Anomaly Detection