劉 星，唐 勇

(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院，湖南 長沙 410073)

惡意代碼的函數(shù)調(diào)用圖相似性分析

劉 星，唐 勇

(國防科學(xué)技術(shù)大學(xué)計算機學(xué)院，湖南 長沙 410073)

惡意代碼的相似性分析是當(dāng)前惡意代碼自動分析的重要部分。提出了一種基于函數(shù)調(diào)用圖的惡意代碼相似性分析方法，通過函數(shù)調(diào)用圖的相似性距離SDMFG來度量兩個惡意代碼函數(shù)調(diào)用圖的相似性，進而分析得到惡意代碼的相似性，提高了惡意代碼相似性分析的準(zhǔn)確性，為惡意代碼的同源及演化特性分析研究與惡意代碼的檢測和防范提供了有力支持。

惡意代碼；函數(shù)調(diào)用圖；圖的相似性距離；指令序列；最大權(quán)匹配

1 引言

惡意代碼分析是檢測和防范惡意代碼的重要基礎(chǔ)。隨著基于蜜罐技術(shù)的惡意代碼自動捕獲器及大量惡意代碼樣本上傳網(wǎng)站的建立，惡意代碼樣本的捕獲已不存在技術(shù)困難，關(guān)鍵問題是如何對數(shù)量呈海量化趨勢的惡意代碼樣本進行自動、及時和準(zhǔn)確的分析。

惡意代碼的相似性分析是當(dāng)前惡意代碼自動分析的重要部分?，F(xiàn)有的惡意代碼相似性分析方法要么過多地關(guān)注于惡意代碼的byte級特征，如Kolter J Z和Maloof M A[1]提出用byte代碼的n-gram作為特征對惡意代碼進行分類；要么過于關(guān)注惡意代碼的函數(shù)調(diào)用圖的結(jié)構(gòu)，比如文獻[2]提出了一種用圖的編輯距離來度量兩個惡意代碼函數(shù)調(diào)用圖的相似性的分析方法。

鑒于這些方法的缺陷和不足，本文提出了一種用圖的相似性距離來度量兩個惡意代碼函數(shù)調(diào)用圖的相似性的分析方法，該方法考慮了惡意代碼中函數(shù)的指令級信息以及函數(shù)之間的調(diào)用關(guān)系信息。

文章組織結(jié)構(gòu)如下：第2節(jié)是文章的主要內(nèi)容，2.1節(jié)介紹了函數(shù)調(diào)用圖的相似性距離的定義， 2.2節(jié)是完全二分圖的構(gòu)建方法，2.3節(jié)是完全二分圖的邊權(quán)矩陣的計算方法，2.4節(jié)是二分圖的最大權(quán)匹配的計算方法以及兩個函數(shù)調(diào)用圖相似性距離SDMFG(Similar Distance of Malware Function-call Graphs)的計算方法;第3節(jié)是實驗部分;第4節(jié)是文章總結(jié)。

2 圖的相似性分析

2.1 函數(shù)調(diào)用圖的相似性距離

首先給出惡意代碼函數(shù)調(diào)用圖的相似性距離SDMFG的定義。

定義1 (SDMFG)設(shè)圖G和H是兩個惡意代碼函數(shù)調(diào)用圖，圖G和H間所有匹配路徑中匹配成本最小的匹配路徑，稱為圖G和H的最優(yōu)匹配路徑，這個最優(yōu)匹配路徑的匹配成本就是兩個惡意代碼函數(shù)調(diào)用圖G和H的相似性距離SDMFG。

這里，圖G和H之間的一個匹配路徑是指由G轉(zhuǎn)化為H所需的所有頂點匹配操作。頂點的匹配操作包括匹配兩個點、刪除一個點和插入一個點三種。只有當(dāng)兩點所對應(yīng)的函數(shù)很相似且它們的調(diào)用函數(shù)序列也很相似時才會進行匹配操作，而對G中其余點做刪除操作，對H中其余點做插入操作。如G由點x1和x2構(gòu)成，而H由y1構(gòu)成，則G和H之間有三條匹配路徑：

(1)點x1匹配點y1，刪除點x2；

(2)點x2匹配點y1，刪除點x1；

(3)刪除點x1和點x2，插入點y1。

每個匹配操作σ都有一個成本，即匹配成本c(σi)，依操作類型分為三類：匹配點成本、刪除點成本和插入點成本。我們從兩個方面來考慮兩個點是否匹配：兩點所對應(yīng)的函數(shù)的相似性以及兩點的鄰接邊所對應(yīng)的調(diào)用關(guān)系的相似性。兩點所對應(yīng)的函數(shù)越相似，兩點的匹配成本越小，兩點也就越相匹配；兩點所對應(yīng)函數(shù)的調(diào)用函數(shù)序列越相似，兩點的匹配成本也越小，兩點也就越相匹配；若有兩個點與另一個點所對應(yīng)的函數(shù)相似性相同時，則它們之中與另一點所對應(yīng)的函數(shù)調(diào)用關(guān)系越相似的那個點與另一個點更匹配。

完全相同的兩個點的匹配成本c(σi)=0，完全不同的兩個點的匹配成本c(σi)=1；插入一個點和刪除一個點的成本很高，接近于1。一條匹配路徑的匹配成本就是構(gòu)成這條路徑的所有得到頂點匹配操作的匹配成本之和。由于惡意代碼函數(shù)調(diào)用圖的相似性距離SDMFG被定義為兩圖間最優(yōu)匹配路徑的成本，惡意代碼函數(shù)調(diào)用圖的相似性問題就轉(zhuǎn)換成了求兩圖的最小成本匹配問題。

(1)

因此，惡意代碼函數(shù)調(diào)用圖的相似性問題就轉(zhuǎn)換成了求最大權(quán)匹配問題，可以通過Kuhn-Munkres算法[3,4]解決。下面介紹通過求最大權(quán)匹配來求惡意代碼函數(shù)調(diào)用圖的SDMFG值的過程。

2.2 構(gòu)造完全二分圖

求最大權(quán)匹配問題可以通過Kuhn-Munkres算法[3,4]來解決。首先，利用兩個惡意代碼函數(shù)調(diào)用圖G1和G2構(gòu)造一個完全二分圖G；然后，計算該二分圖的邊權(quán)矩陣C；接著，利用Kuhn-Munkres算法計算該二分圖的最大權(quán)匹配M；最后，根據(jù)M計算惡意代碼函數(shù)調(diào)用圖的相似性距離。

根據(jù)兩個惡意代碼函數(shù)調(diào)用圖的函數(shù)調(diào)用信息構(gòu)造一個完全二分圖的算法如算法1所示。其中，函數(shù)調(diào)用信息是用反匯編工具提取并以鄰接矩陣的形式存放的。

算法1 構(gòu)造完全二分圖

輸入：兩個惡意代碼函數(shù)調(diào)用圖G1和G2的函數(shù)調(diào)用信息；

輸出：完全二分圖G=(X∪Y,E)；

步驟1 根據(jù)兩個惡意代碼函數(shù)調(diào)用圖的函數(shù)調(diào)用信息,分別提取兩個函數(shù)調(diào)用圖G1的頂點集V1和G2的頂點集V2；把G1的頂點集V1加入到X中，把G2的頂點集V2加入到Y(jié)中。

步驟3 根據(jù)步驟1和步驟2計算得到的圖的頂點集V=X∪Y，對X中任一點和Y中任一點之間都加上一條邊，構(gòu)造二分圖的邊集；對所有邊都進行加權(quán)就得到了一個|X|*|Y|的邊權(quán)矩陣C。

2.3 計算二分圖的邊權(quán)矩陣

對一個完全二分圖的邊權(quán)的選擇是圖比對算法的核心部分之一，因為它表述了兩個比對圖的信息，是圖比對算法的輸入前提，對邊權(quán)選擇得越好，圖比對算法的結(jié)果就越接近實際情況。邊權(quán)矩陣中元素的值是通過計算權(quán)衡函數(shù)的相似性和函數(shù)調(diào)用關(guān)系的相似性得到的。下面，我們先計算函數(shù)的相似性和函數(shù)調(diào)用關(guān)系的相似性，然后計算邊權(quán)矩陣。

2.3.1 計算函數(shù)的相似性

函數(shù)的相似性是通過求用IDA工具提取的函數(shù)指令助記符序列最佳匹配，并計算最佳匹配情況下所有指令中匹配指令所占百分比得到的。

算法2 計算函數(shù)的相似性

輸入：函數(shù)調(diào)用圖G1中函數(shù)v1和圖G2中函數(shù)v2；

輸出：函數(shù)v1和v2的相似性。

步驟1 用反匯編工具IDA提取函數(shù)v1和v2的指令助記符序列S1和S2，若提取函數(shù)v1或v2的指令助記符序列不成功，那么記兩個函數(shù)的相似性分?jǐn)?shù)Sf=0。

步驟2 運用生物信息學(xué)中的雙序列比對算法Needleman-Wunsch[5]做全局序列比對，找到兩個序列S1和S2之間的最佳匹配。

步驟1 把匹配數(shù)在所有指令助詞符數(shù)中所占得的百分比作為兩個函數(shù)v1和v2的相似性分?jǐn)?shù)。

例如，兩個函數(shù)指令助記符序列S1=(push, push, call, push, mov, add, push, push, call, retn)，S2=(push, mov, call, test, jz, push, call, pop, mov, pop, retn)，則最佳Needleman-Wunsch匹配結(jié)果如圖1所示。

Figure 1 The best matching between sequences S1 and S2圖1 S1和S2序列的最佳匹配

顯而得之，S1和S2兩個序列只有3個指令助記符是匹配的，在S1序列中插入了一個空格，且有7個指令助記符是不匹配的，總的指令助詞符數(shù)是11。所以兩函數(shù)的相似性Sf=3/11。

2.3.2 計算函數(shù)調(diào)用關(guān)系的相似性

一般來說，如果兩個函數(shù)相似的話，那么這兩個函數(shù)的指令序列肯定在很大程度上也是很相似的，因此，當(dāng)兩個函數(shù)的指令序列的相似性達到一定程度時，就可以判定這兩個函數(shù)是相似的。在生物信息學(xué)中已有大量研究表明，當(dāng)DNA或氨基酸序列的相似性達到一定程度時，一般就可以判定兩個序列是相似序列。

如果根據(jù)2.3.1小節(jié)中的方法來計算指令序列的相似性，那么當(dāng)函數(shù)的指令序列的相似性達到一定程度時就可以判斷兩個函數(shù)是相似的。通過大量實驗可以得出結(jié)論，只要指令序列的相似性達到50%，就可以判斷兩個函數(shù)是相似的。

當(dāng)然，如果同時有兩個函數(shù)的指令序列與某個函數(shù)的指令序列的相似性都很高，那么，為了保證函數(shù)調(diào)用圖中各個函數(shù)的一對一匹配，則取與之相似性最大的那個函數(shù)作為這個函數(shù)的相似函數(shù)。兩個相似函數(shù)稱為一個相似函數(shù)對。

兩個函數(shù)的調(diào)用關(guān)系的相似性是指這兩個函數(shù)的調(diào)用函數(shù)和被調(diào)用函數(shù)中相似函數(shù)對所占的比例。算法如下所示：

算法3 計算函數(shù)調(diào)用關(guān)系的相似性

輸入：函數(shù)調(diào)用圖G1中函數(shù)v1和圖G2中函數(shù)v2的調(diào)用函數(shù)集和被調(diào)用函數(shù)集，圖G1中任意函數(shù)x與G2中任意函數(shù)y的相似性；

輸出：函數(shù)v1與函數(shù)v2的調(diào)用關(guān)系的相似性。

步驟1 計算函數(shù)v1調(diào)用的函數(shù)(即調(diào)用函數(shù))和函數(shù)v2調(diào)用的函數(shù)所構(gòu)成的相似函數(shù)對的數(shù)量N1，計算調(diào)用函數(shù)v1的函數(shù)(即被調(diào)用函數(shù))和調(diào)用函數(shù)v2的函數(shù)所構(gòu)成的相似函數(shù)對的數(shù)量N2；

步驟2 計算函數(shù)v1的調(diào)用函數(shù)和被調(diào)用函數(shù)中不與函數(shù)v2的任何調(diào)用函數(shù)及被調(diào)用函數(shù)相似的數(shù)量N3，計算函數(shù)v2的調(diào)用函數(shù)和被調(diào)用函數(shù)中不與函數(shù)v1的任何調(diào)用函數(shù)及被調(diào)用函數(shù)相似的數(shù)量N4；

步驟3 以N1+N2+N3+N4作為總數(shù)，并以相似函數(shù)對的數(shù)量N1+N2在其中所占的比例作為兩個函數(shù)v1和v2的調(diào)用關(guān)系的相似性分?jǐn)?shù)Se，即Se=(N1+N2)/(N1+N2+N3+N4)。

2.3.3 計算邊權(quán)矩陣

在文獻[6]中，匹配任何兩個實節(jié)點的成本都被簡單地定義為重標(biāo)成本。而在文獻[2]中，將匹配任何兩個實節(jié)點的成本定義為重標(biāo)成本與鄰居成本之和。它們都沒有考慮函數(shù)內(nèi)部信息(如指令序列)的相似性，匹配結(jié)果精確性太低。本文提出如下加權(quán)算法：

算法4 計算邊權(quán)矩陣

輸入：完全二分圖G=(X∪Y,E)，X中任一頂點所對應(yīng)函數(shù)v1和Y中任一頂點所對應(yīng)函數(shù)v2的相似性及其調(diào)用關(guān)系的相似性；

輸出：二分圖G的邊權(quán)矩陣C。

步驟1 若函數(shù)v1和函數(shù)v2都是實節(jié)點，則它們對應(yīng)的邊的權(quán)值為:

C(v1,v2)=[Sf(v1,v2)+Se(v1,v2)]/2

(2)

步驟2 若函數(shù)v1和函數(shù)v2兩者之中有一個是虛節(jié)點或者都是虛節(jié)點，則它們對應(yīng)的邊的權(quán)值C(v1,v2)=0.1(這意味著它們所對應(yīng)的點是插入或者刪除操作)。

2.4 求最大權(quán)匹配和兩圖的相似性距離

得到了完全二分圖G的邊權(quán)矩陣C之后，利用Kuhn-Munkres算法在完全二分圖的C上求最大權(quán)匹配M。然后根據(jù)二分圖的最大權(quán)匹配M求兩個惡意代碼函數(shù)調(diào)用圖的相似性距離SDMFG，計算算法如下。

Figure 2 The result of SDMFG algorithm圖2 SDMFG方法結(jié)果

算法5 求最大權(quán)匹配算法

輸入：完全二分圖G的最大權(quán)匹配M及其權(quán)值w；

輸出：兩個惡意代碼函數(shù)調(diào)用圖G1和G2的相似性距離SDMFG。

步驟1 找出M中的實節(jié)點與實節(jié)點的匹配邊(匹配點操作)、實節(jié)點與虛節(jié)點的匹配邊(刪除點或插入點操作)和虛節(jié)點與虛節(jié)點的匹配邊(非匹配操作)，并分別計算它們數(shù)量以及二分圖的一個劃分的點數(shù)n(這里n的含義同上文)；

步驟2M中的實節(jié)點與實節(jié)點的匹配邊(匹配點操作)、實節(jié)點與虛節(jié)點的匹配邊(刪除點或插入點操作)構(gòu)成了G1和G2的最優(yōu)匹配路徑，它們匹配成本就是G1和G2的相似性距離。設(shè)虛節(jié)點與虛節(jié)點的匹配邊的數(shù)量為n1，則兩個惡意代碼函數(shù)調(diào)用圖G1和G2的相似性距離SDMFG=(n-w)-n1*(1-0.1)。

3 實驗結(jié)果

本節(jié)應(yīng)用SDMFG算法對惡意代碼的函數(shù)調(diào)用圖進行相似性比對，并評估方法的性能與效率。整個方法是在Windows XP系統(tǒng)上用VC實現(xiàn)的。

3.1 比較SDMFG方法和文獻[2]方法的準(zhǔn)確性

對兩個哈希值分別為awbw_ed5240cd7d5120ae5222b062ec6774ba和awbz_a29d57e661863d6f37c039d58608dd96的樣本，用兩種方法做函數(shù)調(diào)用圖相似性分析的結(jié)果分別如圖2和圖3所示，兩個小框中分別是兩個函數(shù)調(diào)用圖，匹配的函數(shù)點用虛線連接(由于篇幅的原因，圖中沒有畫出被調(diào)用的庫函數(shù)，所以匹配的兩個函數(shù)的調(diào)用函數(shù)數(shù)量在圖中看起來不一樣)。很明顯，在圖2中函數(shù)sub_4024D4匹配sub_402514，在圖3中卻是函數(shù)sub_4065F0匹配sub_402514。由于三個函數(shù)sub_4024D4、sub_4065F0和sub_402514都無法提取到函數(shù)的指令助記符序列，故函數(shù)sub_4024D4與sub_402514、函數(shù)sub_4065F0與sub_402514的相似性分?jǐn)?shù)均為Sf=0，兩組函數(shù)對的頂點重標(biāo)成本也均為1，這時只能通過比較函數(shù)sub_4024D4與sub_402514的調(diào)用關(guān)系相似性(出入度鄰接成本)以及函數(shù)sub_4065F0與sub_402514的調(diào)用關(guān)系相似性(出入度鄰接成本)來判斷哪一組函數(shù)對相匹配更貼近實際情況。然而，函數(shù)sub_4024D4和sub_402514都只調(diào)用了庫函數(shù)(且都只調(diào)用了同一個庫函數(shù)DllFunctionCall)，但是函數(shù)sub_4065F0卻被函數(shù)sub_40-6670調(diào)用(且調(diào)用了一個不同的庫函數(shù)——vbaFreeVar)，即函數(shù)sub_4024D4與sub_402514的調(diào)用關(guān)系相似性(值為1)比函數(shù)sub_4065F0與sub_402514的調(diào)用關(guān)系相似性(值為0)要大，且前一組函數(shù)對的出入度鄰接成本(值為0)比后一組函數(shù)對的(值為1)要小。這里文獻[2]方法給出了錯誤的結(jié)果，因為在求最大權(quán)匹配M時，sub_4065F0與sub_402514匹配可以使得M的權(quán)值最大，即使sub_4065F0與sub_402514并不應(yīng)該相匹配。顯然，文獻[2]方法的準(zhǔn)確性沒有本文方法好。

Figure 3 The result of reference[2] algorithm圖3 文獻[2]方法結(jié)果

Figure 4 Similar distance of malware function-call graphs圖4 惡意代碼的相似性距離

3.2 比較SDMFG方法和文獻[2]方法的效率

假設(shè)兩個比對圖的頂點集平均大小為t，則本文中構(gòu)建二分圖的時間復(fù)雜度是O(2t)。假設(shè)兩個函數(shù)的指令助記符序列平均長度為l，計算所有函數(shù)對的指令助記符序列相似性的時間復(fù)雜度是O(t2*l2)。假設(shè)兩個函數(shù)的調(diào)用和被調(diào)用函數(shù)個數(shù)平均為m，計算所有函數(shù)對的調(diào)用關(guān)系相似性的時間復(fù)雜度是O(t2*m2)。計算加權(quán)矩陣的時間復(fù)雜度是O((2t)2)。用Kuhn-Munkres算法求二分圖的最大權(quán)匹配的時間復(fù)雜度是O((2t)3)。所以,SDMFG方法的時間復(fù)雜度總和是O(2t+t2*l2+t2*m2+(2t)2+(2t)3)。文獻[2]中，構(gòu)建二分圖的時間復(fù)雜度是O(2t)，計算重標(biāo)成本的時間復(fù)雜度是O((2t)2),計算鄰居成本的時間復(fù)雜度是O(t2*m2),計算加權(quán)矩陣的時間復(fù)雜度是O((2t)2),用Kuhn-Munkres算法求二分圖的最大權(quán)匹配的時間復(fù)雜度是O((2t)3)。所以,文獻[2]方法的時間復(fù)雜度總和是O(2t+t2+t2*m2+(2t)2+(2t)3)。很容易就能發(fā)現(xiàn)，兩種方法的時間復(fù)雜度的區(qū)別主要在于計算所有函數(shù)對的指令助記符序列相似性和計算重標(biāo)成本，前者要比后者大，所以后者效率要稍高些。

3.3 一組惡意代碼樣本的函數(shù)調(diào)用圖相似性分析

任取2個Backdoor.Win32.Bifrose樣本、6個Trojan.Win32.Scar樣本、2個Virus.Win32.Nimnul樣本和3個Virus.Win32.Virut樣本進行惡意代碼函數(shù)調(diào)用圖相似性分析，它們的圖相似性距離SDMFG結(jié)果如圖4所示。圖4橫軸是各個樣本，縱軸表示樣本與樣本之間的函數(shù)調(diào)用圖相似性距離，即SDMFG值，每條曲線都表示一個惡意代碼樣本與其它所有樣本的函數(shù)調(diào)用圖的相似性距離?？梢院苋菀卓闯?，同一惡意代碼的樣本之間的SDMFG值比較小且相差不大，而它們與其他惡意代碼的樣本之間的SDMFG值則要比較大，而且與不同惡意代碼的樣本之間的SDMFG值相差較大。

4 結(jié)束語

惡意代碼的相似性分析是當(dāng)前惡意代碼自動分析的重要部分之一。本文利用生物信息學(xué)中的序列比對方法計算函數(shù)的相似性，并據(jù)此計算函數(shù)調(diào)用關(guān)系的相似性以及函數(shù)對應(yīng)點之間的匹配邊的權(quán)值；然后利用圖論中的二分圖最大權(quán)匹配方法計算兩個惡意代碼函數(shù)調(diào)用圖的相似性距離。此方法提高了惡意代碼相似性分析的準(zhǔn)確性，為惡意代碼的同源及演化特性分析研究與惡意代碼的檢測和防范提供了有力支持。

[1] Kolter J Z, Maloof M A. Learning to detect and classify malicious executables in the wild[J]. The Journal of Machine Learning Research, 2006,7:2721-2744.

[2] Hu Xin, Chiueh T, Shin K G. Large-scale malware indexing using function-call graphs[C]∥Proc of the 16th ACM on Computer and Communication Security, 2009:611-620.

[3] Gao Sui-xiang. Graph theory and network flow theory [M]. China Higher Education Press, 2009.(in Chinese)

[4] Kuhn H W. The hungarian method for the assignment problem[J]∥Naval Research Logistics Quarterly, 1955,2(1-2):83-97.

[5] Krane D E, Raymer M L. Fundamental concepts of bioinformatics[M]. Sun Xiao, Translation. Tsinghua:Qinghua University Press, 2004.(in Chinese)

[6] Riesen K, Neuhaus M, Bunke H. Bipartite graph matching for computing the edit distance of graphs[C]∥Proc of the 6th International Conference on Graph-Based Representations in Pattern Recognition IAPRTC-15, 2007:1-12.

附中文參考文獻：

[3] 高隨祥. 圖論與網(wǎng)絡(luò)流理論[M]. 高等教育出版社, 2009.

[5] Krane D E, Raymer M L. 生物信息學(xué)概論[M]. 孫嘯，譯.北京：清華大學(xué)出版社,2004.

LIU Xing,born in 1986,MS candidate,his research interests include network and information security.

唐勇(1979-),男,湖南衡陽人，博士，助理研究員，研究方向為網(wǎng)絡(luò)與信息安全,數(shù)據(jù)挖掘與機器學(xué)習(xí)。E-mail:ytang@nudt.edu.cn

TANG Yong,born in 1979,PhD,assistant researcher,his research interests include network and information security，and data mining and machine learning.

Similarity analysis of malware’s function-call graphs

LIU Xing,TANG Yong
(College of Computer,National University of Defense Technology,Changsha 410073,China)

The similarity analysis of malware is an important part of the current automatic analysis of malware. The paper proposes a new method of similarity analysis of malware based on function-call graphs. This method uses the similarity distance of malware’s function-call graphs (called SDMFG) to measure the similarity of two malwares’ function-call graphs, and then analyzes the similarity of the two malwares. This method improves the accuracy of similarity analysis of malware, providing a strong support for analysis of the homology and evolution characteristics of malware and malware detection and prevention.

malware;function-call graph;SDMFG;instruction sequence;max-weight matching

2012-12-03;

2013-02-17

國家自然科學(xué)基金資助項目(61003303)

1007-130X(2014)03-0481-06

TP309

A

10.3969/j.issn.1007-130X.2014.03.018

劉星(1986-),男,湖南茶陵人，碩士生，研究方向為網(wǎng)絡(luò)與信息安全。E-mail:Tianwaifeishi17@sina.com

通信地址：215300 江蘇省昆山市景王路700號

Address:700 Jingwang Rd,Kunshan 215300,Jiangsu,P.R.China