楊應(yīng)華 夏 勇

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

?

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

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

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

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

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

0 引 言

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

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

1 病毒特征選擇

1.1 選擇病毒特征

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

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

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

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

決定計算機(jī)病毒作用的關(guān)鍵代碼往往只有少許片段，如何定位并提取關(guān)鍵代碼是病毒特征提取的關(guān)鍵。本文引進(jìn)ODN濃度作為平衡因子采用TF-IDF特征詞定位算法對計算機(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時，ODNi在合法代碼的ODN中，反之ODNi在病毒代碼的ODN中。根據(jù)式(5)的計算結(jié)果可以建立ODN庫，本文擬采用滑動窗口的方式來對ODN進(jìn)行計數(shù)，算法偽代碼如下：

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

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

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

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

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

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

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

1.2 病毒候選基因庫

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

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

1.3 病毒檢測基因庫

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

圖2 病毒檢測流程示意圖

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

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

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

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

(6)

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

2 病毒程序檢測模型

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

2.1 模型建立

Pi1Pi2Pinj

(7)

(8)

(9)

(10)

2.2 模型分析

通過模型計算出的相似度值與相似矩陣中每一個元素值成正比，與病毒檢測基因庫中基因長度成反比，則相似閾值k滿足：

(11)

(12)

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

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

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

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

圖3 程序正確檢測率

從圖3曲線走向可以看出：隨著相似度閾值k的增大，合法程序檢測率呈平穩(wěn)遞增的趨勢，相反病毒程序檢測率則出現(xiàn)較大幅度的降低。這是由于相似度閾值k與可變匹配閾值r成反比，可變匹配閾值r與病毒檢測率成正比。雖然隨著相似度閾值k的不斷增大，合法程序檢測率呈遞增趨勢，但是遞增的幅度是相當(dāng)平緩的，而對于病毒程序的檢測率卻是明顯的降低，本文取相似閾值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個合法程序中隨機(jī)抽取1 512個合法程序同樣分成5份，利用本文算法進(jìn)行5倍交叉仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示。

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

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

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

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

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

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

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

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

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

表6 算法性能對比 %

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

4 結(jié) 語

本文在前人研究的基礎(chǔ)上，借鑒人工免疫相關(guān)思想，通過利用TF-IDF算法在代碼層對病毒DNA進(jìn)行趨向性提取，建立病毒候選基因庫；在基因?qū)硬捎每勺價匹配規(guī)則匹配建立病毒檢測基因庫；最后利用余弦相似度算法評估待測程序與病毒的相似度。層層篩選病毒層內(nèi)特征，在有效控制病毒基因庫規(guī)模的情況下，提升了對變異病毒及未知病毒的檢測準(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ī)免疫學(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).面向入侵檢測的集成人工免疫系統(tǒng)[J].通信學(xué)報，2012,33(2):125-131.

[6] 蘆天亮,鄭康鋒,劉穎卿.基于動態(tài)克隆選擇算法的病毒檢測模型[J].北京郵電大學(xué)學(xué)報,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é)報,2011,43(6):141-145.

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

[11] 王輝,于立君,王科俊,等.一種可變模糊匹配陰性選擇算法[J].智能系統(tǒng)學(xué)報,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é)報(自然科學(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。國家自然科學(xué)基金項(xiàng)目(61471297)。楊應(yīng)華，講師，主研領(lǐng)域：數(shù)字圖像檢索與信息安全。夏勇，教授。

TP393

A

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