基于弱变异准则的测试用例约简方法

王曙燕 袁佳娟 孙家泽

摘 要：针对为数较多的测试用例增加了回归测试成本的问题，提出一种基于弱变异准则的测试用例约简方法。首先，基于弱变异准则获得测试用例和变异分支关系矩阵;然后，重复约简4种无效测试需求和子集测试用例;最后，结合人工鱼群算法选择当前最优测试用例，并且交替执行简化和测试用例选择操作直至覆盖所有测试需求。该方法针对6个经典程序与贪心算法和HGS算法相比，基于弱变异准则并且不改变或稍微改变变异评分的条件下，约简率分别提高了73.4%和8.2%，且耗时分别降低了25.3%和56.1%。实验结果表明，所提方法在回归测试中可有效约简测试用例，降低测试代价。

关键词：回归测试;弱变异准则;变异分支;测试用例约简;人工鱼群算法

中图分类号： TP311. 5

文献标志码：A

Abstract： In view of the problem that the test cost is increased by a large number of test suites in regression testing， a test suite reduction method based on weak mutation criterion was proposed. Firstly， the relation matrix between test suites and mutation branches was obtained based on weak mutation criterion. Then， four invalid test requirements and subset test suites were reduced repeatedly. Finally， the current optimal test suite was selected by using artificial fish swarm algorithm， and the simplification and test suite selection operations were performed alternately until all the test requirements were covered. Compared with Greedy algorithm and HGS （Harrold-Gupta-Soff） algorithm on six classical programs， when using weak mutation criterion with no changing or slightly changing mutation score， the reduction rate was improved by 73.4% and 8.2% respectively， and the time consumption was decreased by 25.3% and 56.1% respectively. The experimental results show that the proposed method can effectively reduce the test suites and save the test cost in regression testing.

Key words： regression testing; weak mutation criterion; mutation branch; test suite reduction; artificial fish swarm algorithm

0 引言

軟件测试是评估能否达到预期要求、检验软件质量的过程。回归测试过程中数量较多的测试用例增加了测试成本[1]，因此从原始测试用例集中选择规模较小的测试用例，从而有效降低测试费用是软件测试的主要目标之一。约简测试用例可描述为选择尽可能小的子集测试用例，使之尽可能满足与原测试用例集相同的测试需求。选择覆盖所有测试需求的子集测试用例是一个NP（Non-deterministic Polynomial）问题[2-3]。

目前主要的测试用例约简算法有贪心（Greedy， G）算法、启发式算法、启发式贪婪算法和整数规划算法等[4-5]。G算法总是选择当前满足测试需求最多的测试用例，然后移除已被满足的测试需求，再继续选择直到测试需求集为空[6]。Harrold等[7]首先划分测试需求，以满足某测试需求的测试用例个数作为重要性判断依据，提出了根据重要性选择优化代表集的HGS（Harrold-Gupta-Soff）算法。在此基础上，Chen等[8]提出贪婪进化（Greedy Evolution， GE）算法和GRE（GREedy heuristic G）算法。GE算法首先选出必不可少的测试用例后结合G算法;GRE算法首先基于必不可少策略、1-1冗余策略重复直至不能再应用两种策略，然后结合贪心策略约简测试用例。Lee等[9]应用5种约简规则化简矩阵规模，并将测试用例求解问题转化为整数线性规划问题得到最优解。G算法和HGS算法的求解结果精度不高，GE和GRE算法时间复杂度较高，且均不能保证约简后的测试用例集是优化代表集。Marchetto等[10]以源代码覆盖、应用需求覆盖和执行测试用例成本为为目标，提出多目标测试用例约简（Multi-Objective test suites REduction， MORE+）方法，采用LSI（Latent Semantic Indexing）恢复相似性链接，计算软件度量和可维护性索引自动为代码和需求加权，采用测试用例集约简公式，依赖NSGA-II（Non-dominated Sorting Genetic Algorithm-II）约简测试用例。Vahabzadeh等[11]提出了一种细粒度测试用例最小化方法，在每个语句级别捕获测试状态，得到有相同PMC（Production Method Calls）的等价测试语句和相容状态建立模型，根据模型集合测试用例重组和最小化组合算法识别和移除冗余的测试语句。

聂长海等[6]充分考虑测试需求之间的相互关系，对所有可用测试用例集进行划分得到子集族，每个子集由满足某一个或多个测试需求的测试用例组成，利用启发式算法、贪心算法或整数规划方法简化测试用例集，从而生成满足所有测试需求的最小测试用例集。该方法虽然考虑到测试需求之间的关系，但却没有分析测试用例与测试需求的覆盖关系，简化无效的测试需求。章晓芳等[12]进一步研究如何充分利用测试需求间的相互关系约简测试需求，去除包含、相等和部分重合三种关系的测试需求，将精简的测试需求作为测试用例生成和约简的基础;但通过对所有测试需求的两两组合，判断相互关系，精简测试需求时间复杂度较大，且没有考虑到通过必不可少的测试用例进而精简测试需求。顾庆等[13]提出启发式贪婪搜索算法（Heuristic search Algorithm with Three Strategies， HATS），应用必选策略、替代策略和贪婪策略选择最合适的测试用例。Usaola等[14]首次将变异体覆盖作为测试需求，通过测试用例与变异体的关系，选择覆盖当前变异体最多的测试用例，移除已满足变异体，继续选择直至所有变异体被覆盖;但其基于强变异准则，随着程序规模的增加，大量变异体的产生使得在变异体和测试用例关系获取的代价增加，且得到约简后的测试用例集不能保证全局最优。王曙燕等[5]通过执行变异体与程序变异体集矩阵，然后结合关联规则约简测试用例;但随着程序规模的增加，该方法将产生数量较多的变异体，执行变异体与原程序以结果区分变异体是否被杀死，其时间消耗是不可忽略的过程。

针对上述结合变异测试约简测试用例，未考虑测试用例与测试需求关系获取的代价以及约简测试需求的计算方式复杂问题。基于Papadakis等[15]的弱变异转化方法，一次执行构建变异分支的新程序获取关系矩阵，此外对测试需求进行二进制编码，通过编码值约简4种测试需求可降低计算消耗。本文基于弱变异准则的测试用例约简方法，首先通过弱变异转化方法获得关系矩阵，然后重复约简测试需求和子集测试用例并结合人工鱼群算法，交替执行简化和测试用例选择操作以加快降低求解复杂度，直至满足所有测试需求。实验表明在弱变异准则下，该方法在不改变或稍微改变测试用例充分性情况下可有效约简测试用例。

1 基本概念和术语

变异测试是一种基于缺陷的软件测试技术[16]。变异测试通过对原程序作合乎语法的微小改动模拟软件中的实际缺陷，每个被注入缺陷的副本称为变异体，若相同输入情况下变异体和原程序输出不同，则变异体被杀死，否则变异体存活。在传统强变异测试中，原程序与变异体的输出结果作为判断变异体是否被杀死的依据，即满足可达性、必要性和完全性则判定变异体被杀死[17]。可达性指测试用例可到达变异点;必要性指在变异点之后程序状态发生改变;完全性指程序状态改变影响程序出口，改变程序运行结果。

弱变异准则只需要满足可达性和必要性，即测试用例执行变异语句后，程序的状态发生改变可判定变异体被杀死。通过学者研究表明，弱变异测试可有效替代强变异测试[18]。若被测程序P，m个原始测试用例组成集合T={t1，t2，…，tm}，n个变异体组成集合M={m1，m2，…，mn}。

4 结语

本文针对回归测试中测试用例约简问题，提出一种基于弱变异准则的测试用例约简方法。基于弱变异准则，在不改变或稍微改变变异评分的条件下，本文算法可有效约简测试用例。在此基础上，接下来准备从以下两方面进行研究：一方面，对类级别变异算子进行更深一步研究; 另一方面，弱变异分支转化导致极小部分等价变异体未被识别，影响对应变异分支覆盖，从而改变了某些测试用例约简，因此接下来将对此类未识别变异体作进一步研究。

参考文献：

[1] NARDO D D， ALSHAHWAN N， BRIAND L， et al. Coverage-based regression test case selection， minimization and prioritization： a case study on an industrial system [J]. Software Testing， Verification and Reliability， 2015， 25（4）： 371-396.

[2] JONES J A， HARROLD M J. Test-suite reduction and prioritization for modified condition/decision coverage [J]. IEEE Transactions on Software Engineering， 2003， 29（3）： 195-209.

[3] 鄭炜，杨喜兵，胡圣佑，等.基于变异分析和覆盖准则的回归测试用例集缩减[J].西北工业大学学报，2017，35（3）：494-499. （ZHENG W， YANG X B， HU S Y， et al. Regression test case reduction based on mutation analysis and coverage criterion[J]. Journal of Northwestern Polytechnical University，2017，35（3）： 494-499.）

[4] 华丽，李晓月，王成勇，等.能提高错误检测能力的回归测试用例集约简[J].湖南科技大学学报（自然科学版），2015，30（2）：99-103. （HUA L， LI X Y， WANG C Y， et al. Regression test suite reduction on improving fault detection capability[J]. Journal of Hunan University of Science & Technology （Natural Science Edition）， 2015， 30（2）： 99-103.）

[5] 王曙燕，陈朋媛，孙家泽.基于变异分析的测试用例约简方法[J].计算机应用，2017，37（12）：3592-3596. （WANG S Y， CHEN P Y， SUN J Z. Reduction method of test suites based on mutation analysis[J]. Journal of Computer Applications， 2017， 37（12）： 3592-3596.）

[6] 聂长海，徐宝文.一种最小测试用例集生成方法[J].计算机学报，2003，26（12）：1690-1695. （NIE C H， XU B W. A minimal test suite generation method [J]. Chinese Journal of Computers， 2003， 26（12）： 1690-1695.）

[7] HARROLD M J， GUPTA R， SOFFA M L. A methodology for controlling the size of a test suite [J]. ACM Transactions on Software Engineering & Methodology， 1993， 2（3）： 270-285.

[8] CHEN T Y， LAU M F. A new heuristic for test suite reduction [J]. Information and Software Technology， 1998， 40（5/6）： 347-354.

[9] LEE J G， CHUNG C G. An optimal representative set selection method [J]. Information and Software Technology， 2000， 42（1）： 17-25.

[10] MARCHETTO A， SCANNIELLO G， SUSI A. Combining code and requirements coverage with execution cost for test suite reduction [J/OL]. IEEE Transactions on Software Engineering， 2017 [2018-03-06]. https：//www.onacademic.com/detail/journal_1000040248934010_36b2.html.只查到优先发表的

[11] VAHABZADEH A， STOCCO A， MESBAH A. Fine-grained test minimization [C]// ICSE 2018： Proceedings of the 40th International Conference on Software Engineering. New York： ACM， 2018： 210-221.

[12] 章晓芳，徐宝文，聂长海，等.一种基于测试需求约简的测试用例集优化方法[J].软件学报，2007，18（4）：821-831. （ZHNAG X F， XU B W，NIE C H， et al. An approach for optimizing test suite based on testing requirement reduction [J]. Journal of Software， 2007， 18（4）： 821-831.）

[13] 顾庆，唐宝，陈道蓄.一种面向测试需求部分覆盖的测试用例集约简技术[J].计算机学报，2011，34（5）：879-888. （GU Q， TANG B， CHEN D X. A test suite reduction technique for partial coverage of test requirements [J]. Chinese Journal of Computers， 2011， 34（5）： 879-888.）

[14] USAOLA M P， MATEO P R， LAMANCHA B P. Reduction of test suites using mutation [C]// FASE 2012： Proceedings of the 2012 International Conference on Fundamental Approaches to Software Engineering， LNCS 7212. Berlin： Springer， 2012： 425-438.

[15] PAPADAKIS M， MALEVRIS N. Automatically performing weak mutation with the aid of symbolic execution， concolic testing and search-based testing[J]. Software Quality Journal， 2011， 19（4）： 691-723.

[16] MRESA E S， BOTTACI L. Efficiency of mutation operators and selective mutation strategies： an empirical study [J]. Software Testing Verification & Reliability， 2015， 9（4）： 205-232.

[17] DEMILLI R A， OFFUTT A J. Constraint-based automatic test data generation [J]. IEEE Transactions on Software Engineering， 1991， 17（9）： 900-910.

[18] 张功杰，巩敦卫，姚香娟.基于统计占优分析的变异测试[J].软件学报，2015，26（10）：2504-2520. （ZHANG G J， GONG D W， YAO X J. Mutation testing based on statistical dominance analysis[J]. Journal of Software， 2015， 26（10）： 2504-2520.）

[19] IIDA C， TAKADA S. Reducing mutants with mutant killable precondition [C]// ICSTW 2017： Proceedings of the 2017 IEEE International Conference on Software Testing， Verification and Validation Workshops. Piscataway， NJ： IEEE， 2017： 128-133.

[20] 李曉磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践，2002，22（11）：32-38. （LI X L， SHAO Z J， QIAN J X. An optimizing method based on autonomous animats： fish-swarm algorithm [J]. Systems Engineering — Theory & Practice， 2002， 22（11）： 32-38.）

[21] 张功杰，巩敦卫，姚香娟.基于变异分析和集合进化的测试用例生成方法[J].计算机学报，2015，38（11）：2318-2331. （ZHANG G J， GONG D W， YAO X J. Test case generation based on mutation analysis and set evolution [J]. Chinese Journal of Computers， 2015，38（11）： 2318-2331.）.