改進(jìn)的聚類算法在入侵檢測系統(tǒng)中的應(yīng)用*

邢瑞康，李成海

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051）

0 引言

在網(wǎng)絡(luò)信息技術(shù)高速發(fā)展的時(shí)代，計(jì)算機(jī)網(wǎng)絡(luò)正以難以想象的速度向全世界各個(gè)角落滲透，使其成為當(dāng)今人類社會(huì)運(yùn)轉(zhuǎn)必不可少的一部分。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和網(wǎng)絡(luò)工具的廣泛應(yīng)用，網(wǎng)絡(luò)空間蘊(yùn)藏的巨大力量，以及網(wǎng)絡(luò)資源的戰(zhàn)略性意義正逐漸被世人發(fā)現(xiàn)、認(rèn)可并著手發(fā)掘，世界各國在軍事領(lǐng)域也隨著網(wǎng)絡(luò)的變革而不斷發(fā)生變化。一個(gè)全新的軍事競爭平臺——網(wǎng)電空間成為現(xiàn)代軍事化戰(zhàn)爭的又一主戰(zhàn)場。然而，隨著網(wǎng)絡(luò)范圍的日益擴(kuò)大，由于安全機(jī)制的不盡完善，網(wǎng)絡(luò)空間所要面對的威脅也不斷增多，網(wǎng)絡(luò)安全就成為一個(gè)十分重要的問題。因此，如何有效抵御各種入侵和攻擊的行為成為重要課題。入侵檢測（Intrusion Detection）主要建立在侵犯行為與系統(tǒng)行為不同的這一假設(shè)基礎(chǔ)上，是一種動(dòng)態(tài)的網(wǎng)絡(luò)安全技術(shù)，它通過分析網(wǎng)絡(luò)流量以及系統(tǒng)審計(jì)記錄數(shù)據(jù)等，實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)系統(tǒng)中是否存在與安全策略不相吻合的“入侵”行為，并且對可能危害到系統(tǒng)機(jī)密性、完整性和可用性的行為進(jìn)行響應(yīng)和攔截［1］。入侵檢測技術(shù)作為網(wǎng)絡(luò)與信息安全系統(tǒng)的關(guān)鍵技術(shù)，已經(jīng)成為網(wǎng)絡(luò)與信息安全體系中十分重要的部分。

聚類分析廣泛地應(yīng)用在統(tǒng)計(jì)學(xué)、決策支持、機(jī)器學(xué)習(xí)、模式識別、圖像處理、空間數(shù)據(jù)庫技術(shù)以及電子商務(wù)等相關(guān)領(lǐng)域，是一種十分高效的數(shù)據(jù)分析方法和一項(xiàng)重要的數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘能從大量的審計(jì)數(shù)據(jù)中挖掘出正常和異常的行為模式，使得人工分析和編碼的工作量大大減少，入侵檢測系統(tǒng)的檢測效率也因此得到提高。因而，也被廣泛地應(yīng)用在入侵檢測系統(tǒng)。

聚類算法的優(yōu)劣往往直接會(huì)影響到聚類過程的最終效果。k-中心點(diǎn)算法作為其中的代表性算法之一，具有不易被極端的數(shù)據(jù)影響，適應(yīng)性廣泛，特別是針對“噪聲”點(diǎn)、孤立點(diǎn)不敏感并且在檢測當(dāng)中應(yīng)用廣泛的特點(diǎn)，而且對數(shù)據(jù)屬性的類型沒有局限性，具有比較強(qiáng)的魯棒性等。但是，該算法也存在許多缺陷。主要表現(xiàn)在：在對于處理規(guī)模較大的數(shù)據(jù)集時(shí)，K-中心點(diǎn)算法在聚類過程中的高耗時(shí)性。

因此，針對傳統(tǒng)聚類算法的不足，本文結(jié)合算法和有效性指標(biāo)提出了一種基于“密度”信息改進(jìn)的算法。并將優(yōu)化算法應(yīng)用于入侵檢測系統(tǒng)中。用實(shí)驗(yàn)驗(yàn)證了以這種方法來進(jìn)行數(shù)據(jù)的聚類，顯著地提高了數(shù)據(jù)尤其是大數(shù)據(jù)集聚類的效果。結(jié)果顯示，改進(jìn)的算法應(yīng)用在入侵檢測系統(tǒng)中提高了檢測率并降低了誤檢率。

1 入侵檢測

1.1 入侵檢測的原理

現(xiàn)有的入侵檢測系統(tǒng)主要采用以下方法來實(shí)現(xiàn)系統(tǒng)的檢測機(jī)制，包括：代理、行為分析、概率統(tǒng)計(jì)、模式匹配、生物免疫系統(tǒng)、神經(jīng)網(wǎng)絡(luò)、專家系統(tǒng)、數(shù)據(jù)挖掘、遺傳算法等。這些方法優(yōu)劣不同，所應(yīng)用的情形亦不同。它們不同程度地提高了處理的效率和有效性，能夠滿足一定的需求。

1.2 入侵檢測的系統(tǒng)構(gòu)成

一個(gè)完整的入侵檢測系統(tǒng)通常包括以下基本組件，如圖1所示：

圖1 入侵檢測系統(tǒng)的基本構(gòu)成

1.3 入侵檢測存在的不足

對于網(wǎng)絡(luò)的各種攻擊入侵，如果系統(tǒng)能夠迅速高效地檢測出來，就可以使得系統(tǒng)免于遭受各種不必要的資源以及網(wǎng)絡(luò)空間的浪費(fèi)，目前的IDS還有著諸多不足。主要包括：誤報(bào)/漏報(bào)率較高，產(chǎn)品適應(yīng)能力差，檢測性能不足，同時(shí)檢測實(shí)時(shí)性較差，缺少主動(dòng)防御功能等等［3］。

2 聚類分析算法研究

設(shè)數(shù)據(jù)集合是由n個(gè)樣本所組成的集合X={x1，x2，…，xn}，其中任一元素 xi，可表示為 m 維實(shí)數(shù)空間的向量，xi={xi1，xi2，…，xim}。任意兩個(gè)樣本 xi和xm之間的距離采用歐幾里得距離，計(jì)算公式如下：

2.1 K-中心算法基本思想

k-中心點(diǎn)算法的處理過程主要是：首先，隨機(jī)地從樣本集中選取k個(gè)樣本點(diǎn)作為劃分k的個(gè)簇的代表點(diǎn)，即初始中心點(diǎn)，隨即將其他剩余對象根據(jù)該點(diǎn)與代表點(diǎn)對象的遠(yuǎn)近分配到最近的中心點(diǎn)所代表的簇群中；然后，多次用非中心點(diǎn)來替換中心點(diǎn)，以此來不斷改進(jìn)聚類的效果，聚類的效果用“代價(jià)”函數(shù)進(jìn)行估算。

K-中心點(diǎn)算法以這樣的方式來計(jì)算代價(jià)S：

假設(shè)中心點(diǎn)xi1，然后用非中心點(diǎn)xh來替換中心點(diǎn)xi1，則產(chǎn)生下面4種情況。

1）如果點(diǎn)xj代表屬于xi1所表示簇的任意一點(diǎn)，對于另一個(gè)中心點(diǎn)xi2，若，此時(shí)，xj重新歸入xi2所代表的簇中，則其所產(chǎn)生的代價(jià)為：；

2）如果點(diǎn)xj代表屬于xi1所表示簇的任意一點(diǎn)，對于另一個(gè)中心點(diǎn)xi2，若，此時(shí)，xj重新歸入xh所代表的簇中，則其所產(chǎn)生的代價(jià)為：；

3）如果點(diǎn)xj不屬于xi1所表示的簇，而屬于xi2所代表的簇中任意一點(diǎn)，若，此時(shí)，xj所屬簇不變，則其所產(chǎn)生的代價(jià)為：sji1h=0；

4）如果點(diǎn)xj不屬于xi1所表示的簇，而屬于xi2所代表的簇中任意一點(diǎn)，若，此時(shí)，xj重新歸入xh所代表的簇中，則其所產(chǎn)生的代價(jià)為：。

上述4種情況如圖2所示：

圖2 k-中心點(diǎn)算法計(jì)算代價(jià)示意圖

2.2 k-中心點(diǎn)算法描述

輸入：包含n個(gè)對象的數(shù)據(jù)集，需要得到劃分簇的簇?cái)?shù)k；

輸出：全部對象與中心點(diǎn)的距離總和最小的k個(gè)簇。

流程：

Step1：隨機(jī)選擇k個(gè)對象作為初始的簇中心；

Step2：重復(fù)以下步驟直到中心點(diǎn)不會(huì)再發(fā)生改變；

Step2.1：計(jì)算每一對象距離其最近的簇的中心點(diǎn)，并將其劃分到該中心點(diǎn)所代表的簇中；

Step2.2：隨機(jī)選取非中心點(diǎn)Orandom；

Step2.3：用Orandom代替Oj，計(jì)算形成新簇的總代價(jià)S；

Step2.4：如果 S＜0，用 Orandom代替 Oj，形成新集的k個(gè)中心點(diǎn)的集合；

Step3：輸出k個(gè)簇。

3 改進(jìn)k-中心點(diǎn)聚類算法的入侵檢測模型

3.1 改進(jìn)算法的基本思想

3.2 改進(jìn)的k-中心點(diǎn)算法描述

輸入：包含n個(gè)對象的數(shù)據(jù)集，需要得到劃分簇的簇?cái)?shù)k；

輸出：全部對象與中心點(diǎn)的距離總和最小的k個(gè)簇；

流程：

Step1：計(jì)算每一個(gè)樣本點(diǎn)的樣本空間內(nèi)所有點(diǎn)與該點(diǎn)的距離的和；

Step2：取樣本點(diǎn)中計(jì)算所得的最大距離和與最小距離和的均值作為高密度樣本的閾值；

Step3：取所有距離和小于該閾值的點(diǎn)組成高密度樣本集合M；

Step4：對于所有樣本點(diǎn) xi，計(jì)算距離比 Vi：

選擇使Vi最小的點(diǎn)x1作為第1個(gè)簇中心點(diǎn)；

Step5：從M中找出與x1距離相差最大的樣本x2作為選取的第2個(gè)聚類中心；

Step6：從M中找出與x1和x2距離和相差最大的樣本點(diǎn)x3作為第3個(gè)初始聚類中心；

Step7：從M中找與x1，…，xk-1距離和相差最大的樣本xk作為最后一個(gè)初始聚類中心；

Step8：重復(fù)以下步驟直到中心點(diǎn)不會(huì)再發(fā)生改變；

Step8.1：將剩余的n-k個(gè)樣本點(diǎn)按照距離遠(yuǎn)近分別分配到與它距離最小的中心點(diǎn)所代表的簇中；

Step8.2：隨機(jī)選取非中心點(diǎn)；

Step8.3：計(jì)算用非中心點(diǎn)代替中心點(diǎn)，形成新簇群的總代價(jià)S；

Step8.4：如果 S＜0，用該點(diǎn)代替中心點(diǎn)，形成新的k個(gè)中心點(diǎn)集合；

Step9：輸出k個(gè)簇。

3.3 改進(jìn)的k-中心點(diǎn)算法的入侵檢測模型

入侵檢測系統(tǒng)分為訓(xùn)練部分和異常行為檢測部分［4］。模型如圖3所示：

圖3 基于聚類算法的入侵檢測模型

4 仿真研究

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)源

為了驗(yàn)證聚類算法的有效性以及入侵檢測模型的特點(diǎn)，本文分別采取兩種數(shù)據(jù)進(jìn)行驗(yàn)證。UCI數(shù)據(jù)庫是國際上通用的專門進(jìn)行數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)算法測試的數(shù)據(jù)庫。對本實(shí)驗(yàn)進(jìn)行評估所選取的Iris數(shù)據(jù)集合是UCI數(shù)據(jù)庫中最常用于測試驗(yàn)證聚類算法優(yōu)劣性的數(shù)據(jù)集。

為了測試新建立的入侵檢測算法性能，采用KDD CUP 99數(shù)據(jù)集。采用訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的10%數(shù)據(jù)集并對結(jié)果作出相應(yīng)的分析。

入侵檢測的性能指標(biāo)用檢測率（Detection Rate，DR）和誤報(bào)率（False Positive Rate，F(xiàn)PR）進(jìn)行描述：

檢測率=正確檢測出的入侵樣本數(shù)/入侵樣本總數(shù)。

誤報(bào)率=將正常行為檢測為入侵的樣本數(shù)/正常行為樣本總數(shù)。

4.2 實(shí)驗(yàn)結(jié)果與分析

為了測試基于密度信息來確定初始簇中心點(diǎn)算法的聚類性能，首先，將初始聚類的目標(biāo)數(shù)目設(shè)置為3，即k=3，且在聚類時(shí)不考慮類別屬性存在的影響（類別信息主要用來對聚類結(jié)果進(jìn)行評估）。

對于原始的k-中心點(diǎn)聚類算法，實(shí)驗(yàn)時(shí)需要對其進(jìn)行多次測試以得到實(shí)驗(yàn)的平均值作為結(jié)果（本次進(jìn)行了10次實(shí)驗(yàn)操作），而本文提出的改進(jìn)算法所采用的是基于“密度”的方式來處理初始中心點(diǎn)，對于處理同一數(shù)據(jù)集，其產(chǎn)生的初始中心點(diǎn)是唯一確定的，所以只需要進(jìn)行一次實(shí)驗(yàn)即可。

原始的K-中心點(diǎn)聚類算法10次實(shí)驗(yàn)后的聚類結(jié)果如表1所示。兩種算法迭代的次數(shù)以及聚類結(jié)果中錯(cuò)誤樣本比的實(shí)驗(yàn)對比結(jié)果由表2所示。

表1 傳統(tǒng)k-中心點(diǎn)聚類算法結(jié)果統(tǒng)計(jì)

表2 多種算法聚類結(jié)果比較

由表1可以得到，傳統(tǒng)k-中心點(diǎn)聚類算法會(huì)因?yàn)檫x取不同的初始中心點(diǎn)，而經(jīng)過不同次數(shù)的迭代后才趨于收斂。如果存在隨機(jī)選擇的初始中心點(diǎn)有兩個(gè)或者多個(gè)位于同一簇中的情況時(shí)，則算法需要多次迭代才能結(jié)束。甚至，在有些情況下，結(jié)束時(shí)所得到的結(jié)果僅僅是局部最優(yōu)解，同時(shí)目標(biāo)函數(shù)的值也會(huì)隨著迭代次數(shù)的增加而逐漸變大，在第6次運(yùn)行中，傳統(tǒng)算法經(jīng)過了較長的13次迭代才最終結(jié)束運(yùn)算，而且得到了12.00%的錯(cuò)誤率，簇中心的位置符合真實(shí)的分布情況。而第8次運(yùn)算，算法甚至經(jīng)過了14次迭代，運(yùn)算才得以結(jié)束，同時(shí)得到較高的錯(cuò)誤率，高達(dá)42.66%，算法顯然陷入了局部最優(yōu)解。

從表2可以看出，本文所提出的基于密度信息進(jìn)行的改進(jìn)算法不僅大大減少了迭代的次數(shù)，保證了算法運(yùn)行的穩(wěn)定性，而且避免了算法陷入局部最優(yōu)解的可能。通過實(shí)驗(yàn)可以看到，改進(jìn)的算法僅僅經(jīng)過2次迭代就達(dá)到收斂，得到的錯(cuò)誤率更低，遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)k-中心點(diǎn)聚類算法平均的迭代次數(shù)和錯(cuò)誤率，而且得到的簇中心也更加符合集合的真實(shí)分布情況。

表3 入侵檢測模型結(jié)果比較

由表3實(shí)驗(yàn)數(shù)據(jù)顯示，基于改進(jìn)的K-中心點(diǎn)聚類算法的入侵檢測系統(tǒng)經(jīng)驗(yàn)證不僅是有效可行的，而且檢測率也得以提高，誤報(bào)率有所降低。

5 結(jié)論

入侵檢測技術(shù)是計(jì)算機(jī)網(wǎng)絡(luò)安全的重要保障，本文提出了一種基于“密度”信息改進(jìn)的K-中心點(diǎn)算法，設(shè)計(jì)了入侵檢測系統(tǒng)。采用基于密度的方式抽取樣本集來確定初始中心點(diǎn)，充分考慮到訓(xùn)練集的分布情況，該算法通過將訓(xùn)練數(shù)據(jù)集轉(zhuǎn)換為標(biāo)準(zhǔn)的單位特征度量空間；然后利用密度信息對數(shù)據(jù)進(jìn)行初步劃分，并以此找到聚類中心，這樣得到的初始聚類中心相對準(zhǔn)確，算法穩(wěn)定性和時(shí)效性提高，同時(shí)有效降低了錯(cuò)誤率。對改進(jìn)的K-中心點(diǎn)算法的入侵檢測模型進(jìn)行檢測，提高了入侵檢測系統(tǒng)的性能。結(jié)果表明本文設(shè)計(jì)的檢測模型能夠有效抵抗異常攻擊，可行性和有效性高，與傳統(tǒng)的入侵檢測系統(tǒng)相比具備一定的實(shí)用價(jià)值。