基于并行計(jì)算的木馬免疫算法研究
加入技術(shù)交流群
如果采用完全匹配規(guī)則(r=L)，則當(dāng)且僅當(dāng)兩個(gè)隨機(jī)字符串相應(yīng)位置的每一位字符均相同時(shí)，則兩個(gè)字符串匹配，其匹配概率為PM=1／2L；如果采用部分匹配規(guī)則，即rL時(shí)，則匹配概率PM≈m-r[(l-r)(m-1)m+1]。當(dāng)在試驗(yàn)中字符串采用二進(jìn)制碼，即m=2時(shí)，匹配概率公式則變?yōu)镻M≈2-r[(l-r)／2+1]。
候選檢測器NH的數(shù)量將隨著“自我”集合中二進(jìn)制編碼長度的增加成指數(shù)級(jí)增長，經(jīng)陰性選擇的檢測器沒有經(jīng)過冗余檢查就直接將其作為成熟檢測器中的一個(gè)元素進(jìn)入下一個(gè)環(huán)節(jié)，這可能導(dǎo)致成熟檢測器集合R中的數(shù)據(jù)冗余。盡管在Forrest之后也提出了一些改進(jìn)方法，如線性算法、貪婪算法、二進(jìn)制模塊算法，但都沒有很好地解決上述問題。
2 陰性選擇算法的改進(jìn)
Forrest陰性選擇算法中步驟4隨機(jī)產(chǎn)生一個(gè)長度為L的字符串，并與自體進(jìn)行比較，一般是采用局部匹配的方式進(jìn)行比較，也就是采用r連續(xù)位匹配的方式；如果匹配位數(shù)r太小，在“自我”和“非我”相似度較大時(shí)，檢測器會(huì)把“非我”當(dāng)成“自我”而刪除；但是隨著r的增加和字符串L的增加，匹配次數(shù)呈指數(shù)形式增加，匹配效率明顯不足，并且會(huì)產(chǎn)生大量的候選檢測器，使得該算法時(shí)間復(fù)雜度太大，因此，在實(shí)際應(yīng)用中就存在一個(gè)如何選擇字串長度和匹配區(qū)域的問題。
文中提出一種基于并行計(jì)算的多特征區(qū)域匹配方式，產(chǎn)生檢測器和自體進(jìn)行匹配，然后對(duì)于冗余的候選檢測器進(jìn)行篩選，最后產(chǎn)生成熟檢測器。
該算法步驟如下：
1)把總長度為L的字符串分成n個(gè)特征區(qū)域，每個(gè)特征區(qū)域長度記為Li(i=1，2，3…，n)；
2)每一段特征區(qū)域產(chǎn)生一系列相應(yīng)的檢測器子集合Ni(i=1，2，3…，n)，用這個(gè)檢測器子集合對(duì)相應(yīng)的特征區(qū)域進(jìn)行特征匹配，各個(gè)特征區(qū)域的檢測器集合是相互獨(dú)立的，整個(gè)字符串的檢測器集合N={N1，N2，N3…，Nn}；
3)對(duì)于每一個(gè)特征區(qū)域，采用并行計(jì)算的匹配方式，采用多指令流多數(shù)據(jù)流(MIMD)的體系結(jié)構(gòu)。把自體串和特征區(qū)域放人兩個(gè)數(shù)組中進(jìn)行比較，通過n個(gè)處理器并行計(jì)算；
4)根據(jù)檢測器子集合對(duì)每一個(gè)特征區(qū)域進(jìn)行檢測，得到它的匹配長度ri，設(shè)定每個(gè)特征區(qū)域的重要性權(quán)值Ii，有0≤ri≤li，0≤Ii≤1；
5)設(shè)定Mi表示特征區(qū)域的匹配情況，Mi=1表示該特征區(qū)域匹配，Mi=0表示不匹配，對(duì)于由各個(gè)特征區(qū)域組成的整體字符串，采用r連續(xù)位匹配規(guī)則進(jìn)行匹配，得到它的匹配度R；6)設(shè)定匹配閾值μ，如果公式(1)成立，則兩個(gè)字符串匹配，否則不匹配。
對(duì)于r連續(xù)位匹配算法，影響算法的主要因素是樣本個(gè)數(shù)、字符串長度和連續(xù)位數(shù)。運(yùn)用以往的r連續(xù)位算法，要至少遍歷兩個(gè)字符串的對(duì)應(yīng)位置，但是如果采用并行算法，最佳效果是僅匹配一次即可成功，這將大大減少計(jì)算量，并增加運(yùn)行效率。對(duì)于木馬檢測這種對(duì)實(shí)時(shí)反應(yīng)時(shí)間要求較高的匹配模式來說，運(yùn)用并行算法能較好地提高檢測成功率和減少誤報(bào)率；本算法采用了特征區(qū)域生成的辦法產(chǎn)生檢測器集合，以避免由于匹配區(qū)域r增大所帶來的效率過低的問題，改進(jìn)算法能較快速高效地產(chǎn)生滿足精度要求的檢測器集合。
但是對(duì)于各個(gè)特征區(qū)域，該算法都要產(chǎn)生一系列對(duì)應(yīng)的檢測器子集合，各個(gè)特征區(qū)域的檢測器集合是獨(dú)立的，因此區(qū)域與區(qū)域之間的檢測器有可能會(huì)重復(fù)，從而產(chǎn)生檢測器冗余。針對(duì)這個(gè)問題，文中加入了冗余檢測器篩選步驟，對(duì)經(jīng)過改進(jìn)的陰性選擇算法后產(chǎn)生的候選檢測器進(jìn)行篩選，把它們和已經(jīng)存在的成熟檢測器進(jìn)行比對(duì)，判斷該候選檢測器是否重復(fù)，如果是重復(fù)的則刪除該檢測器，否則把它加入到成熟檢測器集合中。
評(píng)論