刘 音 范 雯 徐林雪

（北京交通大学海滨学院 河北·沧州 061199）

0 引言

从软件工程的角度来说，软件质量是满足内在系列特征要求的程度，即是否符合功能性、可靠性、易用性、可维护性和可移植性等各方面要求，直接影响着软件的使用和维护。在软件的生命周期中，软件测试是一个重要环节，是质量保证的重要手段。Boris Beizer报告称，开发一个可工作的程序的一半工作量一般都消耗在测试活动上。

测试用例（Test Case,TC）指的是一套详细的测试方案，包括测试环境、测试步骤、测试数据和预期结果，是将测试具体量化的方法。软件测试主要通过执行测试用例来查找软件中存在的缺陷，测试用例设计的好坏不仅影响到软件产品的质量而且关系到开发成本。

回归测试是指修改代码后重新对软件进行测试的工作，在整个软件测试过程中占有很大的工作量比重。随着软件功能和实现发生了演变，原始测试用例库中的一些测试用例可能失去作用，需要针对修改的和添加的功能，设计新的测试用例，从而导致测试用例库有可能变得相当大，不可能执行所有测试用例完成回归测试。

1 测试用例优化

目前测试用例优化技术主要包括测试用例优先选择和测试用例优先级排序技术。测试用例的选择和执行策略，直接影响测试效率和成本。

1.1 测试用例优先选择

测试用例优先选择技术又称测试用例约简，侧重于研究测试用例最小化，即保持原测试用例集错误检测能力基础上，依据一定的规则去除冗余测试用例，缩减测试用例规模，选取最少的测试用例来覆盖所有测试需求，降低执行测试用例的成本。1993年，M.J.Harrold等人首次提出测试用例约简的概念，在原始用例集中，找到一个与原始测试用例集，拥有一样的测试覆盖率的最小测试用例子集。可以利用启发式算法（贪心算法、HGS算法、GE算法、GRE算法和遗传算法等）解决测试用例约简问题。

贪心算法求解测试用例约简过程：从测试用例集中挑选出一个测试用例，使其最大限度的覆盖尚未被覆盖的测试需求，直到覆盖所有测试需求。HGS算法先将测试需求分成若干组，然后从测试用例集中选择最少数量的测试用例覆盖每组测试需求。GE算法是先找到必不可少的测试用例，再使用贪心算法。GRE算法交替进行必要和1-1冗余测试用例的查找，直到不存在这两种测试用例为止，最后再使用贪心算法选择测试用例。遗传算法是一个智能全局搜索算法，利用生物遗传和进化过程求解全局最优解的近似解。

1.2 测试用例优先级排序

根据研究表明：测试用例库中，前10%-15%的测试用例可以发现软件中75%-90%的错误。优先级排序技术旨在采用一定的排序策略，更快的检测出错误，提高现在测试用例集的性能。2000年，Rothermel给出了测试用例优先级定义：在测试用例集T的全排列集PT中，执行任意一个全排列T’时，对应的输出函数值f越大，则T’的排序效果越好。

排序目标是以最快速度检测出缺陷，一般以错误检测率、检测错误等级和检测错误类型等作为排序依据，Rothermel等提出了基于测试用例分支覆盖能力的排序方法，Elbaum等提出了基于测试用例耗费和错误严重性的排序方法，Jones等提出了基于MC/DC覆盖率的排序方法等，Wong等人提出以累计覆盖率对测试用例进行排序，Srikanth提出基于测试用例对需求的满足情况的排序方法，Walcott等提出基于测试用例的历史执行时间的排序方法，Zhang等提出基于线性规划的排序方法，Jiang等提出基于错误定位的排序方法。

2 本文工作

测试用例约简的理想结果是：在完全覆盖测试需求的前提下，执行测试用例集的代价最小。但在有限资源的条件下，还要求测试用例集有较快速的错误检测能力，因此优化测试用例时，不仅要缩减测试用例规模，而且测试时要考虑执行用例的顺序。本文采用二者相结合的方法进行测试用例优化，先对测试用例进行约简，然后在对测试用例进行优先级排序。

2.1 实现测试用例约简

遗传算法是模拟生物进化过程的全局搜索方法，通过选择、交叉和变异操作得到问题最优解。基于遗传算法的回归测试测试用例约简步骤如下：

（1）依据测试用例与测试需求的覆盖关系，采用二进制编码初始化种群，种群规模大小由测试需求数量决定，个体基因码长度由测试用例数量决定。

（2）以测试用例与测试需求的覆盖关系，设计适应度函数：f ti=cov i。

（3）应用轮盘赌选择算子产生中间代，单点交叉算子和单点变异算子操作产生新一代种群。

（4）循环操作步骤3，直到新一代种群满足终止条件。

（5）解码，得到约简后的测试用例。

2.2 实现测试用例优先级排序

本文采用基于错误检测率的覆盖率技术对测试用例进行排序，错误检测率是单个测试用例在单位时间上检测到的错误数量。

公式1中RFDn表示第n个测试用例的错误检测率，FNn表示第n个测试用例检测的错误数量，CTn表示第n个测试用例执行所花费的时间。错误检测率越大测试用例对应的优先级越高。测试用例优先级排序算法如下：

（1）计算每个测试用例的优先级（错误检测率）。

（2）依据优先级降序排序测试用例。

（3）输出排序后的测试用例集。

2.3 实现测试用例优化

采用遗传算法进行测试用例集约简，然后对约简结果按照错误检测率进行降序排序，得到最终优化结果，实现流程如图1所示。

图1：测试用例优化流程

3 仿真实验

本文采用matlab作为仿真开发环境，从测试用例最小化后用例集规模和检测错误的速度上分析算法性能。交叉概率设定为0.6，变异概率设定为0.01。选择5个程序作为测试对象，每个程序的初始测试用例是由小组成员精心设计的，实验结果如表1所示。通过实验分析发现：

表1：实验结果对比

（1）遗传算法能有效的缩减测试用例集规模。

（2）由测试用例未排序和排序后错误检测情况对比可知，排序后的测试用例能有效缩短测试时间。

4 结论

采用遗传算法进行测试用例集约简，将已有测试用例错误检测率作为用例优先级，并按照用例优先级取值高低决定测试用例执行顺序。这种优先选择和优先级排序结合的技术，即有利于去除冗余测试用例，又有利于尽快检测到程序中的错误，提高测试效率，降低测试成本；当测试时间有限时，能够在有限时间内执行更多有效的测试用例，充分地保证软件质量。