周麗娟，于雪晶，魏 卓

基于螢火蟲群算法的網絡入侵優(yōu)化檢測算法

周麗娟1，于雪晶1，魏 卓2

（1.長春工業(yè)大學信息傳播工程學院，長春130012；2.長春工程學院計算機技術與工程學院，長春130012）

針對模糊C-均值聚類法因對初始聚類中心敏感且容易陷入局部極小值而導致無法在網絡入侵檢測中獲得精確分類結果的問題，提出了基于螢火蟲群優(yōu)化（GSO：Glowworm Swarm Optimization）算法的網絡入侵檢測方法。采用標記樣本得到初始聚類中心，運用螢火蟲群優(yōu)化實現對聚類中心的優(yōu)化。結果顯示該方法有效。

螢火蟲群優(yōu)化算法；網絡入侵；模糊C-均值聚類；半監(jiān)督

0 引言

隨著網絡技術的高速發(fā)展，網絡規(guī)模不斷擴大、功能日趨強大，其用戶數量持續(xù)增加，為人們的生活帶來極大便利，但同時也為各類網絡入侵制造了越來越多的漏洞，為網絡安全帶來了極大的挑戰(zhàn)?？焖侔l(fā)現各類入侵行為、確保網絡安全已成為各國學者討論的熱點問題。

網絡入侵檢測技術可分為誤用檢測和異常檢測技術。誤用檢測技術是用來訓練一個帶有標記樣本的分類器，然后運用受過良好訓練的分類器識別網絡入侵，此種算法存在的問題在于訓練的可獲得性以及學習過程需要預先識別大量的標記樣本。異常檢測技術是一種不需要大量標記樣本且能實現攻擊類型自動分類的算法［1-3］。

通常，機器學習算法可分為監(jiān)督學習算法、無監(jiān)督學習算法和半監(jiān)督學習算法。根據監(jiān)督學習的設計原理，假定存在一些數據輸入和相關輸出，機器在此過程中學習一種映射函數，以使其具備預測新數據樣本輸出的功能。在非監(jiān)督學習過程中僅有一些數據輸入，但不存在任何來自監(jiān)督信息的引導，此過程旨在設計一些算法，以便開發(fā)隱藏在數據之中的各類屬性。半監(jiān)督算法是近年來問世的一種新的聚類算法，是近年來機器學習與模式識別領域的一個重要研究方向。該算法結合了無監(jiān)督學習和監(jiān)督學習的優(yōu)勢，實現了聚類質量的提升?；诒O(jiān)督學習的異常檢測算法需要大量帶有標記數據的類別信息，人們需要付出巨大的努力才能獲得此類數據，因此，其應用相對受限。然而，基于無監(jiān)督學習的異常檢測算法根據數據的相似性對其進行分組，能克服監(jiān)督學習在標記樣本數據不足的缺陷。但是，該算法的檢測精度明顯次于監(jiān)督檢測。在實際應用過程中，半監(jiān)督聚類僅需獲得少量的標記樣本數據，因此，其優(yōu)越性十分明顯。

筆者提出了一種基于螢火蟲算法的原創(chuàng)半監(jiān)督模糊C-均值入侵檢測優(yōu)化算法。模糊C-均值聚類算法旨在將樣本映射到運用FCM算法進行聚類分析的特征空間。該方法能在一定程度上去除噪聲敏感性和雜亂數據并確保分布在不同形狀之中的數據的準確聚類，且不依賴數據內在形狀分布并能提高算法魯棒性。但是，FCM的聚類性能依賴于對初始聚類中心的選擇且傾向于局部最優(yōu)。因此，筆者采用經過螢火蟲算法優(yōu)化的FCM算法聚類中心。運用少量標記樣本進行監(jiān)督聚類，以便獲得初始聚類中心。同時運用經過螢火蟲算法優(yōu)化的模糊C-均值聚類算法對未標記樣本進行分類，在此過程中采用初始聚類中心作為聚類中心。

1 螢火蟲算法概述

1.1 螢火蟲算法的原理

自然界中存在大約2 000多種螢火蟲，其中，大多數種類的螢火蟲均能出于不同的目的發(fā)出短暫的熒光，但它們發(fā)光的原因目前還沒有研究清楚。人們基本認同成年螢火蟲發(fā)光的生物學功能是通過自身發(fā)出的獨特熒光信號尋找和吸引異性，從而實現交配和繁殖。此外，也有一些種類的螢火蟲利用熒光捕食。熒光的另一個作用是作為警告信號，即螢火蟲可在遭遇危險時發(fā)出熒光。螢火蟲群優(yōu)化算法是一種基于模擬螢火蟲在自然界中發(fā)光過程的隨機優(yōu)化算法。該算法不考慮螢火蟲發(fā)光的生物學功能，而僅考慮其在運用熒光尋找配偶、向處于附近最佳位置的螢火蟲移動過程中發(fā)出熒光的特點。

螢火蟲群優(yōu)化（GSO：Glowworm Swarm Optimization）算法模擬了螢火蟲在自然界中的求偶儀式并憑借其高搜索速度和搜索效率而得到廣泛關注。目前，該算法已被證明在最優(yōu)化問題領域（如路徑規(guī)劃、最優(yōu)化問題等）具有良好的應用效果。

根據螢火蟲算法，在目標函數的解空間內對一個螢火蟲群進行隨機初始化，且該螢火蟲群中的每只螢火蟲均有一定數量的熒光素，其數值取決于螢火蟲所處的位置。螢火蟲所處的位置越好，該位置對應的適合度值越高，熒光素閾值越大。同時，熒光素閾值決定了螢火蟲發(fā)出熒光的強度。熒光的強度越高，螢火蟲對周圍同類的吸引力越強。某只螢火蟲對其他螢火蟲的吸引力稱為決策方位或領地范圍（用rd表示）。只有在i號螢火蟲進入j號螢火蟲的領地范圍內的情況下，j號螢火蟲才對i號螢火蟲具有吸引力。由于相互吸引，螢火蟲會為了實現最優(yōu)化而奔向相對優(yōu)于其他螢火蟲的那只［4-6］。

可通過兩個步驟實現螢火蟲算法：熒光素更新和螢火蟲的追隨運動。

當某只螢火蟲需要更新其熒光素時，可通過一種持續(xù)的方式實現此類更新。熒光素更新公式為

其中ρ和γ為熒光素控制參數，其區(qū)間值在［0，1］之間；l為螢火蟲的熒光素閾值；f（xi（t））為每只螢火蟲的適合度閾值。

i號螢火蟲在一定的概率下會追隨j號螢火蟲移動可表示為

在i號螢火蟲追隨j號螢火蟲的過程中，i號螢火蟲的位置隨時發(fā)生變化。位置更新公式如下

其中xi（t）為i號螢火蟲的位置，s為螢火蟲的更新后步長。

1.2 算法改進

為加強算法的優(yōu)化能力，筆者對螢火蟲的交配行為進行模擬，以實現對基本GSO的改進。人們通過觀察得知，在交配時節(jié)，一只雌性螢火蟲周圍會存在數只雄性螢火蟲等待交配，而雌性螢火蟲會選擇亮度最高、發(fā)光時間最長的螢火蟲。假設具有最多熒光素的那只螢火蟲為雌性、等待與一只雌性螢火蟲交配的雄性螢火蟲的數量為m、一只雌性螢火蟲會與m只雄性螢火蟲交配，則可對螢火蟲的交配過程進行模擬。螢火蟲交配算法與遺傳算法的交叉算法類似公式如下

其中xi為雌性螢火蟲；xj為雄性螢火蟲；α取值在［0，1］之間。

如果一只雌性螢火蟲與m只雄性螢火蟲交配，有m只雄性螢火蟲已經與一只雌性螢火蟲交配，則只有最佳的一只螢火蟲可以得到保留，其他螢火蟲則被拋棄。

1.3 混沌初始化

混沌是在自然界大多數非線性系統(tǒng)中常見的一種非線性現象?；煦绗F象是在完全確定的系統(tǒng)（不存在任何額外的隨機因素）中表現的一種介于規(guī)則與隨機之間的類隨機行為?；煦绗F象具有獨特的性質。

1）隨機性。

2）遍歷性。其可在一定的范圍內根據自身規(guī)律以不重復的方式經歷所有的狀態(tài)。

3）規(guī)則性。毫無疑問，運用混沌變量進行最優(yōu)搜索是一種較優(yōu)的方法。正是遍歷性使其免于在搜索過程中限于局部最優(yōu)并使其成為一種提升全局收斂能力的機制。

混沌搜索通常采用邏輯函數

其中μ為控制參數。當μ=4時，0≤z0≤1，邏輯完全處于混沌狀態(tài)下。

1.4 螢火蟲算法流程

綜上所述，螢火蟲算法的流程如下。

第1步：算法參數初始化。

第2步：根據式（5）對螢火蟲位置進行混沌初始化、計算螢火蟲的目標函數值并以此作為螢火蟲各自的熒光亮度l。

第3步：根據式（1）計算螢火蟲的追隨概率。

第4步：通過式（3）更新螢火蟲的空間位置并對處于最佳位置的螢火蟲實施隨機擾動。

第5步：根據螢火蟲的更新位置重新計算螢火蟲的熒光亮度。

第6步：如果搜索精度能滿足要求或已達到最大搜索次數，則進行第7步，否則，搜索次數加1并回到第3步進行再次搜索。

第7步：輸出全局極值和最優(yōu)值。

2 模糊C-均值聚類

2.1 算法原理

模糊聚類算法是一種基于函數最優(yōu)法、通過微積分計算技術求得最優(yōu)代價函數的算法。當概率密度函數用于基于概率算法的聚類方法中時，假設存在一個適當的模型且模糊聚類算法的矢量同時屬于多個群集，則上述問題即可獲得解決。模糊聚類算法需要在矢量與群集之間定義一個近鄰函數，且各群集中矢量的隸屬關系是由隸屬度函數集賦予的。從模糊法的角度而言，不同群集中矢量的隸屬度函數值存在關聯。硬聚類可被視為模糊聚類方法中的一個特例。

假設樣本集為X=｛x1，x2，…，xn｝。模糊C-均值聚類算法將該樣本集分為c個模糊群并計算各模糊群的聚類中心cj（j=1，2，…，C），以實現對算法目標函數的最小化

其中 JC是基于樣本 C的代價函數，uij是指 i號數據點對 j號聚類中心的隸屬度；cj是指j號模糊聚類中心，其初始值是從訓練樣本集中隨機選出的；α代表模糊性。模糊隸屬度與α成正比例關系。計算模糊隸屬度uij和聚類中心cj公式如下

n n

FCM聚類過程從一個隨機聚類中心開始，并通過搜索目標函數的極小點不斷調整聚類中心和每個樣本的模糊隸屬度，以實現樣本分類的最終目標。

2.2 算法改進

在FCM算法中，由于隸屬度uij需要歸一化，因此，在不良樣本集基礎上得到的結果很可能并不理想。如果樣本點遠離各個聚類中心，則其對各群集的隸屬度很小。但由于歸一化的要求，樣本點對各群集的隸屬度需要提高，進而導致不理想的迭代結果。為了放寬歸一化條件，令每個樣本對各群集的隸屬度之和為n，如下所示

在新隸屬度函數的條件下，隸屬度函數

式（10）顯然并非一般意義上的隸屬度函數，且其區(qū)間并非限于小于1的范圍內。如必要，可根據公式

最終獲得隸屬度函數。

憑借經過改進的隸屬度，FCM算法即使在存在孤立點的情況下仍然能實現良好的聚類效果。而且，由于歸一化條件的放寬，最終的聚類結果對預定義的聚類數并不十分敏感。

3 基于螢火蟲算法的入侵檢測

3.1 對螢火蟲進行編碼

所有聚類中心均包含在每只螢火蟲的編碼中。假設存在K個聚類中心、每個聚類中心的維數為S、每只螢火蟲均是維度K×S中的一部分，表示如下

其中cpk為p號螢火蟲的k號聚類中心。

3.2 適合度值

每只螢火蟲對應一個適合度值，即FCM算法的目標函數。

3.3 算法流程

筆者采用了基于螢火蟲優(yōu)化的半監(jiān)督聚類算法。算法輸入數據包含n個標記數據集和m個未標記數據集，且n?m。

算法包含兩個程序：1）在監(jiān)督下使用少量標記樣本進行聚類，以便得到初始聚類中心；2）通過螢火蟲算法對聚類中心進行優(yōu)化。該程序包括下列步驟：

①根據在程序1）中得到的聚類中心Ok在數據集Cr中生成一個初始隸屬度矩陣，并在Ok周圍初始化一個螢火蟲群；

②對初始模糊C-均值聚類中心的每只螢火蟲進行模糊C-均值聚類，并根據最終聚類結果計算每只螢火蟲的適合度值；

③追隨螢火蟲的交配行為和螢火蟲群的更新；

④計算更新后的螢火蟲群的適合度值；

⑤判斷算法是否滿足最終要求。如果不滿足要求，則返回②。

4 仿真實驗

4.1 實驗數據

筆者采用KDD CUp99網絡攻擊數據集驗證螢火蟲算法的有效性。從數據集中抽取5種類型的數據，分別為Dos、U2R、probe、R2L攻擊模式和正常模式數據。實驗采用的數據集共有41種特性。由于其中一些數據為冗余數據，因此，僅選取21種能反映用戶行為的數據作為研究對象，如Duration（持續(xù)時間）、Service（服務）、protocol type（協(xié)議類型）和Flag（標記）等。

為了滿足檢測算法的假設條件，從全部檢測數據集中選取4組數據進行試驗，每組數據包含117 489條記錄。其中116 001條記錄為正常數據，1 488條為入侵數據。由于正常數據在每個實驗組中所占的比例為99%，因此，滿足檢測算法中的正常數據遠大于入侵數據的假定條件。

4.2 仿真實驗與分析

檢出率和誤報率可用于測試入侵算法的性能。檢出率是指被檢出的入侵檢測樣本數量在此類樣本總數中所占的比例，誤報率是指誤報為入侵樣本的正常樣本數量在正常樣本總數中所占的比例。在螢火蟲算法中，設群數參數為100，迭代數為250。4組數據的入侵檢測結果如表1和表2所示。

表1 檢出率測試結果Tab.1 The test results of DR

表2 誤報率測試結果Tab.2 The test result of FpR

測試結果表明，螢火蟲算法在最優(yōu)化方面表現良好，能有效提高FCM算法的聚類結果，因而能有效提升檢出率、降低誤報率。

5結 語

FCM算法易于使用且適用于聚類問題，但該算法容易陷入局部最優(yōu)，在聚類結果方面表現不佳。筆者提出了螢火蟲算法及其在網絡入侵方面的應用。通過基于螢火蟲算法和半監(jiān)督聚類的優(yōu)化，算法的聚類特性已經得到有效提升。仿真實驗表明，基于螢火蟲算法優(yōu)化的半監(jiān)督FCM算法可更好地應用于網絡入侵檢測，為解決網絡入侵問題提供了一種新的思路。

［1］龔儉，陸晟.大規(guī)模互聯網絡的入侵檢測［J］.東南大學學報：自然科學版，2002，32（3）：325-330. GONG Jian，LU Sheng.Intrusion Detection in Large-Scale Network［J］.Journal of Southeast University：Natural Science Edition，2002，32（3）：325-330.

［2］吳斌，崔志勇，倪衛(wèi)紅.具有混合群智能行為的螢火蟲群優(yōu)化算法研究［J］.計算機科學，2012（5）：198-200. WU Bin，CUIZhiyong，NIWeihong.Research on Glowworm Swarm Optimization with Hybird Swarm Intelligence Behavior［J］.Computer Science，2012（5）：198-200.

［3］胡亮，康健，趙闊，等.入侵檢測系統(tǒng)［J］.吉林大學學報：信息科學版，2002，20（4）：46-47.HU Liang，KANG Jian，ZHAO Kuo，et al.Intrusion Detection Systems［J］.Journal of Jilin University：Information Science Edition，2002，20（4）：46-47.

［4］陳丹瑜，許勇，吳國新.入侵檢測系統(tǒng)系統(tǒng)性能參數的仿真法分析［J］.計算機工程與應用，2004，40（7）：139-141. CHEN Danyu，XU Yong，WU Guoxin.Simulation performance Analysis of Intrusion Detection System［J］.Computer Engineering and Applications，2004，40（7）：139-141.

［5］王艷青，鄭永凡，王玉.入侵檢測系統(tǒng)評估仿真平臺的研究［J］.遼寧大學學報：自然科學版，2009，36（1）：49-51. WANG Yanqing，ZHENG Yongfan，WANG Yu.The Research of Simulation p latform for Testing Intrusion Detection System［J］.Journal of Liaoning University：Natural Science Edition，2009，36（1）：49-51.

［6］呂志軍，金毅，賴海光，等.DApRA測試分析和IDS測試方法研究［J］.計算機科學，2004，31（11）：73-76. LüZhijun，JIN Yi，LAIHaiguang，et al.Analysis of DARpA Testand Research of IDSTestMethod［J］.Computer Science，2004，31（11）：73-76.

（責任編輯：劉東亮）

Optimized Detection Algorithm for Network Intrusion Based on the Glowworm Swarm Algorithm

ZHOU Lijuan1，YU Xuejing1，WEIZhuo2

（1.College of Information Dissemination Engineering，Changchun University of Technology，Changchun 130012，China；2.School of Computer Technology and Engineering，Changchun Institute of Technology，Changchun 130012，China）

Because fuzzy C-means clusteringmethod is sensitive to initial cluster centers and easily trapped into localminima，we can't get precise classification result in network intrusion detection.To solve the problem，a network intrusion detectionmethod based on GSO（Glowworm Swarm Optimization）algorithm is proposed.First，sampleswith label is used to get initial cluster center.Then，GSO is employed to optimize cluster center. Simulation result shows that themethod is effective.

glowworm swarm optimization（GSO）algorithm；network intrusion；fuzzy C-means clustering；semi-supervised

Tp301

A

1671-5896（2015）03-0338-06

2015-04-02

周麗娟（1971— ），女，吉林白山人，長春工業(yè)大學副教授，主要從事軟件開發(fā)和人工智能研究，（Tel）86-13604304528（E-mail）wanglijun@ccut.edu.cn。