基于并行計(jì)算的木馬免疫算法研究

摘要：傳統(tǒng)的木馬檢測(cè)技術(shù)在檢測(cè)正確率、誤報(bào)率和漏報(bào)率上都有不足，針時(shí)傳統(tǒng)陰性選擇算法在檢測(cè)效率上的不足，提出一種基于并行計(jì)算的多特征區(qū)域匹配算法。這個(gè)算法首先把隨機(jī)字符串分為多個(gè)特征區(qū)域，每個(gè)特征區(qū)域內(nèi)對(duì)應(yīng)一個(gè)檢測(cè)器集合進(jìn)行匹配，而且特征區(qū)域之間采用r連續(xù)位匹配方式再次匹配，同時(shí)采用并行計(jì)算，設(shè)置匹配閾值進(jìn)行匹配確認(rèn)。實(shí)驗(yàn)證明改進(jìn)的陰性選擇算法在匹配位數(shù)和隨機(jī)字符串位數(shù)增加時(shí)，候選檢測(cè)器增加速度較平緩，系統(tǒng)負(fù)擔(dān)增加較緩慢，因此具有較好的檢測(cè)效率。
關(guān)鍵詞：并行計(jì)算；木馬檢測(cè)；免疫；算法

免疫算法是借鑒生物免疫系統(tǒng)中抗體識(shí)別抗原的原理發(fā)展起來(lái)的，是人工智能的一個(gè)新的研究領(lǐng)域，也是目前國(guó)內(nèi)外研究的一大熱點(diǎn)，許多研究學(xué)者都針對(duì)這一領(lǐng)域開(kāi)展了深入、富有成效的研究工作。免疫算法主要模擬生物免疫系統(tǒng)中抗原處理的核心原理，運(yùn)用免疫算法求解問(wèn)題，本質(zhì)上是抗體識(shí)別抗原的過(guò)程，而抗體(檢測(cè)器)的產(chǎn)生是非常關(guān)鍵的一個(gè)步驟，關(guān)系到整個(gè)免疫檢測(cè)系統(tǒng)的運(yùn)行效率。
常見(jiàn)免疫算法主要有陰性選擇算法和克隆選擇算法等。陰性選擇算法由Forrest等人在1994年提出，該算法步驟簡(jiǎn)單，但卻實(shí)用有效，陰性選擇算法以r連續(xù)位匹配規(guī)則為基礎(chǔ)，實(shí)現(xiàn)局部匹配，算法效率較高。但其也存在著致命缺陷，因?yàn)楫?dāng)檢測(cè)字符長(zhǎng)度增加或者匹配位數(shù)r增加時(shí)，檢測(cè)效率大大降低，系統(tǒng)開(kāi)銷大大增加。
文中提出一種改進(jìn)的陰性選擇算法，把總長(zhǎng)度為L(zhǎng)的字符串分成n個(gè)特征區(qū)域時(shí)，每一段特征區(qū)域產(chǎn)生一系列相應(yīng)的檢測(cè)器子集合，然后采用并行計(jì)算的匹配方式，對(duì)于整體則采用r連續(xù)位匹配規(guī)則進(jìn)行匹配。設(shè)定匹配閾值，如果匹配度高于該閾值則兩個(gè)字符串匹配，否則不匹配。

1 陰性選擇算法
在免疫系統(tǒng)中，按照機(jī)體內(nèi)外可以把整個(gè)機(jī)體分為“自我”和“非我”。將所要維護(hù)的正常模式行為或者系統(tǒng)的靜態(tài)行為定義成“自我”，將異常行為模式定義為“非我”。陰性選擇算法是個(gè)否定選擇過(guò)程，目的在于區(qū)分“自我”和“非我”。設(shè)免疫系統(tǒng)整個(gè)空間為U，“自我”為S，“非我”為N，它們滿足關(guān)系式：U=S∪N，S∩N=φ。陰性選擇算法以r連續(xù)位匹配規(guī)則為基礎(chǔ)，r代表一個(gè)閾值，是衡量單個(gè)檢測(cè)器能匹配字符串子集大小的指標(biāo)。
圖1給出了采用陰性選擇算法產(chǎn)生檢測(cè)器的流程。

Forrest陰性選擇免疫算法簡(jiǎn)述如下：1)分析問(wèn)題，根據(jù)實(shí)際問(wèn)題確定參數(shù)PM、NS、Pf、r，其中PM為匹配概率，NS為自體個(gè)數(shù)，Pf為期望的檢測(cè)失敗率，r為閾值；2)隨機(jī)產(chǎn)生NS個(gè)長(zhǎng)度為L(zhǎng)的二進(jìn)制字符串作為自體；3)計(jì)算所需檢測(cè)器個(gè)數(shù)NR與候選檢測(cè)器個(gè)數(shù)NH；4)產(chǎn)生檢測(cè)器，即隨機(jī)產(chǎn)生一個(gè)長(zhǎng)度為L(zhǎng)的字符串，并與自體進(jìn)行比較，如果隨機(jī)產(chǎn)生的字符串與自體中任何一個(gè)字符串匹配，則丟棄該字符串；如果隨機(jī)產(chǎn)生的字符串與自體中所有字符串都不匹配，則保留該字符串作為檢測(cè)器。重復(fù)該過(guò)程直到得到NR個(gè)檢測(cè)器。其重復(fù)次數(shù)即為候選檢測(cè)器個(gè)數(shù)NH；5)驗(yàn)證檢測(cè)效果，即改變自體中的某個(gè)字符串，并用所有檢測(cè)器與自體進(jìn)行逐個(gè)比較，若出現(xiàn)匹配則表明檢測(cè)成功否則檢測(cè)失敗。

由表1可知，匹配概率PM、檢測(cè)失敗率Pf對(duì)系統(tǒng)整體性能有很大影響。設(shè)定檢測(cè)失敗率只和自體規(guī)模NS在一定范圍內(nèi)的時(shí)候，決定候選檢測(cè)器規(guī)模NH和檢測(cè)器規(guī)模NR的只有匹配概率PM。當(dāng)PM增大，NH和NR呈指數(shù)形式增加，這將導(dǎo)致檢測(cè)時(shí)間大幅增加。而NH決定著系統(tǒng)的整體運(yùn)行時(shí)間，NR決定著系統(tǒng)所占用的空間，因此PM的選擇范圍對(duì)整個(gè)系統(tǒng)性能起著決定性作用。傳統(tǒng)陰性選擇算法采用隨機(jī)生成字符串的形式，匹配概率PM的值就由兩個(gè)字符串間的匹配規(guī)則、匹配位數(shù)來(lái)決定。