基于動(dòng)態(tài)符號(hào)執(zhí)行的不透明謂詞反混淆算法

宋雪勦，張 俊，何明星

(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院, 四川 成都 610039)

隨著信息技術(shù)的發(fā)展，惡意軟件和漏洞利用程序等層出不窮，嚴(yán)重危害著人們的隱私和財(cái)產(chǎn)安全。通常這些軟件都會(huì)經(jīng)過(guò)代碼混淆來(lái)延長(zhǎng)生存周期，加大了專業(yè)人員的分析難度。代碼混淆方法主要包括控制流混淆、數(shù)據(jù)混淆、布局混淆和預(yù)防混淆。常見(jiàn)的控制流混淆包括不透明謂詞混淆、控制流平展化以及指令替換等方法。

為對(duì)抗代碼混淆，研究人員提出了很多反混淆的方法。馬洪亮等[1]通過(guò)跟蹤抽象語(yǔ)法樹(shù)上節(jié)點(diǎn)的相關(guān)變量，利用相關(guān)的變量終值進(jìn)行反混淆。郭軍等[2]通過(guò)語(yǔ)義相關(guān)指令識(shí)別對(duì)混淆后程序的指令序列優(yōu)化來(lái)進(jìn)行反混淆。目前針對(duì)不透明謂詞的反混淆方法主要是通過(guò)數(shù)據(jù)流分析對(duì)分支條件的布爾邏輯表達(dá)式進(jìn)行化簡(jiǎn)來(lái)消除不可達(dá)路徑[3]。當(dāng)表達(dá)式依賴較多無(wú)法化簡(jiǎn)時(shí)，這種方法的有效性將大大降低。

針對(duì)以上問(wèn)題，本文提出一種基于動(dòng)態(tài)符號(hào)執(zhí)行的路徑不可達(dá)性分析來(lái)對(duì)不透明謂詞混淆進(jìn)行反混淆的算法。不同于數(shù)據(jù)流的靜態(tài)分析，該算法通過(guò)動(dòng)態(tài)分析的方式執(zhí)行程序，在路徑覆蓋率及適應(yīng)性方面都有明顯的優(yōu)勢(shì)。

不透明謂詞混淆是在原程序中加入了大量的不可達(dá)路徑，因此，可以通過(guò)不可達(dá)路徑分析,消除不可達(dá)路徑從而達(dá)到反混淆的目的。路徑敏感的程序分析是程序分析領(lǐng)域中的一個(gè)重要方法，其中不可達(dá)路徑分析是編譯優(yōu)化等領(lǐng)域的重點(diǎn)研究對(duì)象之一。靜態(tài)程序分析方法可以通過(guò)靜態(tài)符號(hào)執(zhí)行對(duì)路徑約束條件進(jìn)行求解，根據(jù)約束求解器的結(jié)果判斷路徑是否可達(dá)，然而靜態(tài)符號(hào)執(zhí)行分析代碼混淆后的程序會(huì)使所要求解的狀態(tài)空間急劇增加，導(dǎo)致路徑爆炸。為此，本文通過(guò)動(dòng)態(tài)符號(hào)執(zhí)行來(lái)緩解路徑爆炸問(wèn)題。

1 相關(guān)工作

1998年Collberg等[4]首先提出用代碼混淆的方法來(lái)保護(hù)程序的知識(shí)產(chǎn)權(quán)，并指出混淆轉(zhuǎn)換需要依賴于不透明謂詞，同時(shí)介紹了2種不透明謂詞的構(gòu)造方法：并發(fā)性構(gòu)造和別名構(gòu)造。2006年Majumdar等[5]提出通過(guò)加入大量冗余分支及不可達(dá)路徑來(lái)實(shí)現(xiàn)控制流混淆以增加程序復(fù)雜度。2007年袁征等[6]提出利用同余方程構(gòu)造一種混淆Java程序的不透明謂詞簇。2013年蘇慶等[7]提出了En_Logistic映射,該映射是通過(guò)改進(jìn)Logistic混沌映射而來(lái)，將該映射應(yīng)用到不透明謂詞簇的構(gòu)造過(guò)程中形成混沌不透明謂詞，并應(yīng)用于代碼的不透明謂詞混淆。

2008年Balakrishnan等[3]提出通過(guò)數(shù)據(jù)流分析來(lái)消除不可達(dá)路徑，通過(guò)常量傳播和可用表達(dá)式來(lái)判斷指定程序點(diǎn)的表達(dá)式是否為常量或是否可用已計(jì)算出的值替換，以避免表達(dá)式的重復(fù)計(jì)算，對(duì)分支條件的布爾邏輯表達(dá)式進(jìn)行化簡(jiǎn)，來(lái)消除不可達(dá)路徑。這是一種靜態(tài)程序分析方法，當(dāng)表達(dá)式依賴較多無(wú)法化簡(jiǎn)時(shí)，這種方法的有效性將降低。

一方面，代碼混淆使得靜態(tài)程序分析的所要求解的狀態(tài)空間急劇增加，出現(xiàn)路徑爆炸問(wèn)題；另一方面預(yù)防混淆能夠?qū)o態(tài)程序分析中的反匯編算法進(jìn)行攻擊，使得靜態(tài)程序分析出錯(cuò)。可見(jiàn)，混淆程序的不可達(dá)路徑分析僅僅使用靜態(tài)程序分析方法是很難實(shí)現(xiàn)的。本文通過(guò)基于動(dòng)態(tài)符號(hào)執(zhí)行的不可達(dá)路徑分析在一定程度上解決了路徑爆炸及預(yù)防混淆對(duì)靜態(tài)程序分析的影響。

2 背景知識(shí)

2.1 不透明謂詞混淆

不透明謂詞混淆[5]是指將不透明謂詞作為基本塊插入到控制流圖中。不透明謂詞是指在混淆過(guò)程中己經(jīng)確定其輸出，但是通過(guò)靜態(tài)程序分析方法很難計(jì)算在某個(gè)程序點(diǎn)的值的謂詞表達(dá)式。通過(guò)在控制流圖中插入不透明謂詞并將其作為分支條件的一部分，能夠加大控制流混淆的強(qiáng)度，使得靜態(tài)程序分析很難自動(dòng)化地計(jì)算出輸出。Collberg等[4]和袁征等[6]分別在他們的論文中給出了不透明謂詞的定義。

定義1(不透明謂詞[4,6]) 當(dāng)程序中的一個(gè)謂詞O在某個(gè)程序點(diǎn)P上的輸出δ的一些屬性在程序進(jìn)行混淆時(shí)就確定了，則將該謂詞O稱為不透明謂詞。根據(jù)其輸出的不同，有3類不透明謂詞：如果其值始終為true則記為OT；始終為false則記為OF；根據(jù)程序輸入的不同，一部分為true，一部分為false則記為O?，如圖1所示。

圖1 3類不透明謂詞

程序經(jīng)過(guò)圖中的不透明謂詞分支后，始終執(zhí)行true分支的不透明謂詞，如圖中的OT，其中虛線表示永遠(yuǎn)不會(huì)執(zhí)行該路徑，實(shí)線表示始終會(huì)執(zhí)行該路徑，虛實(shí)線則表示有可能執(zhí)行該路徑。同理，還存在不透明謂詞始終會(huì)執(zhí)行flase分支的OF和無(wú)法確定執(zhí)行分支的O?。在提高控制流混淆強(qiáng)度上，不透明謂詞混淆有著顯著的效果。

2.2 不可達(dá)路徑分析

在程序優(yōu)化和編譯優(yōu)化領(lǐng)域中，消除程序中的不可達(dá)路徑是一個(gè)重要目標(biāo)。不可達(dá)路徑分析是靜態(tài)數(shù)據(jù)流分析的重要應(yīng)用方向之一。將控制流圖定義為有向圖G=〈N，E，start,end〉，其中N表示控制流圖中的節(jié)點(diǎn)集合，表示程序中的基本塊，E表示圖中邊集合，若程序中有ni跳轉(zhuǎn)到nj的語(yǔ)句，則在G中有一條從ni到nj的有向邊，記為e=(ni,nj)∈E，節(jié)點(diǎn)start和end表示控制流的起點(diǎn)和終點(diǎn)。假設(shè)某程序路徑p=〈n1,n2,…,nm〉，其中m為路徑長(zhǎng)度，ni(1≤i≤m)為程序基本塊。該路徑上存在k條語(yǔ)句為判斷語(yǔ)句，記為集合JD={li|i=1,2,…,k}。集合中的任一語(yǔ)句li都對(duì)應(yīng)一個(gè)判斷條件ci，判斷條件ci通常是由數(shù)個(gè)原子謂詞及邏輯連接詞組成的布爾表達(dá)式。對(duì)于路徑p，其路徑約束條件表達(dá)式為c1∧c2∧…∧ck。如果存在一組輸入變量，使得路徑條件c1∧c2∧…∧ck值為true，稱路徑p為可達(dá)路徑；否則稱為不可達(dá)路徑。

2.3 符號(hào)執(zhí)行

在1975年King[8]最早提出符號(hào)執(zhí)行用于測(cè)試軟件缺陷，可以自動(dòng)化地分析程序中是否存在除0錯(cuò)誤、空指針引用和后門(mén)等。符號(hào)執(zhí)行是一種靜態(tài)程序分析技術(shù)，是把輸入進(jìn)行符號(hào)化，基于控制流程圖生成一顆符號(hào)執(zhí)行樹(shù)，把所有路徑表示為以輸入的符號(hào)為變量的約束表達(dá)式，對(duì)特定路徑的約束表達(dá)式求解生成具體的輸入數(shù)據(jù)。符號(hào)執(zhí)行被廣泛應(yīng)用于不可達(dá)路徑分析當(dāng)中；但由于靜態(tài)分析并沒(méi)有實(shí)際執(zhí)行，因此在遇到循環(huán)、遞歸等代碼邏輯或者環(huán)境交互等這些在靜態(tài)分析中無(wú)法確定的情況時(shí)，會(huì)出現(xiàn)無(wú)法生成約束的問(wèn)題，導(dǎo)致路徑爆炸。

2005年Godefroid等[9]提出動(dòng)態(tài)符號(hào)執(zhí)行用于動(dòng)態(tài)生成測(cè)試數(shù)據(jù)。這是一種典型的結(jié)合靜態(tài)分析和動(dòng)態(tài)分析的混合執(zhí)行技術(shù)，其主要思想是用具體執(zhí)行來(lái)驅(qū)動(dòng)符號(hào)執(zhí)行，用一個(gè)具體的輸入運(yùn)行程序，并在運(yùn)行過(guò)程中收集路徑的約束條件，再使用約束求解器對(duì)這些約束條件取反并求解之后來(lái)生成能夠執(zhí)行其他路徑的輸入。這避免了上面提到的靜態(tài)符號(hào)執(zhí)行中存在的問(wèn)題，因?yàn)樗鎸?shí)地運(yùn)行了程序，能夠直接執(zhí)行庫(kù)函數(shù)并能夠跟環(huán)境交互，循壞次數(shù)和遞歸等都是確定的。其主要過(guò)程如圖2所示。2011年Avgerinos等[10]提出了AEG符號(hào)執(zhí)行引擎。這是基于符號(hào)執(zhí)行分析程序源代碼中潛在的棧破壞漏洞以及return-into-libc攻擊方式的自動(dòng)構(gòu)建，以漏洞優(yōu)先為路徑搜索策略。2012年Cha等[11]提出了MAYHEM符號(hào)執(zhí)行引擎，它是基于動(dòng)態(tài)符號(hào)執(zhí)行發(fā)現(xiàn)二進(jìn)制程序中潛在的漏洞，不需要獲得程序的源代碼。

圖2 動(dòng)態(tài)符號(hào)執(zhí)行過(guò)程

目前動(dòng)態(tài)符號(hào)執(zhí)行[12-15]是軟件安全領(lǐng)域的重點(diǎn)研究對(duì)象之一，有非常廣泛的應(yīng)用前景，常見(jiàn)的動(dòng)態(tài)符號(hào)執(zhí)行軟件如表1所示。由于ANGR使用了狀態(tài)合并和選擇符號(hào)執(zhí)行等多種優(yōu)化技術(shù)[16]，因此本文使用此動(dòng)態(tài)符號(hào)執(zhí)行引擎來(lái)實(shí)現(xiàn)原型系統(tǒng)。

表1 常見(jiàn)動(dòng)態(tài)符號(hào)執(zhí)行軟件

3 不透明謂詞反混淆算法

本算法通過(guò)動(dòng)態(tài)符號(hào)執(zhí)行對(duì)原程序混淆后所產(chǎn)生的所有條件分支進(jìn)行不可達(dá)路徑分析，其主要思路是通過(guò)動(dòng)態(tài)符號(hào)執(zhí)行對(duì)不透明謂詞混淆后的全部分支做路徑不可達(dá)性分析，先從函數(shù)起始基本塊到分支路徑做動(dòng)態(tài)符號(hào)執(zhí)行收集路徑的約束條件，然后對(duì)其進(jìn)行可滿足性求解，如果無(wú)解就判定分支不可達(dá)，最后把不可達(dá)的分支從程序中去除還原出原來(lái)的邏輯。如果條件分支中存在一個(gè)分支可達(dá)，但是另一個(gè)分支不可達(dá)，在這種情況下就把不可達(dá)的分支從控制流圖中切除。如果2個(gè)分支都不可達(dá)或者都可達(dá)則不對(duì)其進(jìn)行處理，避免在特殊情況下所帶來(lái)的負(fù)面影響，例如實(shí)際代碼中某些分支需要滿足特定的時(shí)間條件才能進(jìn)入，如果把這種分支切除就會(huì)影響原來(lái)的代碼邏輯。

整個(gè)算法首先是通過(guò)控制流圖分析得到每個(gè)函數(shù)的基本塊，然后對(duì)含有分支的基本塊進(jìn)行路徑可達(dá)性分析，最后進(jìn)行Patch來(lái)去除不可達(dá)路徑，整體流程如圖3所示。

圖3 反混淆算法整體流程

算法1 路徑可達(dá)性分析算法PathReachability。

輸入：start表示函數(shù)的起始地址；target表示條件分支的起始地址。

輸出：b表示條件分支是否可達(dá)。

initSymbolicState(start,s,δ)

dynamicSymbolicExecute(target,s,δ)

IF SAT (δ) THEN

b←TRUE

ELSE

b←FALSE

ENDIF

算法1中start表示一個(gè)函數(shù)的起始地址，target表示一個(gè)條件分支的起始地址，initSymbolicState根據(jù)函數(shù)的起始地址初始化符號(hào)執(zhí)行的狀態(tài)空間s和路徑約束集δ，接下來(lái)dynamicSymbolicExecute把一個(gè)條件分支的起始地址作為目的地址，并傳入初始化后的狀態(tài)空間和路徑約束集進(jìn)行動(dòng)態(tài)符號(hào)執(zhí)行，如果路徑約束集有解就表示該分支可達(dá)返回true，反之返回false。

在完成條件分支的路徑可達(dá)性分析后需要把不可達(dá)的分支從控制流圖中切除，主要過(guò)程如算法2所示。

算法2 基本塊修改算法Patch。

輸入：preBlock表示條件分支前置基本塊起始地址；branch表示條件分支的起始地址。

輸出：preBlock表示修改后的前置基本塊。

last ← getLastInstruction(preBlock)

offset ← branch-last

instruction ← newJmpInstruction(offset)

preBlock ← changeLastInstruction(preBlock,instruction)

算法2首先getLastInstruction獲取一個(gè)條件分支的前置基本塊的最后一條指令的地址，然后計(jì)算條件分支的起始地址與前置基本塊最后一條指令的地址的偏移offset，接著newJmpInstruction根據(jù)偏移新建一條跳轉(zhuǎn)的分支，并changeLastInstruction把前置基本塊的最后一條指令修改成之前新建的跳轉(zhuǎn)指令。

通過(guò)算法1中的路徑可達(dá)性分析確定分支的可達(dá)性之后，再利用算法2修改基本塊去除不可達(dá)的分支，結(jié)合這2個(gè)算法形成最終的不透明謂詞反混淆算法，具體過(guò)程如算法3所示。

算法3 不透明謂詞反混淆算法。

輸入：p表示不透明謂詞混淆后的二進(jìn)制程序。

輸出：pd表示反混淆后的二進(jìn)制程序。

cfg ← analysisCFG(p)

reachables ← ?

FOR function IN cfg. functions

FOR block in function. blocks

IF count(block.successors)==2 THEN

IF PathReachability(function,block.successors[0])THEN

reachables U block.successors[0]

ENDIF

…

IF count(reachables)==1 THEN

block ← Patch(block,reachables[0])

pd← apply(p,block

ENDIF

ENDIF

ENDFOR

ENDFOR

算法3首先分析不透明混淆后的二進(jìn)制程序的控制流圖，然后依次遍歷每個(gè)函數(shù)中的每個(gè)基本塊，當(dāng)一個(gè)基本塊有2個(gè)后繼節(jié)點(diǎn)，即有條件分支時(shí)，對(duì)其使用PathReachability算法(算法1)做路徑可達(dá)性分析，如果只有一個(gè)分支可達(dá)就使用Patch算法(算法2)把不可達(dá)分支切除，最后把修改后的基本塊應(yīng)用到二進(jìn)制程序中。

4 實(shí)驗(yàn)與分析

為證明本文提出的基于動(dòng)態(tài)符號(hào)執(zhí)行的不透明反混淆算法的有效性，本節(jié)進(jìn)行實(shí)驗(yàn)并分析結(jié)果。實(shí)驗(yàn)的操作系統(tǒng)為Ubuntu 16.04，內(nèi)存為4 GB，CPU為2.9 GHz Intel Core i7。實(shí)驗(yàn)使用的混淆工具是Obfuscator-LLVM 4.0。它是一個(gè)基于LLVM IR實(shí)現(xiàn)的混淆工具，能夠提供不透明謂詞混淆、控制流平展化和指令替換的功能。測(cè)試集是coreutils 8.28軟件集，原型系統(tǒng)使用的符號(hào)執(zhí)行引擎為ANGR[16]。對(duì)測(cè)試集中的部分程序進(jìn)行不透明謂詞混淆后使用原型系統(tǒng)進(jìn)行反混淆，實(shí)驗(yàn)結(jié)果如表2所示。

表2 反混淆前后有條件分支的基本塊數(shù)量對(duì)比

由于不透明謂詞混淆后會(huì)增加很多條件判斷，因此，本文以含有條件分支的基本塊數(shù)量來(lái)衡量反混淆率。從表中可以看出，在進(jìn)行不透明謂詞混淆后，有條件分支的基本塊數(shù)量有了顯著增加，在使用本文提出的基于動(dòng)態(tài)符號(hào)執(zhí)行的不透明謂詞反混淆算法實(shí)現(xiàn)的原型系統(tǒng)進(jìn)行反混淆后有條件分支的基本塊數(shù)量明顯減少，平均反混淆率為81%。這降低了混淆后的程序復(fù)雜度，有助于后續(xù)的分析工作，但是隨著程序的基本塊數(shù)量增加會(huì)導(dǎo)致性能下降，增加耗時(shí)。

5 總結(jié)

本文提出了一種基于動(dòng)態(tài)符號(hào)執(zhí)行的不透明謂詞反混淆算法，它有效降低了經(jīng)過(guò)不透明謂詞混淆后程序的分析難度，減少了應(yīng)急時(shí)間。后續(xù)將會(huì)在符號(hào)執(zhí)行時(shí)適當(dāng)使用函數(shù)摘要來(lái)提高性能，也會(huì)對(duì)控制流平展化和指令替換的反混淆算法做研究，以此來(lái)降低經(jīng)過(guò)多種類別混淆后的程序的分析難度。

參 考 文 獻(xiàn)

[1] 馬洪亮, 王偉, 韓臻. 混淆惡意JavaScript代碼的檢測(cè)與反混淆方法研究[J]. 計(jì)算機(jī)學(xué)報(bào), 2017, 40(7): 1699-1713.

[2] 郭軍, 王蕾, 湯戰(zhàn)勇，等. 基于語(yǔ)義的二進(jìn)制代碼自動(dòng)化反混淆方法[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 44(3): 55-59.

[3] BALAKRISHNAN G, SANKARANARAYANAN S. SLR: Path-sensitive analysis through infeasible-path detection and syntactic language refinement [C]//Static Analysis. Heidelberg: Springer Berlin, 2008, 5079: 238-254.

[4] COLLBERG C, THOMBORSON C, LOW D. Manufacturing cheap, resilient, andstealthy opaque constructs[C]//Proceedings of the 25thACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 1998:184-196.

[5] MAJUMDAR A, THOMBORSON C. Manufacturing opaque predicates in distributed systems for code obfuscation[C]//Proceedings of the 29thAustralasian Computer Science Conference. Darlinghurst: Australian Computer Society, 2006: 187-196.

[6] 袁征, 馮雁, 溫巧燕,等.構(gòu)造一種新的混淆Java程序的不透明謂詞[J]. 北京郵電大學(xué)學(xué)報(bào), 2007, 30(6): 103-106.

[7] 蘇慶, 吳偉民, 李忠良,等. 混沌不透明謂詞在代碼混淆中的研究與應(yīng)用[J]. 計(jì)算機(jī)科學(xué), 2013, 40(6): 155-159.

[8] KING J C. A new approach to program testing[J]. ACM Sigplan Notices, 1975,10(6): 228-233.

[9] GODEFROID P, KLARLUND N, SEN K. DART: Directed automated random testing[J]. Proc ACM SIGPLAN Conf on Programming Language Design and Implementation, 2005,40(6): 213-223.

[10] AVGERINOS T, CHA S K, HAO B L T, et al. AEG:automatic exploit generation[C]//Proc Network and Distributed System Security Symp. [S.l.]:NDSS, 2011:1-18.

[11] CHA S K, AVGERINOS T, REBERT A, et al. Unleashing mayhem on binary code[J]. Security and Privacy, 2012, 19:380-394.

[12] 安靖. 動(dòng)態(tài)符號(hào)執(zhí)行關(guān)鍵技術(shù)研究[D]. 北京: 北京郵電大學(xué), 2014.

[13] LUCKOW K, DIMJSEVC M, GIANNAKOPOULOU D, et al.JD art: A dynamic symbolic analysis framework[C]//Proc 22nd Int Conf on Tools and Algorithms for the Construction and Analysis of Systems. Heidelerg: Springer Berlin, 2016: 442-459.

[14] ZHANG Y, CLIEN Z, WANG J,et al. Regular property guided dynamic symbolic execution[C]//Proc 37th Int Conf on Software Engineering, 2015,1: 643-653.

[15] CHIPOUNOV V, KUZNETSOV V, CANDEA G. The S2E platform: Design, implementation, and applications[J]. ACM Transactions onComputer Systems, 2012, 30(1):2.

[16] SHOSHITAISHVILI Y, WANG R, SALLS C,et al. SOK: (state of) the art of war: Offensive techniques in binary analysis[C]//In IEEE Symp on Security and Privacy.San Jose, CA,USA:IEEE, 2016: 138-157.