Abstract
不使用符號執(zhí)行來解決路徑約束，從而增加分支覆蓋率。為了有效地解決路徑約束，我們引入了幾個關鍵技術：可擴展的字節(jié)級污點跟蹤，上下文敏感的分支計數(shù)，基于梯度下降的搜索和輸入長度探索。
Design
使用上下文敏感的分支覆蓋作為覆蓋的度量。每次 fuzzing，Angora 選擇一個未探索的分支并搜索探索該分支的輸入。
- 對于大多數(shù)條件語句，其判斷僅受輸入中的幾個字節(jié)的影響，因此改變整個輸入將是徒勞的。因此，在探索分支時，Angora會確定哪些輸入字節(jié)流入相應的判斷，并專注于僅改變這些字節(jié)
- 確定要改變的輸入字節(jié)后，將分支上的路徑約束視為輸入上黑盒函數(shù)的約束，并且我們調整梯度下降算法來解決約束
- 在梯度下降期間，我們對黑盒函數(shù)的參數(shù)進行評估，其中一些參數(shù)由多個字節(jié)組成
- 僅僅改變輸入中的字節(jié)是不夠的。只有在輸入超過閾值后才會觸發(fā)一些錯誤，Angora 對程序進行插樁，檢測什么時候較長的輸入能夠探索新分支并且確定所需的最小長度
上下文敏感的分支計數(shù)
元組：
除了分支前后基本塊的 ID，context 是 ，h 是哈希函數(shù)，stack 包含調用棧的狀態(tài)。
因為上下文改變之后到達同一個分支可能觸發(fā)新的內部狀態(tài)。
目前的實現(xiàn)是使用 h 計算所有調用位置 ID 的異或，當 Angora 對程序插樁時，它會為每個調用點分配一個隨機 ID。
字節(jié)級污點跟蹤
Angora 的目標是創(chuàng)建能夠執(zhí)行未被探索的分支的輸入。當它嘗試執(zhí)行未探測的分支時，它必須知道輸入中的哪些字節(jié)偏移影響分支的判斷。因此，Angora需要字節(jié)級別的污點跟蹤。
Angora將程序中的每個變量x與污點標簽tx相關聯(lián)，污點標簽tx表示輸入中可能流入x的字節(jié)偏移量。污點標簽須支持的操作：
- INSERT(b)：插入位向量b并返回其標簽。
- FIND(t)：返回污點標簽t的位向量。
- UNION(tx; ty)：返回污點標簽，表示污點標簽tx和ty的位向量的并集。
不可行的實現(xiàn)：
- 將污點標簽表示為位向量，位 i 表示輸入的第 i 個字節(jié)，那么大輸入就會是禁止的。
- 將位向量存儲在表中，使用索引作為污點標簽，但是 union 代價會很高，union 首先找到兩個標簽的位向量并計算并集 u，接下來會搜索表確定 u 是否已經(jīng)存在，代價很高。
新的數(shù)據(jù)結構，為每個位向量分配唯一標簽（無符號整數(shù)）：
-
二叉樹將位向量映射到其標簽，每個位向量 b 由 level
的唯一節(jié)點
表示，其中
- 查找表將標簽映射到其位向量。標簽是該表的索引，相應的條目指向表示該標簽的位向量的樹節(jié)點。
INSERT：
- 刪除向量的所有尾隨 0
- 跟蹤向量中的位，如果為 0，遍歷左子樹，為 1，遍歷右子樹，如果不存在，創(chuàng)建新節(jié)點
- 將向量標簽存儲在最后一個節(jié)點中
基于梯度下降的搜索算法
字節(jié)級污點跟蹤發(fā)現(xiàn)了輸入的哪些字節(jié)流入條件語句。但是如何改變輸入以運行未探索的分支語句？
將分支的判斷看作黑盒函數(shù) 的約束，
是輸入中流入判斷的值的向量，
捕獲從程序開始到此判斷的路徑的計算，
有三種約束：
如果包含邏輯運算 $$ 或者 ||，Angora 將語句拆分成多個條件語句，如 if (a && b) { s } else { t } 拆分為 if ( a ) { if ( b ) { s } else { t }} else { t }
形狀和類型推斷
對于形狀推斷，最初輸入中的所有字節(jié)都是獨立的。在污點分析期間，當指令將輸入字節(jié)序列讀入變量，其中序列的大小與基本類型的大小匹配（如 1，2，4，8 字節(jié)），Angora 標記這些字節(jié)輸入相同值。當沖突發(fā)生時，Angora 使用最小的 size。
對于類型推斷，Angora 依賴于對值進行操作的指令的語義。如果指令對有符號整數(shù)進行操作，那么 Angora 將相應的操作數(shù)推斷為有符號整數(shù)，當相同的值同時用作有符號和無符號類型時，Angora 將其視為無符號類型。
輸入長度探索
與大多數(shù)其他模糊器一樣，Angora開始使用盡可能小的輸入進行模糊測試。但是，僅當輸入長于閾值時才執(zhí)行某些分支。這給模糊器帶來了兩難境地。如果模糊器使用太短的輸入，則無法探索這些分支。但如果它使用太長的輸入，程序可能運行緩慢甚至內存不足。
在污點跟蹤期間，Angora 將類似 read 的函數(shù)調用中的目標內存輸入中的相應字節(jié)偏移相關聯(lián)。它還使用特殊標簽標記來自讀取調用的返回值。如果在條件語句中使用返回值并且不滿足約束，則Angora會增加輸入長度，以便讀取調用可以獲取它請求的所有字節(jié)。
Implementation
插樁
Angora 通過 LLVM Pass 來對程序進行插樁。插樁
- 收集條件語句的基本信息，并通過污點分析將條件語句鏈接到其對應的輸入字節(jié)偏移。
- 記錄執(zhí)行 trace 以識別新輸入
- 在運行時支持上下文
- 在判斷時收集表達式值（梯度下降）
為了支持可擴展的字節(jié)級污點跟蹤，我們通過擴展 DataFlowSanitizer (DFSan) 為 Angora 實現(xiàn)了污點跟蹤。我們?yōu)?FIND 和 UNION 操作實現(xiàn)了緩存機制，顯著加快了污點跟蹤。
Angora 依賴于 LLVM 4.0.0（包括 DFSan），它的 LLVM Pass 有 820 行 C++ 代碼（不包括 DFSan），runtime 有 1950 行 C++ 代碼，包含存儲污點標簽的數(shù)據(jù)結構以及用于污染輸入和跟蹤條件語句的 hooks。
Angora 將每個 switch 語句轉換為 if 語句序列。Angora 識別 libc 函數(shù)，用于在條件語句中出現(xiàn)時比較字符串和數(shù)組。例如，Angora將 “strcmp（x，y）”轉換為 “x strcmp y”，其中strcmp是Angora理解的特殊比較運算符。
Fuzzer
我們以 4488 行 Rust 代碼實現(xiàn)了 Angora，我們使用 fork server 和 CPU 綁定等技術優(yōu)化了 Angora。
