基于K-means 算法的入侵檢測系統(tǒng)研究

鮑海燕

（晉中學院信息技術(shù)與工程學院，晉中030619）

1 入侵檢測的基本原理

隨著互聯(lián)網(wǎng)的發(fā)展，傳統(tǒng)的防護手段如加密手段、認證技術(shù)以及防火墻等對保護網(wǎng)絡(luò)安全來說越來越無能為力。入侵檢測技術(shù)能夠進行相應策略制定，制定出比以往防火墻更加嚴格的審查方案，對內(nèi)部程序的實時監(jiān)測，有效地進行惡意軟件的隔離與刪除提示。入侵檢測系統(tǒng)（IDS）使網(wǎng)管人員及時的處理入侵警報，識別防火墻不能識別的攻擊，在發(fā)現(xiàn)入侵企圖后提供必要的信息。IDS 需要更多的智能，它首先對數(shù)據(jù)進行分析，并且得出結(jié)果。

入侵檢測系統(tǒng)對于系統(tǒng)配置、界面以及通信方面的管理，數(shù)據(jù)源有很多種，主要有電腦主機上的信息、網(wǎng)絡(luò)信息以及其他系統(tǒng)信息，這里的入侵檢測系統(tǒng)具體如圖1 所示。

圖1 入侵檢測系統(tǒng)結(jié)構(gòu)圖

2 入侵檢測中的K-means算法

2.1 傳統(tǒng)的K-means算法

聚類分析是數(shù)據(jù)挖掘的主要任務(wù)之一。它從樣本數(shù)據(jù)出發(fā)，自動進行分類。該過程主要體現(xiàn)了數(shù)據(jù)的中值處理方法，首先需要進行類的劃分，該類主要設(shè)定一個閾值，并且把這一閾值中的程序數(shù)據(jù)看成擁有同一個中心的數(shù)據(jù)格式，并且將這些數(shù)據(jù)進行中心化處理，得到一個類的平均值，然后對這些類再次劃分，進行高一層級的類劃分，如此以往，到準則函數(shù)收斂完成為止。K-means 算法描述如表1 所示。

表1 K-means 算法描述

2.2 傳統(tǒng)的K-means算法的缺點

K-means 算法存在如下問題：首先傳統(tǒng)K-means算法的聚類個數(shù)是假設(shè)已知的，但事實卻很難得到；其次選擇合理的初始聚類中心是不容易實現(xiàn)的；無關(guān)點的影響會導致聚類中心偏離設(shè)定的位置，從而導致聚類不準確；對非球型的數(shù)據(jù)集聚類誤差較大。

3 改進的K-means算法的入侵檢測系統(tǒng)的設(shè)計

3.1 入侵檢測系統(tǒng)的設(shè)計

使用Snort 現(xiàn)有的六個模塊的成熟技術(shù)，加上關(guān)聯(lián)分析器、聚類分析模塊和異常檢測引擎，便可從所需的訓練數(shù)據(jù)中提取出入侵檢測所需的數(shù)據(jù)和模式[3]。系統(tǒng)通過嗅探器發(fā)現(xiàn)問題，解碼器進行解碼，預處理器進行規(guī)則庫里特征提取，檢測引擎檢測網(wǎng)絡(luò)正常行為模式，進而進行聚類分析和日志記錄。

入侵檢測系統(tǒng)的模塊包括數(shù)據(jù)包嗅探器、解碼器、預處理器、檢測引擎、規(guī)則庫、輸出模塊、關(guān)聯(lián)分析器、聚類分析模塊、異常檢測引擎[4]。

3.2 入侵檢測系統(tǒng)的數(shù)據(jù)挖掘過程

入侵檢測模型的數(shù)據(jù)挖掘流程：首先進行相應網(wǎng)絡(luò)中數(shù)據(jù)文件的收集，對正?；顒蛹肒-means 算法進行數(shù)據(jù)挖掘，得到的正常數(shù)據(jù)用于異常入侵檢測；其次收集出現(xiàn)的異常入侵數(shù)據(jù)集，在正?；顒訑?shù)據(jù)集中過濾入侵訓練數(shù)據(jù)集，用分類算法實現(xiàn)挖掘及區(qū)分正常網(wǎng)絡(luò)行為和入侵行為的區(qū)別，得到誤用檢測規(guī)則，誤用檢測便利用了這個不斷更新獲得的數(shù)據(jù)模型?；跀?shù)據(jù)挖掘的入侵檢測的主要環(huán)節(jié)設(shè)計和總體流程如圖2 所示。

圖2 基于數(shù)據(jù)挖掘的入侵檢測總體流程圖

3.3 改進的K-means算法

改進的K-means 算法的基本思想是，在原有算法的基礎(chǔ)上，用優(yōu)化初始中心位置的方法，提高運行效率和質(zhì)量。獲取集合中分布密度高的數(shù)據(jù)塊，為了使初始位置落在不同的類中，盡可能在距離相差大的塊中獲取初始位置。

文獻[8]提出基于最優(yōu)劃分的初始中心選擇方法，本文亦用數(shù)據(jù)集的概率分布特點和此方法結(jié)合起來得出改進的K-means 算法的起始中心。聚類密度是指為了得到k 個初始類劃分，需要估計數(shù)據(jù)集的類分布情況（依據(jù)每個數(shù)據(jù)對象附近的數(shù)據(jù)分布集估計）。此初始聚類中心采用對象位置ai表示（ai為數(shù)據(jù)集中的每一個對象），取距離ai最近的mins（mins 為類密度數(shù)量）個對象，密度參數(shù)θ為對應的最小半徑范圍，θ的值和ai的值是反比關(guān)系。密度閾用z（表示密度參數(shù)的規(guī)定的臨界值）表示，若θ比z 小，此數(shù)據(jù)對象稱為高密度點。高密度集合V 是指所有的數(shù)據(jù)集中的高密度點的集合。在V 中選取k 個分布分散的高密度點，最大的對象稱為b1，距離b1最遠的對象稱為高密度點b2，若密度點數(shù)量mins=7，假設(shè)有三個中心點，密度參數(shù)分別為5，9，3，密度閾值z=6，則三個中心點鐘有兩個小于密度閾值，這兩個點為高密度點，組成的集合V 為高密度集合。計算V 中每個高密度點ai到每個類中心點的距離v（ai，b1），v（ai，b2），v（ai，bf-1），則第f 個類中心點滿足：max（min（v（ai，b1），v（ai，b2），v（ai，bf-1））），第k 個高密度點集合為（b1，b2，…，bk）。

如果想得到較好的K-means 初始中心，就需要運用粒子群優(yōu)化算法得到k 個初始類劃分靠近類中心的位置。利用文獻[1]迭代POS 算法（初始化每個粒子的位置、速度、全局最優(yōu)位置和歷史最有位置）找出個各類的最優(yōu)全局位置，最終輸出聚類結(jié)果。對于數(shù)據(jù)集A，集中包含m 個對象，n 個屬性。對于數(shù)據(jù)集中的數(shù)據(jù)對象ai，初始最優(yōu)位置為qi，數(shù)據(jù)集所有對象中第j個屬性的變化范圍：

第j 個屬性的初始值為：

每一個對象都利用公式得到初始化最優(yōu)位置，第l個對象局部最優(yōu)位置到數(shù)據(jù)集中其他對象的最大距離，取其中最小值為全局最優(yōu)位置，如公式（3）所示。

若第l 個對象的當前位置al滿足，則用對象當前位置al更新局部最優(yōu)位置ql，可得到新的局部最優(yōu)位置，更新兩個最優(yōu)位置后，更新數(shù)據(jù)集中的對象速度（與對象的當前速度、局部最優(yōu)位置、全局最優(yōu)位置線性相關(guān)）。如此的迭代尋優(yōu)，會在每個類中產(chǎn)生一個全局最優(yōu)位置（當PSO 算法達到最大迭代次數(shù)時），此位置為類心。

將這k 個全局最有位置作為改進后的K-means 算法的起始聚類位置，改進后的K-means 算法描述如表2 所示。

表2 改進的K-means 算法描述

4 基于改進的K-means算法的入侵檢測系統(tǒng)模型

根據(jù)改進的K-means 算法，提出了新的基于聚類的網(wǎng)絡(luò)入侵檢測模型，如圖3 所示。

圖3 改進的K-means算法入侵檢測系統(tǒng)模型

上述模型中的原始數(shù)據(jù)來自網(wǎng)絡(luò)運行中產(chǎn)生的以服務(wù)器網(wǎng)絡(luò)日志為主的數(shù)據(jù)，數(shù)據(jù)收集模塊的數(shù)據(jù)來源于檢測及網(wǎng)上用抓包工具采集的IP 數(shù)據(jù)包。

采用數(shù)據(jù)挖掘技術(shù)提升入侵行為的檢測率，通過訓練數(shù)據(jù)提取出可用于入侵檢測的模式及知識，將部分數(shù)據(jù)用來分析，建立起基于數(shù)據(jù)挖掘的入侵檢測系統(tǒng)，系統(tǒng)具有以下幾個優(yōu)點[5]：

（1）智能性好

系統(tǒng)具有較高的自動化運行的能力，容易擴展，不僅提高了該系統(tǒng)的適用范圍，通過研究人員的努力，也提高了檢測的正確率。

（2）檢測效率高

通過數(shù)據(jù)挖掘，可以大大提高處理數(shù)據(jù)的能力，通過對樣本的一次提取，在一次提取過程中，抽取其中正確的部分與數(shù)據(jù)同時進行預處理，可以大大提高信息處理量。

（3）自適應能力比較強

由于系統(tǒng)選擇的方法是一種應用數(shù)據(jù)挖掘方法，因此具有較高的適應能力，同時又能夠?qū)τ谌肭謱ο蠹捌渥兎N進行檢測。

（4）誤警率低

數(shù)據(jù)挖掘能夠有效地去除重復的多種攻擊數(shù)據(jù)，所以將數(shù)據(jù)挖掘應用于入侵檢測中可以達到較低的誤警率。

5 基于改進的K-means算法的入侵檢測仿真實驗分析

5.1 K-means算法的聚類效果進行比較

入侵檢測實驗系統(tǒng)是在Windows 10 的系統(tǒng)下搭建的，數(shù)據(jù)集采用的UCI 官網(wǎng)數(shù)據(jù)，實驗用對iris 數(shù)據(jù)集、4k2_far 數(shù)據(jù)集和wine 數(shù)據(jù)集在傳統(tǒng)K-means 算法和改進的K-means 算法的聚類效果進行比較，實驗采用的是聚類評估指標是聚類純度Purity 指標（0-1 之間），N 為數(shù)據(jù)集中數(shù)據(jù)對象數(shù)，k 是聚類數(shù)，Bj 是第j個聚類結(jié)果中聚類對象個數(shù)。定義如下：

聚類結(jié)果的準確率與Purity 指標成正比。本次仿真實驗聚類效果如表3 所示。

表3 聚類效果對比表

5.2 入侵檢測實驗

改進的K-means 算法使用的數(shù)據(jù)集是KDD CUP99 數(shù)據(jù)集中的kddcup.data_10_percent 訓練數(shù)據(jù)集中的4000 條數(shù)據(jù)，其中100 條標記為DoS 攻擊類型的數(shù)據(jù)（smurf 攻擊、pod 攻擊、back 攻擊各30 條，剩余的為teardrop 攻擊），其余為正常數(shù)據(jù)。

使用K-means 算法聚類時的迭代代數(shù)F2=100，類密度數(shù)Mins=100，密度閾值w=1.45，利用PSO 迭代尋優(yōu)時的最大迭代次數(shù)F1=10，取聚類值為k=3 和k=4 時做分析，傳統(tǒng)的K-means 算法和改進的K-means 算法對比試驗，每種聚類進行了兩次實驗。如表4-表5 所示。

表4 k=3 的聚類中心變化表

當k=3 時，傳統(tǒng)的K-means 算法第2 次聚類實驗出現(xiàn)了一個空聚類，改進的K-means 算法沒有出現(xiàn)空聚類。

表5 k=4 的聚類中心變化表

當k=4 時，傳統(tǒng)的K-means 算法第1 次聚類實驗出現(xiàn)了兩個空聚類，第2 次聚類實驗出現(xiàn)了一個空聚類，改進的K-means 算法沒有出現(xiàn)空聚類。

從上述的實驗數(shù)據(jù)可以得到，在kddcup.data_10_percent 數(shù)據(jù)集進行聚類分析的過程中，K-means 算法可能出現(xiàn)空聚類，聚類結(jié)果波動較大。而改進的Kmeans 算法基本不會出現(xiàn)空聚類的現(xiàn)象，穩(wěn)定性顯著提高。

入侵檢測的仿真模型有兩個重要指標，檢測率（JC）和誤報率（WB），JC 由檢測出來的異常記錄數(shù)量除以測試集中總的異常記錄數(shù)量。WB 由誤判入侵的正常記錄數(shù)除以測試集中總的正常記錄數(shù)量。在k=3 和k=4 的情況下，取類標記β=2.75%，通過分析得到JC 和WB 的結(jié)果如表6 所示。

表6 入侵檢測結(jié)果分析

從表中可以看出，傳統(tǒng)K-means 算法的平均檢測率為42%，改進的K-means 算法的平均檢測率為74%，檢測率提高了32%。傳統(tǒng)K-means 算法的誤報平均率為0.337%，改進的K-means 算法的誤報平均率為0.179%，誤報率下降了0.158%。

6 結(jié)語

本文主要是對K-means 算法應用于入侵檢測系統(tǒng)做了詳細的闡述。介紹了傳統(tǒng)的K-means 算法和它的優(yōu)缺點，提出了優(yōu)化初始中心的K-means 算法的改進措施，改進的K-means 算法應用到入侵檢測系統(tǒng)中，可提高入侵檢測的成功率和降低誤報率。

入侵檢測技術(shù)和數(shù)據(jù)挖掘技術(shù)的結(jié)合，能在以前的入侵檢測系統(tǒng)的基礎(chǔ)上，更好地檢測出入侵并加以防范。