组合测试用例优先排序算法及选择策略研究

Combinatorial test case prioritization (CTCP) aims at prioritizing a given combinatorial test suite according to certain criterion, in order to identify faults more quickly, and thus enable earlier fault analysis, characterization, and diagnosis. The current CTCP algorithms are mainly based on the greedy strategy, of which efficiency and local optimization affect testing effectiveness and efficiency of CTCP. In this project, we attempt to use new ways to promote the CTCP, according to the following three perspectives: 1) improving the performances of greedy CTCP algorithms; 2) using test case search to avoid the local optimization of greed CTCP algorithms; and 3) intelligently rather than blindly selecting CTCP algorithms. We first analyze some factors that influence greedy CTCP algorithms, in order to build a framework of greedy methods for prioritizing combinatorial test suites, so as to produce effective (or efficiency) greedy CTCP algorithms. Then, we combine search techniques with CTCP to propose search-based CTCP algorithms, which attempts to overcome the drawbacks of local optimization in greedy strategies. After that, we study how to intelligently choose appropriate CTCP algorithms in terms of different testing requirements or (and) types of combinatorial test suites, and then build the relationship among the testing requirement, the type of combinatorial test suite, and the CTCP algorithm, in order to support the intelligent selection to avoid the shortages brought by pure greedy CTCP algorithms.

组合测试用例优先排序旨在对给定的组合测试用例集依据一定的标准进行优先排序，以能够尽快地发现错误，进而能够较早地进行错误分析、定位和修复。当前该领域的排序算法大多直接采用贪心策略，其测试效果和测试效率受贪心算法的效率、局部优化的影响。本项目从提高该排序领域贪心算法性能、以测试用例搜索来避免贪心算法局部优化、以智能选择来避免盲目选择排序算法的不足等三个方面着手，尝试用新方式推进组合测试用例优先排序方法。项目首先分析基于贪心思想的组合测试用例优先排序算法的影响因素，以搭建算法框架进而获取高效的贪心算法。接着结合搜索技术，提出基于搜索思想的组合测试用例优先排序算法，以克服贪心策略的局部优化所带来的不足。在此基础上，本项目研究依据测试需求或（和）组合测试用例集的类型智能地选择合适的优先排序算法，建立测试需求、组合测试用例集的类型与优先排序算法的三方关联，以此智能选择来避免纯粹基于贪心策略方法不足。

组合测试用例优先排序（CTCP）在近些年得到了广泛的研究，目前大多直接采用贪心策略，其测试效果和测试效率受贪心算法的效率、局部优化的影响。本项目从提高该排序领域贪心算法性能、以测试用例搜索来避免贪心算法局部优化、以智能选择来避免盲目选择排序算法的不足等三个方面着手，尝试用新方式推进组合测试用例优先排序方法。项目首先分析基于贪心思想的组合测试用例优先排序算法的影响因素，以搭建算法框架进而获取高效的贪心算法。接着结合搜索技术，提出基于搜索思想的组合测试用例优先排序算法，以克服贪心策略的局部优化所带来的不足。在此基础上，本项目研究依据测试需求或组合测试用例集的类型智能地选择合适的优先排序算法。. 在本项目中，我们提出了一系列高效的CTCP算法，包括基于重复Base-Choice的CTCP算法、基于低力度组合覆盖循环迭代的CTCP算法、基于低力度组合覆盖权重的CTCP算法、以及基于搜索思想的CTCP算法。通过充分的实验表明，我们的贪心算法在保证测试性能的同时，能够较大幅度降低时间开销。而且，基于搜索思想的CTCP算法能够有效地提高错误检测速率和组合覆盖速率。此外，我们提出了两种组合测试用例集的类型分析技术：基于聚类的组合测试用例集分类技术和基于统计分布的组合测试用例集分类技术。在此基础上，我们提出了通过分析组合测试用例集的类型来选择合适的CTCP算法。当测试需求有约束的时候，有些CTCP算法就不适用，因此，我们通过大规模的实验分析了当前CTCP的测试性能和测试效率，给出了基于测试需求的CTCP算法选择准则。最后，我们设计并开发了组合测试用例优先排序算法及选择策略原型系统，用以支持并实现所提出的方法。我们的研究丰富了组合测试用例优先排序的技术，进一步促进了组合测试和回归测试的发展。