C4.5 算法在未知惡意代碼識(shí)別中的應(yīng)用

朱立軍，徐玉芬

(1.沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 沈陽(yáng) 110142;2.遼寧兵器工業(yè)職工大學(xué)，遼寧 沈陽(yáng) 110045)

目前，主流殺毒軟件采用的技術(shù)是特征碼技術(shù)，其原理是在待檢測(cè)文件中查找二進(jìn)制代碼特征，如果與既有特征碼相匹配就判定為病毒程序.其優(yōu)點(diǎn)是能快速、準(zhǔn)確地檢測(cè)出已知惡意代碼;缺點(diǎn)是對(duì)變種及未知惡意代碼無(wú)能為力.文獻(xiàn)［1－2］已經(jīng)證明對(duì)計(jì)算機(jī)病毒的檢測(cè)不可判定.因此，目前對(duì)于未知惡意代碼的識(shí)別，就是采用近似算法，包括兩類:(1)靜態(tài)啟發(fā)式掃描技術(shù).其原理是在代碼不運(yùn)行時(shí)，通過(guò)分析代碼中的特征序列來(lái)識(shí)別惡意代碼的方法，如文獻(xiàn)［3］通過(guò)分析可執(zhí)行文件靜態(tài)調(diào)用的API 序列來(lái)識(shí)別已知惡意代碼的變種，它的依據(jù)是惡意代碼和它的變種一定有足夠多相似的API 調(diào)用序列.文獻(xiàn)［4］是提取已知惡意代碼中的特征字節(jié)序列，采用多重貝葉斯算法建立分類模型.文獻(xiàn)［5］提出一種基于加權(quán)信息增益的特征選擇方法，該方法綜合考慮特征頻率和信息增益的作用，能夠更加準(zhǔn)確地選取有效特征，從而提高檢測(cè)性能.如上靜態(tài)技術(shù)雖然對(duì)未知惡意代碼識(shí)別的誤判率和漏報(bào)率都較低，但其缺點(diǎn)是無(wú)法識(shí)別被加殼的惡意代碼;(2)基于代碼的動(dòng)態(tài)行為分析法.與靜態(tài)掃描技術(shù)不同的是，行為分析技術(shù)監(jiān)控代碼運(yùn)行時(shí)的動(dòng)態(tài)行為，由于某些行為是病毒、木馬等惡意代碼經(jīng)常出現(xiàn)的行為，而在合法程序中卻比較罕見(jiàn)，它們可作為判別應(yīng)用程序是否非法的依據(jù).文獻(xiàn)［6］提出一種基于API 調(diào)用為特征向量并采用貝葉斯分類器來(lái)識(shí)別惡意代碼的方法.文獻(xiàn)［7］采用一種基于API 調(diào)用為特征向量的最小距離分類器來(lái)識(shí)別惡意代碼的方法.這些動(dòng)態(tài)識(shí)別方法的優(yōu)點(diǎn)是簡(jiǎn)單、高效，可檢測(cè)出未知惡意代碼而不用擔(dān)心是否該代碼被加殼，但缺點(diǎn)是誤判率和漏報(bào)率較高.

文獻(xiàn)［6－7］采用的識(shí)別方法誤判率和漏報(bào)率高的一個(gè)主要原因是:由于該方法沒(méi)有考慮到惡意代碼所調(diào)用的API 之間實(shí)際上還存在著某些密切關(guān)聯(lián)這一事實(shí)，鑒于此，本文采用K 長(zhǎng)度的滑動(dòng)窗口來(lái)提取API 調(diào)用序列作為惡意代碼的特征屬性，并以此建立起所有訓(xùn)練樣本的特征向量，采用決策樹(shù)C4.5 算法建立一棵決策樹(shù)，并生成決策規(guī)則，這些規(guī)則就是判斷代碼是否為惡意的依據(jù).實(shí)驗(yàn)表明，該方法與文獻(xiàn)［6－7］所采用的方法相比有著較低的誤報(bào)率和漏報(bào)率.

1 動(dòng)態(tài)惡意代碼行為的捕獲

1.1 惡意代碼的主機(jī)行為

目前最為流行、破壞力最大的惡意代碼就是Win32 PE 病毒，PE (Portable Executables)是win32 系統(tǒng)中可執(zhí)行程序的二進(jìn)制文件形式，它是通過(guò)調(diào)用操作系統(tǒng)中的API 函數(shù)(應(yīng)用程序接口)來(lái)實(shí)現(xiàn)各項(xiàng)功能，而這些API 函數(shù)則依據(jù)功能來(lái)自不同的動(dòng)態(tài)鏈接庫(kù)(DLL).所以，以PE文件為存在形式的病毒在完成植入、控制和傳播等任務(wù)時(shí)都必須借助API 函數(shù)的調(diào)用［8］.

實(shí)踐表明:與運(yùn)行階段相比，惡意代碼病毒在植入、安裝階段會(huì)表現(xiàn)出顯著的有別于一般合法程序的一系列行為特征，如自刪除、自我復(fù)制、殺進(jìn)程、設(shè)置自啟動(dòng)、感染EXE 文件等.因此，捕獲惡意代碼在植入、安裝階段的API 函數(shù)調(diào)用，就捕獲到了相應(yīng)惡意代碼的動(dòng)態(tài)行為.根據(jù)對(duì)惡意代碼和合法程序運(yùn)行時(shí)調(diào)用API 函數(shù)情況的觀察，試驗(yàn)選取141 個(gè)較敏感的API 函數(shù)作為監(jiān)控對(duì)象，部分API 函數(shù)如表1 所示［8］.

表1 部分監(jiān)控API 函數(shù)調(diào)用表Table 1 Part of API function calls

1.2 特征的生成

把待監(jiān)測(cè)的141 個(gè)API 函數(shù)編號(hào)(1～141)，在虛擬機(jī)里面運(yùn)行所有的惡意樣本和正常樣本，提取所有樣本程序在植入、安裝階段調(diào)用的相關(guān)API 函數(shù).這樣每個(gè)樣本就可表示成一個(gè)由一系列數(shù)字組成的串，每個(gè)數(shù)字表示所調(diào)用的API 函數(shù)編號(hào).因?yàn)閻阂獯a在植入、安裝階段有很多區(qū)別于正常代碼的行為，這些行為就表現(xiàn)在一些特定的API 函數(shù)調(diào)用的特殊排列次序上，如典型的病毒在植入、安裝階段的行為次序是:(1)隱藏運(yùn)行，將自身移動(dòng)到系統(tǒng)目錄;(2)修改注冊(cè)表相關(guān)鍵值;(3)遍歷所有硬盤生成Autorun.inf 文件.相應(yīng)地調(diào)用的API 函數(shù)依次為GetSystemDirectory ()，CopyFile ()，RegOpen-KeyEx()，RegSetValueEx()，RegCloseKey()，RegCreateKeyEx ()，RegSetValueEx ()，Reg-CloseKey()，SetFileAttributes()，CopyFile().這一按特定次序排列的調(diào)用序列就可作為檢測(cè)代碼是否為“惡意”的標(biāo)志.盡管不同的惡意代碼在植入、安裝階段的行為有些差異，但它們很多“惡意行為”仍然很相似，這是能夠發(fā)現(xiàn)它們蛛絲馬跡的依據(jù).為能充分提取代碼的行為特征，使用一個(gè)K 長(zhǎng)度的滑動(dòng)窗口來(lái)提取K 長(zhǎng)度的數(shù)字串，窗口每次移動(dòng)一位，這樣就可把一個(gè)代碼樣本的特征表示成一系列K 長(zhǎng)度的數(shù)字串，如圖1 所示.綜合精度和性能的考慮，選取K 的長(zhǎng)度為4.

圖1 K=4 的滑動(dòng)窗口示意圖Fig.1 Sliding window schematic diagram of K=4

試驗(yàn)樣本共849 個(gè)，按照這種方式提取長(zhǎng)度為4 的數(shù)字串，一共可得9 948 個(gè)互不相同的數(shù)字串，作為代碼的特征屬性.

1.3 數(shù)據(jù)模型的建立

惡意代碼檢測(cè)實(shí)際是一個(gè)二值分類問(wèn)題，即惡意代碼與合法代碼，對(duì)這兩類樣本的特征屬性調(diào)用統(tǒng)計(jì)結(jié)果采用二維表形式，如表2 所示.表2 中每個(gè)數(shù)據(jù)元組X=(x1，x2，…，xn，c)記為一個(gè)樣本的特征向量，其中xi(i=1，2，…，n)表示特征向量中的一個(gè)特征屬性，xi∈{0，1}，0 表示某個(gè)特征屬性一次都沒(méi)有被該樣本調(diào)用過(guò)，1 表示某個(gè)特征屬性被該樣本調(diào)用過(guò)1 次或多次.c表示類別，c∈{0，1}，1 代表黑名單樣本，0 代表白名單樣本.

表2 特征向量統(tǒng)計(jì)表Table 2 Feature vector of samples

2 基于C4.5 算法的未知惡意代碼識(shí)別算法

2.1 C4.5 算法概述［9］

C4.5 分類算法是決策樹(shù)分類算法的一種，是從ID3 決策樹(shù)分類算法發(fā)展而來(lái)，其基本思路如下:

設(shè)S 是s 個(gè)數(shù)據(jù)樣本的集合.假定類標(biāo)號(hào)屬性具有m 個(gè)不同值，定義m 個(gè)不同類Ci(i=1，2，…，m).設(shè)si是類Ci中的樣本數(shù).對(duì)一個(gè)給定的樣本分類所需的期望信息由公式

給出.其中，pi是任意樣本屬于Ci的概率，一般可用si/s 來(lái)估計(jì)，對(duì)數(shù)函數(shù)以2 為底.設(shè)屬性A 具有v 個(gè)不同值{a1，a2，…，av}.可以用屬性A 將S劃分為v 個(gè)子集{S1，S2，…，SV}，其中Sj包含S 中這樣一些樣本，它們?cè)贏 上具有值aj.如果A 作為測(cè)試屬性(即最好的分裂屬性).則這些子集對(duì)應(yīng)于由包含集合S 的結(jié)點(diǎn)生長(zhǎng)出來(lái)的分支.設(shè)sij是子集Sj中類Ci的樣本數(shù).根據(jù)由A 劃分成子集的熵E(A)由公式

由期望信息和熵值可以得到對(duì)應(yīng)的信息增益比例值.對(duì)于在A 上分支將獲得的信息增益可由公式

給出.相應(yīng)地得到 關(guān)于屬性A 的信息增益比例值由公式

給出.其中，

C4.5 算法計(jì)算每個(gè)屬性的信息增益，并選取具有最高增益的屬性作為給定集合S 的測(cè)試屬性.對(duì)被選取的測(cè)試屬性創(chuàng)建一個(gè)結(jié)點(diǎn)，并以該屬性標(biāo)記，對(duì)該屬性的每個(gè)值創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本.以此類推，可以通過(guò)計(jì)算信息增益和選取當(dāng)前最大的信息增益屬性來(lái)擴(kuò)展樹(shù)，直到得到最終的決策樹(shù).一旦樹(shù)被建立，就可以把樹(shù)轉(zhuǎn)換成if-then 規(guī)則，一個(gè)規(guī)則就對(duì)應(yīng)從樹(shù)根到葉子之間的一個(gè)路徑，表示依據(jù)所給屬性進(jìn)行分類決策的過(guò)程.

2.2 基于C4.5 的未知惡意代碼識(shí)別算法

本算法采用遞歸方法生成決策樹(shù)(用C++語(yǔ)言實(shí)現(xiàn)).算法主要步驟為:

(1)把訓(xùn)練樣本特征屬性向量輸入到二維數(shù)組infor 中.

(2)計(jì)算infor 數(shù)組中每個(gè)屬性的信息增益比例，確定具有最大信息增益比例的屬性.

(3)創(chuàng)建一個(gè)結(jié)點(diǎn)node，結(jié)點(diǎn)data 域存放當(dāng)前具有最大信息增益比例屬性在infor 數(shù)組中的列序號(hào).

(4)在數(shù)組infor 中把由第(2)步確定的最大信息增益列的值全部賦成－1，意味著以后計(jì)算剩余屬性的最大信息增益時(shí)不考慮該列.

(5)根據(jù)第(2)步確定的最大信息增益列的列值，把infor 數(shù)組分成上下2 部分，上部分所有向量該列列值為1，下部分所有向量該列列值為0.

(6)分別對(duì)重新劃分的2 個(gè)子數(shù)組重復(fù)采用(2)、(3)、(4)、(5)步驟進(jìn)行遞歸，分別得到2個(gè)子數(shù)組中具有最大信息增益比例的屬性，分別作為node 結(jié)點(diǎn)左右孩子結(jié)點(diǎn)date 域的值.

(7)當(dāng)發(fā)現(xiàn)重新劃分的子數(shù)組中，所有向量全部是白名單樣本，則data 域標(biāo)記為－1，遞歸結(jié)束;如果所有向量全部為黑名單樣本，則data域標(biāo)記為－2，遞歸結(jié)束;如果子數(shù)組中只有一列數(shù)據(jù)可用，則如果該子數(shù)組中白名單樣本占的比例大，則data 域值為－1，否則為－2，遞歸結(jié)束.

構(gòu)造好的決策樹(shù)如圖2 所示.

圖2 構(gòu)造的決策樹(shù)局部示意圖Fig.2 Partial schematic diagram of decision tree constructed

非葉子結(jié)點(diǎn)中的數(shù)表示屬性的序列號(hào).葉子結(jié)點(diǎn)－1 表示是合法程序，－2 表示的惡意程序.邊上的值表示對(duì)應(yīng)結(jié)點(diǎn)屬性的值.

2.3 決策樹(shù)規(guī)則的生成及對(duì)未知樣本的分類

從決策樹(shù)的頂點(diǎn)到葉子結(jié)點(diǎn)的一條路徑就是一個(gè)決策規(guī)則，所有從頂點(diǎn)到葉子結(jié)點(diǎn)的路徑就是該決策樹(shù)的分類規(guī)則.例如:某個(gè)樣本的特征向量X，其中x100=0，x53=0，x135=0，x59=1，x64=1.則對(duì)應(yīng)分類規(guī)則路徑是100—53—135—59—64—－1，則該樣本為合法代碼;如果某個(gè)樣本的特征向量X，其中x100=1，x45=0，x122=1，x47=0.則對(duì)應(yīng)分類規(guī)則路徑是100—45—122—47—－2，則該樣本為惡意代碼.

3 實(shí)驗(yàn)結(jié)果及分析

為評(píng)價(jià)算法性能，引入如下相關(guān)概念［8］:

真陽(yáng)性TP:黑樣本被檢測(cè)為黑樣本的數(shù)目;

假陽(yáng)性FP:白樣本被檢測(cè)為黑樣本的數(shù)目;

真陰性TN:白樣本被檢測(cè)為白樣本的數(shù)目;

假陰性FN:黑樣本被檢測(cè)為白樣本的數(shù)目;

檢出率:TPR=TP/(TP+FN);

誤報(bào)率:FPR=FP/(FP+TN);

正確率:ACY=(TP +TN)/(TP +TN +FP+FN).

Youden 指數(shù)=TPR-FPR，其中Youden 指數(shù)的取值范圍為(－1，1)之間，其值越接近于+1，就意味著該檢測(cè)模型的判別準(zhǔn)確性越好.

實(shí)驗(yàn)樣本共849 個(gè)，其中白名單-合法程序樣本是在Windows XP Professional 操作系統(tǒng)首次安裝，能確保在干凈的系統(tǒng)環(huán)境下選取的操作系統(tǒng)PE 文件404 個(gè);黑名單-惡意代碼樣本通過(guò)網(wǎng)絡(luò)及其他途徑搜集總共445 個(gè).將殺毒軟件升級(jí)到最新并對(duì)這些惡意代碼病毒進(jìn)行查殺，確認(rèn)都是惡意代碼病毒.

為防止惡意代碼對(duì)系統(tǒng)的破壞，在虛擬機(jī)環(huán)境下分析惡意代碼的動(dòng)態(tài)行為.實(shí)驗(yàn)平臺(tái)操作系統(tǒng)采用Windows XP Professional，虛擬機(jī)采用Vmware Workstation 6.0.使用ApiMonitorTrial工具軟件對(duì)代碼運(yùn)行時(shí)API 函數(shù)的調(diào)用情況進(jìn)行捕獲.

實(shí)驗(yàn)采用10 次交叉驗(yàn)證的方法，并與樸素貝葉斯算法和基于標(biāo)準(zhǔn)化歐式距離的最小距離分類器算法進(jìn)行比較.實(shí)驗(yàn)結(jié)果如圖3 和表3 所示.由圖3 可知，基于決策樹(shù)C4.5 算法的Youden 指數(shù)的均值(0.775 4)不但高于樸素貝葉斯(0.303 9)和最小距離分類器(0.408 3)兩個(gè)算法，且通過(guò)計(jì)算可知C4.5 算法10 次交叉試驗(yàn)Youden 指數(shù)的方差(0.017)遠(yuǎn)遠(yuǎn)低于樸素貝葉斯(0.047)和最小距離分類器(0.098)的方差，所以C4.5 算法的穩(wěn)定性較其他2 種算法也較好.由表3 可知，雖然最小距離分類器的檢出率(93.60 %)是最高的，但是它的誤報(bào)率(52.77 %)也是最高的.從3 者的檢出率來(lái)看，基于決策樹(shù)C4.5 算法達(dá)到了88.70 %，明顯高于其他2 種算法.

綜合所述，基于決策樹(shù)C4.5 分類算法較其他2 種分類算法有較明顯的優(yōu)勢(shì).

圖3 3 種算法10 次交叉驗(yàn)證Youden 指數(shù)的比較Fig.3 Three algorithms ten times cross-validation Youden index comparison

表3 3 種分類識(shí)別算法10 次交叉驗(yàn)證均值比較Table 3 Ten times cross-validation mean comparison of the three classifications recognition algorithm

4 結(jié)論

采用定長(zhǎng)的滑動(dòng)窗口提取代碼的特征屬性，樣本越多，生成的特征屬性就相應(yīng)越多.這樣，所有樣本的特征向量組成的二維表就是一個(gè)列行之比較大的稀疏矩陣，通過(guò)對(duì)比試驗(yàn)表明:對(duì)基于這類稀疏矩陣的二值分類問(wèn)題，采用決策樹(shù)C4.5 算法比采用樸素貝葉斯和最小距離分類器算法有著較明顯的優(yōu)勢(shì).

［1］Fred Cohen.Computer Viruses:Theory and Experiments［J］.Computers＆Security，1987，6(1):22－35.

［2］Diomidis Spinellis.Reliable Identification of Bounded-lengh Viruses is NP-complete［J］.IEEE Transactions on Information Theory，2003，49(1):280－284.

［3］Xu Jianyun，Sung Andrew H，Mukkamala Srinivas，et al.Obfuscated MaliciousExecutable Scanner［J］.Journal of Research and Practice in Information Technology，2007，39(3):181－197.

［4］Schultzm G，Eskin E，Zadok E，et al.DataminingMethodsfor Detection of New Malicious Executables［C］// Proceedings of the 2001 IEEE Symposium on Security and Privacy.Washington:IEEE ComputerSociety，2001:38－49.

［5］張小康，帥建梅，史林.基于加權(quán)信息增益的惡意代碼檢測(cè)方法［J］.計(jì)算機(jī)工程，2010，36(6):149－151.

［6］張波云，殷建平，蒿敬波，等.基于多重樸素貝葉斯算法的未知病毒檢測(cè)［J］.計(jì)算機(jī)工程，2006，32(10):18－21.

［7］張茜，邵堃，劉磊.一種基于最小距離分類器的惡意代碼檢測(cè)方法［J］.廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2009，27(3):183－187.

［8］朱立軍.基于動(dòng)態(tài)行為的未知惡意代碼識(shí)別方法［J］.沈陽(yáng)化工大學(xué)學(xué)報(bào)，2012，26(1):77－80.

［9］毛國(guó)君，段立娟，王實(shí)，等.數(shù)據(jù)挖掘原理與算法［M］.北京:清華大學(xué)出版社，2005:115－123.