软件测试是一种度量和提高软件质量的重要手段.近年来, 软件系统功能日益强大和复杂, 为支持多平台和多场景, 大部分软件系统都被设计成可配置系统.然而, 对这些系统的测试却面临巨大的组合空间.例如:对于一种有10个参数、每参数3个取值的待测系统, 它的组合测试空间在不考虑约束的情况下将高达3¹⁰.对这样一个系统要进行穷尽测试几乎是不可能的, 也是不切实际的.因此, 我们需要对组合测试空间进行抽样, 从中选取一批测试用例对系统进行有效测试.组合测试便是其中一种.

组合测试CT(combinatorial testing)采用系统地抽样机制对参数间的交互作用进行有针对性的覆盖, 从而减少测试用例的规模^{[1, 2]}.已有研究结果表明:软件系统中大约70%的故障是由两个参数间的交互作用引起的; 同时, 与故障相关的参数个数一般不超过6个^[3].因此, 组合测试是一种科学有效的软件测试方法.

组合测试使用覆盖表CA(covering arrays)作为测试用例集, 它的重要研究内容之一是覆盖表生成问题, 即:如何针对具体的待测系统, 在满足特定覆盖需求前提下, 生成一个规模尽可能小的测试用例集, 以便在保证错误检查能力的前提下, 尽可能降低测试成本.由于覆盖表的生成已被证明是一个NP困难问题, 国内外诸多专家和学者进行了广泛、深入的研究, 提出了很多方法, 这些方法主要分成3类:贪心算法^[4-7]、启发式搜索算法^[8]以及数学方法^{[9, 10]}.数学方法能快速地生成理论上规模最小的覆盖表, 但其对参数及参数取值个数有一定的限制; 贪心法虽然在参数上没有限制, 但其生成的覆盖表规模往往偏大.与上述方法相比, 启发式搜索法, 如禁忌搜索算法^[11]、遗传算法^[12]、模拟退火算法^[13]、蚁群算法^[14]、粒子群算法^[15]等, 既能生成较小规模的覆盖表, 又能不受参数及参数取值个数限制, 应用于任何待测系统.近年来, 越来越多的研究致力于利用启发式搜索算法来解决软件测试中的各类问题, 人们也开发了一系列的测试工具^[16].然而, 相对于其他方法, 启发式搜索算法也有一定的局限性, 如速度过慢.

本文重点关注禁忌搜索算法在覆盖表生成中的研究.禁忌搜索算法TS(tabu search)作为一种启发式搜索算法, 最初由Glover^[17]教授在20世纪70年代提出.它通过模仿人类的记忆功能, 使用禁忌表封锁一些局部最优解, 来达到接纳一部分较差解, 从而跳出局部最优.目前, TS已在通信、网络设计、结构优化、人工智能、工业制造、金融分析等多领域得到广泛应用.近几年, TS还被成功应用到覆盖表生中^{[11, 18]}, 更新了许多覆盖表规模上界.但是, 这些研究仍存在不足:第一, TS生成覆盖表的性能通常会受到如初始化方法、最大迭代次数、禁忌表、邻域函数等这些决策点取值的影响, 为了获得最优性能, 一些文献[11]进行调优, 得到一组最优参数配置, 但是该组参数配置仍可改进; 第二, 在实际应用中, 待测系统的参数间普遍存在约束, 且不同参数交互力度不同, 甚至一些参数间无交互, 然而已有的TS只考虑了无约束、固定力度情况下的覆盖表生成; 第三, TS生成覆盖表的演化过程很长, 通常需要几十万次甚至上百万次迭代, 非常耗时, 据我们所知, 目前还没有公开文献进行TS生成覆盖表加速的相关研究.针对上述3个问题, 为了进一步提高TS在覆盖表生成问题上的应用潜力, 本文提出了一种新的TS算法PTS_CVS(parallelized tabu search with constraint and variable strength handling), 该算法主要从如下3方面开展工作.

● 首先, 在TS的决策点上, Gonzalez-Hernandez等人^[11]曾通过大量实验对TS的初始矩阵、最大迭代次数、禁忌表长度、以及邻域函数这4个决策点进行了调优, 提出了MiTs算法.MiTs算法的最大特点是邻域函数由多种不同收敛速度的函数复合而成, 这在一定程度上平衡了搜索的集中性和多样性.然而, 这种做法是以牺牲搜索速度作为代价, 同时, 构成邻域函数的各分量函数的权值系数也较难确定.根据Jia等人^[19]的研究, 各分量函数的权值系数应根据测试模型动态选取而不是一成不变.在本文中, 我们结合上述工作一方面调整了TS决策点, 同时使用新的调优方法, 最后获得了一组新的TS决策点配置, 使得TS无论在覆盖表规模上还是覆盖表生成时间上都达到最佳性能;

● 其次, 在实际应用中, 参数间的约束关系是普遍存在的^[20-23].例如表 1所述的手机通话功能测试模型中, 当对方场景模式为飞行模式, 对方状态不可能是正在打电话.如果在覆盖表生成时没有对约束进行合适的处理, 将会生成很多无效测试用例, 从而降低测试的有效性; 同时, 在实际应用中, 参数间的交互力度往往不是统一的, 一些参数间关系比较紧密, 一些则相对松散, 甚至还有一些无任何交互.但是, 已有的TS算法^{[11, 18, 24, 25]}既不支持约束的处理, 也不支持可变力度覆盖表的生成.为此, 本文把TS和基于禁止元组的约束处理方法进行结合使其支持约束处理, 同时对TS进行扩展, 使其能生成可变力度覆盖表, 从而增强TS的应用潜力;

● 最后, TS生成覆盖表的时间开销也是影响其应用的重要因素.为了提高TS的生成效率, 本文采用Java的ForkJoin框架对TS进行并行化, 该框架充分利用计算机的多核特性以提高算法速度.

本文主要提出了一种新的TS算法, 该算法不仅可以生成规模较小的覆盖表, 还可以进行约束和可变力度处理; 进行TS算法并行化, 加速了覆盖表的生成; 给出了一系列实验, 系统地评估了所提出算法的性能.

第1节介绍组合测试相关知识以及TS生成覆盖表的通用流程.第2节进行TS生成覆盖表的配置参数调优.第3节介绍约束处理、变力度处理和并行化处理方法.第4节为实验, 用于检验PTS_CVS生成覆盖表的性能.第5节讨论影响本文实验结果的有效性因素.第6节介绍相关工作.最后, 第7节给出本文结论及未来研究方向.

1 背景 1.1 覆盖表相关概念

组合测试使用覆盖表CA作为测试用例集, CA是一个大小N×k为矩阵, 通常表示如下^[1]:

$ CA(N;t,v_1^{{k_1}}v_2^{{k_2}}...v_m^{{k_m}}). $

上式中, N为覆盖表的大小即测试用例条数; t为覆盖强度; $k = \sum\limits_{i = 1}^m {{k_i}} $为待测系统参数个数, 其中, 取值个数为v_i的参数有k_i(1≤i≤m, m≤k)个.覆盖表的一个重要性质是:表中任何一个N×t子矩阵都能覆盖相应t个参数所有可能t维取值组合至少一次.覆盖强度为t的覆盖表称t-way或t维覆盖表.这里的参数可为待测系统配置选项、输入以及消息事件等.在未作特殊说明情况下, 本文用N表示覆盖表大小, k表示待测系统参数个数, V表示所有参数取值集合, V_i(1≤i≤k)表示第i个参数取值集合, |V_i|表示第i个参数取值个数.

现举例说明覆盖表.表 1为一个手机通话功能的简单测试模型, 该测试模型共5个参数, 每个参数3个取值.如果对该系统进行穷尽测试, 则需要3⁵=243条测试用例.然而进行2-way即覆盖强度为2维的测试, 则仅需11条测试用例, 对应的2-way覆盖表见表 2, 该覆盖表可表示为CA(11;2, 3⁵).

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

1.2 禁忌搜索算法生成覆盖表流程

启发式搜索算法通常可采用两种方式进行覆盖表生成:逐条测试用例生成和整表演化.前一种方式每次生成一条测试用例, 然后添加到测试用例集中, 直到所有需要被覆盖的组合全部被覆盖为止; 后一种方式一次生成N条测试用例, 然后通过一定的演化规则使这N条测试用例覆盖所有需要被覆盖的组合.这两种方式各有优缺点, 前者较后者生成时间短, 而后者较前者生成的覆盖表规模小, 本文采用后者.算法1为本文TS生成大小为N×k的t-way覆盖表通用流程.

算法1. TS生成覆盖表通用流程.

在算法1中, 第4行~第14行描述了对矩阵元素不断修改迭代过程, 它是算法的主体.在该过程中:首先由邻域函数确定可进行的所有移动(第5行), 这里, 移动指矩阵中元素取值的修改; 接着, 对这些移动进行禁忌判断, 求出其中未被禁忌的移动(第6行); 最后, 选取最佳的移动对矩阵进行修改(第7行、第8行).这里, 最佳的移动是指通过该移动获得的新矩阵包含的未被覆盖的t元组数最少.另外, 禁忌表中的移动经过一定迭代次数后需要被解禁, 因此每轮迭代还需要更新禁忌表(第12行).更新时, 将新的移动添加到禁忌表的尾部, 并将超过禁忌期的移动移出禁忌表.理想情况下, 算法1返回的最优矩阵S^*为覆盖表, 但是当设定的覆盖表规模N过小时, S^*无法达到全覆盖, 此时为保证算法正常结束, 本文通过设定最大迭代次数I.

由算法1容易看出, 最大迭代次数、初始矩阵生成方法、邻域函数以及禁忌表等配置参数的选取影响着TS生成覆盖表的性能.本文接下来对这些配置参数进行调优, 以提高TS生成覆盖表性能.

2 配置参数调优

在本节中, 首先介绍TS生成覆盖表的各配置参数及其取值选取情况, 然后进行调优实验.

2.1 TS配置参数

1) 最大迭代次数

最大迭代次数用于控制算法终止.如果设置过小, 会造成算法过早收敛而使得生成的解无法接近最优解; 设置过大, 虽可增加优化信息, 防止过早收敛, 但会增加计算量.因此, 需要综合权衡, 力图找到一个平衡点.经多次实验, 我们发现最大迭代次数与覆盖强度、待测系统的参数及参数取值个数是相关的; 在本文所选实例中, 当最大迭代次数大于1 000 000后, 覆盖表规模趋于平稳.基于以上两点, 本文选取参与调优的最大迭代次数取值为:

● Min(N×k×v_max×10, 1000000);

● Min(N×k×v_max×20, 1000000);

● Min(N×k×v_max×30, 1000000),

其中, N为覆盖表规模, k为待测系统参数个数, v_max为前t个最大参数取值的乘积, Min为求最小值函数.例如, 对于覆盖表CA(69;3, 5¹3⁸2²), 如果最大迭代次数采用Min(N×k×v_max×10, 1000000), 则最大迭代次数=Min(69×11×5× 3×3×10, 1000000)=Min(341550, 1000000)=341550.

2) 初始化方法

TS是一种邻域搜索算法, 初始解确定了搜索的最初位置, 选取不恰当容易导致算法陷入局部最优.本文选取了随机方法、t-列子集法以及海明距离法^[24]等3种方法进行调优.

● 随机方法:随机方法是启发式搜索算法生成初始解最常用的一种方法, 在这种方法中, 矩阵的每个元素取值随机生成;

● t-列子集法:t-列子集法通过合并若干个已经达到全覆盖的子矩阵来得到初始矩阵.生成一个N×k的t-way初始矩阵的具体步骤为:首先, 将这k参数划分成⌈k/t⌉组, 除最后一组可能不足t个参数外, 其余每组参数个数均为t; 接着, 为每组参数生成一个N行全覆盖矩阵; 最后, 合并这些子矩阵便可得到初始矩阵.具体细节见文献[24];

● 海明距离法:海明距离法在生成初始时, 尽量使矩阵中不同行之间的元素取值不同.在N行初始矩阵生成中, 首先随机生成第1行, 然后逐行生成剩余的N-1行.这剩余的N-1行每行生成方法相同, 具体如下:第1步, 随机生成两个候选行; 第2步, 分别计算这两个候选行与初始矩阵中已生成的行之间的海明距离和; 最后, 选取海明距离和最大的候选行添加到初始矩阵中.这里, 两行之间的海明距离定义为两行对应取值不同的元素个数.具体细节见文献[24].

3) 禁忌表

TS算法的核心思想是:利用禁忌表封锁被禁止的移动来防止迂回搜索, 当创建一个新解时, 应避免使用禁忌表中的移动, 同时禁忌表中的移动经过一定迭代次数后需要被解禁.因此, 禁忌表包括了两方面内容:禁忌对象, 它规定了哪些移动被禁止; 禁忌长度, 它确定禁忌对象的受禁时间长度.

禁忌对象通常有两种.

● 禁忌对象1:若矩阵中的某一元素在最近L步(禁忌长度)被修改过, 则禁止该元素再次被修改;

● 禁忌对象2:若矩阵中某一元素的修改使当前矩阵还原回最近L步搜索过的任一矩阵, 则禁止该修改.

现举例说明这两种禁忌对象的区别.

设某待测系统有两个参数, 每个参数有2个取值, 不妨设为0和1.假设图 1(a)为该系统覆盖表的初始矩阵, 每行代表一条测试用例.现设第1次、第2次迭代分别对矩阵中的元素(1, 1)和(1, 2)进行了修改, 结果如图 1(b)和图 1(c)所示.现第3次迭代欲将图 1(c)中的元素(1, 1)的值1修改为0, 使结果如图 1(d), 那么该修改是否被允许?此时结果取决于禁忌对象.当禁忌长度L=2时, 如果选用禁忌对象1, 则该修改被禁止, 因为第1次迭代曾对元素(1, 1)进行过修改, 那么禁止在接下来两步内对该元素再作修改; 而采用禁忌对象2, 则该修改被允许, 因为这样修改后得到的矩阵与前两步搜索过的任何一个矩阵都不相同.

需要注意:在禁忌判断的算法设计上, 当禁忌对象为禁忌对象1, 可以直接将最近L步被修改过的元素位置信息存入禁忌表中, 此时只需要通过简单比较便可确定某一移动是否被禁止.然而, 当禁忌对象为禁忌对象2时, 该方法行不通.一种比较直接的解决方法是在禁忌表中存储最近L步被搜索过的矩阵, 然后通过矩阵间的比较去判断某移动是否被禁止.但是当L比较大时, 该方法在时间上和存储空间上都不可行.本文采用了文献[17, 25]提出的另一种方法——反向消除法.该方法在禁忌表中存放最近L步被修改过的元素信息, 这些信息包括被修改元素在矩阵中的行号、列号以及被修改之前的值; 然后, 通过该禁忌表便可推导出当前矩阵与搜索过的矩阵间的差别, 从而可判断出某一移动是否被禁止或允许.反向消除法的具体算法见文献[17, 25].

禁忌长度L的选取与禁忌对象是相关的.当选取禁忌对象1时, L不宜过大, NURMELA^[18]建议L≤10.因为禁忌对象1禁止对最近L步内所有被修改过的元素再次修改, 此时L设置过大会导致搜索空间过小, 进而影响搜索质量.基于此, 本文选取参与调优的禁忌对象1的禁忌长度分别为3, 6, 9.相比之下, 禁忌对象2的禁忌长度可设置大很多.因为在已经改动了若干个元素后, 即使再返回修改这些元素, 得到的矩阵也可能与之前这些矩阵都不相同.经大量实验, 文献[25]将禁忌对象2的禁忌长度确定为50 000.但考虑到:一方面, 本文生成的覆盖表的覆盖强度或测试模型中的参数个数较文献[25]中的小; 另一方面, 禁忌长度过大覆盖表生成会非常耗时.因此, 本文将文献[25]中的禁忌长度适当降低, 选取3 000, 6 000, 9 000参与调优.

综上所述, 本文选取参与配置调优的禁忌表取值为:

● (禁忌对象=禁忌对象1, 禁忌长度=3)

● (禁忌对象=禁忌对象1, 禁忌长度=6)

● (禁忌对象=禁忌对象1, 禁忌长度=9)

● (禁忌对象=禁忌对象2, 禁忌长度=3000)

● (禁忌对象=禁忌对象2, 禁忌长度=6000)

● (禁忌对象=禁忌对象2, 禁忌长度=9000)

4) 邻域函数

在覆盖表生成应用中, TS的邻域函数决定了迭代过程中选取矩阵中哪个元素进行修改以及如何修改, 因此邻域函数决定着搜索方向.邻域函数通常有如下4种.

● 邻域函数1:随机选取矩阵中某元素并随机修改其取值;

● 邻域函数2:首先, 随机选取矩阵中某列元素; 然后, 计算该列每个元素随机修改对应的移动代价; 最后, 选择移动代价最小的移动进行相应的修改;

● 邻域函数3:与邻域函数2类似, 只需把列变成行;

● 邻域函数4:首先, 随机选择一个未被覆盖t元组; 然后, 计算出达到覆盖该元组的所有移动; 最后, 选择移动代价最小的移动进行相应的修改.

以上邻域函数中的移动代价定义为修改后与修改前矩阵中未被覆盖的t元组数的差.下面以第4种邻域函数为例, 对邻域函数进行说明.

假设在覆盖表CA(4;2, 2³)的生成过程中, 初始矩阵S₀经过若干次迭代修改后, 获得的矩阵S为$\left[ {\begin{array}{*{20}{c}} {101}\\ {010}\\ {100}\\ {111} \end{array}} \right]$.显然,

该矩阵还存在2个未被覆盖二元组, 分别为(p₁=0, p₂=0)和(p₁=0, p₃=1), 其中, p_i为第i(1≤i≤3)个参数.假设选择的未被覆盖组合为(p₁=0, p₂=0), 则有3种修改都可达到覆盖这一组合, 分别为将S[1][1]修改为0、S[2][2]修改为0、S[3][1]修改为0.假设这3种移动都未被禁忌, 接下来需要分别计算它们的移动代价.将S[1][1]修改为0后, S的未被覆盖组合数为0, 因此该移动的移动代价=0-2=-2.同理, 可算出第2种、第3种移动的移动代价分别为1, 0.根据选取移动代价最小的原则, 则选取第1种移动, 即将S[1][1]修改为0.

注意到, 移动代价计算是覆盖表生成过程中非常重要的一项操作, 降低其复杂度可提高整个覆盖表生成算法的速度.根据定义, 移动代价的直接计算方法是分别计算出矩阵修改前后未被覆盖的t元组数, 然后求两者的差, 这种方法的时间复杂度为$O\left({2N \times \left({\begin{array}{*{20}{c}} k\\ t \end{array}} \right)} \right)$, 其中, N为覆盖表行数, k为参数个数, t为覆盖强度.实际上, 移动代价的计算并不需要完整地计算出矩阵修改前后未被覆盖的t元组数, 因为当矩阵中某元素被修改后, 那么仅与此被修改元素相关的组合被覆盖情况才有可能发生改变.为了提高移动代价的计算效率, 我们设计了一张表记为CT(count table), 该表用来存放所有需要被覆盖的t元组在当前矩阵中出现的次数, 根据该表, 移动代价的计算时间复杂度可降低为$O\left({2 \times \left({\begin{array}{*{20}{c}} {k - 1}\\ {t - 1} \end{array}} \right)} \right)$, 具体过程计算为:

设CT中包含被修改元素旧值的$\left({\begin{array}{*{20}{c}} {k - 1}\\ {t - 1} \end{array}} \right)$个t元组中有N₁个取值为1, 即目前这些组合只出现1次; 而包含被修改元素新值的$\left({\begin{array}{*{20}{c}} {k - 1}\\ {t - 1} \end{array}} \right)$个t元组中有N₂个取值为0, 即目前这些组合还没有被覆盖.那么该移动的移动代价=N₁-N₂.

这是因为如果某一旧值组合只出现1次, 当其中元素被修改了, 则该旧值组合将由被覆盖变成未被覆盖, 这样未被覆盖组合数增1;而如果某一新值组合未被覆盖, 经过修改该新值组合将变成被覆盖, 这样未被覆盖组合数减1.下面举例说明.

设当前矩阵S=$\left[ {\begin{array}{*{20}{c}} {101}\\ {010}\\ {100}\\ {111} \end{array}} \right]$, 则对应的CT=$\left[ {\begin{array}{*{20}{c}} {011}\\ {101}\\ {211}\\ {121} \end{array}} \right]$.其中, CT的第1列~第3列分别表示(p₁, p₂), (p₁, p₃)以及(p₂, p₃)的取值组合(0, 0), (0, 1), (1, 0), (1, 1)在S中出现的次数.例如, CT[3][1]=2表示(p₁=1, p₂=0)在S中出现了2次.现将S[1][1]由1修改为0, 这时, 与S[1][1]相关的修改前二元取值组合为(p₁=1, p₂=0), (p₁=1, p₃=1), 与该元素相关的修改后二元取值组合为(p₁=0, p₂=0), (p₁=0, p₃=1).由CT可以知, CT[3][1]=2, CT[4][2]=2, 其中, 取值为1的个数是0, 而CT[1][1]=0, CT[2][2]=0, 其中取值为0的个数为2, 因此, 移动代价=0-2=-2, 这与前面直接计算矩阵修改前后未被覆盖组合数的差是相同的.

综上所述, TS生成覆盖表的配置参数取值情况统计结果见表 3.

为了记录方便, 我们对表 3中的配置参数取值进行编号, 对应表 3的第1列(取值编号).假定某个配置参数有n个取值, 我们分别用{0, 1, ..., n-1}来表示各取值.例如, 配置{Min(N×k×v_max×20, 1000000), 随机方法, (禁忌对象2, 禁忌长度=3000), 邻域函数3}可表示为{1, 0, 3, 2}.

2.2 实验设计

接下来进行配置参数调优.根据表 3, TS配置的条数共3×3×6×4=216条.如果在每一条配置下都进行覆盖表的生成, 然后选优, 那么在时间上是不可行的.为了更高效地解决该问题, 本文将调优实验分为两个阶段进行, 分别为pair-wise实验和爬山实验, 以确保在最大程度上击中最优配置的前提下能够减少所需的配置个数.

1) 第1阶段:pair-wise实验

组合测试既是一种测试方法也是一种实验设计方法.调优实验首先利用组合测试中的2-way覆盖即pair- wise实验来检查两两配置参数之间的交互作用.pair-wise实验参数配置集见表 4, 该配置集由组合测试工具ACTS(http://csrc.nist.gov/groups/SNS/acts/index.html)生成.

2) 第2阶段:爬山实验

爬山实验首先以pair-wise得到的最优配置记为C_x0为基准配置, 然后从第1个参数最大迭代次数开始, 改变其在C_x0中的取值并保持其他参数取值不变, 直到该参数所有取值都被覆盖; 接下来, 在该组配置中选取生成效果最好配置记为C_x1, 以C_x1作为新的基准配置, 在其基础上改变第2个参数初始化函数取值.同样, 从这些配置中挑出生成效果最好的配置记为C_x2, 作为新的基准配置.如此反复, 直到改变第4个参数邻域函数取值, 从中获取生成效果最好的配置记为C_x4, 该配置即为最终的最优配置.爬山法的参数配置集是由具体实验一步步动态产生, 具体细节可见第2.3节.

第1个阶段不仅考虑了算法各配置参数之间的二维组合关系对算法的影响, 而且还大大降低了配置的条数, 相对全配置的216条, 这一阶段仅需24条配置; 同时, 第2个阶段为了弥补第1个阶段的不足, 对每个配置参数还进行独立深入探索, 以进一步挖掘各配置参数自身对算法的影响, 这一阶段增加了12(2+2+5+3)条配置.这样, 两阶段共36条配置, 仅为全配置条数的16.7%.

2.3 实验结果

本实验选取20个实例, 覆盖强度2~6维, 详见表 5, 其中, 前15个来自禁忌搜索参数调优文献^[11], 后5个来自由Charlie Colbourm维护的覆盖表专门网站(http://www.public.asu.edu/~ccolbou/src/tabby/catable.html).

参数配置的性能评判标准是为了获得显著性统计结果, 我们对每个实例在各参数配置下执行30次覆盖表生成, 记录这30次中覆盖表成功生成的次数以及平均生成时间, 生成时间以秒为单位, 不足1s的记为0;然后将同一配置下所有实例的成功生成次数和平均生成时间分别求和, 成功生成次数和最大者为最优配置.如果成功生成次数和相同, 则平均生成时间和最少的为最优配置.

本文实验均运行在远程服务器上, 该服务器的硬件环境为:1个2.0GHZ Intel(R) Xeon(R) E5-2640 v2处理器、16GB内存; 软件环境为:Centos 6.5, Java 1.8.

1) pair-wise实验结果

表 6和表 7分别给出了不同参数配置下各实例覆盖表成功生成次数及生成时间, 在这两表以及后续表中用加粗标示最优配置.

从pair-wise实验结果可以看出:TS在不同配置下, 其覆盖表生成的性能差别很大.例如在配置C₁下, TS成功生成覆盖表的总次数为0, 而在C₂₄配置下却高达572.根据性能评判标准, C₂₄=(2, 2, 5, 3)为这一阶段的最优配置, 下面我们将这一配置作为基准配置进行爬山实验.

2) 爬山实验

爬山实验以C₂₄=(2, 2, 5, 3)为基准配置, 依次改变各参数取值, 逐步对配置参数进行优化, 以获得最终最优配置.下面按照最大迭代次数、初始化方法、禁忌表、邻域函数等顺序进行各配置参数的优化.

● 最大迭代次数

将配置C₂₄=(2, 2, 5, 3)中的最大迭代次数编号2分别修改为0, 1, 可获得2个新配置C₂₅=(0, 2, 5, 3), C₂₆=(1, 2, 5, 3), 这3个配置的覆盖表成功生成次数及生成时间分别见表 8和表 9.

通过表 8可以看出:当最大迭代次数由Min(N×k×v_max×10, 1000000)增加到Min(N×k×v_max×20, 1000000)时, C₂₆的覆盖表成功次数由C₂₅的538增加到566, 增加幅度明显.但是当最大迭代次数由Min(N×k×v_max×20, 1000000)增加到Min(N×k×v_max×30, 1000000)时, C₂₄相对于C₂₆只增加了6次, 覆盖表成功生成的次数趋于平稳.

在生成时间方面, 表 9中的数据显示:最大迭代次数与生成时间没有必然关系, 可能会出现最大迭代次数大反而生成时间短.例如, C₂₄的生成总时间比C₂₆小.分析其中原因不难发现, 根据TS生成覆盖表的算法1可知:当未被覆盖组合数达到0时, 即使迭代次数还没到达最大迭代次数, 算法也会结束.因此, 即使最大迭代次数设置的很大, 实际生成时间也可能很小.但这不表示最大迭代次数越大越好, 因为一方面, 当最大迭代次数到达一定次数后, 增加最大迭代次数不会明显降低覆盖表规模; 另一方面, 当覆盖表不能成功生成时, 此时只有迭代次数到达最大迭代次数, 算法才能结束, 在这种情况下, 最大迭代次数越大生成时间定会越长.

在最大迭代次数调优实验结果中, C₂₄的覆盖表成功生成次数最大, 根据性能评判标准, 它为C₂₄~C₂₆三者中的最优配置, 将它作为下一初始化方法调优实验中的基准配置.

● 初始化方法

将配置C₂₄=(2, 2, 5, 3)中的初始化方法编号2分别修改为0, 1, 又可得到2个新配置C₂₇=(2, 0, 5, 3), C₂₈=(2, 1, 5, 3), 这3个配置的覆盖表成功生成次数及生成时间分别见表 10和表 11.

表 10显示:在覆盖表成功生成次数上, 3种初始化方法相差很小, 其中, 次数最大的配置C₂₇与最小的配置C₂₈只差6次.

表 11显示:在生成时间上, 3种初始化方法相差也不大, 平均来看, 速度最快配置C₂₄的速度仅为最慢配置C₂₈的1.36(7823/5769)倍.

综上所述, 3种初始化方法在覆盖表生成上不存在明显差别, 可能还存在其他更好的初始化方法能获得更优的结果, 这为探索新的初始化方法提供了空间.

根据性能评判标准, 在初始化方法调优实验中, C₂₇为其中最有配置.

● 禁忌表

将配置C₂₇=(2, 0, 5, 3)中的禁忌表取值编号5分别修改为0~4, 这样可得5个新配置C₂₉=(2, 0, 0, 3), C₃₀=(2, 0, 1, 3), C₃₁=(2, 0, 2, 3), C₃₂=(2, 0, 3, 3), C₃₃=(2, 0, 4, 3), 这些配置的覆盖表成功生成次数及生成时间分别见表 12和表 13.

表 12和表 13中的数据表明, 禁忌表对TS生成覆盖表的性能具有较大的影响:首先, 采用禁忌对象1的配置(C₂₉~C₃₁)较采用禁忌对象2的配置(C₂₇, C₃₂, C₃₃)覆盖表生成速度快, 但其覆盖表成功生成次数少; 其次, 采用禁忌对象1的配置之间, 覆盖表成功生成次数相差较大.例如, 禁忌长度为9的配置C₃₁, 相比禁忌长度为3的配置C₂₉, 覆盖表成功生成次数少了318次.

这一实验结果与第2.1节中对禁忌表的理论分析基本吻合, 采用禁忌对象1能快速判断某一移动是否被禁忌, 但其禁忌范围比较大, 禁忌长度不能太大, 否则搜索空间很小, 导致搜索质量下降.

根据性能评判标准, 在禁忌表调优实验中, C₂₇仍然为最优配置.

● 邻域函数

将C₂₇=(2, 0, 5, 3)中的邻域函数取值编号3分别修改为0~2, 这样可获得3个新配置C₃₄=(2, 0, 5, 0), C₃₅=(2, 0, 5, 1), C₃₆=(2, 0, 5, 2), 这些配置的覆盖表成功生成次数及生成时间分别见表 14和表 15.

表 14中的数据显示:在覆盖表成功生成次数上, 配置C₃₄~C₃₆覆盖表成功生成的次数全部为0, 而采用邻域函数4的配置C₂₇却高达573.这是因为TS是一种邻域搜索, 加强集中搜索有利于提高其搜索能力.C₂₇在每轮迭代中覆盖一个未被覆盖组合, 搜索比较集中; 而C₃₄~C₃₆这3个配置在矩阵中随机选择一个元素进行修改, 搜索很分散.

表 15中的数据显示:在生成时间上, 各配置之间也存在很大差别.例如, C₃₄的总生成时间为954s, 而C₃₅高达329 119s.分析其中原因不难发现:在配置C₃₄下, 每轮迭代中禁忌判断和移动代价计算次数仅1次, 而C₃₅高达N(覆盖表行数)次.

根据性能评判标准, C₂₇=(2, 0, 5, 3)为最终的最优配置.

2.4 统计分析

通过参数调优实验, 我们获得了TS生成覆盖表的最优配置.由于算法含有随机策略, 因此, 接下来我们对各配置进行统计分析, 以此来检验该最优配置与其他配置在覆盖表成功生成次数上是否存在显著差异.

检验时, 将配置C₁~C₃₆的取值设置为调优实验中各实例成功生成覆盖表的次数, 检验过程具体分成两步:第1步, 利用Friendman检验法检查所有参数配置是否存在显著性差异; 若存在显著差异, 第2步, 利用Wilcoxon符号秩检验法逐对检测最优配置同其他各配置是否存在显著差异.

1) Friedman检验

在Friedman检验中, 显著性水平α=0.05, 两个假设分别为:

● 原假设H0:所有配置之间不存在显著差异;

● 备择假设H1:至少有一个配置与另一个配置存在显著差异.

Friedman检验的统计结果见表 16.

由于渐进显著性=0.000 < 0.05, 因此拒绝原假设, 认为至少有一个配置与另一个配置存在显著差异.下面我们利用Wilcoxon符号秩检验法检查最优配置同其他各配置是否具有显著差异.

2) Wilcoxon符号秩检验

在Wilcoxon符号秩检验中, 我们将最优配置与其余35个配置进行逐对比较, 每一对比较的两个假设为:

● 原假设H0:最优配置与另一配置之间不存在显著差异;

● 备择假设H1:最优配置与另一配置之间存在显著差异.

为了控制Ⅰ类错误概率, 我们采用Bonferroni校正法对显著性水平α=0.05进行校正, 校正后的显著性水平α_Bnf=α/35=0.0014.

将Wilcoxon符号秩检验结果按渐进显著性Asymp Sig升序排序, 结果见表 17.当Asymp Sig < 0.0014时, 拒绝原假设; 反之, 接受原假设.其中, 接受原假设的配置用加粗标示.

通过表 17可以看出:35个配置中, 有23个与最优配置C₂₇存在显著差异.进一步观察还可以发现:与最优配置不存在显著差异的12个配置中, 有8个禁忌对象采用禁忌对象2, 而邻域函数全部采用邻域函数4.这一结果表明了邻域函数4和禁忌对象2在统计意义上要优于其他邻域函数和禁忌对象.

3 约束、变力度和并行化处理 3.1 约束处理

如前文所述, 在实际应用中, 参数间的约束普遍存在, 如果在生成覆盖表时不考虑这些约束, 可能会出现很多无效测试用例, 从而降低测试的有效性, 因此, 覆盖表生成中的约束处理显得非常必要.本文采用基于禁止元组方法进行约束处理, 该方法在约束量不大的条件下(这也是实际应用常见的情况)具备一定优势.禁止元组指的是在有效测试用例中不允许出现的参数取值组合, 例如, 表 1描述的测试模型中(对方场景模式=飞行, 对方状态=正在打电话)就是一个禁止元组.禁止元组按照呈现方式可以分成两类:一类是由系统明确规定的, 称显式禁止元组; 另一类是由显式禁止元组推导出来的, 称隐含禁止元组.

假设某待测系统有3个参数记为A, B, C, 每个参数有2个取值记为0, 1.若(A=0, C=0)和(B=0, C=1)为显式禁止元组, 则(A=0, B=0)为隐含禁止元组.因为包含(A=0, B=0)元组的所有测试用例(A=0, B=0, C=0)和(A=0, B=0, C=1)都必然包含(A=0, C=0)或(B=0, C=1), 从而导致这两条测试用例都是无效的.由于包含(A=0, B=0)所有测试用例都是无效的, 因此认为(A=0, B=0)为禁止元组.限于篇幅, 隐含禁止元组具体求解方法不在此处讨论, 请见文献[20].

当待测系统含有约束时, 为保证所生成覆盖表中的每一条测试用例都有效, 本文从以下3个方面进行处理.

● 首先, 剔除覆盖需求中包含任何禁止元组的取值组合.因为有效测试用例不可能包含这些组合, 若不剔除, 将无法达到全覆盖, 即无法生成覆盖表;

● 其次, 初始矩阵逐行生成时, 对每行进行约束检查, 确保生成的初始矩阵不含任何禁止元组.每行生成时, 逐个参数进行赋值, 约束检查方法为:当为第j(1≤j≤k, k为待测系统参数个数)个参数p_j指定取值v_j(v_j∈V_j, V_j为p_j的取值集合)时, 如果v_j与前面已确定的j-1个参数取值构成的元组(v₁, v₂, …, v_j-1, v_j)不包含任何禁止元组, 则v_j满足约束, 这样可继续为下一参数指定取值, 直到所有参数都确定了取值, 该行生成完毕; 否则, 更换p_j取值为${{v'}_j}({{v'}_j} \ne {v_j}, {{v'}_j} \in {V_j})$, 使得$({v_1}, {v_2}, ..., {v_{j - 1}}, {{v'}_j})$不包含任何禁止元组.这里, 检查v_j是否满足约束的方法是:当(v₁, v₂, …, v_j-1, v_j)不包含任何禁止元组, 便可判定v_j满足约束, 也就是最终一定可以生成一条不包含任何禁止元组的测试用例.这是因为如果不能找到任何一条有效测试用例包含(v₁, v₂, …, v_j-1, v_j), 则(v₁, v₂, …, v_j-1, v_j)一定至少包含一个显示或隐含禁止元组, 这与(v₁, v₂, …, v_j-1, v_j)不包含任何禁止元组相矛盾.这里, 在检查参数p_j某取值是否满足约束时, 不需要考虑后面参数取值情况, 这在一定程度上简化了约束处理;

● 最后, 在迭代过程中进行矩阵中某一元素的修改时, 确保修改后被修改元素所在的行不包含任何禁止元组.

当禁止元组个数较多时, 为了加快约束处理速度, 我们还将禁止元组按照参数取值进行分组, 每组由包含该参数取值的禁止元组构成.假设某待测系统有3个参数分别为A, B, C, 每个参数有2个取值为0, 1, 则禁止元组被分为6组, 分别为(A=0), (A=1), (B=0), (B=1), (C=0)和(C=1), 其中, (A=0)这组由包含(A=0)的禁止元组构成, 其他组类似.禁止元组分组后, 可加快判断某一元组或测试用例是否满足约束.例如, 当矩阵中第i(1≤i≤N)行某元素p_j(1≤j≤k)取值由v_j(1≤j≤k)修改为${{v'}_j}({{v'}_j} \ne {v_j}, {{v'}_j} \in {V_j})$时, 判断$({v_1}, {v_2}, ..., {v_{j - 1}}, {{v'}_j}, ..., {v_k})$是否满足约束, 只需要判断$({v_1}, {v_2}, ..., {v_{j - 1}}, {{v'}_j}, ..., {v_k})$是否包含(${p_j} = {{v'}_j}$)这组任一禁止元组即可.这是因为修改之前的元组(v₁, v₂, …, v_j, …, v_k)不包含任何禁止元组, 此时如果$({v_1}, {v_2}, ..., {v_{j - 1}}, {{v'}_j}, ..., {v_k})$含有禁止元组, 则该禁止元组一定与(${p_j} = {{v'}_j}$)有关.

另外需要注意:在初始矩阵生成中, 当待测系统含有约束时, 参数赋值顺序会影响最终生成的覆盖表规模.为此, 本文在初始矩阵生成时, 将参数赋值顺序按照参数参与约束个数进行降序排序, 这样可以增大那些参与较多约束的参数取值在初始矩阵中出现的概率, 从而有效降低覆盖表规模.如果某参数有多个取值参与约束, 则按参与约束个数最多的取值进行排序.

3.2 变力度处理

在实际应用中, 参数间不仅仅存约束, 而且它们之间的交互力度往往不相同, 一些参数间关系比较紧密, 一些则相对松散, 甚至一些无任何交互.对于这样的系统, 往往很难寻找一个合适的覆盖力度进行固定力度的组合测试:(1)如果覆盖力度选取过大, 则测试用例可能出现不必要的冗余, 从而增加测试成本; (2)如果覆盖力度选取过小, 则某些参数间的交互作用将难以在测试中得到完全的检测, 从而降低错误检测能力.为此, Cohen等人^[13]提出了变力度覆盖表.变力度覆盖表可以有针对性地为不同的参数提供不同的覆盖力度, 是一种非常实用的覆盖表.例如, 变力度覆盖表VCA(N; 2, 3⁵, {CA(3, 3³)})表示不仅对5个参数中任意2个参数进行2维覆盖, 还对其中3个参数进行了3维覆盖.

由于在变力度覆盖表中参数间有多个交互力度, 因此在变力度覆盖表生成中, 我们设计了多张表分别存放不同交互力度参数取值组合被覆盖次数.例如, 对于变力度覆盖表VCA(N; 2, 3⁵, {CA(3, 3³)}), 我们设计了两张表, 分别用来存放交互力度为2维和3维的参数取值组合被覆盖次数.基于这些表, 变力度覆盖表生成处理如下.

● 当所有存放参数取值组合的表都不存在取值为0的元素时, 也就是所有交互力度参数取值组合都被覆盖, 覆盖表才成功生成;

● 当需要选取未被覆盖参数取值组合进行覆盖时, 若多个交互力度参数取值组合都存在未被覆盖, 建议优先从高交互力度表中选取.因为高交互力度的组合比低交互力度组合更难被覆盖, 尽早覆盖这些组合有利于生成较小的覆盖表;

● 在计算某元素被修改的移动代价时, 需要考虑所有表中与该元素相关的参数组合的取值.一旦该元素被修改, 所有这些参数组合的取值都应该被更新.

3.3 并行化处理

为了改善TS算法的速度, 提高其应用潜力, 本文还对TS进行了并行化.

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

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

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

根据ForkJoin工作流程, 并行化需要进行任务拆分, 这一步由编程者完成.一个任务能被拆分成多个子任务的条件是:这些子任务之间相互独立, 能并行进行.容易看出:在TS生成覆盖表的算法1中, 每次循环迭代都需要从邻域的所有移动中选出不被禁忌的移动(第6行), 这一操作涉及到对邻域中每个移动进行禁忌判断, 而邻域中的移动个数通常多达几十个甚至上百个, 且随着覆盖表规模增大而增大, 因此我们可以将这一操作进行拆分, 利用不同子任务实现对不同移动的禁忌判断.同理, 最佳移动的求解(第7行)、最优矩阵的更新(第10行), 它们也都可以拆成多个可并行执行的子任务.

任务拆分后, 可利用ForkJoin提供的框架实现并行化.下面以移动的禁忌判断并行化为例, 对ForkJoin框架下的并行化编程进行说明.

● 首先, 将所有需要进行禁忌判断的移动存入一数组M中, 并且提供一个用于存放每个移动是否被禁忌的数组R;

● 然后, 创建一个ForkJoin任务, 如:

$ TabuJudgeTask\;task = newTabuJudgeTask(M,R,1,M.len); $

其中, TabuJudgeTask是一个用户自定义类.为了实现ForkJoin任务, TabuJudgeTask需要继承Java提供的RecursiveAction或者RecursiveTask类, 这两个类的区别是前者用于任务没有返回结果的场景, 后者用于任务有返回结果的场景.TabuJudgeTask具体实现参见算法2.其中, 参数M.len为M中的元素个数也就是邻域中的移动个数;

● 最后, 通过ForkJoinPool来执行任务, 如:

$ new\;ForkJoinPool().invoke(task). $

TabuJudgeTask类伪代码见算法2, 其中, 重写的computer方法(第13行~第27行)通过递归来完成任务的拆分和计算, 是TabuJudgeTask区别于其他普通类的关键之处.在compute方法中, 首先判断当前任务中需要进行禁忌判断的移动个数是否大于设定的阈值(第14行).若条件不成立, 则对规定区间中的每个移动进行禁忌判断, 并将相应判断结果保存到R中(第21行~第24行); 否则, 把当前任务一分为二(第15行~第17行), 然后启动这两个子任务的执行(第18行).由于这两个子任务又属于TabuJudgeTask类, 因此在它们的执行过程中又会进入该compute方法, 体现了递归.

算法2. 禁忌判断并行化.

有关ForkJoin框架并行化编程更多细节请参考Java相关帮助文档(http://docs.oracle.com/javase/8/docs/api/index.html).

4 实验

为了检验本文所提方法生成覆盖表的效果, 我们基于第2节、第3节的设计实现了算法PTS_CVS(parallel tabu search with constraint and variable strength handling), 并通过实验来检验PTS_CVS生成覆盖表的性能.另外, 为了确定PTS_CVS对某待测系统所能生成的最小覆盖表, 我们在PTS_CVS外面加一层二分搜索, 见算法3.外层二分搜索以覆盖表规模上下界作为输入, 最后返回这一区间规模最小的覆盖表; 而内层PTS_CVS用来完成某一规定规模的覆盖表搜索工作.

算法3. 二分搜索.

在算法3中, 需要注意的是:对于每一覆盖表规模N, 无论PTS_CVS是否成功生成该规模的覆盖表, PTS_ CVS都将最终搜索到的最优矩阵(即未被覆盖t元组数最小)返回(第4行), 因此, 需要确认返回的A'是否达到全覆盖(第5行).

算法3需要输入覆盖表规模下界low和上界upper, 本文将low设置为覆盖表规模理论最小值, 即前t个最大参数取值的乘积; upper设置为对比方法所提供的覆盖规模最大值.如果在这一区间无法生成覆盖表, 则将upper增加10, 然后重新执行算法3, 直到成功生成覆盖表为止.

根据前文, PTS_CVS不仅能生成固定力度覆盖表, 同时还能生成变力度覆盖表、带约束覆盖表, 此外, PTS_ CVS还进行了算法并行化, 因此, 实验部分主要解决以下4个问题.

● 问题1:在固定力度不带约束覆盖表方面, PTS_CVS与目前公开的最优覆盖表生成算法或工具相比, 性能如何?

● 问题2:在变力度不带约束方面, PTS_CVS有怎样的表现?

● 问题3:在固定力度带约束等方面, PTS_CVS又有怎样的表现?

● 问题4:PTS_CVS与其并行化前算法相比, 速度有多大的提高?

前3个问题是PTS_CVS与已有方法的性能比较, 比较从覆盖表规模和覆盖表生成时间两方面进行, 我们将相关实验放在接下来的第4.1节.后一个问题是PTS_CVS与其并行化前算法, 这里称为STS_CVS(sequential tabu search with constraint and variable strength handling)比较.由于并行化只影响覆盖表生成速度, 因此此时只需比较两者生成覆盖表的时间, 我们将相关实验放在第4.2节.

4.1 PTS_CVS与已有方法的比较与分析

在这组实验中, 我们将PTS_CVS与MiTs^[11], HHSA^[19], Calot^[26], CASA^[27], SA^[13], SA^[28], IPGAS ^[29], ACTS等目前公开的覆盖表生成算法或工具做比较, 下面首先对这些方法进行简要介绍.

MiTs是目前公开的最优TS覆盖表生成方法, 用于生成固定力度不带约束的覆盖表.ACTS是一款免费覆盖表生成工具, 由NIST(National Institute of Standards and Technology Information Technology Laboratory)提供, 利用贪心策略IPOG进行覆盖表生成, 该工具既能进行约束处理也能进行变力度处理.SA^[13], SA^[28], CASA, HHSA使用模拟退火算法进行覆盖表生成, 其中, SA^[28]只能进行固定力度覆盖表生成, 而SA^[13]能进行变力度处理, CASA和HHSA能进行约束处理.IPGAS是一种基于Spark的并行化遗传算法, 该方法能加快遗传算法生成覆盖表的速度, 但不能进行约束和变力度处理.Calot方法将覆盖表生成看作约束问题, 然后利用SAT约束求解器进行求解, 因此能生成规模较小的覆盖表.

实验共选取了97个实例.固定力度不带约束实例44个, 见表 18, 其中, 表 18(a)中29个实例来自文献[11], 覆盖强度2~6维; 表 18(b)中15个实例来自文献[29], 覆盖强度2~3维.变力度不带约束实例18个, 见表 19, 其中, 前11个实例由Cohen^[13]提供, 后7个由Bestoun^[15]提供.表中VCA(2, 3¹⁵, {C})表示在对所有15个3值参数进行2维覆盖基础上, 还对部分参数进行了更高力度的覆盖, 更高力度的覆盖具体情况由{C}确定.例如, 在实例VS-10中, {C}为CA(3, 3⁴), CA(3, 3⁵), CA(3, 3⁶), 表示对3组参数进行了3维覆盖, 这3组参数的个数分别是4~6.固定力度带约束实例35个, 见表 20, 其中, 前5个为真实应用, 后30个由Cohen等人^[22]合成, 这35个实例已被广泛应用于带约束覆盖表生成研究中.

实验设置方面, 文中PTS_CVS是一种不确定算法, 具有一定随机性, 为了获得更准确结果, 我们对表 18~表 20中的每个实例都重复执行20次算法3, 实验结果中给出所生成的覆盖表规模的最小值、平均值、标准差以及平均生成时间, 生成时间以秒为单位, 不足1s的记为0.

ACTS的数据由运行该工具生成, ACTS是一种确定算法, 所有只需运行1次.其他方法没对外提供对应工具, 实验结果中的数据均为相关文献公开的数据.

实验结果中还给出了PTS_CVS的规模最小值与所有对比方法所提供的覆盖规模最小值之差, 用Δ表示.下面我们将按照固定力度不带约束、变力度不带约束和固定力度带约束的顺序给出实验结果, 并对实验结果进行分析.

实验软硬件环境与第2节参数配置调优中的相同.

(1) 固定力度不带约束实验(问题1)

固定力度不带约束实例覆盖表生成结果见表 21(a)和表 21(b), 其中, 表 21(a)为PTS_CVS和MiTs对比情况, 表 21(b)为PTS_CVS与ACTS, SA^[28], CASA, HHSA, IPGAS对比情况.

表 21(a)中的数据表明:(1)在覆盖表规模上, PTS_CVS稍优于MiTs, 除了S1-10, S1-16和S1-17这3个实例外, PTS_CVS生成的覆盖表规模都不大于MiTs, 总体上, PTS_CVS比MiTs少6条; (2)在覆盖表生成时间上, PTS_ CVS明显快于MiTs, 平均来看, PTS_CVS的速度为MiTs的162.6(13284657/81686)倍.

PTS_CVS和MiTs都采用了禁忌搜索策略, 两者的主要差别在于禁忌表和邻域函数的取值不同.为了增强搜索的多样性, MiTs将邻域函数1~4通过一定的权值系数进行复合, 但这将会降低搜索速度.而采用单一邻域函数4的PTS_CVS为了增加搜索到最优解的可能, 则选用了禁忌范围很小的禁忌对象2.这样, PTS_CVS能在更短的时间内生成与MiTs规模接近的覆盖表.

表 21(b)中数据显示:在与ACTS, SA^[28], CASA, HHSA, IPGAS等多种方法对比中, 首先, 在覆盖表规模方面, PTS_ CVS占有明显优势, 除了S2-14实例外, PTS_CVS生成的覆盖表规模都为所有方法中的最小值; 在生成时间方面, 从已有的数据来看, PTS_CVS虽然慢于ACTS(ACTS采用贪心策略), 但明显快于HHSA和IPGAS.

(2) 变力度不带约束实验(问题2)

变力度不带约束实例覆盖表生成结果见表 22, NA表示相关文献没有提供对应的数据.

从表 22可以观察出:虽然PTS_CVS的生成速度比ACTS慢, 但PTS_CVS生成的覆盖表规模却远小于ACTS, 两者之差最大可达到166.即使与采用模拟退火算法的SA^[13]相比, 11个实例中仍有5个(VS-1, VS-7, VS-8, VS-10, VS-11), PTS_CVS生成的覆盖表小于SA^[13].

(3) 固定力度带约束实验(问题3)

固定力度带约束实例2维覆盖表生成结果见表 23.

表 23的数据表明:(1)在覆盖表规模方面, PTS_CVS明显小于CASA, 略小于HHSA和Calot, 四者的所有实例覆盖表规模总和分别为1 077, 1 206, 1 084, 1 087;(2)在覆盖表生成速度间方面, PTS_CVS明显快于HHSA和Calot, 平均来看, PTS_CVS速度是HHSA的15.3倍、Calot的2.5倍.在PTS_CVS和CASA两者比较中, 如果不考虑覆盖表规模仅从生成总时间看, PTS_CVS要慢于CASA, 两者生成总时间分别为7581s和6214s.然而从表 23可以看出:当PTS_CVS和CASA在生成同等规模大小的覆盖表时, PTS_CVS需要的时间更少.例如, 对于Apache, CASA生成30行覆盖表需要115s, 而PTS_CVS却不足1s.

4.2 PTS_CVS与STS_CVS的比较与分析

为了检验本文并行化方法对覆盖表生成速度的影响, 我们进行了PTS_CVS和其并行化前的算法STS_CVS的比较.我们分别用STS_CVS和PTS_CVS对表 18~表 20中的每个实例生成一个指定大小的覆盖表, 指定的大小为表 21~表 23中PTS_CVS栏对应的大小(最小值).例如, 对表 18中的实例S1-7, 将生成一个大小为161的覆盖表.我们注意到:STS_CVS和PTS_CVS在生成覆盖表时, 生成时间具有很大的随机性.因此, 在实验次数较少的情况下, 生成时间不宜作为速度的评判标准.但生成时间与迭代次数比值却基本相同, 该比值能较准确反映算法速度本身, 因此, 我们用该比值(记为单次迭代时间)来进行衡量STS_CVS和PTS_CVS的速度.每个实验重复5次, 最后给出5次单次迭代时间的平均值.

图 3~图 5分别为表 18~表 20对应实例的并行化实验结果, 图中横坐标为STS_CVS生成覆盖表的单次迭代时间(单位为ms); 纵坐标为STS_CVS和对应的PTS_CVS单次迭代时间比值记为加速比, 用来表示并行化加速情况.

(1) 固定力度不带约束串并对比实验(问题4)

图 3为固定力度不带约束待测实例的实验结果.可见:当STS_CVS单次迭代时间较小时(约1ms), 加速比 < 1, 表明此时STS_CVS快于PTS_CVS; 但随着STS_CVS单次迭代时间的增加, 加速比也随之增加, 最终达4.0左右.

分析其中原因不难发现, 并行执行的子任务数是影响并行化加速比的重要因素.当STS_CVS的单次迭代时间少, 表明待测系统的参数、参数取值个数以及覆盖强度都比较小, 此时可并行执行的子任务数也较少; 同时, 并行化还在线程创建、切换、销毁等方面存在时间开销, 因此开始时出现并行比串行慢, 加速比 < 1;但随着待测系统中的参数、参数取值个数以及覆盖强度的增大, 随之可并行计算的子任务数也增多, 加速比值相应地得到了增加.

(2) 变力度不带约束串并对比实验(问题4)

图 4为变力度不带约束实例的并行化实验结果.与固定力度不带约束待测实例类似, 虽然加速比存在一些波动, 但整体上仍呈现出随STS_CVS单次迭代时间增加而增加的趋势.由于该模型中的实例总体比较简单(图 4中的横坐标时间短反映了这点), 因此并行执行的子任务数较少, 这样, 该模型的加速比相对固定力度不带约束模型将有所下降.

(3) 固定力度带约束串并对比实验(问题4)

图 5为固定力度带约束实例的并行化实验结果.由于带约束覆盖表的生成相对于无约束覆盖表需要进行额外约束处理, 目前我们还没对这一部分进行并行化处理.因此, 该模型的平均加速比相对前两个模型有所下降; 同时, 在该模型中, 不同实例的约束情况不完全相同, 这导致了该模型的加速比波动性较前两个模型大.

各类测试实例并行化实验结果归纳见表 24, 中间两列分别为各类测试实例的STS_CVS, PTS_CVS的单次迭代时间和.表 24的数据显示:固定力度不带约束测试实例并行化效果最好, 加速比平均达到3.19;变力度测试实例较简单, 并行计算不能充分发挥其作用, 但仍有1.47倍加速.带约束测试实例由于约束的影响, 并行化加速有所降低为1.45.所有测试实例并行化平均加速2.68倍.

4.3 实验结论

为了评估文中PTS_CVS的有效性, 我们实施了大量实验, 将PTS_CVS与目前公开的最优覆盖表生成算法或工具进行对比, 这些对比的方法中有采用IPO贪心策略的, 有采用TS, GA, SA等启发式搜索策略的, 还有使用SAT约束解决器的.在实例模型方面, 我们选取了固定力度、变力度和带约束这3种.实验结果表明:无论是在哪一种实例模型中, 相对于其他方法, PTS_CVS都能在覆盖表规模方面总体上最小; 而在生成时间方面, 虽然PTS_CVS较贪心算法长, 但是较其他对比方法都短.因此, PTS_CVS是目前一种较优的覆盖表生成方法.

另外, 我们还进行了PTS_CVS并、串行速度比较实验.实验结果表明:虽然对不同实例模型, 并行化加速程度不同, 但是并行化加速比整体上还是呈现出随串行执行的单次迭代时间增加而增加的趋势, 因此在一定程度上, 本文并行化方法仍不失为一种有效的提高TS生成覆盖表速度的方法.由于文中采用的ForkJoin是一种本地并行化框架, 其受单机硬件资源性能影响较大, 因此, 并行化加速还不太理想.分布式或云平台下的覆盖表生成并行化研究将是我们今后工作内容的一部分.

5 影响实验结果有效性因素分析

实证性和实验性研究通常都存在影响实验结果有效性的因素, 本文也不例外, 下面我们从3个方面对影响本文实验结果有效性的因素进行分析.首先, 为了确定PTS_CVS所能生成的最小覆盖表, 本文在其外面增加一层较为简单的二分搜索, 更为有效的方法可以获得更好的结果; 其次, 本文虽然选取了一批具有代表性的实例作为实验对象, 但对于其他的实例实验结果可能会有所变化, 我们仍需要在更多的测试实例上验证本文方法的有效性; 最后, 由于实验耗时较长, 文中第4节中的实验次数没有达到统计学上要求的30次以上, 虽然报告了平均值和方差这两个统计量, 但更多的重复次数能带来更准确的实验结果.

6 相关工作

组合测试发展至今已有30多年, 相关的研究论文600多篇, 其中200多篇是有关覆盖表生成.可见, 覆盖表生成是组合测试中非常重要的一个组成部分.这里, 我们仅讨论与TS算法、约束覆盖表生成、变力度覆盖表生成以及并行计算相关的一些主要研究.

Nurmela^[18]在2004年首次使用TS算法生成覆盖表, 该方法更新了一些低维度如2维、3维最优覆盖表上界, 同时, 这项研究为后面的TS算法奠定了基础.2009年, Robert等人^[25]使用TS算法又改进了一些3~5维覆盖表上界, 他们还第一次利用计算搜索方法生成了6~7维高维度覆盖表.为了生成高维度覆盖表, Robert并没有直接使用TS生成覆盖表, 而是先生成CPHF(covering perfect hash family), 然后将CPHF转换成覆盖表, 这样可以大大缩短生成时间, 使得生成高维度覆盖表变得可行.不过, 该方法只能生成参数取值个数必须为素数或素数幂的覆盖表.此后, Gonzalez-Hernandez等人^{[11, 24]}提出了MiTs方法, 该方法利用复合邻域函数来平衡搜索过程的集中性和多样性, 由此获得较小覆盖表, 该方法的缺点是生成时间过长.2016年, Kamal等人^[30]又提出了HHH(high level hyper-heuristic)方法, 它是目前有关TS生成覆盖表的最新方法.该方法利用TS的禁忌表封锁性能较差的低层搜索算法, 从而使性能较好的低层搜索算法有更多被选中的机会去生成覆盖表, 由此来获得规模较小覆盖表.但从文献[30]提供的实验结果来看, HHH方法生成的覆盖表规模要稍大于MiTs方法.

在约束处理方面, 2008年, Cohen等人^[22]首次在AETG下利用可满足性问题(SAT)求解器进行约束处理, 生成了35个含约束的2维覆盖表.接着, 2009年, Garvin等人^{[23, 27]}将模拟退火算法SA与SAT求解器进行结合, 生成了带约束的覆盖表.2015年, Yu等人^[20]基于禁止元组, 使用IPOG进行了约束覆盖表生成.该方法虽然生成的覆盖表规模较大, 但速度优势非常明显.与前面的方法不同, Akihisa Yamada等人^[26]将覆盖表的生成看成一个约束问题, 然后利用约束解决器进行求解, 该方法能获得较小规模的覆盖表.

在变力度覆盖表生成方面, 2003年, Cohen等人^[13]第1次提出了变力度覆盖表的概念, 并使用模拟退火算法SA生成了11个变力度覆盖表.2009年, Chen等人^[14]又使用蚁群算法ACS生成了变力度覆盖表.与SA相比, ACS生成的覆盖表规模虽较大, 但生成速度更快.2011年, Ahmed等人^[15]将变力度实例扩展到18个, 并使用粒子群算法VS-PSTG生成了相应的覆盖表.2012年, 王子元等人^[31]提出一种新的可变力度组合测试模型, 并给出了基于one-test-at-a-time策略的可变力度覆盖表生成算法.在新的变力度测试模型中, 测试用例集不再需要覆盖任意t个参数间取值组合, 仅需要满足给定的覆盖需求即可, 因此, 该模型可以更为准确地描述系统中参数间的交互作用.在覆盖表规模方面, 该文中的算法相对于某些可变力度覆盖表生成工具如PICT^[32]具有一定的优势, 但仍不如Cohen等人提出的SA.

在并行计算方面, 2011年, Himer等人^[33]利用高性能计算机并行地统计各参数取值组合被覆盖情况, 依此来验证一个矩阵是否满足全覆盖, 但该文献并不进行覆盖表的生成.2014年, Lopez-Herrejon等人^[34]利用并行遗传算法为软件生产线生成具有优先级的2维覆盖表.近年来, 一些研究者开始利用分布式系统进行并行化.例如, Geronimo等人^[35]利用Hadoop MapReduce实现遗传算法并行化, 提高覆盖表生成速度.最近, 戚荣志等人^[29]还基于另外一种分布式并行计算框架Spark提出了一种岛模型并行化遗传算法, 该方法支持大规模种群下的快速寻优, 能大大加快覆盖表的生成速度.目前, 这些分布式并行化研究主要还是针对遗传算法.

7 结论及未来工作

覆盖表生成作为组合测试的关键问题之一, 一直受到工业界和学术界的重视.覆盖表规模、种类以及生成时间是衡量覆盖表生成算法的3个重要指标.作为一种有效的覆盖表生成算法, 禁忌搜索在覆盖表规模方面表现出一定优势, 但解的质量和运算速度仍然有提升的空间.特别是目前已有的禁忌搜索算法只关注于相对简单的固定力度无约束的组合测试模型, 而事实上, 在很多软件系统中, 参数间的交互力度往往是不同的, 参数间的约束也普遍存在.如果不考虑这些应用场景, 组合测试将难以发挥其作用.

在已有的研究工作基础上, 为了进一步提升TS在覆盖表生成上的应用潜力, 本文提出了一种新的TS算法PTS_CVS, 所做的主要工作如下.

● 首先, 通过pair-wise实验和爬山实验构成的参数配置调优, 获得了TS最佳参数配置, 并使用Friendman和Wilcoxon检验法对该最优配置进行统计分析;

● 其次, 将TS与禁止元组的约束处理方法相结合, 使TS能够生成带约束的覆盖表, 并进一步扩展TS使其支持可变力度覆盖表的生成;

● 最后, 为了提高覆盖表生成速度, 使用ForkJoin框架实现TS并行化.

实验结果表明:在覆盖表规模方面, PTS_CVS在多种测试模型下都更新了一些覆盖表的上界; 在生成速度上, 虽然不同测试模型会导致并行化提速的不同, 但是平均上仍有2.6倍的提速.

在下一步工作中, 我们将继续探索新的约束处理方法, 进一步提高PTS_CVS的约束处理能力.基于禁止元组约束处理, 在约束量不大情况下效果较好; 但是当约束个数较多时, 效果并不理想.例如, SPIN-V实例中的禁止元组数高达66个, 并且60%的参数至少参与一个禁止元组, 此时PTS_CVS生成的覆盖表是所有方法中最大的(见表 23).其次, 利用ForkJoin框架进行算法并行化, 虽然有一定的提速, 但由于本地并行化受单机硬件资源限制, 效果有限.因此, 我们计划将实验迁移到分布式或云平台环境中, 利用这些平台超强的计算能力更快更好地实施实验, 进一步提升覆盖表生成效率.