函數(shù)調用路徑測試用例自動生成的方法研究

沈 晴，牟永敏

北京信息科技大學 計算機學院，北京 100101

1 引言

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

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

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

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

2 相關研究

2.1 路徑覆蓋測試技術

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

2.1.1 基路徑分析方法

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

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

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

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

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

2.2 符號執(zhí)行技術

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

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

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

3 基于函數(shù)調用關系的路徑優(yōu)化

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

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

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

3.1 整體框架

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

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

3.2.1 相關定義

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

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

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

圖2 示例源代碼

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

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

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

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

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

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

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

表1 基本關鍵節(jié)點類型

步驟2判定節(jié)點類型是否為關鍵節(jié)點類型。

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

步驟4對提取到的所有信息進行約減和自動補全，得到生成函數(shù)調用關系所需的關鍵信息列表。

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

算法1關鍵信息抽取算法

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

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

1.Begin

2.tree<-AST Text；//獲取 ast對象

表2 分支語法結構-關系模型

3.FOR node in tree DO //遍歷每一個節(jié)點

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

5.IF existFunc（type） THEN

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

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

8.ENDIF

9.END FOR

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

11.//補全關鍵信息列表

12.KeyInfoList<-completeFuncInfo（FuncInfoDict）；

13.END

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

3.2.3 語句結構分析

（1）分支調用關系

語法中的分支結構大致分為三種：缺省型、標準型和多分支型。對應的關系模型如表2所示。

（2）循環(huán)調用關系

常用的循環(huán)控制關鍵字包括while、for等，且循環(huán)控制流結構相似。對應的關系模型如表3所示。

表3 循環(huán)語法結構-關系模型

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

3.2.4 函數(shù)調用關系模型的建立

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

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

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

步驟3遍歷局部模型獲取標識為Begin 的作為程序入口點。

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

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

具體算法描述如下：

算法2全局函數(shù)調用關系模型建立算法

輸入：關鍵信息列表KeyInfoList

輸出：全局調用關系模型GlobalModel

變量：entryModel：程序入口模型

ModelList：局部調用關系模型

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.//如果是第一個節(jié)點，則創(chuàng)建節(jié)點

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

11.flag<-TRUE //標識置真

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

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 符號化執(zhí)行

4.1 輸入變量與控制變量的影響關系

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

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

（1）賦值語句

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

規(guī)則2v1=v2op,…,opvn；op代表運算符，則有＜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ù)調用語句

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

規(guī)則7v1=F(x1,x2,…,xn)(1 ≤i≤n),xi為變量或表達式；則有＜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ī)則分析得到兩個變量之間的關系并進行組合，得到控制流影響關系樹，每棵樹的根節(jié)點都是輸入變量，葉子節(jié)點是要分析的控制變量。具體算法如下：

算法3控制變量與輸入變量關系分析算法

輸入：源代碼

輸出：控制變量與輸入變量之間的關系表達式

變量：inputList：輸入變量集合

controlList：控制變量集合

relationList：變量之間的關系集合

relation：輸入變量與控制變量之間的關系

1.Begin

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

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

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./*如果待分析變量是關系樹的子節(jié)點，將此關

13.系樹加入到此變量的關系樹集合中*/

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é)點開始，自底向上廣度優(yōu)先遍歷，將路徑上的關系表達式以圖3所示遞推公式鏈的形式組合輸出，得到控制變量與輸入變量的關系鏈。

圖3 遞推公式鏈

4.2 變量符號化

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

圖4 示例代碼

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

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

分析源代碼得到輸入變量集合，為每一個輸入變量設置符號值，推導出控制變量的符號表達式。分析結果如表4所示。

表4 變量符號化結果

利用函數(shù)調用關系模型和控制流分析得到圖6 所示程序的符號執(zhí)行樹，符號執(zhí)行樹的葉子節(jié)點為程序函數(shù)調用路徑對應的符號表達式。

圖6 符號執(zhí)行樹

4.3 約束求解

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

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

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

4.4 冗余路徑剪枝

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

（1）如果兩條路徑到達同一個程序點，并且到達該程序點的約束集相同，則可以對其中一條進行剪枝。

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

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

圖8 示例程序對應函數(shù)調用路徑圖

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

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

以TC1為例，把a=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ù) 的 實 際 執(zhí) 行 路 徑 為main→f1 →f2 →f4 →f2 →f4 。

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

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

表6 語句覆蓋情況

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

圖9 變更后示例程序

5 實驗分析

評測方法主要通過兩個實驗進行驗證，實驗1 從github 下載（https：//github.com/tianxy0621/TT.git）五個不同規(guī)模、內含多種語法結構的Python 實例源代碼：_color.py、_pycallgraph.py、_config.py、_tracer.py、_memory_profiler.py。

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

表7 實驗1對比結果

表8 實驗2對比結果

5.1 實驗1

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

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

圖10 覆蓋率變化趨勢圖

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

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

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

5.2 實驗2

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

圖11 傳統(tǒng)算法對比結果

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

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

6 結束語

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

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