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

關(guān)鍵詞： 譜聚類(lèi)； 入侵檢測(cè)； K-means算法； KDD CUP99

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)設(shè)置與結(jié)果

2.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

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

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

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

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

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

2.4 實(shí)驗(yàn)結(jié)果及分析

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

[1] 杜強(qiáng)，孫敏.基于改進(jìn)聚類(lèi)分析算法的入侵檢測(cè)系統(tǒng)研究[J].

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

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

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

[3] 李玲俐.一種基于屬性分解的FCM融合聚類(lèi)算法[J].計(jì)算機(jī)

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

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

2008.35（7）：14-18

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

算機(jī)工程與設(shè)計(jì)，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].

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

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

2010.