基于多線程并行的符號執行引擎設計與實現

周 彭 左志強

1（南京大學計算機科學與技術系 南京 210023）

2（計算機軟件新技術國家重點實驗室（南京大學）南京 210023）

符號執行（symbolic execution,SE）[1]是通過采用抽象的符號值代替具體輸入分析程序執行情況的程序分析技術.由于SE 可以有效探索程序路徑，并生成對應路徑的輸入，其被廣泛應用于軟件測試[2-3]、安全分析[4]等一系列重要領域.經過多年的發展，工業界、學術界存在一系列相對成熟的符號執行工具，例如微軟的SAGE[2]、斯坦福開源的KLEE[3]等.

現有的SE 工具依然存在諸多問題.如待分析程序中的循環、分支使得符號執行中產生指數級數量的路徑，該問題被稱作路徑爆炸.路徑爆炸問題限制了SE 的可擴展性.此外，SE 中需要通過SMT 求解器判定大量路徑條件（path condition,PC），隨著對SE的深入研究，約束求解的耗時也逐漸增加.約束求解的求解效率也是影響符號執行可擴展性的一個關鍵因素.

針對路徑爆炸以及約束求解開銷過大的問題，研究人員提出了使用并行化的方式來提高SE 的可擴展性.已有的并行化SE 工作[5]往往采用多進程并行模型，每個進程中單獨運行一個SE 引擎實例并獨立探索不相交的程序狀態空間，不同進程之間通過多進程通信原語來傳遞需要求解的路徑等信息，不共享其他信息.

然而已有的基于多進程的并行化方法仍存在明顯不足.首先，傳統的基于多進程的并行SE 方法為了完成負載均衡，不僅需要引入極大可能成為性能瓶頸的中間節點，還需要獲取新執行路徑的進程重放已有的執行路徑來還原執行路徑的上下文.此外，已有的順序SE 引擎（如KLEE）為了緩解求解約束條件的開銷，引入了大量的約束求解優化技術，例如重復利用已經求解的約束來避免重復求解.而已有的基于多進程的并行化SE 由于路徑的分散性，使得原有的約束求解優化技術難以發揮作用，這極大限制并行化加速的效果.

基于以上觀察與分析，本文提出基于細粒度多線程并行的SE 方法.通過對SE 算法進行細粒度多線程并行，從而規避進程間通信引入的高開銷，同時利用多線程共享內存的便利性來復用已有的一系列約束求解優化技術.本文以符號執行引擎（KLEE）作為基礎，設計并實現了多線程并行化符號執行引擎（PKLEE）.

本文的主要貢獻包括4 個方面:

1）設計了一種基于多線程的并行符號執行方法（PKLEE），通過多個工作線程并行進行SE 求解，緩解路徑爆炸問題.

2）設計了多線程場景下不需要中間協調節點的工作負載竊取方法，有效規避了中間協調節點導致的性能瓶頸問題.

3）基于現有的約束求解優化技術，提出不同工作線程共享約束求解緩存的優化方法，有效提高了約束求解效率.

4）在KLEE 基礎上實現了PKLEE，從而開發完成原型工具PKLEE.在小規模數據集以及真實規模數據集上進行實驗評估，表明PKLEE 取得較高的可擴展性，并行化效率較已有并行化方法具有明顯提升.

1 技術背景

本節介紹傳統SE 過程以及KLEE[3]的組成模塊.

1.1 符號執行算法

每一個程序上所有可能的執行路徑可以生成一棵符號 執行樹（symbolic execution tree,SET）.SET 的根節點表示程序的起始狀態，每一個根節點對應程序執行中的一個中間狀態以及程序可以執行到該節點需要滿足的路徑條件.SET 上的一條從根節點到葉節點的路徑，對應程序的一條執行流.圖1 是一個簡單程序以及其對應SET 的示意圖.

算法1 給出了傳統KLEE 中的SE 算法.

算法1.標準SE 算法.

輸入：當前路徑狀態ES；

輸出：執行過程中生成的測試樣例.

Fig.1 Illustration of SET圖1 SET 示意圖

算法1 的輸入為初始的路徑執行狀態ES（包括當前路徑的全部約束條件、待執行指令，以及當前所有路徑上所有內存對象的映射），一般是程序中的第1 條指令對應的執行狀態.算法1 中出現的states變量為當前所有待探索的路徑，HaltExectution為一個全局標識符，HaltExecution為真時終止當前算法.由于同一時間可能存在多條路徑可以選擇探索，絕大多數KLEE 均提供了諸多搜索算法來選擇其中一條路徑探索.算法1 中行②將獲取當前狀態的過程抽象為getState方法，返回當前搜索策略所選擇路徑的執行狀態ES.

算法1 中的行⑤是SE 的核心，execInst對當前路徑上的當前指令解釋執行.在一般的KLEE 中，execInst往往實現為一個巨大的switch-case，為每一條支持的指令做了不同的處理.本文為了描述方便，進行一些必要的簡化.一般而言，所有的指令實際上可以抽象為分支（branch）、返回（ret）、中止（halt）以及一般的賦值（assign）語句.算法2 中為了屏蔽不必要的細節，對于使用的函數均給出了其含義.

算法2.單條指令解釋執行算法execInst.

輸入：當前路徑狀態ES、當前執行指令inst；

輸出：執行過程中產生的測試樣例.

對于分支語句，KLEE 會根據分支對應的路徑條件PCbr以及路徑狀態ES上原本的路徑條件PC判斷可行性：ES.PCΛPCbr對應分支可行，ES.PCΛ?PCbr則對應分支不可行.如果2 個分支均可行，則KLEE 會復制當前路徑狀態ES，并將對應的路徑條件PC更新，否則直接復用當前的ES（算法2 行④）.

對于返回語句(此處僅考慮從最底層的函數調用返回的情況)，KLEE 會根據路徑狀態ES的路徑條件PC求解并生成一個具體的輸入（算法2 行⑥），然后結束該路徑的求解.

一般的KLEE 實現中對于中止(例如assert 被違反)等指令的處理與返回語句類似，此時生成的樣例往往對應程序中的一個錯誤.

對于賦值語句，本文可以將其看作除了賦值、返回之外的一切不會改動路徑條件PC但可能改變內存對象映射的指令，KLEE 會根據該指令的語義，解釋執行并更新內存對象映射（算法2 行⑧），即更新內存建模中對應變量的值或新建變量等.

1.2 KLEE 基本模塊

KLEE[3]為由斯坦福大學于2008 年提出的符號執行引擎，用C++編寫，使用LLVM IR 作為中間表示，能夠對C、C++以及Rust 等語言進行SE.多年以來，KLEE 作為動態符號執行引擎的state-of-the-art，在學術界被廣泛應用于各類對SE 的測試與擴展中，例如Cloud9[5].

KLEE 核心組件為：

1）符號虛擬機（symbolic virtual machine）.KLEE輸入為SE 程序的LLVM bitcode 格式，它在內存中使用LLVM IR[6]對程序進行符號化的解釋執行.KLEE使用執行狀態（execution state,ES）抽象一條探索中的執行路徑，ES 上保存了路徑的約束條件、內存映射（symbolic memory store,SMS）等信息.因為ES 之間沒有數據上的依賴，KLEE 在SE 過程中可以同時保存多條執行路徑.

2）約束求解器鏈（solver chain）.KLEE 為了方便對約束求解進行優化，將約束求解的過程劃分成若干個階段，提高了約束求解優化流程的可擴展性.KLEE 默認情況下的約束求解鏈依次為計時求解器（Timing Solver）、獨立性 化簡求解器（Independence Solver）、緩存求解器（Caching Solver）以及反例緩存求解器（Cex Caching Solver）.待求解的約束會按照約束求解鏈依次傳遞，如果中途已經得出結果，則不會繼續傳遞；只有當底層求解器之前的階段全部失效時，KLEE 才會調用底層的SMT 求解 器.KLEE 在 文獻[3]中著重介紹了反例緩存，反例緩存基于許多約束之間十分類似的觀察，一個約束的子集的不可解等價于自身的不可解。同理，超集的可解等價于自身的可解.反例緩存會緩存已有的約束求解中的約束以及解，利用約束之間的子集、超集關系推導來避免調用底層SMT 求解器[7-9].

下面通過一個簡單的例子介紹反例緩存的工作原理.假設反例緩存中當前存在一個不可滿足的約束{x>2,x<0}，以及一個可滿足的約束{x>2,y<1}，對應的一個解為{x=3,y=0}.對于約束{x>2,x<0,y>3}，KLEE 查詢反例緩存發現該約束存在一個不可滿足的子集{x>2,x<0}，直接判定該約束不可滿足；對于約束{x>2}，KLEE 查詢反例緩存發現該約束的一個超集{x>2,y<1}可滿足，其中變量x的賦值依然滿足當前約束，直接判定該約束可滿足；對于約束{x>2,y<1,x≠4}，KLEE 通過查詢反例緩存發現該約束的一個子集{x>2,y<1}可滿足，盡管這不能直接說明當前約束可滿足，但是KLEE 通過將已有解帶入新約束中進行判定，如果成功，則能夠避免一次SMT 求解器的調用.

3）運行時環境模擬層.符號執行中的一大難題是模擬外部環境，例如操作系統中的文件在一系列讀寫操作下應保持一致.KLEE 對POSIX/Linux 運行環境進行了細致的建模，并在符號虛擬機對外部環境進行更改時使用該模擬層進行攔截，避免了黑箱調用，提升了SE 的質量.

本文以KLEE 為基礎實現了PKLEE.PKLEE 在保留了KLEE 中核心組件的同時，對KLEE 底層數據結構進行了一系列改寫以支持并行化路徑探索，同時使其支持并行約束求解以及動態負載均衡.

2 相關工作

為了提升SE 的可擴展性，近年來一直有相關工作[5,10-14]力求通過并行化手段對之進行提升.

Siddiqui 等人[10]提出了ParSym，一種基于傳統SE 算法的并行化方案.ParSym 直接將每一次的路徑探索并行化，并且使用中心節點進行任務的分配.然而，ParSym 的負載均衡方式增加了工作節點之間的通信次數，產生了極大的額外開銷，一定程度上限制了可擴展性.

Staats 等人[11]提出的簡單靜態切分方法（simple static partition），使用預先計算的先置條件（pre-condition）來切分SET，不同工作節點被賦予了不同的先置條件，并且只執行路徑條件滿足其先置條件的路徑，靜態地完成了SET 的劃分，不需要像ParSym 一樣引入中間節點頻繁地進行通信，極大地降低了通信開銷.然而，簡單靜態切分方法會導致不同工作節點重復探索一部分路徑，導致了一定計算資源的浪費.此外，簡單靜態切分方法本質上還是一種近似的對SET 靜態均分的方法，沒有徹底解決SET 在運行期形狀不可預知的負載不均衡問題.

Bucur 等人提出的Cloud9[5]與ParSym 的并行化架構類似，Cloud9 使用KLEE 作為底層符號執行引擎，在無共享（share-nothing）的集群上的各個節點上運行KLEE 的獨立線程實例.Cloud9 將SET 中的葉子結 點切分成不相交的部分，并以此作為負載均衡的單位.Cloud9 使用一個中心服務器進行負載均衡，根據不同節點上當前待處理任務數量的標準差以及當前平均待處理任務長度進行負載是否合理的判斷.在新的任務傳輸到工作節點上時，由于不共享內存，工作節點會在本地重放新的任務對應的執行路徑.Cloud9中心化負載均衡的方式容易讓中心服務器成為任務的瓶頸.此外，有對Cloud9 的實證分析[15]指出它沒有充分利用KLEE 內置的諸多約束求解優化技術，例如1.2 節提到的反例緩存優化技術.

Siddiqui 等人提出的Ranged Analysis[16]使用范圍分析(ranged analysis)的方法，通過人工設計或隨機生成的測試輸入來劃分符號執行的搜索樹，進而可以在劃分之后的不同子樹上并行進行SE.該方法通過測試樣例對不同的搜索樹進行了隔絕，一定程度上保證了不同工作節點之間的工作負載類似.Ranged Analysis 支持隨機生成樣例并對搜索樹進行劃分，然而，在這種情況下無法有效保證不同工作節點的工作負載類似.

Wei 等人提出了LLSC[17]，LLSC 將基于多階段編程（multi-stage programming）的高級語言編寫的SE 解釋器轉化為對應的編譯器.LLSC 生成的程序相比KLEE 等傳統符號執行引擎解釋執行的方式，沒有任何解釋執行的開銷，直接進行符號執行、合理調用SMT 求解器.同時，由于LLSC 生成的代碼使用了適合并行化的結構，其天然支持非確定的并行SE.LLSC不僅降低了SE 中探索每一條路徑的成本，同時也通過并行的方式提升了SE 的可擴展性.不過由于LLSC仍然在開發階段，其現在生成代碼中并行化SE 的方式仍然粒度較高.

除了并行化提升SE 可擴展性，也有相關工作通過對SET 進行剪枝[18-20]，去除SE 中冗余的路徑、減少需要探索的狀態空間；也有通過改進現有SE 的核心搜索算法來提升可擴展性的工作[21-22]，旨在使用特殊的搜索算法來專注搜索對于提升程序整體覆蓋率有利的路徑.

由于傳統基于多進程并行符號執行方法存在通信開銷大、中心化負載均衡的問題，本文提出了基于多線程并行的符號執行方法.通過更細粒度的線程并行，不同工作線程可以高效共享已有的路徑信息、約束求解信息，同時可以在不引入中間節點的情況下進行負載均衡.

3 PKLEE

本節介紹PKLEE 的框架.

3.1 方法概述

并行化SE 主要存在動態負載均衡、系統執行開銷2 個方面的挑戰.

SE 的工作負載是動態生成的，為了維持不同工作節點之間的工作負載平衡，現有工作[5,10]主要采取基于主從（Master-Worker）的中心化架構.在主從架構下，主節點（Master）不斷向工作節點（Worker）發送心跳并監視工作節點的待執行路徑數量，通過轉移待執行路徑來動態地實現不同工作節點間負載的平衡.在多線程場景下，工作線程可以通過共享內存直接共享內存中的待執行路徑信息，直接省去了待執行路徑通信的開銷以及路徑中帶有的路徑條件等額外信息；此外，本文注意到SE 過程中工作節點在少量路徑負載時依然能夠保持高CPU 利用率，本文設計了一種惰性的負載均衡策略，盡量減少負載均衡占用的時間.

對于系統執行開銷，SE 的開銷主要來自約束求解以及執行過程中產生的大量待執行路徑所占據的內存.傳統的多進程并行方法中每一個進程獨自運行一個KLEE 實例，不同KLEE 之間重復維護諸如內存建模等數據結構，造成了額外內存開銷.此外，不同的KLEE 之間無法共享已有的約束求解優化信息，例如KLEE 中的反例緩存.在本文多線程模型下，諸多數據結構可以直接在不同線程中共享.

基于這2 點挑戰，本文提出了如圖2 所示的PKLEE整體框架.PKLEE 底層同時運行多個工作線程，每個工作線程獨立解釋執行IR、調用SMT 求解器計算約束可行性.不同工作線程同時共享KLEE 原有的約束求解優化信息來降低約束求解開銷，例如反例緩存.3.2 節對應圖2 中的工作線程的生成以及具體執行的算法，3.3 節對應圖2 中的負載均衡，3.4 節對應圖2 中的共享約束求解緩存信息.

3.2 多線程SE

Fig.2 PKLEE architecture圖2 PKLEE 框架

SE 算法存在天然的并行性，理論上每一條路徑的探索求解彼此獨立，不存在互相依賴的關系.本文提出的并行化方法中以每一個工作線程作為符號執行的最小工作單元，同時保留一個協調線程保證在所有工作線程探索全部路徑或到達指定執行時間后結束符號執行.協調線程算法如算法3 所示.

算法3.協調線程算法.

在并行化符號執行開始階段，協調線程會進行一段時間的串行符號執行探索，直至當前待執行路徑數量達到用戶設定的閾值（算法3 行①）.在路徑數量達到用戶設定閾值之后，協調線程生成工作線程并將當前所有待執行路徑平均分配給工作線程（算法3 行④）.此后，協調線程不再執行任何操作，直至所有工作線程完成全部路徑探索，結束本次符號執行（算法3 行⑤）.如果在執行過程中工作線程使用的總內存達到了用戶設定的總內存上限或工作線程總執行時間超過了用戶設定的時間，協調線程會主動通知其他線程結束執行.

每一個工作線程的執行算法與算法1 中提到的標準符號執行算法類似，如算法4 所示.

算法4.工作線程算法.

輸入：待執行路徑隊列work_queue、其他工作線程列表worker_list、協調線程coordinator、最低工作負載閾值steal_threshold；

輸出：執行過程中產生的測試樣例.

在工作線程開始探索路徑前，它首先會將一些重要的線程局部變量在全局的內存對象映射中進行注冊（算法4 行①）.不同工作線程各自維護待執行路徑隊列，工作線程獲取可執行路徑后將會獨立求解，直至線程本地維護的待執行路徑隊列為空或協調線程通知結束符號執行（算法4 行③）.探索路徑過程中，工作線程會首先根據本地的搜索策略尋找下一條應該執行的路徑，如果待執行路徑隊列中剩余的待執行路徑數量小于用戶設定的最低工作負載閾值，則進入空閑狀態，并進行工作竊取（算法4 行⑤）；反之，工作線程會像標準符號執行算法一樣執行當前路徑，更新本地統計信息（執行時間、執行指令數量）.在完成當前路徑的探索之后，工作線程將本輪執行過程中所生成的新路徑直接加入線程本地的待執行路徑隊列中（算法4 行⑧）.該實現方法的好處是：如果待符號執行的程序本身規模較大，那么每一個工作線程幾乎可以在沒有任何通信的情況下分別高效地進行SE.

3.3 動態負載均衡

SE 過程中的工作負載往往動態變化，因此良好的負載均衡策略相當重要.本文設計了一種不需要中間協調線程參與的工作竊取算法，盡可能減少不同工作線程之間的通信次數.由于不同工作線程的待執行路徑隊列中的待執行路徑均位于堆上，除了不同線程之間同步的開銷，其他工作線程可以幾乎沒有開銷地直接獲取待執行路徑.

算法5.工作竊取算法.

輸入：其他工作線程列表worker_list，協調線程coordinator，最低工作竊取閾值work_threshold；

輸出: 獲取的待執行路徑.

當啟動工作竊取（即工作隊列中待執行路徑數量小于指定閾值）時，當前工作線程輪詢其他具有待執行路徑的工作線程（算法5 行③和④），從其中待執行路徑數量最多的工作線程上獲取待執行路徑（算法5 行⑤）.值得注意的是，為了防止發生工作線程被竊取后工作負載過低，算法5 只竊取待執行路徑數量大于最低工作竊取閾值的工作線程（算法5 行⑤）.實踐中，最低工作竊取閾值至少應該設置為最低工作負載閾值的兩倍.每一個工作線程為了支持被詢問當前的待執行路徑數量，需要對搜索算法以及路徑探索等模塊進行一定的同步，這帶來了一定的開銷，因此在算法中通過每次輪詢并且沒有獲取到待執行路徑時，等待一段時間以避免頻繁的同步操作（算法5 行⑨）.同時，在每一個工作線程均進入工作竊取狀態時，說明全局已經沒有任何工作負載，協調線程將會通知所有工作線程本次運行已經完成.

3.4 共享約束求解優化

已有的KLEE 往往使用約束求解緩存技術來加速約束求解[3].KLEE 在文獻[3]中提出了反例緩存的約束優化方式，其基本思路在第1.2 節已經做了簡要闡述，實質上是通過緩存求解過的約束解來加速之后的約束求解，在SE 過程的不同路徑求解模式類似時可以極大提升求解速率.通過KLEE 在文獻[3]的實驗以及工業界實踐，反例緩存往往可以提升十倍及以上的約束求解效率.

然而，本文發現，由于不同工作線程的約束求解緩存彼此獨立，相比于串行執行，并行執行過程中的單次約束求解開銷往往會更大.同時，不同工作線程對應的SET 的部分往往差異較大，在某個工作線程竊取了待執行路徑之后開始的新求解，可能會產生較高的約束求解開銷，類似于計算機中的Cache miss現象.

基于以上觀察，本文在并行化算法基礎上，將不同工作線程的緩存優化進行共享，每一個工作線程都會將其求解過的約束放入全局約束求解緩存中，并且已有的約束求解信息對其他線程可見.

4 工具實現

本節介紹PKLEE.圖3 給出了PKLEE 中工作線程的執行框架.

Fig.3 Illustration of PKLEE’s worker threads圖3 PKLEE 工作線程示意圖

4.1 KLEE 并行化改造

由于 KLEE 為單進程單線程執行模型設計，支持并行化符號執行存在一定難度.為了實現這一目標，本文對KLEE 底層數據結構、上層執行邏輯進行了諸多改造.

PKLEE 使用路 徑上下 文（execution context,EC）解決KLEE 無法進行多路徑并行執行的問題.路徑上下文記錄執行過程中不同路徑的增刪路徑信息，它使得不同路徑執行過程互相隔離.每一個不同的路徑上下文調用不同的SMT 求解器進行求解.

PKLEE 也對KLEE 中諸如引用計數類ref 等重要的底層數據結構進行了改寫，以保證PKLEE 在并發執行路徑場景下正確工作.對于KLEE 執行邏輯中的數據競爭問題，PKLEE 目前使用互斥訪問的方式進行簡單的保護.

4.2 工作線程實現

PKLEE 中的每一個工作線程對應4.1 節中的一個路徑上下文，每一個工作線程同時維護包含所有未執行路徑的隊列.為了實現3.3 節中的基于工作竊取的動態負載均衡算法，每一個工作線程在被初始化時獲取當前其他工作線程的路徑上下文，并且可以通過路徑上下文獲取其他工作線程當前的待執行路徑隊列中的路徑.如圖3 所示，工作線程3 當前待執行路徑隊列為空，因此它將執行工作竊取.工作線程3 訪問其他所有工作線程的待執行工作隊列，發現工作線程1 具有最多待執行路徑，因此從工作線程1 處竊取了一條路徑并執行.在所有工作線程并行符號執行期間，協調線程根據用戶設定的結束條件（超時、內存資源用盡或完成所有路徑探索），在結束條件滿足時通知工作線程結束符號執行.

PKLEE 在執行涉及外部環境的函數調用時，會使用當前工作線程的errno 來訪問內存建模中的對象，因此每一個工作線程在初始化時需要對類似errno 的線程局部變量在全局變量映射中進行注冊.值得注意的是，由于KLEE 與外部環境交互的重要函數runProtectedCall是不可重入的，PKLEE 目前在處理runProtectedCall時保證只能有一個工作線程，面對與外部環境交互頻繁的真實程序，PKLEE 的可擴展性會受到一定影響.

PKLEE 中還對工作竊取算法做了額外的優化.已有并行符號執行工作中的負載均衡算法往往只考慮了路徑數量，忽略了不同路徑的求解難度.本文注意到，KLEE 中的nurs:qc 搜索算法在搜索過程中考慮了每一條待搜索路徑的上一次約束求解成本，并選擇每一次求解成本最低的路徑，提升路徑吞吐量.基于這一思路啟發，本文在工作竊取算法中加入對于當前工作線程中不同路徑求解難度的衡量，將每一次求解成本較高的路徑優先分配給其他工作線程，減少當前線程的求解開銷.從任務并行的角度來看，將一個約束求解難度更高的路徑分配給其他路徑，在并行求解下，最終總執行時間不會更長；從利用緩存的角度來看，其他線程在求解了更復雜的路徑約束之后，很可能通過更新約束優化信息來加速后續的約束求解.

在完成每一次約束求解之后，工作線程都會將其求解過的約束放入全局反例緩存中.一方面，在不同工作線程中共享反例緩存帶來了一定的同步開銷，但這部分開銷與約束求解開銷相比較小.另一方面，并行化進行符號執行也一定程度上提升了緩存中可行解的數量，從而可以進一步減少約束求解的開銷.

5 實驗評估

本節對本文基于KLEE 實現的PKLEE 進行了2個方面的實驗分析.一方面，考慮了在諸多小規模合成程序上，KLEE 與PKLEE 完成所有可執行路徑探索所需時間的對比，即在窮盡路徑情況下的并行加速比；另一方面，對比了在若干個大規模真實程序上，相同時間內PKLEE 的有效工作負載吞吐量的提升.本節還分析了在以上2 種場景下工作竊取算法、共享反例緩存優化是否開啟對于整體性能的影響.最后，對比了PKLEE 與現有工作的并行加速比.

5.1 實驗設置

對PKLEE 的實驗評估試圖回答4 個研究問題：

問題1.PKLEE 的可擴展性如何？（5.3 節）

問題2.本文提出的工作竊取算法是否可以緩解不同工作線程的負載不均衡問題？（5.4 節）

問題3.本文提出的共享反例緩存是否能在并行執行場景下減少約束求解次數？（5.5 節）

問題4.PKLEE 與相關工作對比表現如何？（5.6 節）

本節開展的所有實驗均基于Ubuntu 18.04，使用的CPU 為AMD? Ryzen 7 4800h(8 核)，8 GB內存.編譯器為clang 9,KLEE 以 及PKLEE 使用的 求解器 為z3-4.8.8.KLEE 默認使用的約束求解器STP 在本文的實驗中無法正常地多實例并行運行，因此我們選擇了更新的z3 求解器.

5.2 實驗程序選取

為了測試PKLEE 在不同規模程序上的可擴展性、動態負載均衡效果等性能指標，本文選取了小規模、大規模2 類程序，并與KLEE 進行對比.

對于小規模程序，本文選取了LLSC 在文獻[17]中給出的測試基準樣例，其中包括3 個人工合成的大量路徑的程序、一些常見的較少涉及外部庫調用以及KLEE 自身的環境建模的小型程序（歸并排序、背包問題等）.為了保證并行化執行能夠在較短時間內能被執行，且避免KLEE 與系統建模的頻繁交互影響并行執行的性能，挑選的測試程序滿足較少涉及外部庫（例如malloc 等）的調用、總體指令數量和路徑數量較少的特點.表1 中列出了測試程序名稱以及其對應的執行指令數量、全部可探索的路徑數量.對于每一個小規模測試程序，對比KLEE 與PKLEE 探索全部路徑耗時的區別.

Table 1 List of Small-scale Benchmark表1 小規模合成測試程序列表

對于大規模程序，本文選取了GNU Coreutils 中的若干測試程序.KLEE 在文獻[3]中使用GNU Coreutils程序集進行性能的測試，并面向GNU Coreutils 等程序設計了一套比較完善的環境建模.本文測試使用的版本為GNU Coreutils 6.11.如 表2 所 示，本文將GNU Coretuils 中程序根據行數從高到低排序，并按大小隨機抽取6 個程序（200 行以上）進行測試.對于每一個測試程序，設定符號執行時間在10 min 內，并對比KLEE 與PKLEE 執行的指令數量的區別.此處之所以選擇KLEE 執行的指令數量而非完成的路徑數量作為有效工作負載的度量單位，是由于KLEE 面對較大規模的程序在較短時間內很難完成較多路徑的探索（可能存在大量未探索完畢的路徑），相比之下執行的指令數量這一指標則更為直觀，已有的工作Cloud9[5]在測試其可擴展性時也使用了該指標，說明了該指標具備可信度.

Table 2 List of Large-scale Benchmark表2 大規模真實測試程序列表

在PKLEE 路徑搜索策略的選擇上，從對比公平的角度出發，KLEE 以及PKLEE 均采用深度優先搜索算法進行路徑選擇.采用深度優先搜索算法的一個潛在好處是，保證了KLEE 每一次執行次序的相對固定，相比之下，KLEE 中的諸多啟發式算法在不同的執行過程中可能會選擇差距較大的執行路徑，需要進行多次實驗.

5.3 可擴展性

圖4 直觀反映了在小規模程序上，以PKLEE 的單個工作線程為基準，在增大工作線程數量的情況下，探索程序中所有可行路徑的耗時.圖4 中展示了在multipath_1048576_klee 樣例上，PKLEE 在不同線程數量下與KLEE 耗時的對比.從耗時較長的knapsack 以及multipath_1048576_klee 2 個樣例可以明顯看出，隨著工作線程數量的增加，總體執行時間顯著減少，并且在6 個線程左右時仍然保持線性的減少趨勢.然而，在8 個工作線程時，探索全部路徑的耗時保持恒定.本文認為，一方面，這可能是由于本文使用的實驗機器最多支持8 個物理線程，此時已經達到了最大負載，導致每一工作線程的執行效率有所下降；此外，從multipath_1048576_klee 樣例上KLEE 與PKLEE 完全探索耗時的對比也可以發現，PKLEE 目前的實現中存在底層諸多數據結構的同步開銷，影響了在單機上進一步擴展.

Fig.4 Total time taken to explore paths exhaustively under small-scale benchmark圖4 小規模測試程序探索完整路徑耗時

在路徑數量較少的情況下，例如multipath_1024_klee 樣例，從圖4 中可以看出，當程序中的整體執行路徑數量較少時，無法從并行化符號執行中獲得收益，甚至在增大工作線程的情況下會獲得負收益.相比之下，在multipath_1048576_klee 樣例上，PKLEE 凸顯了其收益.PKLEE 在所用的測試樣例程序上整體可以達到3.0x 的加速，其中在2 個耗時最長的knapsack和multipath_1048576_klee 上可以達到4.0x 的加速.

圖5 繪制出了隨著工作線程增長，在不同大規模測試程序上，指定時間內完成的有效工作的數量.圖5 中同時展示了在who 樣例上，PKLEE 在不同線程數量下與KLEE 執行指令數量的對比.

Fig.5 Total number of executed instructions under large-scale benchmark圖5 大規模測試程序執行指令數量

不難看出，隨著工作線程數量的增加，所有工作線程共計執行完成的指令數量基本呈線性增長的趨勢，并且增長的速度大致相同.圖5 說明了PKLEE 在8 核并行執行現實程序的場景下依然具備一定線性可擴展性，能夠充分利用不斷增加的計算資源.

本文也對比了在大規模程序上，未經修改的KLEE 與單個工作線程、8 個工作線程的有效工作負載.如表3 所示.

Table 3 Comparison of the Number of Executed Instructions Between KLEE and PKLEE表3 KLEE 與PKLEE 執行指令數量對比

通過加速比一欄可以看出，單個工作線程與KLEE 相比，在相同的執行時間內，執行的指令數量更少，這部分開銷可以視作并行執行中同步不同工作線程的加鎖、解鎖等操作的開銷.在8 個工作線程的情況下，所有線程執行的工作數量最終平均是KLEE 的3.2 倍，是單個工作線程的5.8 倍.

由表3 以及圖5 中的實驗數據可以得出結論，盡管并行化給單個線程執行帶來了一定開銷，但是實際執行過程中不同線程均攤了一部分的同步開銷，總體工作負載依然隨工作線程的數量增加而提升.從表3 中數據也可以發現，規模最大的join，stty，who等3 個測試程序獲得了較高的工作負載提升比例，相比之下PKLEE 在規模較小的runcon 上對工作負載的提升有限，這一定程度上說明并行化符號執行的方法隨著程序規模的增大可以獲得更多的潛在收益.此外，單個工作線程執行過程中的較大執行開銷也可以看出，目前的實現中依然存在較大的優化空間.

對于問題1，經過小規模與大規模測試程序兩個實驗的評估，可以看出PKLEE 具備一定的可擴展性，在8 個工作線程并行執行的情況下依然能夠保證較好的可擴展性.在小規模程序上進行的窮盡所有路徑探索實驗中，平均可以獲得3 倍的運行速度提升，且最多可以獲得4 倍以上的提速；在大規模的現實程序上，與KLEE 相比，在相同工作時間內，PKLEE可以將有效工作負載提升為原先的3 倍左右.總體看來，無論是在涉及較少庫函數、外部環境建模的小規模程序上，還是在真實的大規模程序上，基于多線程并行的符號執行方法都能充分利用多核的計算能力，在沒有做過多深入底層優化的前提下，有效地提升了符號執行的可擴展性.

此外，在大、小規模程序上的實驗數據表明，目前的PKLEE 依然存在一定的額外開銷.這部分開銷不僅來自底層的數據結構改為線程安全所帶來的額外開銷，也來自并行符號執行中同步多個工作線程的開銷.同時，由于KLEE 對外部環境的建模方式，目前實現中僅允許最多一個工作線程進行與外部環境的交互（例如修改errno）.在現實場景中的大規模程序上，勢必需要對該機制進行進一步的優化.

5.4 工作竊取算法效果

表4 中對比了小規模程序上，8 個工作線程下，是否開啟工作竊取情況下的全部路徑探索耗時以及KLEE 的探索路徑耗時.

Table 4 Time Consumption of Work-stealing Algorithms Under Small-scale Benchmark表4 小規模程序上工作竊取算法的時耗s

從表4 實驗數據可以看出，在8 個工作線程沒有開啟工作竊取的前提下，執行總體時間與KLEE 相比，僅有較小的提升.在沒有開啟工作竊取的情況下，不同工作線程的全部工作負載就是其被初始化時所分配的路徑以及執行過程中衍生出的路徑.在最壞情況下，如果沒有工作竊取算法，系統整體的執行時間會變成所有工作線程中最慢的一個.同時未列出的各個工作線程執行指令數量在開啟負載均衡后基本相同.

在表5 中可以看出，在大規模程序上，工作竊取算法開啟對于完成執行指令數量的影響.

在10 min 的執行 時間內，本文觀察到echo，uname 等樣例上存在工作線程提前完成自身工作負載的情況，這些樣例對應的工作負載減少了5%左右.其余樣例上沒有發現工作負載產生明顯變化，這是由于測試用的程序執行流較為復雜，故而在一定時間內幾乎每一個工作線程的工作負載都處于飽和狀態，故而此時的工作竊取算法是否開啟對整體的性能沒有較大影響.該實驗也證明了在工作負載飽和的情況下，工作竊取算法的開啟不會對整體的執行性能產生負面影響.

Table 5 Effect of Work-stealing Algorithms on the Number of Instructions Under Large-scale Benchmark表5 大規模程序上工作竊取算法對指令數量影響

對于問題2，通過2 個實驗，本文發現工作竊取算法在程序中整體可執行路徑較少的情況下，可以有效緩解由于靜態切分SET 形狀不同帶來的負載不均衡問題，并且在程序規模較大的情況下工作竊取算法也幾乎不會引起額外的開銷.小規模程序的測試實際上也可以視作大規模程序在執行后期的場景，即許多路徑會因為探索策略、系統開銷等原因提前終結，不同工作線程之間的工作負載差異極大，印證了本文第3.1 節的假設.

5.5 共享約束求解信息效果

表6 中給出了小規模程序上，在開啟與不開啟共享反例緩存優化情況下8 個工作線程的反例緩存命中情況對比.

Table 6 Effect of Shared Cex Cache on the Number of Hits Under Small-scale Benchmark表6 小規模程序上共享反例緩存對命中次數的影響

從表6 中數據可以看出，在小規模程序上，共享反例緩存可以降低反例緩存的未命中次數，平均減少了30%的反例緩存未命中次數.換而言之，在并行執行場景下，共享反例緩存減少了30%的底層約束求解.在符號執行以約束求解為主的工作負載上，共享反例緩存利用多個工作線程同時生成大量緩存的特點，有效提升了約束求解的效率.相比之下，傳統的基于多進程的并行執行方案中無法有效功共享諸如反例緩存這樣成熟的約束求解優化技術.

表7 中給出了大規模程序上，在開啟與不開啟共享反例緩存優化情況下8 個工作線程的反例緩存命中情況對比.

Table 7 Effect of Shared Cex Cache on the Number of Hits Under Large-scale Benchmark表7 大規模程序上共享反例緩存對命中次數的影響

平均而言，共享反例緩存在測試程序上降低了反例緩存的未命中次數達32%，充分說明在大型實際程序的場景中，通過共享約束求解信息也可以對整體約束求解效率帶來一定幅度的提升.在執行指令數量最多的兩個樣例程序上，共享反例緩存降低了整體的反例緩存未命中次數近50%.共享反例緩存在大規模工作負載上可以獲得更高的收益，因為不同的工作線程的執行樹之間往往存在一定的相似性.

對于問題3，本節的實驗也充分證明了，在大、小規模程序的場景下，共享反例緩存在多個工作線程的情況下可以有效減少底層約束求解器被調用的次數.在待執行路徑較多情況下，多個工作線程可以同時增加大量約束求解信息，實驗中最多可以減少50%的底層約束求解調用，大大提升了約束求解的效率，并且同步的額外開銷較小.反例緩存只是KLEE 約束求解優化技術中的其中一種，本文的嘗試也說明了在并行化執行場景下，如何充分利用已有的約束求解優化技術值得進一步探討.

5.6 與已有工作對比

由于相關的并行化符號執行工具[5,10,11,16]并未開源或長期缺乏維護而無法正常運行，因此無法通過在相同實驗環境下復現已有方法進行完整、精確的性能對比.然而，為了在一定程度上理解PKLEE 和相關并行化工作的優劣，本節選取Ranged Analysis[16]實驗中的公開測試集，在其上對PKLEE 進行實驗，收集加速比數據，然后和Ranged Analysis[16]論文中報告的加速比數據進行直接對比.

Ranged Analysis 中的實 驗測試使用6 個工作 節點并且開啟負載均衡，給出了在GNU Coreutils 程序上的加速比.由于Ranged Analysis 工作未給出源代碼并且沒有給出測試時使用的具體優化、搜索方法以及參數，將PKLEE 與該工作實驗結果直接對比存在一定不可靠性，本文直接使用與真實程序測試中相同的測試參數及搜索方法，不進行任何的優化設置，盡可能保證對比的公平性.

Ranged Analysis 中通過其提出的技術保證了多個工作節點的符號執行與單個節點的符號執行遍歷的路徑完全相同，并比較兩者遍歷完相同路徑所需的時間.為了簡單起見，本文依然采用與真實程序測試中的執行的指令數量來計算加速比.由于不能保證PKLEE 多工作線程執行過程中的路徑與單個工作線程相同，為規避偏見（bias）影響，僅保留多線程探索路徑數量較多的測試程序，表8 展示了具體的加速比數據.

Table 8 Comparison of Speedup Between Ranged Analysis and PKLEE表8 Ranged Analysis 與PKLEE 的加速比對比

通過表8 可以發現，僅僅通過多線程方法并行化符號執行過 程，PKLEE 在許 多Ranged Analysis 表現不佳的測試樣例上依然可以達到3x～4x 的加速比.PKLEE 在Ranged Analysis 的樣例加速比基本持平.其中，在測試程序fold 上，PKLEE 達到了超過工作線程數的并行加速比.這是由于PKLEE 每個工作節點在探索fold 的局部符號執行樹時，由于子樹規模小，工作節點能充分利用已有的約束求解優化，進而獲得了超過工作節點數的加速比.

值得注意的是，PKLEE 目前無法達到Ranged Analysis 表現最好的幾個測試程序上的加速比.由于Ranged Analysis 使用了范圍分析的技術，對符號執行算法本身進行了優化，因此可以在某些測試程序上達到大于6x 的加速比，而PKLEE 對此沒有進行優化.此外，PKLEE 由于KLEE 自身設計的缺陷，同一時刻最多只有一個線程可以同外部庫交互，這也導致了PKLEE 在與外部庫交互多的程序上表現不佳.

6 討論

6.1 線程同步開銷

PKLEE 為了在KLEE 的基礎上實現多線程并行符號執行，引入了一定的線程同步開銷.一部分同步開銷來自于底層數據結構的線程安全化，例如KLEE中使用的智能指針類ref；另一部分同步開銷來自不同線程執行過程中對關鍵數據結構的同步保護，例如KLEE 中的不同線程的工作隊列.

為了削減底層數據結構帶來的額外開銷，本文使用更加輕量級的同步原語改寫現有的數據結構，同時降低數據結構中的鎖粒度，以減少不同線程的競爭，盡可能減少頻繁使用底層數據結構帶來的開銷.

為了減少多線程執行過程中對于關鍵數據結構的競爭，本文使用更具備擴展性的數據結構改寫PKLEE 中的關鍵模塊.例如，使用無鎖隊列改寫每個工作線程的工作隊列.

6.2 KLEE 中其他約束求解優化技術的可擴展性

KLEE 中除了本文著重介紹的反例緩存外，還有諸多成熟的優化技術，其中多數優化技術都使用了緩存來提升效率.

基于求解結果緩存的優化直接緩存已有的約束求解結果，當遇到完全相同的約束求解信息時可以直接復用已有的解.基于求解結果緩存的優化同樣可以通過本文提出的多線程共享方式進一步被優化.

KLEE 中在進行約束求解之前，會對需要求解的約束進行一定的化簡，例如對數組訪問中的索引值可能的取值范圍進行限定.KLEE 在執行此類優化過程中同樣會緩存已經簡化過的約束.簡化約束過程中產生的緩存信息在不同線程上可能存在冗余，也可以考慮使用共享的方式進行優化.

值得注意的是，目前KLEE 中所有的緩存都沒有設置緩存大小上限.隨著符號執行的進行，優化信息的緩存將會占據越來越多的內存，同時查詢緩存的時間也將越來越長[15].在未來的研究中，本文計劃使用LRU 等算法識別出當前被多個線程頻繁命中的優化緩存信息，及時淘汰無用的信息，以減少內存開銷以及每次掃描緩存的時間開銷.

7 結論

本文從現有并行符號執行引擎基于多進程模型通信開銷大、無法有效利用現有的約束求解優化技術的問題出發，設計并實現了一種基于單進程多線程并行模型的并行符號執行引擎（PKLEE）.本文基于KLEE 實現的原型PKLEE，不僅使用了基于多線程的無需中心線程的負載均衡方法，還通過不同線程共享彼此的約束求解信息來減少約束求解.經過實驗分析，在小規模程序的完整路徑探索時間上，PKLEE 在8 個工作線程并行化下加速比為2.5x～4.0x；在大規模程序上的有效工作負載吞吐量這一指標上，PKLEE 在8 個工作線程下最終有效執行的指令數量可以達到KLEE 的2.0x～4.8x.

本文工作依然存在一些不足，如線程同步的開銷沒有進一步削減和針對KLEE 內部的數據結構進行適合并行化的改造.未來工作中，本文將進一步分析PKLEE 當前的瓶頸，并對其加以優化以達到更高的加速比；此外，本文也計劃探索如何在多線程并行場景下，更有效地利用不同約束求解優化技術對已有的一些符號執行技術[23-25]在并行化場景下進行設計.

作者貢獻聲明：周彭提出了算法思路，實現工具并撰寫論文；左志強提出指導意見并修改論文.