[[182416]]

一、前言

代碼覆蓋測(cè)試主要用于漏洞研究領(lǐng)域。主要目的是使用不同輸入覆蓋程序代碼的不同部分。如果某個(gè)輸入導(dǎo)致程序崩潰，我們將檢測(cè)崩潰是否能被利用。有很多代碼覆蓋測(cè)試的方法，比如隨機(jī)測(cè)試等。但是本文重點(diǎn)關(guān)注使用動(dòng)態(tài)符號(hào)執(zhí)行進(jìn)行代碼覆蓋測(cè)試。覆蓋代碼不意味著能找到所有的可能的缺陷。一些缺陷不會(huì)引起程序崩潰。然而2017年剛到，勒索軟件以驚人的速度爆發(fā)。這周我們發(fā)現(xiàn)了大量的新變種，尤其是以很有名的名次命名的FSociety。我們也發(fā)現(xiàn)了一些解密工具，圣誕節(jié)有關(guān)的勒索軟件，CryptoMix/CryptFile2的分析，大量的小的勒索軟件。

二、代碼覆蓋和動(dòng)態(tài)符號(hào)執(zhí)行(DSE)

不像SSE(靜態(tài)符號(hào)執(zhí)行)，DSE應(yīng)用于跟蹤，并且只有在執(zhí)行期間達(dá)到這些分支時(shí)才能發(fā)現(xiàn)新的分支。要想到達(dá)另一個(gè)路徑，我們必須搞清楚從上個(gè)跟蹤發(fā)現(xiàn)的分支約束條件。然后我們重復(fù)操作，直到到達(dá)所有分支。

舉個(gè)例子，我們假設(shè)程序P 有稱為I的輸入。I可以是模型M或者隨機(jī)種子R。執(zhí)行P(I)能返回一組PC約束。所有的φi表示基礎(chǔ)塊，πi表示分支約束。模型Mi是約束πi的一種可靠的解決方案，M1 = Solution(¬π1 ∧ π2)。為了發(fā)現(xiàn)所有的路徑，我們維護(hù)一個(gè)叫W的工作列表，它是一組M。

在***輪迭代，執(zhí)行I = R, W = ∅ 和P(I) → PC。然后是∀π ∈ PC, W = W ∪ {Solution(π)} ，再次執(zhí)行∀M ∈ W, P(M)。當(dāng)模型M作為程序的輸入后，將它從列表W中刪除。重復(fù)操作知道W為空。

符號(hào)執(zhí)行的代碼覆蓋測(cè)試既有優(yōu)點(diǎn)又有缺點(diǎn)。它對(duì)于在混淆的二進(jìn)制文件中很有幫助。確實(shí)利用符號(hào)覆蓋能檢測(cè)到隱藏的、不可達(dá)到的代碼但會(huì)是個(gè)平面的圖表。最糟糕的是當(dāng)你的表達(dá)式太復(fù)雜，可能會(huì)超時(shí)或巨大的內(nèi)存消耗(在過去，我們符號(hào)表達(dá)式在超時(shí)前消耗了差不多450 G的 RAM)。這種場(chǎng)景主要發(fā)生在分析超大二進(jìn)制文件或者包含復(fù)雜功能的混淆的二進(jìn)制文件。

三、使用Triton進(jìn)行代碼覆蓋測(cè)試

從版本v0.1 build 633開始，Triton整合了我們代碼覆蓋測(cè)試需要的一切。它可以讓我們更好的處理及計(jì)算SMT2-lib表達(dá)的AST。下面我們將關(guān)注代碼覆蓋的設(shè)計(jì)和使用的算法。

1. 算法

以下面的代碼為例。

01. char *serial = "\x31\x3e\x3d\x26\x31"; 
02. int check(char *ptr) 
03. { 
04.   int i = 0; 
05.   while (i < 5){ 
06.     if (((ptr[i] - 1) ^ 0x55) != serial[i]) 
07.       return 1; 
08.     i++; 
09.   } 
10.   return 0; 
11. } 

函數(shù)控制流圖如下顯示。它是一個(gè)好例子，因?yàn)槲覀冃枰业胶玫妮斎氩拍芨采w所有的基礎(chǔ)塊。

可以看到可以看到只有一個(gè)變量可控，位于地址rbp+var_18，指向argv[1]的指針。目標(biāo)是通過計(jì)算約束條件和使用快照引擎到達(dá)check函數(shù)的所有基礎(chǔ)塊。例如到達(dá)位于地址0x4005C3基礎(chǔ)塊的約束條件是[rbp+var_4] > 4，但是我們不能直接控制這個(gè)變量。另一方面，在地址0x4005B0處的跳轉(zhuǎn)依賴于用戶的輸入并且這個(gè)約束條件可以通過符號(hào)執(zhí)行解決。

歸納以前的想法的算法是使用基于微軟的Fuzzer算法(SAGE)，下圖表示包含約束條件的check函數(shù)。這個(gè)start和end節(jié)點(diǎn)表示了我們的函數(shù)開端(0x40056D)和函數(shù)的結(jié)尾(0x4005C8)

在***執(zhí)行前，我們不知道任何的分支約束。因此我們按照上文所述，我們注入一些隨機(jī)種子來收集***個(gè)PC并且構(gòu)建我們的W集合。***執(zhí)行P(I)的跟蹤結(jié)果由下圖藍(lán)色表示。

執(zhí)行結(jié)果給了我們***條路徑約束P(I) → (π0 ∧ ¬π1)。

基于***次跟蹤，我們知道發(fā)現(xiàn)了兩條分支(π0 ∧ ¬π1)，并且還有兩條沒有發(fā)現(xiàn)。為了到達(dá)基礎(chǔ)塊φ3，我們計(jì)算***個(gè)分支約束的否定條件。當(dāng)且僅當(dāng)Solution(¬π0) 是SAT，我們將它添加到模型工作列表W中。

同樣到達(dá) φ4 可以得到W = W ∪ {Solution(π0 ∧ ¬(¬π1))}。所有解決方案都生成了并且模型被添加到工作列表中，我們執(zhí)行工作列表中每個(gè)模型。

2. 實(shí)現(xiàn)

執(zhí)行代碼覆蓋的一個(gè)條件是在一個(gè)跳轉(zhuǎn)指令處能預(yù)測(cè)下一條指令的地址。這是構(gòu)建路徑約束的必要條件。

我們不能在一個(gè)分支指令后放置一個(gè)回調(diào)，因?yàn)镽IP寄存器已經(jīng)改變了。因?yàn)門riton為所有的寄存器創(chuàng)建語義表達(dá)式，所以在分支指令時(shí)可以判定RIP。

***次，我們開發(fā)了一個(gè)SMT判定器用來計(jì)算RIP，但是我們發(fā)現(xiàn)Pin提供的用于獲得下一個(gè)RIP值的IARG_BRANCH_TARGET_ADDR和IARG_BRANCH_TAKEN有點(diǎn)滯后。使用Pin計(jì)算下一個(gè)地址非常簡(jiǎn)單，但是SMT判定器用來檢查指令的語義是很有用的。

為了更好的演示判定，我們實(shí)現(xiàn)了visitor pattern來將SMT的抽象語法樹(AST)轉(zhuǎn)化為Z3的抽象語法樹。這個(gè)設(shè)計(jì)能夠用于將SMT AST轉(zhuǎn)化為任意其他的表達(dá)。

Z3的AST使用Z3 API處理更加簡(jiǎn)單。轉(zhuǎn)化代碼是src/smt2lib/z3AST.h 和 src/smt2lib/z3AST.cpp

現(xiàn)在我們解釋代碼覆蓋的工具如何工作。讓我們假定輸入來自命令行。

首先，我們有：

160. def run(inputSeed, entryPoint, exitPoint, whitelist = []): 
161. ... 
175. if __name__=='__main__': 
176.   TritonExecution.run("bad !", 0x400480, 0x40061B, ["main", "check"]) # crackme_xor 

在176行，我們定義了輸入種子bad!，代表程序的***個(gè)參數(shù)。然后我們給出代碼覆蓋的起始地址，在這個(gè)地址我們將做一個(gè)快照。第三個(gè)參數(shù)將匹配***一個(gè)塊，這個(gè)地址我們將恢復(fù)快照。***，我們?cè)O(shè)置一個(gè)避免庫函數(shù)、加密函數(shù)等的白名單。

134. def mainAnalysis(threadId): 
135. 
136.    print "[+] In main" 
137.    rdi = getRegValue(IDREF.REG.RDI) # argc 
138.    rsi = getRegValue(IDREF.REG.RSI) # argv 
139. 
140.    argv0_addr = getMemValue(rsi, IDREF.CPUSIZE.QWORD)      # argv[0] pointer 
141.    argv1_addr = getMemValue(rsi + 8, IDREF.CPUSIZE.QWORD)  # argv[1] pointer 
142. 
143.    print "[+] In main() we set :" 
144.    od = OrderedDict(sorted(TritonExecution.input.dataAddr.items())) 
145. 
146.    for k,v in od.iteritems(): 
147.        print "\t[0x%x] = %x %c" % (k, v, v) 
148.        setMemValue(k, IDREF.CPUSIZE.BYTE, v) 
149.        convertMemToSymVar(k, IDREF.CPUSIZE.BYTE, "addr_%d" % k) 
150. 
151.    for idx, byte in enumerate(TritonExecution.input.data): 
152.        if argv1_addr + idx not in TritonExecution.input.dataAddr: # Not overwrite the previous setting 
153.            print "\t[0x%x] = %x %c" % (argv1_addr + idx, ord(byte), ord(byte)) 
154.            setMemValue(argv1_addr + idx, IDREF.CPUSIZE.BYTE, ord(byte)) 
155.            convertMemToSymVar(argv1_addr + idx, IDREF.CPUSIZE.BYTE, "addr_%d" % idx) 

下一個(gè)執(zhí)行的代碼是mainAnalysis回調(diào)函數(shù)，我們注入一些值到輸入中(行148，154)，我們能通過符號(hào)變量覆蓋這些輸入(行149，155)。

所有被選擇的輸入存儲(chǔ)在全局變量TritonExecution.input中。然后我們開始代碼檢測(cè)。

58. if instruction.getAddress() == TritonExecution.entryPoint and not isSnapshotEnabled(): 
59.        print "[+] Take Snapshot" 
60.        takeSnapshot() 
61.        return 

當(dāng)我們?cè)谌肟邳c(diǎn)時(shí)，我們做一個(gè)快照，為了用新的輸入重新執(zhí)行代碼檢測(cè)。

52. if instruction.getAddress() == TritonExecution.entryPoint + 2: 
53.   TritonExecution.myPC = []                                  # Reset the path constraint 
54.   TritonExecutionTritonExecution.input = TritonExecution.worklist.pop()     # Take the first input 
55.   TritonExecution.inputTested.append(TritonExecution.input)  # Add this input to the tested input 
56.   return 

我們重置路徑約束(行53)，從工作列表中取出一個(gè)新的輸入。

63. if instruction.isBranch() and instruction.getRoutineName() in TritonExecution.whitelist: 
64. 
65.   addr1 = instruction.getAddress() + 2                # Address next to this one 
66.   addr2 = instruction.getOperands()[0].getValue()     # Address in the instruction condition 
67. 
68.   # [PC id, address taken, address not taken] 
69.   if instruction.isBranchTaken(): 
70.     TritonExecution.myPC.append([ripId, addr2, addr1]) 
71.   else: 
72.     TritonExecution.myPC.append([ripId, addr1, addr2]) 
73. 
74.   return 

上述代碼檢測(cè)是否位于分支指令(如jnz，jle等)或者位于白名單中的函數(shù)中。如果是，我們得到兩種可能的地址(addr1和addr2)，通過isBranchTaken()(行69)計(jì)算有效的地址。

然后，我們將條件約束存儲(chǔ)在RIP表達(dá)式中。

81. if instruction.getAddress() == TritonExecution.exitPoint: 
82.  print "[+] Exit point" 
83. 
84.  # SAGE algorithm 
85.  # http://research.microsoft.com/en-us/um/people/pg/public_psfiles/ndss2008.pdf 
86.  for j in range(TritonExecution.input.bound, len(TritonExecution.myPC)): 
87.      expr = [] 
88.      for i in range(0,j): 
89.          ripId = TritonExecution.myPC[i][0] 
90.          symExp = getFullExpression(getSymExpr(ripId).getAst()) 
91.          addr = TritonExecution.myPC[i][1] 
92.          expr.append(smt2lib.smtAssert(smt2lib.equal(symExp, smt2lib.bv(addr,  64)))) 
93. 
94.      ripId = TritonExecution.myPC[j][0] 
95.      symExp = getFullExpression(getSymExpr(ripId).getAst()) 
96.      addr = TritonExecution.myPC[j][2] 
97.      expr.append(smt2lib.smtAssert(smt2lib.equal(symExp, smt2lib.bv(addr,  64)))) 
98. 
99. 
100.      expr = smt2lib.compound(expr) 
101.      model = getModel(expr) 
102. 
103.      if len(model) > 0: 
104.          newInput = TritonExecution.input 
105.          newInput.setBound(j + 1) 
106. 
107.          for k,v in model.items(): 
108.              symVar = getSymVar(k) 
109.              newInput.addDataAddress(symVar.getKindValue(), v) 
110.          print newInput.dataAddr 
111. 
112.          isPresent = False 
113. 
114.          for inp in TritonExecution.worklist: 
115.              if inp.dataAddr == newInput.dataAddr: 
116.                  isPresent = True 
117.                  break 
118.          if not isPresent: 
119.              TritonExecution.worklist.append(newInput) 
120. 
121.  # If there is input to test in the worklist, we restore the snapshot 
122.  if len(TritonExecution.worklist) > 0 and isSnapshotEnabled(): 
123.      print "[+] Restore snapshot" 
124.      restoreSnapshot() 
125. 
126.  return 

當(dāng)我們?cè)诔隹邳c(diǎn)是是***一步。行84-120是SAGE的實(shí)現(xiàn)。簡(jiǎn)言之，我們?yōu)g覽路徑約束列表，對(duì)于每個(gè)PC，我們嘗試獲得滿足否定的模型。如果有不可靠的模型到達(dá)了新的目標(biāo)塊中，我們將這個(gè)模型添加到工作列表中。一旦所有的模型被插入工作列表中，我們恢復(fù)快照并且重新執(zhí)行每個(gè)模型。

全部代碼能在這里找到，我們例子的執(zhí)行過程如下：

四、總結(jié)

盡管代碼覆蓋使用符號(hào)執(zhí)行是一個(gè)好的方法，但它是個(gè)復(fù)雜的任務(wù)。路徑遍歷意味著內(nèi)存消耗，并且一些情況下要計(jì)算的表達(dá)式太過復(fù)雜。目前，判定器非常慢，判定表達(dá)式非常慢。