肖睿卿，劉勝利，顏 猛，肖 達(dá)，孫豪彬

1.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001 2.西安報(bào)業(yè)傳媒集團(tuán)，西安 710002

節(jié)點(diǎn)層次化的二進(jìn)制文件比對(duì)技術(shù)

肖睿卿1，劉勝利1，顏 猛2，肖 達(dá)1，孫豪彬1

1.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001 2.西安報(bào)業(yè)傳媒集團(tuán)，西安 710002

當(dāng)前二進(jìn)制文件比對(duì)技術(shù)主流是以BinDiff為代表的結(jié)構(gòu)化比對(duì)方法，存在結(jié)構(gòu)相似導(dǎo)致的誤匹配、分析耗時(shí)較高的問(wèn)題。針對(duì)該問(wèn)題提出一種基于節(jié)點(diǎn)層次化、價(jià)值化的匹配方法。通過(guò)提取函數(shù)節(jié)點(diǎn)在函數(shù)調(diào)用圖中的層次與函數(shù)在調(diào)用網(wǎng)絡(luò)中的價(jià)值，對(duì)層次模糊的節(jié)點(diǎn)提供了節(jié)點(diǎn)層次估算算法，最后遞歸匹配節(jié)點(diǎn)。實(shí)驗(yàn)表明，該方法避免了結(jié)構(gòu)相似導(dǎo)致的誤匹配，其時(shí)耗低于結(jié)構(gòu)化比對(duì)工具Bindiff的1/2，節(jié)點(diǎn)匹配數(shù)量減少在15%以內(nèi)。該方法可有效提高嵌入式設(shè)備固件的跨版本相似性分析效率。

二進(jìn)制文件比對(duì)；層次分析；節(jié)點(diǎn)價(jià)值；結(jié)構(gòu)化圖形

1 引言

二進(jìn)制文件相似性比對(duì)是逆向工程中一種重要的靜態(tài)分析方法，用以刻畫二進(jìn)制文件之間的關(guān)聯(lián)性，常用于軟件剽竊檢測(cè)、惡意程序同源性檢測(cè)、補(bǔ)丁比對(duì)等領(lǐng)域。隨著軟件功能的復(fù)雜化，部分軟件的程序規(guī)模不斷提高，傳統(tǒng)二進(jìn)制文件相似性分析方法在效率和準(zhǔn)確性方面面臨新的挑戰(zhàn)。

二進(jìn)制文件比對(duì)的方法主要分為兩大類：指令級(jí)比對(duì)和結(jié)構(gòu)化比對(duì)。指令級(jí)比對(duì)包括：二進(jìn)制字節(jié)比較、反匯編后文本比較、基于匯編指令圖形化比較等[1]。二進(jìn)制字節(jié)比較優(yōu)勢(shì)在于比對(duì)粒度細(xì)，但沒(méi)有基于指令語(yǔ)義比較，微量變化即影響相似性識(shí)別（如：程序僅替換操作寄存器且功能不變）。反匯編后文本比較減輕了比較的工作量，同時(shí)兼顧字節(jié)間的聯(lián)系，以匯編的角度來(lái)比對(duì)相似性。文獻(xiàn)[2]提出基于匯編指令圖形化比較主要是指基于匯編指令的相似性圖形比較，此種方法通過(guò)將每條指令設(shè)為圖形的節(jié)點(diǎn)，通過(guò)優(yōu)化CFG圖以獲取結(jié)果。2004年，Halvar Flake于文獻(xiàn)[3]提出了基于結(jié)構(gòu)化圖形的比較方法，該方法通過(guò)將文件結(jié)構(gòu)圖形化，利用控制流圖（CFG）比較，函數(shù)調(diào)用圖（FCG）進(jìn)行簽名并比較，提升了對(duì)程序相似比對(duì)的性能。文獻(xiàn)[4]在前文基礎(chǔ)上引入了屬性的概念，通過(guò)屬性提高比對(duì)效率。文獻(xiàn)[5]亦在結(jié)合指令比較和結(jié)構(gòu)化比較的優(yōu)勢(shì)優(yōu)化比較效果。文獻(xiàn)[7-11]中主要在依靠結(jié)構(gòu)化簽名和屬性進(jìn)行優(yōu)化，并將算法加以實(shí)現(xiàn)，如魏強(qiáng)等人通過(guò)可信基點(diǎn)優(yōu)化了匹配節(jié)點(diǎn)傳播算法，但本質(zhì)都是在結(jié)構(gòu)化簽名和屬性兩個(gè)方面進(jìn)行擴(kuò)展，簽名重點(diǎn)圍繞在CFG圖。此后，結(jié)構(gòu)化比較又逐步衍生出了，基于API調(diào)用序列比較等方向。文獻(xiàn)[12]闡述了指令重排與指令歸并減少了編譯器優(yōu)化帶來(lái)的匹配難度。隨著軟件檢測(cè)需求不斷增加，開(kāi)始出現(xiàn)針對(duì)軟件特別是惡意軟件比對(duì)的研究。文獻(xiàn)[13]引入了相似度衡量方法。文獻(xiàn)[14]將比對(duì)的側(cè)重傾向于FCG圖，這不同于以往的二進(jìn)制文件比對(duì)，特別是補(bǔ)丁比對(duì)的側(cè)重CFG圖。文獻(xiàn)[16]利用確定子圖和相似子圖進(jìn)行基于子圖的相似性分析，提高了對(duì)惡意程序檢測(cè)的效率，脫離了三元組簽名的制約。但二進(jìn)制比對(duì)大體都是在圍繞控制流圖，函數(shù)調(diào)用圖，以三元組〈節(jié)點(diǎn)數(shù)，邊數(shù)，子圖調(diào)用數(shù)＞及圖所含不同屬性（如：出入度，所含特殊數(shù)據(jù)）為基礎(chǔ)進(jìn)行比對(duì)。這種技術(shù)路線存在以下問(wèn)題：

（1）三元組中多為數(shù)量特征，節(jié)點(diǎn)出度、入度等附加屬性也多是如此，當(dāng)程序規(guī)模較大，這種單節(jié)點(diǎn)屬性效果欠佳。

（2）編譯器的不同會(huì)導(dǎo)致函數(shù)節(jié)點(diǎn)的結(jié)構(gòu)形成上產(chǎn)生一定的出入，即使語(yǔ)義相同，因?yàn)閮?yōu)化等因素的影響，也可能產(chǎn)生不同結(jié)構(gòu)的編譯結(jié)果。

（3）傳統(tǒng)匹配需要提供匹配節(jié)點(diǎn)作為初始化的參數(shù)，以降低函數(shù)匹配工作量，同時(shí)提高匹配精度。對(duì)于嵌入式等程序，規(guī)模較大，本身無(wú)公開(kāi)API，可供參考的外部屬性（如：API，字符串）相對(duì)整個(gè)程序規(guī)模而言較少，初始匹配節(jié)點(diǎn)影響范圍較小，需要更多的利用結(jié)構(gòu)圖本身的信息。

針對(duì)現(xiàn)有方法的不足與實(shí)際問(wèn)題的需求，本文在函數(shù)調(diào)用圖基礎(chǔ)上，提出基于節(jié)點(diǎn)價(jià)值與層次的刻畫方法，進(jìn)行二進(jìn)制文件相似性分析。

2 相關(guān)概念

定義1（函數(shù)調(diào)用圖）函數(shù)調(diào)用圖（Function Call Gragh，F(xiàn)CG），由 G=(VG,EG)構(gòu)成的有向圖表示。其中，VG表示節(jié)點(diǎn)集，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)函數(shù)VG={fi|1≤i≤n,i∈Z}，其中Z為整數(shù)集，n為函數(shù)個(gè)數(shù)；EG為邊集，表示函數(shù)調(diào)用關(guān)系的全集，EG?VG×VG，由序偶組成，函數(shù)fi調(diào)用了若邊集EG存在元素則說(shuō)明函數(shù) fi調(diào)用了函數(shù) fj。

為便于后續(xù)定義的描述，參考樹(shù)結(jié)構(gòu)的定義，令集合G中入度為零的節(jié)點(diǎn)作為FCG的根節(jié)點(diǎn)。令集合G中初度為零的節(jié)點(diǎn)作為FCG的葉子節(jié)點(diǎn)。稱 fi，fj兩節(jié)點(diǎn)存在父子關(guān)系，該邊為父節(jié)點(diǎn) fi的度邊、子節(jié)點(diǎn) fj的入度邊。需要說(shuō)明的是，在實(shí)際分析過(guò)程中，由于間接調(diào)用的存在，部分函數(shù)雖然代碼邏輯上并不是根節(jié)點(diǎn)，但在函數(shù)調(diào)用圖中入度為零，無(wú)法與代碼邏輯上的根節(jié)點(diǎn)區(qū)分，因此函數(shù)調(diào)用圖在此種情況下將以森林的形式存在。

定義2（函數(shù)調(diào)用序列）若函數(shù) fa是 fb的祖先，則存在調(diào)用序列表示一條從函數(shù)φ1到函數(shù)φn的調(diào)用路徑，x表示調(diào)用序列的序號(hào)用以區(qū)分調(diào)用序列，φ表示函數(shù)節(jié)點(diǎn)，其角標(biāo)表示函數(shù)節(jié)點(diǎn)在本函數(shù)調(diào)用序列Seqx( )fa,fb中的次序，設(shè)有映射關(guān)系ρ滿足公式（1），則調(diào)用序列滿足公式（2）。

即，對(duì)于調(diào)用序列Seqx( )fa,fb內(nèi)的任意兩個(gè)連續(xù)元組成的序偶，一定屬于邊集EG。存在次序不同的兩個(gè)位置代表一個(gè)函數(shù)，見(jiàn)公式（3）的情況。如果滿足公式（4），稱調(diào)用序列為無(wú)重調(diào)用序列SeqNx( )φ1,φn。

|Seqx( f1,fn)|表示路徑Seqx( f1,fn)的長(zhǎng)度，若，稱Seqk( fa,fb)為函數(shù)fa到 fb的最短函數(shù)調(diào)用序列，其中 fa,fb∈VG。

定義3（節(jié)點(diǎn)深度）對(duì)于一個(gè)節(jié)點(diǎn) fn，如果有根節(jié)點(diǎn) fa，且 fa,fn之間存在無(wú)重調(diào)用序列SeqNx( fa,fn)，則稱路徑長(zhǎng)度 | SeqNx( fa,fn) |為此條路徑下節(jié)點(diǎn) fn的深度Dp(S eqNx( fa,fn) )。對(duì)于所有根節(jié)點(diǎn)到此節(jié)點(diǎn)路徑下深度的均值，稱為該節(jié)點(diǎn) fn的深度Dp(fn)。根節(jié)點(diǎn)深度為0。

定義4（節(jié)點(diǎn)高度）對(duì)于一個(gè)節(jié)點(diǎn) fn，如果有葉子節(jié)點(diǎn) fb且 fn,fb之間存在無(wú)重調(diào)用序列SeqNx( fn,fb)，則稱路徑長(zhǎng)度 | SeqNx( fn,fb) |為此條路徑下節(jié)點(diǎn) fn的高度Hi(S eqNx( fn,fb) )。此節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)路徑高度的均值，稱為該節(jié)點(diǎn) fn的高度Hi(fn)。葉子節(jié)點(diǎn)高度為0。

定義5（節(jié)點(diǎn)依賴度）對(duì)于一個(gè)節(jié)點(diǎn) fn，被s個(gè)節(jié)點(diǎn)直接調(diào)用累積x次，若某一節(jié)點(diǎn) fm對(duì) fn直接調(diào)用次數(shù)為 y次，則Rely( fm,fn)=x/y代表節(jié)點(diǎn) fn對(duì)于 fm的依賴度。對(duì)于依賴度的分布可以有效觀察出函數(shù)功能主要服務(wù)傾向。

定義6（循環(huán)調(diào)用節(jié)點(diǎn)）如果函數(shù)調(diào)用圖存在調(diào)用序列Seqx( fa,fa)，則稱節(jié)點(diǎn) fa為循環(huán)調(diào)用節(jié)點(diǎn)。調(diào)用序列Seqx( fa,fa)稱為 fa的一條循環(huán)路徑。如果調(diào)用序列滿足公式（5），則稱該序列為單純循環(huán)路徑SeqSx( fa,fa)，反之稱為復(fù)雜循環(huán)路徑SeqCx( fa,fa)。

3 基于節(jié)點(diǎn)層次與節(jié)點(diǎn)價(jià)值的匹配方法

本方法的輸入是兩個(gè)程序的二進(jìn)制文件A,B。首先，從兩個(gè)二進(jìn)制文件中分別提取函數(shù)調(diào)用關(guān)系圖GA,GB。通過(guò)節(jié)點(diǎn)層次記錄算法，對(duì)節(jié)點(diǎn)所處高度Hi與深度Dp進(jìn)行記錄。而后，通過(guò)節(jié)點(diǎn)價(jià)值評(píng)估算法，對(duì)節(jié)點(diǎn)在調(diào)用圖中的價(jià)值進(jìn)行評(píng)估，并對(duì)節(jié)點(diǎn)間的依賴關(guān)系進(jìn)行分析。最后，利用節(jié)點(diǎn)層次、節(jié)點(diǎn)價(jià)值、節(jié)點(diǎn)依賴關(guān)系進(jìn)行程序匹配。

基于節(jié)點(diǎn)層次與節(jié)點(diǎn)價(jià)值的匹配方法減少了對(duì)輸入信息的依賴，主要利用函數(shù)在函數(shù)調(diào)用圖中結(jié)構(gòu)化的屬性。

3.1 函數(shù)調(diào)用圖提取

實(shí)際條件下，由于程序的二進(jìn)制文件可能存在一定的反分析保護(hù)措施，需要對(duì)程序進(jìn)行預(yù)處理。但文件脫殼等預(yù)處理方法與本文主題關(guān)聯(lián)不大，在此不做深入討論。本文默認(rèn)將要比對(duì)的二進(jìn)制文件A,B為無(wú)反分析保護(hù)或已解除反分析保護(hù)的形態(tài)。函數(shù)調(diào)用圖最終以矩陣來(lái)表示，使用二維數(shù)組進(jìn)行存儲(chǔ)。提取過(guò)程如下：

（1）識(shí)別二進(jìn)制文件中的函數(shù)，統(tǒng)計(jì)函數(shù)數(shù)量n，構(gòu)建 n?n矩陣 Matrix()G ，用二維數(shù)組G[n+1][n+1]表示，將其中所有分量初始化為0。

（2）為每個(gè)函數(shù)單獨(dú)分配一個(gè)獨(dú)立的序號(hào)n,(0＜i＜n+1)，如果函數(shù) fi直接調(diào)用 fj，且 fi調(diào)用 fj的次數(shù)為s次，則將G[i][j]的值替換為 s，并將G[i][0],G[0][j]的值各加s，分別表示 fi調(diào)用子函數(shù)次數(shù)和，fj被調(diào)用次數(shù)和。

3.2 基于節(jié)點(diǎn)層次的分析方法

基于節(jié)點(diǎn)層次的分析方法主要需要針對(duì)節(jié)點(diǎn)在函數(shù)調(diào)用圖中的高度和深度進(jìn)行分析，并形成節(jié)點(diǎn)深度矩陣和節(jié)點(diǎn)高度矩陣。

3.2.1 非循環(huán)調(diào)用節(jié)點(diǎn)深度計(jì)算

根據(jù)節(jié)點(diǎn)深度的概念，構(gòu)建節(jié)點(diǎn)(n+1)?(n+1)深度矩陣Matrix(D p)，采用二維數(shù)組Dp[n+1][n+1]存儲(chǔ)節(jié)點(diǎn)深度，將其中所有分量初始化為-1。

計(jì)算節(jié)點(diǎn)深度矩陣有兩種方法，第一種方法主要依靠父子關(guān)系從子節(jié)點(diǎn)上溯，隨機(jī)取一個(gè)深度未知的節(jié)點(diǎn)fj。如果 fj存在未知深度父節(jié)點(diǎn) fi，則計(jì)算 fi深度。如果 fi深度無(wú)法計(jì)算則遞歸調(diào)用父節(jié)點(diǎn)深度計(jì)算過(guò)程。

第二種方法主要依靠逐層計(jì)算的思想，首先對(duì)所有根節(jié)點(diǎn)的深度標(biāo)注為0，而后對(duì)所有已知深度節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行遍歷，如果子節(jié)點(diǎn)的所有父節(jié)點(diǎn)深度已經(jīng)明確，計(jì)算出該子節(jié)點(diǎn)深度，不斷擴(kuò)大已知節(jié)點(diǎn)的范圍，直至計(jì)算出所有節(jié)點(diǎn)的深度。

節(jié)點(diǎn)深度計(jì)算公式如公式（6），由于G[n+1][n+1]數(shù)組初始置為0，則滿足公式（7）。

由于節(jié)點(diǎn)深度是基于父節(jié)點(diǎn)的深度已知完成的。當(dāng)函數(shù)調(diào)用序列Seqx不是無(wú)重調(diào)用序列SeqNx時(shí)，即存在函數(shù)循環(huán)調(diào)用至自身的情況時(shí)，必然有節(jié)點(diǎn)無(wú)法求出深度。在此，先提出非循環(huán)調(diào)用節(jié)點(diǎn)的深度計(jì)算算法，考慮到函數(shù)調(diào)用圖中存在循環(huán)調(diào)用節(jié)點(diǎn)，如果使用方法一需要解決上溯去循環(huán)的問(wèn)題，因此使用方法二。流程如下：

（1）構(gòu)建二維數(shù)組Dp[n+1][n+1]用以存儲(chǔ)節(jié)點(diǎn)深度。初始化二維數(shù)組，對(duì)所有節(jié)點(diǎn)賦值-1。定義已知節(jié)點(diǎn)緩沖區(qū)，一維數(shù)組S[n+1]，初始化為0。定義結(jié)構(gòu)體Ns，記錄待處理節(jié)點(diǎn)信息，其中包括節(jié)點(diǎn)序號(hào)Ns.Index，未知深度父節(jié)點(diǎn)序號(hào)數(shù)組Ns.Uf[n+1]，初始化為-1，未知父節(jié)點(diǎn)數(shù)量Ns.Numf。Ns以鏈表形式存在。

（2）搜索G[0][1]到G[0][n]，即所有函數(shù)的入度，如果節(jié)點(diǎn) fi入度為0，表示此節(jié)點(diǎn)為根節(jié)點(diǎn)或間接調(diào)用節(jié)點(diǎn)，對(duì) Dp[0～n][i]賦值為0。

（3）搜索 Dp[0][1～n]，如果 Dp[0][j]＞0，說(shuō)明該節(jié)點(diǎn)深度已知，若S[j]為0，表示該節(jié)點(diǎn)未處理過(guò)，執(zhí)行下一步，反之表示處理過(guò)。若所有深度已知節(jié)點(diǎn)都已經(jīng)表明被處理過(guò)，則結(jié)束。

（4）遍歷Ns所在鏈表，本節(jié)點(diǎn)是否為某鏈表節(jié)點(diǎn)的未知父節(jié)點(diǎn)，如果是，則未知父節(jié)點(diǎn)數(shù)量Ns.Numf減1，并把Ns.Uf[i]置為0。調(diào)整Ns鏈表順序，將Ns.Numf小的靠前放置，如果Ns鏈表節(jié)點(diǎn)(Ns.Index=k)沒(méi)有未知父節(jié)點(diǎn)，則從鏈表中去掉，并依據(jù)公式計(jì)算該函數(shù)節(jié)點(diǎn)的深度，存放在Dp[0][k]。

（5）在G[0][1～n]中逐個(gè)檢索 fj的子節(jié)點(diǎn)，對(duì)于檢索到的子節(jié)點(diǎn) fk，若Dp[0][k]為-1，表明未計(jì)算出該節(jié)點(diǎn)深度，將 Dp[j][k]置為 Dp(fj)+1，在 G[1～n][k]中檢索 fk的其他父節(jié)點(diǎn)，如果不存在深度未知父節(jié)點(diǎn)，則計(jì)算 fk深度存放于Dp[0][k]。否則，統(tǒng)計(jì)該節(jié)點(diǎn)的未知父節(jié)點(diǎn)信息，申請(qǐng)新的Ns鏈表節(jié)點(diǎn)，將未知父節(jié)點(diǎn) fi對(duì)應(yīng)的Ns.Uf[i]置1，插入Ns鏈表。檢索完畢后，跳回執(zhí)行步驟（3）。

此時(shí)，獲取所有深度未知節(jié)點(diǎn)，可以形成一張子圖G1，如果從G1中再計(jì)算出圖中非循環(huán)調(diào)用節(jié)點(diǎn)的節(jié)點(diǎn)高度，并將G1中的高度已知節(jié)點(diǎn)剔除，可以形成一張循環(huán)調(diào)用子圖G2，G2中的任何節(jié)點(diǎn)都可以找到一條調(diào)用序列回到節(jié)點(diǎn)自身。

3.2.2 循環(huán)調(diào)用節(jié)點(diǎn)深度計(jì)算

一個(gè)循環(huán)調(diào)用節(jié)點(diǎn)，可以存在多條循環(huán)路徑。而一條循環(huán)路徑中選擇不同的節(jié)點(diǎn)作為深度值最小的點(diǎn)（下文稱“基點(diǎn)”），將形成不同的深度矩陣。如果在子圖G1中存在一條單純循環(huán)路徑與其他循環(huán)路徑不相交，那么子圖中將需要至少兩個(gè)循環(huán)路徑的基點(diǎn)來(lái)完成深度矩陣Matrix(D p)。解決循環(huán)調(diào)用路徑中節(jié)點(diǎn)的深度的問(wèn)題在于確定合理的基點(diǎn)。

要確定基點(diǎn)，首先要確定目標(biāo)處理的循環(huán)路徑，優(yōu)先選擇路徑較長(zhǎng)的單純循環(huán)路徑，以減小后續(xù)運(yùn)算的規(guī)模。循環(huán)調(diào)用路徑的基點(diǎn)必須具備深度已知父節(jié)點(diǎn)。函數(shù)調(diào)用圖中，靠近根節(jié)點(diǎn)的節(jié)點(diǎn)一般入度較低、出度較高，而靠近葉子節(jié)點(diǎn)的節(jié)點(diǎn)一般入度較高，出度較低。函數(shù)調(diào)用圖整體接近于梭形。因?yàn)楦?jié)點(diǎn)端要分支出多種邏輯情況，而葉子節(jié)點(diǎn)端函數(shù)處理最終會(huì)回歸原子性的函數(shù)操作，如API，庫(kù)函數(shù)。

由于當(dāng)前是在計(jì)算函數(shù)的深度調(diào)用圖，因此基點(diǎn)選取考慮以下條件：

（1）節(jié)點(diǎn)具備已知深度父節(jié)點(diǎn)，且對(duì)未知父節(jié)點(diǎn)的依賴度之和控制在一定范圍內(nèi)。

（2）節(jié)點(diǎn)的已知父節(jié)點(diǎn)平均深度較小。

（3）節(jié)點(diǎn)的出度較大。

（4）計(jì)算兩個(gè)基點(diǎn)互相的依賴度，依賴對(duì)方較小的節(jié)點(diǎn)處于深度值較小的位置，也就是更接近根節(jié)點(diǎn)。

（5）在實(shí)際比對(duì)過(guò)程中，如果程序規(guī)模較大，可能出現(xiàn)從多個(gè)節(jié)點(diǎn)中篩選基點(diǎn)的情況。

在確定了基點(diǎn) fi后，將不再考慮未知深度父節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的深度影響，對(duì)Dp[1～n][i]值不為正的點(diǎn)置-1，基點(diǎn)將通過(guò)已知深度父節(jié)點(diǎn)計(jì)算基點(diǎn)的深度值，并計(jì)入數(shù)組Dp[0][i]，同時(shí)，由于基點(diǎn)忽略了未知深度父節(jié)點(diǎn)，基點(diǎn)入度將有所改變，將Dp[i][0]處填寫已知深度節(jié)點(diǎn)的入度和。

同時(shí)，對(duì)于計(jì)算節(jié)點(diǎn)深度的公式進(jìn)行修改，如公式（8）。

此后采用前文無(wú)循環(huán)調(diào)用節(jié)點(diǎn)的節(jié)點(diǎn)深度計(jì)算算法，繼續(xù)完善深度矩陣，如果深度矩陣仍有節(jié)點(diǎn)深度未知，則說(shuō)明仍有循環(huán)路徑存在，繼續(xù)確定循環(huán)路徑基點(diǎn)，重復(fù)上述步驟，直至完成深度矩陣。

節(jié)點(diǎn)高度矩陣Matrix( )Hi的構(gòu)建參看節(jié)點(diǎn)深度矩陣構(gòu)建流程，以葉子節(jié)點(diǎn)為起始點(diǎn)，其高度初始賦值0，高度調(diào)用圖存儲(chǔ)數(shù)組Hi[n+1][n+1]。

3.3 基于節(jié)點(diǎn)價(jià)值的分析方法

通過(guò)節(jié)點(diǎn)的出入度，可以基本地反應(yīng)節(jié)點(diǎn)的被調(diào)用和調(diào)用子節(jié)點(diǎn)情況。但是，節(jié)點(diǎn)在程序中的重要性并不能得以直觀體現(xiàn)。補(bǔ)充定義如下。

定義7（節(jié)點(diǎn)價(jià)值）使用四元組表示，Val()fi={Fnum,Snum,T,Iv}。Fnum表示父節(jié)點(diǎn)數(shù)量，Snum表示子節(jié)點(diǎn)數(shù)量，價(jià)值類型T表示價(jià)值偏重，計(jì)算公式如公式（9），T＞0.5表示為收斂?jī)A向，T＜-0.5表示為發(fā)散傾向，其他情況表示均勻傾向。Iv表示節(jié)點(diǎn)間接價(jià)值。

節(jié)點(diǎn)間接價(jià)值Iv計(jì)算流程：

（1）將 fi所有父節(jié)點(diǎn)與 fi節(jié)點(diǎn)歸并為一個(gè)新節(jié)點(diǎn)fi'，并將其父節(jié)點(diǎn)所有數(shù)據(jù)計(jì)入新節(jié)點(diǎn) fi'。構(gòu)建新的函數(shù)調(diào)用矩陣Matrix( )G1存儲(chǔ)信息。

①對(duì)于任何 fi的父節(jié)點(diǎn) fj，提取函數(shù)調(diào)用矩陣中的G[1～n][j]的值，并將每個(gè)值累加到新矩陣Matrix( )G1對(duì)應(yīng)列 G1[1～n][i]中。

②對(duì)于任何 fi的子節(jié)點(diǎn) fk，提取函數(shù)調(diào)用矩陣中的G[1～n][k]的值，并將每個(gè)值累加到新矩陣Matrix( )G1對(duì)應(yīng)列 G1[1～n][i]中。

（2）計(jì)算節(jié)點(diǎn) fi'的入度和SumI( fi')與出度和SumO( fi')，并求出函數(shù)調(diào)用原矩陣Matrix(G)的入讀和SumI(G)出度和SumO(G )。節(jié)點(diǎn) fi的間接價(jià)值Iv計(jì)算公式如公式（10）。

節(jié)點(diǎn)間接價(jià)值Iv能夠反應(yīng)節(jié)點(diǎn)服務(wù)的父子節(jié)點(diǎn)在整個(gè)調(diào)用圖中的價(jià)值。即使存在兩個(gè)節(jié)點(diǎn)價(jià)值相近，但是節(jié)點(diǎn)服務(wù)對(duì)象在函數(shù)調(diào)用網(wǎng)絡(luò)的存在價(jià)值差異。

針對(duì)不同規(guī)模的兩個(gè)程序，定義7中的父子節(jié)點(diǎn)數(shù)量會(huì)受函數(shù)總數(shù)量的影響，導(dǎo)致可比性較差。因此，在進(jìn)行比較的過(guò)程中，對(duì)節(jié)點(diǎn)價(jià)值的描述需要進(jìn)行調(diào)整。

在此，對(duì)定義7做出補(bǔ)充，基于相對(duì)深度（或高度）測(cè)算的節(jié)點(diǎn)價(jià)值，將定義其中的Fnum，Snum做出修改，用父子節(jié)點(diǎn)數(shù)量在同層次節(jié)點(diǎn)數(shù)量中占比來(lái)表示。節(jié)點(diǎn)是否為同層次，可以通過(guò)節(jié)點(diǎn)深度（或高度）上下取整來(lái)確定。向上或向下取整只能選擇一個(gè)，并保證整個(gè)調(diào)用圖計(jì)算過(guò)程中只選用此方向。

當(dāng)兩個(gè)程序同節(jié)點(diǎn)層次的節(jié)點(diǎn)數(shù)量相差較大時(shí)，使用占比數(shù)據(jù)已經(jīng)無(wú)法滿足需求，此時(shí)，可以采用Findex,SIndex替代Fnum,Snum，分別表示父子節(jié)點(diǎn)數(shù)量在同層次節(jié)點(diǎn)數(shù)量占比值的大小排序，通過(guò)縱向的大小關(guān)系來(lái)完成比對(duì)。

3.4 結(jié)合節(jié)點(diǎn)層次與節(jié)點(diǎn)價(jià)值的匹配方法

在此，對(duì)函數(shù)節(jié)點(diǎn)定義進(jìn)行補(bǔ)充。

定義8（節(jié)點(diǎn)簽名）為便于后續(xù)分析，對(duì)函數(shù)調(diào)用圖中的函數(shù)節(jié)點(diǎn)三元組定義進(jìn)行擴(kuò)展，由N(fi)={BNum,ENum,SFNum,Dp,Hi,Val(fi)}表示，其中BNum表示節(jié)點(diǎn) fi基本塊數(shù)量，ENum表示函數(shù)控制流圖CFG的邊數(shù)，SFNum表示節(jié)點(diǎn)子函數(shù)數(shù)量，這三個(gè)變量可以參看文獻(xiàn)[3]。Dp表示節(jié)點(diǎn)深度，Hi表示節(jié)點(diǎn)高度，Val(fi)表示節(jié)點(diǎn)價(jià)值。

3.4.1 初始匹配點(diǎn)與擴(kuò)展匹配算法

傳統(tǒng)的匹配算法是通過(guò)輸入被比對(duì)程序的已知匹配點(diǎn)作為初始匹配節(jié)點(diǎn)開(kāi)始，通過(guò)在匹配節(jié)點(diǎn)集的子節(jié)點(diǎn)集合中尋找新的匹配節(jié)點(diǎn)來(lái)擴(kuò)大匹配節(jié)點(diǎn)集，直到匹配完成。如果程序主要調(diào)用方式為直接調(diào)用，且有明確的程序入口點(diǎn)，使用這種方法具備較高的效率。如果程序規(guī)模較大，存在大量間接調(diào)用，無(wú)明確入口點(diǎn)，匹配的效果受匹配點(diǎn)所處節(jié)點(diǎn)高度、節(jié)點(diǎn)價(jià)值影響較大。

在本文中，主要通過(guò)確定同一層次的節(jié)點(diǎn)加入待匹配節(jié)點(diǎn)集，通過(guò)比對(duì)待匹配集內(nèi)不同節(jié)點(diǎn)的價(jià)值，基于節(jié)點(diǎn)價(jià)值與基本三元組信息完成匹配。每向下分析一層，將上層匹配節(jié)點(diǎn)從待匹配集合去除。

3.4.2 同程序內(nèi)函數(shù)相似性

節(jié)點(diǎn)價(jià)值是用以描述函數(shù)的重要特征。當(dāng)同程序內(nèi)多個(gè)函數(shù)具備相似的父子節(jié)點(diǎn)關(guān)系時(shí)，不同節(jié)點(diǎn)的節(jié)點(diǎn)價(jià)值趨同和節(jié)點(diǎn)層次趨同將對(duì)跨程序逐函數(shù)匹配產(chǎn)生干擾。通過(guò)預(yù)處理，可以對(duì)此種情況加以利用。

定義9（公共父節(jié)點(diǎn)）對(duì)于函數(shù)調(diào)用圖G，滿足公式（11），則稱 fi是 fj和 fk的公共父節(jié)點(diǎn)。對(duì)于函數(shù)調(diào)用圖G，滿足公式（12），則稱 fi是 fj和 fk的公共子節(jié)點(diǎn)。

如果兩個(gè)函數(shù)節(jié)點(diǎn) fj和 fk的公共父節(jié)點(diǎn)數(shù)量在各自父節(jié)點(diǎn)數(shù)量中占比80%以上，則認(rèn)為兩函數(shù)具備相似的調(diào)用關(guān)系。通過(guò)這種方法，可以獲取具備關(guān)聯(lián)性的函數(shù)組合[fj,fk]。當(dāng)函數(shù)組合中的某一節(jié)點(diǎn)的控制流圖CFG結(jié)構(gòu)信息有一定變動(dòng)時(shí)，可通過(guò)組合中另一函數(shù)的匹配來(lái)提高匹配效率。

當(dāng)兩個(gè)函數(shù)的子節(jié)點(diǎn)具有相似性時(shí)，說(shuō)明兩個(gè)函數(shù)的功能具有一定相似性。考慮到子函數(shù)可能同時(shí)服務(wù)多個(gè)父函數(shù)，因此，衡量函數(shù)節(jié)點(diǎn)公共子節(jié)點(diǎn)的相似性，應(yīng)當(dāng)結(jié)合子函數(shù)調(diào)用次數(shù)。相似度計(jì)算公式如公式（13），表示 fj,fk的公共子節(jié)點(diǎn)對(duì)前者的相似度。

當(dāng)幾個(gè)函數(shù)的公共子節(jié)點(diǎn)相似度互相達(dá)到80%以上，則認(rèn)為幾個(gè)函數(shù)功能基本相似。如果其中某個(gè)子函數(shù)對(duì)父節(jié)點(diǎn)的依賴度主要集中在這幾個(gè)父函數(shù)中，則認(rèn)為該子函數(shù)具備核心功能。同時(shí)可以用公共子函數(shù)修正函數(shù)所處層級(jí)，將公共子函數(shù)的層次放在幾個(gè)父函數(shù)層次之下。

3.4.3 二進(jìn)制文件相似性度量流程

（1）選擇二進(jìn)制文件 A,B形成函數(shù)調(diào)用關(guān)系圖（FCG）。

（2）檢測(cè)兩個(gè)文件中各自父子節(jié)點(diǎn)的相似函數(shù)，確定關(guān)聯(lián)函數(shù)組集與近似功能函數(shù)集。

（3）進(jìn)行二進(jìn)制程序?qū)哟畏治?，確定函數(shù)高度矩陣和深度矩陣，同時(shí)利用近似功能函數(shù)集進(jìn)行層次修正。

（4）完成二進(jìn)制程序節(jié)點(diǎn)價(jià)值分析。

（5）進(jìn)行關(guān)聯(lián)函數(shù)組匹配，將兩個(gè)二進(jìn)制文件中的關(guān)聯(lián)函數(shù)組優(yōu)先測(cè)試匹配。

（6）以關(guān)聯(lián)函數(shù)數(shù)組匹配點(diǎn)為輸入，從根節(jié)點(diǎn)或葉子節(jié)點(diǎn)開(kāi)始，逐層次進(jìn)行節(jié)點(diǎn)匹配，方向?yàn)楦叨冗f增或深度遞增，將每一層不匹配節(jié)點(diǎn)融入下一層次繼續(xù)匹配。

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

在Windows平臺(tái)上使用Python語(yǔ)言，利用IDApython在IDA pro上進(jìn)行函數(shù)調(diào)用關(guān)系的抽取。使用C#語(yǔ)言完成后續(xù)工作，包括函數(shù)調(diào)用關(guān)系圖構(gòu)建、節(jié)點(diǎn)層次分析、節(jié)點(diǎn)價(jià)值分析、二進(jìn)制文件相似性分析。

4.1 驗(yàn)證性實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)主要驗(yàn)證文中方法能否有效檢測(cè)二進(jìn)制文件相似性以及函數(shù)匹配。通過(guò)實(shí)驗(yàn)，該方法能夠有效檢測(cè)出相似函數(shù)，針對(duì)規(guī)模較大的文件效果良好。

實(shí)驗(yàn)使用ELF文件Adventerprisek9-Mz 124-2 T與adventerprisek9-mz.123-11.T進(jìn)行檢測(cè)。其中，文件1節(jié)點(diǎn)數(shù)量147 011，文件2節(jié)點(diǎn)數(shù)量133 493，共檢測(cè)出匹配節(jié)點(diǎn)115 019個(gè)。

4.2 對(duì)比實(shí)驗(yàn)結(jié)果分析

二進(jìn)制文件比對(duì)工具Bindiff和PEdiff是經(jīng)典的兩款文件相似性比對(duì)工具，由于文件格式以及目標(biāo)平臺(tái)的不匹配，無(wú)法使用PEdiff進(jìn)行匹配，因此，本文主要采用Bindiff進(jìn)行匹配。比對(duì)文件與4.1節(jié)相同，結(jié)果如圖1。

圖1 Bindiff4.2比對(duì)耗時(shí)23 222 s

采用本文方法主要提取節(jié)點(diǎn)層次信息、節(jié)點(diǎn)價(jià)值信息，最后完成匹配，如圖2～4。其中層次信息提取耗時(shí)7 860 s，節(jié)點(diǎn)價(jià)值信息提取耗時(shí)266 s，匹配耗時(shí)568 s。

圖2 層次信息提取

圖3 價(jià)值信息提取

圖4 匹配耗時(shí)

通過(guò)比對(duì)Bindiff4.2的匹配結(jié)果與本文方法匹配結(jié)果，如圖5，發(fā)現(xiàn)本文方法可以避免因函數(shù)結(jié)構(gòu)相似導(dǎo)致的錯(cuò)誤匹配。

圖5 BinDiff4.2匹配函數(shù)0x8002652c結(jié)果

0x8002652c和0x80e6cc0c是BinDiff4.2匹配的兩個(gè)函數(shù)，如圖6、圖7，相似度0.76，可信度0.78。兩者結(jié)構(gòu)一致，但是只通過(guò)特征字符串即可判別兩個(gè)函數(shù)實(shí)際并不一致。利用本文的方法，可以得出函數(shù)0x8002652c所匹配的函數(shù)為0x80d0ae04，如圖8。雖然函數(shù)結(jié)構(gòu)具有較大差異，但函數(shù)語(yǔ)義一致。

圖6 函數(shù)0x8002652c

圖7 函數(shù)0x80e6cc0c

圖8 函數(shù)0x80d0ae04

根據(jù)上個(gè)函數(shù)在BinDiff中的相似度可信度排序可以確定，約有13 000個(gè)函數(shù)節(jié)點(diǎn)可信度低于此。在衡量本文方法不匹配點(diǎn)和Bindiff4.2結(jié)果不匹配點(diǎn)的過(guò)程中，如果以可信度低于0.78作為不匹配點(diǎn)不夠客觀。故Bindiff不匹配節(jié)點(diǎn)數(shù)量的衡量，取其衡量結(jié)果中相似度低于0.5的節(jié)點(diǎn)數(shù)量。

對(duì)于匹配率采用匹配節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)總數(shù)較小值的比值作為結(jié)果。不匹配率采用不匹配節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)總數(shù)較小值的比值作為結(jié)果。通過(guò)比對(duì)發(fā)現(xiàn)，Bindiff4.2中除了相似度匹配和不匹配節(jié)點(diǎn)，還有一部分節(jié)點(diǎn)被丟棄了，本文方法中也對(duì)不具備調(diào)用關(guān)系的節(jié)點(diǎn)進(jìn)行了丟棄，此類孤立節(jié)點(diǎn)需要另行處理，本次前兩個(gè)實(shí)驗(yàn)中，將被遺棄節(jié)點(diǎn)計(jì)入不匹配點(diǎn)。對(duì)于本文方法的匹配時(shí)間衡量，采用節(jié)點(diǎn)層次計(jì)算時(shí)間、價(jià)值計(jì)算時(shí)間、匹配值時(shí)間之和作為整個(gè)匹配過(guò)程的耗時(shí)。兩種方法的匹配結(jié)果見(jiàn)表1、表2、表3。表1為大規(guī)模程序?qū)嶒?yàn)，表2為小規(guī)模程序?qū)嶒?yàn)，表3為版本大跨度實(shí)驗(yàn)。

表1 Bindiff4.2與本文方法對(duì)Adventerprisek9-Mz 124-2 T與adventerprisek9-mz.123-11.T匹配結(jié)果

表2 Bindiff4.2與本文方法對(duì)ds-121-5與ds-122-5匹配結(jié)果

表3 Bindiff4.2與本文方法對(duì)ik8o3s-122-5與ik9o3s3-123-1a匹配結(jié)果

受程序規(guī)模影響，以往進(jìn)行二進(jìn)制文件比對(duì)特別是補(bǔ)丁比對(duì)的實(shí)驗(yàn)，比對(duì)函數(shù)數(shù)量基本在千級(jí)以內(nèi)，差異并不明顯。實(shí)際，BinDiff在處理程序函數(shù)數(shù)量較高時(shí)，比如，函數(shù)規(guī)模達(dá)到10萬(wàn)級(jí)別，時(shí)間消耗明顯。使用文中方法有效降低了比對(duì)時(shí)間，提高了效率，匹配率也接近Bindiff的匹配率，其中在小版本跨度大規(guī)模程序?qū)嶒?yàn)時(shí)，效果最好。

圖9 ds-121-5、ds-122-5、ik8o3s-122-5、ik9o3s3-123-1a匹配過(guò)程

5 總結(jié)與展望

本文提出的基于節(jié)點(diǎn)層次和節(jié)點(diǎn)價(jià)值的相似性檢測(cè)方法依靠函數(shù)調(diào)用圖進(jìn)行分析，根據(jù)需要分別測(cè)算了節(jié)點(diǎn)在調(diào)用圖中的深度、高度，通過(guò)節(jié)點(diǎn)的父子節(jié)點(diǎn)種類，形成了關(guān)聯(lián)函數(shù)組和近似功能函數(shù)，對(duì)節(jié)點(diǎn)的高度深度測(cè)算進(jìn)行了修正。同時(shí)，針對(duì)節(jié)點(diǎn)在調(diào)用圖中的價(jià)值，通過(guò)直接和間接關(guān)系分別在同層次和全局進(jìn)行了評(píng)估。通過(guò)節(jié)點(diǎn)價(jià)值分析以及節(jié)點(diǎn)層次分析，提高了二進(jìn)制文件函數(shù)匹配的效率。下一步將以此方法為基礎(chǔ)，進(jìn)一步優(yōu)化，嘗試完成對(duì)不同函數(shù)數(shù)量級(jí)的文件進(jìn)行相似性比對(duì)，以期克服函數(shù)層次分析受結(jié)構(gòu)影響的缺點(diǎn)，為在不同級(jí)別程序中尋找?guī)旌瘮?shù)提供支撐。

[1]韓鋒.基于結(jié)構(gòu)化圖形的二進(jìn)制文件比對(duì)技術(shù)研究[D].北京：北京林業(yè)大學(xué)，2013.

[2]Sabin T.Comparing binaries with graph isomorphism[EB/OL].Bindview.[2004].http：//www.bindview.com/Support/RAZOR/Papers.

[3]Flake H.Structural comparison of executable objects[C]//IEEE Conference on Detection of Intrusionsamp;Malwareamp;VulnerablityAssessmentDIMVA 2004，Dortmund，Germany，2004.

[4]Dullien T，Rolles R.Graph-based comparison of executable objects（english version）[J].SSTIC，2005，5：1-3.

[5]曾鳴，趙榮彩，姚京松，等.基于特征提取的二進(jìn)制代碼比較技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（22）：8-11.

[6]謝余強(qiáng)，曾穎，舒輝.改進(jìn)的基于圖的可執(zhí)行文件比較算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（2）：257-260.

[7]魏強(qiáng)，金然，王清賢.基于可信基點(diǎn)的結(jié)構(gòu)化簽名比較算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（24）：5850-5853.

[8]傅建明，喬偉，高德斌.一種基于簽名和屬性的可執(zhí)行文件比較[J].計(jì)算機(jī)研究與發(fā)展，2009，46（11）：1868-1876.

[9]宋楊，張玉清.結(jié)構(gòu)化比對(duì)算法研究及軟件實(shí)現(xiàn)[J].中國(guó)科學(xué)院大學(xué)學(xué)報(bào)，2009，26（4）：549-554.

[10]崔寶江，馬丁，郝永樂(lè)，等.基于基本塊簽名和跳轉(zhuǎn)關(guān)系的二進(jìn)制文件比對(duì)技術(shù)[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（10）：1351-1356.

[11]陳慧，郭濤，崔寶江，等.二進(jìn)制文件相似性檢測(cè)技術(shù)對(duì)比分析[C]//信息安全漏洞分析與風(fēng)險(xiǎn)評(píng)估大會(huì)，2011：79-84.

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

[13]劉春紅，郭濤，崔寶江，等.二進(jìn)制文件同源性檢測(cè)的結(jié)構(gòu)化相似度計(jì)算[J].北京郵電大學(xué)學(xué)報(bào)，2012，35（3）：56-60.

[14]劉星，唐勇.惡意代碼的函數(shù)調(diào)用圖相似性分析[J].計(jì)算機(jī)工程與科學(xué)，2014，36（3）：481-486.

[15]牟永敏，楊志嘉.基于函數(shù)調(diào)用路徑的軟件實(shí)現(xiàn)與設(shè)計(jì)一致性驗(yàn)證[J].中國(guó)科學(xué)：信息科學(xué)，2014，44（10）：1290-1304.

[16]孫賀，吳禮發(fā)，洪征，等.基于函數(shù)調(diào)用圖的二進(jìn)制程序相似性分析[J].計(jì)算機(jī)工程與應(yīng)用，2016，52（21）：126-133.

XIAO Ruiqing1,LIU Shengli1,YAN Meng2,XIAO Da1,SUN Haobin1

1.State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450001,China 2.Xi’an Newspaper Media Group,Xi’an 710002,China

Comparison technology of binary files based on hierarchical nodes.Computer Engineering and Applications,2017,53（21）：144-150.

The existing methods of binary files comparison is mainly achieved by the comparison of structural directed graph,such as BinDiff,it has problems such as mismatch caused by structure similar and high time-consumption of analysis.A matching method based on node hierarchy and node value is proposed to solve this problem.By extracting the hierarchical and value information of the function node which in the function call graph,providing a node level estimation algorithm for nodes which hierarchical information is unclearly,it has matched nodes recursively in the end.Experiments show that this method avoids the mismatch caused by structural similarity,the time consumption is less than 1/2 of the time consumed by the structured matching tool BinDiff,and the reduction of matching nodes’number less than 15%.This method can effectively improve the cross-version similarity analysis efficiency of the embedded device firmware.

binary files comparison;hierarchical analysis;node value analysis;structural graphics

A

TP309

10.3778/j.issn.1002-8331.1612-0044

國(guó)家自然科學(xué)基金（No.61271252）；國(guó)家重點(diǎn)研發(fā)計(jì)劃（No.2016YFB0801505，No.2016YFB0801601）。

肖睿卿（1992—），男，碩士研究生，研究領(lǐng)域?yàn)樾畔踩?，E-mail：Xiao_paper@126.com；劉勝利（1973—），男，博士，教授，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全；顏猛（1973—），男，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全；肖達(dá)（1981—），男，博士，副教授，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全；孫豪彬（1988—），男，碩士研究生，助理工程師，研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)安全。

2016-12-05

2017-01-17

1002-8331（2017）21-0144-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2017-04-14,http://kns.cnki.net/kcms/detail/11.2127.TP.20170414.1850.040.html