節(jié)點層次化的二進制文件比對技術(shù)

肖睿卿，劉勝利，顏 猛，肖 達，孫豪彬

1.數(shù)學(xué)工程與先進計算國家重點實驗室，鄭州 450001 2.西安報業(yè)傳媒集團，西安 710002

節(jié)點層次化的二進制文件比對技術(shù)

肖睿卿1，劉勝利1，顏 猛2，肖 達1，孫豪彬1

1.數(shù)學(xué)工程與先進計算國家重點實驗室，鄭州 450001 2.西安報業(yè)傳媒集團，西安 710002

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

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

1 引言

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

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

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

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

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

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

2 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（2）為每個函數(shù)單獨分配一個獨立的序號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é)點層次的分析方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

同時，對于計算節(jié)點深度的公式進行修改，如公式（8）。

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

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

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

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

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

節(jié)點間接價值Iv計算流程：

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

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

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

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

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

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

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

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

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

在此，對函數(shù)節(jié)點定義進行補充。

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

3.4.1 初始匹配點與擴展匹配算法

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

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

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

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

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

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

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

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

3.4.3 二進制文件相似性度量流程

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

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

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

（4）完成二進制程序節(jié)點價值分析。

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

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

4 實驗結(jié)果分析

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

4.1 驗證性實驗結(jié)果分析

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

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

4.2 對比實驗結(jié)果分析

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

圖1 Bindiff4.2比對耗時23 222 s

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

圖2 層次信息提取

圖3 價值信息提取

圖4 匹配耗時

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

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

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

圖6 函數(shù)0x8002652c

圖7 函數(shù)0x80e6cc0c

圖8 函數(shù)0x80d0ae04

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

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

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

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

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

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

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

5 總結(jié)與展望

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

[1]韓鋒.基于結(jié)構(gòu)化圖形的二進制文件比對技術(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]曾鳴，趙榮彩，姚京松，等.基于特征提取的二進制代碼比較技術(shù)[J].計算機工程與應(yīng)用，2006，42（22）：8-11.

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

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

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

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

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

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

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

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

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

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

[16]孫賀，吳禮發(fā)，洪征，等.基于函數(shù)調(diào)用圖的二進制程序相似性分析[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

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

肖睿卿（1992—），男，碩士研究生，研究領(lǐng)域為信息安全，E-mail：Xiao_paper@126.com；劉勝利（1973—），男，博士，教授，研究領(lǐng)域為網(wǎng)絡(luò)安全；顏猛（1973—），男，研究領(lǐng)域為網(wǎng)絡(luò)安全；肖達（1981—），男，博士，副教授，研究領(lǐng)域為網(wǎng)絡(luò)安全；孫豪彬（1988—），男，碩士研究生，助理工程師，研究領(lǐng)域為網(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