改進的遺傳算法在入侵檢測中的應用

魏德志林麗娜吳旭

（集美大學 誠毅學院，福建 廈門 361021）

0 引 言

計算機網絡安全、信息安全已經成為一個國際性的問題，每年全球因計算機網絡的安全問題而造成的經濟損失高達 數百億美元，而且這個數字每年都在增加。檢測與防范入侵攻擊，保障計算機系統、網絡系統及整個信息基礎設施的安全已經成為刻不容緩的重要課題。

近幾年來入侵檢測技術得到了飛速的發展，不斷有新的方法和技術出現，主要的創新包括：Forrest等將免疫原理運用到分布式入侵檢測領域[1]；Supeled將基因算法作為檢測方法而設計得GASSATA系統[2]；Wenke Lee將數據挖掘的技術用到入侵檢測中[3][4]。

受以上研究得啟發，本文先采用改進的遺傳算法，把關聯規則應用在遺傳算法的適應度函數的設計上。經過試驗比較最終得出了混合算法具有較好檢測效果的結論。

1.進的遺傳算法的入侵檢測模型

遺傳算法利用了生物進化和遺傳的思想，將它應用于入侵檢測規則發現中與傳統方法具有不同的特征：首先，它的處理對象是問題參數的編碼集，而不是參數本身；其次，遺傳算法在搜索空間中同時對很多點進行求解，這樣就減小了收斂于局部最小的可能，增強了魯棒性，同時也增加了處理的并行性。我們把關聯規則引入遺傳算法，可以實現入侵檢測系統的進一步優化。在遺傳算法中，通過適應度函數來確定個體的性質，而關聯規則則是通過支持度、可信度和興趣度來確定事物之間的關系，為此，我們可以把支持度、可信度和興趣度用于遺傳算法的適應度函數的構造，以實現兩種算法的結合，達到共同尋求最優解的目的。

1.1.進遺傳算法的概述

基于主機的入侵檢測系統和基于網絡的入侵檢測系統各有優缺點，本文的入侵檢測算法主要是用于基于主機的入侵檢測系統。

一般的入侵檢測模型主要包含四個個模塊：事件產生器、事件分析器、事件數據庫和響應單元。其中事件分析器利用主機的審計數據，產生一組用于檢測的規則：在入侵檢測階段，則是利用這些規則來實時檢測系統，規則產生后檢測是簡單和低開銷的。因此入侵檢測模型最主要的工作是如何生成有效的的規則庫。

1.2.進遺傳算法的染色體編碼的設計

網絡的行為都可以通過一些特征來表示，例如：源地址、目的地址、源端口號、目的端口號、協議類型以及連接時間長度等等，這些都可以表現網絡行為和網絡所能提供的服務等等。每一條入侵檢測規則是一個“if-then”的形式，其中包含條件和結果，網絡特征屬性用邏輯符號“AND”連接，構成規則的條件部分，特征IsAttack是作為結果的，表示是否為攻擊，下面顯示了一個規則的形式，其中的字符串只是為了顯示意義，在實際應用中將用例值代替。

If (Duration= "ANY" and Protocol_ype= "TCP" and Service=“telnet” and Flag= "ANY" and

Logged_in=false and Count=0 and Hot=” ANY” and Num_root=” ANY” Num_access_files=” ANY” Svr Count=0 and Serror rate="ANY”) then (IsAttack=“buffer_ overflow”)

上面的規則表示:如果協議類型為TCP并且服務類型為Telnet并且沒有成功登陸并且在2秒內登陸同一主機的連接數和在2秒內對同一服務的連接數均為0，則該連接可能為緩沖區溢出攻擊。以上僅僅是一個示例，并非真正的規則，真正的規則將在訓練后系統自動給出。

為了使規則更有通用性，我們允許在網絡特征表示中使用通配符，我們將通配符設置為#。則上面的例子用染色體向量表示為：{#, 1, 12,#, 0, 0, ,#, ,#, ,#,0, #, 12}

本文采用二進制編碼來表示關聯規則假定所有的特征屬性和類別屬性的取值是離散的(對于連續型的值先做離散化處理)并且取值范圍已知，對每個屬性的每一個取值用一個合適長度的二進制串來表示，每個二進制串代表一個基因，將所有屬性值的二進制串連接在一起得到一個二進制串作為一個染色體，代表一個關聯規則。

1.3.進遺傳算法的適應度函數的設計

關聯規則挖掘的任務就是要發現能夠反映記錄屬性之間的關聯或者是關系，這些規則應該具有一定的支持度、可信度和興趣度。我們從支持度、可信度、興趣度三個方面來綜合評價一條規則的“好壞”，在進化的過程中，讓越“好”的規則獲得越高的適應度值，使其在選擇競爭中獲得更大的生存和交叉的機會。為了定義規則的適應度，我們采用支持度、可信度、興趣度適應度函數，如果一條規則表示為：if X then Y，那么規則的適應度函數定義為：

S=support( X ? Y )= P (X∪ Y )=|X and Y |/N

C=confidence( X ? Y )=P ( Y/X)=|X and Y |/|X|

I=interest( X ? Y )=log( P ( Y/X)/ P (YnotX))

定義適應度函數為：Fitness= a *S+ b* C+c* I

其中N是訓練數據的總數，|X|代表訓練數據中滿足條件X的數據的數量，|X and Y |代表形如if X then Y的規則中滿足條件X和結果Y的數據的數量。a，b，c是用來平衡三項的權值，其中：a,b,c為常數且0≤a,b, c≤1；S為規則支持度；C為規則的可信度； I為規則的興趣度。a，b，c的值由用戶根據需要調整，從而對規則評價的偏重方面可以發生變化，使進化沿著用戶期望的方向進行。缺省值為：a=0.2，b=0.6，c=0.2。

1.4.進遺傳算法的遺傳操作的設計

遺傳操作[5]主要包括選擇、交叉和變異。

本文選擇采用錦標賽選擇算法，其基本思想是每次選取幾個個體之中最高的一個個體遺傳到下一代群體。由于本文的檢測器采用二進制編碼形式，因此交叉操作采用二進制均勻交叉的方式，其基本思想是對兩個配對的個體的每一個基因位上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體。變異方式有實值變異和二進制變異兩種，本文采用二進制變異方式，隨機選取個體的某個基因位進行翻轉。

1.5.進遺傳算法的描述

首先利用數據挖掘屬性相關分析獲取信息量較大的特征屬性，根據這些特征屬性生成初始的種群，設置缺省參數，然后讀入主機的訓練數據。初始的種群需要經過若干代的進化，在每一代的進化過程中，首先計算每一個規則的適應度函數，根據適應度函數的大小來選擇最適合的規則，而最終的GA的操作如變異、交叉等就施加于該選擇的種群上以生成下一代的種群。

下面顯示了混合算法的偽代碼：

算法：利用混合算法生成檢測規則

輸入：網絡的審計數據，本文采用Kddcup 99的訓練數據

輸出：一組檢測規則

1.輸入檢測數據

2.隨機初試化初試種群；

3.a=0.2；b=0.6；c=0.2；t=0.5；

4.N=訓練數據集的記錄數；

5.For種群中的每一個染色體{

6. X=0；XY=0

7. For訓練數據集合中的每一個數據記錄{

8. If當前的數據記錄匹配當前染色體{

9. XY++；

10. }

11. If當前的數據記錄只匹配條件{

12. X++；

13. }

14.Fitness=a*XY/N+b*XY/X+c*log( P ( Y/X)/ P (YnotX))；

15.IfFitness>T{

16.選擇該染色體進入下一代的種群；

17. }

18.For 在新種群中的每一個染色體{

19. 應用遺傳算法中的交叉獲得新染色體加入該種群；

20. 應用遺傳算法中的變異獲得新染色體加入該種群；

21. }

22.如果進化代數還未到，goto 5；

23.結束。

1.6.進入侵檢測算法的實現

本文的入侵檢測系統是基于主機的，開發工具采用Microsoft Visual Studio.NET2005，開發語言主要有J#。訓練數據和測試數據均采用了KDDCUP99的數據。入侵檢測系統的實現是建立在第三方的軟件開發包 ECJ[6]之上的。ECJ是由喬治梅森大學George Manson大學的ECLab開發和維護的完整的GA/GP的Java開發包，這個開發包提供了豐富的一組GA基礎類庫。我們通過調用ECJ的類庫，實現了兩個功能：1)離線的數據訓練系統，利用歷史數據(KDDCUP99)來推導出判斷規則；2)利用推導出的規則在線實時檢測網絡系統中可能存在的攻擊。

2.驗及結果分析

本文的硬件實驗環境為：Dell服務器PowerEdge 840，至強雙核處理器 1.86G，4G內存；軟件環境為：操作系統Windows Advance Server 2000，數據庫SQL2005，開發工具Microsoft Visual Studio.NET2005。實驗采用10%的訓練數據來進行規則推導，改進算法的適應度函數我們用前面使用的支持度、可信度、興趣度適應度函數，染色體采用經過屬性選擇完的編碼，改進算法的參數a=0.2，b=0.6，c=0.2，一共訓練迭代3000次，初始的染色體種群數量為500個，交叉的概率取值為0. 5，變異的概率取值為0. 02，訓練結束時頭20條質量最好的規則作為最終的檢測規則，這些規則用來檢測訓練數據。同時進行遺傳算法和關聯算法試驗，進行對比。具體試驗結果見圖。

三種算法檢測效果圖

從圖標中我們可以看出改進算法在三種算法當中，它的檢測率最高，誤報率最低，但建規則庫所需要的時間也最長。

3.束語

入侵檢測目前最大的困難就是數據量大，用戶的行為特征的準確描述比較困難。通過前面的試驗分析討論，改進遺傳算法在入侵檢測上具有較好的效果，但還有一些缺點，在建規則庫所需要的時間也最長，這個是將來要改進的地方，進一步提高算法的運行速度。

[1]Forrest S,Hofmeyr S,Somayaji A.A sense of self for unix processes[A].In Proceedings of the 1996 IEEE symposium on Security and Privacy,Los Alamitos,CA 1996 IEEE Computer Society Press: 120-128.

[2]Me L.Genetic Algorithms,a biologically inspired approach for security audit trails analysis[J].short paper,presented at the 1996 IEEE Symposium on Security and Privacy,Oakland,CA, 1996.

[3]Lee W Stolfo S.Mining in a data-flow environment:Experienceinnetworkintrusiondetection[A].In:Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery&Data Mining(KDD-99)[C].1999:186-192.

[4]Lee W Stolfo S.Mining audit data to build intrusion detection models[A].In:Proceedings of the 4th International ConferenceonKnowledgeDiscoveryandData Mining[C].New York,NY,AAAI Press,1998.

[5]ECLab : Computation Fairfax, VA, 2004. evolutionary Computation laboratory,A Java-based Evolutionary(ECJ)and Genetic Programming Research System,George Mason University,USA,http://cs.gmu.edu/eclab/projects/ecj/(access ed in November 2007).

[6]王小明,曹立明.遺傳算法——理論、應用與軟件實現[M].

西安:西安交通大學出版社,2002.