基于并行計算的木馬免疫算法研究

王應戰，魏衍君

（商丘職業技術學院 計算機系，河南 商丘 476000）

免疫算法是借鑒生物免疫系統中抗體識別抗原的原理發展起來的，是人工智能的一個新的研究領域，也是目前國內外研究的一大熱點，許多研究學者都針對這一領域開展了深入、富有成效的研究工作。免疫算法主要模擬生物免疫系統中抗原處理的核心原理，運用免疫算法求解問題，本質上是抗體識別抗原的過程，而抗體（檢測器）的產生是非常關鍵的一個步驟，關系到整個免疫檢測系統的運行效率[1-2]。

常見免疫算法主要有陰性選擇算法和克隆選擇算法等。陰性選擇算法由Forrest等人在1994年提出[3-4]，該算法步驟簡單，但卻實用有效，陰性選擇算法以r連續位匹配規則為基礎，實現局部匹配，算法效率較高。但其也存在著致命缺陷，因為當檢測字符長度增加或者匹配位數r增加時，檢測效率大大降低，系統開銷大大增加[5]。

文中提出一種改進的陰性選擇算法，把總長度為L的字符串分成n個特征區域時，每一段特征區域產生一系列相應的檢測器子集合，然后采用并行計算的匹配方式，對于整體則采用r連續位匹配規則進行匹配。設定匹配閾值，如果匹配度高于該閾值則兩個字符串匹配，否則不匹配。

1 陰性選擇算法

在免疫系統中，按照機體內外可以把整個機體分為“自我”和“非我”。將所要維護的正常模式行為或者系統的靜態行為定義成“自我”，將異常行為模式定義為“非我”。陰性選擇算法是個否定選擇過程，目的在于區分“自我”和“非我”。設免疫系統整個空間為 U，“自我”為 S，“非我”為N，它們滿足關系式：U=S∪N，S∩N=?。陰性選擇算法以r連續位匹配規則為基礎，r代表一個閾值，是衡量單個檢測器能匹配字符串子集大小的指標[6]。

圖1給出了采用陰性選擇算法產生檢測器的流程。

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

圖1 檢測器生成過程Fig．1 Detector generation process

表1 陰性選擇算法中主要參數Tab.1 Negativeselection algorithm m ain param eters in the form ula

由表1可知，匹配概率PM、檢測失敗率Pf對系統整體性能有很大影響。設定檢測失敗率Pf和自體規模NS在一定范圍內的時候，決定候選檢測器規模NH和檢測器規模NR的只有匹配概率PM。當PM增大，NH和NR呈指數形式增加，這將導致檢測時間大幅增加。而NH決定著系統的整體運行時間，NR決定著系統所占用的空間，因此PM的選擇范圍對整個系統性能起著決定性作用。傳統陰性選擇算法采用隨機生成字符串的形式，匹配概率PM的值就由兩個字符串間的匹配規則、匹配位數來決定[7]。

如果采用完全匹配規則（r=L），則當且僅當兩個隨機字符串相應位置的每一位字符均相同時，則兩個字符串匹配，其匹配概率為PM=1/2L；如果采用部分匹配規則，即r＜L時，則匹配概率 PM≈m-r[（l-r）（m-1）/m+1]。 當在試驗中字符串采用二進制碼，即 m=2 時，匹配概率公式則變為 PM≈2-r[（l-r）/2+1]。

候選檢測器NH的數量將隨著“自我”集合中二進制編碼長度的增加成指數級增長，經陰性選擇的檢測器沒有經過冗余檢查就直接將其作為成熟檢測器中的一個元素進入下一個環節，這可能導致成熟檢測器集合R中的數據冗余。盡管在Forrest之后也提出了一些改進方法，如線性算法、貪婪算法、二進制模塊算法，但都沒有很好地解決上述問題。

2 陰性選擇算法的改進

Forrest陰性選擇算法中步驟4隨機產生一個長度為L的字符串，并與自體進行比較，一般是采用局部匹配的方式進行比較，也就是采用r連續位匹配的方式；如果匹配位數r太小，在“自我”和“非我”相似度較大時，檢測器會把“非我”當成“自我”而刪除；但是隨著r的增加和字符串L的增加，匹配次數呈指數形式增加，匹配效率明顯不足，并且會產生大量的候選檢測器，使得該算法時間復雜度太大，因此，在實際應用中就存在一個如何選擇字串長度和匹配區域的問題[8]。

文中提出一種基于并行計算的多特征區域匹配方式，產生檢測器和自體進行匹配，然后對于冗余的候選檢測器進行篩選，最后產生成熟檢測器。

該算法步驟如下：

1）把總長度為L的字符串分成n個特征區域，每個特征區域長度記為 Li（i=1，2，3…，n）；

2）每一段特征區域產生一系列相應的檢測器子集合Ni（i=1，2，3…，n），用這個檢測器子集合對相應的特征區域進行特征匹配，各個特征區域的檢測器集合是相互獨立的，整個字符串的檢測器集合 N={N1，N2，N3…，Nn}；

3）對于每一個特征區域，采用并行計算的匹配方式，采用多指令流多數據流（MIMD）的體系結構。把自體串和特征區域放入兩個數組中進行比較，通過n個處理器并行計算；

4）根據檢測器子集合對每一個特征區域進行檢測，得到它的匹配長度ri，設定每個特征區域的重要性權值Ii，有0≤ri≤li，0≤Ii≤1；

5）設定Mi表示特征區域的匹配情況，Mi=1表示該特征區域匹配，Mi=0表示不匹配，對于由各個特征區域組成的整體字符串，采用r連續位匹配規則進行匹配，得到它的匹配度R；

6）設定匹配閾值μ，如果公式（1）成立，則兩個字符串匹配，否則不匹配。

對于r連續位匹配算法，影響算法的主要因素是樣本個數、字符串長度和連續位數。運用以往的r連續位算法，要至少遍歷兩個字符串的對應位置，但是如果采用并行算法，最佳效果是僅匹配一次即可成功，這將大大減少計算量，并增加運行效率。對于木馬檢測這種對實時反應時間要求較高的匹配模式來說，運用并行算法能較好地提高檢測成功率和減少誤報率；本算法采用了特征區域生成的辦法產生檢測器集合，以避免由于匹配區域r增大所帶來的效率過低的問題，改進算法能較快速高效地產生滿足精度要求的檢測器集合。

但是對于各個特征區域，該算法都要產生一系列對應的檢測器子集合，各個特征區域的檢測器集合是獨立的，因此區域與區域之間的檢測器有可能會重復，從而產生檢測器冗余。針對這個問題，文中加入了冗余檢測器篩選步驟，對經過改進的陰性選擇算法后產生的候選檢測器進行篩選，把它們和已經存在的成熟檢測器進行比對，判斷該候選檢測器是否重復，如果是重復的則刪除該檢測器，否則把它加入到成熟檢測器集合中。

實驗1：設定其他的參數不變，在不同的自體規模（即Ns）下進行實驗，仿真結果如表2所示。

表2 兩種不同算法的比較Tab.2 Two different algorithm s for comparison

由表2可以看出，當自體規模從8增加到136的時候，傳統算法產生的候選檢測器數量大大增加，從207個增加到了4 015個，增加了18倍。而檢測失敗率也從0．015%增加到了0．148%，增加了將近9倍；而用本文改進的算法所產生的候選檢測器數量只從234個增加到3 847個，增加了15倍，而失敗率反而從0．058%降低到了0．047%，檢測失敗率下降了17%；雖然在自體規模只有8個的時候，改進算法產生了234個候選檢測器，多于傳統算法，這是因為改進算法較復雜，可能會增加冗余的檢測器，但是隨著自體規模的增加，候選檢測器的數量能保持較少的增長率，說明改進算法的收斂性較小，收斂效果較好，而且也提高了檢測成功率。

實驗2：設定隨機字符串長度L和自體規模Ns不變，改變匹配位數r的長度，對比兩種算法產生的候選檢測器數目NH和檢測時間t，結果如表3所示。

表3 兩種算法的檢測時間對比Tab.3 Two algorithm testing tim e contrast

由表3可以看出，在字符串L位數和自體規模NS不變的情況下，當匹配位數r增加，傳統算法所產生的候選檢測器數目大大增加，增加了將近18倍，檢測時間增加了18倍，效率明顯降低；采用文中的多屬性特征區域匹配方式，候選檢測器集合數目增加了只有11倍，并且改進算法引入了并行計算的方式，檢測時間增加了14倍，而且低于傳統算法的檢測時間。從這里可以看出，新算法在匹配位數r增加的情況下，系統效率影響較小，能有效改善系統性能。

3 結束語

陰性選擇算法隨著匹配位數r的增加和字符串L的增加，匹配次數呈指數形式增加，匹配效率明顯不足，并且會產生大量的候選檢測器，使得該算法時間復雜度太大，論文提出一種改進的陰性選擇算法，把字符串分為多個特征區域，每個特征區域之間采用r連續位匹配方式再次匹配，同時采用并行計算，實驗結果表明改進的陰性選擇算法在匹配位數和隨機字符串位數增加時，候選檢測器增加速度較平緩，系統負擔增加較緩慢，因此具有較好的檢測效率。

[1]劉念，劉孫俊，劉勇，等．一種基于免疫的網絡安全態勢感知方法[J]．計算機科學，2010（1）：126-129．

LIU Nian，LIU Sun-jun，LIU Yong，et al．A network security situation awarenessmethod based on immune[J]．Computer Science，2010（1）：126-129．

[2]關潮輝，薛琴．木馬的攻擊與防范技術研究[J]．信息網絡安全，2010（12）：20-21．

GUAN Chao-hui，XUEQin．Trojan attacks and guard against technology research[J]．Information Network Security，2010（12）：20-21．

[3]陳雷霆，張亮．人工免疫機制在木馬檢測系統中的應用研究[J]．電子科技大學學報，2005（2）：221-224．

CHEN Lei-ting，ZHANG Liang．Research of trojan detection system based on artificial immune[J]．Journal of University of Electronic Science and Technology of China，2005 （2）：221-224．

[4]張紅梅，范明鈺．人工免疫在未知木馬檢測中的應用研究[J]．計算機應用研究，2009，26（10）：3894-3897．

ZHANG Hong-mei，FAN Ming-yu．Research of unknown trojan detection based on artificial immune[J]．Application Research of Computer，2009，26（10）：3894-3897．

[5]Aickelin U，Green S J，Twycross J．Immune system approaches to intrusion detection-a review[C]//Catania， Italy：Proceedings International Conference on Artificial Immune System，2004．316-329．

[6]HE Shen，LUOWen-jian，WANG Xu-fa．A negative selection algorithm with the variable length detector[J]．Journal of Software，2007，18（6）：1361-1368．

[7]ZHANG Heng，WU Li-fa．An algorithm of radjustable negative selection algorithm and its simulation analysis[J]．Chinese Journal of Computers，2005，28（10）：1614-1618．