基于遺傳算法的入侵檢測系統研究

摘要：隨著科技進步和計算機網絡技術的飛速發展，網絡“黑客”的攻擊手段越來越先進，信息安全問題也越來越突出。本文討論了應用自適應遺傳算法到網絡入侵檢測系統，包括入侵檢測系統、遺傳算法的簡單介紹和相關的檢測技術，詳細論述了遺傳算法在入侵檢測系統中應用的具體過程，特別是染色體的構造以及交叉和突變兩類算子的應用。通過研究我們發現將遺傳算法應用于入侵檢測有著廣闊的前景。

關鍵詞：遺傳算法 入侵檢測系統

一、引言

入侵檢測系統（IDS）就是對網絡或操作系統上的可疑行為做出策略反應，及時切斷資料入侵源、記錄、并通過各種途徑通知網絡管理員，最大幅度地保障系統安全，是防火墻的合理補充，幫助系統對付網絡攻擊，擴展系統管理員的安全管理能力（包括安全審計、監視、進攻識別和響應），提高信息安全基礎結構的完整性，被認為是防火墻之后的第二道安全閘門。遺傳算法已經采用了不同的方法應用到入侵檢測系統中，使其具有智能性，這些研究還處于研究階段。有人使用不同的機器學習技術，如限定狀態機器、決策樹和遺傳算法來為入侵檢測系統產生人工智能規則。

二、遺傳算法

遺傳算法（GA）是自適應啟發性的搜索算法，以自然界選擇和基因的進化思想為先決條件。GA的基本概念是設計模擬自然界進化的過程，特別是由達爾文的適者生存原則。我們通常采用的遺傳算法的工作流程的結構形式是Goldberg在天然氣管道控制優化應用中首先提出的，一般稱為規范遺傳算法（Canonical GA，CGA）或者標準遺傳算法（Standard GA，SGA）。規范遺傳算法的基本流程圖如下：

遺傳算法所涉及到的五大要素：參數編碼、初始群體的設定、適應度函數的設計、遺傳操作的設計和控制參數的設定。

遺傳算法的運行過程為一個典型的迭代過程，它必須完成的工作內容和基本步驟如下：

1）選擇編碼策略，把參數集合X和域轉換為位串結構空間S；

2）定義適應度函數F(x);

3）確定遺傳策略，包括選擇群體大小n，選擇、交叉、變異方法，以及確定交叉概率、變異概率等遺傳參數；

4）隨機初始化生成群體；

5）計算群體中個體位串解碼后的適應值 F(x)；

6）按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體；

7）判斷群體性能是否滿足某一目標，或者已完成預定迭代次數，不滿足則返回

步驟 6），或者修改遺傳策略再返回步驟 6）。

三、遺傳算法在入侵檢測系統中的應用

（一）概述

遺傳算法可以用來產生入侵檢測系統的規則，這些規則是根據已知的網絡連接構成的數據庫來自動產生的。產生的規則用來區分正常的網絡連接和異常的網絡連接。異常的網絡連接就是指可能的入侵活動。存儲在規則庫中的規則一般是以下形式：

if{condition}

then{act}

這里的條件通常是指當前網絡連接和IDS中的規則是否匹配，比如源IP地址、目的IP地址、端口號等等。動作通常是指安全策略定義的對異常的反應，比如給系統管理員報警、將可能的入侵存入日志等等。

應用遺產算法的最終目的就是產生只匹配異常連接的規則。這些規則在歷史網絡連接上測試，并且應用在過濾新的網絡連接上檢測可能的入侵攻擊。

在本文中所述實現中，歷史數據是一個預先分好類的數據庫，由正常的網絡連接和異常的網絡連接組成。這些數據可由網絡嗅探器搜集，比如Tcpdump或者Snort等。搜集到的數據由標準的聚類算法進行智能分類，這個分類的數據庫用來在遺傳算法的運行過程中給確定染色體的適應度提供依據。這樣，通過遺傳算法，一個小的隨機產生的規則集就會生成一個大的包含很多規則的集合給IDS使用。這些規則就是遺傳算法的足夠好的解，這些規則可以用來過濾新的網絡連接。

（二）編碼方案

為了準確發現入侵，我們應該對一個特定網絡連接的所有部分進行檢查。但通常為了簡單起見，我們僅考慮每一個連接的一些明顯屬性。對于一個網絡連接（TCP/IP協議類型）我們通常考慮下表的域。

if

{

一個網絡連接有如下特征：

源IP地址d2.0f.**.**；

目標IP地址c0.a8.a*.**；

源端口號43226；

目標口號80；

持續時間482秒；

終止狀態（連接由發起連接的人終止）11；

使用協議（TCP協議）2；

發送方發送了7341個字節；

接受方接受了37761個字節；

}

then

{

終止該連接；

}

可以將上面的例子轉換為染色體編碼的形式：

該染色體是一57維向量，共有57個基因，為了簡單，我們用十六進制來表示IP地址。

這條規則的實際有效性可以通過匹配由正常連接和異常連接組成的數據集來驗證。如果這條規則匹配了一個正常連接，該染色體就會得到一個處罰。很顯然沒有一個單一的規則就能夠從正常連接中區分出所有的異常連接。種群需要不斷的進化來發現理想的規則集。

表3-1所示的例子中使用了符號*，并且在染色體中的相應基因被顯示為-1.這些符號被用于表示值的一定范圍，它表示IP地址和端口號的一定范圍時有用。一旦空間信息被包含在規則中，IDS的能力就會大大提升，因為一個攻擊可以從許多不同的地方發起。把持續時間包含進染色體保證了時間信息與網絡連接的結合。網絡連接時間的最大值是9999999秒，這個值是一百多天。這對確定入侵非常有用，因為復雜的入侵可以跨越小時、天、甚至月。

（三）適應度函數的建立

對于遺傳算法的應用，定義一個問題的解的適應度是最難的一個問題。在定義一個染色體的適應度之前，我們先來定義兩個染色體對應的網絡連接的匹配問題，也就是如何定義匹配。

（1）

用上式定義兩個網絡連接之間的匹配值。另外定義一個值match_threshold，當Outecome＞math_threshold時，就認為兩個網絡連接是匹配的。式中，Matched的取值為0或1，當對應匹配時取值為1，不匹配時取值為0。weight是不同域的權重。這樣計算出的Outcome值的個數與數據集中染色體的個數相同，取其中最大的一個作為被考察連接的Outcome值。

公式中權值的順序如下圖所示：

這個順序后面的基本思想是TCP/IP包中不同域的重要性不同。這種安排簡單直接。目標IP地址是攻擊的目標而源IP地址是攻擊的發源地，這些是為了捕捉一個入侵最重要的信息。目標端口號顯示了目標系統正在運行的程序（例如FTP服務通常運行于21號端口）。一些IP地址被攻擊的可能性更大——例如軍事領域的IP。其它的參數例如持續時間、發起者發送的字節數、接收者發送的字節數等的重要性通常低一些，但仍然比較有用。協議和源端口號通常不是必要的，一般用于確定一些特定的攻擊。

本文中這樣定義適應度值：

染色體對應的規則匹配的異常網絡連接越多，染色體的適應度越大；

染色體對應的規則匹配的正常網絡連接越多，染色體的適應度越小。

更準確的說，假設已知的分類的網絡連接集合中有m個正常的網絡連接，有n個異常的網絡連接。令

(2)

其中Outcomei＞match_threshold，Ranking表示一條異常連接識別的難度。如果是較難識別的異常連接，Ranking值較大；反之，Ranking值較小。令

（3）

其中Outcomei＞match_threshold，其中的Ranking表示一條異常連接識別的難度。如果是較難識別的異常連接，Ranking值較小；反之，Ranking值較大。

用F表示一個染色體的適應度值，

F=Anomalouss-Normal (4)

這樣適應度高的染色體被加入到特征庫中，從而實現了特征庫的智能動態更新。

（四）交叉算子的應用

通過交叉操作可以在父代的基礎上產生子代，然后在父代與子代組成的種群中根據適應度函數的大小選出下一代個體。在本文中采用了單點交叉，交叉點確定在目標IP地址的后面，即染色體中的第16位后。這樣做的根據是：即使源IP地址與目標IP地址都變了，如果攻擊手段相同，那么染色體后面的部分應該是類似的。所以用這種交叉方式有很大機率產生出適應度比較高的新染色體。具體實現方法如下：

設進行交叉操作的概率為Pm，那么種群中每次約有N·Pm個染色體進行交叉操作，其中N為種群大小。可以用下面的方法來確定交叉操作的父代：

for(int i=1;i＜=N;i++)

{

r=random();

if(r＜Pm)// r得到一個（0，1）之間的隨機數

將Vi加入交叉操作的父代中；//Vi表示種群中的第i個染色體

}

對選擇出的父代兩兩配對進行交叉操作，例如將Vi，Vj交叉后產生新染色體X，Y的方法為：

則

X=P1·Vi+P2·Vj （5）

Y=P1·Vj+P2·Vi （6）

（五）突變算子的應用

突變算子通常一次只改變一個染色體上的一個基因，一般認為，突變算子的重要性次于交換算子，但起作用不容忽視，通過突變可以產生僅通過選擇和交叉無法產生的最優解。在本系統中突變操作是如下進行的：

設發生突變的概率為Pn，這個概率表明種群中每次約有N·Pn個染色體進行突變操作。首先要產生出進行突變操作的父代，產生方法類似交叉操作。用V表示要進行突變操作的任一父代染色體，可以用下面方法產生突變后的新染色體X：

X=V+M·d （7）

式中d為與染色體同維數的向量，它表示隨機產生的變異方向，形式為d=（0，0，……，0，1，0，……，0）。d中1所在的位置就是染色體V中要發生突變的位置。M為一個[0，F]之間的隨機數，如果這樣得出的X不符合表中取值范圍的要求，可以將M置為[0，M]之間的一個隨機數，然后繼續用公式（7）計算，直到得出符合要求的X為止。最后用變異產生的染色體X代替原種群中的染色體V。

在遺傳算法中還有其它一些需要考慮的參數，如種群大小、交叉率、突變率、進化代數等。這些參數可以根據系統的規模大小和機構的安全策略進行調整。

四、結論

我們發現自適應遺傳算法收斂的非常快。因為時間在實時過程中是個非常重要的因素，和一系列的規則引導適應度函數，在我們事件中，收斂速度快是我們需要的。這結果顯示自適應遺傳算法已經發現了一種好的解決方法，所以對入侵檢測來說，它能夠作為一個優秀的數據分析器出色地工作。

自適應遺傳算法要達到入侵檢測的目的則需要更多更深入的測試。在遺傳算法中，參數的詳細信息該通過試驗決定。通過使用自適應遺傳算法為基礎的數據分析器，我們能夠發展為其他各種攻擊使用該分析器。先進的系統將實行實時監控、分析和對入侵行為產生合適的反應。

[參考文獻]

[1] J P Anderson.Computer Security Threat Monitoring and Surveillance.[R] James P.Anderson Co.，Fort Washington，1980.

[2] Dass M.， J.Cannady and W.D.Potter to appear in the digital proceedings of the 41st ACM Sowtheast Conference， Savannah， March 7-8，2003.

[3] Wei Li， Using Genetic Algorithm for Network Intrusion Detection[J]. Proceedings of the United States Department of Energy Cyber Security Group 2004.

[4] 任慶生，葉中行等. 遺傳算法中常用算子的分析[J]. 電子學報. 2000;5:113~114.

[5] B.D. Davison， H. Hirsh ， Experiment in UNIX command prediction[C]， Proceedings of the 14th National Conference on Artificial Intelligence， Rhodes Island， USA， April 1999.

[6]戴英俠，連一峰等編著.系統安全與入侵檢測.清華大學出版社.2002，P6-9，P15.P24-25.

[7] S. E. Smaha. Haystack: An Intrusion Detection Systerm. Orlando ed .In Proceedings of the IEEE Fourth Aerospace Computer Security Applications Conference， Washington: IEEE Computer Society Press， December 1988: P37-44.

[8]李德全.馮登國著.AHost-BasedAnomaly Intrusion Detection Model Based On Genetic Programming， 軟件學報，2003.14 P1120-1124.

[9]陳云芳.王汝傳等著.基于用戶行為分析的入侵檢測應用模型的研究.微機發展.2004，12：P122－124.

[10] 徐小龍，王文國. 縱論新一代入侵檢測系統[J]. 科技信息. 2005; 2:14~15.