基于一種改進(jìn)K-means算法的入侵檢測系統(tǒng)研究

謝霖銓 張思潔

（1.江西理工大學(xué)應(yīng)用科學(xué)學(xué)院，江西 贛州 341000；2.江西理工大學(xué)理學(xué)院，江西贛州 341000）

當(dāng)今社會是一個網(wǎng)絡(luò)化的信息時代，但隨著網(wǎng)絡(luò)應(yīng)用范圍的不斷擴(kuò)大，對網(wǎng)絡(luò)的各類攻擊與破壞也隨之而來。當(dāng)前，國際信息安全領(lǐng)域的一種重要手段就是入侵檢測。入侵檢測技術(shù)由異常檢測和誤用檢測［1］組成，誤用檢測通常需要設(shè)定好檢測模型，具有高的檢測率，但是只能檢測已知類型。對于異常檢測，由于人們主要依賴于他們的直覺和經(jīng)驗(yàn)選擇統(tǒng)計(jì)特性，因此具有較高的誤報(bào)率［2］。

數(shù)據(jù)挖掘技術(shù)在融合不同領(lǐng)域方法的基礎(chǔ)上，利用分析工具從大量復(fù)雜數(shù)據(jù)中獲取對用戶有用的信息［3］。通過數(shù)據(jù)挖掘的方法可以構(gòu)建自動的檢測模型用以降低數(shù)據(jù)分析的難度和復(fù)雜度［4］。由于K-means算法運(yùn)用的廣泛性且由于該算法收斂速度快并可用于較大型的數(shù)據(jù)，因此選取該算法為基礎(chǔ)。將最大距離積法的K-means算法用于入侵檢測是削弱隨機(jī)初始化聚類中心所帶來的影響。對已知類型的訓(xùn)練集進(jìn)行分析和選取，用于整個系統(tǒng)的運(yùn)行。實(shí)驗(yàn)結(jié)果表明，該方法用于入侵檢測系統(tǒng)達(dá)到了良好的結(jié)果。

1 聚類分析算法

根據(jù)事物間的某種相似性對事物進(jìn)行劃分和歸類的過程稱之為聚類，結(jié)果能得到一組具有較高相似度的對象［5］。

根據(jù)聚類算法所采用的基本思想將聚類分成幾類［6］。其中基于分割的K-means算法是實(shí)用性強(qiáng)、應(yīng)用比較廣泛的一類。

標(biāo)準(zhǔn)測度函數(shù)［7］，定義為

傳統(tǒng)的K-means算法描述如下：

1.1 隨機(jī)初始化K個簇中心；

1.2 計(jì)算每個數(shù)據(jù)對象到K個簇中心的距離，根據(jù)相似度將該數(shù)據(jù)對象放入對應(yīng)的簇中。

1.3 重新計(jì)算所有聚類的均值，并且計(jì)算出此時的測度函數(shù)值。

1.4 如果達(dá)到maxStep或滿足：

其中ε是一個極小數(shù)。式（2）表示當(dāng)簇成員不再更改時聚類結(jié)束，否則，返回（2）。

K-means算法的使用范圍非常廣泛，算法簡單又易于操作，復(fù)雜度低，處理數(shù)據(jù)非?？旖荨５怯捎谠嫉腒-means本身的一切缺陷，會產(chǎn)生以下一些問題［6-8］：①初始聚類中心選取的不確定性影響著聚類的結(jié)果；②如果選擇了不正確的初始值，算法可能陷入局部最小值；③方法不適合處理形狀延展性較強(qiáng)的簇；④對K值的選取需要用戶適當(dāng)調(diào)節(jié)；⑤對異常數(shù)據(jù)很敏感。針對缺陷① ②，將最大距離積法改進(jìn)于K-means算法并用于入侵檢測。

2 基于一種改進(jìn)K-means算法的入侵檢測系統(tǒng)

受到文獻(xiàn)［8］的啟發(fā)，把融合了最大距離積的K-means算法用于入侵檢測領(lǐng)域，盡可能地稀疏聚類中心［9］，代替?zhèn)鹘y(tǒng)K-means算法中隨機(jī)初始化K個聚類中心這一步驟。

具體的算法描述如下：

2.1計(jì)算d（Xi，Xj）。

2.2 通過密度參數(shù)MinPts和ε，得到處于高密度點(diǎn)的數(shù)據(jù)對象集合D。

2.3 D中選取一個數(shù)據(jù)對象作為第1個聚類中心Z1，計(jì)入到集合Z中，并從D刪除；在集合D距離Z1最遠(yuǎn)的一個高密度點(diǎn)作為第2個聚類中心Z2，并將其加入到Z中，在集合D中刪除。

2.4 計(jì)算D中所有數(shù)據(jù)對象到集合Z中每個聚類中心的距離d（Xi，Z），（Z=Z1，Z2…Z（tt＜k）），選擇滿足max（d（Xi，Z1）×d（Xi，Z2）×…×d（Xi，Z）t），（i=1，2，3…n），將找到點(diǎn)最為新的聚類中心加入到Z中。

2.5 直到Z中的聚類中心數(shù)目達(dá)到K個，則不必再進(jìn)行上一步驟。

2.6 得到全部初始聚類中心。

基于最大距離積法的K-means算法可以降低聚類結(jié)果對于初始中心的敏感性產(chǎn)生的影響，避免由于中心對象選取稠密而導(dǎo)致的聚類沖突，并且能夠體現(xiàn)數(shù)據(jù)集的分布狀態(tài)［10］。

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

在KDD CUP99提供的10%數(shù)據(jù)集中，包含了特征比較明顯的4大類網(wǎng)絡(luò)攻擊［11］：DOS、Probe、U2R、R2L。

其中訓(xùn)練數(shù)據(jù)集包括23種攻擊行為，測試數(shù)據(jù)集包含38種攻擊行為。由于U2R和R2L兩種攻擊的特殊性，因此需要選取較多與內(nèi)容特征有關(guān)的屬性。文章只選取service，flag，hot等15個特征屬性作為研究的特征屬性值。

表1 文獻(xiàn)［4］的入侵檢測結(jié)果

表2 基于改進(jìn)的K-means算法的入侵檢測結(jié)果

為了營造一個與現(xiàn)實(shí)入侵檢測相差不大的環(huán)境，從10%數(shù)據(jù)集中隨機(jī)抽取100 000條數(shù)據(jù)共分成5組，其中入侵?jǐn)?shù)據(jù)占1.5%共1 500條。這樣的目的是希望可以檢測出改進(jìn)算法對于不同種類入侵?jǐn)?shù)據(jù)的檢測效果，并且由于每個數(shù)據(jù)集中入侵?jǐn)?shù)據(jù)明顯低于正常數(shù)據(jù)的數(shù)量，也符合現(xiàn)實(shí)網(wǎng)絡(luò)入侵行為的特性。兩個算法均在閾值q=0.4，K-means算法中K=5的條件下進(jìn)行。實(shí)驗(yàn)是在CPU：2.70GHZ，內(nèi)存2GB，Window7的平臺上，開發(fā)環(huán)境為VC++6.0的環(huán)境下實(shí)現(xiàn)預(yù)處理和改進(jìn)的K-means算法數(shù)據(jù)處理。

實(shí)驗(yàn)是在算法能正常進(jìn)行的基礎(chǔ)上通過得到的檢測率和誤報(bào)率來判斷系統(tǒng)性能的優(yōu)劣。表1和表2對比可以明顯看出該算法檢測率方面優(yōu)于文獻(xiàn)［4］，同時誤報(bào)率也更低。但是由表中也可以看出，改進(jìn)算法在R2L、U2R攻擊方面的檢測率偏低，這是由于這兩種攻擊的比率在訓(xùn)練集和測試集相差過大，并且由于網(wǎng)絡(luò)數(shù)據(jù)文段的非結(jié)構(gòu)化信息中特征不易提取，因此R2L和U2R的檢測率相比于DOS和Probe兩種攻擊更低，對此，需要進(jìn)行更加深刻的特征描繪。對于DOS和Probe兩種攻擊而言，檢測率和誤報(bào)率都處于相對比較理想的狀態(tài)，這兩種攻擊在某些屬性的變化與正常數(shù)據(jù)相差過大，過大的差異性利于檢測率的提高。

4 結(jié)論

本文融合了最大距離積法的聚類分析在基于密度的思想上的應(yīng)用，充分體現(xiàn)了數(shù)據(jù)的自然分布，將該算法全新地應(yīng)用于入侵檢測系統(tǒng)中除了保證檢測的有效性之外，還可以對于攻擊取得較高的檢測率和較低的誤報(bào)率。在接下來的研究中可以根據(jù)R2L和U2R攻擊本身存在的問題進(jìn)行屬性特征的提取，以便在今后的研究中取得更好的效果。

［1］楊智君，田地，馬駿驍，等.入侵檢測技術(shù)研究綜述［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（12）：2119-2123.

［2］薛靜鋒，曹元大.基于數(shù)據(jù)挖掘的入侵檢測［J］.計(jì)算機(jī)工程，2003，29（9）：17-18.

［3］梁煜.數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)入侵檢測中的應(yīng)用研究［J］.電腦編程技巧與維護(hù)，2014（2）：93-94.

［4］杜強(qiáng)，孫敏.基于改進(jìn)聚類分析算法的入侵檢測系統(tǒng)研究［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：106-108.

［5］王令劍，滕少華.聚類和時間序列分析在入侵檢測中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2010，30（3）：699-701.

［6］賀玲，吳玲達(dá)，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（1）：10-13.

［7］熊忠陽，陳若田，張玉芳.一種有效的K-means聚類中心初始化方法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28（11）：4188-4190.

［8］周涓，熊忠陽，張玉芳，等.基于最大最小距離法的多中心聚類算法［J］.計(jì)算機(jī)應(yīng)用，2006，26（6）：1425-1427.

［9］樊曉光，路釗，王久崇，等.基于密度和距離積的聚類中心選取方法［J］.測控技術(shù)，2013，32（10）：152-154.

［10］Zhang X Y，Zeng H S，Jia L.Research of intrusion detection system dataset-KDD CUP99［J］.Computer Engineering&Design，2010，31（22）：4809-4805.

［11］王潔松，張小飛.KDDCup99網(wǎng)絡(luò)入侵檢測數(shù)據(jù)的分析和預(yù)處理［J］.科技信息：科學(xué)教研，2008（15）：407-408.