惡意代碼的函數調用圖相似性分析

劉 星，唐 勇

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

惡意代碼的函數調用圖相似性分析

劉 星，唐 勇

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

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

惡意代碼；函數調用圖；圖的相似性距離；指令序列；最大權匹配

1 引言

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

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

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

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

2 圖的相似性分析

2.1 函數調用圖的相似性距離

首先給出惡意代碼函數調用圖的相似性距離SDMFG的定義。

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

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

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

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

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

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

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

(1)

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

2.2 構造完全二分圖

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

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

算法1 構造完全二分圖

輸入：兩個惡意代碼函數調用圖G1和G2的函數調用信息；

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

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

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

2.3 計算二分圖的邊權矩陣

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

2.3.1 計算函數的相似性

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

算法2 計算函數的相似性

輸入：函數調用圖G1中函數v1和圖G2中函數v2；

輸出：函數v1和v2的相似性。

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

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

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

例如，兩個函數指令助記符序列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匹配結果如圖1所示。

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

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

2.3.2 計算函數調用關系的相似性

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

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

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

兩個函數的調用關系的相似性是指這兩個函數的調用函數和被調用函數中相似函數對所占的比例。算法如下所示：

算法3 計算函數調用關系的相似性

輸入：函數調用圖G1中函數v1和圖G2中函數v2的調用函數集和被調用函數集，圖G1中任意函數x與G2中任意函數y的相似性；

輸出：函數v1與函數v2的調用關系的相似性。

步驟1 計算函數v1調用的函數(即調用函數)和函數v2調用的函數所構成的相似函數對的數量N1，計算調用函數v1的函數(即被調用函數)和調用函數v2的函數所構成的相似函數對的數量N2；

步驟2 計算函數v1的調用函數和被調用函數中不與函數v2的任何調用函數及被調用函數相似的數量N3，計算函數v2的調用函數和被調用函數中不與函數v1的任何調用函數及被調用函數相似的數量N4；

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

2.3.3 計算邊權矩陣

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

算法4 計算邊權矩陣

輸入：完全二分圖G=(X∪Y,E)，X中任一頂點所對應函數v1和Y中任一頂點所對應函數v2的相似性及其調用關系的相似性；

輸出：二分圖G的邊權矩陣C。

步驟1 若函數v1和函數v2都是實節點，則它們對應的邊的權值為:

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

(2)

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

2.4 求最大權匹配和兩圖的相似性距離

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

Figure 2 The result of SDMFG algorithm圖2 SDMFG方法結果

算法5 求最大權匹配算法

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

輸出：兩個惡意代碼函數調用圖G1和G2的相似性距離SDMFG。

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

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

3 實驗結果

本節應用SDMFG算法對惡意代碼的函數調用圖進行相似性比對，并評估方法的性能與效率。整個方法是在Windows XP系統上用VC實現的。

3.1 比較SDMFG方法和文獻[2]方法的準確性

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

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

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

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

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

3.3 一組惡意代碼樣本的函數調用圖相似性分析

任取2個Backdoor.Win32.Bifrose樣本、6個Trojan.Win32.Scar樣本、2個Virus.Win32.Nimnul樣本和3個Virus.Win32.Virut樣本進行惡意代碼函數調用圖相似性分析，它們的圖相似性距離SDMFG結果如圖4所示。圖4橫軸是各個樣本，縱軸表示樣本與樣本之間的函數調用圖相似性距離，即SDMFG值，每條曲線都表示一個惡意代碼樣本與其它所有樣本的函數調用圖的相似性距離。可以很容易看出，同一惡意代碼的樣本之間的SDMFG值比較小且相差不大，而它們與其他惡意代碼的樣本之間的SDMFG值則要比較大，而且與不同惡意代碼的樣本之間的SDMFG值相差較大。

4 結束語

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

[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] 高隨祥. 圖論與網絡流理論[M]. 高等教育出版社, 2009.

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

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

唐勇(1979-),男,湖南衡陽人，博士，助理研究員，研究方向為網絡與信息安全,數據挖掘與機器學習。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

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

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

TP309

A

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

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

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

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