魏晶+王燕+徐家喜

摘要：启发式搜索算法因其能够生成规模较小的覆盖表，一直是组合测试中覆盖表生成主要技术之一。然而，因该类算法需要较长的计算时间，在实际应用中往往受限。近年来，一些研究对启发式搜索算法进行并行化，以提高算法速度。但这些研究未能全面考虑影响并行化效果的各种因素，如测试模型、覆盖强度以及搜索算法配置等。为此，该文选取了8个测试模型，使用遗传算法进行2-3维覆盖表的生成，系统地探索了影响遗传算法并行化性能的因素，从而为遗传算法并行化提供理论和实践基础。

关键词：组合测试；覆盖表；遗传算法；并行化

1背景

近年来，软件系统的功能日益强大，其运行环境也具有分布式化、网络化和复杂化等特点。为支持多平台和多场景，大部分软件系统都被设计成可配置系统。但这也导致这些系统的测试面临庞大的组合空间。当配置选项较多时，要进行穷尽测试几乎是不可能的，也是不切实际的。例如，对于一个有10个参数、每参数3个取值的待测系统，它的组合测试空间在不考虑约束的情况下将高达3。为此，我们需要对巨大的组合测试空间进行抽样，组合测试就是其中一种抽样测试。组合测试（Combinatorial Testing，CT）采用系统的抽样机制对参数间的交互作用进行有针对性的覆盖，从而极大地减少测试用例的规模。已有研究表明，软件系统中大约70%的故障是由两个参数间的交互作用引起的，并且与故障相关的参数个数一般不超过6个，因此CT是一种能有效地检测系统中交互式故障的测试方法。

组合测试使用覆盖表（Covering Arrays，CA）作为测试用例集，它的重要研究内容之一是如何为待测系统生成一个满足特定覆盖需求且规模最小的覆盖表。目前生成覆盖表的方法主要有3类：贪心方法、启发式搜索方法以及数学方法。数学方法能快速地生成理论上规模最小的覆盖表，但其对参数及参数取值个数有一定的限制；贪心算法和随机算法虽然在参数上没有限制，但其生成的覆盖表规模往往较大。与上述方法相比，启发式搜索算法如禁忌搜索算法、遗传算法、模拟退火算法、蚁群算法、粒子群算法等既能生成较小规模的覆盖表，又能不受参数及其取值个数限制，应用于任何待测系统。近年来启发式搜索算法受到众多研究者的青睐，然而启发式搜索算法通常需要较长运行时间，这限制了其在实际中的应用。

为了提高启发式搜索算法运行速度，一些研究者开始对启发式算法进行并行化。例如，基于Hadoop MapReduce进行遗传算法并行化，并为开源软件库Apache Commons Primi—tives生成JUnit测试用例集。而基于Spark进行遗传算法并行化，并選取四个测试模型进行2维覆盖表的生成。虽然这些研究能不同程度地提高算法速度，但也存在一些不足之处：第一，文献选取的待测实例过少，不足以说明并行化效果。例如，只有一个待测实例，也只有四个。第二，启发式搜索算法通常存在多个影响算法性能的决策点，但现有的研究未能考虑这些决策点不同取值对并行化效果的影响。针对已有工作不足，本文从如下两方面开展工作：

第一，选取多种遗传算法决策点取值，探索算法决策点对并行化影响。

第二，选取多种测试模型和覆盖强度，探索测试模型和覆盖强度对并行化影响。

本文剩余部分内容安排如下：第2节介绍相关背景知识，如覆盖表，启发式搜索算法等基本概念；第3节给出遗传算法生成覆盖表框架以及并行化方法；第4节为具体实验及实验结果分析；第5节讨论影响实验结果的有效性因素；最后一节给出本文结论及未来研究方向。

2相关知识

2.1覆盖表相关概念

组合测试使用覆盖表CA作为测试用例集，CA是一个大小为NXK大小为N×K的矩阵，通常表示如下

其中N为覆盖表的大小即测试用例条数，t为覆盖强度，待测系统参数个数，其中取值个数为v，的参数有。覆盖表的一个重要性质是表中任何一个Nxt子矩阵都能覆盖相应t个参数所有可能t维取值组合至少一次，覆盖强度为t的覆盖表称t-way或t维覆盖表。这里的参数可为待测系统配置选项、输入以及消息事件等。在未作特殊说明情况下，本文用N表示覆盖表大小，k表示参数个数，v表示所有参数取值集合，表示第i个参数取值集合，表示第i个参数取值个数。

例如，表1为一部手机通话功能的简单测试模型，该测试模型共5个参数，每参数3个取值。对于该系统，可找到一个大小为11的覆盖进行2-way测试，对应的2-way覆盖表可表示为CAfll；2，3），覆盖表具体内容见表2。

容易看出，该手机通话功能测试模型中的任意两个参数的9个取值组合在表2中都至少出现一次。例如号码来源和对方系统设置这两个参数的9个取值组合（直接输入，无限制）、（直接输入，黑名单）、（直接输入，呼叫转移）、（电话簿，无限制）、（电话簿，黑名单）、（电话簿，呼叫转移）、（通话记录，无限制）、（通话记录，黑名单）、（通话记录，呼叫转移）分别出现在表2中第4f或91行、第7行、第1行、第11行、第5行、第8行、第2行、第3行、第6（或10）行。

2.2启发式搜索算法

启发式搜索算法在覆盖表生成时，通过适应度函数将覆盖表生成问题转化为函数优化问题，然后利用某搜索算法来解决函数优化。目前常见用于覆盖表的启发式算法主要有：遗传算法、粒子群优化算法、蚁群算法、爬山算法、模拟退火算法、禁忌搜索算法等。

本文以遗传算法为例，探索影响启发式搜索算法并行化的因素。在接下来的第3节首先对遗传算法生成覆盖表的流程以及并行化方法进行介绍。

3遗传算法生成覆盖表框架及并行化

遗传算法（Genetic Algorithm）是一种通过模拟自然世界生物进化过程，探索问题最优解的演化搜索算法，该算法已被广泛地用于复杂的优化问题。在遗传算法中，问题的一组候选解以染色体的形式构成算法的初始种群，算法对每一代种群中的染色体进行交叉变异，然后通过适应度函数值这一评价标准淘汰适应值较差的染色体，保留适应值较好染色体进人下一代，直到某一代种群中出现适应值满足问题要求的染色体，该染色体即为问题的最优解。

3.1遗传算法生成覆盖表流程

考虑到覆盖表是一个NxK大小的矩阵，因此本文将种群中的染色体也称个体设置为NxK大小的矩阵，个体的适应度函数值为矩阵所覆盖的t维取值元组数。生成思路为：首先采用某种方法初始化种群中的每个个体，然后通过一定的交叉变异等进化使种群中的某个体达到全覆盖，那么这个个体便是最终的覆盖表，算法框架如算法1。

在算法1中，行1一行5为覆盖表生成初始化工作；行6至行18构成的循环为种群的进化；行19返回种群中适应度函数值最大的个体。当适应度函数最大值为NATf需要被覆盖的t维参数取值元组数）时，对应个体即为覆盖表。在进化过程中，首先在种群中按照一定的算法选取一半个体作为双亲，然后进行两两交叉（行8至行11），交叉产生的子代依一定的概率进行变异（行13），最后再用这些子代去替换父代中适应度函数值较差的那些个体进行种群更新（行15）。

显然，算法1只提供了遗传算法生成覆盖表的框架，在具体实现时还需要确定种群初始化方法、种群大小、最大迭代次数、双亲选择算法、交叉算法、变异概率等。这些决策点会影响算法的性能，它们的取值我们将在第5节实验部分进行讨论。

我们注意到，在算法1的输人中需要给出覆盖表大小N，为了降低测试成本，通常该值是算法针对某个待测系统所能生成的覆盖表规模最小值。但事实上却很难事先确定这一值。本文解决的方法是：我们在算法1外面加了一层循环，用来确定N。首先让N从一个较大值开始保证该规模的覆盖表能成功生成；如果某一规模N的覆盖表成功生成，则将N=N-1；然后重新利用算法1生成新规模覆盖表；否则，算法结束，N-1便是所能生成的覆盖表规模最小值。

3.2遗传算法生成覆盖表并行化

并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是利用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行处理。并行计算系统既可以是专门设计的、含有多个处理器的单台计算机，也可以是以某种方式互连的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。本文采用单台计算机进行本地并行化，集群下的并行化将是我们下一步工作。

在编程模型方面，本文选用了Java提供的ForkJoin框架。在该框架下，对于一个能被分解成多个子任务，并且通过组合多个子任务的结果，就能够获得最终结果的应用，软件开发人员仅需关注如何划分任务和组合中间结果，其余工作，如同步、通信、死锁等各种并行相关事务由ForkJoin來完成，这样大大简化了并行程序的编写。ForkJoin原理如图1所示。

在图1中，当原始任务Task0的规模比设定的阈值大，则按照向下箭头将其一分为二拆分成2个子任务Task0-1和Task0-2。如果Task0-1、Task0-2的规模仍然比设定的阈值大，则继续拆分它们，这样得到4个子任务Task0-1-1、Task0-1-2、Task0-2-1、Task0-2-2。如果这4个子任务的规模不再大于设定的阈值，则开始执行这些子任务，并将执行结果按照向上箭头进行合并，这样可得到最终结果。

1）任务拆分

由图1可以看出，并行化的第一步是任务拆分，一个任务能被拆分成多个子任务的条件是这些子任务之间需要相互独立，能并行执行。在遗传算法生成覆盖表的算法1中，行6至行18构成的循环是算法的主体，因此，将该部分进行并行化能有效提高算法执行效率。容易看出，在算法1的循环中，每次循环都依赖前一次的结果，因此不同循环之间不能并行进行，此时只能考虑将循环中需要执行的比较耗时的操作进行拆分。我们注意到算法1中行12所描述的交叉操作共涉及到pSize/4对双亲两两交叉，这些双亲交叉之间相互独立，因此可以拆分，利用不同子任务实现对不同双亲的交叉。同理，子代变异（行13）、子代个体适应度函数值计算（行14）以及种群更新（行15）也都可以拆成多个可并行执行的子任务，图2给出了算法1可以并行执行的操作，用加粗部分表示。

2）编程实现

任务拆分后，接下来进行编程实现，下面以子代的变异并行化为例，对ForkJoin框架下的并行化编程进行说明。

首先，将所有需要进行变异的子代存入一数组offspring中。

然后，创建一个ForkJoin任务，如

上式中MutateTask是一个用户自定义类。为了实现Fork-Join任务，MutateTask需要继承Java提供的RecursiveAction或者RecursiveTask类，这两个类的区别是前者用于任务没有返回结果的场景，后者用于任务有返回结果的场景，MutateTask具体实现请参见算法2。其中参数offspring为第一步中定义的数组，offspring.Jen为offspring中的元素个数也就是子代的个体数。参数1和offspring.len表示需要变异的个体从第一个子代个体到最后一个子代个体，即对所有子代个体进行变异。

最后，通过ForkJoinPool来执行任务，如

在MutateTask类中：

首先，MutateTask选择继承RecursiveAction（行1），因为变异后的子代直接存放回原数组offspring中，因此不需要返回结果。

接着，在该类的构造函数中进行相关数据赋值（行5-9），这些数据包括存放子代的数组offspring，本次任务中需要进行变异的个体在offspring中的位置下界beg和上界end。

最后，重写computer方法（行11-23）。在compute方法中，首先判断当前任务中需要进行变异的个体个数是否大于设定的阈值（行12）。若不大于，则对规定区间中的每个个体逐个进行变异（行19-21）。否则，把当前任务一分为二（行13-15），然后启动这两个子任务的执行（行16）。由于这两个子任务又属于MutateTask类，因此在它们的执行过程中又会进人该con-pute方法。该方法体现了图1所示的Fork/Join原理，通过递归来完成任务的拆分和计算，它是区别于其他普通类的关键之处。

有关ForkJoin框架并行化编程更多细节请参考Java相关帮助文档。

3实验及结果分析

并行化是提高启发式搜索算法生成覆盖表速度的有效手段，但并行化性能通常会受到多种因素的影响，本文通过研究遗传算法并行化明确了影响搜索算法并行化性能的主要决策点，并进一步阐述了待测系统和覆盖强度对搜索算法并行化性能的影响。

3.1实验设计

为了回答上述问题，我们首先选取多种不同测试模型和覆盖强度，然后在某种决策点配置下分别使用串、并行遗传算法进行相应覆盖表生成，接着改变决策点取值重复实验，最后通过比较和分析并行化前后覆盖表生成速度，来探索影响搜索算法并行化性能的因素。

本文衡量算法覆盖表生成速度的方法是：实验中记录每个覆盖表生成时间与所经过迭代次数，然后计算出两者的比值，将该比值记为单次迭代时间。每个实验重复5次，最后用5次的平均单次迭代时间来衡量算法速度。

这里用单次迭代时间来衡量算法的速度，主要是考虑到在实验次数较少的情况下，覆盖表生成时间随机性比较大，然而单次迭代时间却能基本保持不变，因此用单次迭代时间较覆盖表生成时间更能真实地反映算法本身速度。

本文从中选取了8个测试模型（见表3），实验中，对每个模型分别使用串、并行遗传算法进行2-3维覆盖表生成。

为了描述方便，我们将串、并行遗传算法分别命名为SGA（sequential Genetic Algorithm）和PGA（Parallel Genetic Algo-rithm）。

实验选用的软硬件配置为：Intel i7-4790CPU、3.60GHZ、8.0GB内存、64位Windowsl0、32位JAVA7。

3.2實验结果

1）决策点初始配置及实验结果

决策点的配置会影响算法生成覆盖表的时间和所生成的覆盖表规模。然而大量研究表明，实际上不存在任何一种决策点配置能够对任意待测系统在最短时间内生成最小覆盖表。本文旨在研究并行化对算法速度的影响，因此不要求这些决策点取值都达到最优，故决策点初始配置选用了一些常用取值。初始配置具体如下：

随机初始化种群、种群大小80、根据个体适应度函数值利用轮盘赌算法选择双亲、单点交叉、变异概率0.01。两双亲单点交叉时，首先随机生成交叉位置pos，其中然后互换两双亲pos前后的行，这样产生两子代个体；子代变异时子代个体对应矩阵中的每个元素以0.01的概率随机改变取值。

SGA和PGA在初始配置下的实验结果如表4所示。其中，size为覆盖表规模，SGAtime和PGAtime分别为SGA和PGA生成覆盖表的单次迭代时间（单位为秒），speed up为两者的比值，该比值反映了PGA的速度与SGA的速度的比值，因此，可以用该指标表示并行化加速情况，称其为并行化加速比。

2）决策点新配置及实验结果

接下来，我们首先改变遗传算法的种群大小，将其设置为160，算法其它参数配置与初始配置相同。为了使结果不受覆盖表行数的影响，覆盖表行数也保持与前一实验相同。在新配置下，重新对表3中的测试模型进行2-3维覆盖表生成，实验结果如表5。

对比表4和表5可知，增大种群大小明显提高了并行化加速比。平均来看，遗传算法的加速比由原来的3.38倍提高到6.1倍。这一结果有力说明了，种群大小是影响并行化性能的重要因素。分析其中原因不难发现，在硬件资源足够多和不考虑子任务之间通信时间方面开销的情况下，并行执行的子任务数是影响并行化提速的主要原因，并行执行的子任务数越多，并行化加速越快。对于遗传算法，由3.2节可以看出，种群大小是决定并行执行子任务数的主要因素，因此，增大种群大小明显提高了并行化加速比。

随后，我们又依次改变种群初始化方法、双亲选择策略、交叉方法、变异概率等，实验结果表明，改变这些决策点的配置都不会明显影响遗传算法并行性能。限于篇幅，本文没有给出这些实验具体结果。

3）测试模型及覆盖强度对并行化影响

进一步观察表4和表5还可以发现，在同一算法配置下，不同测试模型及覆盖强度下并行化加速也不同。例如，在表5中，s1模型的2维并行化加速仅为1.82，而s8模型的3维并行化加速高达6.27。

为了衡量测试模型和覆盖强度对并行化的影响，我们根据表4-表7中的数据，给出了串行单次迭代时间与并行化加速比speedup之间的曲线图，具体如图3和图4。在这些图中，横坐标为串行单次迭代时间，纵坐标为并行化加速比。我们知道，不同测试模型及覆盖强度的覆盖表串行生成时间是不同的。测试模型越复杂（即待测系统中的参数个数和每个参数取值个数越大），覆盖强度大越大，覆盖表串行生成时间就越长，因此覆盖表串行生成时间能反映出测试模型的复杂度和覆盖强度的大小。

由图3和图4可看出，对于遗传算法，无论种群大小是80还是160，总体上，并行化加速比开始时随着串行单次迭代时间增加而快速增加，然后逐渐趋于平稳。这是因为，当测试模型比较简单、覆盖强度比较小时，即串行生成时间比较短，此时并行算法中的子任务创建、销毁以及子任务之间的通信等所消耗的时间占总生成时间的比例比较大，导致并行化加速比比较小；此后随着测试模型复杂度以及覆盖强度的增大，覆盖表生成时间随之增大，因此并行通信额外消耗的时间占总生成时间的比例将逐渐降低，并行加速比呈现出上升趋势；最后当单次迭代时间的增加到一定值后，这部分额外时间相对总生成时间可以忽略不计，此时并行加速比趋于稳定。

3.3实验结论

首先，并行执行的子任务数是影响并行化加速的重要因素。对于遗传搜索算法，种群大小是决定并行执行的子任务数主要因素。因此，种群大小是影响遗传算法并行化性能的主要决策点。

其次，测试模型和覆盖强度也会影响并行化性能。总体上，并行化加速比随着测试模型中的参数个数、每个参数取值个数以及覆盖强度的增加而增加并逐渐趋于稳定。

4影响实验结果有效性因素

实证性和实验性研究通常都存在影响实验结果有效性的因素，本文也不例外，下面我们主要从三个方面对影响本文实验结果有效性的因素进行分析：

首先，本文只选用了遗传算法作为启发式搜索算法研究对象，更多的搜索算法能带来更准确的实验结果。

其次，本文虽然选取了一批具有代表性的实例作为实验对象，但对于其它的实例实验结果可能会有所变化。

最后，由于实验较为耗时，本文只对实验重复了5次，利用单次迭代时间来衡量算法速度。虽说单次迭代时间较总生成时间更为稳定，但仍不能排除随机因素的影响。5结论及未来研究方向

覆盖表生成作为组合测试关键问题之一，一直受到工业界和学术界的重视。为了提高启发式搜索算法速度，一些研究者开始对算法进行并行化。本文在已有的研究工作基础上，系统地探索了遗传算法决策点和测试模型以及覆盖强度对并行化性能的影响。

实验结果表明，对于遗传算法，种群大小是影响算法并行化提速的重要因素。另外，测试模型和覆盖强度也会对算法并行化性能产生一定影响。

目前，本文利用ForkJoin框架进行算法本地并行化，但由于受到单机硬件资源限制，并行化加速有限。因此，在下一步工作中，我们计划将实验迁移到分布式或云平台环境中，利用这些平台超强的并行化计算能力更快更好地实施实验，进一步研究启发式搜索算法并行化。