基于圈復(fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行*

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

(1.哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，黑龍江 哈爾濱 150025；2.上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，上海 200240)

0 引言

路徑爆炸問(wèn)題降低了軟件測(cè)試的效率和質(zhì)量，也給軟件埋下隱患。如何緩解路徑爆炸問(wèn)題成為軟件安全測(cè)試中的一個(gè)研究熱點(diǎn)，符號(hào)執(zhí)行[1]成為緩解該問(wèn)題嚴(yán)重程度的重要技術(shù)之一。其主要算法思想為利用符號(hào)變量來(lái)取代測(cè)試過(guò)程的真實(shí)用例，從而在執(zhí)行過(guò)程中獲取對(duì)應(yīng)的執(zhí)行路徑，成為生成高覆蓋測(cè)試用例和在復(fù)雜軟件應(yīng)用程序中查找深度錯(cuò)誤的有效技術(shù)之一；因該技術(shù)能夠處理復(fù)雜結(jié)構(gòu)程序，開發(fā)人員也經(jīng)常用之于程序自動(dòng)測(cè)試[2]、程序缺陷檢測(cè)[3]、測(cè)試用例生成[4]等。

1 相關(guān)研究工作

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

符號(hào)執(zhí)行使用符號(hào)值而非真實(shí)用例作為輸入值，并將程序變量的值表示為符號(hào)表達(dá)式[5]。因此，由程序計(jì)算的輸出表示為符號(hào)輸入的函數(shù)[6]。也就是說(shuō)，每個(gè)符號(hào)執(zhí)行的結(jié)果等同于大量測(cè)試用例，以便盡可能地檢測(cè)程序中可能出現(xiàn)的行為和狀態(tài)是否滿足安全性能。符號(hào)執(zhí)行技術(shù)分類主要包括以下幾種。

(1)經(jīng)典符號(hào)執(zhí)行技術(shù)。主要特點(diǎn)為在理論上可以遍歷更多的程序，但不能探索路徑約束條件下可能無(wú)法處理的可行執(zhí)行，故并未得到廣泛應(yīng)用。

(2)動(dòng)態(tài)符號(hào)執(zhí)行技術(shù)。主要有Concolic測(cè)試[7-8]和EGT(Execution-Generated Testing)[9]等，能夠利用對(duì)實(shí)際輸入得到的分支路徑判定條件進(jìn)行邏輯取反來(lái)探索所有可能的路徑，如EXE[10]和KLEE[11]工具和擴(kuò)展的EGT方法等。該技術(shù)在軟件測(cè)試、逆向工程等應(yīng)用方面得到認(rèn)可。

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

隨著程序中邏輯判定語(yǔ)句的增加，路徑爆炸問(wèn)題越突出，符號(hào)執(zhí)行面臨的技術(shù)挑戰(zhàn)越嚴(yán)峻[15]。

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

在符號(hào)執(zhí)行過(guò)程中，根據(jù)執(zhí)行路徑而生成的樹狀結(jié)構(gòu)表示定義為執(zhí)行樹，如圖1所示。

圖1 示例程序及生成的符號(hào)執(zhí)行樹

在執(zhí)行樹中，當(dāng)程序執(zhí)行到第3節(jié)點(diǎn)時(shí)，路徑約束條件即為(x > 1)∧(x < 10)∧(x>-6)，約束求解器(要解出3個(gè)約束條件的解，即算出可達(dá)路徑的值)；此時(shí)若遍歷該執(zhí)行樹，路徑條數(shù)將以指數(shù)級(jí)數(shù)目增長(zhǎng)并引發(fā)路徑爆炸問(wèn)題。

若執(zhí)行樹中存在一條由n(當(dāng)n∈Z+)個(gè)邏輯節(jié)點(diǎn)組成的路徑，則程序執(zhí)行時(shí)需對(duì)n個(gè)約束條件集合求解，當(dāng)n→+∞時(shí)其計(jì)算量無(wú)疑是巨大的；若此時(shí)對(duì)易引發(fā)路徑爆炸的執(zhí)行樹進(jìn)行分階段符號(hào)執(zhí)行，則可降低路徑爆炸發(fā)生的概率和約束條件的求解難度，但須在分階段符號(hào)執(zhí)行前探測(cè)執(zhí)行樹的深度。

1.3 圈復(fù)雜度

圈復(fù)雜度(Cyclomatic Complexity)[16]是用來(lái)衡量程序代碼判定結(jié)構(gòu)復(fù)雜程度的重要標(biāo)準(zhǔn)，其值越大說(shuō)明代碼的判斷邏輯結(jié)構(gòu)越復(fù)雜，即代碼質(zhì)量低或難于測(cè)試及維護(hù)，存在潛藏缺陷和漏洞的可能性就越大。

一般情況下，增加圈復(fù)雜度的核心問(wèn)題實(shí)際是大量的邏輯判定語(yǔ)句，表現(xiàn)在代碼上是case、if、while等語(yǔ)句及函數(shù)調(diào)用，而圈復(fù)雜度的計(jì)算有利于控制程序邏輯長(zhǎng)度、設(shè)置檢查點(diǎn)(或測(cè)試點(diǎn))和評(píng)測(cè)代碼質(zhì)量。

定義1圈復(fù)雜度值VCC=e-n+2，其中e、n分別表示代碼對(duì)應(yīng)控制流圖中邊數(shù)和節(jié)點(diǎn)數(shù)(含起點(diǎn)和終點(diǎn)，當(dāng)有多個(gè)終點(diǎn)時(shí)只計(jì)算1次)。

定義2圈復(fù)雜度標(biāo)準(zhǔn)量級(jí)GCC一般被定義為三個(gè)級(jí)別：Ⅰ級(jí)(代碼質(zhì)量?jī)?yōu)秀)、Ⅱ級(jí)(代碼可重構(gòu)或優(yōu)化)和Ⅲ級(jí)(強(qiáng)制重構(gòu))，如公式(1)所示。

(1)

針對(duì)路徑爆炸問(wèn)題，本文提出了基于圈復(fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行模型(Cyclomatic Complexity-based Stage Dynamic Symbolic Execution Model，CCSDSEM)，建立利用圈復(fù)雜度來(lái)探測(cè)圈復(fù)雜度高的代碼段，然后以符號(hào)化邏輯判定分支數(shù)量作為衡量標(biāo)準(zhǔn)，分階段進(jìn)行動(dòng)態(tài)符號(hào)執(zhí)行操作，并在分段處進(jìn)行約束集求解及優(yōu)化，進(jìn)而降低求解的復(fù)雜度。本文貢獻(xiàn)如下。

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

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

2 基于圈復(fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行模型

2.1 模型定義

將待測(cè)代碼作為模型外部輸入數(shù)據(jù)并計(jì)算各檢查點(diǎn)的圈復(fù)雜度及代碼量，然后在統(tǒng)計(jì)結(jié)果的基礎(chǔ)上根據(jù)求得的圈復(fù)雜度與閾值進(jìn)行比較，來(lái)預(yù)判動(dòng)態(tài)符號(hào)執(zhí)行的計(jì)算量級(jí)，并據(jù)此設(shè)置檢查點(diǎn)來(lái)分段執(zhí)行對(duì)應(yīng)的代碼段，在運(yùn)行符號(hào)執(zhí)行引擎后分別生成缺陷報(bào)告。

定義3：將基于圈復(fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行模型定義為一個(gè)四元組CCSDSEM=(I,P,E,O),其中：

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

(2)P=(PCQ,PLC,PIE,PCT,PSSN)表示對(duì)測(cè)試對(duì)象按一定策略進(jìn)行系列處理;其中PCQ表示統(tǒng)計(jì)代碼量(Code Quantity,CQ),PLC表示統(tǒng)計(jì)循環(huán)條件(Loop Condition,LC),PIE表示按照約束規(guī)則進(jìn)行信息提取(Information Extraction,IE)，PCT表示計(jì)算閾值(Calculate the Threshold,CT)，PSSN表示按邏輯結(jié)構(gòu)進(jìn)行階段節(jié)點(diǎn)設(shè)置(Set Stage Node,SSN)。

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

(4)O=(ODR1,ODR2,…,ODRi,…,ODRn|i,n∈Z+)表示輸出的各個(gè)測(cè)試報(bào)告，其中ODRi表示輸出的第i個(gè)缺陷報(bào)告(Defect Report,DR)?；谌?fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行模型框架如圖2所示。

圖2 CCSDSEM框架

2.2 分段執(zhí)行規(guī)則

為便于闡述分段符號(hào)執(zhí)行策略，現(xiàn)構(gòu)造部分代碼如下：

(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執(zhí)行過(guò)程

在測(cè)試過(guò)程中，Concolic執(zhí)行會(huì)隨機(jī)產(chǎn)生輸入測(cè)試值(如{x=3,y=13,z=5})，當(dāng)執(zhí)行else if (x>10)時(shí)，符號(hào)化執(zhí)行會(huì)生成路徑約束(x0>1)，然后Concolic執(zhí)行對(duì)邏輯判斷條件取反并對(duì)(x0<1)求解，并將得到的一個(gè)測(cè)試用例作為輸入，從而執(zhí)行不同路徑。

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

如果圈復(fù)雜度超過(guò)預(yù)先設(shè)定閾值Ф時(shí)，則對(duì)該部分代碼進(jìn)行分段執(zhí)行或優(yōu)化約束條件后再執(zhí)行；此時(shí)，因(y0<12)是取反的分支約束條件，對(duì)(y0<12)分支無(wú)任何影響，故可去掉對(duì)z的約束，可從當(dāng)前路徑條件中移除與當(dāng)前分支結(jié)果無(wú)關(guān)的約束，提高約束求解效率，降低因約束條件過(guò)于復(fù)雜而引發(fā)路徑爆炸的概率。

(2)分階段動(dòng)態(tài)符號(hào)執(zhí)行

當(dāng)在CCSDSEM框架中執(zhí)行分階段動(dòng)態(tài)符號(hào)執(zhí)行時(shí)，根據(jù)控制流順序設(shè)置檢查點(diǎn)并計(jì)算對(duì)應(yīng)代碼段的圈復(fù)雜度，當(dāng)某個(gè)圈復(fù)雜度大于預(yù)先設(shè)定的閾值Ф時(shí)，則對(duì)該段代碼單獨(dú)執(zhí)行動(dòng)態(tài)符號(hào)執(zhí)行；反復(fù)運(yùn)用此策略，直至所有代碼檢測(cè)并分解完畢，算法描述如下：

算法：分階段符號(hào)執(zhí)行策略算法

輸入:C語(yǔ)言格式的待測(cè)代碼

輸出:高圈復(fù)雜度函數(shù)名稱及復(fù)雜度值

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

//初始化模型

(2) 構(gòu)建待測(cè)代碼集I

(3) int Ф=50;

//設(shè)定閾值Ф=50

//遍歷各函數(shù)并計(jì)算函數(shù)的圈復(fù)雜度VCC

(4) int CC(Fi);

//計(jì)算VCC

(5) { inti=0;

(6) while (I!=NULL)

//當(dāng)輸入集非空時(shí)執(zhí)行

(7) {i++;

//第i個(gè)函數(shù)

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

//讀取函數(shù)Fi并求出VCC

(9) if (VCC>Ф)

//若VCC大于Ф

(10) { outputFi,VCC;

//輸出VCC

(11) temp_filei=read(Fi);

//讀取Fi代碼到temp_filei

(12) CC (temp_filei);}

//遞歸計(jì)算Fi的VCC

(13) else Symbolic_ Execution (Fi)；

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

(14) }

(15) }

當(dāng)程序的整體影響處于可控狀態(tài)下，采用此策略對(duì)被測(cè)程序按閾值進(jìn)行分階段動(dòng)態(tài)符號(hào)執(zhí)行，可降低產(chǎn)生路徑爆炸的概率，緩解因動(dòng)態(tài)符號(hào)執(zhí)行將部分值實(shí)例化而引發(fā)的路徑覆蓋不足等問(wèn)題。

3 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)通過(guò)SourceMonitor對(duì)開源項(xiàng)目GNU Binutils-2.14中部分源代碼文件進(jìn)行圈復(fù)雜度測(cè)試，選用VCC值較高的源代碼文件readelf.c進(jìn)行測(cè)試。

3.1 圈復(fù)雜度計(jì)算實(shí)驗(yàn)

實(shí)驗(yàn)進(jìn)一步對(duì)readelf.c計(jì)算圈復(fù)雜度，與本研究有關(guān)的詳細(xì)信息如表1所示。

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

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

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

顯然switch()為readelf.c的主要函數(shù)，而且明顯高于其他函數(shù)，從其Kiviat圖(如圖3所示)上可以看出各項(xiàng)指標(biāo)嚴(yán)重偏離合理區(qū)間(深色圓環(huán)區(qū)域)。

圖3 Kiviat圖

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

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

3.2 分階段動(dòng)態(tài)符號(hào)執(zhí)行實(shí)驗(yàn)

在對(duì)測(cè)試所得的VCC實(shí)驗(yàn)數(shù)據(jù)分析后發(fā)現(xiàn)：若分支情況越多、嵌入層次越深、調(diào)用函數(shù)越多且復(fù)雜，則VCC值越大。因符號(hào)執(zhí)行在VCC越大的情況下效率會(huì)嚴(yán)重降低，若將一個(gè)復(fù)雜程度分解為多個(gè)復(fù)雜度相對(duì)理想且內(nèi)聚性強(qiáng)的代碼片段來(lái)進(jìn)行分階段符號(hào)執(zhí)行，顯然具備緩解或降低路徑爆炸的功效。

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

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

3.3 局限性分析

(1)執(zhí)行分階段動(dòng)態(tài)符號(hào)執(zhí)行時(shí)，具體邏輯判斷語(yǔ)句(如case、if)及嵌套層次嚴(yán)重影響分階段情況，相對(duì)應(yīng)測(cè)試的圈復(fù)雜度之間差別也很大；尤其代碼中case語(yǔ)句趨向全部時(shí)，最簡(jiǎn)單的分階段方法為：當(dāng)case語(yǔ)句數(shù)量等于Ф時(shí)進(jìn)行分割(存在誤判)，此時(shí)VCC=Ф(如表4中序號(hào)4～9情況)。如果循環(huán)或遞歸的終止條件是符號(hào)化的，就可能會(huì)出現(xiàn)無(wú)限數(shù)量的對(duì)應(yīng)路徑，因此對(duì)循環(huán)分支數(shù)量的判定結(jié)果是衡量符號(hào)執(zhí)行樹狀狀況的重要依據(jù)。

(2)實(shí)驗(yàn)情況可以判斷出動(dòng)態(tài)符號(hào)執(zhí)行中可能產(chǎn)生路徑爆炸的不同規(guī)模。目前這種方法并不能完全固定分支的數(shù)量，故每次實(shí)驗(yàn)時(shí)結(jié)果存在誤差，但總體上可以滿足圈復(fù)雜度不高于Ф的條件。

(3)本實(shí)驗(yàn)只對(duì)單個(gè).C程序文件進(jìn)行測(cè)試，尚未對(duì)大型項(xiàng)目代碼進(jìn)行測(cè)試，也未考慮各文件之間的依賴關(guān)系等。

4 結(jié)論

本文首先介紹動(dòng)態(tài)符號(hào)執(zhí)行的相關(guān)研究現(xiàn)狀和基本概念，然后詳細(xì)分析存在的不足以及采用的分階段執(zhí)行方法，并分析路徑覆蓋率，進(jìn)而提出基于圈復(fù)雜度的階段動(dòng)態(tài)符號(hào)執(zhí)行的方法，并通過(guò)示例實(shí)驗(yàn)證明，相比于原有的方案，使用CCCSDSEM優(yōu)化框架后降低了代碼的圈復(fù)雜度并緩解了路徑爆炸。

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