??? 摘? 要: 將生物進化的理論引入入侵檢測系統,在算法中體現出基因算法的并行優勢。

　　關鍵詞: 入侵檢測? 生物進化理論? 基因算法

?

　　生物進化計算理論起源于20世紀50年代末,成熟于20世紀80年代。Holland和Goldberg提出的基因算法GA(Genetic Algorithm)強調染色體的操作。本文采用GA進行實驗。

　　GA通過模擬達爾文“優勝劣汰,適者生存”的原理激勵更好的結構;通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結構,同時尋找更好的結構,即迭代自適應隨機性優化搜索算法。作為生物進化計算的主要手段之一,GA產生之初就是對自然界進化過程的一個簡單模擬,并借用一些生物學術語:個體(individual):表示問題的一個可能解;種群(population):表示一組個體的集合。問題的解用定長二進制編碼來表示,所以也稱個體為位串(string)。在種群中,每個個體的性能用適值函數來度量,其值稱為適應值或適值(fitness)。一組遺傳操作(genetic operation,包括選擇selection、交叉crossover、變異mutation)作用于種群上,使得種群不斷進化,直到產生符合要求的個體即求得問題的最優解或次優解為止。

　　入侵檢測是對以計算機系統或網絡資源為目標的非法、惡意的行為或企圖及那些濫用其權限的識別和反應過程的統稱。目前的研究基本可以歸納為異常檢測(anomaly-based)和誤用檢測(misuse-based)。異常檢測是假設入侵活動具有不同于正常用戶活動的特征,即入侵活動表現為異常。它雖然能檢測到一些未知入侵,但是誤警率很高,閾值很難把握。誤用檢測首先將已知的每種入侵方法都表示成一條入侵規則,將當前發生的活動與入侵規則集進行匹配。如果當前的活動與某條入侵規則匹配,則認為是采用該種入侵方法發起的一次攻擊。商用軟件多采取這種方式,其優點是對已知入侵的判斷準確率高,但對未知入侵則無能為力。

　　為了增大誤用檢測的靈活性,可以通過概念學習的方法對入侵檢測模式庫中的規則進行提純,然后利用生物進化理論中的基因算法進行搜索。

1? 生物進化理論解決模式庫動態提純問題

1.1 實驗在整個系統中的位置

　　本文在已有的基于改進模式匹配的IDS(Intrusion Detection System,入侵檢測系統)中添加了概念學習模塊。所謂改進的模式匹配是指加入了檢測分步攻擊的規則。例如在對主機審計日志的檢測時,考慮到攻擊者在入侵一個系統時往往采用一定的行為模式,而這種行為模式構成了某種具有一定行為特征的模型。因此可用這種模型所代表的攻擊特征作為規則。該模塊主要功能是:利用概念學習的思想,滯后進行提純模式庫。

　　鑒于進化計算運行時需消耗大量資源,為了不影響主模塊(HOST)的實時檢測,該模塊單獨運行在另一臺主機上(LAB_PC)并和主模塊保持通信,定期更新模式庫。圖1為系統相關部分的描述。

?

1.2 實驗的描述

　　在改進的模式匹配IDS中,可以將審計事件集看作一個字符集。每個事件可看成一個字符,審計活動是一個主串,而異常行為(稱作攻擊腳本子集)作為一個子串,需要被定位于主串的某個位置。這樣,問題被轉換為:給定一個輸入字符串p和一個由s所構成的模式,目標是找到p中包含一個可以被s匹配的子串。

　　在一個給定的攻擊集合里,每個攻擊的發生都會引發一個審計事件或事件序列。因此,可以首先計算其中所有攻擊將產生的每種類型事件的數目。如果所記錄到的這些事件實際發生的數目大于或等于這些事件的計算值,則可以認為相對應于這些攻擊子集所作的假設是正確的。反之,認為這些攻擊必定沒有發生(此處借用異常檢測的思想)。而滿足這個條件的解可能有多個,實驗的目的就是分析所記錄的審計活動,在所有可能的攻擊子集中尋找對系統最具威協性的攻擊(最優解)。下面給出精確描述:

?

　　(1)式是典型的0-1規劃NP-Complete。當階次急劇增大時,使用傳統的求解方法相當困難且不現實,因此采用諸如GA這類生物進化的啟發式搜索辦法。

1.3 基因算法的核心要素

　　GA在實現過程中,始終圍繞著以下5個核心要素:參數編碼、初始群體的設定、適應度函數的設計、遺傳操作設計、控制參數設定等。下面將圍繞這幾個核心要素對算法進行闡述。

　　(1)參數編碼

????GA不能直接處理問題空間的參數,因此,必須把優化問題的參數形式的解轉換成位串的表示形式。在編碼時,結合二進制編碼的優勢以及出于避免海明懸崖(Hamming Cliffs)的考慮,采用Gray編碼。

　　設二進制串b₁,b₂,……b_n,對應的Gray串為a₁,a₂,……a_n,從二進制編碼到Gray編碼的變換為:

　　(2)初始群體的設定

　　群體大小L表示群體中所含個體的數量。通常,L越大GA所處理的模式就越多,生成有意義的基因塊并逐漸進化為最優解的機會就越高,算法陷入局部解的危險性也就越小。但是,L增大的代價卻是實驗中的計算復雜度以指數級增加。反之,降低L可提高運算速度,卻降低了整個群體的多樣性,引發每代個體的早熟。所以一般取值為20～100。

　　(3)適值函數的設計

　　GA在優化搜索中基本上不需外部信息,僅以適值函數作為尋優依據。而且GA對適值函數惟一要求是不為負,這使得GA的應用范圍極廣。這里需要搜索整個問題空間,以便找出對系統危害最大的攻擊子集,也就是最大化乘積W×H。實驗設定根據式(3)來評估優劣,并作為以后遺傳操作的依據。但是,如果僅靠適值函數來評估和引導搜索,會使求解問題所固有的約束條件不能明確表示出來。

　　式(3)中并沒有考慮問題的約束條件:(EH)_i≤O_i(1≤i≤Na)。當(EH)_i>Oi時,在總計2^Ne種不同的攻擊子集的假設中有一些個體是不具備現實意義的。所以必須考慮懲罰函數以減少它們的適應值,從而使約束優化問題轉換成為一個附帶考慮代價的非約束優化問題。同時,為避免出現早熟現象,根據Joines提出的動態懲罰函數給出適值函數如下:

　　設A為N_e×1的零矩陣,則:

　　(4)遺傳操作設計

　　本文涉及的遺傳算子有:期望值選擇、單點交叉、基本變異。

1.4 實驗流程

　　實驗通過linux下的C語言編程實現。編程環境:Red Hat7.0,GCC編譯器,GDA調試器。由于GA的隨機性及不確定性等特點,通常要多運行幾次才能找到可靠的解。每次實驗用四元組(P_c,P_m,L,a)表示。其中:P_c為交叉概率;P_m為變異概率;L為群體大小,本實驗中取值為24;a為實際出現在審計活動中的攻擊的數目。最后將終止代的群體中的最佳個體作為所求問題的最優解輸出。實驗中取P_c=0.6,P_m=0.002。

　　定義一個比率T_p來反映檢測的準確程度(實際攻擊所在的編碼位為1的個體數比種群總個體數L)。指定T_pi為T_p在第i代的值。表1是十次平均數據結果,可以看出當進化到80代時,T_pi幾乎接近1,從而得到問題最優解。

?

2? 小? 結

　　本文將生物進化的思想引入IDS,在算法中體現出GA的并行優勢。實驗在以下幾個方面還需改進:

　　(1)如果采用動態Pm,即改進實驗中采用的基本變異算子,則將變異算子與進化代數聯系起來,使進化初期變異的范圍相對較大,而隨著進化的推進,變異的范圍越來越小。這里的Pm對進化起微調的作用。例如可以采用這樣的方法:首先在個體k中隨機選取一個分量ki,對ki變異后的結果ki′服從N(k_i,δ₂(t))的正態分布。其中t是進化的代數,δ₂(t)隨著t的增大而趨于0。當然,若δ₂(t)不同,將導致算法略微不同。

　　(2)如果某些事件或事件組對于特定的攻擊普遍存在,則攻擊者利用這一點向目標系統同時發起多次攻擊,使實驗無法找到最佳的向量表示。

　　(3)此實驗模塊必須和基于改進模式匹配主模塊配合使用,實驗模塊不能獨立承擔實時檢測義務。

?

參考文獻

1? 王正志,薄濤編.進化計算.長沙:國防科技大學出版社,2000

2? Denning D E.An intrusion detection model.IEEE Transaction on Software Engineering,1987;SE-13(2)

3? Kumar S.Classification and Detection of Computer?Intrusions.PH.D thesis.Purdue University,1995

4? Goldberg D E.Genetic Algorithms in Search Optimization and Machine Learning.New York,AddisonWesley

Publishing CO,1989