基于圈復雜度的階段動態符號執行*

畢雪潔，於家偉，李世明,2

(1.哈爾濱師范大學 計算機科學與信息工程學院，黑龍江 哈爾濱 150025；2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240)

0 引言

路徑爆炸問題降低了軟件測試的效率和質量，也給軟件埋下隱患。如何緩解路徑爆炸問題成為軟件安全測試中的一個研究熱點，符號執行[1]成為緩解該問題嚴重程度的重要技術之一。其主要算法思想為利用符號變量來取代測試過程的真實用例，從而在執行過程中獲取對應的執行路徑，成為生成高覆蓋測試用例和在復雜軟件應用程序中查找深度錯誤的有效技術之一；因該技術能夠處理復雜結構程序，開發人員也經常用之于程序自動測試[2]、程序缺陷檢測[3]、測試用例生成[4]等。

1 相關研究工作

1.1 符號執行

符號執行使用符號值而非真實用例作為輸入值，并將程序變量的值表示為符號表達式[5]。因此，由程序計算的輸出表示為符號輸入的函數[6]。也就是說，每個符號執行的結果等同于大量測試用例，以便盡可能地檢測程序中可能出現的行為和狀態是否滿足安全性能。符號執行技術分類主要包括以下幾種。

(1)經典符號執行技術。主要特點為在理論上可以遍歷更多的程序，但不能探索路徑約束條件下可能無法處理的可行執行，故并未得到廣泛應用。

(2)動態符號執行技術。主要有Concolic測試[7-8]和EGT(Execution-Generated Testing)[9]等，能夠利用對實際輸入得到的分支路徑判定條件進行邏輯取反來探索所有可能的路徑，如EXE[10]和KLEE[11]工具和擴展的EGT方法等。該技術在軟件測試、逆向工程等應用方面得到認可。

在動態符號執行時，外部代碼的交互、約束求解(本文暫不過多討論)因超時而降低精確性[1]，在使用真實用例緩解該問題時也破壞了路徑遍歷的完整性，其本質問題依然是路徑爆炸和約束求解的難解，故其成為動態符號執行的技術瓶頸之一。優化路徑選擇可緩解上述問題，相關研究主要包括：(1)使用啟發式搜索探求最佳路徑，提高程序路徑覆蓋率，加快符號執行速度，包括：① 使用靜態控制流圖(CFG)選擇路徑；② 利用先決條件及輸入特性進行符號執行，如預條件符號執行方法[4]、利用靜態分析工具來分析程序中缺陷語句的方法[12]等。(2)利用程序分析技術減少路徑探索的復雜性，包括：①構建函數和循環摘要供后續重用，如Concolic執行提出的可動態生成函數摘要組合方法[7]，可有效重新利用分析結果；② 剪枝冗余路徑，如基于程序功能執行流切片技術[13]，通過裁剪掉與功能無關的分支路徑來提高制導效率；③通過依賴性分析[14]來有效合并變量狀態，提高路徑分析的精度；④通過狀態合并來縮小路徑分支的選擇范圍，緩解路徑爆炸問題，但該方法易降低路徑覆蓋率。

隨著程序中邏輯判定語句的增加，路徑爆炸問題越突出，符號執行面臨的技術挑戰越嚴峻[15]。

1.2 符號執行樹

在符號執行過程中，根據執行路徑而生成的樹狀結構表示定義為執行樹，如圖1所示。

圖1 示例程序及生成的符號執行樹

在執行樹中，當程序執行到第3節點時，路徑約束條件即為(x > 1)∧(x < 10)∧(x>-6)，約束求解器(要解出3個約束條件的解，即算出可達路徑的值)；此時若遍歷該執行樹，路徑條數將以指數級數目增長并引發路徑爆炸問題。

若執行樹中存在一條由n(當n∈Z+)個邏輯節點組成的路徑，則程序執行時需對n個約束條件集合求解，當n→+∞時其計算量無疑是巨大的；若此時對易引發路徑爆炸的執行樹進行分階段符號執行，則可降低路徑爆炸發生的概率和約束條件的求解難度，但須在分階段符號執行前探測執行樹的深度。

1.3 圈復雜度

圈復雜度(Cyclomatic Complexity)[16]是用來衡量程序代碼判定結構復雜程度的重要標準，其值越大說明代碼的判斷邏輯結構越復雜，即代碼質量低或難于測試及維護，存在潛藏缺陷和漏洞的可能性就越大。

一般情況下，增加圈復雜度的核心問題實際是大量的邏輯判定語句，表現在代碼上是case、if、while等語句及函數調用，而圈復雜度的計算有利于控制程序邏輯長度、設置檢查點(或測試點)和評測代碼質量。

定義1圈復雜度值VCC=e-n+2，其中e、n分別表示代碼對應控制流圖中邊數和節點數(含起點和終點，當有多個終點時只計算1次)。

定義2圈復雜度標準量級GCC一般被定義為三個級別：Ⅰ級(代碼質量優秀)、Ⅱ級(代碼可重構或優化)和Ⅲ級(強制重構)，如公式(1)所示。

(1)

針對路徑爆炸問題，本文提出了基于圈復雜度的階段動態符號執行模型(Cyclomatic Complexity-based Stage Dynamic Symbolic Execution Model，CCSDSEM)，建立利用圈復雜度來探測圈復雜度高的代碼段，然后以符號化邏輯判定分支數量作為衡量標準，分階段進行動態符號執行操作，并在分段處進行約束集求解及優化，進而降低求解的復雜度。本文貢獻如下。

(1)分段策略可降低程序邏輯判定分支的規模，緩解路徑爆炸現象。

(2)利用分段執行和優化約束條件求解，可提高符號執行的執行效率和路徑覆蓋率。

2 基于圈復雜度的階段動態符號執行模型

2.1 模型定義

將待測代碼作為模型外部輸入數據并計算各檢查點的圈復雜度及代碼量，然后在統計結果的基礎上根據求得的圈復雜度與閾值進行比較，來預判動態符號執行的計算量級，并據此設置檢查點來分段執行對應的代碼段，在運行符號執行引擎后分別生成缺陷報告。

定義3：將基于圈復雜度的階段動態符號執行模型定義為一個四元組CCSDSEM=(I,P,E,O),其中：

(1)I=(ISC1,ISC2,…,ISCi,…,ISCn|i,n∈Z+)表示該模型中被測序的源代碼(Source Code,SC)。

(2)P=(PCQ,PLC,PIE,PCT,PSSN)表示對測試對象按一定策略進行系列處理;其中PCQ表示統計代碼量(Code Quantity,CQ),PLC表示統計循環條件(Loop Condition,LC),PIE表示按照約束規則進行信息提取(Information Extraction,IE)，PCT表示計算閾值(Calculate the Threshold,CT)，PSSN表示按邏輯結構進行階段節點設置(Set Stage Node,SSN)。

(3)E=(ESG,ESEE)表示對處理后的對象進行符號執行；其中ESG表示符號生成器(Symbol Generator,SG)，ESEE表示符號執行引擎(Symbol Execution Engine,SEE)。

(4)O=(ODR1,ODR2,…,ODRi,…,ODRn|i,n∈Z+)表示輸出的各個測試報告，其中ODRi表示輸出的第i個缺陷報告(Defect Report,DR)。基于圈復雜度的階段動態符號執行模型框架如圖2所示。

圖2 CCSDSEM框架

2.2 分段執行規則

為便于闡述分段符號執行策略，現構造部分代碼如下：

(1) int x,y,z,t;

(2) int t;

(3) scanf("%d,%d,%d",&x,&y,&z);

(4) if (x<1) t=x;

(5) else if (x>10) t=2×x-1;

(6) else if (x+y>10) t=2×y+x;

(7) else if (z<0) t=x+z;

(8) else if(y<12) t=y-z;

(9) else t=fun(x);

(10) printf ("%d ",t);

(11) int fun(int n)

(12) { int m;

(13) m=2×fun(n-1)+1;

(14) return m; }

(1)Concolic執行過程

在測試過程中，Concolic執行會隨機產生輸入測試值(如{x=3,y=13,z=5})，當執行else if (x>10)時，符號化執行會生成路徑約束(x0>1)，然后Concolic執行對邏輯判斷條件取反并對(x0<1)求解，并將得到的一個測試用例作為輸入，從而執行不同路徑。

同理，第5行產生約束條件(x0>=1)∧(x0>10)以及(110)∧(z0>0)∧(y0<12)并對約束求解；隨著程序執行的不斷深入，約束條件復雜性變大，路徑分支將會以指數級增長，加大了約束求解難度。

如果圈復雜度超過預先設定閾值Ф時，則對該部分代碼進行分段執行或優化約束條件后再執行；此時，因(y0<12)是取反的分支約束條件，對(y0<12)分支無任何影響，故可去掉對z的約束，可從當前路徑條件中移除與當前分支結果無關的約束，提高約束求解效率，降低因約束條件過于復雜而引發路徑爆炸的概率。

(2)分階段動態符號執行

當在CCSDSEM框架中執行分階段動態符號執行時，根據控制流順序設置檢查點并計算對應代碼段的圈復雜度，當某個圈復雜度大于預先設定的閾值Ф時，則對該段代碼單獨執行動態符號執行；反復運用此策略，直至所有代碼檢測并分解完畢，算法描述如下：

算法：分階段符號執行策略算法

輸入:C語言格式的待測代碼

輸出:高圈復雜度函數名稱及復雜度值

(1) 初始化CCSDSEM=(I,P,E,O)

//初始化模型

(2) 構建待測代碼集I

(3) int Ф=50;

//設定閾值Ф=50

//遍歷各函數并計算函數的圈復雜度VCC

(4) int CC(Fi);

//計算VCC

(5) { inti=0;

(6) while (I!=NULL)

//當輸入集非空時執行

(7) {i++;

//第i個函數

(8) VCC =count (read (Fi));

//讀取函數Fi并求出VCC

(9) if (VCC>Ф)

//若VCC大于Ф

(10) { outputFi,VCC;

//輸出VCC

(11) temp_filei=read(Fi);

//讀取Fi代碼到temp_filei

(12) CC (temp_filei);}

//遞歸計算Fi的VCC

(13) else Symbolic_ Execution (Fi)；

//符號執行Fi

(14) }

(15) }

當程序的整體影響處于可控狀態下，采用此策略對被測程序按閾值進行分階段動態符號執行，可降低產生路徑爆炸的概率，緩解因動態符號執行將部分值實例化而引發的路徑覆蓋不足等問題。

3 實驗與分析

本文實驗通過SourceMonitor對開源項目GNU Binutils-2.14中部分源代碼文件進行圈復雜度測試，選用VCC值較高的源代碼文件readelf.c進行測試。

3.1 圈復雜度計算實驗

實驗進一步對readelf.c計算圈復雜度，與本研究有關的詳細信息如表1所示。

表1 readelf.c測試后的主要信息

在readelf.c中，以函數為檢查點計算圈復雜度，可看出最復雜函數switch()(在分支語句控制下各函數名相同但內部代碼實際是不同的，即各函數的VCC值不同)的VCC值非常高(值為517)，進一步計算得出各功能函數的詳細信息，如表2所示。

表2 readelf.c測試后的主要信息

顯然switch()為readelf.c的主要函數，而且明顯高于其他函數，從其Kiviat圖(如圖3所示)上可以看出各項指標嚴重偏離合理區間(深色圓環區域)。

圖3 Kiviat圖

對所有switch()函數計算VCC，累計97個(其中I級55個，II級14個，III級28個)，VCC最高為95，最低為2；在III級中VCC>50的switch(*)如表3所示。

表3 復雜度大于50的含參switch()函數

3.2 分階段動態符號執行實驗

在對測試所得的VCC實驗數據分析后發現：若分支情況越多、嵌入層次越深、調用函數越多且復雜，則VCC值越大。因符號執行在VCC越大的情況下效率會嚴重降低，若將一個復雜程度分解為多個復雜度相對理想且內聚性強的代碼片段來進行分階段符號執行，顯然具備緩解或降低路徑爆炸的功效。

此部分實驗選用符號執行工具KLEE 2.0，CPU為Intel(R) Core(TM) i5-3320M 2.60 GHz、內存為16 GB、Ubuntu 16.04.11 LTS、內核版本為5.4.0-6，編譯器clang version 6.0.1，與KLEE相關如llvm6.0，clang6.0。實驗首先對將VCC>Ф(Ф設為50)的switch()函數調用采用剪枝處理(會影響代碼調用，但會簡化與其對應的執行樹)，VCC值越大該方法越有益。此外，實驗中對于case語句非常多的情況，采用簡單以Ф值為上限的簡單分割方法，分割后代碼段的VCC≤Ф；分階段動態符號執行后的數據及原因分析如表4所示。

表4 部分含參switch()分階段執行后的復雜度

3.3 局限性分析

(1)執行分階段動態符號執行時，具體邏輯判斷語句(如case、if)及嵌套層次嚴重影響分階段情況，相對應測試的圈復雜度之間差別也很大；尤其代碼中case語句趨向全部時，最簡單的分階段方法為：當case語句數量等于Ф時進行分割(存在誤判)，此時VCC=Ф(如表4中序號4～9情況)。如果循環或遞歸的終止條件是符號化的，就可能會出現無限數量的對應路徑，因此對循環分支數量的判定結果是衡量符號執行樹狀狀況的重要依據。

(2)實驗情況可以判斷出動態符號執行中可能產生路徑爆炸的不同規模。目前這種方法并不能完全固定分支的數量，故每次實驗時結果存在誤差，但總體上可以滿足圈復雜度不高于Ф的條件。

(3)本實驗只對單個.C程序文件進行測試，尚未對大型項目代碼進行測試，也未考慮各文件之間的依賴關系等。

4 結論

本文首先介紹動態符號執行的相關研究現狀和基本概念，然后詳細分析存在的不足以及采用的分階段執行方法，并分析路徑覆蓋率，進而提出基于圈復雜度的階段動態符號執行的方法，并通過示例實驗證明，相比于原有的方案，使用CCCSDSEM優化框架后降低了代碼的圈復雜度并緩解了路徑爆炸。

后續的研究工作主要從以下方面開展：(1)在KLEE分支狀態跟蹤中收集實際執行的路徑數量并做出相應的判斷及緩解路徑爆炸的策略；(2)如何更好地結合圈復雜度的進行分段優化，并在KLEE中做相應改進是后續研究工作中的重點；(3)如何在分階段動態符號執行過程中提高約束求解效率；(4)如何保證圈復雜度設置的值既不讓程序分割過多而消耗系統資源，又可一定程度上遍歷更多的路徑且緩解路徑爆炸和約束求解。