模糊測試中的靜態插樁技術

王明哲 姜宇 孫家廣

（清華大學軟件學院 北京 100084）

大量系統軟件側重于性能，往往使用C/C++等具有底層控制能力的程序設計語言編寫.然而，這些程序設計語言若存在不規范的使用，會產生數組越界、數據競爭等不安全行為，導致軟件缺陷.部分缺陷會進而引發安全問題，產生任意代碼執行等重大安全影響.因此，有必要識別和修復這些缺陷.

模糊測試是一種自動化的軟件缺陷發現方法.不同于傳統軟件測試依靠人編寫測試用例，模糊測試自動生成輸入并以此執行程序.測試工具在程序運行時監控崩潰或超時等異常行為，從而發現異常行為背后的軟件缺陷.由于構造的輸入內容具有高度的隨機性，能夠觸發開發人員難以想象的邊界條件，這些條件包含了大量容易觸發異常的場景.此外，自動的輸入生成允許模糊測試進行動輒數千萬次的測試，廣泛探索程序的狀態空間.

在實際的模糊測試實踐中，使用靜態插樁技術作為輔助已成為事實上的標準.靜態插樁技術包含2個階段；1）在源程序編譯的過程中，編譯器在程序的關鍵位點插入額外的邏輯（即樁點）；2）在程序運行時樁點被觸發，從而收集執行的動態信息或改變程序的行為.在模糊測試的場景下，靜態插樁技術主要用于安全特性強化和導向信息收集.該技術能夠顯著提升軟件缺陷的發現能力，加快程序狀態空間的探索速度.

安全特性強化插樁旨在提升軟件缺陷的發現能力.模糊測試檢測軟件缺陷的方法主要依賴程序崩潰等操作系統的信號機制.然而，程序中出現的不安全行為僅有少部分會觸發硬件異常（例如內存保護、除零錯誤）且被操作系統捕獲.大部分類型的缺陷，例如絕大多數的單字節緩沖區溢出和有符號數的算術溢出，均不會觸發硬件的保護機制.為了解決這些問題，靜態插樁在潛在的風險位點進行額外的安全檢查，從而在發生問題時通知模糊測試工具.

導向信息收集插樁旨在加快程序狀態空間的探索速度.模糊測試生成的輸入是隨機的，因此存在難以有效探索程序的狀態空間的問題，且該問題在輸入高度結構化的程序和具有大量邏輯的復雜系統上尤為顯著.為了解決此問題，有必要引入導向信息，使得模糊測試工具側重于探索具有更高價值的程序狀態，同時高效求解復雜約束.例如，動態測試技術發現軟件缺陷的前提是觸發缺陷所在的代碼，所以，可以引入代碼覆蓋，從而將模糊測試導向尚未觸發的代碼位點.

此外，靜態插樁引入了額外的邏輯.在提升模糊測試效果的同時，靜態插樁也不可避免地降低了程序的執行速度，從而影響了模糊測試的整體吞吐量.一般地，插樁的能力越強，樁點數量越多，邏輯越復雜，帶來的額外開銷越大.由于模糊測試的整體效果依賴于海量執行對程序狀態空間的探索，在模糊測試中使用靜態插樁時，應合理取舍插樁能力和測試吞吐量.

目前，靜態插樁研究主要有2 類，一是提出了新的插樁特性，二是降低了已有方法的額外開銷.這些工作盡管十分有效，但都局限于單一的插樁策略，缺乏對功能和性能的系統性分析和梳理.為此，本文面向模糊測試場景下靜態插樁技術，從功能和性能2方面入手，系統性分析了典型的插樁技術，測量了它們的額外開銷，并由此展望了插樁技術的發展趨勢.

本文的主要貢獻有3 方面：

1）系統性地分析了靜態插樁技術.對于安全特性強化插樁，本文從程序語言規范的角度說明了缺陷的根源，并詳細分析了檢測技術的核心思想.對于導向信息收集插樁，本文總結了編譯期的樁點部署策略，以及運行時對導向信息的利用策略.

2）測量了插樁的額外開銷.本文選取了有代表性的靜態插樁方案，使用典型的模糊測試項目統計了這些插樁方案的額外開銷.其中，選取的插樁方案涵蓋了控制流特征采集、比較操作數收集、安全特性強化3 個最常見的插樁需求.

3）分析了靜態插樁技術的優勢、局限和優化方向.基于分析和測量，本文結合學術界的最新工作，討論了模糊測試場景下靜態插樁技術的優化方向.

1 研究背景

1.1 模糊測試

模糊測試起源于20 世紀90 年代，其最初目的是測試UNIX 實用程序[1].在此工作中，模糊測試工具Fuzz 生成隨機輸入，接著將輸入通過標準輸入傳遞給目標程序，或通過終端仿真程序ptygig 傳遞給交互式的目標程序，與此同時，測試工具等待程序的異常信號，生成輸入、執行、等待異常的過程被腳本不斷重復，從而發現軟件缺陷.上述過程中，測試工具無需侵入目標程序，因此被稱為黑盒模糊測試.

2008 年Godefroid 等人[2]提出了白盒模糊測試.之所以被稱為白盒模糊測試是因為測試工具深入觀察目標程序內部，從而系統性地探索程序的狀態空間.具體地，模糊測試工具SAGE 使用符號執行技術，首先收集程序執行路徑上的約束，接著對約束逐個取反并使用求解器生成新的輸入，從而探索不同的分支.包括SAGE 在內的大量白盒測試工作盡管對程序有系統性的探索，但受制于約束收集和求解的性能，其發現軟件缺陷的效果依然十分有限.

2014 年提出的AFL 是首個灰盒模糊測試工具[3].不同于高開銷的白盒測試，灰盒模糊測試工具AFL使用輕量級插樁技術，統計程序的控制流特征并以此作為導向信息.具體地，程序執行軌跡的時空特征被映射到一個64KiB 的位圖上.通過分析位圖背后隱含的控制流特征，模糊測試工具能夠識別出尚未發現的全新程序行為，從而繼續深入探索.基于導向信息的灰盒模糊測試十分成功，發現了大量的軟件缺陷和安全漏洞.因此，灰盒模糊測試獲得了包括谷歌[4]、微軟[5]、Adobe[6]在內的工業界的廣泛應用.

1.2 靜態插樁和模糊測試

在實際的模糊測試實踐中，靜態插樁已成為事實上的標準[7].例如，OSS-Fuzz[4]是谷歌發起的模糊測試持續集成服務，囊括了大量被廣泛使用的基礎軟件項目.其中，全部的測試項目都使用了至少一種靜態插樁技術.具體地，表1 顯示了OSS-Fuzz 項目中啟用模糊測試的771 個測試項目中靜態插樁的使用情況.

Table 1 Usage Statistics of Static Instrumentation in OSSFuzz表1 OSS-Fuzz 項目的靜態插樁使用統計

觀察表1 可以發現，當下模糊測試的靜態插樁主要可以分為2 個類型.1）在導向信息收集方面，代碼覆蓋是模糊測試工具關注的核心信息.除此之外，一半多的項目也關注對比較等約束的測試效率，使用了操作數收集等方法處理.2）在安全特性強化的方面，全部的項目無一例外使用了Address Sanitizer 進行內存安全檢查.大多數項目都檢查了未定義行為，也有小部分項目檢查了未初始化內存的訪問.只有3個項目檢查了線程安全問題，這主要是因為OSSFuzz 測試的軟件多為基礎庫，其線程安全多由庫的使用者維護.

1.3 插樁的基本類型

根據插樁的不同時機，插樁主要分為運行時進行的動態插樁和運行前完成的靜態插樁.動態插樁在程序運行中進行，一般對內存中的機器碼進行補丁；靜態插樁在程序運行前進行，將原始程序插樁并生成修改后的二進制文件用于后期執行.

根據插樁能力的不同，動態插樁一般分為輕量級插樁和重量級插樁2 種類型.輕量級插樁具有較低的復雜度和執行開銷.例如，LLVM[11]中的XRay在程序開頭注入額外的空指令.在執行時，插樁邏輯可以將空指令替換為跳轉指令，從而重定向函數的控制流并執行額外的插樁邏輯，若樁點不再需要，則可以將跳轉指令回退為空指令.然而，輕量級插樁局限于對單個指令的補丁，無法提供強大的分析能力，也無法對程序邏輯進行復雜的修改.因此，在要求更強的插樁能力時，人們往往使用重量級插樁.例如，DynInst[12]對二進制程序進行復雜而全面的分析，將其抽象成從模塊、函數到基本塊和指令的完整體系.在程序運行時可以靈活地對體系內的對象進行高層次分析和修改，實現內存安全檢查等復雜的插樁需求.

由于動態插樁的對象一般是機器碼，其蘊含的語義信息遠少于源碼和編譯器內部表示，因此難以滿足模糊測試的需求.例如，內存安全檢查工具為了檢測棧上的緩沖區越界，需要獲得棧上各個對象的內存布局.然而，上述信息在源碼遞降到機器碼的過程中已經消失了.此外，在機器碼上進行直接補丁的性能也弱于包含復雜優化的編譯器，一般會帶來高達數十倍的額外開銷[13]，大大降低了模糊測試的吞吐量.因此，當下的模糊測試一般使用基于編譯器的靜態插樁.

基于編譯器的靜態插樁一般以程序的源碼或編譯器內部的中間表示作為輸入.以編譯器Clang 為例：源碼首先被Clang 前端變換為LLVM 中間表示，該中間表示經由LLVM 中端，完成清理、歸一化和優化；接著被LLVM 的指令選擇組件變換為機器中間表示，機器中間表示被LLVM 后端進一步完成平臺相關的優化和遞降；最后AsmPrinter 組件將該中間表示由MC 層生成ELF 等平臺相關的對象文件.在此過程中的各個環節都可以插樁.例如，可以在Clang 前端結合源碼的語義信息，對程序設計語言內部的未定義行為進行捕獲和檢測；可以在LLVM 中端匹配和內存安全相關的指令（例如內存讀寫）并插入檢測器，從而實現通用的內存安全強化.

2 安全特性強化插樁

2.1 內存安全檢查

手動內存管理是系統程序設計中極其容易出錯的環節.在系統程序中，對內存的申請、使用和釋放操作均可能帶來內存安全問題.本節列舉3 個經典的內存安全問題.

1）內存申請.若申請的內存大小受攻擊者直接控制，攻擊者可以構造畸形的內存申請請求，從而使程序耗盡資源.

2）內存使用.若訪問偏移量超過了內存對象的大小，則會造成經典的緩沖區溢出問題.攻擊者可以依此泄漏程序中的數據，或覆蓋棧幀所保存的函數返回地址，造成任意代碼執行.

3）內存釋放.若釋放過早（或稱為釋放后使用，use-after-free）或釋放了非malloc 返回的對象，則可能使多個內存對象重疊，使得攻擊者任意控制內存對象的值.若忘記釋放，則會造成內存泄漏，攻擊者可以耗盡程序資源造成拒絕服務攻擊.

這3 個安全問題時常不能造成程序崩潰，因此不能被模糊測試工具所發現.不能有效檢測內存安全的另一個重要的原因是硬件的局限.例如，x86 的微處理器中，內存管理單元支持的最小粒度為4KiB.若越界的地址恰好在當前頁內，則無法觸發硬件內存保護.此外，由于系統軟件注重執行效率，內存分配策略也主要側重于降低開銷而非增強安全性.例如，現代微處理器的指令集架構一般要求內存對齊，否則會造成訪問下降或硬件異常.舉一個簡單的例子：在AArch64 下，只能以8B 的整數倍的地址訪問64b整數.在構造棧布局時，編譯器需要將變量對齊到合適的地址，對象間會留下空隙.若非法訪問的地址恰好在2 個對象間的空隙內，則極難發現緩沖區越界的問題.

為了增強內存安全檢查的有效性，引入靜態插樁是一個可行的方案.從本質上講，靜態插樁實現了類似于微處理器內存管理單元的功能，但該功能基于軟件實現，在犧牲性能的情況下帶來了更強的檢測能力.一方面，靜態插樁技術允許監控程序中的每一次內存讀寫操作，從而檢查非法的內存使用；另一方面，靜態插樁可以替換程序的運行時庫，從而檢查對系統庫中的內存申請和釋放函數的調用.類似于內存管理單元，靜態插樁也需要維護內存對象的元信息.下面以Address Sanitizer[8]為例，詳細說明靜態插樁是如何實現內存安全檢查的.

為了高效地管理內存對象的元信息，Address Sanitizer 使用影子內存技術.換言之，任何地址的元信息都會被Address Sanitizer 映射到一個保留的區間.具體地，地址Addr 的元信息存儲地址ShadowAddr為Addr/kScale+kOffset.其中kScale和kOffset均 為平臺相關的常數：kOffset為影子內存的起始地址，在x86平臺下kOffset值取0x20 000000；kScale為壓縮率（即幾個字節的空間共享同一個字節的元信息），例如在x86 平臺下kScale值取8.壓縮率越高，存儲元信息所需的額外內存越少，但驗證內存訪問合法性的算法復雜度也可能上升.

影子內存中的每個字節有[?128,127）的取值范圍.以x86 平臺為例，影子內存中的每個字節負責記錄8B 的程序內存的元信息.對于每個影子內存中的字節，0 表示當前影子內存所對應的8B 均可訪問；負數表示當前影子內存所對應的8B 均不可訪問；[1,8）表示當前影子內存所對應的內存區間的有效長度，例如3 表示前3B 均可訪問.精心設計的內存布局和元信息儲存方式大大簡化了檢查代碼.假設當前內存訪問滿足內存對齊的要求，容易得出內存安全檢查樁點邏輯.檢查邏輯極其簡單，只涉及少量位運算（由除法運算化簡得到）和算術運算、單次內存讀取、單次比較和分支運算.下面的代碼顯示了安全檢查樁點的具體邏輯.

上述代碼只是利用影子內存中的元信息進行安全檢查，但元信息自身還需要維護.Address Sanitizer的基本維護策略是使用禁區和隔離區.在每個內存對象前后，Address Sanitizer 添加禁區并將其標記為不可訪問，從而使數組越界等空間異常被檢查到.在堆中的內存對象被釋放后，Address Sanitizer 將對象加入隔離區，延緩對該地址的重用，從而提升釋放后使用等時間異常被檢測到的概率.為了使禁區和隔離區能夠匹配當前的內存狀態，Address Sanitizer 對內存對象的申請和釋放進行插樁：

1）棧對象.對于當前棧幀中存儲的自動變量等類型的內存對象，Address Sanitizer 修改了內存布局從而在對象間插入禁區；此外，還在函數的入口將禁區標記為不可訪問，在函數退出時刪除這些標記防止誤報.

2）堆對象.Address Sanitizer 將malloc和free等內存管理函數重新實現，從而在對象間插入禁區，在內存釋放后置入隔離區.同時，內存申請的上下文也被記錄，用于生成開發者友好的錯誤報告.

3）靜態對象.對于全局變量、靜態變量等類型的靜態對象，編譯器將這些數據寫入到二進制文件中.程序運行時，操作系統的動態鏈接器在程序運行前將這些數據映射回內存，對象的生命周期是整個進程.除了在對象間插入禁區外，為了維護靜態對象的元信息，Address Sanitizer 使用構造函數完成對禁區的標記.具體地，Address Sanitizer 在編譯期掃描全局變量，并將它們的源碼位置、長度等信息寫入到二進制的一個數組中.同時，Address Sanitizer 生成構造函數asan.module_ctor.該函數被標記為構造函數，在主程序運行前獲得控制權.函數將元信息傳遞給運行時庫所暴露的接口__asan_register_globals，從而注冊全局變量.

此 外，Address Sanitizer 還截獲 了memcpy、fread等系統庫函數，從而對常用的外部函數進行內存訪問建模和檢查.

2.2 未定義行為檢查

ISO C11 標準中寫到，“在使用不可移植的、錯誤的程序結構或錯誤的數據時，本國際標準對其沒有規定要求”[14].例如，有符號數算術運算時發生的溢出就屬于未定義行為，內存安全問題也是未定義行為的子集.引入未定義行為，不光能簡化編譯器設計實現，還能帶來額外的優化空間.

1）簡化編譯器設計實現.例如，在循環等性能攸關的場景下，編譯器往往需要分析2 個指針是否可能指向相同的內存對象.根據語言規范，float 指針和int 指針不能指向同一處內存（即不存在別名），否則為未定義行為.基于此規范，編譯器能夠通過類型信息，在部分場景下直接確認不同指針不會互為別名，從而簡化編譯器的設計.

2）帶來額外的優化空間.例如，有符號數的算術運算在主流平臺下均以2 的補碼形式進行.因此，若不發生溢出，a+1 >a在任何情況下均成立；若規定有符號數的算術運算溢出是未定義行為，編譯器可以不考慮罕見的極端情況，從而將a+1 >a折疊成常量true.

為了檢查未定義行為，可以引入靜態插樁.C/C++程序設計語言規范中規定了大量的未定義行為，例如C11 標準的附錄J 中就列出了近200 條未定義行為.相比于只須處理內存相關原語的內存安全檢查Address Sanitizer，更廣義 的未定 義行為檢查Undefined Behavior Sanitizer 需要緊 密結合 程序語 義.因 此，Address Sanitizer 只須作為LLVM 中 端的一部分，而Undefined Behavior Sanitizer 需要在更靠近源碼的編譯器前端Clang 中進行.具體地，源碼在Clang 的詞法分析、語法分析和語義檢查后，被變換為合法的抽象語法樹；Clang 的代碼生成（CodeGen）組件掃描語法樹，在生成程序LLVM 中間表示的同時，根據插樁選項生成額外的未定義行為檢查代碼.為此，Undefined Behavior Sanitizer 需要緊密結合程序語義，并進行大量的適配.

下面的代碼列出了返回有符號整數x+y的值的函數foo以及安全強化版本foo_ubsan的LLVM 中間表示.該代碼進行了少量編輯，從而刪除無關細節.不難發現，Clang 在代碼生成時，foo函數的加法指令是add nsw，其中nsw 表示不存在有符號計算的溢出（no signed wrap）.而foo_ubsan函數使用了LLVM 的內部函數llvm.sadd.with.overflow.該函數返回2 個值，一個是加法的結果i32，另一個是布爾值i1，它表示是否存在溢出.若發生溢出，則跳轉到函數handler.add_overflow.該函數調用運行時庫的接口__ubsan_handle_add_overflow報告錯誤，接著跳轉到cont 恢復執行.

3 導向信息收集插樁

3.1 控制流特征采集

當下幾乎所有的主流模糊測試工具均采用控制流特征作為導向信息.其中，覆蓋位圖是最常使用的控制流特征.覆蓋位圖的核心思想是壓縮程序執行的時空特征到固定大小的計數器數組.首先，數組的不同元素表示不同的控制流轉移，整體上反映了整體控制流轉移的空間特征.例如，對于最簡單的基本塊覆蓋而言，可以將每一個基本塊都分配獨立的計數器并連續存放，構成數組.其次，數組內元素的值和當前控制流轉移的觸發次數相關，反映了單個控制流轉移的時間特征.例如，假設每個基本塊計數器的取值范圍在0～255 之間，那么可以將計數器的值分為8 類：1,2,3,[4,8),[8,16),[16,32),[32,128),[128,256).在分類下，每個計數器均映射到8 個特征.在某次執行中，若模糊測試工具發現了先前從未發現過的特征，則認為當前執行的輸入較為新穎，需要保存以供后續探索；否則，認為當前執行沒有意義，可以直接丟棄.

下面的代碼總結了模糊測試工具AFL[3]的覆蓋率處理算法.函數checkCoverage接受數組長度N、覆蓋位圖C和未知覆蓋位圖U.checkCoverage的第1 個循環利用預先編制的查找表TO_BITMAP，將每個計數器的值映射到8 個不同的特征中，并以位圖的形式存放.換言之，當計數器為零時，轉換后的位圖也為0，說明沒有任何特征；當計數器為非零時，轉換后的位圖的8 位中有且只有一個位被置為1，置位的位置取決于分類結果.checkCoverage的第2 個循環掃描當前覆蓋和全局的未知覆蓋位圖.若當前覆蓋的特征在全局的未知覆蓋特征中出現，說明當前執行是有價值的，需要判斷執行的價值等級.若當前計數器是首次發現（即未知覆蓋全部被置位），說明當前執行發現了新覆蓋，將返回值設置為2；否則，說明當前執行發現了已經覆蓋計數器的不同計數模式，將返回值設置為1，表示發現了新路徑.

為了收集覆蓋位圖，模糊測試工具往往使用靜態插樁.下面以x86-64 平臺下的afl-gcc 為例，說明覆蓋率的收集方式.在構建待測程序時，afl-gcc 包裹了系統編譯器gcc，從而執行額外的操作.若當前gcc 調用的目標是編譯源文件，afl-gcc 編輯對系統編譯器gcc 的調用參數，使得gcc 在生成對象文件時使用afl-as作為匯編器.afl-as 是帶有插樁功能的匯編器，它接受gcc 生成的匯編文件進行插樁，之后交給系統匯編器as 生成對象文件.afl-as 對匯編文件進行模式匹配，識別基本塊的起始標簽，并插入樁點代碼.修改后的匯編文件調用系統的原始匯編器as 生成對象文件.樁點代碼的主要邏輯是創建棧幀，備份寄存器，接著跳轉到__afl_maybe_log函數中.其中，COMPILE_RANDOM是afl-as 生成的隨機數，被用作當前基本塊的標號.具體的樁點匯編代碼為：

核心函數__afl_maybe_log完全由匯編寫成，在此給出它的偽代碼以便讀者理解.__afl_maybe_log首先備份上下文save_flags，然后判斷存儲于共享內存的覆蓋位圖是否完成初始化.若是首次執行樁點，沒有完成覆蓋位圖的初始化，則嘗試使用shmat 函數加載模糊測試工具所分享的共享內存；接著是核心的控制流到位圖的映射環節，該環節計算了當前控制流所對應的計數器索引index，并維護了上一基本塊標號__afl_prev_loc；最后__afl_prev_loc在退出前恢復了保存的上下文.不難發現，該映射本質上將上一基本塊標號prev和當前基本塊標號curr映射到 (prev>>1) ^curr的計數器上，抽象了控制流的空間特征.對時空特征進行抽象的代碼如下：

3.2 比較操作數收集

僅收集控制流特征不能高效地探索程序的狀態空間.這是因為控制流特征只能反饋是否通過了某個復雜約束，卻不能輔助對復雜約束的求解.以顏色管理庫項目LCMS 為例，其輸入是國際色彩聯盟提出的ICC 描述文件，該文件以ASCII 字符串acsp 作為開頭.LCMS 在執行之始就驗證輸入文件是否為有效的ICC 描述文件，且代碼為：

#definecmsMagicNumber0x61637370//'acsp'

代碼讀入輸入的前4 個字節到Header.magic中，并轉換到大端序，判斷轉換后的值是否和cmsMagic-Number相等，若不相同則調用cmsSignalError函數報錯.顯然，測試程序實際邏輯的前提是構造有效的文件頭.然而，若只收集程序控制流特征，則幾乎不可能構造有效的文件頭.這是因為程序的控制流特征只能反饋該約束是否通過，不能在約束尚未解決前提供任何的導向信息.在缺乏導向信息的情況下，模糊測試工具只能隨機地生成輸入，而恰好能構造原始輸入的概率低至2?32.因此，對復雜約束進行求解來提供導向信息對模糊測試意義重大.

整數比較是程序的一類主要復雜約束.除了LCMS的例子中if-else 的例子外，整數比較還包括switch-case語句.以Clang 內置的SanitizerCoverage 為例，Sanitizer-Coverage 首先掃描程序中的所有指令，若發現表示整數比較的icmp 指令，則執行控制流分析，從而跳過執行頻次高且無意義的循環控制條件；接著判斷比較操作數的長度是否為常量，以此選擇合適的回調函數，并最終創建對回調函數的調用.若發現表示分支選擇的switch 指令，則為其創建常量數組，從而存儲數據類型、選擇數量等元信息以及case 中的值；最后該常量數組和當前switch 值會被作為參數調用回調函數.

下面的代碼列出了典型的回調函數原型.trace_cmp1是對兩端是變量的單字節比較的回調.trace_const_cmp4 是對一端是常量的4B 比較的回調，其中參數const是常量，variable是變量.trace_swith是對switch 的回調，其中參數val 是轉換為uint64_t 的條件變量，參數cases指向元信息.通過實現下列函數，模糊測試工具可以收集并利用執行過程中的比較信息.

除整數比較外，緩沖區比較也是程序中的一類主要約束.這些比較大多由C 標準庫提供，例如strcmp等字符串比較函數，或memcmp等緩沖區比較函數.此外，C++標準庫的部分函數，例如GNU libstdc++內部的std::__cxx11::basic_string::compare 也可能被STL 頭文件所引用.對于此類函數靜態插樁的常用方法是使用鏈接器特性.例如在Linux 下，系統的C 運行時庫將memcmp等函數標記為弱符號，從而允許用戶重載并優化memcmp等函數.基于上述機制，libFuzzer 重新定義了需要插樁的緩沖區比較函數.在鏈接時，重定義的強符號比系統的C 運行時庫有更高的優先級，因而能替換原程序對系統庫函數的調用.除了截獲比較函數，模糊測試工具在運行時也需要調用被截獲函數自身.為了獲取原始符號，libFuzzer 在運行時通過系統的動態鏈接器提供的dlsym和dlvsym函數，動態獲取原始函數的指針.

基于對整數和緩沖區比較的插樁，模糊測試能夠追蹤到控制流變化外的比較操作數，從而輔助對復雜約束的求解.例如，libFuzzer 通過2 種方式利用比較操作數，從而提升模糊測試效果.

1）自動字典構造.對于長度為4B 和8B 的整數比較和長度為2B 及以上的緩沖區比較，libFuzzer 將比較的操作數加入字典中.在生成隨機輸入時，可以根據字典中的記錄項直接替換部分原始輸入，或在原始輸入中插入部分字典記錄項.這種策略對于簡易的常量比較有非常好的求解效果.

2）比較特征提取.當開啟值特征采集功能時，libFuzzer 將比較操作轉化為特征位圖，從而使先前應用于控制流特征的導向算法能夠應用于比較中.具體地，libFuzzer 首先度量比較操作數間的距離：對于整形比較，計算兩數的海明距離和數值差異；對于緩沖區比較，則計算2 個緩沖區前綴的海明距離.接著，libFuzzer 計算操作數距離和比較操作的機器碼地址的哈希，該哈希值被對應到特征位圖中的某個位.libFuzzer 將該位置設為1，從而使執行完畢后的位圖分析邏輯能夠檢測到比較后的變化，并最終保留具有新穎比較特征的輸入文件用于后續探索.

4 靜態插樁的額外開銷

在模糊測試的實踐中，靜態插樁的能力會受到實際因素的制約.首先，不同的插樁類型可能會互相沖突.例如，Address Sanitizer 和Memory Sanitizer 同時使用影子內存技術管理內存對象的元信息，由于內存布局不能互相兼容，二者不能同時打開.此問題較容易規避，例如，可以使用強化了不同安全特性的二進制執行相同的輸入.此外，更重要的是，靜態插樁后的程序執行變慢，其額外開銷嚴重影響了模糊測試效果.當下的主流模糊測試技術無一例外地使用隨機輸入生成的策略.因此，對程序狀態空間的探索離不開海量的輸入執行.然而，越是復雜的插樁特性往往需要引入更多的樁點，且每個樁點需要執行更多的邏輯.重量級插樁會顯著降低程序執行速度，降低模糊測試的整體吞吐量，進而影響整體測試效果.由于額外開銷是由樁點的額外邏輯帶來的，本身是不可避免的.為了指導模糊測試實踐中的靜態插樁選擇，本文測量了不同類型插樁、相同類型插樁下實現的額外開銷.

實驗中待測項目全部選取自FuzzBench[15].Fuzz-Bench 是谷歌發起的模糊測試工具評測平臺，平臺中包含了大量被廣泛使用的開源軟件.這些開源軟件有著截然不同的功能，且均為應用模糊測試的實際項目，因此具有高度的代表性.除非插樁方式有特殊要求，本文使用完全相同的編譯器版本Clang 14.0.6和編譯器優化參數O2 構造二進制，從而保證相同的測試基線.

實驗的測量方法是在相同測試集的重復實驗.由于模糊測試具有隨機性，生成的輸入文件也不完全一致，因此直接測量模糊測試的執行次數會受到隨機性的影響.為了控制變量，對于每個項目，本文均選取某次模糊測試中保存的輸入文件作為測試集；對于每個插樁方式，本文使用Linux 社區的perf tools工具集，用于精確的性能分析和測量.測量環境的微處理器為AMD EPYC 7742，內存為256 GB，內核版本為Linux 5.4.

實驗的測量結果使用未插樁的原始二進制進行標準化.對于各個插樁方式的測量值，本文呈現其測量讀數除以原始二進制的測量值的標準化結果，從而排除不同項目的差異.例如，當測量執行時間時，1.0 表示執行時間和原始二進制相同，數值越高，表示插樁的額外開銷越大.

4.1 整體評估

圖1 呈現了不同插樁方法下各個插樁程序的執行時間分布.數據經過歸一化處理，其中橫線表示原始程序的執行時間，即100%.為了提升表述的簡明性，圖1 中 將Sanitizer Coverage 簡稱為SanCov.由 于Sanitizer Coverage 具有不同的子功能，在此將一般模糊測試中使用的開啟全部功能的版本稱為SanCov-All；為了對比純控制流信息下的不同采集方式，將Sanitizer Coverage 中只收集控制流信息的版本稱為SanCov-Edge，從而和4.2 節的方法一致.此外，對于安全特性強化的插樁模式，將Address Sanitizer 簡稱為ASan，將Memory Sanitizer 簡稱為MSan，將Undefined Behavior Sanitizer 簡稱為UBSan.

從圖1 中可以看出，各個插樁模式對程序執行速度均有顯著的影響.其中，影響最小的是SanCov-Edge，平均會帶來26%的額外執行時間；影響最大的是SanCov-All，Sancov-All 包含了邊覆蓋率、比較操作數收集等豐富功能；此外，ASan 也會帶來146%～230%的額外執行時間.

由于圖1 呈現的是不同項目的執行時間分布，還可以發現其更為宏觀的特征.其中，SanCov-All 和UBSan 的執行時間差別較大，標準差分別為171%和213%.例如，SanCov-All 會帶來10%～577%的額外執行時間；UBSan 也會帶來8%～803%的額外執行時間.需要說明的是，圖1 中的分布是使用核密度估計方法得到的宏觀趨勢，出現小于100%的值屬于正常現象.

Fig.1 Execution duration distribution of instrumented programs圖1 插樁程序的執行時間分布

4.2 導向信息收集的額外開銷

本文將測試工具AFL 內置的導向信息收集插樁模式進行單獨比較.通過將 AFL 作為唯一的模糊測試工具，能夠避免不同測試工具所需的不同信息和不同信息的處理方式帶來的影響.AFL 自身提供了afl-clang 和afl-fast 插樁工具.對于afl-fast 模式，由于兼容性問題，本文修改了插樁引擎代碼，使其能夠適配于LLVM 的新版PassManager 組件.此外，本文還選取了谷歌FuzzBench 平臺上適配AFL 的插樁模式，記為afl-fuzzbench.

如表2 所示，這3 種模式中，只有afl-clang 使用匯編作為插樁對象，其他模式使用LLVM 中間表示；只有afl-fast 將樁點邏輯內聯于程序的原始LLVM 中間表示，其他模式均在樁點處插入對外部運行時函數的調用指令.

圖2 顯示了AFL 插樁下不同程序的標準化執行時間.圖中橫線為原始程序的執行時間，即100%.從整體上看，afl-clang 的性能較差，額外開銷為219%；afl-fuzzbench 的性能較好，額外開銷為112%.afl-clang性能差的原因是基于匯編的插樁模式，即只是使用基本的模式匹配識別基本塊，并未對原始程序的寄存器使用情況進行分析，因此需要保存全部寄存器等大量的上下文，存在大量的額外操作.afl-fast 基于LLVM 中間表示，上下文管理由LLVM 后端在生成機器碼時自動完成，且高度優化.然而，afl-fast 模式將計數器更新邏輯置于程序內部，會帶來可觀代碼膨脹.以harfbuzz 項目為例，其在afl-fuzzbench 模式下的二進制大小為1.23MB，但是在afl-fast 模式下的二進制大下為2.81MB，相差1.28 倍.代碼膨脹會增加微處理器的緩存壓力和前端解碼器壓力，因而影響程序執行速度.afl-fuzzbench 使用基于回調函數的方法，盡管該方法需要增強函數調用和返回的成本，但是現代微處理器的前端能夠良好地預測執行流的切換，因而較小影響.

Table 2 Comparison of AFL’s Instrumentation Modes表2 AFL 的插樁模式對比

Fig.2 Execution duration of programs under AFL instrumentation圖2 AFL 插樁下的程序執行時間

此外，盡管是相同的測試工具、相同的待測程序、相似的反饋信息，但不同插樁模式下程序的性能差異極大.例如，harfbuzz 在afl-clang，afl-fast 和afl-fuzzbench插樁模式下，執行速度分別為原始程序的618%，449%和303%.

圖3 進一步對比了Sanitizer Coverage 不同模式下的插樁成本.其中，SanCov-Edge 表示只統計最基本的控制流信息，而SanCov-All 表示還開啟比較操作數記錄功能.圖3 中的數據經過歸一化處理，其中橫線為原始程序的執行時間100%.

Fig.3 Execution duration of programs under Sanitizer Coverage instrumentation圖3 Sanitizer Coverage 插樁下的程序執行時間

對比圖3 中的SanCov-Edge 和SanCov-All 可以發現，豐富的比較操作數信息嚴重拖慢了程序的執行速度.其中，最原始的SanCov-Edge 模式只會帶來0%～89%的額外開銷.然而，一旦開啟了對比較操作數的追蹤，SanCov-All 模式的額外開銷便突增到11%～577%.

比較操作數處理背后的巨大開銷可以從2 方面來解釋.首先，比較操作廣泛存在于程序中.以出現最大額外開銷的harfbuzz 為例，插樁后的程序中有近11 000 個計數器樁點，此外還有5 000 余個數值比較樁點和70 余個緩沖區比較樁點.雖然比較操作的樁點少于控制流樁點，但其量級卻近似.此外，對比較操作收集的插樁邏輯遠比控制流特征的收集復雜.以模糊測試工具libFuzzer 為例，它的控制流插樁只須對固定位置的計數器做簡單的自增操作；然而對于比較操作，它卻需要以不同方式度量操作數的距離，計算當前比較的哈希，更新全局特征，還需要將操作數拷貝并編入字典.顯然，復雜的樁點邏輯會給開啟比較操作數導向的模糊測試工具帶來巨大的額外開銷.

4.3 安全特性強化的額外開銷

圖4 顯示了OSS-Fuzz 項目中最流行的3 類安全特性強化插樁給不同待測程序帶來的額外開銷.需要注意的是，由于MSan 可能的誤報，導致bloaty 項目不能正常編譯，且sqlite3 項目不能正常執行.因此，本文剔除了上述不能正常評估的實驗項.

從圖4 可以看出，從整體上：內存安全檢查ASan會帶來146%額外開銷；未初始化內存讀取檢查MSan會帶來231%的額外開銷；未定義行為檢查UBSan 會帶來162%的額外開銷.此外，不同項目和不同插樁方式的額外開銷波動劇烈，并無顯著規律，這是由插樁自身和程序自身的固有特性決定的.例如，在檢測未定義行為的UBSan 中，大量的樁點都針對整數和指針運算.因此，對于具有大量算術運算的壓縮/解壓縮類型的算法類程序（例如woff2 和vorbis），UBSan具有巨大的額外開銷.類似地，ASan 對內存的讀寫都需要插樁，而MSan 對內存的讀寫和值的傳播都需要插樁.綜上，對于內存操作較為頻繁的程序會在ASan 和MSan 插樁模式下有較大的額外開銷.

Fig.4 Execution duration of programs under safety enhancement instrumentation圖4 安全特性強化插樁下的程序執行時間

5 靜態插樁的優化方向

5.1 基于硬件特性的優化

現代微處理器往往會提供不同的優化指令集.一方面，可以利用硬件特性加速靜態插樁.例如，在收集控制流特征時精簡插樁指令或加速分析[16].此外，還可以使用新的指令集架構加速內存安全檢查[17-20].另一方面，可以利用硬件特性直接記錄程序的控制流行為[21-23].雖然硬件本身能夠以較低的成本收集程序行為，但在模糊測試上尚存在信息處理較慢的挑戰[24].

5.2 基于程序分析的優化

利用編譯器強大的靜態分析能力可以減小插樁復雜度.例如，可以通過控制流分析減少控制流插樁的樁點數量[25]，或是生成元信息從而輔助運行時的樁點刪減[26-27]，或是增強對動態場景下覆蓋率到源碼的映射精度[28-29].

此外，運行時的動態分析信息也可以輔助模糊測試.例如，可以通過引入模糊測試前的試運行步驟刪除無關的安全檢查[30-31]，還可以交替進行編譯和運行，從而實現靈活的插樁調整[32].

6 結語

模糊測試是一種自動化的軟件缺陷發現方法，其實際應用往往伴隨著靜態插樁技術.本文介紹了模糊測試以及模糊測試背景下的靜態插樁技術，統計了實際模糊測試中各類靜態插樁技術的使用情況.針對內存安全檢查、未定義行為檢查、控制流特征采集、比較操作數收集這4 類具有代表性的靜態插樁技術，本文分析了其設計思想和實現技巧，對開發動態分析工具有參考意義.除了分析插樁的功能，本文還統計了不同插樁模式的額外開銷并分析了額外開銷背后的原因.基于上述內容，本文最后給出了靜態插樁的兩大優化方向，即利用硬件特性和程序分析極速執行或提升程度.

作者貢獻聲明：王明哲負責完成實驗并撰寫論文；姜宇提出了文章思路和實驗方案；孫家廣提出指導意見并修改論文.