测试用例集约简方法综述

陈阳梅，丁晓明

(1.西南大学 计算机与信息科学学院，重庆400715;2.重庆市智能软件与软件工程重点实验室，重庆400715)

软件测试是保证软件质量和可靠性的重要手段。在进行软件测试时，测试人员首先确定软件测试需求，并根据该测试需求集设计出一套完整的测试用例，该测试用例集满足所有的测试需求。由此，该测试用例集的数量和质量决定软件测试的成本和有效性。在软件开发过程中，由于各模块的不断修改完善，各模块的不断添加和融合以及最后对整个系统的可靠性和有效性验证，需要频繁地进行回归测试，在此过程中测试用例集的数量将会越来越大，其中的冗余测试用例也会越来越多。为了提高软件测试效率，降低测试成本，这就很有必要地进行测试用例集约简。

1 测试用例集约简相关概念

1993年，M.J.Harrold等人首次提出了测试用例集约简的概念［1］。令测试用例集T与测试需求集R的二元关系S(T，R)={(t，r)∈T×R:测试用例t满足测试需求r}，即S(T，R)表示测试用例t∈T与测试需求r∈R的满足关系［8］。

如表1所示，测试需求集R={r1，r2，…，r6}，测试用例集 T={t1，t2，…，t7}以及集合 R与集合 T的关系S(T，R)。

由表1可知，T1={t1，t3，t7}即可满足所有的测试需求并且T1是T的子集。在测试用例集T中存在着两种测试用例，一种是对于测试来说必不可少的测试用例，另一种是冗余的测试用例，这些测试用例对测试本身来说并没有执行的价值，相反，执行它们反而会增加测试成本。测试用例集约简问题:令测试需求集R={r1，r2，…，rm}，并有测试用例集T={t1，t2，…，tn}满足所有的测试需求 ri，测试用例集约简问题就是要在测试用例集T中找到一个子集T'，即如果T'的任意真子集T'1都不能实现对测试需求集R的充分测试，有Req(T')=R，∀T'1⊂T1，Re q(T'1)≠R，则测试用例集T'称为满足测试需求集R的最小测试用例集，其中Re q(T')，Re q(T'1)分别表示测试用例集T'和测试用例集T'1所满足测试需求所组成的集合。

表1 测试需求与测试用例的满足关系S(T，R)

2 求解测试用例集约简问题的方法初探

目前已有的测试用例集约简方法主要分为两大类:基于组合覆盖的测试用例集约简技术和基于测试需求集的测试用例集约简技术。

2.1 基于组合覆盖的测试用例集约简技术

(1)正交试验设计方法。正交试验设计方法实现了对各个参数的两两组合的等概率覆盖，是一种比较成熟且有效的测试用例选择方法［17］。该算法在测试用例选取的过程中仍会产生数量较大的测试用例集，无法得到最优集。

(2)两两组合覆盖。两两组合覆盖的概念最早于1985年由Mandl提出。两两组合覆盖测试是一种覆盖任意单个系统因素、任两个系统因素间的组合以及尽可能多地多个因素间组合的方法［17］。该算法能大幅度地减少测试用例的数量，从而降低测试成本。Lei和Tai于2002年利用贪心算法，提出了一种基于参数顺序的渐进扩充的两两组合覆盖测试用例生成方法并实现了相应的测试用例自动自成系统(Pairwise Test System)［21］，随后有研究人员在此基础上进行改进，提出基于IPO策略的有参数约束的两两组合覆盖测试算法［21］。

2.2 基于测试需求集的测试用例集约简技术

(1)启发式算法。现有的启发式算法主要有贪心算法、HGS算法、GE＆GRE算法等。贪心算法(简称G算法)逐次从原始测试用例集T中挑选一个测试用例ti，并使得ti能最大限度地满足测试需求集R中尚未被满足的测试需求，然后将已满足的测试需求从测试需求集R中删除。重复上述过程，直到所有的测试需求都被满足，即测试需求集R为空集。该算法最坏情况下的时间复杂度为O(mn·min(m，n))［8，9］。

HGS算法是M.J.Harrold等人提出的一种根据测试用例的重要性来选择测试用例的启发式算法。该算法首先将测试需求 r1，r2，…，rm分成测试需求子集合 R1，R2，…，Rd(d≤n)，Ri(i=1，2，…，d)表示所有正好可以被T中第i条测试用例满足的测试需求。因此，HGS算法首先选出满足R1中测试需求的测试用例，并从测试需求集R中删除已被满足的测试需求。重复上述过程，直到所有的测试需求子集Ri(i=2，3，…，d)全部被满足。该算法最坏情况下的时间复杂度为O(m(m+n)d)［8］。

GE＆GRE算法是T.Y.Chen等人在贪心算法的基础上提出的。GE算法在贪心算法和必不可少策略的基础上，首先找出必不可少的测试用例，再使用贪心算法继续选择测试用例。该算法最坏情况下的时间复杂度为O(mn·min(m，n))［8，9］。GRE算法基于必不可少策略、冗余策略和贪心策略三种策略提出的。GRE算法反复地交替使用必不可少策略和冗余策略，直到这两种策略都无法应用，再使用贪心算法选择测试用例满足剩下的测试需求。该算法最坏时间复杂度为O(min(m，n)(m+n2k))［8，9］，其中k表示一个测试用例最多能满足的测试需求的数量。

0－1整数规划法将最优代表集选择问题转化为整数线性规划问题(Integer Linear Programming)。整数规划方法适用于多种约束条件、适应值函数和测试充分性准则，是启发式方法的重要补充。该算法时间复杂度较高，运算开销成指数级增长［8］。

(2)智能搜索算法。现有的智能搜索算法主要有:遗传算法(GA算法)、蚁群算法及基于蚁群算法的改进算法、粒子群算法以及一些改进的算法。

遗传算法(GA算法)［10］是一种基于启发式搜索的算法模型，该算法模型模拟达尔文的遗传选择和自然淘汰的生物进化过程完成对原有测试用例集的约简。首先，基于原有的测试用例集进行种群编码并在此基础上随机产生N个解构成初始种群;然后，采用竞争选择从种群中选出2个解p1，p2，并通过融合杂交算子p1，p2生成新的解C。利用测试覆盖率、测试运行代价等信息确保C的可行性并去除冗余。随后用C替代种群中高于平均适应值的个体。重复上述过程，直到产生t=M个不重复个体，从种群中选出具有最小适应值的个体作为最优解。该算法可在一定程度上得到测试用例集约简的近似最优解，但无法保证得到的约简后的测试用例集为最优的集合。

蚁群算法(Ant Colony Optimization algorithm，ACO)是一种利用群体智能，根据蚁群觅食活动的规律进行优化搜索的算法模型［12，20］。该算法首先根据测试需求集 R={r1，r2，…，rm}与原有测试用例集 T={t1，t2，…，tn}构造集合覆盖模型，将构造得到的测试需求集和测试用例集矩阵的每一列都赋一个相等的代价值C。然后，根据覆盖原则，测试用例运行代价等信息对原有测试用例集进行约简，求解集合覆盖问题过程中满足约束条件:每一个测试用例看成一个节点，并且每个节点最多能被蚂蚁访问一次;约简后的测试用例集中的测试用例必须覆盖矩阵中所有的行，即满足所有的测试需求。该算法虽然能在一定程度上生成数量较少且覆盖较多成对组合的测试用例，但该算法一般需要较长的搜索时间，同时，该算法容易出现停滞现象，当搜索到一定程度时，所有个体发现的解完全一致。

基于变异因子的蚁群算法(TSR-ACA)［16］将遗传算法和蚁群算法相结合，在基本蚁群算法的基础上通过引入遗传算法的变异因子增加搜索的随机性、快速性和全局收敛性来克服早熟停滞的缺陷。

蚁群模拟退火混合算法(Ant-Simulated Annealing algorithm，ASA)是将模拟退火思想引入蚁群算法以此来形成新的算法［17］。模拟退火算法(Simulated Annealing algorithm，SA)以物理系统退火过程的相似性为基础并适当地控制温度的下降过程来实现模拟退火，从而求解全局优化问题。该算法以蚁群算法为主，首先利用模拟退火算法在蚁群算法初期产生较优解;然后，按照蚁群算法完成一次循环遍历，再采用模拟退火算法在解的领域内寻找另外一个解。该混合算法分为2部分，即SA阶段和ACO阶段:首先通过模拟退火算法求解领域解的方法产生一个初始测试用例集，随后通过蚁群算法对初始测试用例集进行约简。

需求驱动的测试用例集约简方法［13］是由国内的聂长海等人提出的。该方法首先对测试需求集R进行约简，得到约简测试需求集R'，然后，针对约简测试需求集R'，采用已有的测试用例集生成和约简方法，得到测试用例约简集。该算法能有效地减少后续测试用例生成和约简的计算开销，在一定程度上对现有的测试用例集约简方法进行了补充。

近年来测试用例集的约简问题得到了越来越多的研究者的关注，约简技术也得到了不断的提高，不少研究人员也提出了自己的测试用例集约简技术，如基于依赖分析的方法［3，4］，基于程序操作语差异(operation difference)［5］的方法，基于调用栈覆盖(call stacks coverage)［6］的方法，基于 MC/DC(Modified Condition Decision Coverage)覆盖［7］方法，基于程序切片的测试用例集约简方法［6］，改进的AETG方法和蚁群算法相结合的方法［17］等。

3 测试用例集约简问题评价体系

为了比较不同测试用例集约简算法的性能，分析各种约简算法的适用范围，对于测试用例集约简算法通常采用以下4个属性来评价其约简效果［8］:

(1)充分性(Adequacy)。约简后的测试用例集应保持与原始用例集相同的测试充分性准则。

(2)精确性(Precision)。约简后的测试用例集能够最大限度地剔除冗余测试用例，减小测试用例集的规模。

(3)效益(Cost-effectiveness)。用于测试用例集约简的费用(即运行约简算法得到最优测试用例集的费用)应该小于使用约简后测试用例集进行测试所节省的费用，即需要考虑测试用例集算法的开销。

(4)通用性(Generality)。测试用例集约简算法可以适用于不同类型的程序、不同的测试充分性准则等。

测试用例集约简问题在整个求解过程中，在满足给定测试目标的前提下，删除测试用例集中的冗余测试用例，以尽可能少的测试用例充分满足测试目标，从而削减测试用例集的规模，降低运行、维护测试用例集的开销。与测试用例集约简问题强相关的一个问题是测试用例集的错误检测能力，即如何在测试用例集的规模及错误检测能力中找到一个平衡点，在满足一定测试充分性准则的前提下，减小测试用例集规模并尽可能地保持测试用例集的错误检测能力，这也成为了当前测试用例集约简问题的重要研究课题。

G.Rothermel等人提出的APFD评价方法目前得到了广泛的应用，该方法能有效评估优化测试用例集的平均错误检测效率。设测试用例集T中有n个测试用例，现已检测出的错误集合F中有m个错误，TFi表示T检测到错误i的第一个测试用例在T中的位置，则对应的APFD值如下所示:

由上式可知，APFD值介于0～100%之间，APFD值越大，其错误检测效率越高。在此基础上，S.Elbaum等人提出了改进的APFDc方法，用于评估当错误严重等级和测试用例开销不同时，给定优化测试用例集的平均错误检测效率［8，15］。

4 结束语

随着软件测试技术的不断更新和提高，如何寻找到更为有效的测试用例集约简算法，特别是同时考虑到测试用例约简率及其错误检测能力的双目标测试用例集优化方法，成为了当前软件测试领域中的关键问题和研究重点之一。由测试用例集约简问题的研究表明，未来的研究工作主要将集中在以下几个方面［8］:

(1)从测试用例集的规模及错误检测能力出发，结合测试用例优先级技术和基于搜索的优化方法，研究多测试充分性准则的测试用例集约简方法和多目标的测试用例集优化方法，实现全面的测试用例集优化;

(2)继续研究新的测试用例集约简算法、模型，力求在合理的时间复杂度下，减小测试用例集规模;

(3)采用仿真实验或大型程序实验来分析、比较现有方法的性能、适用范围，为测试人员选择有效的测试用例集约简方法提供建议和指导;

(4)设计并开发有效的测试用例集约简工具，实现测试用例集约简过程的自动化。

［1］HARROLD M J，GUPTA R，SOFFA M L.A methodology for controlling the size of a test suite［J］.ACM Transactions on Software Engineering and Methodology，1993，2(3):270-285

［2］SRIKANTH H.Requirements-based test case prioritization［C］.Student Research Forum in the 12thACM SIGSOFT International Symposium on the Foundations of Software Engineering，2004

［3］VAYSBURGB，TAHAT L，KOREL B.Dependence analysis in reduction of requirement based test suites［C］//Proceedings of the ACM International Symposium on Software Testing and Analysis，2002:107-111

［4］JOURDAN G V，RITTHIRUQNGDECH P，URAL H.Test suite reduction based on dependence analysis［C］//Proceedings of the 21stIEEE International Symposium on Computer and Information Sciences，2006:1021-1030

［5］ HARDER M，MELLEN J，ERNST M D.Improving test suites via operational abstraction［D］//Proceedings of the 25th International Conference on Software Engineering，2003:60-71

［6］MCMASTER S，MEMON A M.Call stack coverage for test suite reduction［C］//Proceedings of the 21stIEEE International Conference on Software Maintenance，2005:539-548

［7］ JONES J A，HARROLG M J.Test-suite reduction and prioritization for modified condition/decision coverage ［J］.IEEE Transactions on Software Engineering，2003，3(29):195-209

［8］章晓芳，陈林，徐宝文，等.测试用例集约简问题研究及其进展［J］.计算机科学与探索，2008，2(3):236-247

［9］章晓芳，徐宝文，聂长海，等.一种基于测试需求约简的测试用例集优化方法［J］.软件学报，2007，18(4):821-831

［10］聂长海，徐宝文.一种最小测试用例集生成方法［J］.计算机学报，2003，26(12):1690-1695

［11］吴洁，丁晓明.基于程序切片的测试用例集约简方法［J］.重庆交通大学学报:自然科学报，2010，29(2):319-320

［12］丁革建，郑燕妮，张璐.基于蚁群算法的测试用例集最小化研究［J］.计算机工程，2009，35(6):213-215

［13］李克文，杨志霞.基于回归测试模型的用例集的优化方法研究［J］.微计算机应用，2008，29(10):7-11

［14］全君林，陆璐.基于遗传算法测试用例集极小化研究［J］.计算机工程与应用，2009，45(19):58-61

［15］彭园园，熊盛武.测试用例集的优化技术分析与改进［J］.计算机应用技术，2009，6:77-80

［16］华丽，丁晓明.一种新的缩减测试用例集的算法［J］.西南师范大学学报:自然科学版，2009，34(6):119-122

［17］杨志霞.基于回归测试模型的用例集的优化研究［D］.中国石油大学(华东)，2009

［18］单锦辉，姜瑛，孙萍.软件测试研究进展［J］.北京大学学报:自然科学报，2005，41(1):134-145

［19］郑燕妮，李志蜀，李奇.蚁群模拟退火算法在测试用例约简中的应用［J］.计算机工程，2009，35(2):197-199

［20］任洪丽，张伟，梁家安.基于蚁群算法的测试用例集优化方法［J］.计算机工程与应用，2010，46(29):58-62

［21］曾劲涛，陈建明.有参数约束的两两组合覆盖测试用例生成的研究［J］.苏州大学学报:自然科学版，2008，24(1):45-49.