楊應(yīng)華 夏 勇

1(蘭州財(cái)經(jīng)大學(xué)信息中心 甘肅 蘭州 730020) 2(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 陜西 西安 710129)

?

基于人工免疫結(jié)合余弦相似度的病毒特征提取算法

楊應(yīng)華1夏 勇2

1(蘭州財(cái)經(jīng)大學(xué)信息中心 甘肅 蘭州 730020)2(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 陜西 西安 710129)

針對(duì)現(xiàn)有計(jì)算機(jī)病毒特征提取算法無法有效提取未知病毒和變種病毒的特征,本文借鑒人工免疫思想，提出一種基于人工免疫結(jié)合余弦相似度的病毒特征提取算法。在代碼層，算法采用TF-IDF對(duì)病毒DNA進(jìn)行趨向性提取建立病毒候選基因庫(kù)；在基因?qū)?，算法利用可變r(jià)匹配規(guī)則提取病毒候選基因庫(kù)生產(chǎn)病毒檢測(cè)基因庫(kù)；在程序?qū)?，算法采用余弦相似度算法評(píng)估待測(cè)程序與病毒的相似度，對(duì)待測(cè)程序進(jìn)行識(shí)別。經(jīng)仿真實(shí)驗(yàn)，本算法與其他病毒特征提取算法相比，在較低虛警率的情況下有較高的病毒識(shí)別率。

人工免疫 特征提取 TF-IDF算法 可變r(jià)匹配 余弦相似度

0 引 言

傳統(tǒng)計(jì)算機(jī)反病毒技術(shù)是以病毒特征碼為檢測(cè)基礎(chǔ)，對(duì)已知病毒有較高的識(shí)別率。但對(duì)未知或變異病毒缺乏有效識(shí)別。人工免疫系統(tǒng)[1]可通過類似生物免疫的機(jī)能，構(gòu)造強(qiáng)大的信息處理能力，以區(qū)分“自我”與“非我”，這種區(qū)分非我的功能與計(jì)算機(jī)病毒的識(shí)別頗為相似[2-3]。針對(duì)于此，國(guó)內(nèi)外學(xué)者提出了基于人工免疫系統(tǒng)的計(jì)算機(jī)病毒識(shí)別模型[4-6]，其中，陰性選擇算法[7-8]及其改進(jìn)算法成為基于人工免疫系統(tǒng)的病毒識(shí)別算法的代表。文獻(xiàn)[9]提出了一種具有疫苗算子的可變模糊匹配陰性選擇算法，基于模糊思想并采用疫苗理論，對(duì)建立特異性免疫應(yīng)答具有自適應(yīng)性。文獻(xiàn)[10]提出了一個(gè)基于帶有懲罰因子的陰性選擇算法的惡意程序檢測(cè)模型，在陰性選擇算法中引入懲罰因子，擺脫了傳統(tǒng)陰性選擇算法中對(duì)“自體”和“異體”有害性定義的缺陷，對(duì)完全未知的惡意程序具有較高的識(shí)別率。文獻(xiàn)[11]提出了一種可變模糊匹配陰性選擇算法，通過調(diào)整匹配閡值降低黑洞數(shù)量，利用模糊思想，實(shí)現(xiàn)連續(xù)相似度的模糊匹配，使病毒的檢測(cè)范圍加大，病毒識(shí)別率進(jìn)一步提高。改進(jìn)算法在自適應(yīng)和病毒檢測(cè)率上有一定的提升，但缺少對(duì)檢測(cè)關(guān)聯(lián)的深入挖掘，病毒的識(shí)別率有待進(jìn)一步的提高。

針對(duì)以上問題，本文在借鑒前人研究成果的基礎(chǔ)上，提出了一種基于人工免疫相關(guān)思想結(jié)合余弦相似度算法提取病毒特征，充分利用了關(guān)鍵特征的關(guān)聯(lián)性，提升算法的檢測(cè)效率。

1 病毒特征選擇

1.1 選擇病毒特征

計(jì)算機(jī)病毒自身機(jī)理與生物學(xué)中的病毒相似，受生物免疫系統(tǒng)對(duì)病毒查殺的啟發(fā)，將生物領(lǐng)域中的研究應(yīng)用到計(jì)算機(jī)中。病毒的特征主要存放在其DNA中，DNA由許多不同的基因組成，而基因又是由若干脫氧核苷酸(ODN)組成，結(jié)合生物研究結(jié)論，將計(jì)算機(jī)病毒中所用到的生物術(shù)語定義如下：

(1)DNA：計(jì)算機(jī)病毒整個(gè)程序的代碼；

(2) 基因：代表計(jì)算機(jī)病毒特征的字符串；

(3) 脫氧核苷酸：計(jì)算機(jī)病毒中每2 B字符串。

決定計(jì)算機(jī)病毒作用的關(guān)鍵代碼往往只有少許片段，如何定位并提取關(guān)鍵代碼是病毒特征提取的關(guān)鍵。本文引進(jìn)ODN濃度作為平衡因子采用TF-IDF特征詞定位算法對(duì)計(jì)算機(jī)病毒的關(guān)鍵代碼進(jìn)行定位提取。訓(xùn)練集合為Q，所用變量定義如下：

(1)

(2)

根據(jù)上式的結(jié)果可以得出ODNi的TF-IDF值：

(3)

為了解決集合Q中選取合法代碼與病毒代碼的不均等性，引入ODNi濃度函數(shù)作為平衡因子，濃度函數(shù)f(C)如下:

(4)

利用濃度函數(shù)f(C)平衡合法代碼集與病毒代碼集的隨機(jī)性。ODNi趨向性選擇函數(shù)S(ODNi)如下：

(5)

根據(jù)式(5)可知，當(dāng)S(ODNi)L大于S(ODNi)V時(shí)，ODNi在合法代碼的ODN中，反之ODNi在病毒代碼的ODN中。根據(jù)式(5)的計(jì)算結(jié)果可以建立ODN庫(kù)，本文擬采用滑動(dòng)窗口的方式來對(duì)ODN進(jìn)行計(jì)數(shù)，算法偽代碼如下：

Temp2. 讀取合法代碼,flag[i]=0;

Temp6. 滑動(dòng)窗口前移1 B;goto Temp3;直到合法代碼結(jié)束；

Temp7. goto Temp2;直到Q中所有合法代碼統(tǒng)計(jì)完；

Temp8. 讀取一個(gè)病毒代碼;flag[i]=0;

Temp12. 滑動(dòng)窗口前移1 B;goto Temp9;直到病毒代碼結(jié)束；

Temp13. goto Temp8；直到Q中所有病毒代碼統(tǒng)計(jì)完；

算法除了考慮ODN濃度，還重點(diǎn)考慮關(guān)鍵ODN的遺傳特性，基于TF-IDF特征詞定位算法檢測(cè)出合法代碼和病毒代碼共有的ODN庫(kù)。根據(jù)病毒的ODN庫(kù)經(jīng)過匹配生成病毒的候選基因庫(kù)，然后再經(jīng)過一系列匹配建立病毒的檢測(cè)基因庫(kù)。

1.2 病毒候選基因庫(kù)

利用病毒ODN庫(kù)與病毒程序進(jìn)行連續(xù)匹配，生成病毒候選基因庫(kù)，病毒候選基因以基于rcb匹配規(guī)則的形式生成。rcb匹配規(guī)則是指兩個(gè)字符串采用滑動(dòng)窗口的方式從相同位置開始向后匹配，直至不再匹配為止，停止匹配后計(jì)算匹配了多少個(gè)病毒ODN庫(kù)中的ODN。與閾值T進(jìn)行比較，若大于閾值T則認(rèn)為此段病毒代碼含有足夠多的病毒信息，可將此段病毒看作病毒候選基因。閾值T的大小對(duì)候選基因的選擇至關(guān)重要，因?yàn)镺DN為2 B,閾值T過大容易造成病毒候選基因過長(zhǎng)，病毒提取的準(zhǔn)確性降低；閾值T過小，提取的候選基因太短，缺乏對(duì)病毒提取的連續(xù)性和完整性。而常用計(jì)算機(jī)指令多為1 B或2 B,這里將閾值T設(shè)為3，這樣最小的候選基因?yàn)? B,可由4個(gè)ODN組成，至少包括4個(gè)計(jì)算機(jī)指令。圖1為候選基因生成流程示意圖。

圖1 候選基因生成流程示意圖

1.3 病毒檢測(cè)基因庫(kù)

病毒檢測(cè)基因庫(kù)的覆蓋率與訓(xùn)練集的數(shù)目呈正相關(guān)，為了提高病毒檢測(cè)基因庫(kù)的檢測(cè)覆蓋率，擴(kuò)大病毒識(shí)別范圍，本文將未知病毒和特種病毒作為可疑程序進(jìn)行檢測(cè)判定。病毒檢測(cè)及檢測(cè)基因庫(kù)的形成流程如圖2所示。

圖2 病毒檢測(cè)流程示意圖

算法將待檢測(cè)集集合與病毒ODN庫(kù)根據(jù)設(shè)定的閾值T進(jìn)行連續(xù)匹配生成檢測(cè)病毒基因庫(kù)；然后將檢測(cè)病毒基因庫(kù)與病毒檢測(cè)基因庫(kù)根據(jù)閾值S進(jìn)行相似度匹配，若不小于閾值S則為病毒代碼，反之進(jìn)行下一步的合法代碼相似性判斷；與合法代碼進(jìn)行相似性匹配，若不小于閾值S則為合法代碼，反之為可疑代碼；并將檢測(cè)集與合法類病毒基因庫(kù)進(jìn)行規(guī)則匹配，生成可疑代碼基因庫(kù)。

病毒代碼與病毒ODN庫(kù)通過匹配規(guī)則生成病毒候選基因庫(kù)，但是病毒ODN庫(kù)中的部分ODN可能存在于合法代碼ODN中。這使病毒候選基因庫(kù)與合法代碼類病毒基因庫(kù)存在部分匹配的可能。降低病毒檢測(cè)的準(zhǔn)確率。在人工免疫系統(tǒng)中應(yīng)用最多的是rcb匹配規(guī)則，因?yàn)槠浜芎玫伢w現(xiàn)兩個(gè)字符的相似程度。rcb匹配比較的是一串連續(xù)的字符串，容易脫離整體。結(jié)合病毒候選基因庫(kù)與合法代碼類病毒基因庫(kù)存在部分匹配的問題，本文采用rcb r字符塊規(guī)則[12]的可變r(jià)匹配規(guī)則來對(duì)病毒候選基因庫(kù)進(jìn)行訓(xùn)練建立病毒檢測(cè)基因庫(kù)。

可變r(jià)匹配規(guī)則是指病毒候選基因庫(kù)中的某個(gè)基因α采用滑動(dòng)窗口的方式與合法類病毒基因庫(kù)中的每個(gè)基因從相同位置進(jìn)行連續(xù)匹配，直至不再匹配為止，停止匹配后計(jì)算匹配了多少個(gè)ODN。若匹配成功ODN數(shù)目不小于r，則認(rèn)為兩個(gè)基因匹配成功，此時(shí)將基因α刪除，重復(fù)以上匹配過程，直到病毒候選基因庫(kù)中匹配成功的所有基因被刪除。此時(shí)，病毒候選基因庫(kù)就成為了病毒檢測(cè)基因庫(kù)。

r的取值是可變的與匹配基因的長(zhǎng)度有關(guān)。若r取值過大，則會(huì)降低匹配成功率，影響病毒檢測(cè)基因庫(kù)的生成；若r取值過小，則會(huì)誤刪病毒候選基因庫(kù)中的基因，r的取值應(yīng)為：

(6)

通過這樣的r取值后，病毒候選基因庫(kù)中與合法程序類病毒基因庫(kù)相匹配的基因，都會(huì)被最大程度地識(shí)別并刪除，提高了對(duì)病毒的區(qū)分度。

2 病毒程序檢測(cè)模型

病毒檢測(cè)基因庫(kù)中所包含的病毒基因只是代碼片段，由病毒基因片段上升到對(duì)病毒程序的檢測(cè)，需要建構(gòu)一個(gè)病毒程序檢測(cè)模型，以實(shí)現(xiàn)對(duì)病毒程序的高效識(shí)別和檢測(cè)。余弦相似度[13]是計(jì)算相似度的一種算法，最常用于文本相似度的檢測(cè)中。該算法將兩個(gè)待測(cè)文本根據(jù)相關(guān)指標(biāo)建立向量，然后通過測(cè)量?jī)蓚€(gè)向量間的內(nèi)積空間夾角余弦來度量?jī)蓚€(gè)文本的相似度。向量的夾角越小即余弦值越大表明兩個(gè)文本的越相似，反之亦然。

2.1 模型建立

Pi1Pi2Pinj

(7)

(8)

(9)

(10)

2.2 模型分析

通過模型計(jì)算出的相似度值與相似矩陣中每一個(gè)元素值成正比，與病毒檢測(cè)基因庫(kù)中基因長(zhǎng)度成反比，則相似閾值k滿足：

(11)

(12)

3 仿真實(shí)驗(yàn)

本文仿真實(shí)驗(yàn)使用兩組數(shù)據(jù)集：一是文獻(xiàn)[14]中使用的1 512個(gè)惡意程序；二是北京大學(xué)計(jì)算機(jī)智能實(shí)驗(yàn)室的cilpku08數(shù)據(jù)集(http://www.cil.pku.edu.cn/ resources.)。這個(gè)數(shù)據(jù)集含有最新的3 547個(gè)惡意程序，表1和表2分別為兩組實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息。仿真實(shí)驗(yàn)從Windows7平臺(tái)上收集到3 682個(gè)合法程序，根據(jù)病毒程序?qū)傩詫⑵浞?80類，仿真是在Windows 7系統(tǒng)下，CPU：i3-3240@3.4 GHz,RAM:4 GB。待檢測(cè)程序檢測(cè)的正確率與相似閾值k的關(guān)系如圖3所示。

表1 文獻(xiàn)[14]所用數(shù)據(jù)集

表2 cilpku08數(shù)據(jù)集

圖3 程序正確檢測(cè)率

從圖3曲線走向可以看出：隨著相似度閾值k的增大，合法程序檢測(cè)率呈平穩(wěn)遞增的趨勢(shì)，相反病毒程序檢測(cè)率則出現(xiàn)較大幅度的降低。這是由于相似度閾值k與可變匹配閾值r成反比，可變匹配閾值r與病毒檢測(cè)率成正比。雖然隨著相似度閾值k的不斷增大，合法程序檢測(cè)率呈遞增趨勢(shì)，但是遞增的幅度是相當(dāng)平緩的，而對(duì)于病毒程序的檢測(cè)率卻是明顯的降低，本文取相似閾值k為0.5。

本文利用第一數(shù)據(jù)集驗(yàn)證本文算法的效果，利用第二組數(shù)據(jù)集，通過隨機(jī)抽取來比較驗(yàn)證本文算法的穩(wěn)定性和泛化能力。本文將文獻(xiàn)[14]中提供的病毒隨機(jī)分成5份，并從Window 7系統(tǒng)下的3 682個(gè)合法程序中隨機(jī)抽取1 512個(gè)合法程序同樣分成5份，利用本文算法進(jìn)行5倍交叉仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

表3 第一組數(shù)據(jù)集分組實(shí)驗(yàn)對(duì)比 %

在分組的數(shù)據(jù)集上各檢測(cè)合法程序與實(shí)驗(yàn)病毒程序相互獨(dú)立，實(shí)驗(yàn)的可信性較高。通過仿真實(shí)驗(yàn)可知，本文算法在5組實(shí)驗(yàn)數(shù)據(jù)集合上能保持較低的虛警率，同時(shí)取得了較高的病毒識(shí)別率。

為了進(jìn)一步驗(yàn)證本文算法的有效性，仿真實(shí)驗(yàn)在3 552個(gè)病毒程序和3 682個(gè)合法程序數(shù)據(jù)集上隨機(jī)選出1 314個(gè)程序(其中655個(gè)合法程序，659個(gè)病毒程序)，按照訓(xùn)練集和檢測(cè)集0.5、1、0.5的比例進(jìn)行三次不同劃分與實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表4所示。

表4 實(shí)驗(yàn)結(jié)果

從表4可以看出，模型對(duì)訓(xùn)練集和檢測(cè)集都有較高的識(shí)別率。其中模型對(duì)訓(xùn)練集中的合法程序有一定的記憶，訓(xùn)練好的模型對(duì)合法程序的識(shí)別率在98.5%以上，對(duì)未知的病毒程序平均識(shí)別率在91%左右。并且，模型的識(shí)別率不因訓(xùn)練集和檢測(cè)集合規(guī)模的縮小而有所降低，在測(cè)試3中，訓(xùn)練集上程序遠(yuǎn)小于檢測(cè)集上的程序，但此時(shí)模型對(duì)訓(xùn)練集上病毒程序的識(shí)別率為92.4%，高于測(cè)試1和測(cè)試2的識(shí)別率。訓(xùn)練好的模型在檢測(cè)集上也表現(xiàn)出色，測(cè)試3中，對(duì)合法程序的識(shí)別率為99.4%，對(duì)病毒程序的識(shí)別率為91.6%，均高于模型在測(cè)試1和測(cè)試2上的識(shí)別率，說明模型能在小數(shù)據(jù)集上利用有限的知識(shí)敏銳學(xué)習(xí)。訓(xùn)練完成后模型可獲得較高的識(shí)別率，具有較高的泛化能力。

下面將在更大數(shù)據(jù)集上驗(yàn)證模型的識(shí)別性能，即用訓(xùn)練好的模型對(duì)整個(gè)數(shù)據(jù)集進(jìn)行檢測(cè)識(shí)別，表5為檢測(cè)結(jié)果。

表5 全部數(shù)據(jù)實(shí)驗(yàn)結(jié)果

模型對(duì)檢測(cè)集合中的合法程序的識(shí)別率都在95%以上，隨著訓(xùn)練的加強(qiáng)，模型對(duì)合法程序的識(shí)別率呈逐步上升的態(tài)勢(shì)；對(duì)病毒程序的識(shí)別率在93%以上，隨著測(cè)試次數(shù)的增加，對(duì)病毒程序的識(shí)別率也在上升，但上升的幅度平緩。

為了對(duì)比本文算法與其他特征提取算法的差別，本文將在1 314個(gè)程序集合上分別運(yùn)行ID3算法、J48算法、SMO算法以及本文算法來比較算法的性能，實(shí)驗(yàn)結(jié)果如表6所示。

表6 算法性能對(duì)比 %

從表6的實(shí)驗(yàn)結(jié)果，可以看出本文算法的虛警率雖比ID3算法稍高，但比其他兩個(gè)算法都低；在保持較低虛警率的情況下，本文算法的病毒識(shí)別率都高于其他算法。這是本算法在病毒代碼層采用TF-IDF算法對(duì)病毒DNA片段進(jìn)行趨向性提取，在基因?qū)硬捎每勺價(jià)匹配規(guī)則提取病毒檢測(cè)基因庫(kù)；在樣本層采用余弦相似度算法評(píng)估檢測(cè)程序與病毒的相似度，最大程度提高病毒的識(shí)別率。

4 結(jié) 語

本文在前人研究的基礎(chǔ)上，借鑒人工免疫相關(guān)思想，通過利用TF-IDF算法在代碼層對(duì)病毒DNA進(jìn)行趨向性提取，建立病毒候選基因庫(kù)；在基因?qū)硬捎每勺價(jià)匹配規(guī)則匹配建立病毒檢測(cè)基因庫(kù)；最后利用余弦相似度算法評(píng)估待測(cè)程序與病毒的相似度。層層篩選病毒層內(nèi)特征，在有效控制病毒基因庫(kù)規(guī)模的情況下，提升了對(duì)變異病毒及未知病毒的檢測(cè)準(zhǔn)確率。

[1] Deng P S, Wang J H, Shieh W G, et al. Intelligent automatic malicious code signatures extraction[C]// IEEE, 2003 International Carnahan Conference on Security Technology, 2003. Proceedings. IEEE Xplore, 2003:600-603.

[2] 莫宏偉. 人工免疫系統(tǒng)原理與應(yīng)用[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2002.

[3] 李濤. 計(jì)算機(jī)免疫學(xué)[M]. 電子工業(yè)出版社, 2004.

[4] Ou C M. Host-based intrusion detection systems adapted from agent-based artificial immune systems[J]. Neurocomputing, 2012, 88(7):78-86.

[5] 陳岳兵,馮超,張權(quán).面向入侵檢測(cè)的集成人工免疫系統(tǒng)[J].通信學(xué)報(bào)，2012,33(2):125-131.

[6] 蘆天亮,鄭康鋒,劉穎卿.基于動(dòng)態(tài)克隆選擇算法的病毒檢測(cè)模型[J].北京郵電大學(xué)學(xué)報(bào),2013,36(3):39-43.

[7] Forrest S,Perelson A S,Allen L,et al.Self-nonself discrimination in a computer[C]// Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy IEEE. Los Alamitos，CA,1994.221-231.

[8] Dasgupta D, Forrest S.Novelty detection in time series data using ideas from immunology[C]// Proceedings of the 5th International Conference on Intelligent Systems.Cancun,Mexico:Springer,1996:82-87.

[9] 王輝,于立君,畢曉君,等.具有疫苗算子的可變模糊匹配陰性選擇算法[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào),2011,43(6):141-145.

[10] 張鵬濤,王維,譚營(yíng).基于帶有懲罰因子的陰性選擇算法的惡意程序檢測(cè)模型[J].中國(guó)科學(xué),2011,41(7):789-802.

[11] 王輝,于立君,王科俊,等.一種可變模糊匹配陰性選擇算法[J].智能系統(tǒng)學(xué)報(bào),2011,6(2):178-185.

[12] Hou H Y, Dozier G. An evaluation of negative selection algorithm with constraint-based detector[C]// ACM Southeast Regional Conference 2006. Melbourne, Florida, USA, 2006. 134-139.

[13] 陳大力,沈巖濤,謝檳竹,等.基于余弦相似度模型的最佳教練遴選算法[J].東華大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(12):1697-1699.

[14] Henchiri O,Japkowicz N. A feature selection and evaluation scheme for computer virus detection[C]// Proceedings of the 6th International Conference on Data Mining(ICDM’06). Hong Kong.China，2006:891-895.

VIRUSFEATUREEXTRACTIONALGORITHMBASEDONTHECOSINESIMILARITYOFARTIFICIALIMMUNESYSTEM

Yang Yinghua1Xia Yong2
1(InformationCenter,LanzhouUniversityofFinanceandEconomics,Lanzhou730020,Gansu,China)2(SchoolofComputerScience,NorthwesternPolytechnicalUniversity,Xi’an710129,Shaanxi,China)

The existing computer virus feature extraction algorithm cannot effectively extract unknown viruses and variants of the virus characteristics, thus a virus feature extraction algorithm based on the cosine similarity of artificial immune system is proposed with the help of artificial immune theory. Establishing the virus candidate gene bank by adopting TF-IDF to carry on the tendency extraction to the virus DNA in the code layer algorithm; using variable r matching rule to extract virus candidate gene pool to produce virus detection gene bank in gene layer algorithm. Finally, the program layer uses the cosine similarity algorithm to evaluate the similarity between the test program and the virus, and to recognize the test program. Simulation experiments show that the proposed algorithm has higher virus recognition rate compared with other virus feature extraction algorithms in the case of low false alarm rate.

Artificial immune Feature extraction TF-IDF algorithm Variable r matching Cosine similarity

2016-07-08。國(guó)家自然科學(xué)基金項(xiàng)目(61471297)。楊應(yīng)華，講師，主研領(lǐng)域：數(shù)字圖像檢索與信息安全。夏勇，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.08.054