基于API依賴關(guān)系的代碼相似度分析

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

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

1 概述

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

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

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

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

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

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

2 問題的提出

2.1 污點(diǎn)源復(fù)用式噪聲API

動態(tài)污點(diǎn)分析是獲取API依賴關(guān)系的主要方式，污點(diǎn)源是污點(diǎn)追蹤過程的開始，污點(diǎn)源的變化是必然引起追蹤過程的變化，進(jìn)而引起 API依賴關(guān)系的變化。污點(diǎn)源復(fù)用攻擊就是一種將原有污點(diǎn)源復(fù)用到新污點(diǎn)源從而導(dǎo)致污點(diǎn)源變化的攻擊方式。

在常見的遠(yuǎn)程線程注入代碼中添加了 Create File和 SetFilePointer 2個噪聲 API，根據(jù)本文對SetFilePointer參數(shù)的設(shè)置，F(xiàn)ILE_BEGIN代表調(diào)整時起始參考點(diǎn)是文件的開頭，hProcess作為參數(shù)是調(diào)整的字節(jié)數(shù)，當(dāng)SetFilePointer調(diào)用成功后，其返回值就是一個與hProcess相等的DWORD值，將其賦給 hProcess2后就完成了污點(diǎn)源復(fù)用，后面的CreateRemoteThread函數(shù)的第 1個參數(shù)就是hProcess2，同樣實(shí)現(xiàn)了向explorer進(jìn)程注入一個線程的功能。

混淆后遠(yuǎn)程線程注入類C代碼如下:

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

圖1 混淆后的遠(yuǎn)程線程注入函數(shù)依賴圖

2.2 API重排

將圖1中的部分函數(shù)分為3組，分別是第1組函數(shù)①～函數(shù)③、第2組函數(shù)④、函數(shù)⑤、第3組函數(shù)⑥。通過對函數(shù)⑥的功能實(shí)現(xiàn)過程分析發(fā)現(xiàn):

(1)前2組函數(shù)的調(diào)用順序是可以互換的，即只要在函數(shù)⑥執(zhí)行前完成前2組函數(shù)的功能即可，而不需關(guān)心這2組函數(shù)的調(diào)用順序。

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

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

圖2 遠(yuǎn)程線程注入API重排的10種情況

3 代碼相似度分析

3.1 API依賴關(guān)系的構(gòu)建

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

污點(diǎn)數(shù)據(jù)信息是五元組＜Address, Length, Type,ParamType, Value＞，其中，Address是污點(diǎn)數(shù)據(jù)的地址；Length為污點(diǎn)數(shù)據(jù)的長度；Type表示污點(diǎn)數(shù)據(jù)的類型，分內(nèi)存數(shù)據(jù) Mem和寄存器 Reg 2類；ParamType表示污點(diǎn)數(shù)據(jù)作為系統(tǒng)調(diào)用的參數(shù)信息，分入?yún)n、出參out、出入?yún)n-out 3類。借鑒文獻(xiàn)[9]中的方法設(shè)計(jì)一個雙向鏈表記錄污點(diǎn)信息，用于回溯污點(diǎn)數(shù)據(jù)的傳播過程。

對于數(shù)據(jù)依賴關(guān)系，在執(zhí)行過程中將系統(tǒng)調(diào)用的出參、出入?yún)⒑头祷刂翟O(shè)置為污點(diǎn)源，然后跟蹤數(shù)據(jù)操作指令和內(nèi)存操作指令進(jìn)行污點(diǎn)傳播，當(dāng)執(zhí)行到新的系統(tǒng)調(diào)用時分析其入?yún)⑹欠駷槲埸c(diǎn)數(shù)據(jù)，若是則回溯分析該系統(tǒng)與前一個系統(tǒng)調(diào)用存在的數(shù)據(jù)依賴關(guān)系，若存在流依賴、反依賴、輸入依賴和輸出依賴中的任何一種，則記錄兩者之間的數(shù)據(jù)依賴關(guān)系然，并將該系統(tǒng)調(diào)用的出參、出入?yún)⒑头祷刂翟O(shè)置為新的污點(diǎn)源。

對于控制依賴關(guān)系，借鑒文獻(xiàn)[8]中的方法進(jìn)行構(gòu)建。以參數(shù)hProcess和hProcess2的污點(diǎn)傳播過程為例，最終形成的SCDG的具體信息如圖3所示。

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

3.2 SCDG預(yù)處理

3.2.1 噪聲API的識別消除

本文主要解決污點(diǎn)源復(fù)用式噪聲API問題，通過對比分析發(fā)現(xiàn)，污點(diǎn)源復(fù)用式噪聲 API有 3個主要特征:

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

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

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

依據(jù)上述3個特征，可以設(shè)計(jì)出噪聲API識別與消除過程:

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

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

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

(4)對于噪聲API，在SCDG中找出與其具有數(shù)據(jù)依賴關(guān)系和控制依賴關(guān)系的前驅(qū)節(jié)點(diǎn) F和后繼節(jié)點(diǎn)B，根據(jù)F和B的污點(diǎn)數(shù)據(jù)信息，建立相應(yīng)的依賴關(guān)系，并去除噪聲API與F、B節(jié)點(diǎn)之間的依賴關(guān)系。

3.2.2 噪聲API的判定與消除

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

為了表示API重排消除后的控制依賴關(guān)系，本文設(shè)計(jì)了統(tǒng)一的控制依賴圖。在該圖中，控制依賴關(guān)系表示一個API的執(zhí)行依賴于其他API的預(yù)先執(zhí)行，如圖4所示，A、B是可以重排的，前2種控制依賴圖可以統(tǒng)一成后面的控制依賴圖。

圖4 統(tǒng)一的控制依賴圖

根據(jù)上述分析可以設(shè)計(jì)出 API重排的判定和消除過程:

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

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

圖5 SCDG預(yù)處理后的函數(shù)依賴圖

3.3 SCDG相似度分析

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

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

其中，A∩B是兩者的公共子圖并集；A∪B是兩者合并圖；|A∪B|表示圖中節(jié)點(diǎn)的數(shù)量，也就是系統(tǒng)調(diào)用的個數(shù)，因此Jaccard系數(shù)就表示2個SCDG中相同功能部分占兩者所有功能的比例。

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

算法 SCDG相似度分析算法

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

輸出 A、B的相似度

(1)對 A、B進(jìn)行預(yù)處理，并對 A中的每一個子圖設(shè)置Visited標(biāo)志為False。

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

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

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

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

在測試中，采用依賴相似度分析方法分別對Downloader和它的4個變種的相似度進(jìn)行分析，同時采用序列相似度分析進(jìn)行對比，實(shí)驗(yàn)結(jié)果如表1所示。

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

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

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

5 結(jié)束語

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

[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]楊 軼, 蘇璞睿, 應(yīng)凌云, 等.基于行為依賴特征的惡意代碼相似性比較方法[J].軟件學(xué)報(bào), 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.