聚類算法在入侵檢測中的應用研究

朱 健，盧秉亮，曲超毅

（1.沈陽航空職業技術學院，沈陽110034；2.沈陽航空航天大學計算機學院，沈陽110136；3.中航工業沈陽飛機工業（集團）有限公司，沈陽110034）

聚類算法在入侵檢測中的應用研究

朱 健1，盧秉亮2，曲超毅3

（1.沈陽航空職業技術學院，沈陽110034；2.沈陽航空航天大學計算機學院，沈陽110136；3.中航工業沈陽飛機工業（集團）有限公司，沈陽110034）

應用聚類算法對入侵檢測數據集進行聚類，通過對其聚類結果的分析，發現聚類的部分簇中存在劃分不夠緊湊的問題。為此，提出應用加權聚類算法對簇中與聚類中心距離較遠的數據進行聚類，解決了聚類結果中存在“子簇”的問題。結果表明，簇的緊湊性有較大提升，同時由于子簇數量的減少使得檢測率有所提升，加快了檢測速度。

網絡安全；入侵檢測；聚類分析；加權聚類算法

1 引 言

隨著網絡技術的逐漸發展，不斷出現新的入侵和新類型的攻擊，為了解決此問題，必須應用智能入侵檢測技術。常見的入侵檢測方法主要包括統計方法、神經網絡、模式匹配、規則推理以及人工免疫理論等方法［1-3］。為了獲得網絡行為模式，需要通過帶標簽數據或者完全正常的網絡行為數據進行訓練。然而，標簽數據和完全正常的網絡行為數據是很難實現的，這是由于數據的海量性和復雜的網絡環境造成的。為了提高入侵檢測效率，以聚類（Clustering）為代表的無監督入侵檢測算法［4-6］被用來直接處理無標簽原始網絡數據。

通過使用應用加權的聚類算法在局域網中進行實際的入侵檢測驗證，對DOS和Probe兩類攻擊進行檢測，結果表明有較好的檢測性能，并對未知網絡入侵具有一定的自適應性。

2 聚類分析算法

2.1 聚類算法進行聚類的原理

聚類分析算法［7-8］可以描述為：給定m維空間R中的n個向量，把每個向量歸屬到k個聚類中的某一個，使得每一個向量與其聚類中心的距離最小。聚類可以理解為：類內的相關性盡量大，類間相關性盡量小。在這里對鏈路流量進行聚類，初始設定一個鏈路流量大的鏈路A作為類A和一個鏈路流量小的鏈路B作為類B。

2.2 聚類分析算法原理

聚類算法包括劃分方法、層次方法、基于密度的方法、基于網格的方法以及基于模型的方法［7］。典型的基于劃分的聚類分析算法是K-means算法：給定一個有N個元組或者紀錄的數據集構造K個分組，每一個分組代表一個聚類，這里的K＜N。K個分組滿足下列條件：①每一個分組至少包含一個數據紀錄；②每一個數據紀錄屬于且僅屬于一個分組；對于給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，最終使得同一分組中的記錄越近，而不同分組中的紀錄越遠。

K-means算法把n個向量xi（i＝1，2，…，n）分成k個類Gi（i＝1，2，…，k）并求每類的聚類中心，使得非相似性（或距離）指標的目標函數達到最小。當選擇第i個類Gi中向量xl與相應的聚類中心Ci間的度量為歐幾里德距離時，目標函數可以定義為

這里Ji是類Gi內的目標函數，顯然J的大小取決于聚類中心Ci和Gi的形狀，J越小，表明聚類的效果越好。

K-means算法的基本思想是：

（1）首先從n個數據對象任意選擇k個對象作為初始聚類中心；

（2）而對于剩下的其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；

（3）設U是一個c×n矩陣，若xj∈類i，則uij＝1，否則uij＝0，即當‖Xj-Ci‖≤‖Xj-Ck‖（k≠j）時，uij＝1，否則uij＝0；

（4）根據uij計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；

（5）根據uij計算標準測度函數的值，直到標準測度函數開始收斂為止，否則回到步驟（3）。

2.3 加權的聚類算法［7］

采用K-means算法也有其局限性，在聚類分析的時候，它考慮了所有因素，而且認為這些因素對距離的影響是等同的［9］，會出現由不相關屬性導致的“維數陷阱”。要解決這一問題，需要對每一個屬性加上特征參數［10］，讓不同的屬性在聚類中起不同作用。從歐氏空間上來說就是拉長相關屬性對應的軸，縮短無關屬性對應的軸。為此，就要把目標函數中的‖Xi-Ci‖2換為，這樣目標函數J還依賴于權值Wj，權值的大小由經驗確定，從而解決“維數陷阱”問題。

3 聚類技術在入侵檢測中的應用

3.1 應用聚類分析進行入侵檢測的基本思想

為了能夠實現聚類，要求網絡環境中的正常網絡行為要遠大于入侵網絡行為并且兩種行為必須是可以區分的，使得算法能夠將網絡行為數據集劃分為不同的類別，在實際網絡環境中，入侵網絡行為遠小于正常網絡行為并且可以區別開來，因此在網絡入侵檢測中可以應用聚類分析算法。聚類后的結果可以應用簇標記算法［11-12］判斷簇是正常網絡行為還是入侵網絡行為。

3.2 應用聚類算法進行入侵檢測主要過程

應用聚類分析技術進行入侵檢測主要經過數據收集、特征向量標準化、聚類分析、標記生成簇、實時檢測、結果驗證等過程。

3.2.1 數據收集

將原始的網絡數據包恢復成TCP／IP層的連接，每個連接記錄包括網絡協議、起始時間、結束時間、端口號、源IP地址、目的IP地址、連接終止狀態、TCP標志等屬性。同時要記錄一段內與當前連接具有相同服務類型的連接數和錯誤的連接百分數等。

3.2.2 特征向量標準化

聚類算法的輸入通常有 N個數據點的集合D＝｛x1，x2，…，xn｝，具有不同的特征向量，其單位也是不同的，如果直接進行聚類會影響聚類結果，通過標準化處理將所有特征向量轉化為無單位，則可提高聚類結果的準確性。

3.2.3 聚類分析

在這里對鏈路流量進行聚類，初始設定兩個類，一個是類A，代表鏈路流量大的鏈路；另一個是類B，代表鏈路流量小的鏈路，然后使用加權K-means算法進行聚類分析得到聚類結果。

K-means有其缺點，即產生類的大小相差不會很大并且對于“臟”數據很敏感，因此，要對初始聚類結果進行優化，使各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。聚類結果的具體評價標準［13］定義如下：

其中，δ（Ck，Cl）定義為簇間距離：

d（x，y）為記錄x與y的距離，Δ（Cm）定義為簇的直徑：

由公式2可知，簇的直徑越小，聚類結果越緊湊；簇間距離越大，各聚類之間的分割性越好，公式2的值越大表示聚類的結果越好。

3.2.4 標記生成簇

由簇標記算法區分正常簇還是異常簇，進而獲得其特征模式。

3.2.5 實時檢測

對異常簇異常行為的特征模式應用檢測器（入侵檢測系統的模式信息庫）對其進行判斷，產生檢測結果，確定并輸出入侵和攻擊［14-16］。

4 實驗結果及其分析

由于數據集中入侵數據的比例遠超過真實環境，不能滿足無監督異常檢測算法中“正常數據的數量要遠大于入侵數據”的要求，而且數據集中含有大量重復數據，因此需要對實驗數據進行篩選。選取的數據分為兩部分，去掉10%數據集中的重復數據。實驗中，訓練集A使用了24790條記錄用來生成檢測模型，其中24294條為正常網絡行為，496條為入侵網絡行為，正常網絡行為的數據比例約為98%，測試集B1和測試集B2用來檢測算法的性能。

表1是以B1為測試集，改進前后的聚類精度及檢測結果對比。

表1 檢測率（%）及聚類精度（Intra-cluster distance）對比

由表1的實驗結果可見，改進后檢測率及Intra-cluster distance值都有進一步的提高，已經能夠獲得所有被不合理聚類的攻擊數據，Intra-cluster distance提升率約為7.43%，說明簇的緊湊度有較明顯的提高。同時，在聚類過程中存在將訓練集中本應屬于同一個簇的數據劃分為多個子簇的現象，影響了檢測時的速度，使得含有較少樣本的正常類型簇在簇的標記過程中被誤判為異常簇，導致誤報率上升的現象。為解決這一問題，在聚類結束后使用簇的合并算法［3］，將含有較少樣本的子簇與其相似簇合并。

表2給出使用測試集B2對未知攻擊類型的測試結果。算法對未知攻擊類型的檢測率約為58%。說明對未知攻擊類型具有一定的檢測能力。

表2 對未知類型的檢測

表3是同其它文獻中方法的對比，加下劃線的數據為最優結果。

表3 與其它文獻使用方法的對比

由表3的檢測結果對比表明，加權聚類算法對DOS，U2R，R2L三個攻擊類型的檢測率有所提升，但是對Probe，normal類型的檢測還存在一定的差距。

5 結束語

應用kdd cup 99入侵檢測數據集對加權聚類算法進行了驗證，將數據集中的數值型屬性進行標準化后用于聚類算法訓練。在檢測過程中，算法分別測試了已知入侵和未知入侵兩種情況，通過對已知入侵的測試來檢測算法的檢測率和誤報率，通過對未知入侵來測試算法的適應性。加權聚類算法的聚類精度和檢測結果都有較明顯提高。

［1］呂志軍，鄭瑞，黃皓.高速網絡下的分布式實時入侵檢測系統［J］.計算機研究與發展，2004，41（4）：667-673.

［2］Lih-Chyau Wuu，Chi-Hsiang Hung，Sout-Fong Chen.Building intrusion pattern miner for Snort network intrusion detection system［J］.The Journal of Systems and Software，2007，80（10）：1699-1715.

［3］Animesh Patcha，Jung-Min Park.An overview of anomaly detection techniques：Existing solutions and latest technological trends［J］.Computer Networks，2007，51（12）：3448-3470.

［4］Eskin E，Arnold A，Prerau M，et al.A Geometric Framework for Unsupervised Anomaly Detection：Detecting Intrusions in Unlabeled Data，2002［C］.Applications of Data Mining in Computer Security.2002：26-29.

［5］向繼，高能，荊繼武.聚類算法在網絡入侵檢測中的應用［J］.計算機工程，2003，29（16）：48-49，185.

［6］徐菁，劉寶旭，許榕生.基于數據挖掘技術的入侵檢測系統設計與實現［J］.計算機工程，2002，28（6）：9-10，169.

［7］閆偉，張浩，陸劍峰，等.聚類分析理論研究及在流程企業中的應用［J］.計算機工程，2006，32（17）：19-21，27.

［8］雷小鋒，何濤，李奎儒，等.面向結構穩定性的分裂-合并聚類算法［J］.計算機科學，2010，37（11）：217-222.

［9］杜強，孫敏.基于改進聚類分析算法的入侵檢測系統研究［J］.計算機工程與應用，2011，47（11）：106-108，181.

［10］延皓，張博，劉芳，雷振明.基于量值的頻繁閉項集層次聚類算法［J］.北京郵電大學學報，2011，34（6）：64-68.

［11］閻慧，曹元大.一種基于入侵統計的異常檢測方法［J］.計算機工程與應用，2002，38（22）：48-50.

［12］蔣建春，馬恒太，任黨恩，等.網絡安全入侵檢測：研究綜述［J］.軟件學報，2000，11（11）：1460-1466.

［13］Dunn JC.A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters［J］.J.Cybernetics，1973（3）：32-57.

［14］Portnoy L，Eskin E，Stolfo S J.Intrusion Detection with Unlabeled Data Using Clustering，2001［C］.Proceedings of ACM CSS Workshop on Data Mining Applied to Security（DMSA-2001），New York：ACM Press，2001：123-130.

［15］Portnoy L，Eskin E，Stolfo S J.Intrusion detection with unlabeled data using clustering，2001［C］.Proceedings of ACM CSSWorkshop on Data Mining Applied to Security（DMSA-2001）.Philadelphia，PA，2001：123-130.

［16］Mukkamala S，Janoski G，Sung A H.Intrusion Detection Using Neural Networks and Support Vector Machines，2002［C］.Proceedings of IEEE International Joint Conference on Neural Networks，2002：1702-1707.

Research of Application of Clustering Algorithm in Network Intrusion Detection

ZHU Jian1，LU Bing-liang2，QU Chao-yi3
（1.Shenyang Aeronautical Vocational College，Shenyang 110034，China；2.School of Computer Science and Engineering，Shenyang Aerospace University，Shenyang 110136，China；3.AVIC Shenyang Aircraft Corporation，Shenyang 110034，China）

The clustering algorithm is used to cluster data set for intrusion detection，the clustering results are analyzed to find the problem of uncompacted division in partof clusters.Therefore，aweighing clustering algorithm is put forward to cluster the data far from the clustering center for solving the problem that clustering results havemany sub-clusters.The results show that the clusters aremore compact and the detection accuracy and speed are increased because of sub-clusters decreased.

Network security；Intrusion detection；Cluster Analysis；Weighted clustering algorithm

10.3969／j.issn.1002-2279.2014.05.012

TP393.07

：A

：1002-2279（2014）05-0040-03

朱健（1971-），男（滿族），遼寧北鎮人，碩士，教授，高級工程師，主研方向：計算機網絡與數據庫。

2013-10-9