魏德志林麗娜吳旭

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

0 引 言

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

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

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

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

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

1.1.進遺傳算法的概述

基于主機的入侵檢測系統(tǒng)和基于網(wǎng)絡的入侵檢測系統(tǒng)各有優(yōu)缺點，本文的入侵檢測算法主要是用于基于主機的入侵檢測系統(tǒng)。

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

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

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

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”)

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

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

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

1.3.進遺傳算法的適應度函數(shù)的設計

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

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))

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

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

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

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

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

1.5.進遺傳算法的描述

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

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

算法：利用混合算法生成檢測規(guī)則

輸入：網(wǎng)絡的審計數(shù)據(jù)，本文采用Kddcup 99的訓練數(shù)據(jù)

輸出：一組檢測規(guī)則

1.輸入檢測數(shù)據(jù)

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

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

4.N=訓練數(shù)據(jù)集的記錄數(shù)；

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

6. X=0；XY=0

7. For訓練數(shù)據(jù)集合中的每一個數(shù)據(jù)記錄{

8. If當前的數(shù)據(jù)記錄匹配當前染色體{

9. XY++；

10. }

11. If當前的數(shù)據(jù)記錄只匹配條件{

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.如果進化代數(shù)還未到，goto 5；

23.結束。

1.6.進入侵檢測算法的實現(xiàn)

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

2.驗及結果分析

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

三種算法檢測效果圖

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

3.束語

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

[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]王小明,曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].

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