基于API依賴關系的代碼相似度分析

姚新磊，龐建民，岳 峰，余 勇

(信息工程大學信息工程學院，鄭州 450002)

1 概述

代碼相似度分析是檢測源代碼竊取和惡意代碼變種的主要方式，其本質上依賴于對代碼的描述和理解。現有對代碼特征的描述有很多種，如特征碼、指令序列、控制流圖、API序列[1]、API依賴圖[2-4]等，不同的描述方式代表著對代碼實際邏輯的不同理解方式。但程序理解本身就是 NP問題[5]，各種理解在實現上只能更大程度地接近代碼的實際邏輯，為此一般要在描述上采取一定的精簡策略。

正如多態引擎[6]在指令級采用垃圾指令插入、等價指令替換、指令順序重排、寄存器隨機等方式實現指令級特征的混淆，針對目前較為流行的API級行為分析，一些API級特征的混淆方式開始大量使用，如API噪聲[7]、API順序重排和等價API替換等。

針對此類混淆，文獻[8]提出一種基于行為依賴的惡意代碼相似度比較方法，首先在依賴圖的構建階段采用虛擬節點消除API序列重排混淆；然后在依賴圖的預處理階段手工構建等價API序列集合，在分析中若發現其中一個序列則，在等價序列集合中尋找統一表示的序列將其替換；最后在污點傳播中對產生了污點但沒有進行傳播，或進行了傳播但在傳播過程中沒有引起系統狀態改變的噪聲API進行消除。該方法有效解決一些 API級特征的混淆方式對相似度分析的影響，但也存在如下改進空間:

(1)對 API噪聲的處理依賴于改變系統狀態的函數集合，若一個API調用使用了污點數據而且改變了系統狀態，則不被認為是噪聲API，就不會從依賴圖中刪除。然而，這樣的 API調用也可能是噪聲 API調用。

(2)對API重排問題的處理有待商榷:1)只處理了2個API的重排問題，沒有考慮2個API序列之間的重排問題；2)對API重排的定義欠妥，其中的“有數據依賴但沒有發生修改”定義擴大了API重排范圍，實際上2個API之間在有數據依賴關系但沒有修改污點數據的情況下并不能交換位置。

鑒于此，本文在分析這2類問題的基礎上，提出基于API依賴關系的代碼相似度分析方式，通過動態分析形成程序的SCDG，然后對SCDG進行預處理消除API噪聲、API重排，最后采用子圖同構算法計算可疑代碼與原有代碼的相似度。

2 問題的提出

2.1 污點源復用式噪聲API

動態污點分析是獲取API依賴關系的主要方式，污點源是污點追蹤過程的開始，污點源的變化是必然引起追蹤過程的變化，進而引起 API依賴關系的變化。污點源復用攻擊就是一種將原有污點源復用到新污點源從而導致污點源變化的攻擊方式。

在常見的遠程線程注入代碼中添加了 Create File和 SetFilePointer 2個噪聲 API，根據本文對SetFilePointer參數的設置，FILE_BEGIN代表調整時起始參考點是文件的開頭，hProcess作為參數是調整的字節數，當SetFilePointer調用成功后，其返回值就是一個與hProcess相等的DWORD值，將其賦給 hProcess2后就完成了污點源復用，后面的CreateRemoteThread函數的第 1個參數就是hProcess2，同樣實現了向explorer進程注入一個線程的功能。

混淆后遠程線程注入類C代碼如下:

從圖1中可以看出，混淆后的遠程線程注入代碼的函數依賴圖發生了巨大變化，新增加的函數⑧與函數③產生輸入依賴關系，與函數⑥產生流依賴關系；而且 SetFilePointer函數將“1.tmp”文件的讀寫頭移動到hProcess值處，導致系統的完整性發生變化即系統狀態發生變化，這是原有方法所不能消除的噪聲API。

圖1 混淆后的遠程線程注入函數依賴圖

2.2 API重排

將圖1中的部分函數分為3組，分別是第1組函數①～函數③、第2組函數④、函數⑤、第3組函數⑥。通過對函數⑥的功能實現過程分析發現:

(1)前2組函數的調用順序是可以互換的，即只要在函數⑥執行前完成前2組函數的功能即可，而不需關心這2組函數的調用順序。

(2)在第 1組和第 2組函數內部，只要保持函數①～函數③和函數④、函數⑤的相對順序即可，而不用關心它們之間是否有其他 API調用，因此，將2組函數混合放置也可以實現相同功能。

基于以上2點對前2組API的順序進行重排，將有如圖2所示的10種實現，也就是有10個不同的依賴圖。在基于SCDG的代碼相似性分析中必須先處理這類情況，將不同的依賴圖歸一化為同一個模型，才能進行后續的比較過程。

圖2 遠程線程注入API重排的10種情況

3 代碼相似度分析

3.1 API依賴關系的構建

定義 1(依賴圖) 依賴圖是一個四元組(V, E, α,β)，其中，V是頂點集合，代表系統調用集合，每個頂點中包含2項:系統調用號和污點數據信息；E:V×V是邊集合，說明2個系統調用之間存在依賴關系；α:V→S是系統調用號與系統調用名稱之間的映射；β:E→D是邊和依賴關系之間的映射，由于2個系統調用的依賴關系可能多于一個，該映射是一個邊到所有依賴關系的映射。

污點數據信息是五元組＜Address, Length, Type,ParamType, Value＞，其中，Address是污點數據的地址；Length為污點數據的長度；Type表示污點數據的類型，分內存數據 Mem和寄存器 Reg 2類；ParamType表示污點數據作為系統調用的參數信息，分入參in、出參out、出入參in-out 3類。借鑒文獻[9]中的方法設計一個雙向鏈表記錄污點信息，用于回溯污點數據的傳播過程。

對于數據依賴關系，在執行過程中將系統調用的出參、出入參和返回值設置為污點源，然后跟蹤數據操作指令和內存操作指令進行污點傳播，當執行到新的系統調用時分析其入參是否為污點數據，若是則回溯分析該系統與前一個系統調用存在的數據依賴關系，若存在流依賴、反依賴、輸入依賴和輸出依賴中的任何一種，則記錄兩者之間的數據依賴關系然，并將該系統調用的出參、出入參和返回值設置為新的污點源。

對于控制依賴關系，借鑒文獻[8]中的方法進行構建。以參數hProcess和hProcess2的污點傳播過程為例，最終形成的SCDG的具體信息如圖3所示。

圖3 混淆后的SCDG部分具體信息

3.2 SCDG預處理

3.2.1 噪聲API的識別消除

本文主要解決污點源復用式噪聲API問題，通過對比分析發現，污點源復用式噪聲 API有 3個主要特征:

(1)該類API的出參或返回值是新的污點源。

(2)為了保證后續調用的正確性，新污點源的值與原污點源的值必須是相等的。

(3)新污點源的值是接受原污點源為輸入，并經過計算而形成的，所以，該API與產生或使用原污點源的API存在流依賴或輸入依賴關系。

依據上述3個特征，可以設計出噪聲API識別與消除過程:

(1)遍歷 SCDG圖，將 ParamType為out或 in-out類型的污點數據加入污點源信息集合。

(2)在污點源信息集合中找出Value相等的污點源對偶。

(3)對于每一對污點源對偶＜A, B＞，若 B對應的API與A對應的API或A所在污點信息雙向鏈表的任一污點信息對應的API存在輸入依賴或流依賴，則標記B對應的API調用為噪聲API。

(4)對于噪聲API，在SCDG中找出與其具有數據依賴關系和控制依賴關系的前驅節點 F和后繼節點B，根據F和B的污點數據信息，建立相應的依賴關系，并去除噪聲API與F、B節點之間的依賴關系。

3.2.2 噪聲API的判定與消除

通過對API之間的4種數據依賴關系發現:流依賴和反依賴直接決定了兩者的執行順序不可改變，存在輸出依賴關系的2個API順序重排后，輸出的值有可能不一樣，所以也不能重排。只有輸入依賴關系的2個API，兩者的順序重排后執行結果是一樣的。

為了表示API重排消除后的控制依賴關系，本文設計了統一的控制依賴圖。在該圖中，控制依賴關系表示一個API的執行依賴于其他API的預先執行，如圖4所示，A、B是可以重排的，前2種控制依賴圖可以統一成后面的控制依賴圖。

圖4 統一的控制依賴圖

根據上述分析可以設計出 API重排的判定和消除過程:

(1)按照控制依賴關系遍歷 SCDG圖，對于每一個節點與其他節點的控制依賴關系，檢查相應的數據依賴關系，若兩者不存在數據依賴或只存在輸入依賴，則兩者的順序是可以重排的。

(2)對于可重排的2個節點，消除兩者原有的控制依賴關系。然后根據前一個節點的數據依賴關系，建立該節點與其數據依賴關系上的后繼節點的控制依賴關系。然后處理下一個節點。圖5是圖1經過預處理的效果。

圖5 SCDG預處理后的函數依賴圖

3.3 SCDG相似度分析

定義 2(公共子圖) 給定圖 G1、G2，C是 G1的子圖，如果C子圖同構于G2，則C是G1和G2的一個公共子圖。

由于2個圖的公共子圖并不一定是連通的，此處稱兩者的公共子圖并集為公共部分。實際中 2個SCDG的公共部分在各自 SCDG中所占比例是不同的，為了更加精確地描述2個SCDG的相似性，本文使用Jaccard系數表示2個SCDG的相似度。對于A、B 2個SCDG:

其中，A∩B是兩者的公共子圖并集；A∪B是兩者合并圖；|A∪B|表示圖中節點的數量，也就是系統調用的個數，因此Jaccard系數就表示2個SCDG中相同功能部分占兩者所有功能的比例。

計算J(A, B)的關鍵點就是獲取|A∩B|，也就是獲取公共子圖并集。本文采用 VF2算法[10]計算2個圖的公共子圖，進而獲取公共子圖并集，由此設計如下的SCDG相似度分析算法:

算法 SCDG相似度分析算法

輸入 惡意代碼SCDG:A，可疑代碼SCDG:B

輸出 A、B的相似度

(1)對 A、B進行預處理，并對 A中的每一個子圖設置Visited標志為False。

(2)若所有子圖的 Visited標志為 True，則轉步驟(3)，否則選擇A中一個Visited標志為False的子圖S，調用VF2算法檢查它是否子圖同構于 B，若是則將 S加入公共子圖集合中。設置S的Visited標志為True，轉步驟(2)。

(3)根據獲取的公共子圖集合，計算A、B的Jaccard系數并返回。

4 實驗結果

本文選取常見的木馬Downloader，它主要功能是向 IE進程注入一個線程，實現下載，并運行下載的程序；然后對源代碼進行修改形成4個變種A、B、C和D。

在測試中，采用依賴相似度分析方法分別對Downloader和它的4個變種的相似度進行分析，同時采用序列相似度分析進行對比，實驗結果如表1所示。

表1 Downloader變種相似度分析比較

從表1可以發現，API噪聲和API重排使得原有惡意代碼的API序列發生巨大變化，對基于序列相似度的分析有較大影響，而基于依賴關系的相似度分析則很好地解決了這個問題，分析結果顯示兩者的相似度達到90%以上。但是對于添加或刪除部分功能的變種，公共功能部分的API序列是沒有發生變化的，所以兩者的分析效果基本相似的。

從該對比中可以發現，基于依賴關系的相似度分析更能有效解決API噪聲、API重排等API級行為混淆的問題。

5 結束語

本文提出一種基于 API依賴關系的代碼相似度分析方法對API噪聲、API重排等混淆方式具有較好的抗干擾效果，但其分析過程與動態分析平臺的效率息息相關，所以針對代碼多路徑分析的抗分析技術必然成為對抗動態分析的重要方向，這也是下一步研究的重點。

[1]Wang Xinran, Jhi Yoon-Chan, Zhu Sencun, et al.Detecting Software Theft via System Call Based Birthmarks[C]//Proc.of the 25th Annual Computer Security Applications Conference.Honolulu, USA∶ [s.n.], 2009∶ 149-158.

[2]Christodorescu M, Jha S, Kruegel C.Mining Specifications of Malicious Behavior[C]//Proc.of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering.New York, USA∶ACM Press, 2007∶ 5-14.

[3]Bayer U, Comparetti P M, Hlauscheck C, et al.Scalable,Behavior-based Malware Clustering[C]//Proc.of NDSS’09.San Diego, USA∶ [s.n.], 2009.

[4]Wang Xinran, Jhi Yoon-Chan, Zhu Sencun, et al.Behavior Based Software Theft Detection[C]//Proc.of the 16th ACM Conference on Computer and Communications Security.New York, USA∶ ACM Press, 2009.

[5]Woods S, Yang Qiang.The Program Understand Problem∶Analysis of Heuristic Approach[C]//Proc.of the 18th Int’l Conference on Software Engineering.Berlin, Germany∶[s.n.], 1996∶ 25-29.

[6]The Symantec Enterprise.Understanding and Managing Polymorphic Virus[EB/OL].(2012-03-20).http∶//www.symantec.com/avcenter/reference/striker.pdf.

[7]Kaze A.Stealth API-based Decryptor[EB/OL].(2012-03-20).http∶//vxheavens.com/lib/vkz00.html.

[8]楊 軼, 蘇璞睿, 應凌云, 等.基于行為依賴特征的惡意代碼相似性比較方法[J].軟件學報, 2011, 22(10)∶2438-2453.

[9]Newsome J, Song D.Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits on Commodity Software[C]//Proc.of the 12th Annual Network and Distributed System Security Symposium.[S.1.]∶ IEEE Press, 2005.

[10]Cordella L P, Foggia P, Sansone C, et al.A (Sub) Graph Isomorphism Algorithm for Matching Large Graphs[J].IEEE Trans.on Pattern Analysis and Machine Intelligence,2004, 26(10)∶ 1367-1372.