基于贪婪算法和搜索算法的组合测试用例生成算法

摘要

本发明公开了一种基于混合的组合测试用例生成算法，包括以下步骤：1)生成满足要求的覆盖数组，后续的操作以覆盖这个数组为判别标准。2)在覆盖率较低的情况下，根据贪婪算法特性，使用贪婪算法来生成测试用例。3)在覆盖率达到比例K后，贪婪算法遇到瓶颈，选择搜索算法替代，以期达到更优的效果。本发明的基于混合算法的组合测试用例生成算法，即保证了贪婪算法生成测试用例前期的高效，又能避免后期陷入局部最优的情况，为从业人员在做测试用例生成方向的工作时，提供一个可以思考的角度。

说明书

技术领域

本发明提出了一种新的组合测试用例生成算法，其基于贪婪算法和搜索算法的组合，该技术属于软件测试领域中的组合测试部分。利用恰到好处的对两种算法的取舍，根据覆盖率指标及时切换生成技术，以更快地生成测试用例。本发明有效地弥补了贪婪算法和搜索算法的缺陷，在高维的情况下更能体现本发明的优势。

背景技术

软件测试是软件开发生命周期中不可或缺的一个重要环节。通过对系统进行各种实际场景的模拟，通过测试用例对系统进行测试，可以保证系统的安全性。然而，在现实生活中，一个软件系统的参数可能有很多，这会导致测试用例数量达到成千上万个，因此组合测试用例生成算法应运而生。

贪婪算法试图在每次系统更新后，使用迭代技术找到当前的最佳选择，以达到最优解。在确定给定测试集时，确定一个测试用例作为源测试用例，然后迭代选择后续的测试用例。但是贪婪算法很容易陷入局部最优解，从而无法达到整体最优解。

搜索算法：许多搜索技术应用于许多领域，包括基于搜索的软件工程(SBSE)领域。作为组合测试的关键问题，生成覆盖数组已经得到了广泛的研究，并且已经应用了许多搜索技术，这些技术称为基于搜索的组合测试(SBCT)。SBCT是SBSE中基于搜索的软件测试(SBST)的一个分支。

本文提出基于贪婪算法和搜索算法的混合算法，用来生成组合测试用例，并给出测试用例生成工具。

发明内容

发明目的：为了解决传统的贪婪算法在生成测试用例时会陷入局部最优的情况，本文提出了一种基于贪婪算法和搜索算法的测试用例生成算法，并且设置动态覆盖率，在未达到设置的覆盖率之前采用贪婪算法，当达到覆盖率要求后，采用搜索算法生成测试用例。

技术方案：为了实现上述目的，本发明采用的技术方案为：

基于贪婪算法和搜索算法的测试用例生成算法，包括以下步骤：

步骤1)、生成满足要求的覆盖数组。

步骤2)、选择贪婪算法，如图2，根据贪婪算法的特性逐步覆盖数组。

步骤3)、当覆盖标准达到K后，贪婪算法可能会遇到瓶颈，选择搜索算法代替，如图3，以期达到更优的效果。

进一步的，所述步骤1)的具体步骤如下：

步骤1.0)、首先是构建数组，构建覆盖数组的目标是创建一个二维数组，其中所有与指定输入关联的t元组都会被覆盖。

步骤1.1)、组合测试使用覆盖表CA作为测试用例集，CA是一个大小为M×k维的矩阵。本发明中，测试用例条数，即覆盖表的大小标记为N；覆盖强度标记为t；待测系统参数个数为

进一步的，所述步骤2)的具体步骤如下：

步骤2.1)、使用贪婪算法，将每个因子与某个值绑定在一起，可以为该集合一次建立一行。一旦所有t元组都被覆盖，覆盖数组就完成了。本发明可以动态设置参数K，当覆盖率达到K时，将贪婪算法转换为搜索算法，避免陷入局部最优。

步骤2.2)、手动选择第一个测试用例T，T的选择会影响后续测试用例的生成。

步骤2.3)、根据步骤2.2)选中的测试用例T，选择测试用例T’，选择标准是转换成本最低，如果同时存在多个T’，则选择其中一个。在此阶段，覆盖率逐渐上升。

进一步的，所述步骤3)的具体步骤如下：

步骤3.1)、用户可以根据自己的实际需求，设置一个覆盖标准值K。如果标准值K设置得过高，则有可能在贪婪算法陷入局部最优时仍未达到K，会影响性能。

步骤3.2)、当覆盖率到达K时，本发明将选择搜索算法继续生成测试用例。

步骤3.4)、假定S为SUT应涵盖的所有未覆盖2值组合的集合，T

Fitness(t)＝|t(2-way)∩S|

其中Fitness用来来衡量每个候选者的质量。以此来选择候选者。因为这是搜索算法的一般方法，因此对于其他强度的组合也适用。

步骤3.5)、当步骤3.4)中S为空时，CA完全覆盖。

附图说明

图1是基于混合算法的组合测试用例生成流程图

图2是一般贪婪算法流程图

图3是一般搜索算法流程图

具体实施方案

下面结合附图和具体实施例，进一步阐明本发明，应理解这些实例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

为了解决传统的贪婪算法在生成测试用例时会陷入局部最优的情况，本文提出了一种基于贪婪算法和搜索算法的测试用例生成算法，并且设置动态覆盖率，在未达到设置的覆盖率之前采用贪婪算法，当达到覆盖率要求后，采用搜索算法生成测试用例。

技术方案：为了实现上述目的，本发明采用的技术方案为：

基于贪婪算法和搜索算法的测试用例生成算法，包括以下步骤：

步骤1)、生成满足要求的覆盖数组。

步骤2)、选择贪婪算法，如图2，根据贪婪算法的特性逐步覆盖数组。

步骤3)、当覆盖标准达到K后，贪婪算法可能会遇到瓶颈，选择搜索算法代替，如图3，以期达到更优的效果。

进一步的，所述步骤1)的具体步骤如下：

步骤1.0)、首先是构建数组，构建覆盖数组的目标是创建一个二维数组，其中所有与指定输入关联的t元组都会被覆盖。

步骤1.1)、组合测试使用覆盖表CA作为测试用例集，CA是一个大小为M×k维的矩阵。本发明中，测试用例条数，即覆盖表的大小标记为N；覆盖强度标记为t；待测系统参数个数为

进一步的，所述步骤2)的具体步骤如下：

步骤2.1)、使用贪婪算法，将每个因子与某个值绑定在一起，可以为该集合一次建立一行。一旦所有t元组都被覆盖，覆盖数组就完成了。本发明可以动态设置参数K，当覆盖率达到K时，将贪婪算法转换为搜索算法，避免陷入局部最优。

步骤2.2)、手动选择第一个测试用例T，T的选择会影响后续测试用例的生成。

步骤2.3)、根据步骤2.2)选中的测试用例T，选择测试用例T’，选择标准是转换成本最低，如果同时存在多个T’，则选择其中一个。在此阶段，覆盖率逐渐上升。

进一步的，所述步骤3)的具体步骤如下：

步骤3.1)、用户可以根据自己的实际需求，设置一个覆盖标准值K。如果标准值K设置得过高，则有可能在贪婪算法陷入局部最优时仍未达到K，会影响性能。

步骤3.2)、当覆盖率到达K时，本发明将选择搜索算法继续生成测试用例。

步骤3.4)、假定S为SUT应涵盖的所有未覆盖2值组合的集合，T

Fitness(t)＝|t(2-way)∩S|

其中Fitness用来来衡量每个候选者的质量。以此来选择候选者。因为这是搜索算法的一般方法，因此对于其他强度的组合也适用。

步骤3.5)、当步骤3.4)中S为空时，CA完全覆盖。

在组合测试领域中，生成测试用例算法各有优缺，本发明的基于混合算法的组合测试用例生成算法，即保证了贪婪算法生成测试用例前期的高效，又能避免后期陷入局部最优的情况。

以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。