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

沈 晴，牟永敏

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

1 引言

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

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

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

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

2 相關研究

2.1 路徑覆蓋測試技術

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

2.1.1 基路徑分析方法

由于完整路徑集合數量過于龐大，在實際中很難實現，因此基本路徑測試方法應運而生?；诨窂降能浖y試是一種縮小規模的路徑測試技術，最小化路徑組合的數量，減少重復測試的次數，使路徑測試得以實現。

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

2.1.2 函數調用路徑分析方法

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

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

2.2 符號執行技術

符號執行自提出以來，經過了傳統符號執行、動態符號執行、選擇性符號執行三個發展過程[18]，但仍存在一些困難。

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

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

3 基于函數調用關系的路徑優化

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

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

圖1 函數調用路徑生成過程

3.1 整體框架

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

3.2 函數調用路徑生成

3.2.1 相關定義

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

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

圖2代碼段中main函數，用函數調用關系模型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（函數調用路徑）根據函數調用關系得到的由程序入口到出口的一個函數名序列，表示為Pi={Fi1,Fi2,…,Fim},Fij為函數名，Fij和Fij+1的關系表示為順序執行或Fij調用Fij+1[20]。

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

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

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

3.2.2 函數關鍵信息抽取

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

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

表1 基本關鍵節點類型

步驟2判定節點類型是否為關鍵節點類型。

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

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

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

算法1關鍵信息抽取算法

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

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

1.Begin

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

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

3.FOR node in tree DO //遍歷每一個節點

4.type<-node.type；//根據節點類型，調用訪問者

5.IF existFunc（type） THEN

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

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

8.ENDIF

9.END FOR

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

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

12.KeyInfoList<-completeFuncInfo（FuncInfoDict）；

13.END

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

3.2.3 語句結構分析

（1）分支調用關系

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

（2）循環調用關系

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

表3 循環語法結構-關系模型

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

3.2.4 函數調用關系模型的建立

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

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

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

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

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

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

具體算法描述如下：

算法2全局函數調用關系模型建立算法

輸入：關鍵信息列表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.//如果是第一個節點，則創建節點

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

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

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

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 符號化執行

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

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

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

（1）賦值語句

規則1v1=v2；則有＜v2→v1,v1=v2＞。

規則2v1=v2op,…,opvn；op代表運算符，則有＜v2→v1,v1=v2op,…,opvn ＞,…, ＜v2→v1,v1=v2op,…,opvn ＞。

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

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

規則 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）函數調用語句

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

規則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）控制語句

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

規則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)＞。

根據上述信息流規則分析得到兩個變量之間的關系并進行組合，得到控制流影響關系樹，每棵樹的根節點都是輸入變量，葉子節點是要分析的控制變量。具體算法如下：

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

輸入：源代碼

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

變量：inputList：輸入變量集合

controlList：控制變量集合

relationList：變量之間的關系集合

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

1.Begin

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

3.制變量集合，依據信息流規則分析變量的關系*/

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

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

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

7.END IF

8.//如果待分析變量是輸入變量，則繼續循環

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

10.END IF

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

12./*如果待分析變量是關系樹的子節點，將此關

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

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

圖3 遞推公式鏈

4.2 變量符號化

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

圖4 示例代碼

圖5 函數調用路徑圖

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

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

表4 變量符號化結果

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

圖6 符號執行樹

4.3 約束求解

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

圖7 SMT約束求解執行流程

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

4.4 冗余路徑剪枝

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

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

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

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

圖8 示例程序對應函數調用路徑圖

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

表5 測試用例執行路徑

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

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

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

表6 語句覆蓋情況

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

圖9 變更后示例程序

5 實驗分析

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

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

表7 實驗1對比結果

表8 實驗2對比結果

5.1 實驗1

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

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

圖10 覆蓋率變化趨勢圖

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

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

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

5.2 實驗2

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

圖11 傳統算法對比結果

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

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

6 結束語

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

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