基于改進人工蜂群優(yōu)化K-means的入侵檢測模型

于立婷，譚小波，解 羽

(沈陽理工大學 信息科學與工程學院，沈陽 110159)

無線傳感器網(wǎng)絡(Wireless Sensor Network，WSN)是一種分布式傳感網(wǎng)絡，通過大量靜止或移動的傳感器節(jié)點以自組織和多跳的方式形成，并以傳感器節(jié)點之間相互協(xié)作的方式來采集、處理和傳輸網(wǎng)絡覆蓋區(qū)域內所被感知對象的信息，最后將這些信息發(fā)送給網(wǎng)絡的所有者[1]。WSN由于其能耗低、成本低等優(yōu)點，廣泛應用于工業(yè)監(jiān)測[2]、智能交通[3]和醫(yī)療衛(wèi)生[4]等領域。但隨著WSN的大規(guī)模應用，也暴露了一些缺陷：(1)由于WSN需要根據(jù)不同的應用環(huán)境來提供服務，所以網(wǎng)絡一旦被部署就不能重復利用，從而增加了WSN的部署成本；(2)現(xiàn)有的分布式控制、拓撲維護和路由算法等將帶來大量的計算和信息交互，這將加快節(jié)點能量消耗的速度，極大縮短傳感器節(jié)點以及整個網(wǎng)絡的生命周期；(3)WSN采用多跳的傳輸方式，當網(wǎng)絡中某些節(jié)點任務過載或連接斷開時，無法動態(tài)改變路由機制，導致數(shù)據(jù)傳送失敗，使得整個網(wǎng)絡狀態(tài)不穩(wěn)定，甚至癱瘓。

針對上述缺陷，許多學者將軟件定義網(wǎng)絡(Software Defined Network，SDN)[5]架構引入WSN中，形成一種新型的網(wǎng)絡架構——軟件定義WSN(Software Defined Wireless Sensor Network，SD-WSN)[6-7]。相比于傳統(tǒng)的WSN，SD-WSN可以根據(jù)實際需求，對傳感器網(wǎng)絡中節(jié)點的感知通信半徑以及節(jié)點運行狀態(tài)進行動態(tài)調整，并且SD-WSN還可以通過編程的方式重新配置網(wǎng)絡設備的參數(shù)來應對突發(fā)的故障，實現(xiàn)實時監(jiān)控和維護網(wǎng)絡設備性能，減少了人工維護的成本和難度，大大提高網(wǎng)絡管理的效率。

然而，網(wǎng)絡安全是SD-WSN實用化的前提條件，而SD-WSN在集中控制下，控制器的入侵攻擊是SD-WSN面臨的最大威脅[8-9]。目前，針對SD-WSN安全方面的研究較少，考慮到網(wǎng)絡架構的繼承性，部分SDN中的入侵檢測方案具有一定借鑒性。

姬生生[10]提出了一種基于SDN和Bloom Filter的入侵檢測方案，通過量化網(wǎng)絡流量關鍵值和網(wǎng)絡入侵行為的參數(shù)特征，采用分層檢測的方式，圍繞關鍵節(jié)點選擇監(jiān)測節(jié)點；該方案提高了主控節(jié)點檢測的準確性，并減小整個網(wǎng)絡的能量消耗，但在檢測率上有待提高。Maggi等[11]提出了一種基于SOM的DDoS攻擊檢測方法，該方法在SDN網(wǎng)絡環(huán)境下，通過構建流量的六元組特征矩陣的方法，并采用SOM分類算法來檢測，但需要花費較長的訓練時間。石冬冬[12]提出的一種基于數(shù)據(jù)挖掘K-means算法的異常檢測模型，具有較低的誤檢率，但需要對大量數(shù)據(jù)進行預處理訓練和分類，存在較長的訓練過程。Nasrin等[13]提出了一種基于系統(tǒng)調用序列和參數(shù)分析的入侵檢測系統(tǒng)，在四種針對系統(tǒng)調用的字符串類型的統(tǒng)計模型基礎上，引入“聚類”概念，使用聚類參數(shù)推斷出同一系統(tǒng)調用的不同使用方式，建立更準確的參數(shù)模型，能夠正確識別異常情況，但運行耗費較高。

綜上所述，基于聚類的入侵檢測算法過度依賴聚類中心的選取，采用人為經(jīng)驗或隨機取樣的方法選取聚類中心存在一定風險，在一定程度上降低了K-means算法的聚類效果。由此，本文提出了一種基于改進人工蜂群優(yōu)化的K-means入侵檢測模型，該模型采用改進的人工蜂群算法對K-means算法中的初始聚類中心的選擇進行優(yōu)化，并采用基于劃分的K-means算法對網(wǎng)絡中的數(shù)據(jù)進行聚類分析。實驗結果表明，基于人工蜂群優(yōu)化的K-means入侵檢測模型可以在較小的迭代次數(shù)下選擇出優(yōu)化的聚類中心，并在聚類效果方面表現(xiàn)出較高的檢測率和較低的誤報率，達到了較好的檢測效果。

1 改進人工蜂群優(yōu)化K-means算法

傳統(tǒng)K-means算法并不能達到較好的聚類效果，本文將采用優(yōu)化適應度函數(shù)的方法改進傳統(tǒng)的人工蜂群算法，并且采用改進后的算法對K-means算法的初始聚類中心的選擇進行優(yōu)化，進而提出改進的人工蜂群優(yōu)化K-means算法。

1.1 K-means算法

K-means聚類算法的基本思想是在數(shù)據(jù)集中隨機選取k個樣本，將這些樣本定義為初始聚類中心，然后計算其余樣本到聚類中心的距離，并且將這些樣本歸類到距離其最近的聚類中心所屬的類簇中。當樣本中的所有數(shù)據(jù)都分配到所屬的類中，再通過迭代計算類簇中數(shù)據(jù)的平均值得到新的初始聚類中心。當?shù)蟮木垲愔行内呌谙嘟鼤r，即平方誤差準則函數(shù)趨于收斂，則算法結束，否則繼續(xù)下一次初始聚類中心的選擇。平方誤差準則函數(shù)如下。

(1)

式中：x(i)表示第i個類簇；μc(i)表示第i個類簇的均值。各類簇內的樣本越相似，該類內樣本的平方誤差越小。樣本之間的距離使用歐幾里得來計算。K-means算法流程圖如圖1所示。

圖1 K-means聚類算法流程圖

1.2 改進的人工蜂群算法

1.2.1 人工蜂群算法

蜂群算法最開始由Seeley在1995年提出，之后被學者Karaboga應用在函數(shù)的極值問題的求解中，并以此提出了人工蜂群算法[14](Arificial Bee Colony，ABC)。該算法受蜜蜂采蜜的啟發(fā)，根據(jù)蜜蜂在采蜜過程中的角色轉換所設計，模擬蜜蜂不斷地尋找優(yōu)秀蜜源的過程，并最終找到全局最優(yōu)蜜源。人工蜂群算法的主要思想如下。

設有N個蜜源{x1,x2…xN}，每個蜜源都代表一組問題的解，可以用d維向量來表示每個問題的解。假設蜜蜂總共進行循環(huán)M次，每個蜜源可以被蜜蜂重復開采L次。

初始化階段：隨機產(chǎn)生N組d維向量作為N組解，然后計算每組解的適應度值，將解按照適應度值的大小進行排列，將適應度值大的一半作為引領蜂，剩下的一半作為跟隨蜂。引領蜂在其蜜源周圍進行領域搜索，根據(jù)式(2)產(chǎn)生一個新的蜜源。比較兩個食物源的適應度值，并保留適應度值較好的蜜源。

Xij=xij+rij(xij-xkj)

(2)

式中：Xij代表xij附近的一個新的位置；k、j都屬于隨機數(shù)，k=1,2…N，并且k≠i；rij∈[-1,1]，使得新位置約束在xij附近；xij為原蜜源。

跟隨階段：跟隨蜂根據(jù)引領蜂所選擇蜜源的適應度值，利用輪盤賭方法，根據(jù)式(3)得到的概率尋找合適的引領蜂。選擇后，跟隨蜂根據(jù)式(2)在蜜源的領域產(chǎn)生一個新的蜜源，并且比較前后兩個蜜源的適應度值，保留適應度函數(shù)較好的蜜源。

(3)

式中：fitnessi表示第i個蜜源的適應度值；Pi表示跟隨蜂選擇下一個引領蜂的概率。當引領蜂經(jīng)過L次循環(huán)蜜源沒有變化后，則引領蜂離開該蜜源，變?yōu)閭刹旆洌^續(xù)去尋找新的蜜源。

1.2.2 改進適應度值的人工蜂群算法

傳統(tǒng)人工蜂群算法在初始搜索階段不一定可以保證優(yōu)秀蜜源的全局搜索，且在隨后的搜索中也可能陷入局部最優(yōu)的情況，影響算法的整體性能。而適應度函數(shù)將會對種群的尋優(yōu)方向、進化行為、迭代次數(shù)和尋優(yōu)結果有著重要的影響，因此本文通過改進適應度函數(shù)的方法，使其在初始階段搜索范圍擴大，避免陷入局部最優(yōu)。改進過程如下。

定義1 設X為數(shù)據(jù)集，X={x1,x2,…,xn}，假設其中的k個樣本數(shù)據(jù)被聚類劃分成類Si，Si={x1,x2…xk}，定義類內距離dbet(Si)為類Si中任意兩個數(shù)據(jù)x、y的平方和。

dbet(Si)=∑x,y∈Si‖x-y‖2

(4)

定義2 設X為數(shù)據(jù)集，X={x1,x2,…,xn}，假設其中的k個樣本數(shù)據(jù)被聚類劃分為類Si，Si={x1,x2…xk}，定義類間距離dwit(Si,Sj)為類Si到其他類Sj的距離，則

(5)

式中：k、p分別為類Si和類Sj中的數(shù)據(jù)對象個數(shù)；x、y分別為類Si和類Sj中的數(shù)據(jù)對象。

本文將類間距離的倒數(shù)和類內距離進行加和得到蜜源的適應度函數(shù)，一組數(shù)據(jù)的聚類結果與類間距離、類內距離都有密切的影響，類間距離越小，說明數(shù)據(jù)之間的聚類效果越好。因此，本文最后采用的適應度函數(shù)為

(6)

1.3 改進的人工蜂群優(yōu)化K-means算法

根據(jù)以上對適應度值的改進，提出了改進的人工蜂群優(yōu)化K-means算法。該算法的基本思想是：通過改進的人工蜂群算法進行一次迭代，將所得到的一組解作為K-means算法的初始聚類中心并進行一次K-means聚類，用聚類后得到的新的聚類中心去更新蜂群，作為下一次的初始蜜源；如此不斷迭代執(zhí)行人工蜂群算法和K-means算法，直到達到事先設定的最大迭代次數(shù)。算法的具體步驟如下。

(1)設置引領蜂、跟隨蜂和偵察蜂的數(shù)量，最大迭代次數(shù)Max以及控制參數(shù)Limit；當前迭代次數(shù)Cycle，初始值為1；聚類類別數(shù)K，隨機選擇N個蜜蜂，產(chǎn)生初始蜂群{Z1,Z2,…，ZN}。

(2)根據(jù)式(6)計算蜂群中每只蜜蜂所代表的初始聚類中心的適應度值，并排列優(yōu)先級，選取適應度值高的蜜蜂作為引領蜂，其余作為跟隨蜂。

(3)利用公式(2)進行領域搜索，得到新位置，并計算該位置的適應度值。若適應度值高于原位置，則新位置將代替原位置，否則，保留原位置。當所有引領蜂完成搜索后，利用式(3)計算概率Pi。

(4)跟隨蜂根據(jù)概率Pi，采用輪盤賭的方法選擇引領蜂。Pi越大，引領蜂選擇蜜源的適應度值越大，該蜜源被跟隨蜂選擇的機會也就越大。當跟隨蜂完成選擇，轉變?yōu)橐I蜂后，利用式(2)繼續(xù)進行領域搜索，依據(jù)貪婪算法選擇適應值更高的位置。

(5)在所有跟隨蜂完成搜索后，將得到的位置作為K-means算法的初始聚類中心，對數(shù)據(jù)集中的數(shù)據(jù)進行一次聚類，得到新的聚類中心作為人工蜂群算法的初始蜜源去更新蜂群。

(6)如果引領蜂在經(jīng)過次迭代后，其位置沒有任何改變，則引領蜂將轉變?yōu)閭刹旆?，并采用新位置代替原位置?/p>

(7)如果當前迭代次數(shù)大于先前所設定的最大次數(shù)Max，則迭代結束，算法結束；否則轉到第2步，Cycle=Cycle+1。

2 仿真實驗與結果分析

為了比較該算法的性能，將在Matlab環(huán)境下對K-means算法、傳統(tǒng)人工蜂群算法優(yōu)化K-means算法以及改進人工蜂群優(yōu)化K-means算法進行仿真。

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

實驗數(shù)據(jù)為目前應用廣泛的KDD CUP99數(shù)據(jù)集，該數(shù)據(jù)集來自于美國空軍局域網(wǎng)連續(xù)9個星期的網(wǎng)絡數(shù)據(jù)，其組成是帶有標識的訓練數(shù)據(jù)和未標記的測試數(shù)據(jù)[15-16]。在訓練數(shù)據(jù)集中包含了正常數(shù)據(jù)類型normal和22種攻擊類型的數(shù)據(jù)組成，如表1所示。

表1 KDD CUP99入侵檢測實驗數(shù)據(jù)的標識類型

KDD CUP99訓練數(shù)據(jù)集包含了1個類標識和41個固定的特征屬性，41個固定的特征屬性包含34個連續(xù)屬性和7個離散屬性。本實驗采用KDD CUP99數(shù)據(jù)集中的攻擊類型的10%抽樣kddcup.data_10_percent，將該數(shù)據(jù)集按照4∶1的比例分為訓練數(shù)據(jù)集和測試數(shù)據(jù)集[17]。根據(jù)SD-WSN實時獲取信息的特點，本文將描述節(jié)點流量變化及更新維護網(wǎng)絡數(shù)據(jù)統(tǒng)計信息所需的流量特征加入到數(shù)據(jù)集中，如表2所示。

表2 網(wǎng)絡特征屬性

表2中流量相關的的屬性值用于DDOS攻擊檢測；路徑相關的屬性值用于路由攻擊檢測。將表2中的特征屬性加入到簡化的KDD CUP99數(shù)據(jù)集中，并通過仿真模擬得到包含這些屬性的數(shù)據(jù)，如表3所示。

2.2 數(shù)據(jù)預處理

數(shù)據(jù)預處理是在算法建模之前，對數(shù)據(jù)的異常和缺失等情況進行處理。并以此來提高挖掘數(shù)據(jù)的效果，數(shù)據(jù)預處理的流程如圖2所示。

表3 加入屬性后的KDD CUP99數(shù)據(jù)集

圖2 數(shù)據(jù)預處理過程

2.2.1 數(shù)據(jù)清洗

數(shù)據(jù)清洗是將數(shù)據(jù)中一些與數(shù)據(jù)本身并無關聯(lián)的數(shù)據(jù)去掉，保留關鍵數(shù)據(jù)，同時采用全局變量、數(shù)據(jù)屬性的均值填補空缺數(shù)據(jù)，使數(shù)據(jù)集平滑，提高實驗結果準確度。

2.2.2 格式轉換

格式轉換的過程將KDD數(shù)據(jù)集的41個屬性中非數(shù)值類型的數(shù)據(jù)轉換為數(shù)值類型的數(shù)據(jù)，并需要將數(shù)據(jù)進行離散化處理，這種方式將需要分析的數(shù)據(jù)量精簡，以此更好的提高聚類的效果。

2.2.3 歸一化

歸一化的過程是為了消除特征屬性值之間的量綱影響，將數(shù)據(jù)集特征屬性值之間存在較大差異的數(shù)據(jù)進行處理，使數(shù)據(jù)的絕對值轉換成相對值，以此加快梯度下降求最優(yōu)解的速度。

對數(shù)據(jù)進行歸一化處理，其公式如下所示。

(7)

此方法將原始數(shù)據(jù)進行了等比縮放，式中Xnorm為利用公式歸一化后的數(shù)據(jù)，X′為原始的入侵檢測數(shù)據(jù)，Xmax、Xmin分別是原始入侵檢測數(shù)據(jù)中每一個屬性的最大值和最小值。處理后的數(shù)據(jù)如表4所示。

表4 預處理后的KDD CUP99數(shù)據(jù)集

2.3 實驗結果與分析

在Matlab環(huán)境下，對預處理后的數(shù)據(jù)集采用改進的人工蜂群優(yōu)化K-means入侵檢測模型進行訓練，使用測試集中(測試集是帶有標記的數(shù)據(jù))的每一條數(shù)據(jù)計算其與分類模型中所有類簇中心的距離，將每條數(shù)據(jù)歸類到離它最近的類簇當中，根據(jù)類簇上的標記對每條數(shù)據(jù)進行異常檢測，區(qū)分正常數(shù)據(jù)和異常數(shù)據(jù)。

利用改進的人工蜂群算法對數(shù)據(jù)集進行尋優(yōu)，并記錄迭代200次和400次的適應度函數(shù)值。圖3和圖4分別是對數(shù)據(jù)集進行200次和400次迭代后的適應度函數(shù)值曲線。

圖3 200次迭代適應度函數(shù)值

由圖3可知，改進的人工蜂群優(yōu)化K-means算法的適應度函數(shù)值較傳統(tǒng)的人工蜂群優(yōu)化K-means算法有相對的降低。表明改進后的算法在聚類效果上有了明顯的提高。由圖4可知，傳統(tǒng)人工蜂群優(yōu)化K-means算法在迭代150次達到最優(yōu)，而改進的人工蜂群優(yōu)化K-means算法在迭代的前100次快速收斂，并達到極優(yōu)值，在迭代100次后無限接近于最優(yōu)值，較傳統(tǒng)的人工蜂群優(yōu)化K-means算法迭代速度明顯加快。

圖4 400次迭代適應度函數(shù)值

與改進的K-means算法不同，傳統(tǒng)K-means算法k值的確定是隨機選擇的，而k值的選擇在很大程度影響聚類結果。因此，本實驗根據(jù)k值的選取情況，利用檢測率和誤檢率兩項指標，如式(8)、式(9)所示，對傳統(tǒng)的K-means算法、傳統(tǒng)人工蜂群優(yōu)化的K-means算法以及改進的人工蜂群優(yōu)化K-means算法進行評價。實驗結果如表5所示。

(8)

(9)

表5 檢測率和誤檢率 %

圖5為K-means算法、傳統(tǒng)人工蜂群優(yōu)化的K-means算法以及改進的人工蜂群優(yōu)化K-means算法的檢測響應時間曲線。

由圖5可知，相比于K-means算法和傳統(tǒng)人工蜂群優(yōu)化的K-means算法，改進的人工蜂群優(yōu)化K-means算法隨著k值的增加，響應時間明顯低于其他算法。響應時間上的差距主要在K-means算法確定k值的方法上，采用優(yōu)化的人工蜂群算法改進K-means的k值選取方法，避免隨機選取和經(jīng)驗選取的不準確性，從而達到快速迭代的效果。

圖5 檢測響應時間變化曲線

圖6、圖7展示了K-means算法、傳統(tǒng)人工蜂群優(yōu)化K-means算法以及改進人工蜂群優(yōu)化K-means算法檢測率與誤報率的變化曲線。

圖6 檢測率變化曲線

圖7 誤檢率變化曲線

實驗結果分析：表5中K-means算法、傳統(tǒng)人工蜂群優(yōu)化K-means算法以及改進人工蜂群優(yōu)化K-means算法，根據(jù)k值的選取不同，分別得到相應的檢測率和誤報率。比較實驗結果以及圖6、圖7的變化曲線可以看出，改進的人工蜂群優(yōu)化K-means算法在檢測率上較其他兩種算法提高5%以上，誤檢率降低至4.5%。

3 結束語

針對SD-WSN網(wǎng)絡環(huán)境下，傳統(tǒng)K-means入侵檢測模型檢測率低、檢測速度慢等問題，提出了一種基于改進的人工蜂群優(yōu)化K-means檢測模型。該模型首先通過優(yōu)化適應度函數(shù)的方法改進傳統(tǒng)人工蜂群算法，加快算法的迭代速度，實現(xiàn)快速尋優(yōu)。通過改進的人工蜂群算法優(yōu)化K-means算法，實現(xiàn)K-means算法初始聚類中心的優(yōu)化選擇，消除了傳統(tǒng)K-means算法初始聚類中心隨機選擇的弊端，提高了入侵檢測中各種攻擊類別的聚類效果，并加快了異常檢測速度。仿真結果表明，改進的人工蜂群算法優(yōu)化K-means入侵檢測模型較傳統(tǒng)入侵檢測模型的檢測率提高5%以上，誤檢率降低至4.5%。