基于遺傳算法的入侵檢測技術的研究

摘要：在簡要介紹入侵檢測和遺傳算法的基礎上，給出了基于異常檢測的訓練算法模型。詳細介紹了遺傳算法的構造過程，包括染色體的構造以及選擇、交叉、變異等操作，并予以簡單實現。算法提高了入侵檢測的效率，并能檢測部分未知攻擊。

關鍵詞： 入侵檢測；遺傳算法；入侵訓練算法

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)36-2582-03

The Research of Intrusion Detection Technology Based on Genetic Algorithms

CHEN Zhong-min， XUAN Song-sheng

(College of Science，Huazhong Agricultural University，Wuhan 430070，China)

Abstract: Based on the brief introduction of intrusion detection and genetic algorithms， this paper gives the training algorithms model based on amomaly detection， and introduces specificly the constructing process of genetic algorithms， including the constructing， choosing， crossing and mutating of chromosome and realize them. The algorithms increase the efficiency of intrusion detection and it can check some unknown attack.

Key words: intrusion detection; genetic algorithms;intrusion training algorithms

1 引言

計算機網絡安全不僅對每個人都有現實意義，而且對一個國家的政治、經濟和國防安全也十分重要。隨著現有網絡環境的日益復雜以及攻擊者手段的日益高明，網絡安全面臨的威脅也越來越大。CNCERT/CC監測發現中國大陸被篡改網站的數量近年來增長迅猛。2007年，CNCERT/CC監測到中國大陸被篡改網站總數累積達61228個，比2006年增加了1.5倍。2003年至2007年中國大陸網頁被篡改情況年度統計如圖1所示。

入侵監測系統一般不是以采取預防的措施來防止入侵事件的發生，入侵檢測作為安全技術，其主要目的在于：第一，識別入侵者；第二，識別入侵行為；第三，檢測和監視已成功的安全突破；第四，為對抗入侵及時提供重要信息，阻止事件的發生和事態的擴大。從這個角度看安全問題，入侵檢測對于建立一個安全系統來說是非常必要的，它可彌補傳統安全措施的不足。[1]

2 入侵檢測技術和遺傳算法介紹

入侵檢測是對入侵行為的發現。它在計算機網絡或計算機系統中若干關鍵點收集信息，并對收集到的信息進行分析，判斷網絡或系統中是否有違反安全策略的行為和遭受攻擊的跡象。

入侵檢測技術按原理來分可以分為異常檢測和誤用檢測。

異常檢測(Abnormal Detection)又稱為基于行為的檢測，建立在系統正常工作模式基礎上。異常檢測方法通過異常監測器觀察主體的活動，然后產生刻畫這些活動的行為的輪廓。通過比較當前輪廓與己存儲的輪廓判斷異常行為，檢測出網絡入侵。

誤用入侵檢測型(Misuse Detection)又稱為基于知識的檢測，通過對比已知攻擊手段及系統漏洞的模式特征來判斷系統中是否有入侵發生。

遺傳算法(Genetic Algorithms，GA)是20世紀70年代初期，主要由美國密歇根大學的John.H.Holland和他的同事、學生們研究形成了一個較完整的理論和方法，從試圖解釋自然系統中生物的復雜適應過程入手，模擬生物進化的機制來構造人工系統的模型。遺傳算法是一種借鑒生物界自然選擇和進化機制發展起來的高度并行、隨機、自適應搜索算法。[2]

最早在入侵檢測系統中使用GA可以追溯到1995年的Crosbie使用多個代理和GP來檢測網絡的異常，每一個代理監控網絡的一個或幾個參數，GP用來綜合各個代理收集的數據來判斷網絡的異常行為。[3]

Lu在2004年提出了采用GP直接推導分類規則的方法，它采用支持一有效性適應度函數(support-confidence fitness function)，能準確地區分網絡入侵。當然由于使用GP，開銷非常大。[4]

Taeshik等利用遺傳算法研究了TCP/IP數據包中哪些字段和入侵關系最密切，結果顯示24個字段中有15個字段和入侵相關。[5]

目前來看，遺傳算法用在入侵檢測上主要進行的是異常檢測，而且大部分是采用訓練數據計算出相應網絡上的某個閾值，以此作為判斷是否有入侵的條件。

3 基于遺傳算法的入侵檢測訓練算法的設計

3.1 算法模型描述

數學模型的建立有助于更精確地描述入侵問題，特別是異常入侵檢測。Dennying提出了可用于入侵檢測的5種統計模型。

實驗模型基于這樣的假設：若變量X出現的次數超過某個預定的值，就有可能出現異常的情況。[6]

在基于異常入侵檢測的方法中經常使用的就是統計方法。其基本過程是：假設正常的數據存在內在的統計規律，入侵訓練算法通過對比某一段時間內的數據來獲得一個閾值。這些數據包含正常的數據和異常的數據，在訓練過程中的數據是人為發送的。系統根據訓練算法得出一個結論，也就是閾值。閾值可以是單值，也可以是區間。如果是單值，則大于閾值的判斷為異常數據，反之正常；如果是區間，在閾值內的判斷為異常數據，閾值外的是正常數據。此方法有個很大的缺點就是對于不同的網絡會得到不同的結論，訓練的時間長短也將會得到不同的結論。但是對于網絡規模比較小，而且數據都比較有規律的系統比較實用，這樣可以檢測到某些并不常用的攻擊。

3.2 訓練算法的偽代碼

下面給出訓練算法的偽代碼：

輸入：網絡的審計數據，本文采用林肯實驗室的測試數據

輸出：一組檢測規則

隨機初試化種群;

N=訓練數據集的記錄數;

For種群中的每一個染色體

A₁=A₂=…A_n=0;

For訓練數據集合中的每一個數據記錄If當前的數據值分布在區間A_j{ A_j++; }

Fitness=1-Min(A_j)/N;

IfFitness符合要求{退出;}

IfFitness>T { 選擇該染色體進入下一代的種群; }

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

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

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

如果進化代數還未到，next;

結束。

4 遺傳算法的構造和簡單實現

4.1 遺傳算法的構造

算法以TCP/IP數據包為研究對象，其中染色體是由表1中的異常值所組成的，例如(a₁，a₂，…，a₂₁)。每個染色體包含很多個屬性，也就是基因。每個基因對于染色體的影響(異常值)不相同。對于某個染色體而言，判斷某個數據包是否入侵的函數為：

C(X) = AX(x)

= a_ix_i+…+a₂x₂+a₁x₁，i=(1，…，21)

其中a_i是表1中的異常值，x_i是那個參數所對應的實際數據中的值。異常值中很多是沒有用的也就是為0。算法的目的就是要確定出最佳染色體，也就是得到最佳異常值的組合，得到最佳染色體的同時可以獲得一個閾值。

為了獲得最佳染色體，我們需要構造一個適應度函數。假設訓練數據的總數為N，根據函數C(X)計算出的值會分布在不同的區間，設每個區間的長度為L，分布在每個區間的數據包數量為A_j(j=0，1，2，…，n)，那么入侵的數據就應該分布在某個區間內。如何正確選擇這個區間關系到入侵檢測系統的正確率、漏報率等很多重要性能。由于入侵的數據一般都是占少數，所以選擇區間中包含數據包最少的為異常區間，也即閾值。根據這個原理，那么適應度函數構造如下:

F(X) = 1-MinA_j/N(j=0，1，2，…，n)

上面構造的適應度函數滿足連續、非負的要求。有了適應度函數后，就需要設計遺傳算子。遺傳算子包括選擇、交叉與變異運算。選擇運算建立在對染色體適應度評價基礎上，它將優良個體進行復制，從而體現遺傳算法優勝劣汰的進化準則。交叉算子是產生新個體的最主要方法，而變異算子模擬生物進化變異，也是產生新物種不可忽視的因素。[7]

遺傳算法的主要步驟：

1) 初始化種群

產生初始種群的方法通常有兩種。一種是完全隨機的方法產生，它適合于對問題的解無任何先驗知識的情況。某些先驗知識可轉變為必須滿足的一組要求，然后在滿足這些要求的解中再隨機地選取樣本。這樣選擇初始種群可使遺傳算法更快地到達最優解[8]。隨機初始化染色體種群，一般情況下用隨機的方法產生。種群的大小決定了搜索的時間同時也影響搜索的精度。一般拿情況下種群大小為20-100。

2) 選擇再生

選擇是用來確定重組或交叉個體，以及被選個體將產生多少個子代個體。選擇操作的算法有比列選擇、排序選擇等，本文選擇后者，就是把適應度排在最后幾位的淘汰。

3) 交叉

通過交又操作可以在父代的基礎上產生子代，然后在父代與子代組成的種群中根據適應度函數的大小選出下一代個體。在本文中為了簡單起見采用單點交叉。具體實現方法是：設進行交叉操作的概率為Pc，那么種群中每次約有G*Pc個染色體進行交叉操作，G為種群大小。

4) 變異

變異算子通常一次只改變一個染色體上的一個基因，一般認為，變異算子的重要性次于交叉算子，但其作用不容忽視。通過突變可以產生僅通過選擇和交叉無法產生的最優解。具體實現方法是：設發生突變的概率為Pm，這個概率表明種群中每次約有G*Pm個染色體進行突變操作。

5) 終止條件

當迭代代數達到指定代數還未產生最佳染色體時，算法終止，需要重新計算。當某個染色體符合要求時，算法也終止。

4.2 算法簡單實現

算法使用C語言簡單實現。

算法的框架：

initpopulation(generation); //初始化種群

srand((unsigned)time(0));

flag=-1;

for(i=1;i<=100;i++)//i代表目前的代數

{

for(j=0;j

{

fitness[j]=gene(generation[j]，fp，pkt_data，header，100000);

if(fitness[j]<0.0005)flag=j;

}

if(flag>=0)

{

printf(\"The final fitness:%f\\"，fitness[flag]);

printf(\"The generation is %d\The gene is :\\"，i);

for(k=0;k<8;k++)

{

printf(\"%d \"，generation[flag][k]);

}

printf(\"\\");

break; //終止條件

}

arraysort(fitness，fitnessorder);

//選擇再生

for(k=0;k

{

tmp1=fitnessorder[k];

tmp2=fitnessorder[POPULATION-k-1];

selectgene(generation[tmp1]，generation[tmp2]);

}

//交叉

for(k=0;k

{

tmp3=1.0*(rand()%100)/100.0;

if(tmp3

{

crossover(generation[k]，generation[k+1]);

}

}

//變異

for(k=0;k

（上接第2584頁）

{

tmp3=1.0*(rand()%100)/100.0;

if(tmp3

{

mutation(generation[k]);

}

}

}//end for

選取了10000條林肯實驗室的數據對算法進行測試，初始種群大小為100，通過不同的選擇概率、交叉概率和變異概率，得出了不同的最佳適應度個體。樣本中我們自己插入了10條攻擊樣本，包括SYN Flood，Land，netpune等常見針對TCP/IP協議進行的攻擊，適應度最高時能正確檢測到8條攻擊數據，而適應度為0.9500時能檢測到9條數據。最終選擇適應度為0.9500，如表2所示。

表2 最佳適應度測試

5 結論

該文介紹了一個基于遺傳算法的入侵檢測模型，該模型與傳統入侵檢測模型相比有如下特點：入侵檢測效率高，準確率高，而且能檢測到部分未知攻擊，可以彌補目前基于誤用檢測的一些不足。

目前算法還存在很多不足，穩定性不夠，有時需要多次運行才能得到結果。今后需要進一步對算法進行優化。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”參考文獻：

[1] 羅守山.入侵檢測[M].北京:北京郵電大學出版社，2004.

[2] 張文修，梁怡.遺傳算法的數學基礎[M].2版.西安:西安交通大學出版社，2004.

[3] Crosbie M，Spafford G.Defending a Computer System using Autonomous Agents[R].Technical Report No.95-022，1994，1-11.

[4] Lu W， Traore I.Detecting New Forms of Network Intrusion Using Genetic Programming[J].Evolutionary Computation， 2003，3: 2165-2172.

[5] Taeshik S， Xeno K， Jongsub M．Applying genetic algorithm for classifying anomalous TCP/IP packets[J].Neurocomputing， 2006，69: 2429-2433

[6] 印潤遠.計算機信息安全[M].北京:中國鐵道出版社，2006:121.

[7] 金義富，朱慶生，鄒咸林.基于遺傳算法的離群約簡搜索算法[J].計算機科學，2006(33):200.

[8] 王小平，曹立明.遺傳算法—理論、應用與軟件實現[M].西安:西安交通大學出版社，2002.