節點層次化的二進制文件比對技術

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

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

節點層次化的二進制文件比對技術

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

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

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

二進制文件比對；層次分析；節點價值；結構化圖形

1 引言

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

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

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

（2）編譯器的不同會導致函數節點的結構形成上產生一定的出入，即使語義相同，因為優化等因素的影響，也可能產生不同結構的編譯結果。

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

針對現有方法的不足與實際問題的需求，本文在函數調用圖基礎上，提出基于節點價值與層次的刻畫方法，進行二進制文件相似性分析。

2 相關概念

定義1（函數調用圖）函數調用圖（Function Call Gragh，FCG），由 G=(VG,EG)構成的有向圖表示。其中，VG表示節點集，每個節點對應一個函數VG={fi|1≤i≤n,i∈Z}，其中Z為整數集，n為函數個數；EG為邊集，表示函數調用關系的全集，EG?VG×VG，由序偶組成，函數fi調用了若邊集EG存在元素則說明函數 fi調用了函數 fj。

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

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

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

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

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

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

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

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

3 基于節點層次與節點價值的匹配方法

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

基于節點層次與節點價值的匹配方法減少了對輸入信息的依賴，主要利用函數在函數調用圖中結構化的屬性。

3.1 函數調用圖提取

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

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

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

3.2 基于節點層次的分析方法

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

3.2.1 非循環調用節點深度計算

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

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

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

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

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

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

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

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

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

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

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

3.2.2 循環調用節點深度計算

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

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

由于當前是在計算函數的深度調用圖，因此基點選取考慮以下條件：

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

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

（3）節點的出度較大。

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

（5）在實際比對過程中，如果程序規模較大，可能出現從多個節點中篩選基點的情況。

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

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

此后采用前文無循環調用節點的節點深度計算算法，繼續完善深度矩陣，如果深度矩陣仍有節點深度未知，則說明仍有循環路徑存在，繼續確定循環路徑基點，重復上述步驟，直至完成深度矩陣。

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

3.3 基于節點價值的分析方法

通過節點的出入度，可以基本地反應節點的被調用和調用子節點情況。但是，節點在程序中的重要性并不能得以直觀體現。補充定義如下。

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

節點間接價值Iv計算流程：

（1）將 fi所有父節點與 fi節點歸并為一個新節點fi'，并將其父節點所有數據計入新節點 fi'。構建新的函數調用矩陣Matrix( )G1存儲信息。

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

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

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

節點間接價值Iv能夠反應節點服務的父子節點在整個調用圖中的價值。即使存在兩個節點價值相近，但是節點服務對象在函數調用網絡的存在價值差異。

針對不同規模的兩個程序，定義7中的父子節點數量會受函數總數量的影響，導致可比性較差。因此，在進行比較的過程中，對節點價值的描述需要進行調整。

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

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

3.4 結合節點層次與節點價值的匹配方法

在此，對函數節點定義進行補充。

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

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

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

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

3.4.2 同程序內函數相似性

節點價值是用以描述函數的重要特征。當同程序內多個函數具備相似的父子節點關系時，不同節點的節點價值趨同和節點層次趨同將對跨程序逐函數匹配產生干擾。通過預處理，可以對此種情況加以利用。

定義9（公共父節點）對于函數調用圖G，滿足公式（11），則稱 fi是 fj和 fk的公共父節點。對于函數調用圖G，滿足公式（12），則稱 fi是 fj和 fk的公共子節點。

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

當兩個函數的子節點具有相似性時，說明兩個函數的功能具有一定相似性。考慮到子函數可能同時服務多個父函數，因此，衡量函數節點公共子節點的相似性，應當結合子函數調用次數。相似度計算公式如公式（13），表示 fj,fk的公共子節點對前者的相似度。

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

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

（1）選擇二進制文件 A,B形成函數調用關系圖（FCG）。

（2）檢測兩個文件中各自父子節點的相似函數，確定關聯函數組集與近似功能函數集。

（3）進行二進制程序層次分析，確定函數高度矩陣和深度矩陣，同時利用近似功能函數集進行層次修正。

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

（5）進行關聯函數組匹配，將兩個二進制文件中的關聯函數組優先測試匹配。

（6）以關聯函數數組匹配點為輸入，從根節點或葉子節點開始，逐層次進行節點匹配，方向為高度遞增或深度遞增，將每一層不匹配節點融入下一層次繼續匹配。

4 實驗結果分析

在Windows平臺上使用Python語言，利用IDApython在IDA pro上進行函數調用關系的抽取。使用C#語言完成后續工作，包括函數調用關系圖構建、節點層次分析、節點價值分析、二進制文件相似性分析。

4.1 驗證性實驗結果分析

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

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

4.2 對比實驗結果分析

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

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

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

圖2 層次信息提取

圖3 價值信息提取

圖4 匹配耗時

通過比對Bindiff4.2的匹配結果與本文方法匹配結果，如圖5，發現本文方法可以避免因函數結構相似導致的錯誤匹配。

圖5 BinDiff4.2匹配函數0x8002652c結果

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

圖6 函數0x8002652c

圖7 函數0x80e6cc0c

圖8 函數0x80d0ae04

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

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

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

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

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

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

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

5 總結與展望

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

[1]韓鋒.基于結構化圖形的二進制文件比對技術研究[D].北京：北京林業大學，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].計算機工程與應用，2006，42（22）：8-11.

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

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

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

[9]宋楊，張玉清.結構化比對算法研究及軟件實現[J].中國科學院大學學報，2009，26（4）：549-554.

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

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

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

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

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

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

[16]孫賀，吳禮發，洪征，等.基于函數調用圖的二進制程序相似性分析[J].計算機工程與應用，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

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

肖睿卿（1992—），男，碩士研究生，研究領域為信息安全，E-mail：Xiao_paper@126.com；劉勝利（1973—），男，博士，教授，研究領域為網絡安全；顏猛（1973—），男，研究領域為網絡安全；肖達（1981—），男，博士，副教授，研究領域為網絡安全；孫豪彬（1988—），男，碩士研究生，助理工程師，研究領域為網絡安全。

2016-12-05

2017-01-17

1002-8331（2017）21-0144-07

CNKI網絡優先出版：2017-04-14,http://kns.cnki.net/kcms/detail/11.2127.TP.20170414.1850.040.html