牟永敏，李慧麗

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

1 概述

軟件的調(diào)試、升級與維護往往需要更改部分代碼，為了驗證修改后的程序是否引發(fā)新的問題或?qū)ξ葱薷牡牟糠衷斐捎绊懀托枰l繁地對軟件進行回歸測試[1]。

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

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

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

2 基本概念

2.1 基于函數(shù)調(diào)用路徑的覆蓋分析

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

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

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

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

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

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

例如，若源代碼為：

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

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

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

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

表1 測試用例-函數(shù)調(diào)用路徑關系

2.2 測試用例優(yōu)先級技術(shù)

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

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

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

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

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

3 優(yōu)先級排序算法

3.1 測試用例優(yōu)先級量化方法

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

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

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

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

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

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

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

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

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

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

1)函數(shù)調(diào)用路徑檢錯指標

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

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

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

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

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

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

綜合測試用例函數(shù)調(diào)用路徑覆蓋能力和測試用例覆蓋路徑檢錯指標，第i個測試用例ti的優(yōu)先級取值Vi為：

3.2 測試用例優(yōu)先級優(yōu)化算法

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

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

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

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

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

Begin

/*初始化*/

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

/*測試用例集優(yōu)化排序*/

while(testC_UR≠φ)

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

testC_UR=testC_UR–t1;

if(testRt_UC≠φ)

if(P(t1)∩ testRt_UC≠φ)

/*遍歷測試用例t1的覆蓋路徑集，實現(xiàn)優(yōu)先級的動態(tài)調(diào)整*/

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

/*動態(tài)調(diào)整Pj的執(zhí)行用例集t(Pj)中所有測試用例的優(yōu)先級量化值*/

for each(tk∈t(Pj))

modify(Vk);//動態(tài)調(diào)整測試用例tk的優(yōu)先級量化值

end for;end for;

sort(testC_UR);

end if;

else

/*若未覆蓋路徑集為空，則按優(yōu)先級取值依次執(zhí)行所有測

試用例*/

for each(ti∈testC_UR)

run(ti);end for;

testC_UR=φ

end if;

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

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

4 實驗與評測

4.1 優(yōu)先級排序方法度量標準

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

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

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

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

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

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

4.2 實驗結(jié)果

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

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

表3 優(yōu)先級排序算法的實驗數(shù)據(jù)

通過實驗分析發(fā)現(xiàn)：

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

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

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

5 結(jié)束語

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

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

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

[2]彭園園.回歸測試方法及測試用例優(yōu)化研究[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]屈 波,聶長海,徐寶文.基于測試用例設計信息的回歸測試優(yōu)先級算法[J].計算機學報,2008,31(3):431-439.

[5]屈 波,聶長海,徐寶文.回歸測試中測試用例優(yōu)先級技術(shù)研究綜述[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]張志華,牟永敏.基于函數(shù)調(diào)用的路徑覆蓋生成技術(shù)研究[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.