Xgadget：基于動靜結(jié)合的二進制Gadget搜索

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

1.華中科技大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，武漢 430074

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

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

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

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

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

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

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

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

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

（2）設(shè)計Token級和指令級DFA，并實現(xiàn)了“動靜結(jié)合”的二進制Gadget 搜索算法，并開發(fā)了二進制Gadget搜索工具Xgadget，解決問題2。

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

1 動靜結(jié)合的二進制Gadget搜索算法

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

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

1.1 搜索框架

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

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

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

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

1.2 DOP類型Gadget特征定義

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

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

以下是Openssl案例中算術(shù)操作Gadget的實例：

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

mov 寄存器1，地址1

mov 地址2，寄存器1

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

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

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

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

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

以上匯編代碼實現(xiàn)了加1的加法操作，也可以定義為加法Gadget。如果該Gadget 存在于可控的循環(huán)體內(nèi)部，則可以實現(xiàn)任意的加法復(fù)用語義。

1.3 基于IMG插樁的動態(tài)反匯編

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

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

算法1基于IMG插樁的動態(tài)反匯編算法。

輸入：可執(zhí)行程序。

輸出：反匯編指令集合。

步驟1創(chuàng)建OutFile集合，并清空。

步驟2判斷IMG是否有效，如果有效，繼續(xù)執(zhí)行步驟3～6，如果無效，程序結(jié)束。

步驟3遍歷IMG中所有節(jié)、函數(shù)和指令。

步驟4獲取指令地址，并反匯編當(dāng)前指令。

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

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

1.4 基于指令級有窮自動機的靜態(tài)搜索

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

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

1.4.1 指令級DFA設(shè)計

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

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

標(biāo)準(zhǔn)DFA 通常是一個五元組，例如有限自動機T=(Q,Σ,δ,q0,F)，其中Q代表有窮狀態(tài)集，Σ代表有窮輸入符號集或字母表，δ代表Q×Σ→Q的狀態(tài)轉(zhuǎn)移函數(shù)，q0∈Q代表初始狀態(tài)，F(xiàn)?Q代表終結(jié)狀態(tài)集或接收狀態(tài)集。

（1）mov類操作符DFA設(shè)計

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

上述狀態(tài)轉(zhuǎn)移函數(shù)δ對應(yīng)狀態(tài)轉(zhuǎn)移圖如圖3 所示。根據(jù)DFA 轉(zhuǎn)化成對應(yīng)的正則表達式為"mov[zs]*[bx]*l*"。

圖3 mov類操作數(shù)DFA狀態(tài)轉(zhuǎn)移Fig.3 DFA state transfer diagram for mov class operands

按照mov 類操作符DFA 設(shè)計方法，可以設(shè)計其他常見操作符DFA，同時可以轉(zhuǎn)化為對應(yīng)的正則表達式，詳見表1所示。

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

（2）存儲指令DFA設(shè)計

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

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

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

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

1.4.2 ROP/JOP類型搜索算法

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

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

算法2 ROP/JOP類型Gadget靜態(tài)搜索算法。

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

輸出：Gadgets集合。

步驟1創(chuàng)建索引集合IDEX[]，設(shè)置搜索深度deep。

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

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

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

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

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

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

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

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

1.4.3 DOP類型Gadget搜索算法

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

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

算法3DOP類型Gadget靜態(tài)搜索算法。

輸入：目標(biāo)程序反匯編指令inputFile。

輸出：Gadgets集合。

步驟1創(chuàng)建ArithmeticQueue，AssignmentQueue，DerefQueun集合，并初始化為空。

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

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

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

步驟5依據(jù)1.4.1 小節(jié)相關(guān)DFA 設(shè)計，判定Gadget類型，如果是算術(shù)Gadget，將其添加到ArithmeticQueue集合中，如果是賦值Gadget，將其添加到AssignmentQueue集合中，如果是解引用Gadget，將其添加到DerefQueun集合中。

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

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

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

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

2 實驗結(jié)果與評估

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

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

2.1 支持的Gadget類型

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

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

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

2.2 搜索Gadget數(shù)量

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

表4 Xgadget DOP類Gadgets搜索數(shù)量Table 4 Xgadget method search quantity for DOP Gadgets

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

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

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

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

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

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

2.3 動態(tài)鏈接庫Gadget搜索效果

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

表7 Xgadget在動態(tài)鏈接庫中搜索DOP gadget數(shù)量Table 7 Experimental results for Xgadget in DOP gadget search for dynamic link libraries

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

2.4 時間性能評估

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

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

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

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

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

表8 時間復(fù)雜度對比Table 8 Time-complexity comparison

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

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

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

Xgadget總時間開銷包括動態(tài)反匯編和靜態(tài)搜索兩個環(huán)節(jié)時間開銷的和。ROPgadgets 不能同時對動態(tài)鏈接庫進行搜索，它的時間只包含主程序的搜索開銷，然而Xgadget搜索時間卻包含了對動態(tài)鏈接庫進行了搜索的開銷。為了更合理地比較，對兩款搜索工具在單位指令搜索時間開銷上做了比較。兩款工具在單位指令搜索時間開銷對比圖如圖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服務(wù)程序，其私鑰是保證其安全性的重要數(shù)據(jù)信息，因此Proftpd設(shè)計者，將私鑰存儲的地址采取隨機化的方式處理，根據(jù)對Proftpd私鑰地址隨機化策略的深入分析，其隨機化過程最初由全局變量ssl_ctx 指針指向SSL_CTX 結(jié)構(gòu)體，SSL_CTX結(jié)構(gòu)體的成員指針cert指向的cert_st結(jié)構(gòu)體，再由cert_st結(jié)構(gòu)體的成員指針key指向CERT_PKEY結(jié)構(gòu)體，依次類推，通過7次指針指向，最終由BIGNUM結(jié)構(gòu)體成員指針d指向私鑰的真實地址，整個過程需要利用到解引用Gadget和加法Gadget來實現(xiàn)。解引用Gadget用來實現(xiàn)結(jié)構(gòu)體間指針的解引用，加法Gadget用來獲取結(jié)構(gòu)體內(nèi)特定成員變量的指針值。

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

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

經(jīng)過對Proftpd 密鑰泄露過程調(diào)試跟蹤，其過程使用的加法Gadget 是存在xfer_log_retr 函數(shù)中，具體加法Gadget形式如下：

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

2.5.2 ROP類Gadget搜索評估

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

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

表10 確定復(fù)用ROP GadgetsTable 10 Reuse ROP Gadgets in experiment

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

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

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

2.5.3 討論

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

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

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

3 結(jié)束語

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