基于改進K均值算法的入侵檢測系統設計

劉華春，候向寧，楊 忠

(成都理工大學 工程技術學院,四川 樂山 614007)

基于改進K均值算法的入侵檢測系統設計

劉華春，候向寧，楊 忠

(成都理工大學 工程技術學院,四川 樂山 614007)

傳統的入侵檢測系統是將規則庫與網絡數據包逐一匹配，進行檢測，當網絡數據量巨增時，檢測效率顯著降低，甚至面臨不能即時檢測的巨大挑戰。數據挖掘是從海量的數據中挖掘發現需要的各種有價值信息的技術，入侵檢測系統中植入數據挖掘技術，將極大提高入侵檢測系統的檢測效率和智能性。研究了數據挖掘中K-means聚類算法應用于入侵檢測領域中的難點問題。K-means算法具有易受初始K值和孤立點影響，難以確定K值，對初始質心依賴程度高等不足問題。針對上述缺點，提出了改進的K-means聚類算法。設計了基于改進K-means的入侵檢測系統并進行了實驗。結果表明，將改進的聚類算法應用于入侵檢測可顯著提高異常檢測效率；可自適應地建立入侵檢測異常模式庫；對未知的入侵攻擊能有效防范；能進一步降低誤檢率。

數據挖掘；入侵檢測；聚類算法；異常檢測

0 引 言

傳統的入侵檢測系統(Intrusion Detection System,IDS)是采取分析和提取入侵模式和攻擊特點，建立檢測規則庫及模式庫，所以傳統IDS在檢測效率和智能性上存在明顯不足。在網絡帶寬快速提高，入侵和攻擊模式不斷變化的新形勢下，傳統IDS的檢測方式、檢測效率面臨巨大挑戰，甚至不能即時響應和檢測。數據挖掘(Data Mining,DM)能夠從海量數據中根據不同的挖掘算法，挖掘出具有不同用途的知識和信息。因此，可以將數據挖掘技術植入到IDS中，應用適當的挖掘算法，就可解決前文提出的IDS效率和自適應問題。目前，DM+IDS已成為入侵檢測領域的一個重要研究方向。數據挖掘應用于入侵檢測系統的研究，在國內外都有很多的研究機構及大學在進行，已取得了一定的研究成果，但總體仍處于初始階段。

文中將數據挖掘技術應用于入侵檢測系統，對于入侵檢測系統具有較大的實際應用價值。

1 入侵檢測與數據挖掘

1.1 入侵檢測技術

入侵檢測的原理是通過從網絡中特定點收集和分析網絡數據,以判別該網絡中是否存在被攻擊或違反安全策略的行為。入侵檢測系統對網絡進行實時監測和控制，所以能夠提供對各種錯誤配置和來自網絡內部、外部攻擊的防范[1-2]。入侵檢測系統能及時發現入侵行為，并產生警報信號，因此極大地提高了網絡系統的安全性。

入侵檢測工作過程主要由數據采集、數據分析和響應三個步驟組成。美國互聯網工程任務組(IETF)為入侵檢測系統制定了標準，并發起制訂了系列的建議草案[3]，提出了入侵檢測系統框架模型。此模型把一個入侵檢測系統分解為事件產生器、事件分析器、事件數據庫和響應單元四個部分[4]。事件產生器進行網絡數據的抓取和預處理，事件分析器進行規則的分析匹配，事件數據庫存放規則模式，響應單元產生動作執行操作。根據采用的檢測方法，入侵檢測技術可分為異常檢測和誤用檢測。

1.2 數據挖掘

數據挖掘又稱數據庫中的知識發現(Knowledge Discover in Database，KDD)，能夠從大量的、海量的數據中提取出未知的、并具有用戶期望價值的信息。數據挖掘技術已廣泛應用于機器學習、模式識別、人工智能、統計學等領域，是一個決策支持的過程。數據挖掘高度自動地分析海量數據，進行推理、歸納，挖掘出潛在的模式和規則，用戶根據挖掘結果調整策略，進行決策，可有效降低風險，提高決策的正確率[5]。數據挖掘的過程，根據其工作內容，可分為數據準備、數據挖掘、挖掘結果的解釋與評價三個階段，也是針對具體應用項目的數據分析和處理過程[6]。應用于不同領域的數據挖掘，其數據內容、數據格式、挖掘算法，應根據具體的挖掘目標而進行設計。數據挖掘技術可分為以下幾種類型：關聯規則、序列模式、分類、聚類等[7]。

在傳統的入侵檢測系統中植入數據挖掘技術，研究探索適當的數據挖掘算法，通過從海量網絡數據中，過濾掉正常數據模式，只提取異常入侵模式，智能地構建入侵檢測模型，就可以極大地提高傳統入侵檢測系統的檢測效率，并拓展其自適應性，從而降低傳統IDS的誤檢率[8]。

2 聚類算法K-means研究

2.1 原始K-means算法

K-means算法的主要思想是將輸入數據按照一定的方法劃分到不同的類中，在同一個類中的數據，數據特征具有最大的相似性，在不同類中的數據，其數據特征具有最大的相異性[9]。

若有數據集D，其中有N個數據，每一個數據Xi有q維特征，由q維特征屬性描述一個數據，即Xi=(Xi1,Xi2,…,Xiq)，Xi∈D，1

(1)從數據集D中隨機選擇一個數K(需滿足K

(2)第一個聚類中心為第一個數xi。計算每一個數據xi到各個聚類中心的距離d(xi,rj),1

(3)當增加一個數據到類中后，計算聚類中所有數據的屬性均值，重新得到了新的聚類中心。

(4)計算準則函數。

(5)用準則函數是否收斂判別是否要繼續,如果收斂，轉到結束；如果不收斂，返回到第(2)步，進入新的一輪迭代過程，迭代計數器s=s+1。

(6)結束，顯示聚類結果。

K-means算法具有很多優點：算法簡單；容易理解，易實現；能快速處理較大量的數據；當各個類相差明顯時，能快速識別；算法的復雜度低，為線性的；具有良好的擴展性[10-11]。

K-means算法存在如下缺陷：

(1)初始化聚類中心K值，對聚類結果的影響較大，選取不同的K值，得到的聚類結果有較大差異。而K值通常需要進行實驗確定，也可根據經驗來確定，沒有一個通用的方法來確定。當K值取法不當時，會導致聚類結果的質量下降[12]。

(2)孤立點對聚類結果有較強影響，而且，在聚類算法處理時，數據的輸入順序會影響聚類結果[13]。

(3)K-means算法中數據對象之間的距離是用歐氏距離來表示。這樣只能處理連續型數值而不能處理離散型數據對象[14]。網絡數據中一些數據特征值是連續型數值，而一些是離散型的，如數據幀標志、類型等。K-means算法無法直接處理這些離散特征數據。

2.2 IDSK-means算法

由于K-means算法的缺陷，不能直接應用于入侵檢測，文中將對其進行改進，將改進的K-means算法稱為IDSK-means算法。

2.2.1IDSK-means算法設計

對于聚類個數K值確定困難的缺陷，提出一種預定距離的聚類算法。該算法的思路為，預先確定一個聚類半徑r，第一個聚類中心以第一個數據為中心。第二個數據獲取后，計算與前聚類中心的距離，若小于r，則將第二個數歸到這個類中，重新計算該類的中心數值。若大于等于r，以第二個數據作為一個新類的中心。依次類推，后面到達的數據，計算其與已有各個類中心的距離，小于r則歸入該類，大于r則為一個新類中心。

對于提高檢測效率，確定聚類結果是正常數據模式還是入侵數據模式的問題。將正常聚類模式和異常聚類模式分別放在正常行為表和異常行為表中。預先設定一個閾值參數β，當某一類成員的數目與所有成員比例大于或等于β時，表明該類是一個正常數據類，反之為入侵數據的聚類。由于在網絡中，正常數據的數量遠大于入侵數據的數量；將正常數據過濾掉，只保留異常的疑似入侵的數據進行下一階段的檢測，可以極大提高檢測效率。

對于傳統K-means聚類算法只能處理數字量，而無法處理離散量的問題，將離散屬性轉化為0和1的數值屬性，采用離散屬性值出現的頻率進行量化，把最高的值作為聚類中心的值，再利用K-means算法進行聚類分析。

2.2.2IDSK-means算法流程

Step1：

input：訓練數據和半徑參數r；

output：訓練數據的聚類C1,C2,…,Ck。

算法流程：

(1)將輸入的訓練數據集T歸一化預處理，減少特定較大數據對聚類結果的影響。

(2)讀入數據集T中的第一個數據X1，以X1為中心值，構造聚類C1。

(3)重復(2)，讀入下一個數。

(4)讀入數據集T后續的數據Xi,i=1,2,…,n。計算每一個數Xi與已有的類Cj中心值的距離d(Xi,Cj)。

(5)若d(Xi,Cj)≤r，將Xi歸入到Cj類，即Xi屬于Cj類中；再新計算Cj類的中心值,將Cj類的成員加1。

(6)若d(Xi,Cj)>r，將Xi作為中心值，創建一個新的類。

(7)重復輸入的數據，直到全部數據結束。

Step2：

input：C1,C2,…,Ck，閾值β。

output：正常數據的聚類和異常數據的聚類。

算法流程：

(1)若某一個聚類中，其成員數目與全部數據之比大于或等于參數值β，則該類為正常行為數據的聚類，將其移入正常聚類表，構造正常行為模式庫。

(2)若某一類中，其成員數目與全部成員之比小于參數值β，則該類為異常行為數據的聚類，把其放入異常聚類表，構建異常行為模式庫。

Step3：

孤立點的處理，文中采用基于統計的方法，對聚類算法運行后，生成的每一個類i，計算類i中數據成員所占的比率q(i)值，根據q(i)值進行排序，q(i)值越小，表明i中的成員數據越不適合這個類，可能是個孤立點，取q(i)值最小的類i作為孤立點，從該類中刪除。然后將孤立點重新進行聚類，直到所有孤立點數據全部放到合適的類中為止。這樣能有效減少因輸入數據的順序而形成孤立點后，對聚類結果的影響。

3 基于數據挖掘的入侵檢測系統

系統設計遵循通用入侵檢測系統模型(CIDF)，文中在CIDF模型的基礎上，引入數據挖掘技術，將改進的聚類算法IDSK-means應用于入侵檢測，增加了聚類分析模塊。

3.1 系統結構

該入侵檢測系統的結構設計，包括通用IDS結構的部分，即事件產生器、事件分析器、事件數據庫、響應單元部分外，還包括數據挖掘模塊部分，即聚類分析、關聯規則分析共計六大模塊，如圖1所示。

圖1 基于改進聚類算法的入侵檢測結構

各模塊詳細功能如下：

事件產生器：包括數據包嗅探器和預處理器兩個子模塊。從網絡中捕獲數據包，并將獲取的數據包進行分析解碼處理后，供后面的模塊使用。

聚類分析器：采用IDSK-means算法構建網絡正常行為模式庫和異常行為模式庫。

事件數據庫：存放異常入侵規則模式數據，并維護異常入侵規則數據，供誤用檢測和關聯規則進行模式檢測。

事件分析器：分析和處理網絡數據，包括異常檢測和誤用檢測兩個模塊。實現過濾和檢測雙重功能。

(1)過濾功能：異常檢測模塊通過網絡正常行為模式和異常模式對輸入的網絡數據進行模式識別，把正常的網絡數據過濾，保留異常網絡數據送誤用檢測。

(2)檢測功能：誤用檢測將異常檢測過濾后通過的疑似入侵數據與異常事件數據庫中的入侵規則進行檢測，判斷該數據是哪一類入侵數據。

響應單元：當誤用檢測為異常數據時，產生入侵行為觸發，讓IDS產生動作，阻止入侵行為繼續發生，通過報警，記錄到日志文件，通知防火墻切斷該連接，通知管理員等。

關聯規則分析：將入侵的網絡數據進行關聯挖掘，挖掘出入侵行為與異常數據之間的關聯關系，并將其轉化為入侵規則，添加到入侵規則庫中。

3.2 工作流程

該入侵檢測系統的工作流程設計為兩個階段，分別為訓練和檢測階段，如圖2所示。

圖2 入侵檢測系統工作流程

1)訓練階段:如圖2中1流程所示，系統在訓練階段要將大量的網絡數據作為訓練數據存入數據庫。

(1)根據數據取出關鍵特征進行預處理。

(2)采用IDSK-means聚類算法對數據進行聚類分析。

(3)提取網絡數據正常模式和異常入侵數據模式。

(4)過濾正常網絡數據。

2)檢測階段:如圖2中2流程所示。

(1)輸入網絡數據。

(2)對數據進行預處理。

(3)正常網絡數據過濾，將網絡數據與模式庫中的數據進行匹配，如果為正常數據，過濾掉，提高系統的檢測效率。

(4)將入侵數據送誤用檢測，判斷該入侵數據為哪一類攻擊。

(5)觸發響應模塊，報警。

(6)如沒有與入侵規則庫匹配成功，該數據為未知攻擊類型，則由關聯規則挖掘出攻擊行為與數據的關系，將其添加到入侵規則庫中，使系統具備了發現未知攻擊的能力。

3.3 仿真實驗

3.3.1 實驗設計

實驗數據采用KDD CUP99數據集[15]，通常采用該數據來對設計的IDS進行各種性能測試。其中的所有數據都是在實際運行的互聯網環境下，模擬真實攻擊的情景得到的數據，數據格式如下：

0,tcp,http,SF,51,8127,0,0,0,2,0,1,0,1,0,0,0,0,1,0,0,0,1,2,0.00,0.00,0.00,0.50,1.00,0.00,1.00,255,255,1.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,phf

該數據集的每一個數據由42個屬性值構成，其中有數值型屬性，也有離散型屬性，第42個屬性標識該數據記錄是正常行為產生的數據，還是入侵行為產生的數據。

該實驗的目的是驗證改進的IDSK-means算法的有效性及性能分析。實驗中，采用數據集的10%來測試設計的IDS系統的各種性能，把實驗數據隨機分割成S1和S2兩個子集。將S1作為訓練數據集，用于訓練IDS構建正常網絡數據模式和入侵網絡數據模式，S2作為測試數據集，其中包含有S1中沒有出現的網絡攻擊數據，用來檢測該IDS的檢測能力。

將實驗數據導入到SQLServer數據庫中，建立數據庫，并新建訓練數據表和測試數據表。

3.3.2 實驗結果分析

采用誤檢率來評價該IDS檢測效果的度量指標，公式如式(1)所示：

(1)

在實驗中，經過多次選取不同參數r和β，測試該IDS的檢測性能。r為聚類半徑參數指標，β為孤立點閾值參數指標。

(1)r對實驗結果的影響(β=0.4)。

設定孤立點閾值β=0.4時，通過改變不同r的值，其結果如表1所示。

從表1可以看出，當聚類半徑r越大時，誤檢率越高，表明IDS將入侵數據當成正常數據，會把攻擊數據過濾，不做檢測，即檢測不出入侵數據，容易造成漏檢。

表1 不同r值對結果的影響

分析：聚類半徑r直接影響后的結果。當r越大時，聚類后的類數量就越少，這樣入侵數據被當成正常數據的幾率越大。當r越小時，聚類后類的數量就越多，數據匹配就更細化，入侵數據被當成正常數據的幾率就越小。所以，聚類半徑r對誤檢率有非常顯著的影響，r越小，誤檢率越低。

(2)不同β值的影響(設定聚類半徑r=5)。

對數據進行多次聚類分析，設定聚類半徑r=5，不斷變化閾值β，如表2所示。

表2 孤立點閾值β的影響

從表2可以看出，孤立點閾值β越小，誤檢率越高，β越大，誤檢率越低。

分析：孤立點閾值β對誤檢率也有很大的影響，β值是某一類成員數與全部數據的比率。當β越小時，表明更多的入侵數據被當成正常數據類，誤檢率就高。反之，孤立點閾值β越大，更多的數據要進行再次聚類，入侵數據被當成正常數據的可能性越低，這樣，誤檢率就越低。

從上述實驗結果及分析可知，采用該IDSK-means聚類算法的入侵檢測系統，聚類半徑r和孤立點閾值β直接影響聚類結果，從而對IDS檢測結果產生重大影響，合理選擇聚類半徑r和閾值β直接關系到IDS系統的檢測性能。在實際應用的入侵檢測系統中，需要根據具體情況調整合適的r和β參數值，以達到滿意的檢測效果，即提高檢測效率，降低誤檢率。

4 結束語

文中研究了在入侵檢測系統中植入數據挖掘的聚類技術，達到提高檢測效率、降低誤檢率的目標。詳細研究了聚類算法K-means的流程、優點及不足，創新性地提出了根據聚類半徑r和閾值β進行聚類的改進IDSK-means算法。設計了基于IDSK-means算法的智能入侵檢測系統結構，并采用模擬網絡攻擊數據包KDDCUP99對系統進行了實驗測試。研究結果表明數據挖掘技術應用于入侵檢測系統可有效地提高異常檢測效率；能夠自適應建立入侵檢測異常模式庫，對未知的入侵攻擊能有效防范；調整合適的聚類半徑r和閾值β，能達到較好的檢測效果。

[1] 郭紅艷,谷保平.改進k均值算法在網絡入侵檢測中的應用研究[J].計算機安全,2008(5):24-26．

[2] 劉 靜.基于聚類的網絡入侵檢測的研究[D].太原：太原理工大學，2008.

[3] 秦子燕.基于聚類分析的入侵檢測方法研究[D].無錫：江南大學，2008.

[4]SabahiF,MovagharA.Intrusiondetection：asurvey[C]//Procofthethirdinternationalconferenceonsystemsandnetworkscommunications.[s.l.]:[s.n.],2008：23-26．

[5] 李 洋.K-means聚類算法在入侵檢測中的應用[J].計算機工程,2007,33(14):154-156.

[6] 張建萍,劉希玉.基于聚類分析的K-means算法研究及應用[J].計算機應用研究,2007,24(5):166-168.

[7] 陳小輝.基于數據挖掘算法的入侵檢測方法[J].計算機工程,2010,36(17):72-73.

[8]GaddamSR，PhohaVV，BalaganiKS．K-Means+ID3：anovelmethodforsupervisedanomalydetectionbycascadingK-MeansclusteringandID3decisiontreelearningmethods[J]．IEEETransactionsonKnowledgeandDataEngineering,2007,19(3):345-354．

[9] 李文華.基于聚類分析的網絡入侵檢測模型[J].計算機工程,2011,37(17):96-98.

[10]EnsafiR,DehghanzadehS,MohammadR,etal.OptimizingfuzzyK-meansfornetworkanomalydetectionusingPSO[C]//ProcofACS/IEEEinternationalconferenceoncomputersystemsandapplications.Doha,Qatar:IEEE,2008:686-693．

[11] 杜 強,孫 敏.基于改進聚類分析算法的入侵檢測系統研究[J].計算機工程與應用,2011,47(11):106-108.

[12] 吳慶濤,邵志清.入侵檢測研究綜述[J].計算機應用研究，2005，22(12):11-14．

[13] 宋宇翔,劉 琰.特征和分類器聯合優化的網絡入侵檢測算法[J].計算機工程與應用,2012,48(19):77-81.

[14] 朱廣彬．基于數據挖掘的入侵檢測技術研究[D]．北京：北京交通大學，2010．

[15]UniversityofCalifornia，Irvine.KDDcup1999data[EB/OL].(1999-10-28)[2012-03-20].http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.

Design of Intrusion Detection System Based on ImprovedK-means Algorithm

LIU Hua-chun,HOU Xiang-ning,YANG Zhong

(Engineering & Technical College of Chengdu University of Technology,Leshan 614007,China)

Traditional intrusion detection system is matched to the rule base and network packet one by one.When the network is the huge increase in the amount of data,detection efficiency significantly reduces,even in the face of enormous challenges not immediately detected.Data mining is a technology finds a variety of valuable information from the mass of data,data mining technology into the intrusion detection system will greatly improve efficiency and intelligence of this IDS．Focus on researching theK-meansclusteringalgorithmindataminingforapplicationtointrusiondetectionsystem.TheK-meansalgorithmhassomeshortcomings,suchastobeaffectedbytheinitialKvalueandoutlier,difficultyofdeterminingKvalue,highlydependingontheinitialcenterpoint.Toovercomethesedisadvantages,animprovedK-meansclusteringalgorithmisproposed.Andanintrusiondetectionsystembasedonthisisdesigned.Theresultsshowthattheimprovedclusteringalgorithmisappliedtointrusiondetection,itcansignificantlyimprovetheabnormalitydetectionefficiency,andadaptivelyestablishtheabnormalpatterndatabaseofintrusiondetection,andeffectivelypreventtheunknownintrusionandgreatlyreducethefalsedetectionrate.

data mining;intrusion detection;clustering algorithm;anomaly detection

2015-03-21

2015-06-23

時間：2015-11-19

四川省自然科學重點項目(A22012003)

劉華春(1966-),男,碩士,副教授,研究方向為信息安全、機器學習。

http://www.cnki.net/kcms/detail/61.1450.TP.20151119.1111.052.html

TP

A

1673-629X(2016)01-0101-05

10.3969/j.issn.1673-629X.2016.01.021