??? 摘? 要: 將生物進(jìn)化的理論引入入侵檢測系統(tǒng),在算法中體現(xiàn)出基因算法的并行優(yōu)勢。

　　關(guān)鍵詞: 入侵檢測? 生物進(jìn)化理論? 基因算法

?

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

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

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

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

1? 生物進(jìn)化理論解決模式庫動(dòng)態(tài)提純問題

1.1 實(shí)驗(yàn)在整個(gè)系統(tǒng)中的位置

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

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

?

1.2 實(shí)驗(yàn)的描述

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

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

?

　　(1)式是典型的0-1規(guī)劃NP-Complete。當(dāng)階次急劇增大時(shí),使用傳統(tǒng)的求解方法相當(dāng)困難且不現(xiàn)實(shí),因此采用諸如GA這類生物進(jìn)化的啟發(fā)式搜索辦法。

1.3 基因算法的核心要素

　　GA在實(shí)現(xiàn)過程中,始終圍繞著以下5個(gè)核心要素:參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定等。下面將圍繞這幾個(gè)核心要素對算法進(jìn)行闡述。

　　(1)參數(shù)編碼

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

　　設(shè)二進(jìn)制串b₁,b₂,……b_n,對應(yīng)的Gray串為a₁,a₂,……a_n,從二進(jìn)制編碼到Gray編碼的變換為:

　　(2)初始群體的設(shè)定

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

　　(3)適值函數(shù)的設(shè)計(jì)

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

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

　　設(shè)A為N_e×1的零矩陣,則:

　　(4)遺傳操作設(shè)計(jì)

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

1.4 實(shí)驗(yàn)流程

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

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

?

2? 小? 結(jié)

　　本文將生物進(jìn)化的思想引入IDS,在算法中體現(xiàn)出GA的并行優(yōu)勢。實(shí)驗(yàn)在以下幾個(gè)方面還需改進(jìn):

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

　　(2)如果某些事件或事件組對于特定的攻擊普遍存在,則攻擊者利用這一點(diǎn)向目標(biāo)系統(tǒng)同時(shí)發(fā)起多次攻擊,使實(shí)驗(yàn)無法找到最佳的向量表示。

　　(3)此實(shí)驗(yàn)?zāi)K必須和基于改進(jìn)模式匹配主模塊配合使用,實(shí)驗(yàn)?zāi)K不能獨(dú)立承擔(dān)實(shí)時(shí)檢測義務(wù)。

?

參考文獻(xiàn)

1? 王正志,薄濤編.進(jìn)化計(jì)算.長沙:國防科技大學(xué)出版社,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