Xgadget：基于動靜結合的二進制Gadget搜索

呂建強，付 才，何 帥，江 帥，李 明，韓蘭勝

1.華中科技大學網絡空間安全學院，武漢 430074

2.分布式系統安全湖北省重點實驗室，武漢 430074

代碼復用亦稱代碼重用[1]，它是對目標代碼中現有的代碼片段進行重復利用的技術。復用者利用現有代碼片段運行過程中可執行權限，將可復用的代碼片段（稱為Gadget）組織起來，形成非程序原邏輯的代碼語義[2]，繞開WX（write or execute）[3]、DEP（data execute prevention）[4]、ASLR（address space layout randomization）[5]和CFI（control flow integrity）[6-8]等防御機制，實施有效攻擊。不知攻，焉知防。代碼復用攻擊的研究，最終目的是更好地防御。通過逆向代碼復用研究，可以形成更有針對性的防御體系，如針對以ROP（return-oriented programming）為代表的控制流劫持攻擊的防御技術CFI。代碼復用亦可以用在具有積極的應用場景，如Ma等人[9]利用ROP技術實現軟件版權保護，開啟了ROP技術正向利用的先河。因此，代碼復用的研究在攻、防和正向利用等方面，都有重要研究價值。復用Gadget搜索是代碼復用研究的基石，尤其是二進制指令的搜索，對提高代碼復用效率和自動化水平起到了關鍵作用。

Gadget 搜索與代碼復用原理緊密相連。最早是由Solar Designer 提出的return-into-libc（ret2libc）開始，Ret2libc主要思想是通過改變return地址，將控制流轉移到庫函數，對庫函數進行整體復用。該類復用Gadget為ret 指令，其搜索核心思路是搜索程序所有ret 指令。Shacham等人[3]在2007年提出了ROP概念，它的主要思想將以ret 指令結尾，在它之前字節包含有效指令的一組指令集，這一組指令集稱為ROP Gadget。其中有效指令常見類型有保存棧數據到寄存器的指令、系統調用指令和影響棧幀的指令等。2011 年Bletsch 等人[10]提出了JOP（jump-oriented programming）技術，它主要思想是使用以間接call和jmp指令結束的代碼來實現代碼復用。因此，JOP Gadget特征是以call或jmp指令為結尾，在它之前字節包含有效指令的一組指令集，其中有效指令特征與ROP相同。

以上復用工作可以歸屬于基于控制流的代碼復用技術[11-16]，隨著CFI廣泛部署在Chrome、Windows10操作系統和Edge 中，基于控制流的代碼復用技術利用空間越來越小[17-18]，研究者逐漸轉向面向數據的非控制流代碼復用的研究[19-20]。2016年Hu等人[19]提出了DOP（dataoriented programming），該方法僅改變目標程序非控制數據值，在不改變控制流的前提下，實現了DOP代碼復用攻擊。其Gadget特征偏向功能語義的描述，主要是由基本的加載指令、算術指令、解引用指令和存儲指令組合起來的指令集合。文獻[19]設計并實現了DOP Gadget靜態搜索算法DOPModule，但該算法是基于LLVM IR（intermediate representation）實現的，不支持二進制搜索，也不支持動態鏈接庫。2018年Ispoglou等人[20]提出了BOP（block-oriented programming），該方法實現了在理想的CFI策略下遵循目標程序執行控制流，自動化地發現某復用語義對應的程序執行路徑。BOP 中基本塊就是目標程序靜態CFG（control flow graph）中的基本塊（廣義的BOP Gadget），可以直接使用任意的CFG 提取算法即可完成搜索，不需要單獨設計。但它引入了候選塊的概念，每一個候選塊是CFG 中能夠完成SPL payload（SPloit language payload）[20]中具體某一條語句功能的基本塊映射。SPL payload 是BOP 作者提出的一種高級語言，它能夠描述任意復用語義。因此，BOP Gadget 搜索過程本質上就是找所有能夠完成復用語義對應的CFG 基本塊，它需要跟具體的復用語義聯動實現，沒有通用特征定義標準，難以設計通用搜索算法，不方便單獨從Gadget 搜索角度研究。因此，本文只討論ROP、JOP和DOP三類Gadget搜索。

目前，主流的ROP/JOP Gadget 搜索方法是基于capstone 的純靜態反匯編和搜索，不能搜索動態鏈接庫中Gadget，減少了復用組織環節Gadget 選擇范圍，可能錯過最佳復用路徑，復用效果與質量有所下降。如果需要使用到動態鏈接庫中的Gadget時，復用者還需對某動態鏈接庫單獨進行Gadget搜索與分析，從而增加了分析和利用時間，降低了復用效率。ROP/JOP Gadget 搜索工具使用較多的是ROPgadget和Ropper。DOP類Gadget搜索工具主要是DOPModule[19]，它是基于LLVM IR文件，輸出為IR（intermediate representation）層面的Gadget，不便于后續的自動化復用，以上三種主流的Gadget搜索算法都基于靜態的搜索策略，存在如下問題：

問題1支持的Gadget 類型不多，不能同時支持ROP、JOP和DOP類型Gadget的搜索。

問題2純靜態面的搜索，搜索過程不能同時搜索目標程序依賴的動態鏈接庫，存在漏掉可用的Gadget。

為了解決以上問題，本文提出一種“動靜結合”的二進制Gadget搜索算法，算法分動態反匯編和靜態搜索兩個環節，分別設計了基于IMG（image）插樁的動態反匯編算法和基于指令級DFA（deterministic finite automaton）的靜態搜索算法，并在實戰案例中開展了有效性評估實驗。本文的主要貢獻有：

（1）給出了DOP 類型二進制Gadget 特征定義，為DOP 類型Gadget 在二進制層面的搜索提供判別標準，解決問題1中支持DOP類型Gadget的搜索。

（2）設計Token級和指令級DFA，并實現了“動靜結合”的二進制Gadget 搜索算法，并開發了二進制Gadget搜索工具Xgadget，解決問題2。

（3）在五款應用程序中開展搜索實驗，與DOPModule、ROPgadget 搜索工具做了對比分析，并對Xgadget 搜索時間性能和有效性進行了評估。無論是搜索數量還是單位指令搜索性能上都有更好的表現，搜索出來的Gadget也是有效的。

1 動靜結合的二進制Gadget搜索算法

代碼復用的基礎是Gadget搜索，Gadget搜索又依賴具體Gadget 類型的特征定義。針對現有靜態搜索算法支持的Gadget類型不多，不能同時搜索依賴的動態鏈接庫問題，提出了基于動靜結合的二進制Gadget 搜索算法，命名為Xgadget。該算法的“動”體現在載體程序運行狀態時實現反匯編；“靜”體現在反匯編指令上進行基于DFA靜態搜索，因此，整個過程包括動態反匯編和靜態搜索兩個階段。動態反匯編解決了依賴的動態鏈接庫的反匯編問題；靜態搜索解決了目標程序內最大范圍的Gadget搜索。該算法包括三個子算法，分別是動態反匯編（算法1）、ROP/JOP類型Gadget搜索（算法2）、DOP類型Gadget 搜索（算法3）。其中算法1 由C++語言實現，算法2、算法3由Python實現。

本章分別從動靜結合搜索算法框架設計、DOP類型Gadget特征定義、動態反匯編算法以及基于指令級有窮自動機的靜態搜索四個方面做介紹。

1.1 搜索框架

圖1展示了動靜結合Gadget搜索算法整體框架，主要包含兩個階段。第一個階段是動態反匯編：輸入是某應用程序的二進制文件，輸出反匯編指令；第二階段是對反匯編指令進行靜態搜索，輸入是第一階段生成的反匯編指令，輸出是Gadget集合。

圖1 動靜結合Gadgets搜索框架Fig.1 Framework of combination of dynamic and static

動態反匯編思路：通過動態IMG級插樁，在程序運行時，獲取目標程序所有函數列表，包括動態鏈接庫中的函數，然后對函數內每條指令進行反匯編，最終得到反匯編指令。

靜態搜索思路：通過對反匯編指令逐一判定，ROP類型Gadget 判定標準是：查看ret 之前有沒有操作寄存器、系統調用和影響棧幀的指令；JOP 類型判定標準是查看call 或者jmp 之前有沒有操作寄存器、系統調用和影響棧幀的指令；DOP類型判定標準詳見1.2節DOP類型Gadget 特征定義。判定步驟，首先定位邊界指令，ROP Gadget 的邊界指令是ret；JOP Gadget 的邊界指令是call 或者jmp；DOP Gadget 的邊界指令是存儲類指令，如，mov地址、寄存器等；接著指令回溯，在回溯的同時根據不同Gadget類型的指令特征進行判定，符合要求的指令加入到Gadget隊列中，最后輸出。

1.2 DOP類型Gadget特征定義

本文提出的Gadget 搜索算法同時支持ROP、JOP、DOP類型的二進制指令的搜索，算法是基于不同Gadget類型特征規則的搜索策略。ROP 和JOP 類型的特征規則參考文獻[14]，DOP類型特征是基于加載、存儲、操作和跳轉四種元操作的基礎上組成的算術、賦值和解引用三種基本復用功能語義特征，其詳細特征定義如下。

（1）算術操作：以加法運算為例，實現一個典型的加法運算，需要兩個加載元操作，一個加法運算元操作和一個存儲元操作。二進制指令特征定義如下：

以下是Openssl案例中算術操作Gadget的實例：

（2）賦值操作：實現典型賦值功能，需要一個加載元操作，一個存儲元操作。二進制指令特征定義如下：

mov 寄存器1，地址1

mov 地址2，寄存器1

以下是Openssl中賦值操作Gadget的實例：

（3）解引用操作：實現典型解引用操作，需要兩個加載元操作，一個存儲元操作，二進制指令特征定義如下：

說明：①[寄存器1]表示，把寄存器1中的值作為地址，取該地址的值。②地址1 可以與地址2 相同，亦可以不同。

以下是Openssl中解引用操作Gadget的實例：

以上只列出了典型的算術、賦值和解引用操作形式化定義，實際程序中存在一些變異的情況，以加法為例說明，如下某匯編代碼：

以上匯編代碼實現了加1的加法操作，也可以定義為加法Gadget。如果該Gadget 存在于可控的循環體內部，則可以實現任意的加法復用語義。

1.3 基于IMG插樁的動態反匯編

傳統的動態Gadget搜索算法通常是指令級插樁，它過于依賴程序運行時的輸入，不同的輸入會執行不同路徑上的指令，沒有執行到的指令，無法動態搜索。靜態搜索算法能夠很好地解決此問題，但是靜態算法不能同時反匯編依賴的動態鏈接庫，因此動態鏈接庫中的Gadget無法有效利用。

本文提出的基于IMG 插樁的動態反匯編算法，其創新之處在于，在程序動態運行狀態下，及時獲取got節中外部函數的地址，能對依賴的動態鏈接庫指令有效處理。具體實現過程如算法1所示，算法的輸入是可執行程序，輸出是目標程序及其依賴的所有動態鏈接庫的反匯編指令集合。算法通過設計一個IMG插樁的回調函數實現動態反匯編任務。當程序運行時，對每一個IMG都調用回調函數，首先判斷IMG 是否有效，如果無效，則直接返回；如果有效則遍歷IMG中的所有節，再遍歷節內所有函數及其函數內所有指令，對指令進行反匯編，將反匯編指令添加到集合OutFile中輸出，步驟如下。

算法1基于IMG插樁的動態反匯編算法。

輸入：可執行程序。

輸出：反匯編指令集合。

步驟1創建OutFile集合，并清空。

步驟2判斷IMG是否有效，如果有效，繼續執行步驟3～6，如果無效，程序結束。

步驟3遍歷IMG中所有節、函數和指令。

步驟4獲取指令地址，并反匯編當前指令。

步驟5將地址和反匯編指令合并添加OutFile。

步驟6是否符合停止條件，符合則退出，輸出Out-File，否則繼續執行步驟3～步驟6。

1.4 基于指令級有窮自動機的靜態搜索

靜態搜索算法分兩步：第一步，通過指令級DFA對反匯編文件進行邊界指令全文匹配，獲取邊界指令的索引號集合；第二步，循環回溯，每次從邊界指令處開始指令級回溯，根據不同類型Gadget特征規則對指令進行判定，得到不同類型的Gadget。判定規則，ROP 和JOP 類型的Gadget搜索規則是根據文獻[14]的指令特征判定，DOP 類型的Gadget 判定規則是根據本文1.2 節DOP 類型Gadget特征定義。算法流程圖如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flow diagram

1.4.1 指令級DFA設計

本文搜索算法可以同時實現對程序依賴的動態鏈接庫進行Gadget搜索，處理的反匯編指令數量通常比僅包含主程序指令多，算法設計須考慮搜索效率。DFA技術在大文件中快速搜索具有較好的優勢，本文以DOP類型指令級DFA設計為例，其指令特征根據1.2節相關定義。

指令由操作符、操作數兩部分組成。操作數又包括立即操作數、寄存器操作數和存儲器操作數等，雖涉及種類較多，但其DFA 設計思想是一致的。因此本文只選擇mov類操作符作為Token級代表，存儲指令作為指令級代表闡述其DFA設計過程。

標準DFA 通常是一個五元組，例如有限自動機T=(Q,Σ,δ,q0,F)，其中Q代表有窮狀態集，Σ代表有窮輸入符號集或字母表，δ代表Q×Σ→Q的狀態轉移函數，q0∈Q代表初始狀態，F?Q代表終結狀態集或接收狀態集。

（1）mov類操作符DFA設計

x86 匯編指令中mov 類常見操作符包括：mov、movsx、movzx、movl、movzbl。其DFA 中五個元素的值分別如下所示：

上述狀態轉移函數δ對應狀態轉移圖如圖3 所示。根據DFA 轉化成對應的正則表達式為"mov[zs]*[bx]*l*"。

圖3 mov類操作數DFA狀態轉移Fig.3 DFA state transfer diagram for mov class operands

按照mov 類操作符DFA 設計方法，可以設計其他常見操作符DFA，同時可以轉化為對應的正則表達式，詳見表1所示。

表1 x86常見操作符正則表達式Table 1 Regular expressions for common operators in x86 architecture

（2）存儲指令DFA設計

x86匯編指令中存儲指令主要包括全局存儲指令和局部存儲指令兩種形式。其主要區別是全局存儲指令的操作數一是全局地址，局部存儲指令的操作數一是寄存器或者寄存器加減一個偏移量。存儲指令本質上是多種不同的Token 級DFA 的一種組合，其可以通過Token DFA做相應的連接運算得到。

設Tmov為mov類操作符DFA，Timd是立即數DFA，Treg為寄存器DFA，那么存儲指令DFA 如下公式所示，公式（1）為全局存儲指令DFAIgStore，公式（2）為局部存儲指令DFAIlStore。

按照存儲指令DFA 設計方法，可以設計其他常見指令的DFA公式，詳見表2所示。

表2 x86常見指令級DFA公式Table 2 DFA formulas for common instructions in x86 architecture

1.4.2 ROP/JOP類型搜索算法

ROP 類型Gadget 靜態搜索算法創新之處是基于DFA 的設計，能夠在大文件中快速獲取邊界指令集合，同時在某區間內快速判定是否包含改變控制流指令，有效提升搜索性能。算法步驟見算法2，其中IDEX[]用來存儲匹配邊界指令的索引號，start_index和end_index分別代表開始索引號和結束索引號，deep代表搜索深度，gadgets是存儲ROP/JOP Gadget集合。

算法具體實現過程：首先獲取ret、jmp或call等邊界指令索引集合IDEX[]，然后循環從IDEX[]中取邊界指令索引，作為結束索引值賦值給end_index，通過公式end_index-deep得到開始索引值賦值給start_index，接著將[start_index：end_index]區間內不存在改變控制流且符合定義的指令序列加入到gadgets并輸出，步驟如算法2所示。

算法2 ROP/JOP類型Gadget靜態搜索算法。

輸入：二進制反匯編指令。

輸出：Gadgets集合。

步驟1創建索引集合IDEX[]，設置搜索深度deep。

步驟2基于DFA定位邊界指令集合IDEX[]。

步驟3在IDEX[]取邊界指令索引給end_index。

步驟4根據步驟1 中deep，通過end_index-deep公式，得到開始索引值賦值給start_index。

步驟5判斷索引區間[start_index：end_index]中是否包含改變控制流指令，如果存在，執行步驟3，獲取下一個邊界指令索引；如果不存在，執行步驟6。

步驟6判斷是否符合ROP/JOP 類Gadget 定義，如果符合，執行步驟7；否則執行步驟3。

步驟7將步驟5 索引區間的地址和指令加入到gadgets中。

步驟8是否符合停止條件，符合則退出，輸出gadgets，否則繼續執行步驟3～步驟8。

需要說明的是步驟5需要對[start_index：end_index]索引區間中指令進行分析，判斷其中是否包含操作符是jmp、call、jz、jnz、jl、jmp、jb等改變控制流的指令，如果存在，則該區間的指令不能構成一組完整的ROP類Gadget，開啟下一輪循環；否則，按照定義判定是否可以成為一組Gadget。

1.4.3 DOP類型Gadget搜索算法

算法3是DOP類型Gadget靜態搜索算法，其創新之處體現在兩方面。一方面，基于DFA的高效匹配，提高了較為復雜、多樣的DOP類Gadget判定速度和準度，且容易擴展；方面，從每一個邊界指令，獨立地開始回溯和判定，有利于并行搜索實現。此處的邊界指令為存儲指令。

算法步驟詳見算法3 所示。首先創建算術集合ArithmeticQueue，賦值集合AssignmentQueue，解引用集合DerefQueune，分別存放算術、賦值和解引用Gadget；然后基于DFA技術，快速獲取inputFile中全部存儲指令索引號，存儲在IDEX[]集合中；接著循環從IDEX[]取出存儲指令，獨立地從該處開始回溯，依據1.4.1節相關正則表達式進行匹配和判定，添加到相應的Gadget 集合中，直至IDEX[]中存儲指令全部取完，算法結束，最后從三個集合中輸出結果。算法輸入為inputFile，是算法1反匯編指令集合，輸出為DOP類Gadget集合，算法中所有指令類型的判定都是基于1.4.1 小節設計的DFA 確定。算法3具體步驟如下。

算法3DOP類型Gadget靜態搜索算法。

輸入：目標程序反匯編指令inputFile。

輸出：Gadgets集合。

步驟1創建ArithmeticQueue，AssignmentQueue，DerefQueun集合，并初始化為空。

步驟2設置DOP Gadget 邊界指令正則表達式，獲取邊界指令集合IDEX[]。

步驟3在IDEX[]取邊界指令索引，獲取邊界指令。

步驟4從邊界指令處，回溯指令。

步驟5依據1.4.1 小節相關DFA 設計，判定Gadget類型，如果是算術Gadget，將其添加到ArithmeticQueue集合中，如果是賦值Gadget，將其添加到AssignmentQueue集合中，如果是解引用Gadget，將其添加到DerefQueun集合中。

步驟6是否符合停止條件，是否符合停止條件，符合則退出，輸出Gadgets，否則繼續執行步驟3～步驟6。

目前主流的ROP 類Gadget 搜索算法ROPgadget 和Ropper只對少量的結束操作符進行匹配，因此采用直接匹配的方式。DOP 類搜索算法DOPModule 在IR 層通過store和load關鍵字進行匹配。本文搜索算法針對缺失關鍵字信息的匯編指令，實現更加復雜的DOP 類Gadget 搜索任務，針對性地設計了Token 級和指令級DFA，快速定位邊界指令，并行回溯判定，算法具備如下特性和優勢：

（1）設計了Token 級操作符和操作數的DFA，由此構建了指令級的DFA，利用DFA 實現全文范圍的快速匹配與定位，在保證了其搜索性能優勢的同時，還具備良好的可擴展性能。如需將算法拓展到X64，或ARM、MIPS 等不同架構指令集中，只需要修改或少量增加對應的Token級和指令級的正則表達式。

（2）算法采用先定位邊界指令索引，再從每個索引處獨立地開始回溯和判定，在判定過程中不受連續出現多個邊界指令的影響，且方便將判定算法封裝成獨立的方法，有利于工程應用層面實現并行搜索，加快搜索效率。

2 實驗結果與評估

為了驗證本文提出Xgadget 的有效性，本章首先與現在主流的Gadget搜索工具支持的Gadget類型做了對比分析，然后將本文設計的算法在五個應用程序中開展實驗，結果表明本文提出的搜索算法有著明顯的優勢，如：支持的Gadget 類型更多，數量比ROPgadget 提高了12.5 倍，且能同時對載體程序依賴的動態鏈接庫進行Gadget 搜索，單位指令搜索時間開銷降低了31.2%，最后在兩個案例中對搜索算法做了有效性評估。

實驗環境：虛擬機軟件VMware Workstation 16.2.1 pro，內存1 GB，操作系統是Ubuntu32 位，內核版本是12.04，編譯器版本為gcc 4.6.3，插樁框架版本為InterPin 3.21。

2.1 支持的Gadget類型

目前代碼復用的Gadget 類型主要包括ROP、JOP、DOP 三大類。Gadget 搜索工具主要有DOPModule、ROPgadget、Ropper和本文設計的Xgadget。

從表3 可以看出，ROPgadget 和Ropper 兩款工具僅支持ROP 和JOP 類型Gadget 搜索；DOPModule 僅支持DOP Gadget搜索，而Xgadget可以同時支持三類Gadget搜索。從是否支持二進制層面的搜索來看，DOPModule不支持，它僅支持LLVM IR層的搜索，ROPgadget、Ropper和Xgadget 都支持二進制。搜索結果為二進制指令，對復用后續自動化工作起到關鍵基礎作用。

表3 主流代碼復用Gadget搜索工具支持類型對比Table 3 Support type in common code reuse Gadget search

2.2 搜索Gadget數量

在Gadget 搜索數量方面，Xgadget 分別做了DOP、ROP、JOP三大類的Gadget搜索實驗，均在Ngnix、sudo、ProFTPD、sshd和OpenSSL五款應用程序中進行。針對DOP類Gadget搜索數量如表4所示。

表4 Xgadget DOP類Gadgets搜索數量Table 4 Xgadget method search quantity for DOP Gadgets

之所以選擇以上五款應用程序作為測試對象，原因是Hu等人在文獻[19]中首次提出DOP類Gadget搜索算法，它也有對這五款應用程序做搜索實驗。單從搜索數量上看，Xgadget有很大的優勢，但是兩者不是在同一個層級上搜索，數量角度沒有可比性，因此在這里，沒有跟它做對比。

搜索實驗的另一方面，本文選擇ROPgadget 作為ROP/JOP 類Gadget搜索工具代表，與Xgadget工具在不同類型的Gadget搜索數量上做對比實驗，分別在Nginx等五款應用程序中實驗，結果如表5所示。

表5 Xgadget與ROPgadget搜索數量對比Table 5 Comparison of search quantity between Xgadget and ROPgadget

不選擇Ropper工具做對比實驗的原因是ROPgadget和Ropper 支持Gadget 搜索類型相同，但是ROPgadget較Ropper 更受歡迎。從表5 可以看出Xgadget 在ROP/JOP 類Gadget 搜索數量具有明顯的優勢，平均是ROPgadget 工具的12.5 倍，表5 第4 列沒有數據，原因是ROPgadget不支持DOP Gadget搜索。Gadget搜索數量對比圖如圖4所示。

圖4 ROP類Gadgets搜索數量對比Fig.4 Comparison of ROP-Type Gadgets search quantity

從圖4可以看出Xgadget在搜索數量上與ROPgadget有較大的優勢，其主要原因是Xgadget 同時把依賴的動態鏈接庫中的Gadget搜索出來了，ROPgadget不能同時做到。Xgadget在動態鏈接庫搜索效果請參閱2.3節。

2.3 動態鏈接庫Gadget搜索效果

為了評估Xgadget 在動態鏈接庫中Gadget 搜索效果，Xgadget 針對Ngnix 等五款應用程序的動態鏈接庫進行實驗，表6展示Xgadget在Ngnix等五款應用程序進行Gadget 搜索的時候處理到的動態鏈接庫數量及其具體的鏈接庫名字信息。表7展示了Xgadget在相應動態鏈接庫上進行DOP類型Gadget搜索數量。

表7 Xgadget在動態鏈接庫中搜索DOP gadget數量Table 7 Experimental results for Xgadget in DOP gadget search for dynamic link libraries

由表6和表7可以看出，Xgadget是可以同時處理動態鏈接庫的Gadget搜索，這樣可以同時對程序依賴動態鏈接庫的Gadget做一個整體的了解，有利于探索動態鏈接庫中Gadget復用。

2.4 時間性能評估

為了評估Xgadget 時間性能，首先對ROPgadget、DOPModule，以及Xgadget 算法進行時間復雜度的對比分析，然后與ROPgadget 開展對比實驗。沒有與DOPModule開展對比實驗的原因是兩者不在同一個層級上搜索，沒有可比性。

對ROPgadget7.1 版本進行分析，首先循環對ret、call或jmp等結束操作符通過二進制硬編碼方式直接匹配與定位，然后獲取結束指令的地址列表，接著遍歷所有的地址列表，根據設定的深度回溯，循環反匯編指定地址區間指令并輸出。設結束操作符數量為m，結束指令地址數量為n，回溯深度為k，則ROPgadget 算法時間復雜度為Ο(mnk)。

文獻[19]中DOPModule 算法則是先獲取IR 文件中所有函數列表，然后遍歷每個函數的CFG，接著從存儲指令開始回溯，直至遇到加載指令，視為一個完整的DOP類Gadget。設函數數量為m，基本塊數量為n，回溯深度為k，則DOPModule算法時間復雜度為Ο(mnk)。

Xgadget 搜索算法先通過DFA 實現全文范圍的快速匹配，獲取所有存儲指令位置，然后從每個存儲位置開始獨立地開始回溯，直到滿足完成的Gadget 特征輸出。設存儲指令數量為n，回溯深度為k，則Xgadget算法時間復雜度為Ο(nk)。

ROPgadget、DOPModule 與Xgadget 三款算法最好情況是m=1,k=1 ，此時三款算法時間復雜度都是Ο(n) ，但最壞情況是m=n,k=n，此時ROPgadget 和DOPModule 時間復雜度為Ο(n3)，Xgadget 時間復雜度為Ο(n2)，性能提高了一個數量級。Xgadget可以通過多線程并行搜索，時間復雜度可以進一步降到Ο(n)。時間復雜度對比如表8所示。

表8 時間復雜度對比Table 8 Time-complexity comparison

時間開銷實驗：選擇sudo1.8.16 和openssl1.0.2g 兩個應用程序，在ubuntu16，32位環境下進行ROP類Gadget搜索時間開銷的實驗，并與ROPgadget 工具進行對比，對比結果如表9所示。

表9 Xgadget與ROPgadget搜索時間性能對比Table 9 Comparison of time cost for case searching amongs Xgadget and ROPgadget

表9中t1列代表動態反匯編時間，t2列代表靜態搜索時間，t3列代表Xgadget搜索總的時間，num列代表搜索出來的指令數量，tˉ列代表單指令搜索時間，tˉ=num/總時間，t4列代表ROPgadgets搜索時間。

Xgadget總時間開銷包括動態反匯編和靜態搜索兩個環節時間開銷的和。ROPgadgets 不能同時對動態鏈接庫進行搜索，它的時間只包含主程序的搜索開銷，然而Xgadget搜索時間卻包含了對動態鏈接庫進行了搜索的開銷。為了更合理地比較，對兩款搜索工具在單位指令搜索時間開銷上做了比較。兩款工具在單位指令搜索時間開銷對比圖如圖5所示。圖5可以看出，Xgadget在單位指令搜索時間上比ROPgadget降低了32.1%。

圖5 單位指令搜索時間開銷對比Fig.5 Comparison of time cost for single instruction searching amongs Xgadget and ROPgadget

2.5 Xgadget有效性評估

2.5.1 DOP類Gadget搜索評估

本文選擇在Proftpd中對DOP類Gadget搜索有效性進行評估。Proftpd是一款流行的FTP服務程序，其私鑰是保證其安全性的重要數據信息，因此Proftpd設計者，將私鑰存儲的地址采取隨機化的方式處理，根據對Proftpd私鑰地址隨機化策略的深入分析，其隨機化過程最初由全局變量ssl_ctx 指針指向SSL_CTX 結構體，SSL_CTX結構體的成員指針cert指向的cert_st結構體，再由cert_st結構體的成員指針key指向CERT_PKEY結構體，依次類推，通過7次指針指向，最終由BIGNUM結構體成員指針d指向私鑰的真實地址，整個過程需要利用到解引用Gadget和加法Gadget來實現。解引用Gadget用來實現結構體間指針的解引用，加法Gadget用來獲取結構體內特定成員變量的指針值。

解引用Gadget 存在于棧溢出漏洞函數sreplace 中。圖6 為sreplace 函數中存在漏洞函數sstrncpy 上下文部分CFG 圖。每個節點是一個基本塊，邊是基本塊之間的跳轉關系；（b）圖是（a）圖5 號節點部分匯編代碼，其代碼段0x0805F7FD 處調用了_strncmp 函數對s1 和s2的前n個字符串進行對比，如果條件成立則跳轉6 號節點，6 號節點部分匯編代碼見（c）圖，（c）圖中0x0805F84B處調用sstrncpy漏洞函數，該函數是將源地址src 內容，拷貝n個字節長度的字符串到dest 地址中。根據（c）圖可知src 的值等于rptr 內存單元的值，dest 的值等于cp 單元的值。rptr 和cp 內存單元的值可以通過用戶輸入超長字符串覆蓋來修改。具體rptr 內存值通過解引用Gadget 獲取私鑰真實地址，解引用Gadget具體形式如下：

圖6 sreplace函數CFG（漏洞函數上下文部分）Fig.6 Snippet of CFG for sreplace function

經過對Proftpd 密鑰泄露過程調試跟蹤，其過程使用的加法Gadget 是存在xfer_log_retr 函數中，具體加法Gadget形式如下：

通過Xgadget對應用程序Proftpd進行Gadget搜索，上述Gadget均已被搜索出來。

2.5.2 ROP類Gadget搜索評估

本小節是為了驗證Xgadget 工具關于ROP 類的Gadget 搜索的有效性評估。選用了某CTF 比賽的網上練習題。首先對可執行程序進行IDA反編譯，其漏洞函數反編譯代碼如下所示：

上述反編譯代碼可知buf數組是由16單位大小，但是read 的大小卻是0x100，存在棧溢出漏洞。但是程序中不存在system，也不存在/bin/sh 之類的字符串，要想成功拿到shell，思路是先泄露libc的地址，然后利用libc中的system和/bin/sh。泄露地址可以使用程序中的puts函數把地址輸出來。首先需要找pop_rdi的ROP Gadget，通過Xgadget 工具進行ROP Gadget 搜索，共搜索出來25 個匹配項，根據經驗，分別在main 函數中和libc 中確定兩個ROP Gadgets，如表10所示。

表10 確定復用ROP GadgetsTable 10 Reuse ROP Gadgets in experiment

其次，利用泄露puts的got表的地址，計算出libc的基地址；接著將該基地址加上表10 中右列Gadget 的偏移量地址，然后通過該Gadget 將bin/sh 字符串傳參給system函數，最終實現拿到shell的目的。最終實現效果如圖7所示。

圖7 獲得shell效果圖Fig.7 Effective of vulnerable program for create shell process

該題成功獲取shell 過程中，既用到了主程序中的Gadget，又用到了動態鏈接庫libc 中的Gadget。以上兩個案例可以表明Xgadget 可以支持ROP 類和DOP 類gadget搜索，同時可以自動化地處理目標程序的動態鏈接庫Gadget的搜索。

2.5.3 討論

Xgadget 目前可以同時支持ROP、JOP 和DOP 三類的Gadget的搜索，但存在一個基本前提，動態反匯編需要目標程序的DEBUG 版本。Xgadget 暫不支持BOP Gadget，原因是廣義BOP Gadget 就是CFG 中每一個基本塊，可以直接使用任意的CFG 提取算法即可完成搜索，不需要單獨設計；而狹義BOP Gadget需要結合具體的復用語義，不方便單獨設計。

Xgadget 搜索算法，也可以理解為一種動靜結合的二進制Gadget搜索框架，它有很好的可擴展性，如果添加對新類型Gadget 搜索的支持，只需要增加支持新的Gadget 類型搜索代碼，然后加入到框架代碼中即可。Xgadget 源代碼已在gitee 上公開，網址為https：//gitee.com/cse-sss/non-control-flow-n。

Gadget 搜索存在高可用性與高覆蓋率兩者兼顧難的問題。實戰過程中，復用需求千變萬化，如果追求Gadget高可用性搜索，很有可能會漏掉許多潛在可用的Gadget。因此，通常Gadget 搜索需要偏向高覆蓋率，然后結合其他的手段進一步驗證其可用性，本文提出Xgadget也是遵循高覆蓋率的搜索原則。

3 結束語

本文首先定義了二進制的代碼復用基本語義特征，且在此基礎上設計了基于動靜結合的Gadget 搜索算法。該算法的“動”體現在載體程序運行狀態的同時實現依賴的動態鏈接庫的反匯編；“靜”體現在反匯編指令上進行基于指令級DFA 的靜態搜索。本文設計了Token 級和指令級的DFA，實現了基于動靜結合算法思想的Xgadget 搜索工具，并在實際應用程序中開展搜索實驗，與ROPgadget 和DOPModule 搜索工具做了對比，Xgadget在搜索數量是ROPgadget12.5倍，單位指令搜索時間較之降低了32.1%，且同時支持主流的ROP、JOP和DOP三類二進制Gadget的搜索，支持類型更加豐富，能夠實現載體程序依賴的動態鏈接庫的Gadget搜索，有效提高代碼復用效率。該算法其本質上也是一種二進制Gadgets 搜索框架，它可以靈活拓展。下一步將拓展到ARM、MIPS 等架構指令集的搜索，同時探索在此基礎上實現語義導向的定向Gadget 搜索及自動化篩選與組織，進一步提高代碼復用自動化水平，進而推動代碼復用領域的研究進展。