基于隨機森林和加權(quán)K均值聚類的網(wǎng)絡(luò)入侵檢測系統(tǒng)

任曉芳，趙德群，秦健勇

?

基于隨機森林和加權(quán)K均值聚類的網(wǎng)絡(luò)入侵檢測系統(tǒng)

任曉芳，趙德群，秦健勇

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

關(guān)鍵詞：入侵檢測系統(tǒng)；隨機森林；加權(quán)K-均值聚類；誤用檢測；異常檢測

0　引言

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

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

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

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

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

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

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

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

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

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

2.1 隨機森林算法

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

隨機森林的執(zhí)行過程為：

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

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

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

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

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

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

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

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

2.2 誤用檢測

采用隨機森林算法作為數(shù)據(jù)挖掘分類算法，來進行誤用檢測，其基本結(jié)構(gòu)如圖2所示：

圖2　誤用檢測方法框架

隨機森林算法的操作分為兩個階段：訓(xùn)練階段和檢測階段。訓(xùn)練階段用來離線構(gòu)建基于訓(xùn)練數(shù)據(jù)集的入侵和正常模式；檢測階段基于訓(xùn)練階段產(chǎn)生模式在線檢測網(wǎng)絡(luò)入侵。

訓(xùn)練階段中，將一個標(biāo)記過的訓(xùn)練數(shù)據(jù)集經(jīng)過一些預(yù)處理后輸入到隨機森林中，從而構(gòu)造檢測所需要的入侵模式。在線階段中，網(wǎng)絡(luò)感應(yīng)器捕獲網(wǎng)絡(luò)封包，經(jīng)過一些預(yù)處理后基于訓(xùn)練產(chǎn)生的模式將其轉(zhuǎn)換為網(wǎng)絡(luò)特征數(shù)據(jù)庫。然后，利用誤用檢測器對網(wǎng)絡(luò)特征數(shù)據(jù)庫進行分類，分類為正常或入侵狀態(tài)。如果發(fā)現(xiàn)入侵，預(yù)警系統(tǒng)就會發(fā)出警報。

3　基于加權(quán)K-均值算法的異常檢測

3.1 加權(quán)K-均值算法

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

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

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

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

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

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

3.2 異常檢測

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

圖3　異常檢測方法框架

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

4　實驗及分析

4.1 誤用檢測器性能實驗

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

表1　訓(xùn)練和測試數(shù)據(jù)集中的各種連接類型的總數(shù)

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

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

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

4.2 異常檢測性能實驗

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

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

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

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

5　總結(jié)

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

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

參考文獻

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

[2] 高苗粉, 秦勇, 李勇,等. 網(wǎng)絡(luò)入侵檢測系統(tǒng)自體集檢測中的概率匹配高效尋優(yōu)機制[J]. 計算機應(yīng)用, 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 的網(wǎng)絡(luò)入侵檢測系統(tǒng)[J]. 計算機工程與設(shè)計, 2012, 33(10):3777-3782.

[6] 趙建華, 李偉華. 有監(jiān)督SOM神經(jīng)網(wǎng)絡(luò)在入侵檢測中的應(yīng)用[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]. 吉林大學(xué)學(xué)報：工學(xué)版, 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算法及其在網(wǎng)絡(luò)入侵檢測中的應(yīng)用[J]. 計算機科學(xué), 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

文獻標(biāo)志碼：A

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

收稿日期：（2015.12.30）

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

作者簡介：任曉芳（1979-），女，新疆工學(xué)院，計算機工程系，碩士，講師，研究領(lǐng)域：網(wǎng)絡(luò)安全、算法設(shè)計等，烏魯木齊，830023趙德群（1964-），男，新疆工學(xué)院，計算機工程系，碩士，副教授，研究領(lǐng)域：網(wǎng)絡(luò)安全、物聯(lián)網(wǎng)等，烏魯木齊，830023秦健勇（1978-），男，新疆工學(xué)院，計算機工程系，碩士，講師，研究領(lǐng)域：網(wǎng)絡(luò)安全、智能算法等，烏魯木齊，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