否定選擇算法

1、關(guān)于否定選擇算法第一張，PPT共三十七頁，創(chuàng)作于2022年6月否定選擇算法 1.1 算法功能 1994年，F(xiàn)orrest，Perelson等人提出的否定選擇算法成功的模擬了免疫系統(tǒng)識別自我和非我的免疫耐受過程。這種識別能力源于T細(xì)胞(免疫細(xì)胞的一種)表面的受體可檢測到外來抗原。在T細(xì)胞的產(chǎn)生過程中，通過偽隨機(jī)遺傳重組過程來形成，然后這些細(xì)胞通過一個檢測過程即否定選擇過程，在胸腺的T細(xì)胞(未成熟的T細(xì)胞)，對自身蛋白有反應(yīng)的被破壞，只有那些不與自身蛋白結(jié)合的T細(xì)胞可以離開胸腺(成熟的T細(xì)胞)此后，這些成熟的細(xì)胞就在體內(nèi)血液中循環(huán)，完成免疫功能，保護(hù)身體不受外來抗原損害。 目前，免疫細(xì)胞的自體耐受

2、主要由否定選擇算法來實(shí)現(xiàn)。在入侵檢測領(lǐng)域里，使用否定選擇算法生成檢測器。1.2 算法描述 否定選擇算法 (如圖3.1所示)可概括如下:(1)定義自體為一個長度為L的字符串的集合，S表示“自體”一個受保護(hù)或者監(jiān)督的集體。例 如，S可以是一個文件片段或者是某個系統(tǒng)與過程的活動模式;(2)產(chǎn)生檢測器集合R，每一個R中檢測器與任何S中的字符串都不匹配;(3)通過不斷地將R中的檢測器與S比較來監(jiān)控S的改變。采用部分匹配規(guī)則，兩個字符串當(dāng)且僅 當(dāng)至少在r個連續(xù) 位上一樣時才發(fā)生匹配，是一個被選定的合適的參數(shù)，監(jiān)督S變化。檢測 器與S連續(xù)匹配，如果任何檢測器都匹配，則一定有變化發(fā)生。第二張，PPT共三十七頁

3、，創(chuàng)作于2022年6月 否定選擇算法 第三張，PPT共三十七頁，創(chuàng)作于2022年6月 2.1 r一連續(xù)位匹配規(guī)則 r-連續(xù)位的匹配規(guī)則是指任意兩個字符串，如果兩個字符串中至少有連續(xù)r個對應(yīng)位上的符號相同，就說這兩個字符串匹配。即有任意兩個字符串x和y，如果x和y至少有r個連續(xù)對應(yīng)位上的符號相同，則有x和y連續(xù)r位匹配。例如:字符表A，B，C，D，E，x和y為定義于其上的任意2個字符串X CBACDEABY BDADCDEA 其中，有3個連續(xù)位上的符號相同(見下劃線部分)。當(dāng)r3時，為x和y匹配。 這種匹配規(guī)則可應(yīng)用于任意符號表上定義的字符串,最通用的符號表為0，l。 在一連續(xù)位的匹配規(guī)則，用P

4、M為任意兩個等長隨機(jī)字符串的匹配的概率，設(shè)如下參數(shù): m:表示符號表所含的符號數(shù)目 l:表示字符串所含符號的數(shù)目，即字符串的長度 r:表示匹配中所要求的連續(xù)匹配位數(shù)，即匹配長度 符號表中的m個符號是各不相同的、是互補(bǔ)的。對于字符串每一個位置上的符號，從符號表中選取符號與之匹配即相同的概率是1/m，而與之不匹配(即互補(bǔ))的概率是(1一1/m)。當(dāng)兩個長度為Z的字符串進(jìn)行比較時，如果至少有r連續(xù)對應(yīng)位上的符號相同，則這兩個串匹配。如果兩個字符串匹配，并且這種匹配是:從l長度字符串的最左端開始，有連續(xù)r個對應(yīng)位取值相同，則匹配的概率為:第四張，PPT共三十七頁，創(chuàng)作于2022年6月如果兩個字符串匹配

5、，并且匹配的起始位置是從l長度字符串左邊的第2位到第(l一r+1)位，那么在每次匹配成功的起始位置之前，總有不匹配發(fā)生時，其每次匹配成功的概率為:(m一1)/mXm一應(yīng)當(dāng)注意:該匹配概率是近似值。因?yàn)樗鼉H包括了那些在每次匹配成功的起始位置之前，沒有匹配發(fā)生的情況。而忽視了那些在每次匹配成功的起始位置之前，有匹配發(fā)生的情況。當(dāng)使r足夠大(即m一rl)時，可以減小精度誤差。因?yàn)楫?dāng)l不變時，隨r的增大，兩個字符串多處發(fā)生匹配的可能性將減小。于是，兩個字符串匹配的總概率可見，PM隨m，r和l變化而變化。第五張，PPT共三十七頁，創(chuàng)作于2022年6月2.2 檢測能力第六張，PPT共三十七頁，創(chuàng)作于202

6、2年6月第七張，PPT共三十七頁，創(chuàng)作于2022年6月2.3 否定選擇算法存在的問題 使用否定選擇算法產(chǎn)生的檢測器覆蓋異己空間越大說明檢測器的檢測能力也就越強(qiáng)。理想情況下，檢測器的容量越大，則覆蓋異己空間也就越廣。但實(shí)際情況是，自體集合是一個相對較為有限的空間，而非自體集合多數(shù)情況下近似于一個無窮的空間，要完全覆蓋異己空間就需要極其大量的檢測器。而從實(shí)際應(yīng)用的情況來看，有限的系統(tǒng)資源無法滿足完全產(chǎn)生這些有效檢測器的要求。故產(chǎn)生能覆蓋整個非自體空間的檢測器是不現(xiàn)實(shí)的。同時，根據(jù)3.2.4結(jié)論2也為該觀點(diǎn)提供了理論基礎(chǔ):有限的檢測器可以保護(hù)大量的自體數(shù)據(jù)集。 現(xiàn)在的問題是如何在檢測器容量確定的情況

7、下，盡可能多的覆蓋異己空間。 Forrest提出的否定選擇算法中，使用r一連續(xù)位匹配規(guī)則產(chǎn)生的檢測器會存在黑洞，使得覆蓋異己空間變小。 Forrest否定選擇算法中全長串的:一連續(xù)位匹配規(guī)則會存在兩類漏洞:交叉漏洞和限長漏洞。(1)限長漏洞 限長漏洞是漏洞串h至少有一個r位窗口不在S，其它窗口能夠和S匹配。 例如:S=110010，l=3，r=2，則h=101就是一個限長漏洞。因?yàn)闄z測h的檢測串必須 以10開頭或者以01結(jié)尾，但是任何這樣的檢測串都會與自體匹配而不能生成。(2)交叉漏洞 交叉漏洞是一個串h不在自我集S中，h中的所有窗口與S相鄰窗口交叉。 第八張，PPT共三十七頁，創(chuàng)作于2022

8、年6月2.3 否定選擇算法存在的問題下面用有向非循環(huán)圖DAG來描述這個漏洞。設(shè)s=0002，1011，l=4，r二2，則相應(yīng)的DAG圖(如圖3.2所示) 從左端結(jié)點(diǎn)出發(fā)，能夠產(chǎn)生串0001，0011，1001，1011，1000，其中0011，1001是交叉漏洞。第九張，PPT共三十七頁，創(chuàng)作于2022年6月 3.黑洞問題討論3.1 黑洞產(chǎn)生的原因盡管希望構(gòu)造一個完整的有效檢測器集合，但是總會有一些Nonself字符串無法被檢測到，這些Nonself串就稱為“黑洞”。圖3.3給出了黑洞的直觀形象表達(dá)，在形態(tài)空間中，self集與Nonself集的界面往往是不規(guī)則的，而匹配閩值是固定的，因此有一些

9、Nonself不能被任何檢測器檢測。 黑洞存在于任何匹配規(guī)則中，事實(shí)上，在生物免疫系統(tǒng)中，也存在黑洞問題，而且病原體總在向黑洞中進(jìn)化，使其更難被檢測到。第十張，PPT共三十七頁，創(chuàng)作于2022年6月3.2減少黑洞數(shù)目對于給定字符串長度L和匹配閉值r下帶有固定匹配率的r連續(xù)位匹配算法不可避免地會出現(xiàn)這樣的檢測黑洞。對于固定不變的Self集合，不同“形狀”的檢測器可以覆蓋不同的Nonself集，產(chǎn)生不同的檢測黑洞，如果能將不同“形狀”的檢測器共同作用，那么必然可以減少黑洞的存在。如圖3.4所示第十一張，PPT共三十七頁，創(chuàng)作于2022年6月 3.3漏洞的判定算法在描述算法之前首先給出以下幾個定義。

10、定義3.1字符串的r模板:在長度為L的字符串中，只對r個連續(xù)位置進(jìn)行定義，其它l-r個位置的字符可以任意取值，這樣的字符串稱為字符串r模板。定義3.2第i頭模板:是指從字符串的第i個位置開始有確定的定義，則該模板是第i模板。定義3.3第j尾模板:是指從字符串的第j+l個位置開始沒有確定的定義，則該模板是第j尾模板。 例如，*011*就是一個長度為8的字符串的3模板，同時也是一個第2頭模板和第4尾模板。定義3.4字符串的模板匹配:如果一個模板c，其連續(xù):個位置與字符串e的對應(yīng)位置的字符相同，則稱c，和e匹配。例如，*011*和1011010。 判定c是否為漏洞及生成有效檢測器的算法:(1)尋找c

11、的字符串r模板，并設(shè)其為第i頭模板，記為:Ci，使其與C匹配，但不與集合A的任 何元素匹配，同時根據(jù)r和i找到cj。如果存在這樣的模板則執(zhí)行第2步;否則認(rèn)為是漏洞，第十二張，PPT共三十七頁，創(chuàng)作于2022年6月如圖3.5所示第十三張，PPT共三十七頁，創(chuàng)作于2022年6月3.3 漏洞的判定算法第十四張，PPT共三十七頁，創(chuàng)作于2022年6月3.3漏洞的判定算法第十五張，PPT共三十七頁，創(chuàng)作于2022年6月舉例說明: 設(shè)模式的長度L=10，有“自體”模式串集合為A=11111100，10001111l，1100110100，0010010011。設(shè)“非自體”模式串e=0010110100，匹

12、配長度r=3。 利用上述算法判定字符串c是否是漏洞，如圖3.7。首先，構(gòu)造一個字符串r模板Ci=*101*，然后如圖進(jìn)行搜索，則可以看到*10101010就是一個有效的檢測器，因此可以說字符串c不是漏洞。 第十六張，PPT共三十七頁，創(chuàng)作于2022年6月4.基于改進(jìn)否定選擇算法的異常檢測模型第十七張，PPT共三十七頁，創(chuàng)作于2022年6月4.1.2模型框架 該模型分為檢測器生成和檢測器識別兩個模塊。如圖4.1所示。檢測器生成模塊采用否定選擇算法來生成，但將算法中采用的rcb匹配規(guī)則用r-字符塊匹配規(guī)則替換。首先，選擇匹配閡值R，設(shè)置T檢測器容量，利用改進(jìn)的否定選擇算法生成T檢測器;其次，選擇匹

13、配閉值R1，使得R1R，設(shè)置B檢測器容量，利用改進(jìn)的否定選擇算法生成B檢測器。 檢測器識別模塊采用B、T雙檢測器協(xié)同識別，匹配規(guī)則仍為r一字符塊匹配規(guī)則。如圖第十八張，PPT共三十七頁，創(chuàng)作于2022年6月第十九張，PPT共三十七頁，創(chuàng)作于2022年6月第二十張，PPT共三十七頁，創(chuàng)作于2022年6月第二十一張，PPT共三十七頁，創(chuàng)作于2022年6月第二十二張，PPT共三十七頁，創(chuàng)作于2022年6月4.3 B/丁檢測器協(xié)同識別4.3.1生物免疫中B、丁細(xì)胞的作用及其協(xié)同關(guān)系 生物免疫系統(tǒng)是一個主要由淋巴細(xì)胞構(gòu)成的系統(tǒng)。淋巴細(xì)胞有兩種，一種是B細(xì)胞，它是體液免疫，分泌抗體，抗體能夠識別并結(jié)合抗原

14、，最終清除抗原。另一種是T細(xì)胞，它是細(xì)胞免疫。其作用主要是給B細(xì)胞提供一個信號，確認(rèn)B細(xì)胞識別的nonself. B、T細(xì)胞通過細(xì)胞的接收器和抗原的抗原決定基綁定來識別抗原。接收器是由基因片斷隨機(jī)組合生成，接收器和抗原決定基越相似，它們之間的親合度越高，越容易綁定。識別抗原的任務(wù)主要是由B細(xì)胞完成的，當(dāng)它綁定到未接觸過的抗原時，會產(chǎn)生一個初次反應(yīng)，分泌抗體，消滅抗原。同時“學(xué)習(xí)”并記憶這種特殊的抗原結(jié)構(gòu)，當(dāng)它再次接觸同種抗原時，會快速發(fā)生再次反應(yīng)，表現(xiàn)出很快的響應(yīng)速度。其中，B細(xì)胞的“學(xué)習(xí)”、記憶能力是通過一個親和性成熟的過程。在初次反應(yīng)后，和抗原具有高親和性的B細(xì)胞大量克隆(復(fù)制)自身，在克

15、隆過程中以較高的概率進(jìn)行變異，因變異率較高，所以經(jīng)克隆、變異過程后產(chǎn)生的新的B細(xì)胞，可能其親合度還不及父細(xì)胞，所以必須再經(jīng)過親合度判斷，親合度最高的B細(xì)胞留下，去替換親合度低的B細(xì)胞。 T細(xì)胞是在胸腺中分化發(fā)育的，而胸腺中存在體內(nèi)大部分的self蛋白，當(dāng)新生成的T細(xì)胞可以和Self蛋白綁定時，就在成熟培養(yǎng)的過程中死亡。所以，最后存活下來的T細(xì)胞是能識別nonself，而不能識別Self。T細(xì)胞的作用就是給B細(xì)胞提供一個信號，確認(rèn)B細(xì)胞識別的是nonself，表現(xiàn)出和兩種細(xì)胞的協(xié)同關(guān)系，由此可以降低B細(xì)胞的誤識別率。第二十三張，PPT共三十七頁，創(chuàng)作于2022年6月4.3.2 B、T檢測器原理

16、該文借鑒B、T細(xì)胞協(xié)作識別抗原的免疫機(jī)理，生成B、T雙檢測器進(jìn)行協(xié)同識別異常行為。 首先，匹配閡值設(shè)置為r，使用改進(jìn)的否定選擇算法生成T檢測器。 其次，選擇另一匹配閉值r1，令r1r，仍然使用改進(jìn)的否定選擇算法生成B檢測器。 最后，生成B、T雙檢測器進(jìn)行協(xié)同識別。將B檢測器作為T檢測器的前置過濾檢測器，用于進(jìn)一步減輕T檢測器的檢測負(fù)擔(dān)，提高檢測速度和準(zhǔn)確率。4.3.3 檢測器生成 檢測器的生成算法(如圖4.5)如下: (l)字符串隨機(jī)發(fā)生器隨機(jī)生成L位的二進(jìn)制字符串，這時生成的字符串是未成熟的，還不能作為檢測器使用，這些隨機(jī)生成的字符串只是作為檢測器的候選字串; (2)二進(jìn)制字符串與Self集

17、中的每一個字符串作，一字符塊匹配運(yùn)算，如果該二進(jìn)制字符串與Self集中任一個字符串匹配運(yùn)算為真，則忽略字符串(所謂的殺死)，轉(zhuǎn)入步驟1，如果該二進(jìn)制字符串與Self中的每一個字符串都不匹配，那么將該字符串加入到檢測器集中去，成為成熟的檢測器; (3)判斷檢測器集中的檢測器的數(shù)目是否達(dá)到一定的量，如果達(dá)到，構(gòu)造完畢，否則轉(zhuǎn)入步驟1。第二十四張，PPT共三十七頁，創(chuàng)作于2022年6月檢測器的生成算法如圖4.5如下:第二十五張，PPT共三十七頁，創(chuàng)作于2022年6月4.3.4 檢測器識別 當(dāng)B、T檢測器生成后，就可用它們協(xié)同起來識別抗原。正如在機(jī)體免疫中用B細(xì)胞識別抗原一樣，用B檢測器集來識別抗原，

18、因?yàn)锽檢測器所覆蓋的抗原空間更大。將外來抗原用和檢測器一樣的編碼方式表示，同樣運(yùn)用r一字符塊匹配規(guī)則，將它們和每一個B檢測器相比較，當(dāng)某個B檢測器與之匹配，此檢測器被激活，由B檢測器的生成過程可知，B檢測器可能和sel曬配，所以，為了降低偽肯定率(將seir當(dāng)作nonsel喲幾率)，需要T檢測器的協(xié)同刺激。此時，將那些由B檢測器識別到的抗原再和T檢測器相比較，如果能和T檢測器相匹配，說明該抗原是nonself，報警。反之，如果不能匹配，則報警等待系統(tǒng)相應(yīng)。另一方面，B檢測器作為T檢測器的前置過濾檢測器，提高了使用T檢測器單一檢測器的檢測速度。如圖4.6所示。第二十六張，PPT共三十七頁，創(chuàng)作于

19、2022年6月5.仿真實(shí)驗(yàn) 在前面章節(jié)理論分析的基礎(chǔ)上，首先對黑洞問題進(jìn)行了仿真實(shí)驗(yàn)來說明黑洞的存在及黑洞存在的數(shù)量和自體集S本身的相似度、匹配閡值:的大小有關(guān)。然后對模型采用改進(jìn)否定選擇算法生成B、T檢測器協(xié)同識別檢測的檢測率進(jìn)行仿真實(shí)驗(yàn)，并通過對實(shí)驗(yàn)結(jié)果的分析，來進(jìn)一步研究基于否定選擇算法的入侵檢測系統(tǒng)模型，從而驗(yàn)證該模型的檢測準(zhǔn)確性，實(shí)現(xiàn)較高的檢測率和低的誤報率。5.1黑洞仿真實(shí)驗(yàn) (l)采用r連續(xù)位匹配算法，在r，L固定情況下。假設(shè)在否定選擇算法中采用r連續(xù)位匹配算法，字符串長度為L，匹配閡值r固定，并設(shè)為L=10，r=5。自我集s1=0110100110;1000010000;101

20、0101010;1111011100通過仿真實(shí)驗(yàn)，計算出黑洞的數(shù)量為4個。如圖5.1所示。圖中橫坐標(biāo)為自我串的高五位10進(jìn)制數(shù)值，縱坐標(biāo)為自我串的低5位10進(jìn)制數(shù)值。圖中橫坐標(biāo)和縱坐標(biāo)交差點(diǎn)上的黑點(diǎn)代表檢測器覆蓋異己空間點(diǎn)。圖中空白點(diǎn)為self和漏洞點(diǎn)。第二十七張，PPT共三十七頁，創(chuàng)作于2022年6月5.1Self集相似度小情況下黑洞數(shù)量圖 當(dāng)自我集s2=0110100110;1011011000;0010010100;0100110011，通過仿真實(shí)驗(yàn)，計算出黑洞數(shù)量為2個。如圖5.2所示。圖中橫坐標(biāo)為自我串的高5位10進(jìn)制數(shù)值，縱坐標(biāo)為自我串的低5位10進(jìn)制數(shù)值。圖中橫坐標(biāo)和縱坐標(biāo)交差點(diǎn)

21、上的黑點(diǎn)代表檢測器覆蓋異己空間點(diǎn)。圖中空白點(diǎn)為self和漏洞點(diǎn)。第二十八張，PPT共三十七頁，創(chuàng)作于2022年6月圖5.2Self集較相似情況下黑洞數(shù)量圖 比較圖5.1和圖5.2可知，Self集本身越相似，黑洞數(shù)量越少。(2)假設(shè)在否定選擇算法中采用:連續(xù)位匹配算法，字符串長度為L，self集固定， 設(shè)為s=0110100110;1011011000;0010010100;0100110011，L=10。匹配閩值r可變。 當(dāng)r=7時，如圖5.2所示。 當(dāng)r=5時，如圖5.3所示。第二十九張，PPT共三十七頁，創(chuàng)作于2022年6月圖5.3 當(dāng)r=時的黑洞數(shù)量圖 比較圖5.2和圖5.3可知，匹配閉

22、值:越大，黑洞數(shù)量越少。第三十張，PPT共三十七頁，創(chuàng)作于2022年6月 5.2改進(jìn)算法仿真實(shí)驗(yàn) 要驗(yàn)證模型的檢測準(zhǔn)確性，主要著重驗(yàn)證該模型采用的改進(jìn)否定選擇算法生成的B、T雙檢測器的檢測率要比原算法生成的檢測器的檢測率在一定程度上有所提高。 由于入侵檢測是一個很復(fù)雜的問題，不僅涉及大量使用的通信協(xié)議，而且還涉及到許多操作系統(tǒng)，網(wǎng)絡(luò)服務(wù)、軟件漏洞等。另外，網(wǎng)絡(luò)中入侵或攻擊方式多種多樣，因此，我們不可能采用眾多的入侵或攻擊分別對模型的功能進(jìn)行實(shí)驗(yàn)驗(yàn)證，所以本次實(shí)驗(yàn)我們準(zhǔn)備構(gòu)造一個具有通用性的數(shù)據(jù)格式來表示網(wǎng)絡(luò)中的數(shù)據(jù)信息。如表5.1所示是TCP包和UDP包的預(yù)處理編碼規(guī)則，從中我們可以把它們具有的共同信息抽取出來作為此次實(shí)驗(yàn)的通用數(shù)據(jù)格式，如圖5.4所