基于覆盖度的回归测试用例选取方法

贺英杰，周仁杰

(1.91404部队，河北 秦皇岛 066000；2.杭州电子科技大学 计算机学院，浙江 杭州 310018)

0 引 言

软件发生变更后需要进行回归测试，软件回归测试是软件测试的一个重要阶段，对软件质量的固化起着关键作用。回归测试一般分为全面回归和部分回归，全面回归的成本高，代价大，为了节约资源成本，提高测试效率，部分回归的执行频度更高[1]。无论是全面回归还是部分回归，都可以通过测试用例集约简技术对测试用例集进行优化，从而删除冗余测试用例，减少测试用例数量，达到提高测试效率的目的[2]。

测试用例集约简技术已有很多人进行过研究，早期有G算法[3]、H算法[4]、GE算法[5]和GRE算法[6]等，这些算法各有特点，已经证实任何一种算法都不比其他算法优越[7]。上述算法都只是对测试用例集的简化策略，未考虑测试需求在测试用例集优化过程中的作用，后来有研究者在上述思想的基础上，将测试用例集优化与测试需求相结合，进一步拓展测试用例集约简技术。例如，文献[8]考虑测试需求集和测试用例集的约简，提出基于概念格分析的约简算法，将概念格理论的可约简属性与可约简对象等概念[9-10]引入进来，但该方法适用Web应用，不具备普遍有效性；文献[11]考虑各测试需求间的相互关系，对满足测试需求的所有测试用例进行了划分，生成测试用例集，再利用现有约简技术进行优化；文献[12]先给出测试需求约简模型，对测试需求进行约简，再对测试用例集进行优化；文献[13]也提出了一种测试需求模型，通过建立模型，整理了测试依据，为测试用例设计搭好框架。但这些方法都不是面向回归测试的，没有针对性和适用性，软件回归测试有其特殊性，主要是从首轮测试用例中筛选出重要的、覆盖需求多的用例[14]，从而提高回归测试执行效率和质量。文献[15]针对回归测试，提出基于部分需求进行测试用例集优化的方法，但定义不够全面，认为需求集只和软件改动和修正相关，实践发现还应包括通过影响域分析发现的相关需求、与发现问题用例特征吻合的用例所对应的需求，必要时还应包括新增需求。

该文将理论与实际相结合，从工程实践出发，提出基于覆盖度的回归测试用例选取方法—RCSC(a regression test case selection method based on coverage)。该方法面向重点测试需求集，采用贪婪策略筛选用例，能有效降低回归测试成本，提高回归测试的性价比。

1 相关技术介绍

测试用例集约简技术主要分为两类，包括传统的约简技术和基于需求驱动的约简技术。前者是直接对测试用例集进行约简，也称为非需求驱动技术；后者是先对测试需求集进行约简，再利用传统的约简技术对测试用例集进行约简。目前无论哪种技术，传统的约简技术都是测试用例集约简的基础，研究者对此已经提出多种算法，这些算法大致可归为3个类别：启发式贪婪搜索、元启发概率优化以及二进制整数线性规划[15]。

启发式贪婪搜索技术一般一次选择一个或多个能覆盖最多数量测试需求的测试用例，排除已经覆盖的测试需求，循环直到测试需求被完全覆盖为止。G算法、H算法、GE算法和GRE算法均属于这类技术。

元启发概率优化技术从一个初始的代表用例集(如备选集T)出发，应用全局概率优化算法推算最优的代表用例集。模拟退火算法和混合遗传算法属于这类算法。

二进制整数线性规划(binary integer linear programming)技术通过将最优用例集选择问题转化为0-1整数规划问题，成本开销最小是优化目标，所有测试需求被覆盖是约束条件，最终获得最优用例集。整数规划技术适用于多种约束条件、适应值函数和测试充分性准则，但是时间复杂度高，实际应用中存在局限性。

2 基本概念

定义1 原始测试需求：一般包括显性测试需求和隐性测试需求，显性测试需求主要通过需求文档、设计说明、用户手册等软件开发文档直接获取；隐性测试需求主要通过相关测试标准规范来获取。原始测试需求标记为rorg，可分解为若干条最小测试需求，其集合可用Rorg表示。

定义3 重点测试需求集：回归测试中有必要进行测试的需求项集合，标记为Rkey，集合中的元素标记为rkey。重点测试需求集Rkey与原始测试需求集Rorg的关系如图1所示。

图1 Rkey与Rorg关系图

定义4 回归测试用例集：重点测试需求集所对应的测试用例集合，标记为T，包含问题用例集T1、相关用例集T2、相似用例集T3、新增用例T4。T=T1∪T2∪T3∪T4={t1,t2,…,tm}，且|T|=m，即回归测试用例集的基数为m。

定义5 二元关系矩阵：描述回归测试用例集T对重点测试需求集Rkey的覆盖关系，矩阵的行代表重点测试需求，矩阵的列代表回归测试用例。矩阵元素定义为a(ti,rkey(j))，在这里称之为覆盖度，其定义如式(1)所示。

(1)

如果ti∈T覆盖rkey(j)∈Rkey，则a(ti,rkey(j))=covj(x)，否则a(ti,rkey(j))=0，其中x为被当前用例覆盖的最小测试需求序号，取值范围为1,2,…,|rkey(j)|(|rkey(j)|表示第j个重点测试需求所包含的最小测试需求的数量)，i=1,2,…,m，j=1,2,…,n。

3 方法描述

3.1 选取策略

其次，通过语义分析、测试经验等知识将重点测试需求分解成最小测试需求，计算重点测试需求的基数，即包含的最小测试需求的数量；构建二元关系矩阵表示回归测试用例对重点测试需求的覆盖关系，行代表用例，列代表需求，默认用例已根据优先级排序；依次标注出用例对每一重点测试需求的覆盖度，如果用例覆盖需求，则覆盖度标记为covj(x)，即第j个用例所对应的第x个最小测试需求，否则标记为0；比较每个用例的覆盖情况，筛选覆盖需求最多的测试用例，放入最优回归测试集中，如果出现多个用例并列的情况，则比较用例的优先级，优先级高的用例置为最优回归测试用例；在关系矩阵中删除最优回归测试用例及其对应的覆盖度，将其他用例所对应的重复的覆盖度置为0，调整重点测试需求的基数，减去被覆盖的最小测试需求的项数，从比较每个用例的覆盖情况开始重复上述操作，直到所有重点测试需求的基数变为0，表明所有最小测试需求均已覆盖。

3.2 RCSC算法

输出：T'，最优回归测试用例集；

begin

if(T1≠ø) //存在问题用例集

foreachti∈T1do

列出ti所对应的测试需求rkey(j)；

end for

end if

end if

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

end if

设计新增用例集T4；

end if

//列出重点测试需求集组成

//列出回归测试用例集元素组成

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

//构建从T到Rkey的二元关系矩阵，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为被当前用例覆盖的最小测试需求序号

else

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

end if

end for

end for

while(|rkey(j))|≠0)//重点测试需求基数不全为0，j=1,2,…,n

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

if(|covT|>1)//多个用例并列，查看优先级

t'=min(ti)；//序号最小的优先级高

T'=T'∪{ti}//放入最优回归测试用例集中；

end if

deletet'and covj(i)//删除最优回归测试用例及其对应的覆盖度；

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

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

if(covj(i)重复)//其他用例的覆盖度重复，则置为0

covj(i)=0；

end if

end for

end for

|rkey(j)|--//相关重点测试需求基数减1；

end while

4 实例分析

为了说明该方法的有效性，本节通过一个实例对回归测试用例的选取过程进行演示。回归测试用例的选取流程如图2所示。

图2 回归测试用例的选取流程

进行如下假定：

(2)rkey(1)、rkey(2)、rkey(3)、rkey(4)、rkey(5)包含最小测试需求的数量分别为3、2、2、1、1，即|rkey(1)|=3、|rkey(2)|=2、|rkey(3)|=2、|rkey(4)|=1、|rkey(5)|=1。

选取的具体步骤说明如下：

(3)构建从T到Rkey的二元关系矩阵，矩阵大小为9×5，默认ti按照优先级排好序，如果ti覆盖rkey(j)，则相应的覆盖度置为covj(x)，即满足第j个重点测试需求中第x条最小测试需求，否则置为0。具体覆盖关系如表1所示。

表1 选取前测试用例与测试需求的覆盖关系

(4)比较每个测试用例t1～t9的覆盖情况，筛选覆盖测试需求最多的测试用例，放入最优回归测试集中，如果出现多个用例并列的情况，则比较用例的优先级，优先级高的用例置为最优回归测试用例。例如，表1中t3和t6覆盖的需求数一样多，但是t3优先级高，所以将t3放入最优回归测试用例集中，在关系矩阵中删除t3及其对应的覆盖度，将t6和t8中重复的覆盖度置为0，如表2所示，t3及其对应的覆盖度带下划线，表示已被删除，t6和t8中数字0带下划线，表示覆盖度重复被置0；同时将rkey(1)、rkey(3)、rkey(4)的基数减1，各重点测试需求基数分别变更为2、2、1、0、1。

表2 首次筛选后的覆盖关系

(5)判断重点测试需求基数是否全为0，如果否，则重复步骤(4)中的筛选覆盖测试需求最多的测试用例等相关操作，比较剩余用例的覆盖情况，直到所有重点测试需求的基数变为0，得到最终覆盖关系如表3所示，表中用例集合即为最优回归测试用例集。

表3 最终覆盖关系

从最后的筛选结果可以看出，用例集{t1，t3，t6，t7，t9}可以满足所有测试需求，从而达到了用最少回归测试用例覆盖重点测试需求的目的。

5 结束语

测试用例优化的目的是用最小的用例集达到最大的覆盖率，对于回归测试来说，从时间、人力等成本的角度考虑，不需要达到测试需求的全覆盖，满足最优覆盖即可，即覆盖重点测试需求，实现用最小的代价达到最优的目标；对于回归测试用例约简方面，该文不但从实际应用角度将原始测试需求分解成最小测试需求，而且对测试用例与测试需求的二元关系矩阵重新定义，提出覆盖度概念，摒弃简单的1-0关系表示，便于剔除重复的覆盖关系，相比于传统方式更直接有效。

该方法适用于规模大、进度要求高的软件系统测试，既可减少回归测试的工作量，又不降低回归测试的质量，能够在用例数量与软件质量之间达到一个平衡。下一步需要对原始测试需求分解标准、相似用例选取方法等方面进行深入研究，提出详细的标准规范，进一步完善方法的体系结构。