基于覆蓋度的回歸測試用例選取方法

賀英杰，周仁杰

(1.91404部隊，河北 秦皇島 066000；2.杭州電子科技大學(xué) 計算機(jī)學(xué)院，浙江 杭州 310018)

0 引 言

軟件發(fā)生變更后需要進(jìn)行回歸測試，軟件回歸測試是軟件測試的一個重要階段，對軟件質(zhì)量的固化起著關(guān)鍵作用。回歸測試一般分為全面回歸和部分回歸，全面回歸的成本高，代價大，為了節(jié)約資源成本，提高測試效率，部分回歸的執(zhí)行頻度更高[1]。無論是全面回歸還是部分回歸，都可以通過測試用例集約簡技術(shù)對測試用例集進(jìn)行優(yōu)化，從而刪除冗余測試用例，減少測試用例數(shù)量，達(dá)到提高測試效率的目的[2]。

測試用例集約簡技術(shù)已有很多人進(jìn)行過研究，早期有G算法[3]、H算法[4]、GE算法[5]和GRE算法[6]等，這些算法各有特點，已經(jīng)證實任何一種算法都不比其他算法優(yōu)越[7]。上述算法都只是對測試用例集的簡化策略，未考慮測試需求在測試用例集優(yōu)化過程中的作用，后來有研究者在上述思想的基礎(chǔ)上，將測試用例集優(yōu)化與測試需求相結(jié)合，進(jìn)一步拓展測試用例集約簡技術(shù)。例如，文獻(xiàn)[8]考慮測試需求集和測試用例集的約簡，提出基于概念格分析的約簡算法，將概念格理論的可約簡屬性與可約簡對象等概念[9-10]引入進(jìn)來，但該方法適用Web應(yīng)用，不具備普遍有效性；文獻(xiàn)[11]考慮各測試需求間的相互關(guān)系，對滿足測試需求的所有測試用例進(jìn)行了劃分，生成測試用例集，再利用現(xiàn)有約簡技術(shù)進(jìn)行優(yōu)化；文獻(xiàn)[12]先給出測試需求約簡模型，對測試需求進(jìn)行約簡，再對測試用例集進(jìn)行優(yōu)化；文獻(xiàn)[13]也提出了一種測試需求模型，通過建立模型，整理了測試依據(jù)，為測試用例設(shè)計搭好框架。但這些方法都不是面向回歸測試的，沒有針對性和適用性，軟件回歸測試有其特殊性，主要是從首輪測試用例中篩選出重要的、覆蓋需求多的用例[14]，從而提高回歸測試執(zhí)行效率和質(zhì)量。文獻(xiàn)[15]針對回歸測試，提出基于部分需求進(jìn)行測試用例集優(yōu)化的方法，但定義不夠全面，認(rèn)為需求集只和軟件改動和修正相關(guān)，實踐發(fā)現(xiàn)還應(yīng)包括通過影響域分析發(fā)現(xiàn)的相關(guān)需求、與發(fā)現(xiàn)問題用例特征吻合的用例所對應(yīng)的需求，必要時還應(yīng)包括新增需求。

該文將理論與實際相結(jié)合，從工程實踐出發(fā)，提出基于覆蓋度的回歸測試用例選取方法—RCSC(a regression test case selection method based on coverage)。該方法面向重點測試需求集，采用貪婪策略篩選用例，能有效降低回歸測試成本，提高回歸測試的性價比。

1 相關(guān)技術(shù)介紹

測試用例集約簡技術(shù)主要分為兩類，包括傳統(tǒng)的約簡技術(shù)和基于需求驅(qū)動的約簡技術(shù)。前者是直接對測試用例集進(jìn)行約簡，也稱為非需求驅(qū)動技術(shù)；后者是先對測試需求集進(jìn)行約簡，再利用傳統(tǒng)的約簡技術(shù)對測試用例集進(jìn)行約簡。目前無論哪種技術(shù)，傳統(tǒng)的約簡技術(shù)都是測試用例集約簡的基礎(chǔ)，研究者對此已經(jīng)提出多種算法，這些算法大致可歸為3個類別：啟發(fā)式貪婪搜索、元啟發(fā)概率優(yōu)化以及二進(jìn)制整數(shù)線性規(guī)劃[15]。

啟發(fā)式貪婪搜索技術(shù)一般一次選擇一個或多個能覆蓋最多數(shù)量測試需求的測試用例，排除已經(jīng)覆蓋的測試需求，循環(huán)直到測試需求被完全覆蓋為止。G算法、H算法、GE算法和GRE算法均屬于這類技術(shù)。

元啟發(fā)概率優(yōu)化技術(shù)從一個初始的代表用例集(如備選集T)出發(fā)，應(yīng)用全局概率優(yōu)化算法推算最優(yōu)的代表用例集。模擬退火算法和混合遺傳算法屬于這類算法。

二進(jìn)制整數(shù)線性規(guī)劃(binary integer linear programming)技術(shù)通過將最優(yōu)用例集選擇問題轉(zhuǎn)化為0-1整數(shù)規(guī)劃問題，成本開銷最小是優(yōu)化目標(biāo)，所有測試需求被覆蓋是約束條件，最終獲得最優(yōu)用例集。整數(shù)規(guī)劃技術(shù)適用于多種約束條件、適應(yīng)值函數(shù)和測試充分性準(zhǔn)則，但是時間復(fù)雜度高，實際應(yīng)用中存在局限性。

2 基本概念

定義1 原始測試需求：一般包括顯性測試需求和隱性測試需求，顯性測試需求主要通過需求文檔、設(shè)計說明、用戶手冊等軟件開發(fā)文檔直接獲取；隱性測試需求主要通過相關(guān)測試標(biāo)準(zhǔn)規(guī)范來獲取。原始測試需求標(biāo)記為rorg，可分解為若干條最小測試需求，其集合可用Rorg表示。

定義3 重點測試需求集：回歸測試中有必要進(jìn)行測試的需求項集合，標(biāo)記為Rkey，集合中的元素標(biāo)記為rkey。重點測試需求集Rkey與原始測試需求集Rorg的關(guān)系如圖1所示。

圖1 Rkey與Rorg關(guān)系圖

定義4 回歸測試用例集：重點測試需求集所對應(yīng)的測試用例集合，標(biāo)記為T，包含問題用例集T1、相關(guān)用例集T2、相似用例集T3、新增用例T4。T=T1∪T2∪T3∪T4={t1,t2,…,tm}，且|T|=m，即回歸測試用例集的基數(shù)為m。

定義5 二元關(guān)系矩陣：描述回歸測試用例集T對重點測試需求集Rkey的覆蓋關(guān)系，矩陣的行代表重點測試需求，矩陣的列代表回歸測試用例。矩陣元素定義為a(ti,rkey(j))，在這里稱之為覆蓋度，其定義如式(1)所示。

(1)

如果ti∈T覆蓋rkey(j)∈Rkey，則a(ti,rkey(j))=covj(x)，否則a(ti,rkey(j))=0，其中x為被當(dāng)前用例覆蓋的最小測試需求序號，取值范圍為1,2,…,|rkey(j)|(|rkey(j)|表示第j個重點測試需求所包含的最小測試需求的數(shù)量)，i=1,2,…,m，j=1,2,…,n。

3 方法描述

3.1 選取策略

其次，通過語義分析、測試經(jīng)驗等知識將重點測試需求分解成最小測試需求，計算重點測試需求的基數(shù)，即包含的最小測試需求的數(shù)量；構(gòu)建二元關(guān)系矩陣表示回歸測試用例對重點測試需求的覆蓋關(guān)系，行代表用例，列代表需求，默認(rèn)用例已根據(jù)優(yōu)先級排序；依次標(biāo)注出用例對每一重點測試需求的覆蓋度，如果用例覆蓋需求，則覆蓋度標(biāo)記為covj(x)，即第j個用例所對應(yīng)的第x個最小測試需求，否則標(biāo)記為0；比較每個用例的覆蓋情況，篩選覆蓋需求最多的測試用例，放入最優(yōu)回歸測試集中，如果出現(xiàn)多個用例并列的情況，則比較用例的優(yōu)先級，優(yōu)先級高的用例置為最優(yōu)回歸測試用例；在關(guān)系矩陣中刪除最優(yōu)回歸測試用例及其對應(yīng)的覆蓋度，將其他用例所對應(yīng)的重復(fù)的覆蓋度置為0，調(diào)整重點測試需求的基數(shù)，減去被覆蓋的最小測試需求的項數(shù)，從比較每個用例的覆蓋情況開始重復(fù)上述操作，直到所有重點測試需求的基數(shù)變?yōu)?，表明所有最小測試需求均已覆蓋。

3.2 RCSC算法

輸出：T'，最優(yōu)回歸測試用例集；

begin

if(T1≠?) //存在問題用例集

foreachti∈T1do

列出ti所對應(yīng)的測試需求rkey(j)；

end for

end if

end if

if(T3≠?)//相似用例集T3

end if

設(shè)計新增用例集T4；

end if

//列出重點測試需求集組成

//列出回歸測試用例集元素組成

T=T1∪T2∪T3∪T4={t1,t2,…,tm}，且|T|=m；

//構(gòu)建從T到Rkey的二元關(guān)系矩陣，i=1,2,…,m，j=1,2,…,n

S(T，Rkey)={a(ti,rkey(j))∈T×Rkey}；

foreachti∈Tdo

foreachrkey(j)∈Rkeydo

if(ti覆蓋rkey(j))

(ti，rkey(j))=covj(x)；//x為被當(dāng)前用例覆蓋的最小測試需求序號

else

a(ti,rkey(j))=0;

end if

end for

end for

while(|rkey(j))|≠0)//重點測試需求基數(shù)不全為0，j=1,2,…,n

covT={ti};//查找覆蓋需求最多的用例(集)；

if(|covT|>1)//多個用例并列，查看優(yōu)先級

t'=min(ti)；//序號最小的優(yōu)先級高

T'=T'∪{ti}//放入最優(yōu)回歸測試用例集中；

end if

deletet'and covj(i)//刪除最優(yōu)回歸測試用例及其對應(yīng)的覆蓋度；

for(i=1;i≤m;i++)

for(j=1;j≤n;n++)

if(covj(i)重復(fù))//其他用例的覆蓋度重復(fù)，則置為0

covj(i)=0；

end if

end for

end for

|rkey(j)|--//相關(guān)重點測試需求基數(shù)減1；

end while

4 實例分析

為了說明該方法的有效性，本節(jié)通過一個實例對回歸測試用例的選取過程進(jìn)行演示。回歸測試用例的選取流程如圖2所示。

圖2 回歸測試用例的選取流程

進(jìn)行如下假定：

(2)rkey(1)、rkey(2)、rkey(3)、rkey(4)、rkey(5)包含最小測試需求的數(shù)量分別為3、2、2、1、1，即|rkey(1)|=3、|rkey(2)|=2、|rkey(3)|=2、|rkey(4)|=1、|rkey(5)|=1。

選取的具體步驟說明如下：

(3)構(gòu)建從T到Rkey的二元關(guān)系矩陣，矩陣大小為9×5，默認(rèn)ti按照優(yōu)先級排好序，如果ti覆蓋rkey(j)，則相應(yīng)的覆蓋度置為covj(x)，即滿足第j個重點測試需求中第x條最小測試需求，否則置為0。具體覆蓋關(guān)系如表1所示。

表1 選取前測試用例與測試需求的覆蓋關(guān)系

(4)比較每個測試用例t1～t9的覆蓋情況，篩選覆蓋測試需求最多的測試用例，放入最優(yōu)回歸測試集中，如果出現(xiàn)多個用例并列的情況，則比較用例的優(yōu)先級，優(yōu)先級高的用例置為最優(yōu)回歸測試用例。例如，表1中t3和t6覆蓋的需求數(shù)一樣多，但是t3優(yōu)先級高，所以將t3放入最優(yōu)回歸測試用例集中，在關(guān)系矩陣中刪除t3及其對應(yīng)的覆蓋度，將t6和t8中重復(fù)的覆蓋度置為0，如表2所示，t3及其對應(yīng)的覆蓋度帶下劃線，表示已被刪除，t6和t8中數(shù)字0帶下劃線，表示覆蓋度重復(fù)被置0；同時將rkey(1)、rkey(3)、rkey(4)的基數(shù)減1，各重點測試需求基數(shù)分別變更為2、2、1、0、1。

表2 首次篩選后的覆蓋關(guān)系

(5)判斷重點測試需求基數(shù)是否全為0，如果否，則重復(fù)步驟(4)中的篩選覆蓋測試需求最多的測試用例等相關(guān)操作，比較剩余用例的覆蓋情況，直到所有重點測試需求的基數(shù)變?yōu)?，得到最終覆蓋關(guān)系如表3所示，表中用例集合即為最優(yōu)回歸測試用例集。

表3 最終覆蓋關(guān)系

從最后的篩選結(jié)果可以看出，用例集{t1，t3，t6，t7，t9}可以滿足所有測試需求，從而達(dá)到了用最少回歸測試用例覆蓋重點測試需求的目的。

5 結(jié)束語

測試用例優(yōu)化的目的是用最小的用例集達(dá)到最大的覆蓋率，對于回歸測試來說，從時間、人力等成本的角度考慮，不需要達(dá)到測試需求的全覆蓋，滿足最優(yōu)覆蓋即可，即覆蓋重點測試需求，實現(xiàn)用最小的代價達(dá)到最優(yōu)的目標(biāo)；對于回歸測試用例約簡方面，該文不但從實際應(yīng)用角度將原始測試需求分解成最小測試需求，而且對測試用例與測試需求的二元關(guān)系矩陣重新定義，提出覆蓋度概念，摒棄簡單的1-0關(guān)系表示，便于剔除重復(fù)的覆蓋關(guān)系，相比于傳統(tǒng)方式更直接有效。

該方法適用于規(guī)模大、進(jìn)度要求高的軟件系統(tǒng)測試，既可減少回歸測試的工作量，又不降低回歸測試的質(zhì)量，能夠在用例數(shù)量與軟件質(zhì)量之間達(dá)到一個平衡。下一步需要對原始測試需求分解標(biāo)準(zhǔn)、相似用例選取方法等方面進(jìn)行深入研究，提出詳細(xì)的標(biāo)準(zhǔn)規(guī)范，進(jìn)一步完善方法的體系結(jié)構(gòu)。