改進數據挖掘算法在入侵檢測系統中的應用

趙艷君，魏明軍

ZHAOYanjun1,WEIMingjun2

1.河北聯合大學 理學院，河北 唐山 063009

2.河北聯合大學 信息學院，河北 唐山 063009

1.College of Science,Hebei United University,Tangshan,Hebei 063009,China

2.College of Information Engineering,Hebei United University,Tangshan,Hebei 063009,China

1 引言

隨著網絡安全問題在人們生活中的重要性不斷增強，作為新一代網絡安全技術的入侵檢測技術在網絡安全中也發揮著越來越重要的角色。與此同時，現有入侵檢測系統存在問題日益突出。現有入侵檢測大多采用模式匹配的方式檢測攻擊，需要將待檢測的數據包與規則庫中的數據一一匹配，對已知攻擊行為檢測率較高，誤報率較低，但對于已知攻擊的變種或未知攻擊卻不能檢測出來。而且，模式匹配需要事先建立一個已知攻擊的檢測規則和模式庫，并需要安全領域專家不斷進行規則庫的更新和維護，否則就會造成系統的漏報率升高。因此，提高現有入侵檢測系統的檢測率、降低漏報率具有非常重要的現實意義。

依據檢測所使用方法的不同，可以將傳統入侵檢測模型分為基于誤用的入侵檢測模型和基于異常的入侵檢測模型兩種[1-2]。基于誤用的入侵檢測模型需要建立一個已知攻擊的規則庫，并需要不斷對知識庫進行更新，才能跟蹤攻擊技術的發展，及時將新的攻擊檢測出來。因此，誤用檢測模型檢測效果的好壞很大程度上依賴于模式庫的及時更新。由此，可以看出，誤用檢測只能對已經發現的攻擊進行防護，它不具備感知未知攻擊的能力。而基于異常的入侵檢測模型是根據統計數據，給正常行為建立一個模式庫，一旦發現某種行為超出了正常行為的范圍，就會將其當做入侵，做出相應反應[3-5]。此種檢測模型的好處是對于未知攻擊有著天生的良好感知能力。但是，由于系統的活動行為是在不斷變化的，因此，需要對于正常行為模式庫也需要不斷調整，難于計算。對比這兩種檢測模型可發現，異常模型難于進行定量分析，不易實現；而誤用模型會按照事先定義好的規則，將待檢測數據與規則庫中的數據做模式匹配，實現起來相對簡單。因此，目前大多數的入侵檢測系統采用的是基于誤用的入侵檢測模型，而基于異常檢測的入侵檢測系統和二者結合的還比較少，多處于研究階段。

為了改善現有入侵檢測系統的性能，本文將誤用檢測與異常檢測結合起來，構建一個基于誤用檢測和異常檢測相結合的混合入侵檢測模型。數據挖掘的最大特點在于它能夠從繁雜的數據中發現人們未知的知識和規律，并且具有分析過程自動化、快速等優點。本模型中采用數據挖掘技術[6]實現以上提出的對入侵檢測系統的改進。利用數據挖掘中的聚類分析算法對網絡數據進行處理，建立正常行為類，以排除大部分正常數據。利用關聯規則算法實現規則集的自動擴充機制。最后使用實驗數據對兩個改進算法進行了功能驗證。

2 構建基于改進數據挖掘算法的網絡入侵檢測系統模型

2.1 系統組成

基于以上設計思路，本文構建了一個基于改進數據挖掘算法的網絡入侵檢測系統模型，如圖1所示。

圖1 基于數據挖掘的入侵檢測系統模型

圖1 中，實線表示實時部分，虛線表示非實時的部分。

模塊的基本功能與設計說明如下：

（1）數據采集與數據標準化模塊：該模塊主要負責采集網絡數據并將數據進行標準化處理，為攻擊檢測做好準備。

（2）正常行為類模塊：該模塊的作用是將收集的數據作為訓練數據，通過采用改進的聚類分析算法K-means，把訓練數據歸為幾類，提取出形成的正常行為類的特征作為類的標志，形成正常行為類模式，并將其做為正常行為過濾模塊的依據。

（3）正常行為過濾模塊：該模塊作為網絡數據在進入檢測分析引擎前的預處理程序。它利用正常行為類模塊生成的正常行為類模式，對即將要進入檢測分析引擎的數據包進行過濾，將符合正常行為類的數據過濾出來，這樣可以大大降低分析引擎的工作量。

（4）入侵檢測分析引擎模塊：該模塊將來自正常行為過濾模塊的異常行為進行進一步分析，主要采取模式匹配的方法與規則數據庫中的已知攻擊規則進行匹配，若為攻擊則響應輸出；若不是，則是未知行為，存入數據庫待下一步處理。

（5）數據分離模塊：該模塊處理的數據是經過分析引擎處理過的數據，這部分數據中會包含未知攻擊數據和正常數據，需要將兩部分數據進行分離，將未知攻擊數據提供給規則生成模塊，正常數據保存起來，用以更新正常行為類。采用的算法仍然是改進的K-means算法。

由于該模塊的功能與正常行為類模塊的實質相同，只是所處理的數據源不同，流程及過程不再重復，只需將數據換為日志記錄即可，將正常數據保存到數據集中，攻擊數據傳送給規則生成模塊。

（6）規則生成模塊：該模塊采用改進的Apriori算法，對來自數據分離模塊的未知攻擊數據進行關聯規則挖掘，將發現的未知入侵行為模式表示成規則，并將其保存到規則庫。

（7）規則數據庫：規則數據庫用于存放入侵檢測分析引擎進行模式匹配所需要的規則。

（8）數據集：開始時使用的是初始數據集KDD CUP1999。

2.2 系統工作流程

以上提出的基于數據挖掘的入侵檢測系統模型的運行過程可以分為以下幾步：

（1）建立正常行為類：①利用基于誤用的入侵檢測系統，如snort來收集網絡正常行為數據作為前期的訓練數據。②利用數據挖掘中聚類分析算法，對收集的數據進行處理，將其聚類成幾類，形成正常行為類，將其存儲到數據庫中。

（2）入侵檢測：①利用網絡嗅探器收集網絡數據包。②將數據包解碼，并將數據字段存入相應的數據結構當中。③數據進行標準化處理，為正常行為過濾做準備。④將數據與正常行為類進行比較，如果屬于其中的某類，則表明是正常數據，將其丟掉；如果不是，則將其轉交給檢測引擎進行模式匹配，作進一步分析。⑤模式匹配，如果成功，則為攻擊，那么相應模塊會做出設定措施；若不是，則該數據中可能包含新攻擊，將數據存儲起來作為產生新規則的數據集。

（3）添加新規則：利用聚類分析算法對存儲的數據進行聚類，排除小部分正常數據。然后，利用數據挖掘中的關聯規則算法作關聯分析，發現新規則并將其添加到規則庫中。

3 入侵檢測系統中算法的實現

基于改進數據挖掘算法的網絡入侵檢測系統中采用的算法是聚類分析算法（K-means）和關聯規則算法（Apriori），并對兩種算法分別進行了改進。

3.1 改進K-means算法

K-means算法[7-11]是硬聚類算法，是典型的基于聚類準則函數的聚類方法的代表，它把每個數據對象到各個類中心的某種距離之和作為進行優化的目標函數，同時采取函數求極值的方法獲得進行迭代運算的調整規則。該算法的最終目的是根據輸入的聚類個數k，將數據對象劃分為k個類。

K-means算法思想簡單、計算復雜度小，能夠滿足入侵檢測對于實時性的要求，實現起來比較簡單。但該算法本身也存在著一些急需解決的問題：

（1）無法自主確定聚類個數，需要事先輸入確定的k值。在K-means算法開始聚類前，它必須要預先確定聚類的個數k，同時隨機選擇相同個數的數據對象作為初始聚類中心。這樣的話就會造成劃分的類不是很準確，而且自主確定聚類個數也很困難，有時還需要結合相關領域的先驗知識作為參考。同時，網絡入侵檢測的過程是實時的，所以可能沒有辦法事先知道聚類的個數k，這樣也就無法選擇用做初始聚類中心的k個數據對象。

（2）通過K-means算法聚類出來的類不能確定哪個類是正常的，哪個類是異常的。但是在進行檢測的過程中卻需要通過正常行為類來排除正常數據包，減輕檢測引擎的工作量。

針對K-means算法存在的缺點，作出一些改進。

在改進的K-means算法中，引入了聚類引導函數 f(xi)，該函數可以幫助確定聚類向著點密度高的方向進行聚類。

定義1（曼哈頓距離）

式中，xi=(xi1，xi2，…，xis)，yj=(yj1，yj2，…，yjs)都是s維的數據對象。

聚類引導函數中r的計算：

其中，m為正數，可調節，通常情況下為2。

定義2（聚類引導函數）

式中，X是數據對象集合，Dist(p，xi)為數據對象 p到數據對象xi的距離，r代表距離半徑，采用曼哈頓距離計算。

數據集中的每個對象可以根據以上定義的計算方法計算出對應的聚類引導函數值，該值將會被用做聚類中選擇聚類對象的依據。

改進的K-means算法基于找到一個小范圍內具有最大聚類引導函數值 f(xi)的對象，即點密度最高的對象作為所在類的代表，每個類將會是由代表點所代表的對象和屬于該代表點的對象組成。

改進K-means算法的整個算法描述如下：

過程：

根據輸入的數據對象，計算出r及每個對象的聚類引導函數；

將每個對象看做一類，這樣就形成了n個類，每個類中只有一個代表點；

Do

對于每個類代表點 xi，尋找對象 xj，i≠j，xj到 xi的距離小于r，且 f(xj)是所有小于r對象中 f(xj)最大的；

比較 f(xi)和 f(xj)，若 f(xi)?f(xj)，則類 xj歸入類 xi中，否則，類xi不變；

Until對于每個 i=1，2，…，n ，類 xi不再發生變化。

3.2 改進Apriori算法

Apriori是由R.Agrawal等人提出的數據挖掘中經典的關聯規則算法，Apriori采取多次掃描數據庫的方法來產生頻繁項目集[12]。具體做法是：第一次掃描后只產生寬度為1的候選項目集，然后通過比較每個項目的支持度與最小支持度，將不低于最小支持度的1-階候選項目集添加到頻繁項目集中，此時形成了只包含1-階項目的最初的頻繁項目集。此后，每一次掃描，都要根據前一次產生的頻繁項目集，先構造出本次的候選項目集，然后再掃描數據庫，從候選項目集中確定出本次的頻繁項目集。重復以上過程，直到不再產生新的頻繁項目集為止。

Apriori算法是一個通用的數據挖掘算法，并不支持入侵檢測的多屬性問題。Apriori算法中的各個事務中的項目之間不存在相互關系，一個項目的存在不會影響另一個項目，任何項目組合都可以。但是，對于入侵檢測數據庫中的數據并不是如此。如果直接使用該數據庫的數據進行關聯規則，由于中間過程中會產生無效候選項，可又需要掃描數據庫計算其支持度，會大大降低該算法的效率。

根據入侵檢測領域知識，可知同一特征下的不同屬性支持度為0這一性質，可對Apriori算法作如下改進：

將Apriori算法cand-gen（）子程序改為：

4 驗證算法功能

4.1 K-means算法性能驗證實驗

實驗數據集：采用入侵檢測領域比較權威的測試數據KDD cup99[13]中的“kddcup.data_10.percent”10%數據集。

該實驗數據集中主要包括DoS、U2R、R2L和Probe四大類攻擊數據。以下分別針對這四類攻擊數據對算法性能進行檢測。

為了滿足檢測算法中兩個假設的需要，每次實驗從相應數據集中選擇2 000條記錄用于實驗，其中正常數據1 966條，入侵數據34條，正常數據在所有數據中所占比例為98.30%，滿足了檢測算法對于正常數據的數量要遠大于入侵數據數量的假設的需要。將各數據集分別在K-means和改進K-means上進行實驗，比較算法性能。檢測率越高，誤檢率越低，說明算法的檢測能力越好。

以下將采用兩種不同的角度對算法的性能進行實驗，檢測算法的性能。一種是采用單一攻擊數據集，即數據集中的攻擊數據均屬于單一類別。另一種就是混合攻擊檢測，即數據集中的攻擊數據是各種攻擊數據的混合，類別更豐富。

（1）算法對單一攻擊的檢測性能：K-means算法需要事先指定聚類個數，且不同的聚類數對算法的聚類結果有很大的影響，所以需要進行反復實驗。通過調整聚類個數得出K-means算法在各種攻擊數據集上的聚類性能如表1所示。

表1 K-means算法單一攻擊性能

改進K-means算法不需要事先指定聚類個數，可以根據數據集特定自主確定聚類個數。最終得出改進K-means算法對各種攻擊的聚類性能如表2。

表2 改進K-means算法單一攻擊性能

實驗結果分析：從表1和表2中可以看出，和K-means算法相比，改進K-means算法的單一攻擊性能中誤報率更低、檢測率更高。

（2）算法對綜合攻擊的檢測性能：K-means算法聚類性能如表3所示。

表3 K-means算法的綜合攻擊性能

改進K-means算法性能如表4。

表4 改進K-means算法的綜合攻擊性能

實驗結果分析：從表3和表4中可以看出，和K-means算法相比，改進K-means算法的綜合攻擊性能中誤報率更低、檢測率更高。

綜上所述，改進K-means算法在不需要輸入聚類個數的前提下，能夠根據數據特點找出比較適當的聚類數量。它對單種入侵和混合入侵均表現出較低的誤報率和較高的檢測率，因此，改進K-means算法是可行的。

4.2 Apriori算法性能驗證實驗

利用改進的Apriori算法實現規則自動擴充能力。首先從數據集中挖掘出頻繁項目集，進而形成關聯規則并將其存入規則庫中。

本次實驗輸出規則采用的Snort規則的格式，因此，選擇duration，protocol_type，service，flag，src_bytes和dst_bytes這六個和Snort規則相關的字段。

實現規則自動擴充功能的程序界面如圖2所示。

圖2 規則生成

根據圖2所示，生成規則的過程為：當設定最小支持度為0.2時，接著點擊“頻繁集生成”按鈕，在下面的列表框里會顯示出生成的滿足最小支持度階數最高的頻繁集，如圖2，生成兩個支持度大于0.2的頻繁集。然后，設置最小置信度為0.2時，點擊“生成強規則”按鈕，在下面列表框里將會顯示生成的滿足最小置信度的規則。如圖2，剛剛產生的頻繁集都是強規則。最后，點擊“輸出Snort規則”，程序就會將剛剛生成的強規則按Snort規則的格式寫到文本文件rules.txt中。

結論，通過規則生成程序對未知攻擊數據進行關聯規則挖掘，可以實現入侵檢測系統規則庫的擴充。

5 結束語

本文設計了一個基于數據挖掘的、將誤用檢測和異常檢測相結合的入侵檢測系統模型，并對相關模塊的工作流程及工作步驟進行了詳細的介紹。針對模型中重點模塊要實現的功能，在數據挖掘算法中選擇了合適的算法。用改進的K-means算法實現正常行為類及數據分離模塊，用改進Apriori算法實現規則庫的自動擴充功能，并通過實驗驗證了兩個算法的功能。

基于改進數據挖掘算法的入侵檢測系統模型的研究實現了入侵檢測系統的檢測率的提高和漏報率的降低，改善了整個檢測系統的檢測性能。

[1]王艷，肖維民.數據挖掘技術在入侵檢測系統中的應用研究[D].馬鞍山：安徽工業大學，2010.

[2]Verwoerd T，Hunt R.Intrusion detection techniques and approaches[J].Computer Communications，2002，25（15）：1356-1365.

[3]于琨.基于高頻統計的異常檢測方法的設計與實現[D].北京：北京郵電大學，2006.

[4]蔡堅.基于人工神經網絡的入侵檢測系統的研究與實現[D].貴陽：貴州大學，2005.

[5]武濤，王新房.基于數據挖掘的入侵檢測研究[D].西安：西安理工大學，2010.

[6]陳宇暉，傅明.基于數據挖掘的入侵檢測方法研究[D].長沙：長沙理工大學，2010.

[7]李洋.K-means聚類算法在入侵檢測中的應用[J].計算機工程，2007，33（14）：154-156.

[8]張建萍.基于聚類分析的K-means算法研究及應用[J].計算機應用研究，2007，24（5）：166-168.

[9]Chinrungrueng C，Sequin C H.Optimal adaptive k-means algorithm with dynamic adjustment of learning rate[J].IEEE Trans on Neural Networks，1995，6.

[10]嚴曉光.聚類在網絡入侵的異常檢測中的應用[J].計算機系統應用，2005（10）：34-37.

[11]馬曉春，高翔，高德遠.聚類分析在入侵檢測系統中應用研究[J].微電子學與計算機，2005，22（4）：134-136.

[12]Sun Ying.Using data mining technology solve intrusion detection of network[J].Computer Knowledge and Technology，2010，6（23）：6463-6464.

[13]張新有，賈磊.入侵檢測數據集KDD CUP99研究[J].計算機工程與設計，2010，31（22）：4809-4812.