基于模糊模式與決策樹融合的腳本病毒檢測算法

張 濤 張 瀚 付壘朋

?

基于模糊模式與決策樹融合的腳本病毒檢測算法

張 濤 張 瀚*付壘朋

(南開大學天津市智能機器人技術重點實驗室 天津 300071)

構建決策樹進行腳本病毒檢測可以全面利用訓練樣本的信息，在樣本特征較為復雜、樣本數較大的情況下會產生大量節點，計算時間復雜度高，在剪枝過程中影響分類準確度。為融合模糊模式的信息以提高分類器性能，該文設計了決策樹分類基礎上的融合算法。該算法將關于模糊模式貼近度的3個特性作為決策樹樣本信息向量中的屬性。使用訓練樣本集，根據上述屬性在劃分點上的分裂信息值及信息增益率選擇分裂屬性，逐步構建決策樹。實驗結果驗證了算法的穩定性與準確度，表明這種融合方法可增加屬性的區分度，減少決策樹的分支數。

腳本病毒檢測；模糊模式；決策樹；貼近度

1 引言

腳本病毒[1]作為網絡中的流行病毒對信息安全產生巨大威脅，腳本病毒檢測技術的研究有著積極的意義。腳本與瀏覽器的緊密結合，簡單的腳本語法使得病毒易于變形與撰寫。特征代碼法、校驗和法等對于變種病毒檢測效果不好[2]，使得統計與人工智能方法被廣泛應用。

腳本病毒與可執行文件病毒等在語言與執行環境上有明顯區別，腳本病毒研究有其自身特點。 Choi等人[3]采用N-gram分析腳本代碼，結合SVM方法識別未知腳本病毒。Asaf等人[4]使用機器學習理論構建分類器，通過對靜態特征的分析檢測惡意代碼。Robert等人[5]總結了機器學習方法提取惡意代碼靜態特征的研究進展，模糊理論[6]被應用到病毒檢測中，可以識別未知的計算機病毒。文獻[7]細致討論了腳本病毒檢測中，模糊模式的具體構造算法與參數選取。模糊模式的使用能提取病毒集的特征相互之間的規則信息，一定程度上能反映腳本語言編寫特點，但是僅使用模糊模式檢測病毒的效果不太理想。

決策樹[8,9]是模式分類中的常用技術，文獻[10]使用決策樹分析可執行文件病毒的機器碼。決策樹算法通常[8,9,11]具有較高的準確率，分類效果與訓練樣本有直接關系。如果訓練樣本包含噪聲數據過多，特征過于復雜，或統計出現波動，使得增加了不必要的分支，會產生決策樹的過度適應現象，這樣分支的增多會導致資源消耗的增加。

針對決策樹算法的不完善及模糊模式在腳本檢測中的缺點，本文提出了一種基于模糊模式和決策樹相融合的腳本病毒檢測算法。決策樹使用腳本文件集預處理產生的特征信息訓練生成；為了增加屬性區分度，減少樹節點個數，構建決策樹時融合了模糊模式中貼近度的信息；混合使用模糊模式信息與自身特征信息可提高決策樹的穩定性，改善決策樹的準確性，所得決策樹為新的腳本病毒分類器，最后通過實驗結果驗證檢測效果。

2 腳本文件集的來源與預處理

實驗對象為VBScript腳本構成的病毒腳本集與正常腳本集，通過VirusTotal, VirusScan標記。其中病毒腳本1277個，來源為VX Heavens[12]網站下載的病毒實例與腳本病毒生成器生成的典型病毒實例，及知名安全網站看雪、劍盟、卡飯、http:// malwareurl.com等。病毒腳本的種類涉及后門程序、自動運行病毒、郵件蠕蟲、漏洞攻擊代碼、P2P蠕蟲、局域網蠕蟲、WORD宏病毒、EXCEL宏病毒、加密變型病毒等。正常腳本集4041個，由版本1.15.4的Heritrix工具爬取網頁獲得，接近現實網絡中的分布，包括網站的特效腳本代碼、word宏、excel宏和http://www.computerperformance.co.uk/ vbscript/網站的示例代碼。

腳本病毒的行為主要通過調用如CreateObject, CreateObject的關鍵的系統函數和如FileSystem Object的對象來實現，Zou等人[13]使用它們來表示病毒行為。文中這兩類作為關鍵詞被提取，對病毒腳本集和正常腳本集進行關鍵詞的統計分析[7]，按其在病毒集和正常集中出現頻率的均方誤差大小排序，本文選取均方誤差顯著較大的關鍵詞。樣本信息由矩陣描述，行表示某樣本的向量信息，元素為樣本的屬性取值，即關鍵詞的出現頻率。

3 模糊模式與決策樹算法融合的檢測算法

由文獻[7]可知基于模糊模式的腳本病毒檢測算法穩定性好，但對病毒文件檢測正確率不太理想。基于決策樹算法的腳本病毒檢測算法分類效果同訓練樣本有關，全面的樣本集會帶來較高的準確率；但如果訓練樣本噪聲過多，統計出現波動，都會出現決策樹過度適應現象，產生的多余分支會使得分類出現錯誤。在決策樹修剪環節中，決策樹過于復雜會增加難度。精確的決策樹需要較多的節點，訓練建樹時間較長，將模糊模式和決策樹相融合，模糊模式的使用可增加屬性的區分度，減少決策樹的分支數，即減小計算時間復雜度，增加檢測的穩定性。因此，本文設計了利用模糊貼近度信息的融合算法。

3.1模糊化與貼近度的計算

3.2 融合算法

3.2.2決策樹構建子算法描述 依據文件預處理后的關鍵詞及其模糊屬性信息生成C4.5決策樹[8,9,11]，并對決策樹進行悲觀剪枝[15]，以控制生成決策樹規模，提高準確率，算法主要步驟如下：

步驟3 對所有屬性使用上述方法，選取具有最大信息增益率的屬性作為此次分裂的屬性，并將集合劃分為兩個子集；

步驟4 對劃分的兩個子集使用上述方法遞歸進行決策樹的生長；

步驟5 設置葉節點，停止決策樹的生長。以下3種情況設為葉節點：節點數據集的純度達到98%；節點數據集與整個數據集樣本數比值小于1%，即數據集過小；沒有用來分割的屬性。當該節點集合中病毒比重較大時，將此葉節點的類別設置病毒，反之設置為正常文件。

3.2.3分類算法描述

4 實驗結果分析

4.1 融合算法的實驗結果

使用10次交叉驗證實驗方式[16]，共5318個樣本。每次隨機提取1772個實驗樣本作為測試數據集，其中病毒文件425個，正常文件1347個，其余3546個樣本作為訓練集。決策樹停止生長的條件設置為：最小的葉準確率為98%，最下的葉分支比例為0.001，連續屬性的劃分數設置為30。

圖1 融合算法中關鍵詞數與實驗正確率的關系圖

4.23種檢測模型的對比分析

4.2.1正常文件的檢測率 由表1，表2將融合算法與決策樹算法、文獻[7]的模糊模式算法比較，正常文件檢測率均值依次為0.9638, 0.9584, 0.9875，總體樣本差依次為0.0011, 0.0024, 0.0020。模糊模式算法對于正常文件檢測效果稍強于其它兩個檢測模型，因模糊模式算法構造時傾向于判斷為正常文件。

表1決策樹模式10次交叉實驗結果

序號TPTNFPFN節點數 1129239926550.95920.93880.06120.0408440.94890.9078 2128939629580.95690.93180.06820.0431430.94430.9010 3128640223610.95470.94590.05410.0453460.95030.9054 41287416 9600.95550.97880.02120.0445430.96710.9234 5128940619580.95690.95530.04470.0431470.95610.9134 6128939629580.95690.93180.06820.0431410.94430.9010 7129541213520.96140.96940.03060.0386530.96540.9269 8129539530520.96140.92940.07060.0386480.94530.9060 9129441510530.96070.97650.02350.0393550.96860.9295 10129440322530.96070.94820.05180.0393510.95440.9149 綜合1291040402105600.95840.95060.04940.041647.10.95450.9130

表2融合算法10次交叉實驗結果

序號TPTNFPFN節點數 1130140817460.96590.96000.04000.0341120.96290.9283 2129940916480.96440.96240.03760.0356110.96340.9274 3129841114490.96360.96710.03290.0364140.96530.9288 4129941312480.96440.97180.02820.0356120.96810.9323 5129741411500.96290.97410.02590.0371100.96850.9314 6129641312510.96210.97180.02820.0379150.96690.9291 7129841114490.96360.96710.03290.0364110.96530.9288 8130041312470.96510.97180.02820.0349130.96840.9333 9129741411500.96290.97410.02590.0371160.96850.9314 10129740817500.96290.96000.04000.0371120.96140.9241 綜合1298241141364880.96380.96800.03200.036212.60.96590.9295

圖2 3個模型10次交叉驗證值曲線圖

4.2.4決策樹的節點個數 兩種決策樹模型生成的結點數見表1，表2，決策樹模型節點數在47個左右，節點數總體標準差為4.41。融合算法檢測方法需要節點數較少，僅為13個左右，融合模型節點數總體標準差為1.8，生成節點數的穩定性較好，其生成的節點數僅為決策樹模型的25%左右。

4.3 融合算法的理論分析

決策樹的顯著優點是所給分類問題的計算時間復雜度與決策樹的節點數成線性增長關系。決策樹中某些重要模式由于噪聲及數據波動可導致建樹過程復雜，而由模糊模式提煉的較為本質的屬性具有一定魯棒性，一定程度上可抗噪聲干擾，結合建樹算法互為補充，在保證正確率的前提下，既可由模糊模式提高穩定性，也能在兩者的融合下大幅度節省節點數。當樣本足夠多，種類全面時融合算法的優勢會更加明顯。

圖3 3個模型10次交叉驗證值曲線圖

5 結束語

本文在決策樹檢測實驗的基礎上提出了一種基于模糊模式和決策樹算法相融合的腳本病毒檢測算法，通過實驗結果分析，融合算法在腳本病毒檢測中具有很好的檢測效果與可行性，總體分類性能與病毒分類性能較模糊模型有明顯提高，比單純的決策樹模型也有一定提高。這種模糊模式同決策樹融合的具體方法可顯著減少節點生成個數，增加了屬性的區分度。它克服了模糊模式對病毒類的低檢測率，優化了決策樹的構建過程，較好地同時利用了模糊信息與自身的特征信息，且性能穩定，生成節點數較少。

本文提出的腳本病毒檢測算法針對VBScript，對于其它的腳本病毒的研究需提取有效特征再應用。尋求模糊模式和改進決策樹的更有效的融合辦法，是將來的工作方向之一。

[1] Willem D G, Dominique D, and Frank P. Better security and privacy for web browsers: a survey of techniques, and a new implementation[C]. 8th International Workshop on Formal Aspects of Security and Trust, Leuven, Belgium, 2011: 21-38.

[2] Kim J Yand Moon B R. New malware detection system using metric-based method and hybrid genetic algorithm[C]. Proceedings of the 14th International Conference on Genetic and Evolutionary Computation Companion, Philadelphia, PA, United States, 2012: 1527-1528.

[3] Choi J H, Choi C, Kim H Y,. Efficient malicious code detection using N-gram analysis and SVM[C]. International Conference on Network-Based Information Systems, Tirana, Albania, 2011: 618-621.

[4] Asaf S, Robert M, Yuval E,. Detection of malicious code by applying machine learning classifiers on static features: a state-of-the-art survey[J]., 2009, 14(1): 16-29.

[5] Robert M and Yuval E. Malicious code detection using active learning[C]. Second ACM SIGKDD International Workshop, PinKDD 2008, Las Vegas, NV, USA, 2008: 74-91.

[6] Zadeh L A. The concept of a linguistic variable and its applications to approximate reasoning[J]., 1975, 8(3): 199-249.

[7] 張濤, 付壘朋, 張瀚, 等. 一種基于模糊模式的腳本病毒檢測方法[OL].中國科技論文在線, http://www.paper.edu.cn. 2011.9.

Zhang Tao, Fu Lei-peng, Zhang Han,. Research on method of classification based on fuzzy pattern model in script virus detection[OL]. http://www.paper.edu.cn. 2011.9.

[8] Quinlan J R. C4.5 Programs for Machine Learning[M]. San Mateo, CA, Morgan Kaufmann Publishers, 1993, Chapter 1- Chapter 5.

[9] Thakur D, Markandaiah N, and Raj D S. Re optimization of ID3 and C4.5 decision tree[C]. International Conference on Computer and Communication Technology, Allahabad, India, 2010: 448-450.

[10] Rad B B, Masrom M, Suhaimi I,. Morphed virus family classification based on opcodes statistical feature using decision tree [C]. The International Conference on Informatics Engineering & Information Science, University Technology Malaysia, Kuala Lumpur, Malaysia, 2013: 123-131.

[11] Fan Jie and Wen Pu. Application of C4.5 algorithm in web- based learning assessment system[C]. The Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, China, 2007: 4139-4143.

[12] VX Heavens. Virus collection[OL]. http://vx.netlux.org. 2009.10.

[13] Zou Meng-song, Han Lan-sheng, Liu Qi-wen,. Behavior- based malicious executables detection by multi-class SVM[C]. Proceedings of IEEE Youth Conference on Information, Computing and Telecommunication, Piscataway, NJ, United States, 2009: 331-334.

[14] Nakamura E and Kehtarnavaz N. Optimization of fuzzy membership function parameters[C]. Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, Piscataway, NJ, United States, 1995: 1-6.

[15] Rajeev S and Kyuseok S. A decision tree that integrates building and pruning[C]. Proceedings of 24th International Conference on very Large Database, New York, USA, 1998: 404-415.

[16] Duda R O, Hart P E, and Stork D G. Pattern Classification [M]. 2nd Edition, New York: USA, Wiley, 2001, Chapter 8.

張 濤： 女，1983年生，碩士生，研究方向為信息安全.

張 瀚： 男，1978年生，男，博士，教授，博士生導師，研究方向為計算智能、信息安全、生物信息學.

付壘朋： 男，1983年生，碩士生，研究方向為信息安全.

Script Virus Detection Algorithm Based on Fusion of Fuzzy Pattern and Decision Tree

Zhang Tao Zhang Han Fu Lei-peng

(,,300071,)

The method using the decision tree for script virus detection can make full use of the information of training samples. But complex sample features and large number of samples will produce large number of nodes which result in the high algorithm time complexity and affect the classification accuracy due to the pruning process. In order to improve classification performance, a fusion algorithm using the information of fuzzy pattern is designed based on the decision tree classification algorithm. Three important characteristics of fuzzy pattern about close degree are regarded as the three attributes of sample information vector in the decision tree to build decision tree through training get.The stability and accuracy of the algorithm is verified by experiment. The experiment results show that the proposed algorithm increases discrimination of attributes and reduces the decision tree branch.

Script virus detection; Fuzzy pattern; Decision tree; Close degree

TP309.5; TP181

A

1009-5896(2014)01-0108-06

10.3724/SP.J.1146.2012.01491

2012-11-16收到，2013-08-12改回

國家自然科學基金(61004086)和高等學校博士學科點專項科研基金(200800551024)資助課題

張瀚 zhanghan@nankai.edu.cn