基于C4.5決策樹的嵌入型惡意代碼檢測方法*

張福勇 齊德昱 胡鏡林

(華南理工大學(xué)計(jì)算機(jī)系統(tǒng)研究所，廣東廣州510006)

嵌入型惡意代碼指利用文檔漏洞將惡意代碼嵌入到正常文檔中，以實(shí)現(xiàn)其傳播和攻擊的惡意代碼.這種嵌入文檔中的惡意代碼不易被察覺，而且即使在這些惡意代碼的特征碼已知的情況下，商業(yè)反病毒軟件也不能對其進(jìn)行有效的檢測［1-3］.對于利用零日漏洞嵌入的惡意代碼而言，基于特征掃描的反病毒軟件對其更是無能為力［4-6］.

研究人員普遍采用統(tǒng)計(jì)分析的方法進(jìn)行嵌入型惡意代碼檢測，該方法將文檔看成一個(gè)字節(jié)序列，提取其n-gram(連續(xù)的n個(gè)字節(jié))作為分析特征［7］，通過計(jì)算n-gram的馬氏距離［1］、n-gram在模型中出現(xiàn)的比例［2］、n-gram熵率等方式實(shí)現(xiàn)惡意代碼檢測［3］.文獻(xiàn)［3］的結(jié)果表明，馬氏距離不能得到較好的檢測結(jié)果，n-gram 熵率對 JPG、MP3、PDF、ZIP等格式的文件檢測結(jié)果較好，但對DOC(Word)文檔不能進(jìn)行有效檢測.Li等［2］采用 high-order n-gram建立normal和abnormal兩個(gè)模型，計(jì)算測試文檔中n-gram在兩個(gè)模型中出現(xiàn)的比例，賦予相應(yīng)的分值，測試文檔的類型即為得分高的模板類型;此方法在對Word文檔的檢測中取得了較好的結(jié)果，但其對訓(xùn)練和檢測數(shù)據(jù)較為敏感.

為此，文中提出一個(gè)采用C4.5決策樹的嵌入型惡意代碼檢測方法.首先，提取文檔的n-gram，計(jì)算所有n-gram的信息增益，選擇具有最大增益的500個(gè)n-gram作為特征值，如果文檔中存在某個(gè)n-gram特征，將此特征值標(biāo)為1，否則標(biāo)為0，然后采用C4.5決策樹進(jìn)行分類.

1 Boosting C4.5決策樹方法

1.1 特征選擇

文中選用n-gram信息增益進(jìn)行特征選擇.信息增益被廣泛用于信息檢索［8］、文本分類和病毒檢測等領(lǐng)域［9-10］.信息增益通過衡量特征為分類系統(tǒng)帶來的信息量來判斷特征的重要性，帶來的信息量越多，該特征越重要.

文中以n-gram作為特征T，其信息增益為

式中:P(Ci)為Ci出現(xiàn)的概率;P(T)為T出現(xiàn)的概率為T出現(xiàn)時(shí)Ci出現(xiàn)的概率為T不出現(xiàn)的概率;為T不出現(xiàn)時(shí)Ci出現(xiàn)的概率.

1.2 C4.5 決策樹

文中選用目前廣泛應(yīng)用于分類、檢索的C4.5決策樹算法進(jìn)行分類［11-14］，該算法根據(jù)信息增益率來選擇屬性，從一個(gè)無次序、無規(guī)則的實(shí)例集合中歸納出一組采用樹形結(jié)構(gòu)表示的分類規(guī)則［15］.以文中選擇的最大信息增益n-gram屬性為例:已知樣本集D{X1，X2，…，Xn}，假定類別屬性具有 m 個(gè)不同的值，根據(jù)類別屬性取值的不同可以將D劃分為m個(gè)子集{D1，D2，…，Dm}.由此可以得出樣本集 D 對分類的平均信息量為

則利用屬性A對D進(jìn)行劃分的信息增益等于使用A對D進(jìn)行劃分前后不確定性下降的程度，即信息增益

由于信息增益傾向于選擇具有大量值的屬性，但某些屬性(例如充當(dāng)唯一標(biāo)識的屬性)雖具有最高的信息增益，卻對分類沒有用.為了克服這種偏奇，C4.5決策樹采用信息增益率作為屬性選擇的依據(jù).信息增益率的計(jì)算公式為

1.3 Boosting技術(shù)

決策樹是一種不夠穩(wěn)定的分類方法，訓(xùn)練集的小范圍變動(dòng)就可能造成分類模型的顯著變化.為了提高決策樹分類的穩(wěn)定性，可以利用不同的訓(xùn)練集構(gòu)造多個(gè)分類模型，先由每個(gè)模型獨(dú)立做出決策，再通過綜合打分的方法得到最終結(jié)果.

Boosting的思想是對每個(gè)樣本賦予一個(gè)相同的初始權(quán)重，在此后的迭代過程中不斷調(diào)整權(quán)重.整個(gè)過程進(jìn)行k次迭代，每次迭代首先根據(jù)樣本的權(quán)重構(gòu)造訓(xùn)練集，權(quán)重越大的樣本出現(xiàn)在訓(xùn)練集中的概率越高.然后，利用訓(xùn)練集構(gòu)造決策樹，找出不符合決策樹模型的例外樣本，加大它們的權(quán)重，使得下一次的迭代更加關(guān)注這些樣本.同時(shí)對每個(gè)模型賦予一個(gè)權(quán)重，表示模型對決策的影響因子，該值與模型的錯(cuò)誤率成反比，也就是說，模型對訓(xùn)練集的錯(cuò)誤率越低，它的權(quán)重就越大，對決策的結(jié)果就越重要.Boosting的過程描述如下.

(1)訓(xùn)練過程.

{輸入:訓(xùn)練數(shù)據(jù)T，樣本數(shù)n，迭代次數(shù)k.

輸出:決策樹序列 α1，α2，…，αk.

根據(jù)樣本權(quán)重，從T中抽取樣本集Ti;

根據(jù)樣本集得到模型αi;

計(jì)算模型αi的錯(cuò)誤率ε(i);

(2)決策過程.

{輸入:測試數(shù)據(jù) γ，決策樹序列 α1，α2，…，αk.

輸出:預(yù)測類別 α(γ).

根據(jù)αi判斷γ的類別，結(jié)果為αi(γ);

end for

根據(jù)模型的權(quán)值統(tǒng)計(jì)每個(gè)類別的得票，得票最高的就是α(γ)}

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

為了驗(yàn)證方法的有效性，文中采用真實(shí)的嵌入型惡意代碼作為實(shí)驗(yàn)數(shù)據(jù).從VX Heavens［16］上收集了Word、Excel和PPT 3種類型的惡意文檔共3173個(gè)，收集了正常文檔760個(gè)，所有正常文檔均為本研究所日常交流所用文檔.實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息見表1.

表1 實(shí)驗(yàn)數(shù)據(jù)Table 1 Experimental data

圖1 3-gram屬性分布圖Fig.1 Distribution of 3-gram attributes

3 實(shí)驗(yàn)分析

3.1 評估策略

在惡意代碼檢測中，通常采用檢測率(TP)即正確分類的惡意代碼數(shù)與惡意代碼總數(shù)的比值和誤檢率(FP)即正常文件被認(rèn)定為惡意代碼數(shù)與正常文件總數(shù)的比值來評價(jià)檢測方法的優(yōu)劣.分類準(zhǔn)確率(ACC)也被應(yīng)用到檢測算法優(yōu)劣的評估中，其為正確分類的樣本數(shù)與所有測試樣本數(shù)的比值.

3.2 有效性驗(yàn)證

為驗(yàn)證文中提出的方法的有效性，首先選擇了惡意文檔274個(gè)(其中Word 131個(gè)，Excel 131個(gè)，PPT 12個(gè))，正常文檔236個(gè)(其中Word 123個(gè)，Excel 95個(gè)，PPT 18個(gè))，進(jìn)行特征提取和分類測試.3種類型文檔測試均采用10次迭代，建立10棵決策樹，采用10折交叉驗(yàn)證，測試結(jié)果見表2.

表2 小規(guī)模數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 2 Experimental results in the small data set %

由表2可見，所提出的Boosting C4.53-gram信息增益法適用于嵌入型惡意代碼檢測，并具有很高的檢測率和分類準(zhǔn)確率.其中對Word文檔的檢測率為100%.對PPT文檔的檢測率稍低為91.70%，這主要是因?yàn)閰⑴c測試的樣本數(shù)太少，不能很好地展現(xiàn)分類效果.實(shí)際上在對PPT文檔的檢測中，惡意文檔和正常文檔均只有1個(gè)被錯(cuò)誤分類.

接下來分別采用從上述3類文檔中提取的500個(gè)3-gram作為屬性，計(jì)算所有3346個(gè)Word文檔、458個(gè)Excel文檔和129個(gè)PPT文檔的屬性值，采用上述的10棵決策樹序列對這些文檔進(jìn)行測試，結(jié)果見表3.

表3 大規(guī)模數(shù)據(jù)集實(shí)驗(yàn)結(jié)果Table 3 Experimental results in the large data set %

由表3可以看出，僅采用少量樣本提取的500個(gè)屬性建立的決策樹，對3類文檔均具有較高的檢測率.由表2、3可知，Boosting C4.5 n-gram信息增益法適用于嵌入型惡意代碼檢測，而且通過預(yù)先提取的屬性特征可以實(shí)現(xiàn)對未知惡意代碼的準(zhǔn)確檢測.

3.3 檢測結(jié)果比較

采用Markov 2-gram熵率法、High-order 5-gram模型法、C4.53-gram信息增益法以及Boosting C4.53-gram信息增益法對表1列出的數(shù)據(jù)集進(jìn)行測試，比較各種方法的檢測結(jié)果.對于High-order 5-gram模型法，僅采用對整篇文檔建模的方法，因?yàn)榉侄文Ｐ偷臋?quán)值大小對檢測結(jié)果有很大影響，對于不同的測試數(shù)據(jù)檢測結(jié)果差異較大.表4示出了各種方法的檢測結(jié)果，所列結(jié)果均為10折交叉驗(yàn)證的結(jié)果.

表4 4種方法的檢測結(jié)果Table 4 Test results of the four methods %

從表4可以看出，Markov 2-gram熵率法對3種類型文檔的檢測率都在60%左右，而且都有很高的誤檢率.因此，Markov 2-gram熵率法并不適用于這3類文檔的嵌入型惡意代碼檢測.與 High-order 5-gram模型法相比，C4.53-gram信息增益法和Boosting C4.53-gram方法對Word文檔和Excel文檔的檢測率均有明顯提升.兩種決策樹方法對Word文檔的檢測率均為99.80%，但由于Boosting技術(shù)的運(yùn)用使C4.5決策樹的誤檢率由2.20%降低到1.70%，同時(shí)分類準(zhǔn)確率也有所提高;而對Excel文檔的檢測卻出現(xiàn)了相反的結(jié)果，采用Boosting技術(shù)的決策樹檢測率低于未采用Boosting的決策樹，誤檢率高于未采用Boosting的決策樹.其原因?yàn)?，Boosting技術(shù)雖然可以在一定程度上提高決策樹分類的穩(wěn)定性，但它有時(shí)也會存在過擬合的情況，導(dǎo)致分類準(zhǔn)確率的降低.

由于收集的惡意PPT文檔數(shù)量較少，High-order 5-gram模型法、C4.53-gram信息增益法和Boosting C4.53-gram信息增益法對PPT文檔得到了同樣的檢測率，都有2個(gè)惡意文檔被誤認(rèn)為正常文檔.但Boosting C4.53-gram信息增益法的誤檢率要明顯低于High-order 5-gram模型法和C4.53-gram信息增益法.更重要的是在分類準(zhǔn)確率方面，Boosting C4.53-gram信息增益法要高于High-order 5-gram模型法和C4.53-gram信息增益法.說明 Boosting C4.53-gram信息增益法可以對未知樣本進(jìn)行更準(zhǔn)確的分類.

4 結(jié)語

針對嵌入型惡意代碼這種新興的計(jì)算機(jī)安全威脅.文中在分析了以往統(tǒng)計(jì)分析方法不足的基礎(chǔ)上提出采用C4.5決策樹的機(jī)器學(xué)習(xí)方法進(jìn)行嵌入型惡意代碼檢測，該方法通過從訓(xùn)練樣本中提取的500個(gè)具有最大信息增益的3-gram作為屬性特征，實(shí)現(xiàn)了高檢測率和高分類準(zhǔn)確率;該方法通過對少量樣本的學(xué)習(xí)，即可實(shí)現(xiàn)對未知嵌入型惡意代碼的準(zhǔn)確檢測，在檢測率和分類準(zhǔn)確率方面與以往的檢測方法Markov 2-gram和High-order 5-gram相比有明顯優(yōu)勢.

［1］ Stolfo S J，Wang K，Li W J.Towards stealthy malware detection［M］∥Malware detection.Heidelberg:Springer-Verlag，2007:231-249.

［2］ Li W J，Stolfo S J，Stavrou A，et al.A study of malcodebearing documents［C］∥Proceedings of the 4th International Conference on Detection of Intrusions and Malware，and Vulnerability Assessment.Heidelberg:Springer-Verlag，2007:231-250.

［3］ Shafiq M Z，Khayam S A，F(xiàn)arooq M.Embedded malware detection using Markov n-grams［C］∥Proceedings of the 5th International Conference on Detection of Intrusions and Malware，and Vulnerability Assessment.Heidelberg:Springer-Verlag，2008:88-107.

［4］ John Leyden.Trojan exploits unpatched Word vulnerability［EB/OL］.(2006-05-22)［2010-05-28］.http:∥www.theregister.co.uk/2006/05/22/trojan_exploit_word_vuln/.

［5］ Joris Evers.Zero-day attacks continue to hit Microsoft［EB/OL］.(2006-09-28)［2010-05-28］.http:∥news.cnet.com/Zero-day-attacks-continue-to-hit-Microsoft/2100-7349_3-6120481.html.

［6］ David Kierznowski.Backdooring PDF files ［EB/OL］.(2006-09-13)［2010-05-28］.http:∥michaeldaw.org/md-hacks/backdooring-pdf-files.

［7］ Damashek M.Gauging similarity with n-grams:languageindependent categorization of text［J］.Science，1995，267(5199):843-848.

［8］ Grossman D A，F(xiàn)rieder O.Information retrieval:algorithms and heuristics［M］.2nd ed.Heidelberg:Springer-Verlag，2004.

［9］ Dumais S，Platt J，Heckerman D，et al.Inductive learning algorithms and representations for text categorization［C］∥Proceedings of the 7th International Conference on Information and Knowledge Management.New York:ACM Press，1998:148-155.

［10］ Kolter J Z，Maloof M A.Learning to detect malicious executables in the wild［C］∥Proceedings of the International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2004:470-478.

［11］ Garcia S，F(xiàn)ernandez A，Herrera F.Enhancing the effectiveness and interpretability of decision tree and rule induction classifiers with evolutionary training set selection over imbalanced problems［J］.Applied Soft Computing，2009，9(4):1304-1314.

［12］ Conway M，Doan S，Kawazoe A，et al.Classifying disease outbreak reports using n-grams and semantic features［J］.International Journal of Medical Informatics，2009，78(12):47-58.

［13］ 閔華清，盧炎生，蔣曉宇.基于共同進(jìn)化計(jì)算的分類規(guī)則算法［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2006，34(6):69-73.Min Hua-qing，Lu Yan-sheng，Jiang Xiao-yu.Algorithm of classification rules based on co-evolution computation［J］.Journal of South China University of Technology:Natural Science Edition，2006，34(6):69-73.

［14］ Tso B，Tseng J L.Multi-resolution semantic-based imagery retrieval using hidden Markov models and decision trees［J］.Expert Systems with Applications，2010，37(6):4425-4434.

［15］ 徐鵬，林森.基于C4.5決策樹的流量分類方法［J］.軟件學(xué)報(bào)，2009，20(10):2692-2704.Xu Peng，Lin Sen.Internet traffic classification using C4.5 decision tree ［J］.Journal of Software，2009，20(10):2692-2704.

［16］ VX Heavens.Computer virus collection ［DB/OL］.(2007-09-14)［2010-05-28］.http:∥vx.netlux.org/vl.php.