基于函數調用路徑的測試用例優先級排序

牟永敏，李慧麗

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

1 概述

軟件的調試、升級與維護往往需要更改部分代碼，為了驗證修改后的程序是否引發新的問題或對未修改的部分造成影響，就需要頻繁地對軟件進行回歸測試[1]。

回歸測試中最簡單的方法就是全部重測，但是實際情況是更改的代碼往往只是系統中很小的一部分，對整個系統的重測會耗費大量的時間，造成人力和物力的浪費，因此實際工作中一般采用選擇性回歸測試方法[2-3]。選擇性回歸測試是當源代碼修改后，僅對那些跟源代碼變化相關的模塊進行測試。

測試用例的選擇、測試用例集約簡以及測試用例優先級排序等技術是回歸測試研究的關鍵問題。其中，測試用例優先級技術認為不同測試用例對于測試目標的完成有著不同的貢獻程度，為了能夠更快地達成測試目標，有必要將不同的測試用例進行比較和排序，然后優先執行相對重要的測試用例[4]。目前測試用例優先級排序技術可分為覆蓋率技術和非覆蓋率技術[5]。

基于覆蓋的測試用例優先級技術根據測試用例的歷史覆蓋信息，設計優先級排序方法，但其考慮的優先級影響因素過于單一。為此，本文提出一種基于函數調用路徑的測試用例集優化方法。以函數調用路徑覆蓋分析為基礎，分析函數調用路徑中影響測試用例優先級的因素，設計測試用例優先集量化方法，并且根據測試執行情況動態調整優先級，以進一步優化優先級排序。

2 基本概念

2.1 基于函數調用路徑的覆蓋分析

路徑覆蓋測試是一種針對白盒測試的常用充分性準則，它觀察程序運行的整個路徑[6]。但是即使是規模很小的程序，包含的邏輯路徑數量也是相當大的，而在大型程序中進行完全的路徑測試幾乎是不可能的[7-8]。基于函數調用路徑的覆蓋分析技術是在保證每個函數完成單元測試的前提下，將覆蓋分析粒度由語句級擴展到函數級，分析函數調用的控制邏輯關系，這樣既能避免路徑的爆炸式增長，又可以保證測試的充分性。

RegressiontestC1.0[9]是自主開發的基于函數調用路徑的覆蓋分析工具，利用該工具可以得到全局靜態路徑集和測試用例執行對應的動態路徑。其整體思路是：通過對軟件源代碼的靜態分析，繪制帶有控制邏輯的函數調用關系圖，給出所有可能的函數調用路徑，稱為全局靜態路徑集[10]；對函數首尾和控制邏輯關鍵字進行插裝預處理，輸入測試用例，執行預處理后的程序，根據裝點信息得到該測試用例對應的動態函數調用路徑，下面給出相關的定義。

定義1函數調用路徑是指根據函數調用關系得到的由程序入口點到出口點的一個函數名序列，表示為Pi={Vi0,Vi1,…,Vim}，Vij為函數名；Vij和Vij+1的相鄰關系表示Vij調用了Vij+1。

定義2靜態路徑是指對源代碼進行靜態分析，根據函數調用關系得到函數調用路徑。全局靜態路徑集是全部靜態路徑的集合，表示為B(S,C)={P1,P2,…,Pn}，其中，S是源代碼；C是函數調用關系準則；Pi是函數調用路徑。

定義3動態路徑是指輸入測試數據后，程序動態執行時實際執行的函數調用路徑，表示為L(S,ti)={P1,P2,…}，

其中，S是指插裝后的源代碼；ti指測試用例。

例如，若源代碼為：

其中包含函數：main，scanf，add，f2，multi。根據函數調用關系，得到4條函數調用路徑形如P1={main,scanf}，P2={main,scanf,add}，P3={main,scanf,f2}，P4={main,scanf,multi}。此程序的全局靜態路徑集S={P1,P2,P3,P4}。當輸入測試數據a=2時，程序執行對應的動態路徑為P3和P4，如圖1所示。

圖1 函數調用路徑

基于函數調用路徑的回歸測試用例集確定的基本思想是：對新舊版本源程序進行比較，采集函數變更點數據，函數變更點是指產生了變更的函數。在全局靜態路徑集中標出所有經過變更點的路徑，稱為變更路徑集[11]。回歸測試時覆蓋全部變更路徑集，既能測試變更模塊，也能保證受變更模塊影響的相關模塊的正確性。因此，變更路徑集即回歸測試的測試需求，每一條變更路徑即一條測試需求。覆蓋變更路徑集中的一條或多條路徑的測試用例即回歸測試用例集。

例如上例中的函數minus和multi發生了變更，minus和multi即變更函數。路徑P3和P4即變更路徑集。P3和P4分別對應測試需求2個測試需求。若有如表1所示的測試用例-函數調用路徑關系，則回歸測試用例集為t3,t4,t5,t6。其中，×表示測試用例ti覆蓋函數調用路徑Pj。

表1 測試用例-函數調用路徑關系

2.2 測試用例優先級技術

測試用例優先級技術認為不同測試用例對于測試目標的完成有不同的貢獻程度，在回歸測試時將測試用例按其重要程度進行優先級排序后使用，能更快地達成測試目標。

例如，某被測程序中測試用例的缺陷檢測情況如表2所示。其中，×表示測試用例Ti檢測出錯誤Fj。如果按照T1-T10的順序執行測試用例，顯然直到執行到T3才會檢測出錯誤，且只有所有測試用例全部被執行才能檢測出所有的錯誤。顯然T4,T7,T9,T10可以檢測出全部的錯誤，如果按照T3-T4-T7-T9-T10-T1-T2-T5-T6-T8的順序執行，測試用例能夠更早地檢測到程序的錯誤。

表2 測試用例缺陷檢測情況

但是在測試用例被執行前，測試用例所檢測出的錯誤是無法預知的，研究發現依據一定的覆蓋準則和測試用例執行的歷史信息，盡快達到覆蓋標準能提高測試用例的檢錯率。測試用例優先級技術就是依據測試的歷史信息，以代碼覆蓋率或檢錯效率等為標準，為每個待復用的測試用例賦予一個優先級，并在回歸測試過程中按優先級順序選取和執行這些測試用例。

測試用例優先級技術的核心問題是如何確定和表述測試用例的重要程度[12]，目前主要是根據測試用例歷史覆蓋率排序測試用例優先級，即優先運行覆蓋能力較強的測試用例。但是傳統的優先級排序方法方法都只選取代碼覆蓋信息作為測試用例的特征加以度量，而忽略了其他影響測試用例優先級的因素，且缺乏動態性。

3 優先級排序算法

3.1 測試用例優先級量化方法

基于函數調用路徑的測試用例優先級排序方法以測試用例對函數調用路徑的歷史覆蓋信息作為優先級的一個影響因子，在此基礎上分析函數調用路徑與檢錯結果的關系，提取單元測試時函數中檢測出缺陷的個數和函數的扇入系數2個特征作為優先級的影響因子對優先級進行排序。

為了便于描述，給出以下相關定義：

定義4(測試覆蓋矩陣)測試用例集 T={t1,t2,…,tn}，變更路徑集，即測試需求集 P={P1,P2,…,Pm}，則測試覆蓋矩陣tCM是一個m×n階矩陣，當ti在執行過程中執行到了函數調用路徑路徑Pj時，元素δij=1，否則δij=0。

定義5(測試用例的覆蓋路徑集)測試用例ti的覆蓋路徑集 P(ti)(P(ti)∈P)是一個函數調用路徑集，其中包含執行測試用例ti時所執行到的所有P中的函數調用路徑。

定義6(函數調用路徑的執行用例集)Pj的執行用例集t(Pj)(t(Pj)∈T)是一個測試用例集，為測試用例集T中所有能夠覆蓋路徑Pj的測試用例。

(1)測試用例函數調用路徑覆蓋能力影響因子

測試用例ti函數調用路徑覆蓋能力是指，測試用例ti的覆蓋路徑集 P（ti）中的路徑條數 |P（ti）|。在回歸測試過程中，挑選覆蓋能力強的測試用例優先執行，能盡快達到覆蓋標準，滿足測試覆蓋需求。因此，將測試用例函數調用路徑覆蓋能力應用于優先級排序中，使覆蓋能力強的測試用例有較高的優先級，保證其更早地被執行以有效提高測試效率。用下式量化計算第i個測試用例ti的函數調用路徑覆蓋能力對優先級的影響值

其中，Ni為測試用例ti執行到的路徑條數 |P（ti）|，即測試用例ti的函數調用路徑覆蓋能力；max{N}為所有測試用例中函數調用路徑覆蓋能力的最大值。式(1)將測試用例函數調用路徑覆蓋能力影響值量化至0～1的數值區間。

(2)測試用例覆蓋路徑檢錯指標影響因子

軟件測試的二八原則指出，軟件中約20%的系統模塊包含了約80%的軟件缺陷。因此，單元測試時檢測出錯誤較多的模塊應作為重點測試的模塊。模塊的扇入系數是指，直接調用該模塊的上級模塊的個數。測試經驗表明，一個模塊出現錯誤很可能會引起調用該模塊的其他模塊出錯，高扇入的模塊會引起這種錯誤的迅速擴散。在C語言中單元測試的一個模塊通常是指一個函數。因此，本文將單元測試時函數中檢測出錯誤的個數和函數的扇入系數應用于優先級排序中。用式(2)、式(3)量化其對第i個測試用例ti優先級的影響值

1)函數調用路徑檢錯指標

若已知函數調用路徑 Pk={Vk0,Vk1,…,Vkm)，則路徑Pk的函數調用路徑檢錯指標量化值為：

其中，Vkl∈Pk，且在回歸測試的單元測試階段函數Vkj中至少檢測出一處錯誤；Ekj為單元測試時函數Vkj中所檢測出的錯誤個數；max{E}指在回歸測試的單元測試階段所有被測函數中檢測出的錯誤個數最大值；CVkj為函數vkj的扇入值；max{CV}是指在回歸測試的單元測試階段，所有至少檢測出一處錯誤的函數中函數扇入值的最大值。式(2)將函數調用路徑檢錯指標量化至0～1的數值區間，使得錯誤個數多、扇入系數高的函數所在的函數調用路徑有更高的量化值。

2)測試用例的覆蓋路徑檢錯指標

測試用例ti的覆蓋路徑檢錯指標是指測試用例ti的覆蓋路徑集中所有元素的函數調用路徑檢錯指標平均值：

其中，n為ti覆蓋路徑集中的元素個數。式(2)、式(3)使檢測出錯誤概率較高的測試用例有更高的優先級量化值，保證盡早地檢測出盡量多的錯誤。

(3)測試用例優先級量化取值

綜合測試用例函數調用路徑覆蓋能力和測試用例覆蓋路徑檢錯指標，第i個測試用例ti的優先級取值Vi為：

3.2 測試用例優先級優化算法

測試用例的執行將不斷地覆蓋函數調用路徑，因此，在測試執行過程中變更路徑集可以分為2個部分，尚未被任何執行過的測試用例覆蓋的未覆蓋路徑集testRt_UC，以及已經至少被一個執行過的測試用例覆蓋的覆蓋路徑集testRt_C。如果每次選擇的測試用例tj使tj盡可能多地滿足未覆蓋路徑集，而不關注其對覆蓋路徑集的覆蓋情況，則這種測試用例優先級選擇方法將能更快速地覆蓋所有的變更路徑集。因此，本文在測試用例執行過程中，根據測試用例對變更路徑集的覆蓋情況動態調整測試用例函數調用路徑覆蓋能力：，其中，為動態函數調用路徑覆蓋能力取值；為|P(ti)∩ testRt_ UC|，即測試用例ti執行到的尚未被任何已執行過的測試用例覆蓋的函數調用路徑條數。

測試用例優先級優化算法在測試用例執行過程中，根據覆蓋覆蓋路徑集和未覆蓋路徑集的變化，計算動態函數調用路徑覆蓋能力取值，從而動態調整測試用例優先集量化值，使優先級排序方法盡快覆蓋所有測試需求(函數調用路徑)，算法描述如下：

輸入 T為回歸測試用例集；P為變更路徑集；tCM為測試覆蓋矩陣

輸出 排序后的測試用例集T’

變量 testRt_UC為未覆蓋路徑集；testC_UR為未執行測試用例集

Begin

/*初始化*/

sort(T);//根據測試用例優先級量化值對T中測試用例排序testRt_UC=P;testC_UR=T;

/*測試用例集優化排序*/

while(testC_UR≠φ)

run(t1);//執行測試用例testC_UR中排序第一的測試用例，//即尚未執行的測試用例中優先級取值最高的測試用例

testC_UR=testC_UR–t1;

if(testRt_UC≠φ)

if(P(t1)∩ testRt_UC≠φ)

/*遍歷測試用例t1的覆蓋路徑集，實現優先級的動態調整*/

for each(Pj∈(P(t1) ∩ testRt_UC))

/*動態調整Pj的執行用例集t(Pj)中所有測試用例的優先級量化值*/

for each(tk∈t(Pj))

modify(Vk);//動態調整測試用例tk的優先級量化值

end for;end for;

sort(testC_UR);

end if;

else

/*若未覆蓋路徑集為空，則按優先級取值依次執行所有測

試用例*/

for each(ti∈testC_UR)

run(ti);end for;

testC_UR=φ

end if;

testRt_UC=testRt_UC-P(t1);end while;

在最外層的while循環中，首先執行當前測試用例優先級取值最高的測試用例t1，并在未執行測試用例集testC_UR移除該測試用例。若未覆蓋路徑集為空，則說明所有變更路徑都已經至少被覆蓋一次，此時未覆蓋路徑集不會再發生變化，測試用例的優先級取值也就不會再發生變化，因此按優先級取值依次執行所有測試用例；若未覆蓋路徑集非空，則遍歷測試用例t1的覆蓋路徑集P(t1)與未覆蓋路徑集testRT_UC的交集，動態地調整每條路徑的執行用例集中的測試用例優先級取值。最后在未覆蓋路徑集中testRt_UC移除測試用例t1覆蓋路徑集P(t1)。循環執行整個過程，直至所有測試用例都被執行。

4 實驗與評測

4.1 優先級排序方法度量標準

測試用例優先級排序方法的目標是為了提高測試的缺陷檢測率，盡早發現程序中的錯誤。文獻[12]提出了APFD度量標準作為優先級排序方法的度量指標。

APFD即缺陷檢測加權平均百分比，若測試用例集T包含n個測試用例，該測試用例集能夠檢測出的錯誤集合F中包含m個錯誤，則測試用例集T的一個順序集T′的APFD值定義為：

其中，T1F為順序集T′中第一個檢測出錯誤i的測試用例在T中的位置。

APFD的取值范圍是0～1。APFD的值越高，表示對應測試用例順序集缺陷檢測率越高。

例如測試用例缺陷檢測情況如表2所示，若按照T1-T10順序執行測試用例，則該順序集的APFD值為：

若按照T1-T10-T3-T4-T7-T9-T10-T1-T2-T5-T6-T8的順序執行，則該順序集的APFD值為：

4.2 實驗結果

基于函數調用路徑的測試核心關注點是程序的規模，函數調用路徑的條數等信息，因此選取了代碼行數幾十行到幾百行、函數調用路徑條數為數十條到上百條的5個實用C語言程序作為被測程序進行對比實驗。

針對每一個被測程序執行3輪測試。第一輪執行未排序的測試用例集，第二輪執行僅使用優先級量化方法排序的測試用例集，第三輪執行使用測試用例優先級優化方法排序的測試用例集。被測程序的代碼行數、函數調用路徑條數、測試用例數、缺陷數以及3輪順序集對應的APFD值如表3所示。

表3 優先級排序算法的實驗數據

通過實驗分析發現：

(1)使用優先級量化方法排序后的測試用例順序集APFD值要高于未使用任何排序方法的測試用例順序集APFD值，且兩者差值較大，說明優先級量化方法能明顯提高測試的缺陷檢測率。

(2)使用測試用例優先級優化方法動態排序后的測試用例順序集APFD值要高于僅使用優先級量化方法排序的順序集APFD值，但是提升幅度不明顯，一般能提高幾個百分點。在測試用例數和缺陷數較少的情況下，該優化方法可能失效。例如被測程P1，第三輪APFD值和第二輪APFD值無差別。因為優化方法本身會有資源和時間的開銷，在實際測試工程中要綜合考慮軟件規模、測試開銷等問題決定是否選用優化方法。

(3)隨著軟件規模的增加，測試用例優先級量化方法和測試用例優先級優化方法對缺陷檢測率的提升都更加穩定。

5 結束語

傳統的基于覆蓋的優先級技術僅考慮代碼覆蓋信息，而忽略了其他優先級影響因素。本文采用基于函數調用路徑的測試用例優先級排序方法，將測試用例的歷史覆蓋信息和其他優先級影響因素應用于優先級量化排序。按照此方法排序測試用例，能盡快地檢測到程序中的缺陷，使系統的調試修改工作盡早進行，降低風險。而根據測試執行動態調整優先級的優化方法，在測試用例數和缺陷數較多的測試中能進一步提高缺陷檢測速度。

隨著軟件規模的不斷擴大，軟件系統的迭代開發導致測試用例不斷被設計、修改和執行，其組成的測試用例集規模將更加龐大。如何尋找影響測試用例優先級的各種因素，并綜合各種因素制定合理的優先級計算方法，進一步提高測試效率，并保證算法的成本開銷是優先級研究的方向之一。

[1]郭晶晶,高建華.基于冗余測試用例的最小測試用例集生成方法[J].計算機工程,2010,36(1):45-48.

[2]彭園園.回歸測試方法及測試用例優化研究[D].武漢:武漢理工大學,2009.

[3]Mu Yongmin,Zheng Yuhui,Zhang Zhihua,et al.The Algorithm of Infeasible Paths Extraction Oriented the Function Calling Relationship[J]. Chinese Journal of Electronics,2012,21(2):236-240.

[4]屈 波,聶長海,徐寶文.基于測試用例設計信息的回歸測試優先級算法[J].計算機學報,2008,31(3):431-439.

[5]屈 波,聶長海,徐寶文.回歸測試中測試用例優先級技術研究綜述[J].計算機科學與探索,2009,3(3):225-233.

[6]Mu Yongmin,Wang Rui,Zhang Zhihua,et al.Automatic Test Method Research on the Word Part of Document Format Translator[J].Chinese Journal of Electronics,2013,22(1):55-60.

[7]侯 蕓,顧 剛,高海昌,等.一種路徑覆蓋自動生成的改進方法[J].計算機工程,2007,33(4):67-69.

[8]杜慶峰,李 娜.白盒測試基路徑算法[J].計算機工程,2009,35(15):100-102,123.

[9]張志華,牟永敏.基于函數調用的路徑覆蓋生成技術研究[J].電子學報,2010,38(8):1808-1811.

[10]Zheng Huiyu,Mu Yongmin,Zhang Zhihua.Research on the Static Function Call Path Generating Automatically[C]//Proc.of the 2nd IEEE International Conference on Information Management and Engineering.Chengdu,China:[s.n.],2010:405-409.

[11]Jiang Yu,Mu Yongmin,Zhang Zhihua.Modificatory Indentification Algorithm Research for Source Code Oriented[C]//Proc.of the 2nd International Workshop on Education Technology and Computer Science.Wuhan,China:[s.n.],2010:388-391.

[12]Rothermel G,Untch R H,Chu Chengyun,et al.Prioritizing Test Cases for Regression Testing[J].IEEE Transactions on Software Engineering,2001,27(10):929-948.