摘要：傳統(tǒng)的木馬檢測技術(shù)在檢測正確率、誤報率和漏報率上都有不足，針時傳統(tǒng)陰性選擇算法在檢測效率上的不足，提出一種基于并行計算的多特征區(qū)域匹配算法。這個算法首先把隨機字符串分為多個特征區(qū)域，每個特征區(qū)域內(nèi)對應(yīng)一個檢測器集合進(jìn)行匹配，而且特征區(qū)域之間采用r連續(xù)位匹配方式再次匹配，同時采用并行計算，設(shè)置匹配閾值進(jìn)行匹配確認(rèn)。實驗證明改進(jìn)的陰性選擇算法在匹配位數(shù)和隨機字符串位數(shù)增加時，候選檢測器增加速度較平緩，系統(tǒng)負(fù)擔(dān)增加較緩慢，因此具有較好的檢測效率。
關(guān)鍵詞：并行計算；木馬檢測；免疫；算法
免疫算法是借鑒生物免疫系統(tǒng)中抗體識別抗原的原理發(fā)展起來的，是人工智能的一個新的研究領(lǐng)域，也是目前國內(nèi)外研究的一大熱點，許多研究學(xué)者都針對這一領(lǐng)域開展了深入、富有成效的研究工作。免疫算法主要模擬生物免疫系統(tǒng)中抗原處理的核心原理，運用免疫算法求解問題，本質(zhì)上是抗體識別抗原的過程，而抗體(檢測器)的產(chǎn)生是非常關(guān)鍵的一個步驟，關(guān)系到整個免疫檢測系統(tǒng)的運行效率。
常見免疫算法主要有陰性選擇算法和克隆選擇算法等。陰性選擇算法由Forrest等人在1994年提出，該算法步驟簡單，但卻實用有效，陰性選擇算法以r連續(xù)位匹配規(guī)則為基礎(chǔ)，實現(xiàn)局部匹配，算法效率較高。但其也存在著致命缺陷，因為當(dāng)檢測字符長度增加或者匹配位數(shù)r增加時，檢測效率大大降低，系統(tǒng)開銷大大增加。
文中提出一種改進(jìn)的陰性選擇算法，把總長度為L的字符串分成n個特征區(qū)域時，每一段特征區(qū)域產(chǎn)生一系列相應(yīng)的檢測器子集合，然后采用并行計算的匹配方式，對于整體則采用r連續(xù)位匹配規(guī)則進(jìn)行匹配。設(shè)定匹配閾值，如果匹配度高于該閾值則兩個字符串匹配，否則不匹配。
1 陰性選擇算法
在免疫系統(tǒng)中，按照機體內(nèi)外可以把整個機體分為“自我”和“非我”。將所要維護(hù)的正常模式行為或者系統(tǒng)的靜態(tài)行為定義成“自我”，將異常行為模式定義為“非我”。陰性選擇算法是個否定選擇過程，目的在于區(qū)分“自我”和“非我”。設(shè)免疫系統(tǒng)整個空間為U，“自我”為S，“非我”為N，它們滿足關(guān)系式：U=S∪N，S∩N=φ。陰性選擇算法以r連續(xù)位匹配規(guī)則為基礎(chǔ)，r代表一個閾值，是衡量單個檢測器能匹配字符串子集大小的指標(biāo)。
圖1給出了采用陰性選擇算法產(chǎn)生檢測器的流程。
Forrest陰性選擇免疫算法簡述如下：1)分析問題，根據(jù)實際問題確定參數(shù)PM、NS、Pf、r，其中PM為匹配概率，NS為自體個數(shù)，Pf為期望的檢測失敗率，r為閾值；2)隨機產(chǎn)生NS個長度為L的二進(jìn)制字符串作為自體；3)計算所需檢測器個數(shù)NR與候選檢測器個數(shù)NH；4)產(chǎn)生檢測器，即隨機產(chǎn)生一個長度為L的字符串，并與自體進(jìn)行比較，如果隨機產(chǎn)生的字符串與自體中任何一個字符串匹配，則丟棄該字符串；如果隨機產(chǎn)生的字符串與自體中所有字符串都不匹配，則保留該字符串作為檢測器。重復(fù)該過程直到得到NR個檢測器。其重復(fù)次數(shù)即為候選檢測器個數(shù)NH；5)驗證檢測效果，即改變自體中的某個字符串，并用所有檢測器與自體進(jìn)行逐個比較，若出現(xiàn)匹配則表明檢測成功否則檢測失敗。
由表1可知，匹配概率PM、檢測失敗率Pf對系統(tǒng)整體性能有很大影響。設(shè)定檢測失敗率只和自體規(guī)模NS在一定范圍內(nèi)的時候，決定候選檢測器規(guī)模NH和檢測器規(guī)模NR的只有匹配概率PM。當(dāng)PM增大，NH和NR呈指數(shù)形式增加，這將導(dǎo)致檢測時間大幅增加。而NH決定著系統(tǒng)的整體運行時間，NR決定著系統(tǒng)所占用的空間，因此PM的選擇范圍對整個系統(tǒng)性能起著決定性作用。傳統(tǒng)陰性選擇算法采用隨機生成字符串的形式，匹配概率PM的值就由兩個字符串間的匹配規(guī)則、匹配位數(shù)來決定。
如果采用完全匹配規(guī)則(r=L)，則當(dāng)且僅當(dāng)兩個隨機字符串相應(yīng)位置的每一位字符均相同時，則兩個字符串匹配，其匹配概率為PM=1／2L；如果采用部分匹配規(guī)則，即r<L時，則匹配概率PM≈m-r[(l-r)(m-1)m+1]。當(dāng)在試驗中字符串采用二進(jìn)制碼，即m=2時，匹配概率公式則變?yōu)镻M≈2-r[(l-r)／2+1]。
候選檢測器NH的數(shù)量將隨著“自我”集合中二進(jìn)制編碼長度的增加成指數(shù)級增長，經(jīng)陰性選擇的檢測器沒有經(jīng)過冗余檢查就直接將其作為成熟檢測器中的一個元素進(jìn)入下一個環(huán)節(jié)，這可能導(dǎo)致成熟檢測器集合R中的數(shù)據(jù)冗余。盡管在Forrest之后也提出了一些改進(jìn)方法，如線性算法、貪婪算法、二進(jìn)制模塊算法，但都沒有很好地解決上述問題。
2 陰性選擇算法的改進(jìn)
Forrest陰性選擇算法中步驟4隨機產(chǎn)生一個長度為L的字符串，并與自體進(jìn)行比較，一般是采用局部匹配的方式進(jìn)行比較，也就是采用r連續(xù)位匹配的方式；如果匹配位數(shù)r太小，在“自我”和“非我”相似度較大時，檢測器會把“非我”當(dāng)成“自我”而刪除；但是隨著r的增加和字符串L的增加，匹配次數(shù)呈指數(shù)形式增加，匹配效率明顯不足，并且會產(chǎn)生大量的候選檢測器，使得該算法時間復(fù)雜度太大，因此，在實際應(yīng)用中就存在一個如何選擇字串長度和匹配區(qū)域的問題。
文中提出一種基于并行計算的多特征區(qū)域匹配方式，產(chǎn)生檢測器和自體進(jìn)行匹配，然后對于冗余的候選檢測器進(jìn)行篩選，最后產(chǎn)生成熟檢測器。
該算法步驟如下：
1)把總長度為L的字符串分成n個特征區(qū)域，每個特征區(qū)域長度記為Li(i=1，2，3…，n)；
2)每一段特征區(qū)域產(chǎn)生一系列相應(yīng)的檢測器子集合Ni(i=1，2，3…，n)，用這個檢測器子集合對相應(yīng)的特征區(qū)域進(jìn)行特征匹配，各個特征區(qū)域的檢測器集合是相互獨立的，整個字符串的檢測器集合N={N1，N2，N3…，Nn}；
3)對于每一個特征區(qū)域，采用并行計算的匹配方式，采用多指令流多數(shù)據(jù)流(MIMD)的體系結(jié)構(gòu)。把自體串和特征區(qū)域放人兩個數(shù)組中進(jìn)行比較，通過n個處理器并行計算；
4)根據(jù)檢測器子集合對每一個特征區(qū)域進(jìn)行檢測，得到它的匹配長度ri，設(shè)定每個特征區(qū)域的重要性權(quán)值Ii，有0≤ri≤li，0≤Ii≤1；
5)設(shè)定Mi表示特征區(qū)域的匹配情況，Mi=1表示該特征區(qū)域匹配，Mi=0表示不匹配，對于由各個特征區(qū)域組成的整體字符串，采用r連續(xù)位匹配規(guī)則進(jìn)行匹配，得到它的匹配度R；6)設(shè)定匹配閾值μ，如果公式(1)成立，則兩個字符串匹配，否則不匹配。
對于r連續(xù)位匹配算法，影響算法的主要因素是樣本個數(shù)、字符串長度和連續(xù)位數(shù)。運用以往的r連續(xù)位算法，要至少遍歷兩個字符串的對應(yīng)位置，但是如果采用并行算法，最佳效果是僅匹配一次即可成功，這將大大減少計算量，并增加運行效率。對于木馬檢測這種對實時反應(yīng)時間要求較高的匹配模式來說，運用并行算法能較好地提高檢測成功率和減少誤報率；本算法采用了特征區(qū)域生成的辦法產(chǎn)生檢測器集合，以避免由于匹配區(qū)域r增大所帶來的效率過低的問題，改進(jìn)算法能較快速高效地產(chǎn)生滿足精度要求的檢測器集合。
但是對于各個特征區(qū)域，該算法都要產(chǎn)生一系列對應(yīng)的檢測器子集合，各個特征區(qū)域的檢測器集合是獨立的，因此區(qū)域與區(qū)域之間的檢測器有可能會重復(fù)，從而產(chǎn)生檢測器冗余。針對這個問題，文中加入了冗余檢測器篩選步驟，對經(jīng)過改進(jìn)的陰性選擇算法后產(chǎn)生的候選檢測器進(jìn)行篩選，把它們和已經(jīng)存在的成熟檢測器進(jìn)行比對，判斷該候選檢測器是否重復(fù)，如果是重復(fù)的則刪除該檢測器，否則把它加入到成熟檢測器集合中。
實驗1：設(shè)定其他的參數(shù)不變，在不同的自體規(guī)模(即Ns)下進(jìn)行實驗，仿真結(jié)果如表2所示。
由表2可以看出，當(dāng)自體規(guī)模從8增加到136的時候，傳統(tǒng)算法產(chǎn)生的候選檢測器數(shù)量大大增加，從207個增加到了4 015個，增加了18倍。而檢測失敗率也從0．015％增加到了0．148％，增加了將近9倍；而用本文改進(jìn)的算法所產(chǎn)生的候選檢測器數(shù)量只從234個增加到3 847個，增加了15倍，而失敗率反而從0．058％降低到了0．047％，檢測失敗率下降了17％；雖然在自體規(guī)模只有8個的時候，改進(jìn)算法產(chǎn)生了234個候選檢測器，多于傳統(tǒng)算法，這是因為改進(jìn)算法較復(fù)雜，可能會增加冗余的檢測器，但是隨著自體規(guī)模的增加，候選檢測器的數(shù)量能保持較少的增長率，說明改進(jìn)算法的收斂性較小，收斂效果較好，而且也提高了檢測成功率。
實驗2：設(shè)定隨機字符串長度L和自體規(guī)模Ns不變，改變匹配位數(shù)r的長度，對比兩種算法產(chǎn)生的候選檢測器數(shù)目NH和檢測時間t，結(jié)果如表3所示。
由表3可以看出，在字符串L位數(shù)和自體規(guī)模Ns不變的情況下，當(dāng)匹配位數(shù)r增加，傳統(tǒng)算法所產(chǎn)生的候選檢測器數(shù)目大大增加，增加了將近18倍，檢測時間增加了18倍，效率明顯降低；采用文中的多屬性特征區(qū)域匹配方式，候選檢測器集合數(shù)目增加了只有11倍，并且改進(jìn)算法引入了并行計算的方式，檢測時間增加了14倍，而且低于傳統(tǒng)算法的檢測時間。從這里可以看出，新算法在匹配位數(shù)r增加的情況下，系統(tǒng)效率影響較小，能有效改善系統(tǒng)性能。
3 結(jié)束語
陰性選擇算法隨著匹配位數(shù)r的增加和字符串L的增加，匹配次數(shù)呈指數(shù)形式增加，匹配效率明顯不足，并且會產(chǎn)生大量的候選檢測器，使得該算法時間復(fù)雜度太大，論文提出一種改進(jìn)的陰性選擇算法，把字符串分為多個特征區(qū)域，每個特征區(qū)域之間采用r連續(xù)位匹配方式再次匹配，同時采用并行計算，實驗結(jié)果表明改進(jìn)的陰性選擇算法在匹配位數(shù)和隨機字符串位數(shù)增加時，候選檢測器增加速度較平緩，系統(tǒng)負(fù)擔(dān)增加較緩慢，因此具有較好的檢測效率。
下載文檔
