C4.5 算法在未知惡意代碼識別中的應用

朱立軍，徐玉芬

(1.沈陽化工大學 計算機科學與技術學院，遼寧 沈陽 110142;2.遼寧兵器工業職工大學，遼寧 沈陽 110045)

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

文獻［6－7］采用的識別方法誤判率和漏報率高的一個主要原因是:由于該方法沒有考慮到惡意代碼所調用的API 之間實際上還存在著某些密切關聯這一事實，鑒于此，本文采用K 長度的滑動窗口來提取API 調用序列作為惡意代碼的特征屬性，并以此建立起所有訓練樣本的特征向量，采用決策樹C4.5 算法建立一棵決策樹，并生成決策規則，這些規則就是判斷代碼是否為惡意的依據.實驗表明，該方法與文獻［6－7］所采用的方法相比有著較低的誤報率和漏報率.

1 動態惡意代碼行為的捕獲

1.1 惡意代碼的主機行為

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

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

表1 部分監控API 函數調用表Table 1 Part of API function calls

1.2 特征的生成

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

圖1 K=4 的滑動窗口示意圖Fig.1 Sliding window schematic diagram of K=4

試驗樣本共849 個，按照這種方式提取長度為4 的數字串，一共可得9 948 個互不相同的數字串，作為代碼的特征屬性.

1.3 數據模型的建立

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

表2 特征向量統計表Table 2 Feature vector of samples

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

2.1 C4.5 算法概述［9］

C4.5 分類算法是決策樹分類算法的一種，是從ID3 決策樹分類算法發展而來，其基本思路如下:

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

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

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

給出.相應地得到 關于屬性A 的信息增益比例值由公式

給出.其中，

C4.5 算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合S 的測試屬性.對被選取的測試屬性創建一個結點，并以該屬性標記，對該屬性的每個值創建一個分支，并據此劃分樣本.以此類推，可以通過計算信息增益和選取當前最大的信息增益屬性來擴展樹，直到得到最終的決策樹.一旦樹被建立，就可以把樹轉換成if-then 規則，一個規則就對應從樹根到葉子之間的一個路徑，表示依據所給屬性進行分類決策的過程.

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

本算法采用遞歸方法生成決策樹(用C++語言實現).算法主要步驟為:

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

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

(3)創建一個結點node，結點data 域存放當前具有最大信息增益比例屬性在infor 數組中的列序號.

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

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

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

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

構造好的決策樹如圖2 所示.

圖2 構造的決策樹局部示意圖Fig.2 Partial schematic diagram of decision tree constructed

非葉子結點中的數表示屬性的序列號.葉子結點－1 表示是合法程序，－2 表示的惡意程序.邊上的值表示對應結點屬性的值.

2.3 決策樹規則的生成及對未知樣本的分類

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

3 實驗結果及分析

為評價算法性能，引入如下相關概念［8］:

真陽性TP:黑樣本被檢測為黑樣本的數目;

假陽性FP:白樣本被檢測為黑樣本的數目;

真陰性TN:白樣本被檢測為白樣本的數目;

假陰性FN:黑樣本被檢測為白樣本的數目;

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

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

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

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

實驗樣本共849 個，其中白名單-合法程序樣本是在Windows XP Professional 操作系統首次安裝，能確保在干凈的系統環境下選取的操作系統PE 文件404 個;黑名單-惡意代碼樣本通過網絡及其他途徑搜集總共445 個.將殺毒軟件升級到最新并對這些惡意代碼病毒進行查殺，確認都是惡意代碼病毒.

為防止惡意代碼對系統的破壞，在虛擬機環境下分析惡意代碼的動態行為.實驗平臺操作系統采用Windows XP Professional，虛擬機采用Vmware Workstation 6.0.使用ApiMonitorTrial工具軟件對代碼運行時API 函數的調用情況進行捕獲.

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

綜合所述，基于決策樹C4.5 分類算法較其他2 種分類算法有較明顯的優勢.

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

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

4 結論

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

［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］張小康，帥建梅，史林.基于加權信息增益的惡意代碼檢測方法［J］.計算機工程，2010，36(6):149－151.

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

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

［8］朱立軍.基于動態行為的未知惡意代碼識別方法［J］.沈陽化工大學學報，2012，26(1):77－80.

［9］毛國君，段立娟，王實，等.數據挖掘原理與算法［M］.北京:清華大學出版社，2005:115－123.