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

關(guān)鍵詞： 譜聚類； 入侵檢測； 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 引言

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

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

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

1 入侵檢測系統(tǒng)中常用的聚類算法

數(shù)據(jù)挖掘也稱數(shù)據(jù)庫中知識發(fā)現(xiàn)（knowledge discovery in database，KDD），通過對海量的安全審計數(shù)據(jù)進行智能化的處理，從中提取系統(tǒng)安全相關(guān)的行為特征，從而識別出入侵行為。

聚類，就是按照事物的某些特征，把事物分成若干類或簇，使得在同一個類內(nèi)的對象之間最大程度相似，而不同類之間的對象最大程度不同。聚類是數(shù)據(jù)挖掘和機器學(xué)習(xí)領(lǐng)域中的一個研究熱點，它可以對大量數(shù)據(jù)進行分析并將這些數(shù)據(jù)對象自動歸類，適合用于異常檢測?；诰垲惙治龅娜肭謾z測技術(shù)是采用無參數(shù)的方法用向量表示事件流，再利用聚類算法將它們分為行為類。每一類都代表相似的活動或用戶的行為，以辨別出正常和異常的行為[1]。

本文主要介紹K-means、模糊C均值（Fuzzy C-Means，F(xiàn)CM）聚類和譜聚類算法。

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

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

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

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

2 實驗設(shè)置與結(jié)果

2.1 實驗數(shù)據(jù)集

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

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

2.2 提取數(shù)據(jù)集

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

2.3 數(shù)據(jù)處理

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

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

2.4 實驗結(jié)果及分析

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

3 結(jié)束語

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

參考文獻（References）：

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

計算機工程與應(yīng)用，2011.47（11）：106-108

[2] 李斌，王勁松，黃瑋.一種大數(shù)據(jù)環(huán)境下的新聚類算法[J].計算

機科學(xué)，2015.42（12）：247-250

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

應(yīng)用與軟件，2013.30（8）：65-67

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

2008.35（7）：14-18

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

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

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

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

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

計算機應(yīng)用與軟件，2014.31（11）：321-325

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

2010.