人工免疫系統(tǒng)及其在計算機(jī)病毒特征提取中的應(yīng)用

1、人工免疫系統(tǒng)及其在計算機(jī)病毒特征提取中的應(yīng)用黃宏偉 （100320）摘要：本報告在相關(guān)參考文獻(xiàn)的支持下得到。對于計算機(jī)病毒問題的日益重視，相關(guān)的病毒特征提取算法也一直在快速發(fā)展。受自然免疫系統(tǒng)的啟發(fā)，人工免疫系統(tǒng)也逐漸被關(guān)注并得以應(yīng)用。這樣得到一種基于人工免疫的利用計算機(jī)病毒代碼相關(guān)性的計算機(jī)病毒特征提取方法。根據(jù)文獻(xiàn)，這種特征提取方法在底層提取出與病毒相關(guān)的字節(jié)模式，在相對更高的層面上記錄這些字節(jié)模式之間的共同作用信息，之后利用陰性選擇算法提取出計算機(jī)病毒檢測基因庫，實(shí)現(xiàn)了對訓(xùn)練集上合法程序的完美記憶，從而保證了該文方法的誤判率處于極低的水平。關(guān)鍵字：計算機(jī)病毒；人工免疫；陰性選擇；特征匹配

2、；代碼相關(guān)性1 引言在自然界，生物體得以在各種病毒與細(xì)菌之間安全地生存，得益于生物體自身的免疫系統(tǒng)，有效地保護(hù)生物體不受各種有害病毒的傷害。自然免疫系統(tǒng)可以識別身體內(nèi)部異己的成分，并將這些對自身有害的部分消滅清除。計算機(jī)病毒是隱藏在計算機(jī)軟件中間的一些程序代碼。計算機(jī)學(xué)界的科學(xué)家們通過對自然免疫系統(tǒng)的模擬，建立了人工免疫系統(tǒng)模型，可以有效的將計算機(jī)軟件中的“異己”成分識別出來，從而使得計算機(jī)能夠處在一種類似“自我保護(hù)”的狀態(tài)中。本報告根據(jù)相關(guān)的文獻(xiàn)，對計算機(jī)病毒4、人工免疫系統(tǒng)2（其中的陰性選擇算法23）等做出介紹，重點(diǎn)講述一種基于人工免疫和代碼相關(guān)性的計算機(jī)病毒特征提取方法1。2 計算機(jī)病毒

3、計算機(jī)病毒(Computer Virus)在中華人民共和國計算機(jī)信息系統(tǒng)安全保護(hù)條例4中被明確定義，病毒指“編制者在計算機(jī)程序中插入的破壞計算機(jī)功能或者破壞數(shù)據(jù)，影響計算機(jī)使用并且能夠自我復(fù)制的一組計算機(jī)指令或者程序代碼”。而在一般教科書及通用資料中被定義為：利用計算機(jī)軟件與硬件的缺陷，由被感染機(jī)的內(nèi)部發(fā)出的破壞計算機(jī)數(shù)據(jù)并影響計算機(jī)正常工作的一組指令集或程序代碼。計算機(jī)病毒具有的幾個特點(diǎn)：寄生性；傳染性；潛伏性；隱蔽性；破壞性；可觸發(fā)性。由于這些特點(diǎn)，計算機(jī)病毒往往會造成計算機(jī)資源的損失和破壞。這不但會造成資源和財富的巨大浪費(fèi)，而且有可能造成社會性的災(zāi)難，隨著信息化社會的發(fā)展，計算機(jī)病毒的威

4、脅日益嚴(yán)重，反病毒的任務(wù)也更加艱巨了。計算機(jī)病毒具有很強(qiáng)的隱蔽性，時隱時現(xiàn)、變化無常，這類病毒處理起來通常很困難。而免疫系統(tǒng)具有天然的病毒處理能力，故而人們想到采用人工免疫系統(tǒng)來提取計算機(jī)病毒的特征，保護(hù)計算機(jī)系統(tǒng)的安全。3 人工免疫系統(tǒng)近年來，人們不斷從生物系統(tǒng)獲得靈感，提出了若干采用計算途徑實(shí)現(xiàn)的學(xué)習(xí)系統(tǒng)。生物免疫系統(tǒng)是一個高度進(jìn)化的生物系統(tǒng)，它旨在區(qū)分外部有害抗原和自身組織，從而清除病原并保持有機(jī)體的穩(wěn)定。從計算的角度來看，生物免疫系統(tǒng)是一個高度并行、分布、自適應(yīng)和自組織的系統(tǒng)，具有很強(qiáng)的學(xué)習(xí)、識別、記憶和特征提取能力。人們自然希望從生物免疫系統(tǒng)的運(yùn)行機(jī)制中獲取靈感，開發(fā)面向應(yīng)用的免疫系

5、統(tǒng)計算模型人工免疫系統(tǒng)(Artificial Immune System , AIS)，用于解決工程實(shí)際問題。目前，AIS 已發(fā)展成為計算智能研究的一個嶄新的分支。3.1 人工免疫系統(tǒng)（AIS）的生物原型在生物自然界中，免疫系統(tǒng)是一個由執(zhí)行免疫功能的器官、組織、細(xì)胞和分子等組成的復(fù)雜系統(tǒng)。它是生物系統(tǒng)保護(hù)機(jī)體，抵抗細(xì)菌、病毒和其他致病因子入侵的基本防御系統(tǒng)，它能夠識別自身與異已抗原，并通過免疫應(yīng)答排除抗原性異物，維持機(jī)體的生理平衡。免疫系統(tǒng)的主要功能是識別體內(nèi)細(xì)胞，將其歸類為“自我”和“非我”，并引發(fā)適當(dāng)?shù)姆佬l(wèi)機(jī)制去除“非我”。自我對應(yīng)于機(jī)體自身的組織；非我對應(yīng)于外來有害病原或者體內(nèi)病變組織。

6、免疫應(yīng)答主要由分布在生物體全身的免疫細(xì)胞實(shí)現(xiàn)。免疫細(xì)胞泛指所有參與免疫應(yīng)答過程的相關(guān)細(xì)胞，包括吞噬細(xì)胞、NK細(xì)胞、淋巴細(xì)胞等。淋巴細(xì)胞又分為B細(xì)胞和T細(xì)胞兩種。B 細(xì)胞的主要功能是產(chǎn)生抗體，且每個B 細(xì)胞只產(chǎn)生一種抗體。免疫系統(tǒng)主要依靠抗體來對入侵抗原進(jìn)行攻擊以保護(hù)有機(jī)體。T 細(xì)胞的主要功能是調(diào)節(jié)其它細(xì)胞的活動或直接對抗原實(shí)施攻擊。成熟的B 細(xì)胞產(chǎn)生于骨髓中，成熟的T 細(xì)胞產(chǎn)生于胸腺之中。B 細(xì)胞和T 細(xì)胞成熟之后進(jìn)行克隆增殖、分化并表達(dá)功能。兩種淋巴細(xì)胞共同作用并相互影響和控制對方功能，形成了機(jī)體內(nèi)部高度規(guī)律的反饋型免疫網(wǎng)絡(luò)。3.2 人工免疫系統(tǒng)（AIS）的仿生機(jī)理從信息處理的角度來看，免疫

7、系統(tǒng)具備強(qiáng)大的識別、學(xué)習(xí)和記憶的能力及分布式、自組織和多樣性特性，這些顯著的特性不斷地吸引著研究人員從免疫系統(tǒng)中抽取有用的隱喻機(jī)制，開發(fā)相應(yīng)的AIS模型和算法用于信息處理和問題求解。下圖給出了AIS仿生機(jī)理的主要內(nèi)容描述，然后對各種典型的AIS仿生隱喻機(jī)理及其具體實(shí)現(xiàn)進(jìn)行討論。圖1：人工免疫系統(tǒng)的仿生機(jī)理圖中前4 種AIS仿生機(jī)理對應(yīng)于免疫系統(tǒng)的應(yīng)答過程。免疫應(yīng)答包括初次應(yīng)答和再次應(yīng)答，初次應(yīng)答是指免疫系統(tǒng)首次遇到一種抗原，再次應(yīng)答則是對已識別抗原產(chǎn)生的免疫應(yīng)答。免疫應(yīng)答的實(shí)質(zhì)是一個識別、效應(yīng)和記憶的過程。免疫識別是免疫系統(tǒng)的主要功能，同時也是AIS的核心之一，而識別的本質(zhì)是區(qū)分“自我”和“非

8、我”，通過淋巴細(xì)胞上的抗原識別受體(receptor)與抗原的結(jié)合(binding)實(shí)現(xiàn)的，結(jié)合的強(qiáng)度稱為親合度(affinity)。免疫識別過程同時也是一個學(xué)習(xí)的過程，學(xué)習(xí)的結(jié)果是免疫細(xì)胞的個體親合度提高、群體規(guī)模擴(kuò)大，并且最優(yōu)個體以免疫記憶的形式得到保存。免疫學(xué)習(xí)大致可分為兩種：一種發(fā)生在初次應(yīng)答階段，即免疫系統(tǒng)首次識別一種新的抗原時，其應(yīng)答時間相對較長；而當(dāng)機(jī)體重復(fù)遇到同一抗原時，由于免疫記憶機(jī)制的作用，免疫系統(tǒng)對該抗原的應(yīng)答速度大大提高，并且產(chǎn)生高親合度的抗體去除病原，這個過程是一個增強(qiáng)式學(xué)習(xí)( reinforcement learning) 過程，對應(yīng)于再次應(yīng)答。免疫記憶對應(yīng)于再次免

9、疫應(yīng)答和交叉免疫應(yīng)答，而交叉應(yīng)答是免疫系統(tǒng)對結(jié)構(gòu)相似的抗原所產(chǎn)生的免疫應(yīng)答。免疫記憶屬于聯(lián)想式記憶，是AIS區(qū)別于其它進(jìn)化算法的重要特性之一?？寺∵x擇原理大致內(nèi)容為：當(dāng)淋巴細(xì)胞實(shí)現(xiàn)對抗原的識別（即抗體-抗原的親和度超過一定閾值）后，B細(xì)胞被激活并增殖復(fù)制產(chǎn)生B細(xì)胞克隆，隨后克隆細(xì)胞經(jīng)歷變異過程，產(chǎn)生對抗原具有特異性的抗體。主要特征是免疫細(xì)胞在抗原刺激下產(chǎn)生克隆增殖，隨后通過遺傳變異分化為多樣性效應(yīng)細(xì)胞（如抗體細(xì)胞）和記憶細(xì)胞。克隆選擇對應(yīng)著一個親合度成熟的過程，本質(zhì)上是一個達(dá)爾文式的選擇和變異的過程。免疫網(wǎng)絡(luò)理論對免疫細(xì)胞活動、抗體生成、免疫耐受、自我與非我識別、免疫記憶和免疫系統(tǒng)的進(jìn)化過程等

10、做出了系統(tǒng)的假設(shè)，并且將免疫系統(tǒng)視為由免疫細(xì)胞或者分子組成的調(diào)節(jié)網(wǎng)絡(luò)，免疫細(xì)胞以抗體間的相互反應(yīng)和不同種類免疫細(xì)胞間的相互通信為基礎(chǔ)，抗原識別是由抗原相互作用所形成的免疫網(wǎng)絡(luò)完成的?？贵w多樣性的生物機(jī)制主要包括免疫受體庫的組合式重整、體細(xì)胞高突變以及基因轉(zhuǎn)換等。多樣性仿生機(jī)理可以廣泛應(yīng)用于優(yōu)化搜索過程，特別是組合優(yōu)化與多峰函數(shù)優(yōu)化。免疫系統(tǒng)的分布式特性首先取決于病原的分布式特征，即病原是分散在機(jī)體內(nèi)部的；其次免疫系統(tǒng)的分布式特性有利于加強(qiáng)系統(tǒng)的健壯特性，從而使得免疫系統(tǒng)不會因?yàn)榫植拷M織損傷而使整體功能受到很大影響。3.3 陰性選擇原理未成熟的T細(xì)胞首先要經(jīng)歷一個審查環(huán)節(jié)，只有那些不能與自我發(fā)生

11、應(yīng)答的T細(xì)胞才可以離開胸腺，執(zhí)行免疫應(yīng)答任務(wù)，該過程稱為陰性選擇，它是免疫識別的一種主要方式。陰性選擇是T細(xì)胞在胸腺中產(chǎn)生、成熟過程中的一個重要階段。未成熟T細(xì)胞在胸腺中與大量的“自己”細(xì)胞進(jìn)行匹配操作，與“自己”細(xì)胞匹配的T細(xì)胞死亡，只有不與任何“自己”細(xì)胞匹配的未成熟T細(xì)胞才最終生長為成熟T細(xì)胞。在計算機(jī)免疫系統(tǒng)中，探測器生成過程采用陰性選擇過程的稱為遵循陰性選擇原則。1994 年Forrest等3提出了陰性選擇算法。該算法很好地體現(xiàn)了陰性選擇原則的思想。算法分兩個階段，一是探測器生成階段，該階段是探測器的產(chǎn)生和成熟的過程，探測器由等長的字符串表示，成熟的探測器不與“自己”集中的任何個體匹

12、配。該階段稱為評價( Censoring )階段。二是探測器監(jiān)控(Monitor)階段，在該階段利用比較輸入字符串和探測器集的匹配情況來保護(hù)被保護(hù)的數(shù)據(jù)集。免疫細(xì)胞對抗原的識別是通過結(jié)合(或匹配)過程實(shí)現(xiàn)的，相應(yīng)地AIS中的抗原識別通過特征匹配來實(shí)現(xiàn)，其核心是定義一個匹配閾值，而對匹配的度量則采用多種方法，如Hamming距離、Euclidean距離以及Forrest2所提出的R連續(xù)位匹配方法(見下圖) 等。陰性選擇原理對應(yīng)AIS中的陰性選擇算法，其核心是根據(jù)識別的對象特征進(jìn)行編碼，定義一個自我集合并隨機(jī)產(chǎn)生一系列檢測器，用于檢測自我集合的變化。根據(jù)陰性選擇原理，若檢測集合與自我集合匹配，則完

13、成匹配任務(wù)。圖2：陰性選擇的R位連續(xù)匹配規(guī)則基于陰性選擇原理，Dhaeseleer2給出了一種陰性選擇算法，用于監(jiān)測數(shù)據(jù)改變。其中抗體(問題解答)與抗原(問題)的匹配采用Forrest提出的部分匹配規(guī)則。該算法的流程如下：Step 1：有限字符表上，定義一組長度為L的字符串集合S來代表自我，用于檢測。Step 2：產(chǎn)生檢測器集合R，依據(jù)陰性選擇原理，對每個檢測器進(jìn)行審查。審查采用部分匹配規(guī)則，即兩個字符串匹配當(dāng)且僅當(dāng)至少有r個連續(xù)位相同，其中r為參數(shù)。Step 3：通過連續(xù)地將R中的檢測器與S比較來監(jiān)測S的改變。如果檢測器發(fā)生匹配，則有改變發(fā)生。該算法的優(yōu)點(diǎn)是簡便、易于實(shí)現(xiàn)，主要問題是計算復(fù)雜

14、度呈指數(shù)級增長，難以處理復(fù)雜問題。4 一種基于人工免疫和代碼相關(guān)性的計算機(jī)病毒特征提取方法傳統(tǒng)的計算機(jī)反病毒方法是以特征檢測為基礎(chǔ)的，這些方法利用從病毒中提取的特定特征來檢測出有相似行為的病毒程序。它們對于已知或者是出現(xiàn)過的病毒有著很高的識別率，但是對于沒有出現(xiàn)過的未知病毒或者病毒的新變種缺乏快速而準(zhǔn)確的識別能力。以生物體為原型的計算機(jī)系統(tǒng)和自然生物系統(tǒng)有著天然的聯(lián)系，而自然免疫系統(tǒng)又具有強(qiáng)大的區(qū)分“自體”和“異體”的能力，這種功能與計算機(jī)安全系統(tǒng)的反病毒功能極為類似。因此，借助自然免疫機(jī)理，如陰性選擇機(jī)理、克隆選擇機(jī)理等機(jī)理，采用人工免疫模型來識別計算機(jī)中的合法程序（稱為“自體”）和病毒程序

15、（稱為“異體”）成為病毒檢測的一個可行的發(fā)展方向。在病毒的實(shí)際工作機(jī)理中，一個病毒的多個指令都是相關(guān)的，病毒多個關(guān)鍵代碼的有機(jī)結(jié)合才產(chǎn)生了病毒作用?；诖怂枷?，文獻(xiàn)1提出了一種特征提取方法，充分利用了組成病毒的相關(guān)指令的相關(guān)性，使得病毒特征的提取在個體層上完成，將每個病毒樣本的多個指令存放在此病毒樣本對應(yīng)的數(shù)據(jù)庫空間中，采用與其特征生成、儲存對應(yīng)的匹配檢測模式，并由此建立了模型。4.1 特征的有向?qū)赏ㄟ^對自然免疫過程的模擬產(chǎn)生的人工免疫系統(tǒng)，移植了相關(guān)的一些概念：（1）DNA：整個程序的bit串稱為程序的DNA；（2）基因：病毒的檢測器，DNA的片斷，病毒檢測的比較單元；（3）脫氧核苷酸：

16、每兩個字節(jié)看作是一個脫氧核苷酸，記作ODN，若干個脫氧核苷酸組成了基因。病毒程序的代碼對應(yīng)著生物體中的DNA。少量起著病毒作用的關(guān)鍵代碼被認(rèn)為是病毒的基因，這些基因由病毒的ODNs組成。多個ODN的有序連接表示程序的一個指令或多個指令的有序集合。病毒特征的初始選擇采用了有向?qū)У姆绞剑靡阎獫舛鹊男畔斫y(tǒng)計每個ODN 趨向于代表病毒的程度。模型能夠統(tǒng)計出ODN 在合法程序和病毒程序中出現(xiàn)的頻率信息。模型要根據(jù)其頻率信息，計算出每個ODN 趨向于代表病毒的程度：ODN i 被挑選進(jìn)入病毒ODN 庫的概率與其在病毒程序所有ODN 中出現(xiàn)的頻率成正比，與其在合法程序所有ODN 中出現(xiàn)的頻率成反比；與

17、訓(xùn)練集中包含ODN i 的病毒文件數(shù)與所有病毒文件數(shù)的比例成正比，與訓(xùn)練集中包含ODN i 的合法程序數(shù)與所有合法程序數(shù)的比例成反比。通過有向?qū)У纳珊?，一個基本的病毒ODN特征庫就形成了，但是其中也存在著很多非病毒基因段或疑似病毒基因段，需要通過進(jìn)一步的篩選。以此基本庫為訓(xùn)練集進(jìn)一步訓(xùn)練。4.2 特征的存儲結(jié)構(gòu)實(shí)際的病毒運(yùn)行機(jī)理是：（1）特征不應(yīng)該為了計算的簡潔方便而采取不符合實(shí)際的固定長度；（2）多個特征并存才可以用來標(biāo)識一個病毒，而非只采用一個病毒特征；（3）病毒的多個特征間是有極大的相關(guān)聯(lián)系的。文獻(xiàn)1依據(jù)這些特點(diǎn)，提出了在個體層上檢測病毒的概念，以充分利用多個相關(guān)基因的相關(guān)性。嘗試將每

18、個病毒樣本的多個基因存放在此病毒樣本對應(yīng)的一個數(shù)據(jù)庫空間中，最后通過空間中的所有病毒進(jìn)行兩兩匹配，得出病毒個體之間定義出的相似度值，為充分利用多個基因的相關(guān)性提供基礎(chǔ)。這種存儲方式被稱為個體層上的存儲?；谟邢?qū)У奶卣魃煞椒?，可以很好控制住ODN的個數(shù)，特征存儲的空間即可被控制住，從而控制了最終匹配檢測時的計算代價，避免了出現(xiàn)訓(xùn)練的時間過長而致模型失去實(shí)用性的問題。病毒基因庫的基本存儲單位是病毒樣本個體。在每個病毒樣本個體中，保存了該樣本的所有基因，這樣就使得同一病毒的不同基因存放在一起，不同病毒的基因分離保存。每個基因是不定長的，每個樣本儲存的基因數(shù)目也不同。圖3：病毒基因的儲存方式4.3

19、 病毒基因庫有向?qū)У厣刹《咎卣鞯腛DN庫后（這是組成病毒特征的最基本單元）， 在此基礎(chǔ)上與任一程序的字符串進(jìn)行匹配，形成一系列不定數(shù)目的不定長ODN串，屬于某個程序的儲存在一起，不同程序的分開儲存，從而得到了病毒基因庫和類病毒基因庫，在這過程中，需要運(yùn)用人工免疫方法中的陰性選擇算法，對初始得到的這種病毒候選基因進(jìn)行免疫，去除其特征表示的模糊狀態(tài)，進(jìn)而得到用來標(biāo)示文件可以應(yīng)用于特征檢測的檢測基因庫。圖4：病毒候選基因庫和檢測基因庫的生成模型利用第一步生成的病毒ODN庫中的ODN為訓(xùn)練集，采用連續(xù)匹配的方式匹配病毒DNA，從而生成病毒的候選基因。所謂連續(xù)匹配方式是指從第一個發(fā)生匹配的位置開始，采

20、用滑動窗口的方式向后進(jìn)行匹配比較，一直匹配前進(jìn)，直到發(fā)生間斷為止，此時檢查從開始匹配到結(jié)束匹配共有多少個病毒ODN庫中的ODN參與了匹配，如果ODN數(shù)目超過某個閾值T，則將病毒DNA的這個片段作為病毒基因，否則認(rèn)為該片段不包含足夠多的信息，不是病毒的關(guān)鍵代碼，即不是病毒的基因。模型將所有生成的病毒基因都保存到與其對應(yīng)的病毒樣本的數(shù)據(jù)庫空間中，形成了病毒候選基因庫。以同樣的方法，將ODN庫中的特征片段與已知的合法程序進(jìn)行連續(xù)匹配，可以得到類病毒基因庫。模型將合法程序的類病毒基因看作“自體”，將病毒的候選基因看作“異體”，采用T連續(xù)一致匹配規(guī)則，進(jìn)行陰性選擇，即一旦病毒的某個基因與合法程序的任何一個基因匹配成功，則刪除病毒的該候選基因。重復(fù)這個過程，直到病毒候選基因庫中所有和合法程序類病毒基因發(fā)生匹配的基因都被刪除為止。至此，病毒候選基因庫升級成為病毒的檢測基因庫。4.4 特征的多層次匹配病毒庫的生成，可以開始識別測試程序。在特征的匹配問題之上，為了提高模型的準(zhǔn)確度，在3個邏輯層面上進(jìn)行逐一匹配。在對可疑程序進(jìn)行檢測時，在底層，即基因?qū)?，采用了T連續(xù)一致匹配規(guī)則，采用模糊匹配的方式來進(jìn)行容錯匹配，