劉 星，唐 勇

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073)

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

劉 星，唐 勇

(國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073)

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

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

1 引言

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

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

鑒于這些方法的缺陷和不足，本文提出了一種用圖的相似性距離來(lái)度量?jī)蓚€(gè)惡意代碼函數(shù)調(diào)用圖的相似性的分析方法，該方法考慮了惡意代碼中函數(shù)的指令級(jí)信息以及函數(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)矩陣的計(jì)算方法，2.4節(jié)是二分圖的最大權(quán)匹配的計(jì)算方法以及兩個(gè)函數(shù)調(diào)用圖相似性距離SDMFG(Similar Distance of Malware Function-call Graphs)的計(jì)算方法;第3節(jié)是實(shí)驗(yàn)部分;第4節(jié)是文章總結(jié)。

2 圖的相似性分析

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

對(duì)一個(gè)完全二分圖的邊權(quán)的選擇是圖比對(duì)算法的核心部分之一，因?yàn)樗硎隽藘蓚€(gè)比對(duì)圖的信息，是圖比對(duì)算法的輸入前提，對(duì)邊權(quán)選擇得越好，圖比對(duì)算法的結(jié)果就越接近實(shí)際情況。邊權(quán)矩陣中元素的值是通過(guò)計(jì)算權(quán)衡函數(shù)的相似性和函數(shù)調(diào)用關(guān)系的相似性得到的。下面，我們先計(jì)算函數(shù)的相似性和函數(shù)調(diào)用關(guān)系的相似性，然后計(jì)算邊權(quán)矩陣。

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

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

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

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

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

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

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

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

例如，兩個(gè)函數(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兩個(gè)序列只有3個(gè)指令助記符是匹配的，在S1序列中插入了一個(gè)空格，且有7個(gè)指令助記符是不匹配的，總的指令助詞符數(shù)是11。所以兩函數(shù)的相似性Sf=3/11。

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

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

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

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

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

算法3 計(jì)算函數(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 計(jì)算函數(shù)v1調(diào)用的函數(shù)(即調(diào)用函數(shù))和函數(shù)v2調(diào)用的函數(shù)所構(gòu)成的相似函數(shù)對(duì)的數(shù)量N1，計(jì)算調(diào)用函數(shù)v1的函數(shù)(即被調(diào)用函數(shù))和調(diào)用函數(shù)v2的函數(shù)所構(gòu)成的相似函數(shù)對(duì)的數(shù)量N2；

步驟2 計(jì)算函數(shù)v1的調(diào)用函數(shù)和被調(diào)用函數(shù)中不與函數(shù)v2的任何調(diào)用函數(shù)及被調(diào)用函數(shù)相似的數(shù)量N3，計(jì)算函數(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ù)對(duì)的數(shù)量N1+N2在其中所占的比例作為兩個(gè)函數(shù)v1和v2的調(diào)用關(guān)系的相似性分?jǐn)?shù)Se，即Se=(N1+N2)/(N1+N2+N3+N4)。

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 比較SDMFG方法和文獻(xiàn)[2]方法的效率

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

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

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

4 結(jié)束語(yǔ)

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

[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.

附中文參考文獻(xiàn)：

[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-),男,湖南衡陽(yáng)人，博士，助理研究員，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全,數(shù)據(jù)挖掘與機(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61003303)

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

TP309

A

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

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

通信地址：215300 江蘇省昆山市景王路700號(hào)

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