基于譜聚類的網絡入侵檢測算法研究

摘 要： 針對傳統聚類分析算法在入侵檢測中存在的問題，提出基于譜聚類的入侵檢測算法。闡述入侵檢測與聚類分析相結合的優勢，并分析幾種入侵檢測系統中常用的聚類方法。譜聚類算法可以在任意形狀的樣本空間上聚類，并能獲得全局最優解。將譜聚類用在經典的入侵檢測數據集KDD CUP99中，實驗結果表明，與基于K-means的入侵檢測方法相比，該方法有較高的檢測率和較低的誤檢率。

關鍵詞： 譜聚類； 入侵檢測； K-means算法； KDD CUP99

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2016）06-40-03

Abstract： Aiming at the problem of traditional clustering analysis algorithm in intrusion detection， an intrusion detection algorithm based on spectral clustering is proposed. The advantages of combining intrusion detection and cluster analysis are described， and the commonly used clustering methods in several intrusion detection systems are analyzed. Spectral clustering algorithm can cluster on any shape of the sample space， and can obtain a global optimization solution. Using spectral clustering algorithm to the classic intrusion detection data set KDD CUP99， and comparing to the intrusion detection method based on K-means， the experiment results show that this algorithm has higher detection rate and lower false detection rate.

Key words： spectral clustering； intrusion detection； K-means algorithm； KDD CUP99

0 引言

隨著計算機網絡的普及和黑客技術的發展，網絡攻擊和安全問題越來越嚴峻。為了實時有效地發現攻擊行為以保證網絡正常運行，繼防火墻、信息加密等傳統安全保護措施后，入侵檢測（Intrusion Detection System，IDS）作為一種新的安全防護手段應運而生[1]。入侵檢測是對入侵行為的發覺，它通過收集計算機網絡或計算機系統中若干關鍵點的信息并對其進行分析，從中發現網絡或系統中是否有違反安全策略的行為和被攻擊的跡象，對網絡或系統中非授權的，或威脅到系統安全，又或存在攻擊的行為作出響應。

網絡入侵檢測方法一般分為誤用檢測和異常檢測兩類。誤用檢測根據已知系統的安全漏洞和應用軟件的弱點及其攻擊行為特征，與審計數據進行匹配來判斷入侵行為，它可以準確地檢測已知的入侵行為，具有檢測率高、檢測效果穩定、誤檢率低的特點，但不能發現新的入侵行為，漏報率較高。而異常檢測是基于行為的檢測，其特點是通過對系統異常行為的檢測來發現未知的攻擊模式，不但能檢測已知入侵，也能檢測未知入侵。異常檢測對系統的依賴性相對較小，可移植性強，其難點在于正常行為模型庫的建立，且誤檢率較高。為了解決傳統入侵檢測系統的缺陷，研究者將異常檢測與數據挖掘的聚類分析方法相結合來提高檢測精確度和檢測性能。

本文提出基于譜聚類（Spectral Clustering，SC）的異常檢測算法，實驗采用部分KDD CUP99的數據集，并與K-Means算法相比較，其結果表明，所提出的算法比傳統的聚類檢測算法有更高的檢測率和更低的誤檢率。

1 入侵檢測系統中常用的聚類算法

數據挖掘也稱數據庫中知識發現（knowledge discovery in database，KDD），通過對海量的安全審計數據進行智能化的處理，從中提取系統安全相關的行為特征，從而識別出入侵行為。

聚類，就是按照事物的某些特征，把事物分成若干類或簇，使得在同一個類內的對象之間最大程度相似，而不同類之間的對象最大程度不同。聚類是數據挖掘和機器學習領域中的一個研究熱點，它可以對大量數據進行分析并將這些數據對象自動歸類，適合用于異常檢測。基于聚類分析的入侵檢測技術是采用無參數的方法用向量表示事件流，再利用聚類算法將它們分為行為類。每一類都代表相似的活動或用戶的行為，以辨別出正常和異常的行為[1]。

本文主要介紹K-means、模糊C均值（Fuzzy C-Means，FCM）聚類和譜聚類算法。

K-means算法最早被用到入侵檢測系統中，且使用率較高。應用于異常檢測的優點是算法簡單、計算復雜性小，速度快，易達到入侵檢測的實時性要求。但是，由于K-means采用隨機法選取初始聚類中心，初值不同的情況下，可能會產生不同的聚類結果，將其應用于入侵檢測系統中，算法的執行結果將會不穩定。并且，該算法基于梯度下降進行搜索常使算法陷入局部最優[2]。K-means算法的這兩大缺陷極大地限制了其應用范圍。

FCM算法也是目前應用廣泛的一種聚類方法。根據客觀事物間的不同特性、相似性和親疏程度等，通過建立模糊相似關系對客觀事物進行分類。和其他傳統聚類算法一樣，FCM算法用歐式距離度量數據對象之間的相似性，但只能對類球狀聚類[3]。同K-means算法，FCM算法對初始值的選取依賴性也很大，對孤立點和噪音點敏感，使得其在異常檢測中得到的結果不能滿足要求。

相對于前兩種聚類算法，譜聚類算法由給定的樣本數據集定義一個描述數據點之間相似度的親和矩陣，再計算矩陣的特征值和特征向量，最后選擇合適的特征向量聚類不同的數據點[4]。譜聚類算法是一個判別式算法，其思想相對簡單易于實現，且不受數據點維數的限制。譜聚類能對任意形狀的樣本空間聚類，并能獲得全局最優解，非常適用于入侵檢測中。

近年來上述算法的運用改善了入侵檢測的性能，但也存在著不足之處。在實際的應用中，必須要根據數據類型、聚類的目的，以及具體的聚類應用情況等選擇聚類算法。因此，選擇合適的聚類算法應用于入侵檢測是一項很具挑戰性的工作。本文基于以上研究背景，將譜聚類算法應用于網絡入侵檢測系統中，以提高入侵檢測的效率。

2 實驗設置與結果

2.1 實驗數據集

選擇合適的數據訓練集對于聚類結果有很大影響，網絡異常檢測系統中采用聚類算法的目的是為了建立正常行為模式匹配庫。如果訓練集太小，導致模式匹配庫包含行為特征太少，匹配的未知行為過多，會降低檢測效率；如果選擇的訓練集過大，會增加計算的時間復雜度以及空間復雜度。因此，選擇合適的數據集對于模式匹配庫的建立尤為重要。

本文實驗數據采用了在第三屆國際知識發現和數據挖掘工具競賽上使用的KDD CUP99數據集，其提供了從模擬美國空軍局域網上收集的9周時間的網絡連接和系統審計數據，仿真各種用戶類型、各種不同的網絡流量和攻擊手段。這些原始數據被分為兩個部分：7周時間的訓練數據大概包含5百萬個網絡連接記錄；其余2周時間的測試數據大概包含2百萬個網絡連接記錄。一個網絡連接是指，在某個時間內由開始到結束的TCP數據包序列，并且在該時間內，數據在預定義的協議下（如TCP、UDP）從源IP地址到目的IP地址的傳遞。每個網絡連接被標記為正常（normal）或異常（attack）。KDD CUP99數據集都采用相同的文本記錄格式存儲，每行表示一個記錄，每條記錄用一條連接中提取的41個特征（一共42個，未包括最后標注的攻擊類型）[5]來描述，被細分為4大類共39種攻擊類型，其中22種攻擊類型出現在訓練集中，另有17種未知攻擊類型出現在測試集中[6]。所以，使用該數據集的實驗更加接近真實的網絡環境。

2.2 提取數據集

由于數據集過大，為了使之能適用于譜聚類算法，首先對KDD CUP99數據集做分塊處理，以減少單次分析的數據量大小[7]。根據service屬性特征（目標主機網絡服務類型）將該數據集分為http、ftp、smtp和other四個部分，每個部分包含10%入侵數據。在這四個部分，http服務在數據集中所占的比例比較高，實驗選取http服務的數據記錄數略多于其他服務的記錄數，數據記錄一共為800條，正常和入侵數據的比例如表1。

2.3 數據處理

KDD CUP99數據集中的數據中存在連續變量和離散變量，根據本實驗設計，需要將離散型變量做連續化的處理。一共7個離散型變量中，flag、land、logged_in、is_host_login和is_guest_login 5個屬性特征均只包括兩種狀態：0或者1。因此，這里只用對提取的數據集的protocol_type（協議類型）和service（網絡服務）特征轉換成連續化特征變量，如表2和表3。為了在計算的時候不產生誤差，還要確保每條記錄間同一離散型特征之間的距離相等[8]。

接著用譜聚類的NJW算法對數據進行降維和歸一化處理[8]，得到新的數據源。

2.4 實驗結果及分析

將處理后得到的新數據源所獲得的重要特征應用到譜聚類算法和傳統的聚類算法K-means中，并進行比較。實驗結果用檢測率（DR）和誤檢率（Fdr）2個參數作為評價標準，既要保證較低的誤檢率，又要獲得盡可能高的檢測率。聚類結果如表3。

3 結束語

本文在經典的入侵檢測KDD CUP99數據集上進行實驗，采用基于譜聚類的異常檢測算法，在選取的數據集中能達到較好的檢測率和較低的誤檢率。相對于K-means算法，克服了隨機選取初始聚類中心和容易受到局部最優解的缺陷[1]。在后續研究中，除了在真實環境下檢驗本實驗方法的有效性，還將實驗譜聚類算法與其他方法相結合用于異常檢測中，提高聚類精度和速度。

參考文獻（References）：

[1] 杜強，孫敏.基于改進聚類分析算法的入侵檢測系統研究[J].

計算機工程與應用，2011.47（11）：106-108

[2] 李斌，王勁松，黃瑋.一種大數據環境下的新聚類算法[J].計算

機科學，2015.42（12）：247-250

[3] 李玲俐.一種基于屬性分解的FCM融合聚類算法[J].計算機

應用與軟件，2013.30（8）：65-67

[4] 蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，

2008.35（7）：14-18

[5] 張新有，華燊，賈磊.入侵檢測數據集KDDCUP99研究[J].計

算機工程與設計，2010.31（22）：4809-4812

[6] KDD CUP 99數據集[EB/OL].[2011-11-18]. http：//blog.

csdn.net/com_stu_zhang/article/details/6987632.

[7] 吳建勝，張文鵬，馬垣.KDDCUP99數據集的數據分析研究[J].

計算機應用與軟件，2014.31（11）：321-325

[8] 朱正偉.譜聚類研究及其在入侵檢測中的應用[D].重慶大學，

2010.