王曙燕, 張振豪, 孫家澤

(西安郵電大學 計算機學院， 陜西 西安 710121)

回歸測試屬于軟件測試的一種，用于確認程序或代碼的更改并未對現有功能產生不利的影響。在軟件維護過程中，回歸測試需要重新執(zhí)行訪問程序的所有測試用例，將產生時間和資源等額外的花費?，F有的解決方法主要包括測試用例約簡技術、測試用例選擇技術和測試用例優(yōu)先排序(test case prioritization, TCP)技術[1]。測試用例約簡和測試用例選擇雖然可以加快回歸測試過程，但是可能導致程序的某些語句無法正常執(zhí)行,測試用例檢測能力受到影響。而測試用例優(yōu)先排序按照最大化某種既定的測試目標對現有的測試用例重新排序，確定其執(zhí)行順序，不會舍棄任何測試用例，對改進回歸測試的效率和有效性具有重要意義[2]。

目前，測試用例優(yōu)先排序算法主要包括貪婪算法和啟發(fā)式算法[3]。貪婪算法是最常用的一種TCP技術[4-5]，在求解優(yōu)化問題時，總是選擇滿足當前覆蓋能力最高的測試用例，從而希望結果最優(yōu)。通過查找被修改函數與其他函數的關聯關系，從初始數據中選擇出回歸測試數據集，并對測試用例先排序再選擇，可有效地減少測試用例的數量，減低測試成本。但是，該算法是對因為系統修改受到影響的代碼部分進行測試，僅考慮了函數調用之間的關聯性，在執(zhí)行大量與輸出相關的語句時，也可能受到修改的影響[6]。使用測試用例輸出的相關切片信息可識別影響輸出結果的語句和分支覆蓋信息，并依據切片中的覆蓋需求確定測試用例優(yōu)先序列，但是，該方法也僅考慮了對輸出有影響的語句和分支[7]。

基于佳點集的新遺傳算法[8]在測試用例優(yōu)先排序過程中，考慮了遺傳算法的收斂速度和穩(wěn)定性的問題，利用數論中佳點集的特性，對遺傳算法中的交叉操作進行改進，提高了收斂速度，避免了早熟，并使用了語句、方法和分支等3種覆蓋速率的評價指標，更具代表性。但是，該算法穩(wěn)定性差，依賴初始種群的選擇?；谥档牧Ｗ尤簝?yōu)先排序方法[9]考慮了6種優(yōu)先級因子，并分配相應的優(yōu)先級，通過實施復雜性、需求波動性和需求可塑性等影響因子的組合，進行優(yōu)先級排序。但是，該方法對于影響因子需求有等級設置，具有不可復制性。

測試用例優(yōu)先排序的標準包括代碼覆蓋率、代碼復雜性和路徑復雜性等[5,10]。以獎勵多樣性為目標，類似聚類分析從不同的簇中選擇，使得測試用例更具多樣化[11]，意味著必須從那些與已經確定優(yōu)先序列的測試用例集中，選擇差異性最大的測試用例，并分配更高的優(yōu)先序列。而且，測試用例本身具有很重要的信息，與覆蓋信息之間也具有相關性，相似的測試用例具有相似的錯誤檢測能力[12]，因此，有必要關注測試用例之間的關聯。本文通過考慮測試用例之間的關聯性，將多樣性感知圖算法(diversity-aware graph algorithm,DAGA)應用于測試用例優(yōu)先排序?；谡Z句覆蓋標準，使用測試用例的多樣性化對測試用例序列優(yōu)化，以期提高測試用例排序的效率。

1 問題描述和技術標準

1.1 問題描述

測試用例優(yōu)先排序問題[13]可描述為給定測試用例T，T的全排列集為P，排序目標函數f的定義域為P,值域為實數，需要解決的問題是尋找T′∈P,使得(?T″∈P)(T″≠T′),滿足f(T″)≥f(T′)。

1.2 語句覆蓋矩陣

代碼覆蓋測試屬于白盒測試的一種，在進行代碼覆蓋測試時，要求可以直接訪問待測程序代碼并查看測試用例運行時的代碼覆蓋信息。按照被測程序所作測試的粒子程度，可劃分為語句覆蓋、基本塊覆蓋、分支覆蓋、路徑覆蓋和方法覆蓋等5種覆蓋標準[14]。程序代碼的覆蓋信息體現了測試用例的測試能力，收集測試用例的覆蓋信息，在測試用例優(yōu)先排序中借鑒聚類的一些策略，考慮不同測試用例間的關聯性，可提高代碼覆蓋速率。

設待測程序P，測試用例集Ω={T1,T2,…,Tn}，其中Ti(1≤i≤n)為測試用例集中第i個測試用例，使用eclemma工具[15]收集語句覆蓋信息Aij，生成語句覆蓋矩陣A。當Aij=1時，表示第i個測試用例執(zhí)行中覆蓋了第j條語句；當Aij=0時，表示第i個測試用例執(zhí)行中未覆蓋第j條語句。令P中有9條語句，測試用例集用Ω={T1,T2,T3,T4,T5}，測試用例語句覆蓋信息如表1所示。

表1 測試用例覆蓋信息

表1中X表示測試用例覆蓋語句，Y表示測試用例未覆蓋語句，則生成的語句覆蓋矩陣可表示為

1.3 距離函數和測試用例相異矩陣

測試用例間具有關聯性，使用杰卡德函數[15]計算不同測試用例間的多樣性，可以擴大錯誤的檢測率。給定測試用例Ti和Tj，每個測試用例有n個二進制屬性，利用杰卡德函數度量測試用例Ti和Tj的重疊有用相似性[16]，計算表達式為

(1)

其中：P11表示Ti和Tj的屬性值都為1的總數；Q01表示Ti的屬性值為0且Tj的屬性值為1的總數；R10表示Ti的屬性值為1和Tj的屬性值為0的總數。

利用杰卡德距離度量測試用例Ti和Tj的相異性，計算表達式為

Jdist(Ti,Tj)=1-Jindex(Ti,Tj)。

(2)

令Sij=Jdist(Ti,Tj)，1≤i≤n,1≤j≤n，則測試用例集Ω間的相異矩陣可表示為

(3)

2 多樣性感知圖的優(yōu)先排序

基于多樣性感知圖算法進行測試用例排序時，先將測試用例優(yōu)先排序問題轉換成圖的問題，通過轉換測試用例為圖的節(jié)點，轉換測試用例相異信息為圖的邊，構建多樣性感知圖；然后遍歷多樣性感知圖，實現對測試用例的排序。

2.1 多樣性感知圖的生成

為了映射測試用例優(yōu)先排序到圖，提取測試用例的某些特征并將其映射到圖中，對節(jié)點和邊增加額外功能，使用語句覆蓋率和測試用例相異信息作為測試的指標，構建多樣性感知圖G。G屬性信息包括節(jié)點和邊，節(jié)點的標簽為測試用例的編號，節(jié)點的值為語句覆蓋率；由式(2)計算得出任意兩個測試用例間的邊的權值，利用式(3)生成相異矩陣M，即得到圖G所有邊的權值。

生成多樣性感知圖的具體步驟如下。

輸入測試用例集Ω

輸出多樣性感知圖G

步驟1將Ω中測試用例的編號作為圖的標簽值。

步驟2計算測試用例的語句覆蓋率，并將其作為圖的節(jié)點值。

步驟3通過式(2)計算任意兩個測試用例之間的杰卡德距離，將其作為節(jié)點間的邊權值，利用式(3)生成相異矩陣M。

步驟4以節(jié)點的標簽和節(jié)點值作為節(jié)點信息，相異矩陣M為節(jié)點間邊的信息生成多樣性感知圖G。

2.2 遍歷多樣性感知圖

構建多樣性感知圖G后，遍歷多樣性感知圖G找到更有價值的測試用例優(yōu)先級。首先選擇覆蓋率最高的節(jié)點，移入已遍歷的集合；然后選擇具有最高增益值的節(jié)點S；最后使用遞歸算法計算剩余節(jié)點，直到遍歷完所有節(jié)點。遍歷多樣性感知圖算法具體步驟如下。

輸入多樣性感知圖G

輸出測試用例優(yōu)先排序序列L

步驟1遍歷多樣性感知圖G的所有節(jié)點選擇節(jié)點值最大的值作為初始節(jié)點，并將其移入L中。

步驟2遍歷G中剩余節(jié)點，計算剩余節(jié)點的節(jié)點值與剩余節(jié)點到L中節(jié)點邊的權值之和并將最大值賦值給S。

步驟3將S中最大的節(jié)點移入L中。

步驟4若G不為空，返回步驟2重新執(zhí)行；否則輸出L。

2.3 多樣性感知圖的生成及遍歷實例

圖1為多樣性感知圖遍歷算法示例。多樣性感知由T1、T2、T3、T4、T5和T6等6個節(jié)點組成，每個節(jié)點值是由語句覆蓋率計算得出，若總的可執(zhí)行語句量是15，T3覆蓋12條語句，該節(jié)點的值等于0.66(12/15)。邊的權值由式(2)計算得出，式(1)可計算得出T1和T6之間相似性為0.5，T1和T2的邊的權值為0.5(1-0.5)。使用多樣性感知圖算法，節(jié)點T6增益為最高值0.8，因此，遍歷過程從這個節(jié)點開始。將T6移入已遍歷集合L中，計算當前節(jié)點的增益值，與Ω中其他節(jié)點相比，節(jié)點T3增益為最高值1.66(0.66 + 1 = 1.66)，因此，第二待選節(jié)點是T3。將T3及移入L中，刪除邊(T3,T5)，重復此過程，直到算法遍歷所有剩余的節(jié)點。最后L中存儲路徑為{T6,T3,T5,T4,T1,T2}。

圖1 多樣性感知圖遍歷算法示例

3 實驗結果及分析

實驗環(huán)境為Intel Core 1.5 GHZ,4 GB內存Windows 764位，在集成開發(fā)環(huán)境Eclipse 4.5中運行，Java虛擬機版本號為jdk 1.8。

為了驗證基于多樣性感知圖的測試用例優(yōu)先排序的效率，選取jasmine 、apns 、jopt 和Scrib 等4個GitHub[17]上的程序作為回歸測試數據集，分別對比多樣性感知算法、貪婪算法、隨機算法、順序算法及逆序算法的平均語句覆蓋(average percentage of statement coverage,APSC)[18]。數據集信息如表2所示。對每個待測試程序使用上述5種算法分別進行30次實驗，平均結果如表3所示。

表2 數據集說明

表3 APSC實驗結果

由表3中的APSC值可以看出，在4個數據集中，多樣性感知算法都優(yōu)于貪婪算法、隨機等其他算法，在jasmine數據集中多樣性感知算法效果明顯；在apns數據集中，由于測試用例間的多樣性區(qū)分度不高，多樣性感知算法優(yōu)于貪婪算法；jopt與Scribe數據集中由隨機和順序可知測試用例集較為穩(wěn)定。因此，多樣性感知算法在覆蓋速率優(yōu)于其他算法。

4 結語

考慮了測試用例的多樣性及測試用例的覆蓋能力，利用多樣性感知圖的算法求解測試用例優(yōu)先排序，減少了盲目性的排序，提高了測試用例覆蓋速率。實驗結果表明，本文算法具有較快的覆蓋速度，有效地提高了測試用例排序的效率。