沈 晴，牟永敏

北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100101

1 引言

軟件測(cè)試可以提高軟件的可靠性[1]。在軟件開發(fā)周期，軟件測(cè)試是軟件開發(fā)過程中不可或缺的環(huán)節(jié)，如果利用人工的方法實(shí)現(xiàn)測(cè)試需求，會(huì)耗費(fèi)大量人力物力，所需成本占比高達(dá)50%以上，因此研究人員致力于實(shí)現(xiàn)自動(dòng)化測(cè)試，降低軟件測(cè)試成本。隨著軟件規(guī)模日趨大型化和復(fù)雜化，及時(shí)發(fā)現(xiàn)并修復(fù)軟件中存在的錯(cuò)誤可以很大程度上避免軟件使用過程中發(fā)生故障帶來的損失，但同時(shí)也給軟件測(cè)試帶來進(jìn)一步的挑戰(zhàn)，自動(dòng)化測(cè)試的重要性日益凸顯。其中，測(cè)試用例對(duì)保證軟件測(cè)試的充分性和可靠性有著重要影響，一組合理的測(cè)試用例可以幫助測(cè)試人員找出程序中的錯(cuò)誤。人工設(shè)計(jì)測(cè)試用例需要測(cè)試人員具備豐富的經(jīng)驗(yàn)，且不可避免地受到人為因素影響，可能無法保證測(cè)試的充分性，因此，測(cè)試用例自動(dòng)生成技術(shù)對(duì)提高軟件測(cè)試的效率有著重要意義。根據(jù)測(cè)試方法的不同，可以分為四大類型：隨機(jī)測(cè)試方法、基于搜索的測(cè)試方法、模型檢測(cè)測(cè)試方法以及符號(hào)執(zhí)行測(cè)試方法[2]。

1983年Bird等人[3]提出隨機(jī)法，易于實(shí)現(xiàn)且十分高效，一些研究會(huì)將它作為基準(zhǔn)方法之一[4]，但對(duì)于較為復(fù)雜的程序，隨機(jī)法很難達(dá)到較高的覆蓋率。為保證測(cè)試用例均勻地分布在搜索空間，提出自適應(yīng)隨機(jī)測(cè)試方法[5]，但覆蓋率低的問題依然存在?；谒阉鞯臏y(cè)試用例自動(dòng)生成方法[6]將測(cè)試用例自動(dòng)生成問題轉(zhuǎn)化為函數(shù)優(yōu)化問題，并利用遺傳算法[7]、粒子群優(yōu)化算法[8]、蟻群算法[9]以及一些優(yōu)化后的進(jìn)化算法[10]等來尋找最優(yōu)解。但同樣存在總體覆蓋率較低的問題，并且很大程度上受限于適應(yīng)度函數(shù)，容易進(jìn)入局部最優(yōu)解中，尤其在大型復(fù)雜程序中效果不理想，會(huì)產(chǎn)生大量冗余用例。模型檢測(cè)方法是一種形式化驗(yàn)證方法，包括許多的驗(yàn)證技術(shù)[11]，通過模型檢測(cè)器搜索整個(gè)系統(tǒng)的狀態(tài)空間，根據(jù)生成的反例分析識(shí)別并修復(fù)軟件中的錯(cuò)誤，但是模型創(chuàng)建難度較大，不同的模型的效果差異較大，并且由于狀態(tài)爆炸問題會(huì)導(dǎo)致性能下降。

符號(hào)執(zhí)行是King[12]于1976 年提出的一種重要的形式化方法和程序分析技術(shù)，被廣泛應(yīng)用于程序測(cè)試領(lǐng)域[13]。采用抽象符號(hào)代替程序變量，程序計(jì)算的輸出被表示為輸入符號(hào)值的函數(shù)，根據(jù)程序的語義，遍歷程序的執(zhí)行空間，符號(hào)執(zhí)行技術(shù)能夠以盡可能少的測(cè)試用例實(shí)現(xiàn)高覆蓋率，從而挖掘出復(fù)雜軟件程序的深層錯(cuò)誤，但在實(shí)際應(yīng)用中不可避免地會(huì)遇到許多限制條件，如路徑爆炸、約束求解等問題。

在此基礎(chǔ)上，本文將研究粒度提升至函數(shù)，用函數(shù)調(diào)用路徑圖替代控制流圖，從函數(shù)層面分析程序執(zhí)行過程，提出一種基于函數(shù)調(diào)用路徑的測(cè)試用例生成方法，分析程序抽象語法樹得到函數(shù)調(diào)用關(guān)系和執(zhí)行路徑，結(jié)合符號(hào)執(zhí)行技術(shù)生成與函數(shù)調(diào)用路徑對(duì)應(yīng)的全局測(cè)試用例集。該方法類似于狀態(tài)合并，將語句塊合并，且最大程度保留程序信息。實(shí)現(xiàn)在不降低測(cè)試覆蓋率的同時(shí)，提高符號(hào)執(zhí)行的效率。

2 相關(guān)研究

2.1 路徑覆蓋測(cè)試技術(shù)

路徑覆蓋是軟件測(cè)試充分性的一個(gè)重要準(zhǔn)則[14]，可歸結(jié)為面向路徑的測(cè)試數(shù)據(jù)生成問題[15]，核心是選取最小測(cè)試用例集，覆蓋程序的所有可執(zhí)行路徑（如果程序圖中有環(huán)，則要求每個(gè)環(huán)至少經(jīng)過一次）。

2.1.1 基路徑分析方法

由于完整路徑集合數(shù)量過于龐大，在實(shí)際中很難實(shí)現(xiàn)，因此基本路徑測(cè)試方法應(yīng)運(yùn)而生。基于基路徑的軟件測(cè)試是一種縮小規(guī)模的路徑測(cè)試技術(shù)，最小化路徑組合的數(shù)量，減少重復(fù)測(cè)試的次數(shù)，使路徑測(cè)試得以實(shí)現(xiàn)。

目前基路徑分析主要算法有McCabe法[16]、Halstead法等。

2.1.2 函數(shù)調(diào)用路徑分析方法

基本路徑覆蓋測(cè)試在一定程度上縮小了路徑的數(shù)量，但其路徑數(shù)量會(huì)隨著程序的規(guī)模和復(fù)雜度的增大呈指數(shù)增長(zhǎng)，使得精確率不甚理想，對(duì)循環(huán)結(jié)構(gòu)帶來的在路徑數(shù)量上的影響以及重疊路徑識(shí)別的處理方法仍存在一定缺陷。

面向函數(shù)調(diào)用路徑的思想是在回歸測(cè)試和路徑覆蓋測(cè)試基礎(chǔ)上發(fā)展起來的，簡(jiǎn)化了面向基路徑的測(cè)試缺陷，使得面向基路徑的測(cè)試工作量大幅減少?；诤瘮?shù)調(diào)用關(guān)系的路徑覆蓋測(cè)試技術(shù)以路徑覆蓋為基礎(chǔ)，將函數(shù)調(diào)用與控制邏輯結(jié)合起來，把路徑單元從語句提升至函數(shù)，通過對(duì)被測(cè)程序的源代碼進(jìn)行靜態(tài)和動(dòng)態(tài)分析，分別獲取包含控制邏輯的靜態(tài)函數(shù)調(diào)用路徑以及動(dòng)態(tài)函數(shù)調(diào)用序列，將動(dòng)態(tài)獲取的序列轉(zhuǎn)化成靜態(tài)邏輯路徑，建立測(cè)試用例和路徑上的對(duì)應(yīng)關(guān)系[17]。

2.2 符號(hào)執(zhí)行技術(shù)

符號(hào)執(zhí)行自提出以來，經(jīng)過了傳統(tǒng)符號(hào)執(zhí)行、動(dòng)態(tài)符號(hào)執(zhí)行、選擇性符號(hào)執(zhí)行三個(gè)發(fā)展過程[18]，但仍存在一些困難。

路徑爆炸問題是制約符號(hào)執(zhí)行在現(xiàn)實(shí)程序分析中應(yīng)用的主要因素。在符號(hào)執(zhí)行的分析過程中，每個(gè)分支節(jié)點(diǎn)都會(huì)衍生出兩個(gè)符號(hào)執(zhí)行實(shí)例，就串行程序而言，一個(gè)具有n個(gè)條件語句的程序段就有可能包含2n條路徑。

目前已有狀態(tài)合并、冗余路徑剪枝、采用啟發(fā)式搜索方法對(duì)程序路徑空間進(jìn)行搜索以及優(yōu)化回歸測(cè)試集等方法緩解路徑爆炸問題，但仍存在一些問題，比如狀態(tài)合并會(huì)一定程度上影響程序分析的準(zhǔn)確性；啟發(fā)式搜索在面臨長(zhǎng)路徑搜索時(shí)，路徑的計(jì)算和篩選需要耗費(fèi)較長(zhǎng)時(shí)間，且可能無法得到符合的路徑。

3 基于函數(shù)調(diào)用關(guān)系的路徑優(yōu)化

目前能夠生成函數(shù)關(guān)系圖的工具，如CallTree、Codeviz、Source Insight、DGML 等，生成的函數(shù)調(diào)用關(guān)系并不包含控制邏輯，屬于函數(shù)包含關(guān)系圖；另一類工具，如 AlgoView、GNU CFlow 等，基于語句的分析，同樣不能得到函數(shù)粒度的調(diào)用路徑。

文獻(xiàn)[19]對(duì)比了正則技術(shù)、開源工具以及語法樹三種提取函數(shù)調(diào)用關(guān)系的方法。對(duì)于正則技術(shù)，通過多次掃描源代碼以匹配函數(shù)調(diào)用相關(guān)信息，獲取函數(shù)調(diào)用關(guān)系。對(duì)于開源工具，通過CTags和Cscope獲取并解析代碼樹中的索引，生成基于函數(shù)調(diào)用的依賴關(guān)系，獲取函數(shù)調(diào)用信息。語法樹主要是通過Yacc 和Lex 構(gòu)建語法樹來提取函數(shù)調(diào)用關(guān)系。從準(zhǔn)確率上說，三者中基于語法樹的提取方法效果最佳，因此本文基于抽象語法樹提取函數(shù)關(guān)鍵信息。

圖1 函數(shù)調(diào)用路徑生成過程

3.1 整體框架

提出一種函數(shù)調(diào)用路徑靜態(tài)提取方法，通過分析抽象語法樹和字節(jié)碼序列，得到函數(shù)間的依賴關(guān)系以及相應(yīng)的控制條件；設(shè)計(jì)關(guān)鍵信息提取算法，獲取函數(shù)調(diào)用關(guān)系，從而構(gòu)建函數(shù)調(diào)用關(guān)系模型；以函數(shù)為節(jié)點(diǎn)，同時(shí)結(jié)合程序控制條件，生成包含控制信息的函數(shù)調(diào)用關(guān)系圖，如圖1所示。

3.2 函數(shù)調(diào)用路徑生成

3.2.1 相關(guān)定義

定義1（函數(shù)調(diào)用關(guān)系）指兩個(gè)函數(shù)之間的調(diào)用，用R表示，其中R={(Fi,Fj)|Fi是源函數(shù)，F(xiàn)j是被調(diào)用的函數(shù)} 。如果在源函數(shù)中存在多個(gè)函數(shù)調(diào)用，則按調(diào)用的先后順序表示調(diào)用關(guān)系，如R={(F0,F1),(F1,F2 )}，表示源函數(shù)中的函數(shù)調(diào)用關(guān)系為F0 →F1 →F2。

定義2（函數(shù)調(diào)用關(guān)系模型）表示單個(gè)函數(shù)的函數(shù)調(diào)用關(guān)系，用三元組T(M,R,S)表示，M是函數(shù)集合，R表示函數(shù)間的調(diào)用關(guān)系，S表示源函數(shù)。

圖2代碼段中main函數(shù)，用函數(shù)調(diào)用關(guān)系模型T(M,R,S)表示，其中M={main,f1,f2,f3},R={(main,f1,O),(f1,f2,O),(f2,f3,B)},S={main},O表示順序調(diào)用，B表示分支調(diào)用。

圖2 示例源代碼

定義3（函數(shù)調(diào)用路徑）根據(jù)函數(shù)調(diào)用關(guān)系得到的由程序入口到出口的一個(gè)函數(shù)名序列，表示為Pi={Fi1,Fi2,…,Fim},Fij為函數(shù)名，F(xiàn)ij和Fij+1的關(guān)系表示為順序執(zhí)行或Fij調(diào)用Fij+1[20]。

定義4（函數(shù)調(diào)用路徑集）函數(shù)調(diào)用路徑的集合，表示為B(S,C)={P1,P2,…,Pn},C是函數(shù)調(diào)用關(guān)系準(zhǔn)則，用來判斷函數(shù)是否被調(diào)用以及函數(shù)以何種方式被調(diào)用。例如：v1=F(x)，其中v1表示變量，F(xiàn)(x)表示函數(shù)；語句v1=F(x)，表示將函數(shù)F(x)返回值賦值給v1，故該語句以函數(shù)返回值參與表達(dá)式運(yùn)算的方式調(diào)用函數(shù)，S是源代碼，Pi是函數(shù)調(diào)用路徑[21]。

定義5（函數(shù)調(diào)用路徑圖）表示為一個(gè)有向圖FCG(V,R),V是FCG中所有節(jié)點(diǎn)的有窮非空集合，R是相連節(jié)點(diǎn)之間邊的有限集合，滿足R?V×V，具體描述如下：

其中，funcSet是函數(shù)調(diào)用路徑圖中的節(jié)點(diǎn)集合；R是函數(shù)調(diào)用路徑圖中節(jié)點(diǎn)之間的關(guān)系集合，P(x,y)表示從x到y(tǒng)的一條通路，C(x,y)表示從x到y(tǒng)通路上的控制條件。

3.2.2 函數(shù)關(guān)鍵信息抽取

以Python語言為例，抽象語法樹是一個(gè)深層嵌套的樹形結(jié)構(gòu)，鑒于需要對(duì)不同類型節(jié)點(diǎn)進(jìn)行不同的處理，本文采用訪問者模式實(shí)現(xiàn)對(duì)抽象語法樹的遍歷，使節(jié)點(diǎn)類與作用于自身的操作相互獨(dú)立。

步驟1訪問者從抽象語法樹根節(jié)點(diǎn)開始對(duì)抽象語法樹中的關(guān)鍵節(jié)點(diǎn)類型進(jìn)行遍歷，基本關(guān)鍵節(jié)點(diǎn)類型如表1所示。

表1 基本關(guān)鍵節(jié)點(diǎn)類型

步驟2判定節(jié)點(diǎn)類型是否為關(guān)鍵節(jié)點(diǎn)類型。

步驟3如果節(jié)點(diǎn)類型是關(guān)鍵節(jié)點(diǎn)類型，則通過抽象訪問者進(jìn)行轉(zhuǎn)發(fā)，直接訪問具體訪問者visit_Key(node)，（如visit_Assign(node)是基于賦值關(guān)鍵字的訪問者）。提取相應(yīng)的關(guān)鍵信息；反之，則調(diào)用通用訪問者，統(tǒng)一處理。

步驟4對(duì)提取到的所有信息進(jìn)行約減和自動(dòng)補(bǔ)全，得到生成函數(shù)調(diào)用關(guān)系所需的關(guān)鍵信息列表。

其中，關(guān)鍵節(jié)點(diǎn)類型具體算法描述如下：

算法1關(guān)鍵信息抽取算法

輸入：抽象語法樹文本AST Text

輸出：關(guān)鍵信息列表KeyInfoList，函數(shù)字典FuncInfoDict

1.Begin

2.tree<-AST Text；//獲取 ast對(duì)象

表2 分支語法結(jié)構(gòu)-關(guān)系模型

3.FOR node in tree DO //遍歷每一個(gè)節(jié)點(diǎn)

4.type<-node.type；//根據(jù)節(jié)點(diǎn)類型，調(diào)用訪問者

5.IF existFunc（type） THEN

6.visit_Key（node）；//如果存在具體訪問者

7.ELSE generic_visito（rnode）；//如果不存在

8.ENDIF

9.END FOR

10.FuncInfoDict<-completeFuncDic（t）；//補(bǔ)全函數(shù)字典

11.//補(bǔ)全關(guān)鍵信息列表

12.KeyInfoList<-completeFuncInfo（FuncInfoDict）；

13.END

在抽象訪問者中數(shù)據(jù)結(jié)構(gòu)的每個(gè)節(jié)點(diǎn)都能夠接受來自訪問者的調(diào)用，該算法結(jié)合先序遍歷的思想，從根節(jié)點(diǎn)開始向訪問者傳入節(jié)點(diǎn)對(duì)象，而訪問者則反過來執(zhí)行基于該節(jié)點(diǎn)對(duì)象的操作，提取函數(shù)關(guān)鍵信息列表。

3.2.3 語句結(jié)構(gòu)分析

（1）分支調(diào)用關(guān)系

語法中的分支結(jié)構(gòu)大致分為三種：缺省型、標(biāo)準(zhǔn)型和多分支型。對(duì)應(yīng)的關(guān)系模型如表2所示。

（2）循環(huán)調(diào)用關(guān)系

常用的循環(huán)控制關(guān)鍵字包括while、for等，且循環(huán)控制流結(jié)構(gòu)相似。對(duì)應(yīng)的關(guān)系模型如表3所示。

表3 循環(huán)語法結(jié)構(gòu)-關(guān)系模型

這種語法與if-else 的結(jié)構(gòu)類似，結(jié)合Z 路徑覆蓋思想，采用二分支結(jié)構(gòu)，兩個(gè)分支分別為執(zhí)行循環(huán)體和不執(zhí)行循環(huán)體。

3.2.4 函數(shù)調(diào)用關(guān)系模型的建立

以算法1的輸出作為輸入，即以關(guān)鍵信息列表Key-InfoList為輸入，構(gòu)建局部調(diào)用關(guān)系模型，再將局部關(guān)系模型以一定規(guī)則組合為全局函數(shù)調(diào)用關(guān)系模型。

步驟1遍歷關(guān)鍵信息列表中的每一個(gè)元素，判斷元素類型，執(zhí)行相應(yīng)操作。

步驟2如果元素是第一個(gè)節(jié)點(diǎn)，則創(chuàng)建新的空函數(shù)調(diào)用關(guān)系模型；如果元素是分支或循環(huán)的開始或結(jié)束標(biāo)記，如if、while 和for 等關(guān)鍵字，根據(jù)函數(shù)調(diào)用關(guān)系模型構(gòu)建原理，向左插入子模型；如果元素是其他分支標(biāo)記，如elif、else等關(guān)鍵字，則向右插入子模型，表分支調(diào)用。得到局部調(diào)用關(guān)系模型。

步驟3遍歷局部模型獲取標(biāo)識(shí)為Begin 的作為程序入口點(diǎn)。

步驟4從入口點(diǎn)開始，將每一個(gè)函數(shù)的調(diào)用關(guān)系模型依次插入到全局的函數(shù)調(diào)用關(guān)系模型中，插入的模型的葉節(jié)點(diǎn)的左孩子指向被替代的那個(gè)函數(shù)的左孩子。

步驟5遍歷全局函數(shù)調(diào)用關(guān)系模型，獲得全局函數(shù)調(diào)用路徑集合。

具體算法描述如下：

算法2全局函數(shù)調(diào)用關(guān)系模型建立算法

輸入：關(guān)鍵信息列表KeyInfoList

輸出：全局調(diào)用關(guān)系模型GlobalModel

變量：entryModel：程序入口模型

ModelList：局部調(diào)用關(guān)系模型

1.Begin

2.FOR i<-0 to KeyInfoList.length DO

3.flag<-FALSE

4.list<-KeyInfoLis（ti）

5.FOR j<-0 to list.length DO

6.IF lis（tj）.index（）==0 THEN

7.model<-createMode（l“Begin”）

8.ENDIF

9.//如果是第一個(gè)節(jié)點(diǎn)，則創(chuàng)建節(jié)點(diǎn)

10.IF lis（tj）==“elif”or lis（tj）==“else”THEN

11.flag<-TRUE //標(biāo)識(shí)置真

12.ENDIF //如果節(jié)點(diǎn)類型是分支關(guān)鍵字

13.IF lis（tj）.index（）==list.length THEN

14.model.insertLef（t“END”）

15.ENDIF

16.IF flag==FALSE THEN

17.model.insertLef（tlis（tj））

18.ELSE model.insertRigh（tlis（tj））

19.ENDIF

20.ENDFOR

21.IF i==0 TNEN

22.entryModel<-model

23.ELSE ModelList<-ModelList+model

24.ENDFOR

25.FOR i<-0 to entryModel.length DO

26.value<-entryMode（li）

27.FOR j<-0 to ModelList DO

28.model<-ModelLis（tj）

29.IF model.containsHead（value） THEN

30.value.data<-model.data；

31.model.leaf<-value.subMode（l）；

32.value.leftchild<-model.leftchild；

33.ENDIF

34.ENDFOR

35.GlobalModel<-GlobalModel+entryModel；

36.ENDFOR

37.END

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

4.1 輸入變量與控制變量的影響關(guān)系

由于不是所有控制條件中的變量都能直接作為測(cè)試用例輸入程序，因此需要分析控制變量與輸入變量之間的關(guān)系，本文利用信息流規(guī)則對(duì)信息流進(jìn)行分析。

目前針對(duì)高級(jí)語言中賦值語句、條件語句、循環(huán)語句等信息流規(guī)則較為簡(jiǎn)單，因此提出一種擴(kuò)展的語句信息流規(guī)則，具體定義如下：

（1）賦值語句

規(guī)則1v1=v2；則有＜v2→v1,v1=v2＞。

規(guī)則2v1=v2op,…,opvn；op代表運(yùn)算符，則有＜v2→v1,v1=v2op,…,opvn ＞,…, ＜v2→v1,v1=v2op,…,opvn ＞。

規(guī)則3v0--,--v0,v0++,++v0；則有＜v0→v0;v0=v0+1＞。

規(guī)則4v0op=v1；則 有＜v0→v0∧v1→v0;v0=v0opv1＞。

規(guī)則 5v0op0=v1op1…vi opi…opn-1vn(1 ≤i≤n)；則有＜v0→v0∧v1→v0∧…∧vi→v0∧…∧vn→v0;v0=v0op0(v1op1…vi opi…opn-1vn)＞。

（2）函數(shù)調(diào)用語句

規(guī)則6v1=F(x),x為變量或表達(dá)式；則有＜x→R（R為F(x)的返回值集合），R→v1,F(x)前置條件→F(x)后置條件；v1=R ＞。

規(guī)則7v1=F(x1,x2,…,xn)(1 ≤i≤n),xi為變量或表達(dá)式；則有＜xi→R(R為F(x)的返回值集合），R→v1,F(x1,x2,…,xn)前置條件 →F(x1,x2,…,xn)后置條件＞。

（3）控制語句

規(guī)則8if/while(v0op0vc0…opi vci)v1=n（n為常量,1 ≤i,vc代表常量或變量）；則有＜v0→＜v0→v1,vc0→v1,…,vci→v1;(v0op0vc0…opi vci)→ (v1=v2)＞。

規(guī)則9if/while(F(x)op0vc0…opi vci)v1=n（n為常量，1 ≤i,vc代表常量或變量）；則有＜x→R（R為F(x)的返回值集合），R→v1,vc0→v1,…,vci→v1;(v0op0vc0…opi vci)→ (v1=n)＞。

根據(jù)上述信息流規(guī)則分析得到兩個(gè)變量之間的關(guān)系并進(jìn)行組合，得到控制流影響關(guān)系樹，每棵樹的根節(jié)點(diǎn)都是輸入變量，葉子節(jié)點(diǎn)是要分析的控制變量。具體算法如下：

算法3控制變量與輸入變量關(guān)系分析算法

輸入：源代碼

輸出：控制變量與輸入變量之間的關(guān)系表達(dá)式

變量：inputList：輸入變量集合

controlList：控制變量集合

relationList：變量之間的關(guān)系集合

relation：輸入變量與控制變量之間的關(guān)系

1.Begin

2./*讀取Python源代碼，分析得到輸入變量集合、控

3.制變量集合，依據(jù)信息流規(guī)則分析變量的關(guān)系*/

4.FOR i<-controlList.size（）-1 to 0 DO

5.//如果該變量已分析過，則跳出

6.IF controlList.ge（ti）THEN break；

7.END IF

8.//如果待分析變量是輸入變量，則繼續(xù)循環(huán)

9.IF controlList.get(i) in inputListTHEN continue；

10.END IF

11.FOR j<-relationList.size（）-1 to 0 DO

12./*如果待分析變量是關(guān)系樹的子節(jié)點(diǎn)，將此關(guān)

13.系樹加入到此變量的關(guān)系樹集合中*/

14.IF controlList.ge（ti）is relationList.childnode

15.THENrelation=combine（relation，relationList.ge（ti））

16.END IF

17.ENDFOR

18.print relation

19.ENDFOR

20.END

遍歷每棵控制流影響樹：從葉子節(jié)點(diǎn)開始，自底向上廣度優(yōu)先遍歷，將路徑上的關(guān)系表達(dá)式以圖3所示遞推公式鏈的形式組合輸出，得到控制變量與輸入變量的關(guān)系鏈。

圖3 遞推公式鏈

4.2 變量符號(hào)化

以圖4中源代碼為例，根據(jù)算法1、算法2可得到圖5所示函數(shù)調(diào)用路徑圖。

圖4 示例代碼

圖5 函數(shù)調(diào)用路徑圖

根據(jù)算法3 生成控制變量與輸入變量的遞推公式鏈，得到控制變量與輸入變量之間的關(guān)系表達(dá)式集合。

分析源代碼得到輸入變量集合，為每一個(gè)輸入變量設(shè)置符號(hào)值，推導(dǎo)出控制變量的符號(hào)表達(dá)式。分析結(jié)果如表4所示。

表4 變量符號(hào)化結(jié)果

利用函數(shù)調(diào)用關(guān)系模型和控制流分析得到圖6 所示程序的符號(hào)執(zhí)行樹，符號(hào)執(zhí)行樹的葉子節(jié)點(diǎn)為程序函數(shù)調(diào)用路徑對(duì)應(yīng)的符號(hào)表達(dá)式。

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

4.3 約束求解

采用深度優(yōu)先搜索算法（DFS）遍歷符號(hào)執(zhí)行樹，收集每條函數(shù)調(diào)用路徑對(duì)應(yīng)的符號(hào)表達(dá)式。利用SMT求解器對(duì)符號(hào)表達(dá)式進(jìn)行求解，SMT是一階邏輯表達(dá)式，其在編譯優(yōu)化，形式化驗(yàn)證都可以用到該模型理論，符號(hào)執(zhí)行測(cè)試中利用該模型理論對(duì)于收集的路徑約束組成的表達(dá)式求解，比如收集到a＜b∧b-5=c路徑條件下的一組表達(dá)式進(jìn)行SMT 求解，根據(jù)其理論模型會(huì)就計(jì)算出一組值{a=5,b=10,c=5}，這組解即為一組測(cè)試用例數(shù)據(jù)。SMT求解器從輸入到輸出的執(zhí)行流程如圖7所示。

圖7 SMT約束求解執(zhí)行流程

微軟的Z3 求解器能夠滿足幾乎所有求解理論，求解范圍更廣，對(duì)于復(fù)雜程序下的非線性約束表達(dá)式也有較好的表現(xiàn)，因此選用Z3 求解器對(duì)符號(hào)表達(dá)式進(jìn)行求解，得到對(duì)應(yīng)的測(cè)試用例集合。

4.4 冗余路徑剪枝

在程序分析過程中有些路徑是冗余的，冗余路徑剪枝可以簡(jiǎn)化路徑空間，提高分析效率，總結(jié)出以下兩種路徑可對(duì)其進(jìn)行剪枝處理：

（1）如果兩條路徑到達(dá)同一個(gè)程序點(diǎn)，并且到達(dá)該程序點(diǎn)的約束集相同，則可以對(duì)其中一條進(jìn)行剪枝。

（2）對(duì)每條路徑的約束信息進(jìn)行可滿足性判定，如果該約束是不可滿足的，則意味著不存在能驅(qū)動(dòng)該路徑具體執(zhí)行的測(cè)試用例，該路徑為冗余路徑，可以直接進(jìn)行剪枝。

（3）圖8 左側(cè)為示例源代碼，右側(cè)是其對(duì)應(yīng)的函數(shù)調(diào)用路徑圖。以此為例，分析冗余路徑剪枝策略。

圖8 示例程序?qū)?yīng)函數(shù)調(diào)用路徑圖

由本文測(cè)試用例自動(dòng)生成算法可得到3 條測(cè)試用例，將其作為程序輸入分別執(zhí)行程序，可得到每條測(cè)試用例對(duì)應(yīng)的函數(shù)實(shí)際執(zhí)行路徑，如表5所示。

表5 測(cè)試用例執(zhí)行路徑

以TC1為例，把a(bǔ)=2 作為程序輸入執(zhí)行程序，從語句粒度分析，將先后經(jīng)過源代碼第15、16、17、18、01、02、03、04、07、08、06、11、12、02、03、04、07、08、06、11、12行；從函數(shù)粒度分析，則先后經(jīng)過main、f1、f2、f4、f2、f4，故 函 數(shù) 的 實(shí) 際 執(zhí) 行 路 徑 為main→f1 →f2 →f4 →f2 →f4 。

當(dāng) 0 ＜a≤3 即執(zhí)行測(cè)試用例a=2 時(shí)，程序?qū)嶋H執(zhí)行過程中函數(shù)間調(diào)用關(guān)系R0＜a≤3={(main,f1),(f1,f2),(f2,f4)}；當(dāng)a＞3 即執(zhí)行測(cè)試用例a=4 時(shí)，函數(shù)間的調(diào)用關(guān)系Ra＞3={(main,f1),(f1,f2),(f1,f3),(f2,f4)}；當(dāng)“a≤0 ∪a不是整數(shù)”即執(zhí)行測(cè)試用例a=0 時(shí)，函數(shù)調(diào)用關(guān)系Ra≤0∪a不是整數(shù)={(main,f5)} ，分析可知R0＜a≤3?Ra＞3，即TC1 實(shí)際執(zhí)行路徑的函數(shù)調(diào)用關(guān)系集合是TC2 實(shí)際執(zhí)行路徑的函數(shù)調(diào)用關(guān)系集合的子集，同時(shí)TC1實(shí)際執(zhí)行路徑中包含的函數(shù)集合也是TC2 的子集。因此在函數(shù)級(jí)別TC2包含TC1，表6進(jìn)一步分析TC1、TC2的語句覆蓋情況，1表示語句被覆蓋，0表示未被覆蓋。

根據(jù)表6 可知，TC2 的語句覆蓋集包含TC1 的語句覆蓋集，因此在語句粒度TC2 可以完全囊括TC1 的執(zhí)行語句，故TC1 對(duì)應(yīng)的路徑在此例中為冗余路徑，進(jìn)行剪枝。

表6 語句覆蓋情況

如若將此段代碼修改為圖9所示，則TC1執(zhí)行語句集合中的09 行無法被TC2 囊括，此時(shí)不能對(duì)TC1 對(duì)應(yīng)的路徑進(jìn)行剪枝操作。

圖9 變更后示例程序

5 實(shí)驗(yàn)分析

評(píng)測(cè)方法主要通過兩個(gè)實(shí)驗(yàn)進(jìn)行驗(yàn)證，實(shí)驗(yàn)1 從github 下載（https：//github.com/tianxy0621/TT.git）五個(gè)不同規(guī)模、內(nèi)含多種語法結(jié)構(gòu)的Python 實(shí)例源代碼：_color.py、_pycallgraph.py、_config.py、_tracer.py、_memory_profiler.py。

以此作為數(shù)據(jù)集并用本文的算法分別進(jìn)行實(shí)驗(yàn)，自動(dòng)生成程序的測(cè)試用例集合，分析隨程序規(guī)模的擴(kuò)大，覆蓋率、效率等因素的變化。實(shí)驗(yàn)2 采用同實(shí)驗(yàn)1 的數(shù)據(jù)集，將本文算法生成的函數(shù)調(diào)用路徑數(shù)與傳統(tǒng)符號(hào)執(zhí)行算法路徑條數(shù)進(jìn)行比較，并分析其原因。

表7 實(shí)驗(yàn)1對(duì)比結(jié)果

表8 實(shí)驗(yàn)2對(duì)比結(jié)果

5.1 實(shí)驗(yàn)1

為了計(jì)算測(cè)試用例自動(dòng)生成工具生成的測(cè)試用例覆蓋率，使用插裝技術(shù)計(jì)算被測(cè)程序動(dòng)態(tài)執(zhí)行的路徑條數(shù)，將生成的測(cè)試用例作為程序的輸入，動(dòng)態(tài)獲得執(zhí)行的函數(shù)調(diào)用路徑，根據(jù)覆蓋率公式：

計(jì)算本文算法對(duì)于不同規(guī)模程序的覆蓋率，結(jié)果如圖10所示。

圖10 覆蓋率變化趨勢(shì)圖

實(shí)驗(yàn)中執(zhí)行時(shí)間、函數(shù)調(diào)用路徑條數(shù)以及測(cè)試用例個(gè)數(shù)等其他指標(biāo)數(shù)據(jù)的綜合比較如表7所示。

從表7 中數(shù)據(jù)可以看出隨程序規(guī)模的增加函數(shù)調(diào)用路徑條數(shù)增加，同時(shí)生成的測(cè)試用例個(gè)數(shù)也隨之增加。

結(jié)合圖10可以看出，當(dāng)源程序規(guī)模較大時(shí)，可以保證較高的覆蓋率和效率，但相比小規(guī)模的程序，覆蓋率有所下降，原因主要有兩點(diǎn)：一是程序中可能存在不可達(dá)路徑，導(dǎo)致動(dòng)態(tài)執(zhí)行路徑小于函數(shù)調(diào)用路徑數(shù)；另一個(gè)可能的原因是設(shè)計(jì)的信息流規(guī)則考慮不夠充分，使得對(duì)復(fù)雜語句結(jié)構(gòu)的分析不夠準(zhǔn)確。因此下一步研究工作是分析不可達(dá)路徑以及完善程序信息流分析算法。

5.2 實(shí)驗(yàn)2

實(shí)驗(yàn)2 數(shù)據(jù)集與實(shí)驗(yàn)1 相同，利用本文算法與傳統(tǒng)符號(hào)執(zhí)行算法生成的路徑條數(shù)進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖11、表8所示。

圖11 傳統(tǒng)算法對(duì)比結(jié)果

基于函數(shù)調(diào)用路徑的符號(hào)執(zhí)行算法首先構(gòu)建函數(shù)調(diào)用關(guān)系模型，從函數(shù)角度出發(fā)分析程序，并生成函數(shù)粒度的符號(hào)執(zhí)行樹，利用符號(hào)執(zhí)行技術(shù)求解測(cè)試用例。

最終結(jié)果表明，相比于傳統(tǒng)符號(hào)執(zhí)行算法，該方法有效縮減了路徑條數(shù)，減少了生成的測(cè)試用例個(gè)數(shù)。

6 結(jié)束語

測(cè)試用例自動(dòng)生成技術(shù)目前仍然是軟件測(cè)試自動(dòng)化的重點(diǎn)研究?jī)?nèi)容，用最少的測(cè)試用例達(dá)到更高的覆蓋率并找到最多的錯(cuò)誤是軟件測(cè)試的目標(biāo)。本文利用函數(shù)調(diào)用路徑對(duì)符號(hào)執(zhí)行進(jìn)行優(yōu)化，通過提取字節(jié)碼序列和抽象語法樹中的關(guān)鍵信息得到函數(shù)調(diào)用路徑圖，將其與符號(hào)執(zhí)行技術(shù)相結(jié)合，約束求解生成程序的測(cè)試用例集合。

此方法將分析粒度提升至函數(shù)，減少路徑數(shù)以及約束表達(dá)式的數(shù)量，一定程度上解決符號(hào)執(zhí)行的路徑爆炸問題。從實(shí)驗(yàn)結(jié)果可知，本文方法相比較于傳統(tǒng)方法，可在不降低覆蓋率的條件下，有效減少測(cè)試用例條數(shù)從而提高測(cè)試效率。