本篇文章收錄于2021年網(wǎng)絡(luò)安全頂會(huì)NDSS，介紹了最新的符號(hào)執(zhí)行技術(shù)，并且清晰地比較了當(dāng)前流行的各種符號(hào)執(zhí)行的引擎的優(yōu)劣勢(shì)，可以比較系統(tǒng)的了解符號(hào)執(zhí)行技術(shù)的相關(guān)知識(shí)

title =        {{SymQEMU}: Compilation-based symbolic execution for binaries},  
author =       {Poeplau, Sebastian and Francillon, Aurélien},  
booktitle =    .NETwork and Distributed System Security Symposium},  
year =         2021,  organization = {Network & Distributed System Security Symposium},  
month =        {February},  affiliations = {Eurecom, Code Intelligence},  
extralink =    {Details: tools/symbolic_execution/symqemu.html}  
download_address = https://www.ndss-symposium.org/wp-content/uploads/2021-118-paper.pdf`

摘 要

符號(hào)執(zhí)行技術(shù)是針對(duì)軟件分析和bug檢測(cè)的強(qiáng)力技術(shù)，基于編譯的符號(hào)執(zhí)行技術(shù)是最近提出的一種方法，當(dāng)對(duì)象源代碼可以得到時(shí)可以提升符號(hào)執(zhí)行的性能。本文提出了一種新的基于編譯的，針對(duì)二進(jìn)制文件的符號(hào)執(zhí)行技術(shù)。此系統(tǒng)名為symqemu，在qemu基礎(chǔ)之上開發(fā)，在將target程序轉(zhuǎn)換為host架構(gòu)的機(jī)器碼之前修改其IR，這使得symqemu能夠?qū)⒕幾g符號(hào)執(zhí)行引擎的能力應(yīng)用于二進(jìn)制文件，并且在維持架構(gòu)獨(dú)立性的同時(shí)能夠獲得性能上的提升。

本文提出了這個(gè)方法以及其實(shí)現(xiàn)，我們利用統(tǒng)計(jì)學(xué)方法證明了他比最先進(jìn)的符號(hào)執(zhí)行引擎s2e以及qsym，在某些benchmarks上，他甚至由于針對(duì)源碼帶分析的symcc。并且利用symqemu在經(jīng)過多重測(cè)試的library上發(fā)現(xiàn)了一個(gè)位置漏洞，證明了他在實(shí)際軟件中的可用性。

介 紹

符號(hào)執(zhí)行技術(shù)近年來大力發(fā)展，一種有效但是代價(jià)大的技術(shù)，其經(jīng)常與fuzzing技術(shù)混合，并成為混合fuzzing，fuzzing用來探索容易到達(dá)的路徑，而符號(hào)執(zhí)行用來探索不易到達(dá)的路徑。

針對(duì)符號(hào)執(zhí)行技術(shù)的重要特征之一就是其是否需要提供源代碼進(jìn)行分析，而真實(shí)世界中的大多數(shù)程序(由于某些原因)是不提供源代碼的。

所以binary-only的符號(hào)執(zhí)行技術(shù)被迫切需要，但是面臨一個(gè)兩難的困境，到底是選擇性能的提升還是架構(gòu)的獨(dú)立性呢？比如，QSYM針對(duì)binary有很高的性能，但是其僅限于x86處理器的指令集。它不僅僅造成了系統(tǒng)架構(gòu)依賴性，并且由于現(xiàn)在處理器指令的龐大提升了其復(fù)雜性。SE則是可以被廣泛的應(yīng)用但是性能較差，S2E可以分析多架構(gòu)代碼以及內(nèi)核代碼。然而他這么做的代價(jià)是針對(duì)target程序的多種翻譯的最終表示，導(dǎo)致了復(fù)雜性升高以及影響性能。

在本文中，我們提出了一個(gè)方法（a）獨(dú)立于被測(cè)試的程序的target架構(gòu)（b）實(shí)現(xiàn)復(fù)雜度低（c）具有高性能。symqemu的關(guān)鍵是qemu的cpu 仿真可以同于輕量級(jí)的符號(hào)執(zhí)行機(jī)制：不是像s2e中使用中的那種計(jì)算復(fù)雜度高的將target程序向IR的轉(zhuǎn)換方式，我們hook qemu中的二進(jìn)制轉(zhuǎn)換機(jī)制為了將符號(hào)處理直接編譯到機(jī)器碼中。這樣使得在性能優(yōu)于最先進(jìn)符號(hào)執(zhí)行系統(tǒng)的同時(shí)可以保持加夠獨(dú)立性。目前，我們針對(duì)于linux用戶程序(ELF binaries)，但我們可以將其拓展到任何qemu支持的架構(gòu)中取，同時(shí)我們將symqemu開源來加速未來相關(guān)領(lǐng)域的研究。

將符號(hào)處理編譯到target程序中同樣是symcc的核心工作，其性能優(yōu)于其他符號(hào)執(zhí)行引擎，但是symcc只針對(duì)于有源碼的程序。symqemu性能優(yōu)于se2以及qsym，并且相比于基于源代碼的symcc性能來說，某些情況也是可以比較。

本文工作主要有一下貢獻(xiàn)：

1. 分析了當(dāng)前最先進(jìn)的binary-only的符號(hào)執(zhí)行引擎并且明確了其設(shè)計(jì)中的優(yōu)勢(shì)和劣勢(shì)。
2. 提出了一個(gè)方法，融合了其他工具的優(yōu)勢(shì)，避免了其他工具的缺點(diǎn)，核心idea是應(yīng)用基于編譯的符號(hào)執(zhí)行技術(shù)到binary上，我們工具的源代碼開源。
3. 進(jìn)行了詳細(xì)的評(píng)價(jià)試驗(yàn)，并且實(shí)驗(yàn)數(shù)據(jù)以及實(shí)驗(yàn)?zāi)_本開源。

背 景

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

符號(hào)執(zhí)行的目的是在目標(biāo)程序的執(zhí)行過程中跟蹤中間值是如何計(jì)算的，每一個(gè)中間值都可以表示為程序輸入的一個(gè)公式。在任何點(diǎn)，系統(tǒng)都會(huì)使用這個(gè)公式查看這個(gè)點(diǎn)是否可達(dá)，這個(gè)指針是否為空等。如果答案是確定的，那么符號(hào)執(zhí)行引擎將會(huì)提供測(cè)試用例，一個(gè)新的輸入例子來觸發(fā)對(duì)應(yīng)的行為。所以符號(hào)執(zhí)行可以被方便的用來探測(cè)程序路徑以及觸發(fā)bug。

為了跟蹤程序的計(jì)算過程，符號(hào)執(zhí)行系統(tǒng)必須對(duì)程序指令集有一個(gè)深入的理解，許多實(shí)現(xiàn)都是通過將程序翻譯為IR，比如LLVM和VEX。IR隨后被符號(hào)化執(zhí)行，因?yàn)閳?zhí)行器只需要處理IR(通常由少量的指令集構(gòu)成)，所以實(shí)現(xiàn)相對(duì)比較簡(jiǎn)單。<font color=red>并且在之前的工作中我們發(fā)現(xiàn)，在對(duì)進(jìn)行測(cè)試的程序的高級(jí)表示的查詢較低級(jí)指令的表示的查詢更加容易解決。</font>

然而將程序轉(zhuǎn)換為IR需要計(jì)算能力并且對(duì)程序執(zhí)行過程引入了開銷；然而一些實(shí)現(xiàn)過程放棄了翻譯而直接工作在機(jī)器代碼上，這種解決方案除了性能上的優(yōu)勢(shì)，同時(shí)在執(zhí)行器無法怎樣解釋指令時(shí)，會(huì)幫助提升魯棒性。然而在另一方面，這種解決方案會(huì)導(dǎo)致執(zhí)行器被限制在了一種特定的架構(gòu)之中。另一種基于源碼的執(zhí)行器在實(shí)際中并不是那么廣泛使用，因?yàn)榇蠖鄶?shù)情況下只能得到二進(jìn)制文件。

binary-only符號(hào)執(zhí)行

僅僅針對(duì)二進(jìn)制文件的符號(hào)執(zhí)行添加了許多挑戰(zhàn)：缺少源代碼，將程序翻譯為IR需要可靠的反匯編器；由于靜態(tài)反匯編的挑戰(zhàn)，大多數(shù)實(shí)現(xiàn)都是在運(yùn)行態(tài)按需進(jìn)行反匯編。當(dāng)源碼不可得時(shí)，針對(duì)架構(gòu)的支持同樣也是重要的，此時(shí)交叉編譯不可行。尤其針對(duì)嵌入式設(shè)備來說，缺少對(duì)多架構(gòu)的支持是不可行的。

無需翻譯的執(zhí)行器除了面對(duì)復(fù)雜實(shí)現(xiàn)帶來的可維護(hù)問題外，還面臨可移植性問題。將程序翻譯為中間語(yǔ)言的執(zhí)行器需要可靠的反匯編器，已經(jīng)有大量的工作來確定翻譯器的準(zhǔn)確性。基于源碼的執(zhí)行器可以較容易的獲得IR。

基于二進(jìn)制文件的符號(hào)執(zhí)行對(duì)于高性能以及多架構(gòu)支持具有更迫切的需求。

最先進(jìn)解決方案

下面描述最先進(jìn)的符號(hào)執(zhí)行實(shí)驗(yàn)方案以及他們各自對(duì)應(yīng)解決的問題。

angr

一個(gè)經(jīng)典的符號(hào)執(zhí)行翻譯器，使用VEX，Valgrind框架的翻譯器和IR。目標(biāo)程序在運(yùn)行時(shí)被翻譯。其中一個(gè)優(yōu)化，angr可以在Unicorn，基于qemu的快速CPU模擬器，上執(zhí)行不涉及符號(hào)數(shù)據(jù)的計(jì)算。

由于基于VEX，agnr固然可以支持所有VEX能夠處理的架構(gòu)，因?yàn)閍ngr核心由Python/ target=_blank class=infotextkey>Python語(yǔ)言實(shí)現(xiàn)，所以他速度慢但是很通用。

s2e

由于想要將基于源代碼符號(hào)執(zhí)行覆蓋范圍拓展到目標(biāo)程序依賴以及操作系統(tǒng)內(nèi)核，創(chuàng)造了s2e。為了實(shí)現(xiàn)這個(gè)目的，s2e在qemu仿真器內(nèi)執(zhí)行整個(gè)操作系統(tǒng)并且將其與KLEE鏈接為了符號(hào)化執(zhí)行相關(guān)代碼。

這個(gè)系統(tǒng)相當(dāng)復(fù)雜，包括被測(cè)試程序的多重翻譯：

1. QEMU是一個(gè)二進(jìn)制文件翻譯器，比如在通常操作中，他講目標(biāo)程序從機(jī)器代碼翻譯為一種中間表示即TCG ops，然后將其重新編譯為針對(duì)host CPU的機(jī)器碼。
2. 當(dāng)執(zhí)行是設(shè)計(jì)符號(hào)化數(shù)據(jù)時(shí)，S2E使用的修改過的QEEMU不再將TCGops重編譯為機(jī)器代碼，他將其翻譯為L(zhǎng)LVM bitcode，隨后將其傳遞給KLEE。
3. KLEE符號(hào)化解釋執(zhí)行LLVM bitcode，然后將結(jié)果的具體情況回傳給QEMU。

此系統(tǒng)可以很靈活的處理不同處理器架構(gòu)，并且可以支持針對(duì)操作系統(tǒng)全層面的計(jì)算跟蹤。然而他需要付出一下代價(jià)：S2E是一個(gè)具有龐大代碼基礎(chǔ)的復(fù)雜系統(tǒng)。并且兩部分翻譯，從機(jī)器碼翻譯為TCG ops和從TCG ops翻譯為L(zhǎng)LVM bitcode損害了他的性能。與angr針對(duì)用戶態(tài)程序來比較，S2E需要更多的設(shè)計(jì)建立以及運(yùn)行，但是提供了一個(gè)更加全面的分析。

QSYM

QSYM在性能上有極大的增強(qiáng)，他不將目標(biāo)程序翻譯為中間語(yǔ)言。他在運(yùn)行態(tài)時(shí)向x86機(jī)器碼內(nèi)進(jìn)行插樁來向二進(jìn)制文件內(nèi)添加符號(hào)追蹤。具體來講，他應(yīng)用了Inter Pin，一種動(dòng)態(tài)二進(jìn)制插樁框架，來向目標(biāo)程序內(nèi)插入hook代碼。在hook內(nèi)部，他和程序運(yùn)行的實(shí)際代碼等價(jià)的運(yùn)行符號(hào)代碼。

這種方式產(chǎn)生了一種針對(duì)x86程序的非常快速并且魯棒性很強(qiáng)的符號(hào)執(zhí)行引擎。然而，這個(gè)系統(tǒng)固然會(huì)被限制在x86框架內(nèi)，并且實(shí)現(xiàn)是繁瑣的，因?yàn)樗枰幚碓谟?jì)算中可能出現(xiàn)的任何指令。并且將其遷移到其他架構(gòu)將會(huì)有很大的困難。

symcc

最近提出的符號(hào)執(zhí)行工具，SYMCC，同樣是本文作者之前的工作，基于源代碼的，不支持分析二進(jìn)制文件。SYMQEMU的靈感來自于SYMCC，所以簡(jiǎn)要概括一下他的設(shè)計(jì)。

我們?cè)谠O(shè)計(jì)SYMCC時(shí)觀察到，目前大多數(shù)符號(hào)執(zhí)行系統(tǒng)是解釋器。然而我們卻提出一個(gè)基于編譯的方法，并且展示了他能夠提升執(zhí)行性能以及系統(tǒng)實(shí)際探索能力。SYMCC在編譯器內(nèi)進(jìn)行hook，并且在target代碼內(nèi)進(jìn)行插裝，并且注入實(shí)施支持庫(kù)的調(diào)用。因此符號(hào)執(zhí)行成為了被編譯文件的一部分。并且分析代碼可以進(jìn)行優(yōu)化，并且插裝代碼并不會(huì)在每次執(zhí)行時(shí)進(jìn)行重復(fù)。

SYMCC基于編譯的方式需要編譯器，所以他只能在被測(cè)試程序源代碼可用時(shí)發(fā)揮作用。盡管如此，我們認(rèn)為這個(gè)方式是足夠有前途，所以一直尋找一種方式將其應(yīng)用到binary-only的方面之中，本文的主要工作就是說明基于編譯的符號(hào)執(zhí)行系統(tǒng)是如何在二進(jìn)制文件上高效的工作。

SYMQEMU

現(xiàn)在提出針對(duì)binry-only設(shè)計(jì)實(shí)現(xiàn)的SYMQEMU。他的靈感來自于之前的工作并結(jié)合了如今最先進(jìn)的符號(hào)執(zhí)行系統(tǒng)的技術(shù)。

design

系統(tǒng)兩個(gè)主要目標(biāo)：

1. 實(shí)現(xiàn)高效能，以致于實(shí)際軟件。
2. 合理的架構(gòu)獨(dú)立性，比如將其遷移到新的處理器架構(gòu)不需要做過多工作。

基于之前的調(diào)查，我們發(fā)現(xiàn)流行的最先進(jìn)的符號(hào)執(zhí)行系統(tǒng)實(shí)現(xiàn)了如下兩個(gè)目標(biāo)中的一個(gè)，但并非全部：angr和s2e是架構(gòu)靈活的但是性能差；QSYM在性能上比較高但是其只針對(duì)x86架構(gòu)。

如今針對(duì)架構(gòu)獨(dú)立的解決方案是將被測(cè)程序翻譯為IR，這樣如果想要支持一個(gè)新的架構(gòu)，只有翻譯器需要移植，理想情況下，我們選擇一種中間語(yǔ)言，其已經(jīng)存在支持多種架構(gòu)的相關(guān)翻譯器。以中間語(yǔ)言靈活地表示程序是一種著名的，已經(jīng)成功的應(yīng)用于許多其他領(lǐng)域的技術(shù)，比如編譯器設(shè)計(jì)以及靜態(tài)代碼分析。我們也將這種技術(shù)合并到我們的設(shè)計(jì)中來。

當(dāng)將程序翻譯為中間語(yǔ)言獲得便利的同時(shí)，我們同樣需要了解這種方式對(duì)于性能的影響：將binary-only程序靜態(tài)翻譯是具有挑戰(zhàn)性的，因?yàn)榉磪R編器可能是不可靠的，尤其是存在間接跳轉(zhuǎn)的情況下，并且在分析過程中運(yùn)行時(shí)進(jìn)行翻譯會(huì)提升功耗。我們認(rèn)為這是s2e性能劣于QSYM的主要原因。我們的目標(biāo)就是找到一種翻譯系統(tǒng)同時(shí)保持性能優(yōu)越。

首先，我們主要到s2e以及angr都收到了非重要問題的影響，并且這些問題都是可以通過工程方面的工作解決的：

1. S2E將被測(cè)試程序翻譯了兩次，然而如果符號(hào)執(zhí)行過程是在第一次中間表示上實(shí)現(xiàn)的話，第二次翻譯過程其實(shí)是可以避免的。
2. angr的性能受到python實(shí)現(xiàn)影響，將其核心代碼移植到一種更快速的語(yǔ)言中會(huì)顯著提升速度。

然而我們的貢獻(xiàn)并不僅僅是找出并且避免上述兩個(gè)問題，我們還觀測(cè)到：s2e以及angr，以及其他所有的binaty-only的符號(hào)執(zhí)行器，都解釋執(zhí)行被測(cè)試程序的中間表示，解釋是設(shè)計(jì)的核心部分。我們推測(cè)，將目標(biāo)程序編譯為插樁版本將會(huì)帶來很高的性能上的提升。雖然SYMCC是基于源代碼的，基于編譯的符合執(zhí)行引擎，但是他證明了這一點(diǎn)。

收到上述觀測(cè)到的啟發(fā)，我們的設(shè)計(jì)方法如下：

1. 在運(yùn)行態(tài)將目標(biāo)程序翻譯為IR。
2. 為符號(hào)執(zhí)行所需的IR插樁。
3. 將IR編譯為適合CPU運(yùn)行分析的機(jī)器碼并且直接執(zhí)行。

通過將插樁的目標(biāo)程序編譯為機(jī)器碼，補(bǔ)償了在第一階段將二進(jìn)制文件翻譯為中間代碼時(shí)的性能損失。CPU執(zhí)行機(jī)器碼比解釋器運(yùn)行IR速度快得多，因此我們獲得了一個(gè)可以與沒有翻譯的系統(tǒng)的性能相當(dāng)?shù)南到y(tǒng)，同時(shí)由于進(jìn)行了程序翻譯可以保持架構(gòu)的獨(dú)立性。

implementation

我們?cè)趒emu的基礎(chǔ)之上實(shí)現(xiàn)了SYMQEMU，選擇qemu的原因是因?yàn)樗且粋€(gè)魯棒性的系統(tǒng)仿真器，并且可以支持許多架構(gòu)，在他的基礎(chǔ)之上進(jìn)行實(shí)現(xiàn)，我們可以實(shí)現(xiàn)架構(gòu)獨(dú)立性。并且qemu還有另一個(gè)特點(diǎn)正好滿足我們的需求，他不僅將二進(jìn)制文件翻譯為針對(duì)處理器獨(dú)立的IR，他同時(shí)支持將中間語(yǔ)言便已成為host CPU的機(jī)器碼。qemu的主要優(yōu)點(diǎn)是他能夠?qū)⒍M(jìn)制文件翻譯為不同host架構(gòu)的機(jī)器代碼，并且可以完成全系統(tǒng)仿真，方便于之后拓展支持交叉架構(gòu)的固件分析。

具體來說，我們拓展了QEMU的組件TCG。在未被修改的qemu中，TCG負(fù)責(zé)將guest架構(gòu)的機(jī)器碼塊翻譯為架構(gòu)獨(dú)立的語(yǔ)言，叫做TCG ops，然后編譯這些TCG ops為host架構(gòu)的機(jī)器碼。由于性能原因，這些翻譯好的blocks隨后被緩存，所以翻譯在每次執(zhí)行過程中只需要進(jìn)行一次。SYMQEMU在這過程中插入了一步：當(dāng)被測(cè)程序翻譯為TCG ops時(shí)，我們不僅插樁來模擬guest CPU而且產(chǎn)生一些額外的TCG ops來建立對(duì)應(yīng)的符號(hào)約束表達(dá)式。針對(duì)建立符號(hào)表達(dá)式以及求解這些的支持庫(kù)，symqemu重用SYMCC的支持庫(kù)，即重用QSYM的。

（此處有詳細(xì)例子，感興趣去讀原文）

目前我們使用的qemu linux用戶模式的仿真，即我們只模擬了普通用戶空間的guest系統(tǒng)。系統(tǒng)調(diào)用被轉(zhuǎn)換來滿足host架構(gòu)的要求，這些是針對(duì)host的內(nèi)核來工作的，使用了qemu常規(guī)的機(jī)制。因此我們的符號(hào)執(zhí)行分析在系統(tǒng)調(diào)用處停止，與QSYM以及angr類似。與全系統(tǒng)仿真(比如s2e)來講，這樣節(jié)省了為每個(gè)target架構(gòu)準(zhǔn)備系統(tǒng)鏡像的方面，并且提升了性能，因?yàn)槭侵苯舆\(yùn)行kernel代碼而不是通過仿真。但是如果需要的話，SYMQEMU是很容易的被拓展為QEMU的全系統(tǒng)仿真。

架構(gòu) 獨(dú)立

首先要明確，執(zhí)行分析的主機(jī)的架構(gòu)叫做host，被測(cè)代碼在其架構(gòu)之上被編譯的叫做guest。尤其是在嵌入式設(shè)備分析中，host與guest架構(gòu)不同是顯然的，嵌入式設(shè)備的系統(tǒng)進(jìn)行符號(hào)執(zhí)行分析的能力不足，所以將固件放置到其他系統(tǒng)中進(jìn)行分析，SYMQEMU就是為這種情況準(zhǔn)備的，能夠在多架構(gòu)下運(yùn)行。

SYMQEMU利用qemu TCG translators，涵蓋多種處理器類型，并且我們針對(duì)其修改幾乎獨(dú)立于target架構(gòu)。

也就是說，SYMQEMU可以在相關(guān)的host架構(gòu)上運(yùn)行并且可以支持所有qemu能夠處理的guest架構(gòu)下的二進(jìn)制文件的分析。

與之前的設(shè)計(jì)比較

本節(jié)之處SYMQEMU與最先進(jìn)的符號(hào)執(zhí)行系統(tǒng)的不同之處。

與angr和s2e相似，SYMQEMU使用傳統(tǒng)的，以IR來完成符號(hào)執(zhí)行處理，顯著的降低了實(shí)現(xiàn)的復(fù)雜性。但是不同于此二者的是，他是基于編譯的符號(hào)執(zhí)行技術(shù)，顯著的提升了性能。

與QSYM比較，SYMQEMU設(shè)計(jì)最重要的優(yōu)勢(shì)是架構(gòu)靈活性的同時(shí)，能夠維持很高的執(zhí)行速度。在qemu之上進(jìn)行設(shè)計(jì)使其能夠或者很多的數(shù)量的模擬器支持的架構(gòu)處理能力。

SYMCC雖然不能夠分析二進(jìn)制代碼，但是其給SYMQEMU提供了基于編譯的思路。此二者都是通過修改其IR來在目標(biāo)程序中插入符號(hào)處理，并且都是將結(jié)果直接編譯為能夠高效運(yùn)行的機(jī)器碼。然而SYMCC是面向源代碼的，而SYMQEMU解決了分析二進(jìn)制文件的不同指令集的挑戰(zhàn)，SYMQEMU在翻譯過程中的TCG ops中插樁，SYMCC在編程過程中的LLVM bitcode內(nèi)插樁。并且SYMQEMU解決了guest和target架構(gòu)不匹配的問題。

我們認(rèn)為本文工作結(jié)合了s2e以及angr的優(yōu)勢(shì)，即多架構(gòu)支持，同時(shí)結(jié)合了symcc的優(yōu)點(diǎn)，高性能，摒棄了他們的缺點(diǎn)；并且我們找到了一種方式，能夠?qū)YMCC的核心idea應(yīng)用到二進(jìn)制文件的分析之中。

內(nèi)存管理

當(dāng)symqemu分析軟件時(shí)，他會(huì)建立很多符號(hào)公式來描述中間結(jié)果和路徑約束。他們占用的內(nèi)存會(huì)隨著時(shí)間而一直增長(zhǎng)，所以symqemu需要一種方式來清除那些不再被使用的公式。

首先我們討論一下為什么內(nèi)存管理是第一位的。IR在任何合理的程序中或?qū)Τ绦蛄饔杏绊懀蛘叱蔀樽罱K結(jié)果的一部分；在前者情況下，對(duì)應(yīng)的表達(dá)式被添加到路徑約束的集合中，并且不能被清楚；但是針對(duì)后者情況，表達(dá)式成為最終結(jié)果的描述中的字表達(dá)式。所以符號(hào)表達(dá)式是什么時(shí)候變成不重要的呢？關(guān)鍵就是程序的輸出是程序結(jié)果的一部分，但是他可能在程序的結(jié)束之前就已經(jīng)產(chǎn)生了。

所以我們應(yīng)該在符號(hào)在最后一次使用之后將其清除。QSYM使用的C++ smart points來實(shí)現(xiàn)了這個(gè)目的，但是我們?cè)诒恍薷牡膓emu中不能簡(jiǎn)單的相同的辦法：TCG是一個(gè)動(dòng)態(tài)翻譯器，由于性能因素，它不產(chǎn)生任何被翻譯代碼的拓展分析。這使得高效的確定插入清除代碼的位置非常困難。并且經(jīng)驗(yàn)告訴我們，大多數(shù)程序中包含很少的，在程序執(zhí)行過程之中無用的，相關(guān)符號(hào)數(shù)據(jù)和表達(dá)式，所以我們不想我們的清除機(jī)制造成很大的功耗。

我們使用了一種樂觀的清除機(jī)制，在一種expression garbage collector的基礎(chǔ)之上：SYMQEMU跟蹤所有從后端獲得的符號(hào)表達(dá)式，如果他們的數(shù)目非常大時(shí)進(jìn)行回收。最主要的觀測(cè)是所有l(wèi)ive表達(dá)式可以通過掃描如下發(fā)現(xiàn)

1. 模擬的CPU符號(hào)寄存器
2. 存儲(chǔ)對(duì)應(yīng)符號(hào)內(nèi)存結(jié)果的符號(hào)表達(dá)式的，內(nèi)存中的shadow regions

以上兩種，后端都是可感知的。在感知到所有l(wèi)ive表達(dá)式之后，symqemu將其與所有已經(jīng)創(chuàng)建的符號(hào)表達(dá)式進(jìn)行比較，并且釋放那些不再使用的表達(dá)式。尤其是當(dāng)一個(gè)程序在寄存器和內(nèi)存中移除了計(jì)算的結(jié)果，對(duì)應(yīng)的符號(hào)表達(dá)式同樣被認(rèn)為不再使用也被移除。我們將 expression garbage collector 和QSYM’s smart pointer based memory management相聯(lián)系，這兩種基礎(chǔ)都認(rèn)為表達(dá)式不再使用之后可以被釋放。

修改TCG ops

我們的方法要求能夠像TCG ops中插樁。然而TCG不支持在翻譯過程之中的拓展修改功能，作為一個(gè)翻譯器，他高度關(guān)注速度問題。因?yàn)椋瑢?duì)于TCG ops的程序化修改的工作很少。然而LLVM提供了豐富的API，支持compiler檢查和修改LLVM bitcode。TCG ops單純的將指令存儲(chǔ)在一個(gè)平面鏈表中，而沒有任何高層次的類似于基本快的數(shù)據(jù)結(jié)構(gòu)。并且程序流被期望與翻譯塊呈線性關(guān)系。

為了不和TCG產(chǎn)生不一致，我們的實(shí)現(xiàn)對(duì)每一個(gè)指令生成時(shí)進(jìn)行符號(hào)處理。雖然這種方法可以避免與TCG 優(yōu)化以及代碼生成器產(chǎn)生的問題，但是使得靜態(tài)優(yōu)化技術(shù)不可行，因?yàn)槲覀兠看蝺H僅關(guān)注一條指令。尤其是我們無法靜態(tài)確定給定的值是否是實(shí)際值，并且如果所有的操作都是符號(hào)值的情況下，我們也不能產(chǎn)生跳過符號(hào)計(jì)算的階段的跳轉(zhuǎn)。

因此我們最終于TCG所需要的運(yùn)行環(huán)境的限制條件達(dá)成了妥協(xié)，同時(shí)允許我們有相關(guān)很高的執(zhí)行速度：我們?cè)谥С值恼{(diào)用庫(kù)中進(jìn)行實(shí)際值性檢查，這樣，如果實(shí)際計(jì)算的輸入都是準(zhǔn)確值的話，就可以直接跳過符號(hào)值計(jì)算，但是這樣會(huì)導(dǎo)致額外的庫(kù)調(diào)用開銷。

shadow call stack

QSYM引入了上下文敏感的基本快剪枝，如果在同樣的調(diào)用堆棧環(huán)境中頻繁調(diào)用確定的計(jì)算會(huì)導(dǎo)致壓抑符號(hào)執(zhí)行(基于如下直覺，在同樣的上下文環(huán)境中重復(fù)的執(zhí)行分析并不會(huì)導(dǎo)致新的發(fā)現(xiàn))。為了實(shí)現(xiàn)這個(gè)優(yōu)化，符號(hào)執(zhí)行需要維護(hù)一個(gè)shadow call stack，記錄跟蹤call以及return指令。

在qemu基礎(chǔ)之上，我們面臨一個(gè)新的挑戰(zhàn)，TCG ops是一個(gè)非常低級(jí)別的target程序的中間表示。尤其是，call以及return指令不是被表示為單獨(dú)的指令而是被翻譯為一系列TCG ops。比如一個(gè)在x86架構(gòu)下的程序調(diào)用會(huì)生成TCG ops，其將返回地址push到模擬的stack上，調(diào)整guest的stack pointer，并且根據(jù)被調(diào)用函數(shù)來修改guest的指令。這使得僅僅通過檢測(cè)TCG ops來以一個(gè)可靠并且架構(gòu)獨(dú)立的方式來識(shí)別call以及return是不可能的。我們選擇了如下優(yōu)化來提高魯棒性：在架構(gòu)獨(dú)立的，能夠?qū)C(jī)器代碼轉(zhuǎn)換為TCG ops的qemu 代碼中，每當(dāng)遇到call和return時(shí)，我們會(huì)通知代碼生成器。缺點(diǎn)就是針對(duì)每個(gè)target架構(gòu)，類似的通知代碼都必須被插入到翻譯代碼中去，但這并不復(fù)雜。

評(píng) 價(jià)

詳見原文，主要是一些指標(biāo)與測(cè)試效果

未來工作

全系統(tǒng)仿真

SYMQEMU目前運(yùn)行符號(hào)執(zhí)行針對(duì)linux用戶態(tài)二進(jìn)制程序，之后將會(huì)對(duì)其拓展到全系統(tǒng)分析，尤其是針對(duì)嵌入式設(shè)備而言，分析此類程序要求全系統(tǒng)仿真。

我們認(rèn)為在SYMQEMU實(shí)現(xiàn)這一改進(jìn)是可能的。將target翻譯為TCG ops，對(duì)其插樁，并將其編譯為機(jī)器碼，這些基本過程不改變。需要添加的一個(gè)機(jī)制是將符號(hào)化數(shù)據(jù)引入到guest系統(tǒng)中，這是受到S2E fake-instruction技術(shù)的啟發(fā)，以及當(dāng)在guest內(nèi)存以及符號(hào)表達(dá)式之間存在映射時(shí)，shadow-memory系統(tǒng)需要記錄虛擬MMU的數(shù)量。最終將會(huì)產(chǎn)生一個(gè)不僅可以對(duì)用戶態(tài)程序進(jìn)行測(cè)試，同樣可以對(duì)內(nèi)核代碼進(jìn)行測(cè)試的系統(tǒng)，并且其同樣可分析非linux系統(tǒng)的代碼以及裸固件等。

caching across executions

混合fuzzing技術(shù)的特點(diǎn)之一是能夠?qū)ν怀绦蜻M(jìn)行大量的連續(xù)執(zhí)行。作為動(dòng)態(tài)翻譯器，SYMQEMU在運(yùn)行態(tài)按需翻譯target程序。并且翻譯的結(jié)果在單個(gè)運(yùn)行的過程之中被緩存，但是當(dāng)目標(biāo)程序執(zhí)行終止時(shí)這些緩存結(jié)果會(huì)被丟棄。我們猜想，可以通過緩存多個(gè)執(zhí)行過程中的翻譯結(jié)果，可以顯著提升結(jié)合SYMQEMU的混合FUZZ的性能。主要的挑戰(zhàn)就是需要確定目標(biāo)是確定性加載的，以及針對(duì)自我修改代碼需要進(jìn)行特殊處理。所以，這些潛在的優(yōu)化性能提升主要在于被測(cè)程序的特點(diǎn)。

symbolic QEMU helpers

QEMU利用TCG ops表示機(jī)器碼，然而一些target的指令難以用TCG ops來進(jìn)行表示，尤其是在CISC架構(gòu)之上。針對(duì)這情況，QEMU使用helpers:可以被TCG調(diào)用的內(nèi)置變異函數(shù)，仿真target架構(gòu)的每一個(gè)復(fù)雜指令。由于helpers工作在常規(guī)的TCG架構(gòu)之外，SYMQEMU在TCG層級(jí)的插樁不能插入符號(hào)處理到他們之中。這樣的結(jié)果是implicit concretization，在分析使用大量目標(biāo)的指令時(shí)會(huì)產(chǎn)生精讀損失。

我們有如下兩種實(shí)現(xiàn)qemu helpers符號(hào)處理的方式：

1. 第一種方式是為每一個(gè)要求的helper手動(dòng)添加符號(hào)等價(jià)式，更像在一些符號(hào)執(zhí)行引擎中使用的常用libc功能的函數(shù)總結(jié)。這個(gè)方式非常容易實(shí)現(xiàn)，但是不方便應(yīng)用于大數(shù)量的helpers中。
2. 另一種方式是自動(dòng)化的實(shí)現(xiàn)helpers的符號(hào)化版本。為了實(shí)現(xiàn)這個(gè)目的，SYMCC可以被用來編譯符號(hào)化追蹤到helpers中，他的源代碼作為QEMU的一部分是公開的。最終得到的二進(jìn)制文件是和SYMQEMU兼容的，因?yàn)镾YMCC的使用相同的符號(hào)推理的后端。S2E也是使用類似的方式編譯helpers到KLEE中的解釋器中的LLVM bitcode。

相關(guān)工作

binary-only符號(hào)執(zhí)行

Mayhem是一個(gè)高性能的基于解釋器的符號(hào)執(zhí)行系統(tǒng)，贏得過DAPRA CGC比賽，然而由于其不開源無法比較性能。Triton是可以以兩種方式運(yùn)行的符號(hào)執(zhí)行系統(tǒng)，一種使用二進(jìn)制文件轉(zhuǎn)換，類似于QSYM，一種使用CPU仿真，類似于S2E以及angr。Eclipser覆蓋了介于fuzzing和符號(hào)執(zhí)行之間的一些中間區(qū)域，他認(rèn)為在分支條件和輸入數(shù)據(jù)之間存在線性關(guān)系。這種約束的簡(jiǎn)化提升了系統(tǒng)的性能，然而他卻不能發(fā)現(xiàn)常規(guī)符號(hào)執(zhí)行系統(tǒng)可以發(fā)現(xiàn)的那些路徑。Redqueen利用一種啟發(fā)式的方法尋找路徑條件和輸入之間的關(guān)系。SYMQEMU相比較來說實(shí)現(xiàn)了全系統(tǒng)仿真。

運(yùn)行態(tài)bug檢測(cè)

混合fuzzing依靠fuzzer以及sanitizers來檢測(cè)bugs。Address sanitizer是一種流行的用來檢測(cè)確定內(nèi)存錯(cuò)誤的sanitizer。由于其需要源代碼來產(chǎn)生插樁程序， Fioraldi et al設(shè)計(jì)了QASan，基于qemu的系統(tǒng)來對(duì)二進(jìn)制文件實(shí)現(xiàn)類似的檢測(cè)。有大量的需要源代碼的sanitizers。我們推測(cè)通過QASan的思路，可以將大量上述sanitizers用于二進(jìn)制文件分析。

混合fuzzing

Driller是基于angr的混合fuzzer，其設(shè)計(jì)理念類似于QSYM，但是有其angr的python實(shí)現(xiàn)以及基于解釋器的方式，其執(zhí)行速度較低。與QSYM以及SYMQEMU比較，它使用了一種更加精細(xì)的策略來融合fuzzer以及符號(hào)引擎：他監(jiān)控fuzzer的進(jìn)展情況，并且當(dāng)其似乎遇到自身無法解決的障礙時(shí)，會(huì)自動(dòng)切換到符號(hào)執(zhí)行。類似的，最近提出的Pangolin通過不僅提供fuzzer測(cè)試用例，以及一些抽象的符號(hào)約束，還有快速樣本生成方法，強(qiáng)調(diào)了fuzzer結(jié)合符號(hào)執(zhí)行的優(yōu)勢(shì)；利用這些，fuzzer能夠生成可以有很大概率解決由符號(hào)執(zhí)行生成的路徑約束的輸入。

我們認(rèn)為更加精細(xì)的符號(hào)執(zhí)行和fuzzer的組合可以很大程度上提升混合fuzzing的性能

總 結(jié)

我們提出了SYMQEMU，一種基于編譯的，針對(duì)二進(jìn)制文件的符號(hào)執(zhí)行引擎。我們的評(píng)價(jià)展示了SYMQEMU性能優(yōu)于最先進(jìn)的符號(hào)執(zhí)行引擎并且可以在某些方面與基于源代碼的符號(hào)執(zhí)行技術(shù)相匹配。而且SYMQEMU非常方便的向其他架構(gòu)進(jìn)行遷移，只需要幾行代碼即可。