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

賀英杰，周仁杰

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

0 引 言

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

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

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

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

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

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

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

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

2 基本概念

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

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

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

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

定義5 二元關(guān)系矩陣：描述回歸測(cè)試用例集T對(duì)重點(diǎn)測(cè)試需求集Rkey的覆蓋關(guān)系，矩陣的行代表重點(diǎn)測(cè)試需求，矩陣的列代表回歸測(cè)試用例。矩陣元素定義為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)前用例覆蓋的最小測(cè)試需求序號(hào)，取值范圍為1,2,…,|rkey(j)|(|rkey(j)|表示第j個(gè)重點(diǎn)測(cè)試需求所包含的最小測(cè)試需求的數(shù)量)，i=1,2,…,m，j=1,2,…,n。

3 方法描述

3.1 選取策略

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

3.2 RCSC算法

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

begin

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

foreachti∈T1do

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

end for

end if

end if

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

end if

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

end if

//列出重點(diǎn)測(cè)試需求集組成

//列出回歸測(cè)試用例集元素組成

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)前用例覆蓋的最小測(cè)試需求序號(hào)

else

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

end if

end for

end for

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

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

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

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

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

end if

deletet'and covj(i)//刪除最優(yōu)回歸測(cè)試用例及其對(duì)應(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)重點(diǎn)測(cè)試需求基數(shù)減1；

end while

4 實(shí)例分析

為了說(shuō)明該方法的有效性，本節(jié)通過(guò)一個(gè)實(shí)例對(duì)回歸測(cè)試用例的選取過(guò)程進(jìn)行演示?；貧w測(cè)試用例的選取流程如圖2所示。

圖2 回歸測(cè)試用例的選取流程

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

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

選取的具體步驟說(shuō)明如下：

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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