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

楊應華 夏 勇

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

?

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

楊應華1夏 勇2

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

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

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

0 引 言

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

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

1 病毒特征選擇

1.1 選擇病毒特征

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

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

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

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

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

(1)

(2)

根據上式的結果可以得出ODNi的TF-IDF值：

(3)

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

(4)

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

(5)

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

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

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

Temp7. goto Temp2;直到Q中所有合法代碼統計完；

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

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

Temp13. goto Temp8；直到Q中所有病毒代碼統計完；

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

1.2 病毒候選基因庫

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

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

1.3 病毒檢測基因庫

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

圖2 病毒檢測流程示意圖

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

病毒代碼與病毒ODN庫通過匹配規則生成病毒候選基因庫，但是病毒ODN庫中的部分ODN可能存在于合法代碼ODN中。這使病毒候選基因庫與合法代碼類病毒基因庫存在部分匹配的可能。降低病毒檢測的準確率。在人工免疫系統中應用最多的是rcb匹配規則，因為其很好地體現兩個字符的相似程度。rcb匹配比較的是一串連續的字符串，容易脫離整體。結合病毒候選基因庫與合法代碼類病毒基因庫存在部分匹配的問題，本文采用rcb r字符塊規則[12]的可變r匹配規則來對病毒候選基因庫進行訓練建立病毒檢測基因庫。

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

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

(6)

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

2 病毒程序檢測模型

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

2.1 模型建立

Pi1Pi2Pinj

(7)

(8)

(9)

(10)

2.2 模型分析

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

(11)

(12)

3 仿真實驗

本文仿真實驗使用兩組數據集：一是文獻[14]中使用的1 512個惡意程序；二是北京大學計算機智能實驗室的cilpku08數據集(http://www.cil.pku.edu.cn/ resources.)。這個數據集含有最新的3 547個惡意程序，表1和表2分別為兩組實驗數據的詳細信息。仿真實驗從Windows7平臺上收集到3 682個合法程序，根據病毒程序屬性將其分680類，仿真是在Windows 7系統下，CPU：i3-3240@3.4 GHz,RAM:4 GB。待檢測程序檢測的正確率與相似閾值k的關系如圖3所示。

表1 文獻[14]所用數據集

表2 cilpku08數據集

圖3 程序正確檢測率

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

本文利用第一數據集驗證本文算法的效果，利用第二組數據集，通過隨機抽取來比較驗證本文算法的穩定性和泛化能力。本文將文獻[14]中提供的病毒隨機分成5份，并從Window 7系統下的3 682個合法程序中隨機抽取1 512個合法程序同樣分成5份，利用本文算法進行5倍交叉仿真實驗，實驗結果如表3所示。

表3 第一組數據集分組實驗對比 %

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

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

表4 實驗結果

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

下面將在更大數據集上驗證模型的識別性能，即用訓練好的模型對整個數據集進行檢測識別，表5為檢測結果。

表5 全部數據實驗結果

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

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

表6 算法性能對比 %

從表6的實驗結果，可以看出本文算法的虛警率雖比ID3算法稍高，但比其他兩個算法都低；在保持較低虛警率的情況下，本文算法的病毒識別率都高于其他算法。這是本算法在病毒代碼層采用TF-IDF算法對病毒DNA片段進行趨向性提取，在基因層采用可變r匹配規則提取病毒檢測基因庫；在樣本層采用余弦相似度算法評估檢測程序與病毒的相似度，最大程度提高病毒的識別率。

4 結 語

本文在前人研究的基礎上，借鑒人工免疫相關思想，通過利用TF-IDF算法在代碼層對病毒DNA進行趨向性提取，建立病毒候選基因庫；在基因層采用可變r匹配規則匹配建立病毒檢測基因庫；最后利用余弦相似度算法評估待測程序與病毒的相似度。層層篩選病毒層內特征，在有效控制病毒基因庫規模的情況下，提升了對變異病毒及未知病毒的檢測準確率。

[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] 莫宏偉. 人工免疫系統原理與應用[M]. 哈爾濱：哈爾濱工業大學出版社，2002.

[3] 李濤. 計算機免疫學[M]. 電子工業出版社, 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] 陳岳兵,馮超,張權.面向入侵檢測的集成人工免疫系統[J].通信學報，2012,33(2):125-131.

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

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

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

TP393

A

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