??? 摘? 要: 將生物進化的理論引入入侵檢測系統(tǒng),在算法中體現(xiàn)出基因算法的并行優(yōu)勢。
關(guān)鍵詞: 入侵檢測? 生物進化理論? 基因算法
?
生物進化計算理論起源于20世紀(jì)50年代末,成熟于20世紀(jì)80年代。Holland和Goldberg提出的基因算法GA(Genetic Algorithm)強調(diào)染色體的操作。本文采用GA進行實驗。
GA通過模擬達爾文“優(yōu)勝劣汰,適者生存”的原理激勵更好的結(jié)構(gòu);通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結(jié)構(gòu),同時尋找更好的結(jié)構(gòu),即迭代自適應(yīng)隨機性優(yōu)化搜索算法。作為生物進化計算的主要手段之一,GA產(chǎn)生之初就是對自然界進化過程的一個簡單模擬,并借用一些生物學(xué)術(shù)語:個體(individual):表示問題的一個可能解;種群(population):表示一組個體的集合。問題的解用定長二進制編碼來表示,所以也稱個體為位串(string)。在種群中,每個個體的性能用適值函數(shù)來度量,其值稱為適應(yīng)值或適值(fitness)。一組遺傳操作(genetic operation,包括選擇selection、交叉crossover、變異mutation)作用于種群上,使得種群不斷進化,直到產(chǎn)生符合要求的個體即求得問題的最優(yōu)解或次優(yōu)解為止。
入侵檢測是對以計算機系統(tǒng)或網(wǎng)絡(luò)資源為目標(biāo)的非法、惡意的行為或企圖及那些濫用其權(quán)限的識別和反應(yīng)過程的統(tǒng)稱。目前的研究基本可以歸納為異常檢測(anomaly-based)和誤用檢測(misuse-based)。異常檢測是假設(shè)入侵活動具有不同于正常用戶活動的特征,即入侵活動表現(xiàn)為異常。它雖然能檢測到一些未知入侵,但是誤警率很高,閾值很難把握。誤用檢測首先將已知的每種入侵方法都表示成一條入侵規(guī)則,將當(dāng)前發(fā)生的活動與入侵規(guī)則集進行匹配。如果當(dāng)前的活動與某條入侵規(guī)則匹配,則認(rèn)為是采用該種入侵方法發(fā)起的一次攻擊。商用軟件多采取這種方式,其優(yōu)點是對已知入侵的判斷準(zhǔn)確率高,但對未知入侵則無能為力。
為了增大誤用檢測的靈活性,可以通過概念學(xué)習(xí)的方法對入侵檢測模式庫中的規(guī)則進行提純,然后利用生物進化理論中的基因算法進行搜索。
1? 生物進化理論解決模式庫動態(tài)提純問題
1.1 實驗在整個系統(tǒng)中的位置
本文在已有的基于改進模式匹配的IDS(Intrusion Detection System,入侵檢測系統(tǒng))中添加了概念學(xué)習(xí)模塊。所謂改進的模式匹配是指加入了檢測分步攻擊的規(guī)則。例如在對主機審計日志的檢測時,考慮到攻擊者在入侵一個系統(tǒng)時往往采用一定的行為模式,而這種行為模式構(gòu)成了某種具有一定行為特征的模型。因此可用這種模型所代表的攻擊特征作為規(guī)則。該模塊主要功能是:利用概念學(xué)習(xí)的思想,滯后進行提純模式庫。
鑒于進化計算運行時需消耗大量資源,為了不影響主模塊(HOST)的實時檢測,該模塊單獨運行在另一臺主機上(LAB_PC)并和主模塊保持通信,定期更新模式庫。圖1為系統(tǒng)相關(guān)部分的描述。
?
1.2 實驗的描述
在改進的模式匹配IDS中,可以將審計事件集看作一個字符集。每個事件可看成一個字符,審計活動是一個主串,而異常行為(稱作攻擊腳本子集)作為一個子串,需要被定位于主串的某個位置。這樣,問題被轉(zhuǎn)換為:給定一個輸入字符串p和一個由s所構(gòu)成的模式,目標(biāo)是找到p中包含一個可以被s匹配的子串。
在一個給定的攻擊集合里,每個攻擊的發(fā)生都會引發(fā)一個審計事件或事件序列。因此,可以首先計算其中所有攻擊將產(chǎn)生的每種類型事件的數(shù)目。如果所記錄到的這些事件實際發(fā)生的數(shù)目大于或等于這些事件的計算值,則可以認(rèn)為相對應(yīng)于這些攻擊子集所作的假設(shè)是正確的。反之,認(rèn)為這些攻擊必定沒有發(fā)生(此處借用異常檢測的思想)。而滿足這個條件的解可能有多個,實驗的目的就是分析所記錄的審計活動,在所有可能的攻擊子集中尋找對系統(tǒng)最具威協(xié)性的攻擊(最優(yōu)解)。下面給出精確描述:
?
(1)式是典型的0-1規(guī)劃NP-Complete。當(dāng)階次急劇增大時,使用傳統(tǒng)的求解方法相當(dāng)困難且不現(xiàn)實,因此采用諸如GA這類生物進化的啟發(fā)式搜索辦法。
1.3 基因算法的核心要素
GA在實現(xiàn)過程中,始終圍繞著以下5個核心要素:參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定等。下面將圍繞這幾個核心要素對算法進行闡述。
(1)參數(shù)編碼
????GA不能直接處理問題空間的參數(shù),因此,必須把優(yōu)化問題的參數(shù)形式的解轉(zhuǎn)換成位串的表示形式。在編碼時,結(jié)合二進制編碼的優(yōu)勢以及出于避免海明懸崖(Hamming Cliffs)的考慮,采用Gray編碼。
設(shè)二進制串b1,b2,……bn,對應(yīng)的Gray串為a1,a2,……an,從二進制編碼到Gray編碼的變換為:
(2)初始群體的設(shè)定
群體大小L表示群體中所含個體的數(shù)量。通常,L越大GA所處理的模式就越多,生成有意義的基因塊并逐漸進化為最優(yōu)解的機會就越高,算法陷入局部解的危險性也就越小。但是,L增大的代價卻是實驗中的計算復(fù)雜度以指數(shù)級增加。反之,降低L可提高運算速度,卻降低了整個群體的多樣性,引發(fā)每代個體的早熟。所以一般取值為20～100。
(3)適值函數(shù)的設(shè)計
GA在優(yōu)化搜索中基本上不需外部信息,僅以適值函數(shù)作為尋優(yōu)依據(jù)。而且GA對適值函數(shù)惟一要求是不為負(fù),這使得GA的應(yīng)用范圍極廣。這里需要搜索整個問題空間,以便找出對系統(tǒng)危害最大的攻擊子集,也就是最大化乘積W×H。實驗設(shè)定根據(jù)式(3)來評估優(yōu)劣,并作為以后遺傳操作的依據(jù)。但是,如果僅靠適值函數(shù)來評估和引導(dǎo)搜索,會使求解問題所固有的約束條件不能明確表示出來。
式(3)中并沒有考慮問題的約束條件:(EH)i≤Oi(1≤i≤Na)。當(dāng)(EH)i>Oi時,在總計2Ne種不同的攻擊子集的假設(shè)中有一些個體是不具備現(xiàn)實意義的。所以必須考慮懲罰函數(shù)以減少它們的適應(yīng)值,從而使約束優(yōu)化問題轉(zhuǎn)換成為一個附帶考慮代價的非約束優(yōu)化問題。同時,為避免出現(xiàn)早熟現(xiàn)象,根據(jù)Joines提出的動態(tài)懲罰函數(shù)給出適值函數(shù)如下:
設(shè)A為Ne×1的零矩陣,則:
(4)遺傳操作設(shè)計
本文涉及的遺傳算子有:期望值選擇、單點交叉、基本變異。
1.4 實驗流程
實驗通過linux下的C語言編程實現(xiàn)。編程環(huán)境:Red Hat7.0,GCC編譯器,GDA調(diào)試器。由于GA的隨機性及不確定性等特點,通常要多運行幾次才能找到可靠的解。每次實驗用四元組(Pc,Pm,L,a)表示。其中:Pc為交叉概率;Pm為變異概率;L為群體大小,本實驗中取值為24;a為實際出現(xiàn)在審計活動中的攻擊的數(shù)目。最后將終止代的群體中的最佳個體作為所求問題的最優(yōu)解輸出。實驗中取Pc=0.6,Pm=0.002。
定義一個比率Tp來反映檢測的準(zhǔn)確程度(實際攻擊所在的編碼位為1的個體數(shù)比種群總個體數(shù)L)。指定Tpi為Tp在第i代的值。表1是十次平均數(shù)據(jù)結(jié)果,可以看出當(dāng)進化到80代時,Tpi幾乎接近1,從而得到問題最優(yōu)解。
?
2? 小? 結(jié)
本文將生物進化的思想引入IDS,在算法中體現(xiàn)出GA的并行優(yōu)勢。實驗在以下幾個方面還需改進:
(1)如果采用動態(tài)Pm,即改進實驗中采用的基本變異算子,則將變異算子與進化代數(shù)聯(lián)系起來,使進化初期變異的范圍相對較大,而隨著進化的推進,變異的范圍越來越小。這里的Pm對進化起微調(diào)的作用。例如可以采用這樣的方法:首先在個體k中隨機選取一個分量ki,對ki變異后的結(jié)果ki′服從N(ki,δ2(t))的正態(tài)分布。其中t是進化的代數(shù),δ2(t)隨著t的增大而趨于0。當(dāng)然,若δ2(t)不同,將導(dǎo)致算法略微不同。
(2)如果某些事件或事件組對于特定的攻擊普遍存在,則攻擊者利用這一點向目標(biāo)系統(tǒng)同時發(fā)起多次攻擊,使實驗無法找到最佳的向量表示。
(3)此實驗?zāi)K必須和基于改進模式匹配主模塊配合使用,實驗?zāi)K不能獨立承擔(dān)實時檢測義務(wù)。
?
參考文獻
1? 王正志,薄濤編.進化計算.長沙:國防科技大學(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