晏慧，康茜，雷建云

(中南民族大学 计算机科学学院，武汉 430074)

软件测试是保障软件质量的重要手段,是构建高可信软件的关键环节.软件测试占软件开发总成本的比例一般达到50% 以上[1].为了修复软件中未发现的问题或者满足客户提出的新的需求，常常需要对软件不断地修改，软件迭代过程中容易引入新的缺陷，导致软件质量受到影响.回归测试可有效解决此类问题，避免软件演化带来的副面影响.最简单的办法是将所有测试用例重新执行一遍，但存在如下问题：

(1)如果项目复杂，测试用例集庞大，执行所有代码代价较大，会导致超出项目预算或者延长软件开发周期.例如ROTHERMEL等人在某一合作企业内，在测试一个包含约20000行代码的软件产品时发现，运行所有测试用例所需时间长达49 d[2].

(2)对部分代码修改会影响到被测模块的原有外部接口或内在语义，并导致部分测试用例失效[1].

这使得研究如何提升回归测试的效率变得有意义.常见的测试用例维护技术有：失效测试用例的识别和修复、测试用例选择、测试用例优先排序(test case prioritization, TCP)、测试用例缩减和测试用例扩充[3].

测试用例优先排序策略是将所有测试用例按照一定约束进行处理并排序，从而在进行回归测试时，能使用较少的测试用例检测出较多软件缺陷的算法.李征等人通过将TCP问题多项式时间规约为背包问题, 证实该问题是一个NP难问题[4].同时他引入元启发式算法(如蚁群算法、遗传算法……