基于基本塊指紋的二進(jìn)制代碼同源性分析

◆顏 穎 方 勇 劉 亮 劉露平 賈 鵬

?

基于基本塊指紋的二進(jìn)制代碼同源性分析

◆顏 穎 方 勇 劉 亮 劉露平 賈 鵬

（四川大學(xué)電子信息學(xué)院 四川 610065）

二進(jìn)制代碼同源性分析在代碼的專利保護(hù)和惡意代碼溯源分析中有重大意義，本文提出了一種基于基本塊指紋的、以更細(xì)粒度的對比分析算法來確定二進(jìn)制代碼同源性的方法。該方法從基本塊中提取三個(gè)指紋信息：跳轉(zhuǎn)邏輯特征、代碼序列特征和子函數(shù)名特征，將基本塊的控制流程圖根據(jù)跳轉(zhuǎn)邏輯表示成由0、1構(gòu)成的序列以計(jì)算基本塊跳轉(zhuǎn)邏輯特征的相似度，利用基于滑動(dòng)窗口的點(diǎn)距陣方法計(jì)算代碼序列特征的相似度，并用Levenshtein Distance算法計(jì)算基本塊子函數(shù)名特征的相似度，最后綜合計(jì)算出二進(jìn)制代碼基本塊的相似度，從而進(jìn)行二進(jìn)制代碼同源性分析。實(shí)驗(yàn)結(jié)果表明，三種指紋信息的綜合對比分析能有效區(qū)別基本塊的異同，進(jìn)行二進(jìn)制代碼基本塊的同源性分析。

二進(jìn)制；指紋；同源性比較；控制流程圖；代碼序列

0 引言

近年，無論是甲骨文公司起訴谷歌非法使用自己的多行Java代碼事件，還是銀行SWIFT系統(tǒng)被攻擊后，安全團(tuán)隊(duì)根據(jù)惡意代碼追查背后的攻擊者，無不顯示出分析代碼同源性在實(shí)際應(yīng)用中的重要性。二進(jìn)制代碼同源性的分析不僅能鑒別代碼作者是否有抄襲行為以維護(hù)知識(shí)產(chǎn)權(quán)，而且能對惡意代碼的家族進(jìn)行聚類[1]以追溯和確定惡意代碼的作者或組織。

在現(xiàn)有的代碼同源性分析技術(shù)研究中，大致分為基于源碼和基于二進(jìn)制代碼的同源性分析技術(shù)兩個(gè)方向。

基于源碼的同源性分析的依據(jù)有四類：基于語義的相似性、基于編程風(fēng)格的相似性、基于文本的相似性以及抽象語法樹的代碼同源性鑒別技術(shù)?；谖谋镜南嗨菩詸z測方法比較簡單，易于操作，缺點(diǎn)但該方法忽略了源代碼本身的語義特征，代碼抄襲者很容易利用這一點(diǎn)逃過鑒別，漏檢率較高?；诰幊田L(fēng)格的檢測方法需要利用模塊檢測方法確定克隆的位置，這會(huì)導(dǎo)致耗費(fèi)大量人力而難以實(shí)現(xiàn)自動(dòng)化，可行性較差。而基于抽象語法樹的檢測方法是依靠語法分析生成屬性存儲(chǔ)結(jié)構(gòu)，保存樹節(jié)點(diǎn)相關(guān)信息再進(jìn)行比對，該方法技術(shù)實(shí)現(xiàn)復(fù)雜，理論上有很大誤檢可能。

基于源代碼的同源性分析技術(shù)的首要條件就是要有完整的源代碼，但實(shí)際運(yùn)用中由于企業(yè)知識(shí)產(chǎn)權(quán)和專利的保護(hù)，源代碼是不會(huì)公開的。因此基于二進(jìn)制代碼的同源性分析技術(shù)的重要性便顯現(xiàn)出來。

現(xiàn)階段的二進(jìn)制代碼同源性分析技術(shù)中，基本以控制流程圖的特征[2]來進(jìn)行同源性的分析。崔寶江等分別提出了“基于基本塊簽名和跳轉(zhuǎn)關(guān)系的二進(jìn)制文件比對技術(shù)”、 “二進(jìn)制文件同源性檢測的結(jié)構(gòu)化相似度計(jì)算”和“基于特征提取的二進(jìn)制代碼比較技術(shù)”。這些方法闡述的基本策略是：提取反匯編代碼后的代碼基本塊，用小素?cái)?shù)乘積法[3]對基本塊處理后對264取模的值作為基本塊的指紋簽名；用基本塊的出入度表示該基本塊的調(diào)用頻率；用基本塊中子函數(shù)調(diào)用次數(shù)表示該基本塊的活躍程度；用IDA插件提取代碼基本塊的控制流程圖；最后綜合兩個(gè)代碼基本塊的控制流程圖和指紋簽名及出入度和子函數(shù)調(diào)用頻率的吻合度來確定這兩段代碼的相似性和同源性。該策略中小素?cái)?shù)乘積法克服了代碼重排對簽名的影響，但是在應(yīng)用過程中素?cái)?shù)的乘法增長快、開銷大，在考慮效率的情況下，基本塊內(nèi)的語句最好在14條以內(nèi)[4]，適用性受到限制。

以上所述的方法都是針對于整個(gè)文件的比對結(jié)果來確定相似度和同源性的，比對方法中涉及的都是基本塊與基本塊的關(guān)系。但是在如今的惡意代碼的分析工作中，經(jīng)常遇到一個(gè)惡意程序只是引用或借鑒了已知惡意程序的某一功能模塊，如果用整個(gè)文件的匹配度來確定兩個(gè)代碼文件的同源性，往往會(huì)因漏報(bào)而降低正確率。由此，本文提出了一種針對于基本塊的內(nèi)部指紋、以更細(xì)粒度的對比分析方法來進(jìn)行二進(jìn)制代碼同源性的度量。

1 二進(jìn)制代碼同源性分析算法

本文實(shí)驗(yàn)中的基本塊由IDA逆向工具提取，一個(gè)視圖下的控制流程圖視為一個(gè)完整的基本塊，該基本塊常以ret指令、call指令或jmp指令結(jié)束。以Win XP 系統(tǒng)下的kernel32.dll中的LoadLibraryA為例，在控制流程圖下的一個(gè)基本塊如圖1所示。

圖1 win XP 32位LoadLibraryA控制流程圖

1.1 基本塊跳轉(zhuǎn)邏輯特征

現(xiàn)階段的二進(jìn)制代碼同源性分析技術(shù)中，基本以控制流程圖的特征來進(jìn)行同源性的分析。

提取基本塊的所有完整執(zhí)行流程中的跳轉(zhuǎn)邏輯，生成跳轉(zhuǎn)邏輯序列，表示如下：L=（n，t1，t2，t3，….，tn），t有兩種取值：在跳轉(zhuǎn)處為true的分支，t=1；在跳轉(zhuǎn)處為false的分支，t=0；為call、jmp的分支，略過。

設(shè)基本塊A和基本塊B，基本塊A的執(zhí)行流程有CA個(gè)，基本塊B的執(zhí)行流程有CB個(gè)，基本塊A和基本塊B的執(zhí)行流程中的跳轉(zhuǎn)邏輯表示為：

基本塊A和基本塊B的跳轉(zhuǎn)邏輯相似度L-Similarity可表示為：

對于n值相等的兩個(gè)跳轉(zhuǎn)邏輯序列才計(jì)算其相似度。對于的，或許有幾個(gè)的值與它相等。

以圖1為例，跳轉(zhuǎn)邏輯序列集為：

以win7 32位系統(tǒng)下的kernel32.dll的LoadLibraryA為對比，將圖1所示基本塊的控制流程圖轉(zhuǎn)換為跳轉(zhuǎn)邏輯序列集：

由公式（1）得

1.2 基本塊代碼序列特征

在生物學(xué)上，常用矩陣作圖法計(jì)算DNA序列的相似度，其原理如下：構(gòu)成DNA序列的四種堿基對分別表示為{A，C，G，T}，將生物分子序列抽象為對應(yīng)的字符串，進(jìn)行序列比較的兩個(gè)序列分別放在矩陣的X軸和Y軸上，當(dāng)對應(yīng)的行與列的序列字符匹配時(shí)，就在矩陣對應(yīng)的位置做“點(diǎn)”標(biāo)記，最終形成點(diǎn)矩陣。如果兩條序列完全相同，則點(diǎn)矩陣中所有的點(diǎn)將構(gòu)成一條對角線，如圖2。

圖2 完全相似序列點(diǎn)陣圖

圖3 非等長不完全相似序列點(diǎn)陣圖

如果兩條序列存在相同子串，則對于每一個(gè)相同的子串對都有一條與對角線平行的由標(biāo)記點(diǎn)組成的斜線，如圖3。所以找兩條序列的最佳比對實(shí)際上就是在矩陣標(biāo)記圖中找非重疊平行斜線的最長的組合。

當(dāng)兩條序列中有很多匹配的字符時(shí)會(huì)形成很多點(diǎn)標(biāo)記，導(dǎo)致點(diǎn)陣圖變得復(fù)雜和模糊，此時(shí)便需要引入滑動(dòng)窗口來代替一次一個(gè)點(diǎn)位的比較。設(shè)滑動(dòng)窗口為H，相似度閾值為h（h

因此，本文借鑒了生物學(xué)上計(jì)算DNA序列相似度的矩陣作圖法和打分矩陣[5]的方法及思路，利用二維數(shù)組編程模擬點(diǎn)矩陣，實(shí)現(xiàn)對可執(zhí)行二進(jìn)制匯編代碼序列的相似性度量。

對需要比較的兩個(gè)二進(jìn)制匯編代碼序列提取匯編指令操作符，分別表示為：

滑動(dòng)窗口值設(shè)為H，打分規(guī)則為：

sequenceA和sequenceB比對得出打分矩陣ScoreMatrix，掃描ScoreMatrix得到打分矩陣非重疊平行斜線的最長組合的序列長度：

sequenceA和sequenceB中出現(xiàn)的相同序列長度為SC。

該矩陣算法能檢測出連續(xù)相同指令序列，并且能有效消除指令重排的影響，準(zhǔn)確地得出兩個(gè)指令序列的相似度。

1.3 基本塊子函數(shù)名特征

由于每個(gè)代碼作者在給函數(shù)和變量取名時(shí)會(huì)有一定的習(xí)慣和慣性思維[6]，所以基本塊中的字符特征能作為代碼同源性檢測的重要依據(jù)。

在二進(jìn)制代碼中，call指令常常會(huì)泄露一定的字符串特征，這些字符串有些是代碼作者命名的，也有些是系統(tǒng)提供的API接口函數(shù)名。經(jīng)過編譯鏈接的可執(zhí)行二進(jìn)制代碼在功能相同處調(diào)用的系統(tǒng)函數(shù)是相同的。因此本文從call指令的操作數(shù)中提取有效的子函數(shù)名作為另一重要的匹配特征。

子函數(shù)名的相似性判斷采用俄國科學(xué)家Vladimir Levenshtein發(fā)明的Levenshtein Distance算法[7]。該算法的原理是計(jì)算兩個(gè)字符串之間通過最少步驟使兩個(gè)字符串相同。每個(gè)步驟的操作方法是修改、增加或者刪除一個(gè)字符。這個(gè)最少步驟即為編輯距離ED。

設(shè)基本塊A和基本塊B，分別掃描A、B基本塊所有的call指令，提取call指令的操作數(shù)即子函數(shù)名稱，過濾掉為8個(gè)16進(jìn)制數(shù)的函數(shù)名，得到兩個(gè)字符串集StrA和StrB，并且m>n。

兩個(gè)字符串集的相似度為：

以圖1和圖2為例，提取字符串特征：

StrA=（6，_strcmpi，RtlAllocateHeap，LoadLibraryExA，LoadLibraryA，GetWindowsDirectoryA，RtlFreeHeap）

StrB=（8，_strcmpi，LoadLibraryExA_0，LoadLibraryA，KernelBaseGetGlobalData，__imp_RtlAllocateHeap，GetWindowsDirectoryA_0，strncat_s，__imp_RtlFreeHeap）

對比結(jié)果如表1所示，因此：

表1 win xp與win7 32位kerlnel32.dll LoadLibrary子函數(shù)名特征對比

1.4 權(quán)重與閾值

為考慮到函數(shù)名變化太大無可比較性時(shí)（借鑒代碼者很容易更改函數(shù)名），則字符串特征指紋信息的相似度會(huì)拉低總體相似度的值而產(chǎn)生漏報(bào)。所以，通過提供調(diào)節(jié)指紋信息權(quán)重的接口，來排除已確定可不予比較的因素或減小某一指紋信息的影響程度以減小誤報(bào)率。即用u、v和（1-u-v）分別表示邏輯跳轉(zhuǎn)特征、代碼序列特征和子函數(shù)名特征的所占權(quán)重，通過調(diào)節(jié)權(quán)重比例，綜合量化出兩個(gè)基本塊的整體相似度，總相似度可表示為公式（4）。

2 實(shí)驗(yàn)結(jié)果及分析

利用Win XP 32位系統(tǒng)與Win7 32位系統(tǒng)下的同名DLL文件以及常見文字處理工具notepad的不同版本作為實(shí)驗(yàn)樣本，得出相關(guān)測試結(jié)果如表2。

表2 u=v=1/3 測試結(jié)果

在win XP和win7 32位的kernel32.dll的LoadLibrary基本塊的對比中，F(xiàn)similarity的值為0.8576，說明盡管系統(tǒng)版本不一樣，但調(diào)用的子函數(shù)基本上是相同的，并且跳轉(zhuǎn)邏輯相似度也遠(yuǎn)遠(yuǎn)高于表中其他對比項(xiàng)；在win7 32位的kernel32.dll的LoadLibrary與DllEntryPoint基本塊的對比中，F(xiàn)similarity為0說明兩個(gè)基本塊調(diào)用的子函數(shù)完全不同，這反映出兩個(gè)基本塊所完成的功能是完全不一樣的，并且跳轉(zhuǎn)邏輯的相似度也只有0.0370；用VS2010編譯的Helloworld.exe與win7 32位的kernel32.dll的LoadLibrary基本塊做對比發(fā)現(xiàn)Ssimilarity的值與前兩項(xiàng)對比值較接近，這是因?yàn)檫@些對比中的二進(jìn)制文件都是同一編譯器生成的，在調(diào)用函數(shù)時(shí)的堆棧操作的代碼特征是一樣的，而在win7 32位系統(tǒng)自帶的notepad.exe與asm編譯的wordpad.exe的對比中，Ssimilarity的值卻只有0.0571，這是因?yàn)殡m然兩個(gè)文字處理程序notepad.exe和wordpad.exe的功能大致相同，但是由不同語言、不同編譯器生成的，不僅在調(diào)用函數(shù)時(shí)的堆棧操作的特征不一樣，在功能實(shí)現(xiàn)的調(diào)用函數(shù)以及調(diào)用函數(shù)的順序都是不一樣的，反映在Ssimilarity上的結(jié)果就是Ssimilarity的值非常低。

本文從主流安全網(wǎng)站上收集到被曝光的10個(gè)APT組織流出的相關(guān)代碼樣本，將這些代碼樣本作為測試數(shù)據(jù)，對比傳統(tǒng)的基于控制流程圖的同源性檢測方法，得到測試結(jié)果如表3。

實(shí)驗(yàn)中所用的同源測試樣本來自于不同的APT組織被曝光的利用代碼，由于這些被捕獲到的代碼樣本并不是完整的可執(zhí)行二進(jìn)制文件，所以傳統(tǒng)的基于控制流程圖的同源性分析方法能檢測出的同源樣本數(shù)量有限，而本論文提出的方法能以更細(xì)粒度的分析策略檢測出二進(jìn)制可執(zhí)行代碼的同源性。

表3 同源樣本檢測對比結(jié)果

3 總結(jié)

二進(jìn)制代碼的同源性分析對惡意代碼的溯源和代碼抄襲的確定有著重要的輔助作用。本文通過提取基本塊內(nèi)部的跳轉(zhuǎn)邏輯、代碼序列和子函數(shù)名的指紋信息，以更細(xì)粒度的對比分析算法來確定二進(jìn)制代碼同源性，該方法能對可執(zhí)行二進(jìn)制代碼進(jìn)行量化分析，以準(zhǔn)確的代碼特征取證完成二進(jìn)制代碼同源性的判斷過程，得到準(zhǔn)確結(jié)果。

[1]錢雨村，彭國軍，王瀅等.惡意代碼同源性分析及家族聚類[J].計(jì)算機(jī)工程與應(yīng)用，2015.

[2]Kunhua Zhu，Yancui Li．Binary Software Copy Detection Scheme based on Fingerprint Signatures．Journal of Convergence Information Technology（JCIT）and Control Flow Graph[J]，2012.

[3]趙連朋.一種基于素?cái)?shù)存儲(chǔ)的關(guān)聯(lián)規(guī)則算法[J].計(jì)算機(jī)工程與應(yīng)用，2006.

[4]王建新，楊凡，韓鋒.二進(jìn)制文件比對中的指令歸并優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013.

[5]袁二毛，郭丹，胡學(xué)鋼，吳信東.基于打分矩陣的生物序列頻繁模式挖掘[J].模式識(shí)別與人工智能，2016.

[6]董志強(qiáng).編碼心理學(xué)分析病毒同源性[J].信息安全與通信保密，2005.

[7]Frederic P. Miller，Agnes F. Vandome，John McBrewster. Levenshtein Distance[M]， 2013.