基于候選函數組的固件間函數對應關系構建方法

肖睿卿，祝躍飛，劉勝利，蘆斌

基于候選函數組的固件間函數對應關系構建方法

肖睿卿，祝躍飛，劉勝利，蘆斌

（數學工程與先進計算國家重點實驗室，河南 鄭州 450001）

由于固件的特點，傳統二進制比對方法在匹配函數節點傳播匹配的過程中易產生誤匹配。針對匹配函數傳播效果不理想的問題，設計了基于候選函數組的函數對應關系構建方法，并引入了函數層局部網絡匹配的概念。然后，結合3種候選函數組構造策略形成候選函數組構造方法及候選函數組匹配方法，并分析了時間開銷。最后，基于所提方法實現了原型系統，并與Bindiff進行比較。通過隨機抽樣和人工核對，所提方法匹配結果的86.04%與Bindiff匹配結果一致，所提方法匹配結果的11.3%可以修正Bindiff的匹配錯誤，緩解了傳播帶來的誤匹配問題。

固件；二進制比對；函數匹配；候選函數組

1 引言

二進制代碼比對旨在確定兩段代碼（基本塊、函數、程序）是否相似[1]，也稱作二進制比對。文獻[2-5]的工作表明，二進制比對技術具有廣泛的應用場景，可用于固件補丁/漏洞比對[4]、軟件抄襲檢測[6]、惡意軟件檢測[7]等領域。

本文研究鄰近版本固件間構建函數對應關系的方法，對固件安全性進行分析，此問題屬于二進制比對范疇。文獻[1]將二進制比對的粒度分為基本塊、函數、程序三級；輸入形式包括一對一、一對多、多對多；比對形式包括同構、等價、相似3種。依據此條件，本文研究內容可以描述為，對于輸入兩個固件程序，以一定方法判別每個固件中的每一個函數在另一個固件中是否有函數與之對應（也稱為匹配）。對應可以理解為，即使是本身發生了一定幅度修改的補丁函數，通過固件比對方法也可以在鄰近版本的固件之間（補丁前后）判定補丁前后的兩個函數最為相似。

從現有研究工作看，二進制比對大體分為兩個步驟。

1) 函數對相似性計算。通過各類特征判斷一對函數的相似性。

2) 匹配節點傳播。在各文獻（如文獻[4-11]等）中稱為選擇器、過濾器等，主要目的是提供待計算相似性的函數對。通過不同的方法（如基于固定點傳播算法）選擇一組可能匹配的函數對，而后計算相似性。目的是避免全局范圍內尋找待匹配函數對，借此減少計算量。

多數研究者對于二進制比對的研究聚焦于函數對相似性計算方法，特別是聚焦于函數本身的信息提取以表達函數自身；而對匹配節點的傳播方法關注較少。

近年來二進制比對的研究聚焦于跨指令集比對和深度學習，并未聚焦于匹配節點傳播問題。文獻[3]采用部分統計特征和結構特征表示控制流圖（CFG，control flow graph）中的基本塊。通過譜聚類形成質心和碼本。利用質心計算編輯距離，以代表該函數CFG。文獻[4]沿用上述特征但不再使用碼本表示CFG。在使用特定維度向量的基礎上，將CFG周邊具有調用關系的圖的向量以一定權重整合入自身，通過神經網絡，訓練出合適的權重。其特征整合了函數所在局部子圖的特征，可以更好地用以區分函數。文獻[5]利用中間語言模擬執行函數，提取函數中分支指令的值及系統調用相關信息，以代表函數語義。然后，利用最大公共子序列進行匹配。文獻[8]利用中間語言對基本塊的輸入輸出對進行捕獲，判別函數語義是否一致。文獻[9]使用函數調用數、邏輯指令等數字特征以及結構特征，結合機器學習的KNN算法，降低匹配時間代價，完成匹配。

以結構化比對為代表的早期研究提出傳播算法嘗試解決函數對應關系構建問題，但其測試用例程序規模較小，相關實驗無法暴露其在固件比對上的缺陷。文獻[10]首次將CFG用于二進制比對，之后基于該方法出現了二進制比對工具Bindiff。文獻[11]在此基礎上，引入了屬性的概念，并且提出了基于固定點和傳播的方法進行匹配。文獻[12]對指令歸一化處理后進行指令排序，以此解決匹配過程中發現指令順序變化的問題。文獻[13]提取了匯編指令的操作碼以及數據常量，該文僅提取CFG中大小為的圖或圖的子圖，減少了提取量。文獻[14]使用Bindiff完成初步匹配，對未匹配函數節點使用圖編輯距離（GED）和Hungarian算法進行匹配。

由于固件相較于普通應用程序函數數量較大，特別是網絡設備固件，以Bindiff為代表的傳統二進制比對方法直接應用于固件易出現預期外的誤匹配。其原因主要是傳播算法對匹配準確性有較高的依賴，函數匹配算法帶來的錯誤被傳播算法放大。另外，固件函數數量大，往往存在一個函數與多個函數相似接近，如果基于匹配節點傳播的過程選擇待比較函數對較少，則可能導致遺失真正匹配的函數節點；如果選擇過多的待比較函數對，則會導致時間開銷較大和誤匹配。

為解決上述問題，本文設計了基于候選函數組的函數間對應關系構建方法以提高函數匹配準確率，本文工作如下。

1) 設計了基于候選函數組的函數間對應關系構建方法，補充了適用于固件比對場景的函數匹配的定義。

2) 提出候選函數組構造方法。該方法結合了基于統計特征、調用關系和函數地址分布的候選函數組構造策略。此外，分析了候選函數組構造帶來的時間開銷。

3) 提出基于候選函數組的節點匹配方法。使用低時間開銷的指令統計特征提高函數對匹配的效率，利用局部網絡特征提高節點對匹配準確率，并提供候選函數組節點匹配結果篩選策略。

4) 使用本文方法形成原型系統，對樣本固件進行二進制比對。分析了各個候選函數組構造策略對匹配工作產生的影響，并與Bindiff5[23]的匹配結果進行比對。

2 模型建立

2.1 相關概念

在固件升級的場景下，由于固件函數數量過大，基于上述概念構建函數對應關系會產生問題。例如，圖1(a)指令序列與圖1(b)完全一致（Bindiff認為這對函數匹配），但實際圖1(a)應與結構不同的圖1(c)匹配。

此例反映了兩個問題：一是基于函數本身進行匹配分析有局限性；二是函數指令序列相同（基于指令提取的特征值必相同），并不代表函數匹配。推廣而之，即使兩個函數本身相似性最高甚至語義等價，也不能表示這對函數有對應關系，即匹配。

因此，需要補充限定條件，現引入相關概念如下。

圖1 兩版本固件的3個函數控制流圖

Figure 1 Three CFG of two firmwares with different version

函數匹配并不僅僅有層局部網絡匹配。但層局部網絡匹配，是現行條件下可以給出嚴格定義的一種情況。

2.2 匹配流程

本文采用二進制文件匹配流程如圖2所示，算法表示如算法1。

首先，從待比較的二進制文件中挑選函數節點構造候選函數集合，如果兩個候選函數集合具有相似性，則生成候選函數組；然后，進行候選函數組匹配操作，主要針對候選函數組內的函數進行相似性分析，并從中篩選出函數匹配結果。重復上述過程，直到沒有新的匹配結果產生。

算法1 二進制文件比對算法

輸入 二進制文件,的函數調用圖G,G；已匹配節點集合oldmatchset

輸出 匹配節點集合matchset

過程1 二進制文件比對流程

1) matchset =old_matchset

2) DO{

3) (Ca,Ca)get_ca (matchset,G,G)

4) //獲取候選函數組

5) new_matchset=math_ca(Ca,Ca)

6) //獲取新匹配結果集合

7) FOREACH node_pair in new_matchset DO

8) matchsetappend(node_pair)

9) END

10) }WHILE nematchset is empty

11) END//無新增匹配節點出現則結束比對

12) RETURN matchset

候選函數組構造：目的是從大量函數中選擇部分具有關聯性的函數用于后續分析，避免全局性的比對，借此減少工作量。此階段工作側重于研究匹配節點傳播方法，即利用已有的匹配結果，挑選候選函數集合。

圖2 二進制文件匹配流程

Figure 2 Binary file matching process

候選函數組匹配：通過對候選函數組所有的函數對進行相似性分析，計算相似度，而后，根據相似度篩選出函數匹配的結果。其中，使用層局部網絡匹配的概念輔助函數匹配工作，并研究匹配結果篩選策略，用以挑選最優匹配結果。

3 候選函數組構造方法

候選函數組構造的目的是利用已有匹配結果，確定下一步匹配工作范圍。由于候選函數組是由候選函數集合構成的二元組，對兩個待比較文件采用相同的候選函數集合構造方法即可。如果兩個候選函數集合具備一定的相似性（如集合內函數數量、函數平均長度近似），即可形成候選函數組。本節重點是從候選函數集合構建的角度進行說明，對于集合相似性不再贅述。

3.1 候選函數組構造流程

單輪次的候選函數組構建流程如圖3所示，使用符號如前文所述。其中，G,G表示二進制文件的FCG圖，SM表示匹配節點集合，SLM表示上一輪匹配的匹配節點集合，Fg表示策略選擇標識（Fg不為負），Cagp表示構造的候選函數組集合。

圖3 單輪次的候選函數組構建流程

Figure 3 Single round of candidate function group construction process

3.2 基于統計特征構建候選函數組

候選函數組的構造基于已函數匹配節點。若沒有函數匹配節點，應當使用基于統計特征構建候選函數組的策略，篩選特征特征值相同或相似的節點以構建候選函數組。

本文選擇的特征為函數長度、基本塊數、子節點數、被調用次數，并依照上述次序對函數進行排序，選取特征值相同的函數構建候選函數組。以上統計特征，特征值越大，同一文件內出現函數具有相似特征的可能性越小。

統計特征本身不像其他兩種方法具備傳播能力，即從已匹配節點關聯其他節點能力，因此不依賴已匹配節點也可工作。統計特征是對函數部分語義信息的提取，相較于全函數匹配，運算量更小、篩選速度快。在篩選過程中，應當盡量避免同文件內特征相同的函數加入候選組，這會對后續分析帶來干擾。

當基于調用關系和地址分布不產生新的匹配節點時，可考慮再次使用基于統計特征來構建候選函數組。但匹配后期的剩余函數以短小函數為主，將存在大量同文件內函數相似的情況，實際效果可能不夠理想。

本文基于統計特征構建候選函數組主要是為了替代人工提供初期的匹配節點，給后續的傳播類算法提供基礎，因此并不追求利用統計特征解決全部匹配問題。使用統計特征篩選初始匹配節點的過程中，候選函數集合包含函數節點的數量以及篩選函數節點的長度下限值是需要討論的。

對基于特征篩選的候選函數集合，其集合內節點數量最大值（后文以表示）的選擇，將影響初始匹配節點的生成量，進而對后續分析的時耗產生影響。實驗表明，基于統計特征策略構建候選函數組，其數量限定為100時實驗效果最好。

對于函數長度下限的設定，則將影響函數匹配的準確率。在代碼中修改同樣數量的寄存器、操作碼，對于長函數而言，修改量所占百分比低于短函數。這意味著同等數量的修改，對長函數而言影響更小。因此本文基于統計特征的匹配過程中，特征值越大越可靠。

此外，實驗使用候選函數長度下限為50條指令。固件函數數量較大，即使構建候選函數組的過程中達到候選函數數量限制，所選函數的長度遠大于長度限制，不影響后續分析，因此本文對候選函數長度不做實驗進行分析。

3.3 基于調用關系構建候選函數組

3.3.1 基于父子節點的構建候選函數組

6) 重復步驟2)~步驟5)，將生成的候選函數組匯總，并輸出。

基于子節點已匹配的候選函數組構建策略與上述流程類似，區別僅在于，候選函數集合是上輪匹配節點的子節點構成的集合。

文獻[11]提出針對已匹配函數節點的子節點進行相似性分析的方法。實際上，這是較為可靠的分析方法，這種傳播方法將節點周邊局部網絡的信息間接融入分析流程；若子函數語義一致，計算子節點相似性的過程中可以不再進行局部網絡的相似性分析。

并沒有文獻提出利用已經匹配函數節點分析其父節點的思路。此法同樣可行，但分析難度較前者略大。因為匹配函數的子節點易做到一一對應，便于候選函數組構造分析。但函數父節點常難以找到對應關系，在構造候選函數組時易包含較多不匹配節點，后續的候選函數組匹配工作負擔相對大。但匹配函數節點的父函數集合，仍是一種降低匹配量的思路，可以用作構造候選函數組。

實驗結果表明，基于已匹配節點的父節點構造候選函數組，最終貢獻的匹配節點量遠大于利用已匹配節點子節點的策略貢獻的匹配節點量。

3.3.2 基于兄弟節點構建候選函數組

算法2 基于兄弟節點構建候選函數的算法

輸出 候選函數組集合newca

2) //提取所有已匹配節點對

3) Son_set = get_son_matched(1,2,G,G)

4) //獲取匹配節點對的已匹配子節點

5) FOREACH (fs1, fs2) in Sonset DO

6) (Ca, Ca) = get_pa(fs1, fs2,G,G)

7) //獲取匹配子節點的父節點集合

8) new_caappend (Ca, Ca>)

9) // 錄入候選函數組集合

10) END

11) Pa_set = get_pa_matched (1,2)

12) //獲取匹配節點對的父節點

13) FOREACH (fp1, fp2) in Pa_set DO

14) (Ca, Ca) = get_son(fp1, fp2,G,G)

15) //獲取匹配父節點的子節點集合

16) new_ca) append (, Ca>)

17) // 錄入候選函數組集合

18) END

19) END

20) RETURN newca

此策略的設計基于如下考慮。理論上，只要反復判別已匹配節點的父子節點集合是否會出現新的匹配點，就可以完成基于調用關系的匹配工作。但實際上，由于匹配工作是基于候選函數集合進行的，如果候選函數集合中存在無法區分的相似節點（同文件內的相似函數），則策略上會放棄匹配這種節點，以避免產生誤匹配或由于相似度過于接近以至無法選擇匹配結果的問題。此時，若后期成功匹配了一個早期被放棄的相似節點，那么同文件內相似節點應當重新嘗試尋找匹配點，因為早期放棄匹配的節點已經成功匹配，不再影響其分析。反復對早期節點進行重復的調用關系分析，就是在處理這類問題。

已匹配節點數量是隨著每一輪分析而遞增的，如果每次產生新增匹配節點時都對前幾輪的匹配節點進行再分析，會帶來大量的時耗。實際上，后期匹配節點對早期不匹配節點的影響，主要發生在兄弟節點上。例如，某個節點的若干父節點相似性較高，被放棄分析；如果后續分析過程中，其中一個被放棄的父節點已經完成匹配，則可以嘗試重新分析這些被放棄的父節點。這樣，不再需要每次對全部的早期匹配節點進行重復分析，只需要根據新增匹配節點查找兄弟節點即可，減少了運算量。

實驗表明，在所有基于調用關系匹配貢獻的匹配節點中，基于兄弟節點的策略貢獻了50%以上的匹配量，充分說明對早期匹配節點進行重匹配的必要，也說明此策略降低時耗的必要。

3.4 基于地址分布構建候選函數組

本節主要介紹基于地址分布的構建候選函數組策略，包括基于連續地址和基于未匹配區間兩個角度。目的是突破基于調用關系構建候選函數組的局限。

3.4.1 基于連續地址構建候選函數組

基于連續地址構建候選函數組的策略，主要篩選與已匹配函數節點在地址上鄰接的函數節點，檢查其是否已經匹配，如未匹配，則加入候選函數組。連續地址可以突破調用關系的傳播壁壘，此策略對于以短小函數為代表的低特征函數具有較好的匹配效果。

基于調用關系構建候選函數組的方法本身屬于傳播算法。實際上，基于已有匹配結果進行擴展分析的方法，應當視為傳播算法，本質上是為了利用已匹配節點篩選候選函數組，縮小后續匹配工作的匹配范圍。理想狀態下的二進制文件，如果其FCG圖以一棵樹的形態存在，使用前文策略即可完成匹配。即任意兩個函數節點之間存在一條路徑可以從一個節點經過若干節點后到達另一個節點。然而，現實中更為可能的情況是，二進制文件的FCG是以森林狀態存在的，此種情況下會出現傳播壁壘，以圖4為例。

這種方法的合理性在于，如果沒有特殊要求，編譯器在編譯過程中會將同一文件內的函數連續編譯，這些函數在物理上連續存在是大概率事件。邏輯上講，程序中某段特定功能相關的代碼一般存在于一段鄰近空間，這也符合局部性原理和開發規律。此外，這種基于連續地址進行分析的策略，也可以看作對最大公共序列問題的延伸。連續匹配的函數越多，連續匹配的指令就越多，匹配結果就更為可靠。

實驗表明，使用本策略后，新增匹配節點占總匹配函數量的38%。

圖4 調用關系隔離的匹配示例

Figure 4 Matching example of call relation isolation

3.4.2 基于未匹配區間構建候選函數組

在匹配分析的后期，整個二進制文件的未匹配函數節點被已匹配節點分割成若干段。此時，從局部性原理考慮，對于兩段連續未匹配函數區間，如果其邊界的匹配節點是互相匹配的，則直接將兩段函數構造成候選函數組，用以后續分析。

此情況產生的原因可能是多樣的。如編譯器在編譯過程中，不同文件在鏈接的過程中可能插入未知數據；文件編譯時，文件內的小函數往往分布在編譯結果的邊緣；將編輯結果鏈接成可執行文件的過程中，排序可能有變化。雖然有局限性，此策略依然可以用作突破調用關系的傳播壁壘。由于傳播過程沒有融入語義信息，一旦產生新的匹配節點，仍優先采用更為可靠的基于調用關系的策略。

圖5 匹配結果示例

Figure 5 Examples of matching results

在實際操作過程中，可以考慮利用函數序列關系、剔除函數特征相似節點、優先分析鄰近已匹配點函數等策略加以優化。

實驗表明，使用基于未匹配區間構建候選函數組策略后，新增匹配節點量占總匹配量的5%。

3.5 時間開銷分析

候選函數組構造過程本身不涉及函數節點的比較，主要是基于已有匹配結果查找具有關聯性的未匹配節點，并匯入候選函數組。在已經構建FCG的條件下，這種查找過程的時間開銷是常量級的。因此，構造過程本身的時耗可以忽略。

但函數節點相似性分析是具有一定時間開銷的，候選函數組的構建結果直接影響每個候選函數組需要進行的節點相似性分析計算次數。因此，本節主要分析候選函數組構造方法對節點匹配過程帶來的影響，進而分析對整個固件匹配分析流程帶來的時耗影響。

3.5.1 等尺寸候選函數集合的時間開銷分析

在假設1的條件下，補充假設2。

除了初始階段，本文候選函數組的構建是需要依賴匹配節點的。因此，每次候選函數組至少應當有一個新匹配節點產生，才能保證生成用于分析的新的候選函數組。

3.5.2 不等尺寸候選函數集合節點的時間開銷分析

在假設1的條件下，補充假設3。

3.5.3 節點相似性重分析對時間開銷的影響

除上述因素外，需要對節點重分析帶來的時耗進行討論。部分早期不匹配節點，隨著匹配過程的推進，可以完成匹配。因此，重新構建候選函數組進行分析，以圖6為例。

圖6 重匹配示例

Figure 6 Rematch example

公共節點匯總工作主要受兩個因素影響：首先是單輪匹配節點數量帶來的影響，匹配節點數量越多，關聯到的節點越多，排序時耗越大；其次，匹配輪次的影響，匹配輪次越多，排序查找次數越多，時耗越大。

4 候選函數組匹配分析方法

圖7 節點匹配流程

Figure 7 Node matching process

其主要思路如下。

3) 最優匹配結果篩選。根據所有節點對的相似度計算結果，首先基于函數層局部網絡匹配的概念完成部分函數節點匹配工作。然后，對于多函數對相似度接近等不同情況，從候選函數集合的角度，挑選出整個集合的最優匹配結果的組合。

4.1 節點相似度計算方法

對于一對函數節點相似度的計算應當包含兩部分，函數自身特征的相似性和函數所在局部網絡的相似性。因此，節點相似性計算如式（6）所示。

4.1.1 基于函數自身特征的相似度計算方法

基于函數自身特征的相似性分析，本文直接使用函數中匯編指令序列進行比對。如果函數指令序列相同，則視為函數自身特征相同。理論上，依靠LCS算法，可以直接計算兩個函數之間指令序列的最大公共子序列，以此來完成相似度計算。在實際處理上略有差異。

4.1.2 基于局部網絡特征的相似度計算方法

4.2 匹配節點篩選策略

匹配節點篩選工作主要是利用前文計算出各個節點對相似度，在候選函數組內挑選出匹配節點，形成匹配節點集合。其中，要解決單個函數與多個函數相似度較高等問題。

4.2.1 無序列關系的候選函數組匹配方法

構建候選函數組時，候選函數集合內的函數節點并沒有直接順序關系。在完成各個節點相似度計算后，匹配篩選流程如下。

3) 多相似節點匹配結果篩選。在完成前兩步工作后，剩余的相似度大于0的節點多數含有多個匹配節點。參考解決皇后問題的思想，解決剩余子節點匹配問題。

4.2.2 有序候選函數組匹配方法

候選組生成過程中，候選組內函數會存在具有序列關系的情況，如連續地址區間、連續調用序列等。有序候選組相較于無序候選組實際上僅多了一個可以用于輔助分析的有序條件。在此，不再敘述候選結果篩選流程，僅討論如何在無序篩選的基礎上加以改進。

一個較為簡單的方法是將LCS算法融入篩選過程。由于LCS中各個節點僅存在匹配與不匹配情況，而函數比對的相似性是一段連續的區間，相似度有高低區分。需要對算法進行調整，其流程如下。

2) 利用LCS算法計算匹配結果。

3) 將步驟結果與4.2.1節結果進行比對，修正步驟2)的誤匹配，以此避免由于LCS算法導致的連續誤匹配問題。

5 實驗與分析

5.1 實驗環境

本文實驗環境為Win10 x64操作系統，IntelXeonGold6150CPU@2.70 GHz處理器，128 GB內存，SamsungT5SSD2TB硬盤。使用軟件IDApro[14]進行輔助分析。實現語言是python2.7x64。實驗基于收集的Cisco[22]C2600 系列（約660個）和C800系列固件進行，收集方法如文獻[24]。從C2600系列固件中挑選兩組固件，每組隨機抽取10個，標號分別是A1-A10和B1-B10，兩組之間的固件兩兩比對以進行相似性分析，共計100對比對樣例；從C800系列固件中選擇4個版本號、編譯次數、功能號相近的固件，標號是C1-C4。所挑選的固件列表如表1所示。

C組固件的函數數量波動小于10%，主要用于參考和跨系列比對驗證；而A、B兩組固件的函數數量波動達到了90%，且選擇的固件源自不同的功能號，足以驗證本文方法在多種場景下的分析效果。

5.2 預處理

固件比對分析前，需要對固件進行解析。主要依靠IDApro進行反匯編，并提取函數比對需要的基本信息。本文對收集的600余個固件進行了預處理，包括為Bindiff比對提前生成Binexport文件，共時耗23 h。

5.3 參數選擇

因此，兩個參數聯合進行實驗，共計進行20組實驗，每組都使用文件A1-A10和B1-B10進行兩兩比對，即每組100對比對樣例。每組比對后，累加所有匹配節點數量和時耗秒數，形成表2。

表1 待比較文件列表

5.4 候選函數組構造策略匹配效果

基于上述結果可以確定，調用關系貢獻了最多的節點匹配數量，約占匹配總量的60%；基于連續地址的策略是單位時間內貢獻匹配量最多的策略，影響了匹配總量的38%。相當于提升了前者效果的50%；基于未匹配區間的匹配策略同樣發揮了自身的價值。

需要說明的是，由于實際程序所限，基于連續地址與基于調用關系策略是混用的。因此在統計過程中，部分結果重復統計在表中，與上文中總的匹配數量有出入。但通過差值計算不難得出，純粹依靠連續地址匹配的函數節點仍然有782 709個，相當于36%的貢獻量。

在時耗問題上，受程序提供API影響，程序時耗的精度是1 s，因此帶來誤差。結合連續地址和調用關系混用導致的時耗重計算，其數據的總和是高于第5.3節的。但從單位時間匹配節點量的角度看，即使是混合的數據，也可以證明連續地址策略的效率是絕對高于調用關系策略的。

對于調用關系內的3種不同策略，其統計結果如表4所示。

基于兄弟節點策略本質上是基于父子節點關系，從匹配數量上可以看出，基于父子關系匹配的節點總數是基于調用關系匹配的總數。但父子關系的總時耗上少于基于調用關系的時耗，因為基于兄弟節點本身有篩選兄弟節點的流程，以降低無效重匹配的時耗。這部分時耗差正是兄弟節點策略獨有的時耗。兄弟節點策略貢獻了半數以上的匹配量。

從單位時間匹配量而言，基于已匹配父節點的策略效率更高，但是基于已匹配子節點的策略可以匹配更多的節點。從失敗消耗上講，后者更高。

5.5 與Bindiff比較實驗

本節介紹本文方法匹配結果與Bindiff5匹配結果的差異，并使用A、B兩組樣本進行比對實驗后，完成采樣分析。Bindiff5是2019年3月最新更新的工具，且其算法[14]主要依賴已匹配父節點的調用關系，具有比較價值。實驗表明，本文方法匹配的結果與Bindiff有差異，各個策略帶來的差異量如表5所示。

表2 單位時間節點匹配量（匹配個數/s）

注：每一單元格表示，在相應參數下，比對100對樣例后，匹配量、時間開銷的總和，單位是個數和秒。

表3 各策略匹配函數效果

注：輪次表示候選函數組匹配的次數，失敗表示一輪匹配未產生新的匹配節點。

實驗結果表明以下結論。

1) 基于連續地址和基于未匹配區間兩種非調用關系的策略提供了較高的差異量。差異函數的平均長度小于30，而兩種基于地址分布的策略提供的差異函數，其平均長度普遍小于其他方法，說明基于地址分布策略影響的匹配結果對小函數更有效。

2) 基于調用關系和統計特征的策略與Bindiff5的分析結果相比有97%以上的相似度，說明兩者實驗效果接近。

3) 基于地址分布策略累積貢獻的差異量占所有策略匹配總量13.18%，是很可觀的差異量。這些差異量是直接基于該方法產生的差異量，如果分析這些差異匹配節點影響到的匹配節點，可能會在調用關系的匹配結果中找到。由此說明，基于地址分布的策略對差異匹配的影響可能高于預期，而基于調用關系貢獻的差異可能低于預期。

針對差異匹配結果，需要人工核實Bindiff5與本文方法差異的函數匹配結果哪個正確。由于差異量較大，采用抽樣分析的方法，將A1-A10和B1-B10產生的100對測試樣例，針對不同的候選函數組構造策略抽取500個差異匹配結果，共2 215個（基于統計特征僅有215個差異結果，無法抽取更多），對結果進行人工核對，時耗10天，核對結果如表6所示。通過人工核對，差異結果中本文方法至少有70%的正確率，本文方法匹配結果的11.8%可以修正Bindiff的錯誤。需要說明的是，本文測試用例中確實存在人工無法判別是否匹配的情況，這主要發生在小函數中，對于以往的研究，研究者往往忽略了這些數據。

5.6 跨系列比較

本節使用A、C兩組樣本進行比對實驗，通過分析本文方法比對結果和Bindiff比對結果的差異結果可知，本文方法各匹配策略的準確率。

本實驗采用抽樣分析的方法，將A1-A10和C1-C4產生的40對測試樣例針對不同的候選函數組構造策略抽取100個差異匹配結果，共計466個（基于統計特征僅有77個差異結果，基于未匹配區間僅有89個結果），對結果進行人工核對，結果如表7所示。

實驗結果表明，在跨系列固件比對條件下，本文方法依然可以對Bindiff比對結果的錯誤進行修正，且準確率在60%以上。

表4 調用關系策略匹配函數效果

表5 各策略匹配結果與Bindiff5的差異量

注：差異匹配數量，本文匹配結果與Bindiff5不同的函數數量。

表6 同系列固件比對各策略匹配差異結果抽測情況

表7 跨系列固件比對各策略匹配差異結果抽測情況

實際上，跨系列的固件本身僅有部分功能模塊相似，固件間的相似函數數量較少。使用A、B兩組樣本進行同系列不同功能和版本的固件間比對，足以證明本文方法在不同相似程度固件間的效果，A、C組的跨系列比對實驗，主要作用是更直觀地證明本文方法在低相似度固件間比對的效果。

6 相關工作

除引言提到的研究外，二進制比對領域也有其他分支，但與本文目標關聯較低。文獻[15]提取了函數調用圖（FCG，function call graph），引入圖編輯距離的概念進行相似性比對。文獻[16]針對FCG使用SDMFG來計算圖的相似性距離，該法主要通過測量匹配過程中，最小匹配成本的路徑，形成最優匹配路徑，以此計算相似性。文獻[17]針對已有簽名方法易被小變化欺騙、無法形成匹配的情況，使用調用圖，規避這類問題，并使用模擬退火算法來近似調用圖編輯距離。文獻[18]基于子圖匹配的層次分析方法，在剔除確定匹配節點后形成待檢測的相似子圖，利用函數調用序列，進行相似序列比對，以此形成新的相似節點匹配。文獻[19]主要比對源碼中的補丁。文獻[20]通過提取Tracelet（一段短而連續的執行路徑）完成比對。文獻[21]先將二進制文件基本塊進行符號簡化，以此抵抗語法變化。而后，針對符號簡化形成樹形圖，使用基于樹編輯距離等的匹配方法，進行相似性計算。

7 結束語

[1] A survey of binary code similarity[R]. 2019.

[2] GAO J, YANG X, FU Y, et al. VulSeeker: a semantic learning based vulnerability seeker for cross-platform binary[C]//Conference on Automated Software Engineering(ASE 2018). 2018.

[3] FENG Q, ZHOU R, XU C, et al. Scalable graph-based bug search for firmware images[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 480-491.

[4] XU X, LIU C, FENG Q, et al. Neural network-based graph embedding for cross-platform binary code similarity detection[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017: 363-376.

[5] HU Y, ZHANG Y, LI J, et al. Cross-architecture binary semantics understanding via similar code comparison[C]//2016 IEEE 23rd International Conference on Software Analysis, Evolution, and Reengineering (SANER). 2016: 57-67.

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

LIU C H, GUO T, CUI B J, et al. Similarity computation for executable objects homology detection based on structural signature [J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(3): 56-60.

[7] CESARE S, XIANG Y. Classification of malware using structured control flow[C]//Proceedings of the Eighth Australasian Symposium on Parallel and Distributed Computing-Volume 107. 2010: 61-70.

[8] PEWNY J, GARMANY B, GAWLIK R, et al. Cross-architecture bug search in binary executables[C]//2015 IEEE Symposium on Security and Privacy. 2015: 709-724.

[9] ESCHWEILER S, YAKDAN K, GERHARDS-PADILLA E. DiscovRE: efficient cross-architecture identification of bugs in binary code[C]//NDSS. 2016.

[10] Flake H. Structural comparison of executable objects[C]//Proc of the International GI Workshop on Detection of Intrusions and Malware & Vulnerability Assessment. 2004: 161-174.

[11] DULLIEN T, ROLLES R. Graph-based comparison of executable objects[J]. SSTIC, 2005, 5(1): 3.

[12] 王建新, 楊凡, 韓鋒. 二進制文件比對中的指令歸并優化算法[J].計算機應用與軟件, 2013, 30(12): 40-42+126.

WANG J X, YANG F, HAN F. Instruction merging optimization algorithm in binary files comparison[J]. Computer Applications and Software,2013,30(12):40-42+126.

[13] KHOO W M, MYCROFT A, ANDERSON R. Rendezvous: a search engine for binary code[C]//Proceedings of the 10th Working Conference on Mining Software Repositories. 2013: 329-338.

[14] BOURQUIN M, KING A, ROBBINS E. Binslayer: accurate comparison of binary executables[C]//Proceedings of the 2nd ACM SIGPLAN Program Protection and Reverse Engineering Workshop. 2013: 4.

[15] HU X, CHIUEH T, SHIN K G. Large-scale malware indexing using function-call graphs[C]//Proceedings of the 16th ACM Conference on Computer and Communications Security. 2009: 611-620.

[16] 劉星, 唐勇. 惡意代碼的函數調用圖相似性分析[J]. 計算機工程與科學, 2014, 36(3): 481-486.

LIU X, TANG Y. Similarity analysis of malware's function-call graphs[J]. Computer Engineering & Science, 2014, 36(3):481-486.

[17] KOSTAKIS O, KINABLE J, MAHMOUDI H, et al. Improved call graph comparison using simulated annealing[C]//Proceedings of the 2011 ACM Symposium on Applied Computing. 2011: 1516-1523.

[18] 孫賀, 吳禮發, 洪征, 等. 基于函數調用圖的二進制程序相似性分析[J]. 計算機工程與應用, 2016, 52(21): 126-133.

SUN H, WU L F, HONG Z, et al. Research on function call graph based method for similarity analysis of binary files[J]. Computer Engineering and Applications, 2016, 52(21): 126-133.

[19] JANG J, AGRAWAL A, BRUMLEY D. ReDeBug: finding unpatched code clones in entire OS distributions[C]//2012 IEEE Symposium on Security and Privacy. 2012: 48-62.

[20] DAVID Y, YAHAV E. Tracelet-based code search in executables[J]. ACM Sigplan Notices, 2014, 49(6): 349-360.

[21] PEWNY J, SCHUSTER F, BERNHARD L, et al. Leveraging semantic signatures for bug search in binary programs[C]//Proceedings of the 30th Annual Computer Security Applications Conference. 2014: 406-415.

[22] Cisco 2600 Series Multiservice Platforms - Retirement Notification[EB].

[23] Bindiff5[EB]. 2019.

[24] COSTIN A, ZADDACH J, FRANCILLON A, et al. A large-scale analysis of the security of embedded firmwares[C]//23rd {USENIX} Security Symposium ({USENIX} Security 14). 2014: 95-110.

[25] 肖睿卿, 劉勝利, 顏猛, 等. 節點層次化的二進制文件比對技術[J]. 計算機工程與應用, 2017, 53(21): 144-150.

XIAO R Q, LIU S L, YAN M, et al. Comparison technology of binary files based on hierarchical nodes[J]. Computer Engineering and Applications, 2017, 53(21): 144-150.

Method for constructing function correspondence between firmware based on candidate function group

XIAO Ruiqing, ZHU Yuefei, LIU Shengli, LU Bin

State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China

Due to the characteristics of firmware, traditional binary comparison methods are prone to mismatches during the propagation of the matching function.Aiming at the problem that the matching function propagation algorithm is not ideal, a method for constructing function correspondence based on candidate function groups was designed, and the concept of function matching inlayer local network is supplemented.Then, three candidate function group construction strategies and candidate function group matching methods are proposed, and the time overhead were analyzed. Finally, a prototype system was implemented based on the method and compared with Bindiff. Through random sampling and manual check, 86.04% of the matching results of the proposed method are consistent with Bindiff matching results, while 11.3% can correct Bindiff matching errors.

firmware, binary comparison, function matching, candidate function group

TP393

A

10.11959/j.issn.2096?109x.2021018

2020?02?20；

2020?06?21

劉勝利，dr_liushengli@ 163.com

科技委基礎加強項目（2019-JCJQ-ZD-113）；國家重點研發計劃（2019QY1300, 2016YFB0801505）

Science and Technology Commission Foundation Enhancement Project (2019-JCJQ-ZD-113), The National Key R&D Program of China (2019QY1300, 2016YFB0801505)

肖睿卿, 祝躍飛, 劉勝利. 等. 基于候選函數組的固件間函數對應關系構建方法[J]. 網絡與信息安全學報, 2021, 7(2): 110-125.

XIAO R Q, ZHU Y F, LIU S L, et al. Method for constructing function correspondence between firmware based on candidate function group[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 110-125.

肖睿卿（1992?），男，黑龍江牡丹江人，數學工程與先進計算國家重點實驗室博士生，主要研究方向為二進制分析。

祝躍飛（1962?），男，浙江蘭溪人，數學工程與先進計算國家重點實驗室教授、博士生導師，主要研究方向為安全協議和密碼學。

劉勝利（1973?），男，河南周口人，數學工程與先進計算國家重點實驗室教授、博士生導師，主要研究方向為網絡設備安全和網絡攻擊檢測。

蘆斌（1982-），男，山西靈石人，數學工程與先進計算國家重點實驗室副教授，主要研究方向為信息安全、機器學習。