2016, Vol. 27
2. 山东建筑大学 计算机科学与技术学院, 山东 济南 250101
2. School of Computer Science and Technology, Shandong Jianzhu University, Ji'nan 250101, China
测试是提高软件质量的重要途径[1].为了对软件进行测试, 通常需要准备一定数量的测试数据, 称为测试数据集.测试数据集的充分性对于提高软件测试的可信度是非常重要的.评价某测试数据集的充分性, 往往通过对被测软件实施变异测试[2].实施变异测试时, 首先采用变异算子对原程序的某个语句进行符合语法的微小变动, 得到的新程序称为变异体;然后采用某一相同的输入, 分别执行原程序和变异体, 如果这两个程序的输出或者某中间状态不同, 则称该输入杀死了变异体;如果对于任何输入, 这两个程序的输出或者中间状态都是相同的, 则称该变异体是等价变异体[3].
变异测试的有效性一般通过变异得分衡量, 即被杀死的变异体个数与全部非等价变异体个数的比.
在变异测试中, 变化语句所在的位置称为变异点, 变化之后的语句称为变异语句.对于某变异体而言, 对原程序的变化得到的变异语句可能有一个, 也可能有多个.如果变异语句只有一个, 那么称该变异体为一阶变异体;否则, 称为高阶变异体[4].相应的变异测试分别称为一阶和高阶变异测试.考虑到一阶变异测试是高阶变异测试的基础, 本文仅研究一阶变异测试.变异测试是一种直接面向缺陷的测试方法, 具有很强的检错能力, 但是对于某程序而言, 变异体数量的增多, 增大了变异测试代价, 降低了变异测试效率.
如前所述, 可以采用不同的准则判定某变异体是否被杀死.如果基于原程序和变异体的输出, 那么该变异测试准则称为强变异测试[5];如果基于原程序和变异体变异点的状态, 那么相应的变异测试准则称为弱变异测试[6].已有研究表明:弱变异测试不但能够保证变异测试的有效性, 而且能够大幅度降低变异测试代价[7].鉴于此, 本文考虑弱变异测试.
所谓并行程序, 是指含有两个或者以上并行执行进程(线程)的程序, 已经广泛应用于科学研究和生产生活中, 如天气预报、邮件过滤以及病毒分析等[8].在诸多并行程序中, 消息传递并行程序的应用非常广泛, 该程序不但具有传统串行程序的很多语句类型, 而且包含若干并行环境控制和通信语句[9].与串行程序相比, 消息传递并行程序不但变异体数量多, 而且变异语句类型繁多.此外, 该程序的执行还具有不确定性, 这使得消息传递并行程序的变异测试非常具有挑战性.这也说明, 研究该程序的变异测试理论与方法是十分有意义的.
本文研究消息传递并行程序的一阶弱变异测试, 借鉴已有串行程序弱变异测试转化的方法, 提出该程序的弱变异测试转化方法.该方法将消息传递并行程序的弱变异测试问题转化为另一新程序的分支覆盖问题, 为采用已有的分支覆盖方法解决变异测试问题奠定了基础, 从而提高了变异测试效率.为此, 首先根据消息传递并行程序包含语句的类型和语句变异之后导致的变化, 构建相应的变异条件语句;然后, 将构建好的所有变异条件语句插入原程序中, 形成新的被测程序.可以看出, 消息传递并行程序变异条件语句的构建和新的被测程序的形成是本文的关键.
本文的创新之处主要体现在:(1) 给出了变异点语句为进程之间通信语句的变异条件语句构建方法;(2) 给出了变异点语句为进程之间通信语句的消息传递并行程序弱变异测试转化方法.
本文第1节介绍与本文研究相关的工作.本文提出的方法在第2节详细阐述, 包括进程内语句和进程之间通信语句的变异条件语句构建以及并行程序弱变异测试转化等.第3节是本文方法在典型并行程序测试中的应用以及对比实验.第4节总结全文, 并指出需要进一步研究的问题.
1 相关工作鉴于本文研究消息传递并行程序的一阶弱变异测试, 因此, 与本文研究相关的工作主要包括如下3个方面:变异测试、串行程序弱变异测试转化以及并行程序测试.
1.1 变异测试记被测程序为S, 变异点所在的语句为sj, 对该语句实施某一变异算子之后, 得到的变异语句记为
记S的输入向量为
以
强变异测试最早由DeMillo等人提出[5].基于强变异测试准则判定某变异体是否被杀死, 必须同时满足以下3个条件:(1) 可达性, 测试数据能够到达变异点;(2) 必要性, 测试数据到达变异点之后, 能够使变异点的状态发生改变;(3) 充分性, 变异点状态的改变, 能够传播到程序的输出, 且使得变异体和原程序的输出不同[10].容易看出, 强变异测试需要执行整个被测程序, 因此测试代价非常高.
为了降低变异测试代价, Howden提出了弱变异测试准则[11].该准则基于变异点的状态是否与原程序相同, 判定某变异体是否被杀死.可以看出, 只需满足强变异测试中的可达性和必要性条件, 即可依据弱变异测试准则判定某变异体被杀死.由于弱变异测试只需执行部分被测程序, 因此, 弱变异测试所需的代价明显低于强变异测试, 这通过Girgis等人[12]和Marick[7]的实验得到了验证.但是变异点状态的改变, 不一定能够传播到程序的输出, 因此, 弱变异测试的有效性一般比强变异测试低.不过, Horgan等人从理论上证明, 在特定条件下, 弱变异和强变异测试能够产生同样有效的测试数据[13].之后, Offutt等人通过实验验证了上述论断的正确性[14].
除了弱变异测试之外, 还可以通过约简变异体降低变异测试代价.所谓约简变异体, 是在保证变异测试有效性的前提下, 通过分析变异体之间的相关性减少需要杀死的变异体[15, 16].目前, 已有的变异体约简方法主要包括变异体抽样、变异体聚类、选择性变异以及高阶变异等[2].
1.2 串行程序弱变异测试转化与变异测试相比, 结构覆盖测试也是一种重要的软件测试方法.该方法要求生成测试数据以覆盖程序的某种结构, 如语句、分支以及路径等, 相应的结构覆盖准则分别称为语句覆盖[17]、分支覆盖[18]以及路径覆盖[19]等.将结构覆盖问题转化为优化问题, 并采用进化优化方法生成期望的测试数据, 成为目前软件测试界的重要研究方向之一.Lin等人采用遗传算法生成覆盖路径的测试数据[20], 之后, Ahmed[21], Watkins和Hufnagel[22]等人也提出了用于路径覆盖的测试数据生成方法.Pargas利用控制依赖图和遗传算法, 分别生成覆盖语句和分支的测试数据[23].Wegener等人针对嵌入式软件, 提出了基于进化算法的分支覆盖测试数据生成方法[24].此外, 我们针对多路径覆盖问题, 采用遗传算法生成了期望的测试数据[25, 26].
对于前面提及的弱变异测试, 如果将杀死变异体的条件转化为分支覆盖条件, 就能将生成杀死变异体的测试数据问题转化为覆盖分支的测试数据生成问题, 而后者可以利用已有的方法求解.这样一来, 就可以利用结构覆盖测试的成果解决变异测试问题.
鉴于此, Papadakis提出了弱变异测试转化方法, 基于杀死变异体的必要条件生成条件语句的谓词表达式, 从而将杀死变异体的问题转化为条件语句真分支的覆盖问题, 并利用符号执行、混合执行以及基于搜索的方法生成变异测试数据[27].进一步地, Papadakis通过选择合适的路径生成测试数据, 提高了变异测试的实用性[28].
1.3 并行程序测试如前所述, 并行程序包含多个进程, 其执行具有不确定性.这使得对于相同的程序输入, 不同的调度序列可能会产生不同的输出.这样一来, 对于一个并行程序的测试不但要考虑该程序的输入, 而且要考虑不同进程的调度序列.因此, 与串行程序相比, 并行程序测试的复杂度大为提高, 难度大为增加.
对于并行程序的结构覆盖测试, 目前已有了一些研究成果.Carver等人对并行程序的通信序列进行了测试[29].Hilbrich等人通过追踪等待状态, 检测一个并行程序可能发生的死锁[30].Takahashi等人针对并发程序提出了相应的覆盖准则, 以发现该程序的特定缺陷[31].Souza等人提出了并行程序的多种结构覆盖准则, 为测试数据的生成提供了指导[8, 9].此外, 我们定义了等价路径, 并利用遗传算法生成了覆盖目标路径或其等价路径的测试数据[32].
鉴于变异测试具有很强的缺陷检测能力, 因此对并行程序实施变异测试, 对于及时发现该程序存在的缺陷是非常必要的.但是并行程序存在的大量变异体, 使得该程序的变异测试代价非常高.此外, 并行程序生成的变异体还可能导致程序死锁, 这进一步增加了变异测试的难度.
尽管如此, 目前已有了诸多并行程序变异测试的方法.Carver提出了一种执行测试和变异测试相结合的并行程序变异测试方法[33], 之后, Bradbury等人针对java语言定义了一系列与线程和同步运算相关的变异算子[34].考虑并发程序可能产生多个调度序列, Sen等人提出了一种新的覆盖准则, 使得生成的测试数据集更加充分[35]. Gligoric等人利用程序的执行信息, 减少了多线程代码的变异测试代价[36], 之后, Gligoric提出了一种选择变异测试方法, 减少了并发代码生成的变异体数量[37].针对消息传递并行程序, Sliva等人设计了相关的变异算子, 为该程序的变异测试奠定了基础[38].但是, 已有的研究成果要么适用于并发程序的变异测试, 要么针对消息传递并行程序, 仅设计了变异算子, 还没有提出针对消息传递并行程序变异测试效率提高的方法, 特别是还没有研究该程序的弱变异测试方法.
对于串行程序的弱变异测试, 已有将变异测试转化为分支覆盖测试的方法.但是对于消息传递并行程序的弱变异测试, 如果期望利用上述思想转化为分支覆盖问题, 那么需要采用合适的方法, 生成条件语句的谓词表达式.考虑到并行程序包含的语句不但有进程内部的语句, 还有不同进程之间的通信语句, 而基于不同的语句产生的变异体对程序执行的影响不同, 因此需要采用有针对性的方法, 对于不同类型的语句构建相应的条件语句.
2 提出的方法本文研究消息传递并行程序的弱变异测试问题, 提出了该程序的弱变异测试转化方法, 从而将该程序的弱变异测试问题转化为另一新程序的分支覆盖问题, 以期采用已有的方法解决变异测试问题, 从而提高变异测试的效率.为此, 首先根据消息传递并行程序包含语句的类型和语句变异之后导致的变化构建相应的变异条件语句, 然后将构建好的所有变异条件语句插入原程序中, 形成新的被测程序.
为了清楚地阐述本文提出的方法, 首先引出一些常用的概念.
2.1 基本概念在不引起混淆的前提下, 记被测的并行程序为S, 该程序由n(n>1)个进程构成, 分别记为S0, S1, …, Sn-1.这n个进程并行执行, 共同完成任务, 那么S可以表示为S={S0, S1, …, Sn-1}.
对于程序S的第i个进程Si, 其基本执行单元称为一个节点.对于程序S的某一输入向量, 一个节点中的语句要么全部执行, 要么全部不执行.一个节点可以是一条分支语句的判断条件, 也可以是一条循环语句的控制条件;可以是一或多条连续执行的语句, 也可以是一条消息发送或接收语句.通常, 记进程Si的第j个节点为
考虑进程Si, 其控制流图是一个有向图, 记为G(Si)={N(Si), E(Si), s(Si), e(Si)}, 其中,
· N(Si)是G(Si)的顶点集, 对于G(Si)的任何一个顶点, 进程Si中都有一个节点与之对应;对于进程Si的任意2个节点nk和nl, 如果在某一输入下, nk执行之后nl立即执行, 那么这2个节点形成了G(Si)的一条边, 记为
· G(Si)的所有边形成的集合为E(Si);
· 此外, s(Si), e(Si)分别为Si的入口和出口节点.
基于进程的控制流图, 可以构建一个并行程序的控制流图.如果记S的控制流图为G(S), 那么其顶点集记为N(S), 可以表示为N(S)={N(S0), N(S1), …, N(Sn-1)};其边集记为E(S), 可以表示为
E(S)={E(S0), E(S1), …, E(Sn-1), E(S0, S1), …, E(S0, Sn-1), E(S1, S0), …, E(S1, Sn-1), …, E(Sn-1, S0), …, E(Sn-1, Sn-2)},其中, E(Si, Sj)(i, j=0, 1, …, n-1)为从进程Si发送到Sj的通信边集.需要注意的是, 由于进程Si到Sj的通信是有向的, 因此一般情况下, E(Si, Sj)≠E(Sj, Si);此外, 对于S而言, 由于该程序的多个进程可以同时开始执行, 因此, 并行程序G(S)的入口和出口节点均不再是唯一的, 且这些节点的个数与该程序包含的进程数密切相关.
图 1(a)~图 1(c)为某一并行程序的源程序, 该程序的功能是求取3个整数的最大公约数, 包含4个进程.其中, 图 1(a)为进程S0的源程序, 图 1(b)为进程S1和S2的源程序, 图 1(c)为进程S3的源程序.对于每一进程, 采用上面的方法可以得到该进程的控制流图.考虑不同进程的通信, 可以得到基于不同进程的节点形成的通信边.与上述控制流图一起, 可以构成整个并行程序的控制流图, 如图 1(d)所示.
|
Fig. 1 Sample parallel program and its control flow graph 图 1 示例并行程序及其控制流图 |
2.2 变异条件语句构建
容易知道, 对并行程序的不同进程、同一进程的不同变异点实施变异算子以及同一变异点实施不同的变异算子, 都可以得到该程序的不同变异体.这样一来, 并行程序的变异体是非常多的.因此, 有必要采用合适的方法提高变异测试的效率.
为了提高变异测试效率, Papadakis等人考虑弱变异测试准则, 以杀死变异体的必要条件为基础, 将变异体杀死问题转化为某一条件语句真分支的覆盖问题[27].这样做的好处是, 能够利用已有的方法解决变异测试问题.这样一来, 与变异体对应条件语句的构建, 简称为变异条件语句, 显得十分重要.Papadakis等人给出的方法如下:记由某变异点语句形成的表达式为e, 变异后语句形成的表达式为e′, 那么杀死该变异体的必要条件可以表示为“e!=e′”.以此作为某条件语句的谓词表达式, 以反映该变异体被杀死的标志语句, 作为该条件语句的真分支, 即可得到与该变异体对应的条件语句.
可以看出, 构建与某变异体对应的条件语句的关键在于形成该条件语句的谓词表达式.对于串行程序而言, 上述条件语句的构建比较容易.但是, 由于并行程序除了包含各进程的语句之外还包含反映不同进程通信的语句, 且对于后类语句的变异有可能引起通信环境的改变和程序的死锁, 这使得已有的变异条件语句构建方法很难适用于并行程序.这说明, 有必要采用新的方法构建针对并行程序的变异条件语句.
对于进程内的语句, 实施变异操作之后形成的变异体, 可以采用文献[27]的方法构建其变异条件语句.但是对于进程之间的通信语句, 实施变异操作形成的变异体, 构建相应的变异条件语句之前需要重现原程序的通信环境.构建这类语句的变异条件语句时, 不仅要考虑杀死变异体的必要条件, 还要避免程序死锁, 这些问题都是已有方法所不能解决的.下面详细阐述这两类语句的变异条件语句构建方法.
2.2.1 进程内语句的变异条件语句构建考虑并行程序S的进程Si, 记变异点所在的语句为
考虑图 1示例程序的进程S3, 变异点所在的语句为 s73 :“if (a<b)”, 该语句的谓词表达式为“a<b”.采用算术运算变异算子对上述语句实施变异操作之后, 得到的变异语句为
| $\begin{matrix} if\text{ }(\left( a ＜b \right)!=(a\le b)) \\ sgn=1; \\ \end{matrix}$ |
对于一个并行程序, 对其变异之后, 可能引起程序死锁:如果引起死锁, 则说明该变异体是可以被杀死的;如果不引起死锁, 则需要采用合适的方法构建相应的变异条件语句.表 1列出了一些常用的MPI变异算子[38].下面根据程序变异后是否引起程序死锁, 对这些变异算子进行分析.
对于表 1中的变异算子“ReplProbe”, 将其施加于消息接收函数“MPI_Recv(&recvbuf, count, dtype, source, tag, comm, &status);”之后, 得到变异语句为一个消息探测函数“MPI_Probe(source, tag, comm, &status);”.考虑到消息探测函数没有改变原来接收函数的消息标签, 因此可以直接执行.这样一来, 该变异算子对程序中某语句的变异将不会引起变异体的死锁.类似的变异算子还有ReplRoot, ReplReduce, ReplGather, DelBarrier, MoveCollectiveUp Down, ReplModelSend, ReplModeSend, ReplSendRecv以及ReplModelRecv.
对于变异算子“ReplSource”, 如果将其施加于消息接收函数“MPI_Recv(&recvbuf, count, dtype, source, tag, comm, &status);”, 那么, 可以得到变异语句为“MPI_Recv(&recvbuf, count, dtype, othersource, tag, comm, &status);”.可以看出, 该变异算子将接收函数中的参数“onesource”变为“othersource”.这样一来, 变异后的接收语句将不能接收到来自进程“onesource”的消息, 可能会一直等待, 使得变异体发生死锁.对于表 1中的其他变异算子, 如Del Send, ReplTag, ReplArg, ChanArg, ReplCall, DelCall, ReplStart, ReplWait以及InsUnaArg, 对相应的语句实施变异操作之后, 也可能使得变异体发生死锁.
|
Table 1 Commonly used MPI mutation operators 表 1 常用的MPI变异算子 |
对于不会引起死锁的并行程序, 其通信语句执行之后, 可能引起该程序通信环境的改变.在构建变异条件语句之前, 为了保证通信环境的一致性, 需要重现并行程序原来的通信环境, 使得变异前后在同一通信环境下具有可比性;另外, 还需要在变异语句或(和)与该语句匹配的语句之后, 添加原语句或(和)原语句的匹配语句, 以便于对比.这样一来, 添加一些语句, 用于记录变异语句或其匹配语句执行之后的参量值, 根据记录的参量值, 便可形成变异条件语句的谓词表达式, 再将能够反映变异体被杀死的标志语句作为该条件语句的真分支, 即可得到变异条件语句.
容易知道, 某并行程序的不同通信语句对应不同的通信环境.这需要采用有针对性的方法重现相应的通信环境.对于点到点通信函数, 由于它们只涉及两个相关的进程, 因此只需在变异语句和原语句之间插入相应的赋值语句, 即可重现相应的通信环境.但是集合通信函数往往涉及多个进程, 在重现相应的通信环境时, 不仅要在变异语句和原语句之间插入相应的赋值语句, 还需要对其他相关进程进行必要的处理.
现在通过一个例子说明上述构建变异条件语句的方法.
考虑图 1示例程序的进程S1, 变异点所在的语句
“MPI_Recv(buf, 2, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);”.
对该语句施加变异算子“ReplModelRecv”之后, 得到的变异语句s'21为
“MPI_Irecv(buf, 2, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);”.
由于该变异算子不会引起变异体死锁, 因此在构建变异条件语句之前, 首先保留变异语句s'21及其匹配语句
综上所述, 在转化后的新程序中, 与对
|
Fig. 2 Building the mutation condition statement of communication statements 图 2 通信语句的变异条件语句构建 |
2.3 弱变异测试转化
对于每一变异语句, 按照第2.2节的方法构建变异条件语句之后, 将这些语句插入到原程序的合适位置, 能够形成一个新的被测程序, 简称新程序.然而, 由不同类型的语句构建的变异条件语句, 其插入原程序的方式不同, 下面根据不同类型的变异条件语句给出其插入原程序的不同方法.
如果变异点所在的语句属于某进程内的语句, 那么将这些变异条件语句依次插入到变异点所在语句之前.如图 3所示, 其中, 图 3(a)为图 1示例并行程序进程S3的控制流图, 图 3(b)为插入节点7的变异条件语句之后形成新程序的控制流图.该图中, 节点N[1], N[2], …, N[n]分别对应不同的变异条件语句.
|
Fig. 3 Mutation statement is the statement in-process 图 3 变异语句为进程内语句 |
如果变异点所在的语句是不同进程之间的通信语句, 那么将该语句插入到变异语句之后, 并将这些变异条件语句依次插入到原语句或与之匹配的接收语句之后.如图 4所示, 其中, 图 4(a)为示例并行程序进程S0和S1的部分控制流图.由于变异点所在的语句为S0的节点2, 变异语句为S0的节点2′, 与节点2匹配的接收语句为S1的节点2′, 因此, 将变异条件语句插入到S1的节点2′之后, 如图 4(b)所示.
|
Fig. 4 Mutation statement is the communication statement between processes 图 4 变异语句为进程间通信语句 |
可以看出, 形成的新程序包含的节点急剧增多, 但是并没有改变原程序的功能.这是因为在相同的调度序列下, 对于相同的程序输入, 原程序和新程序会执行相同的路径, 从而产生相同的程序输出.
由于新程序中的变异条件语句与变异体一一对应, 且变异条件语句能够反映杀死变异体的必要性条件, 因此, 如果某测试数据能够在弱变异测试准则下杀死原程序的某一变异体, 那么该测试数据一定能够覆盖新程序对应变异条件语句的真分支.这样一来, 就能将杀死原程序变异体的问题转化为新程序的分支覆盖问题, 从而实现并行程序弱变异测试的转化.
2.4 实例分析下面以图 1中的示例程序为例, 说明消息传递并行程序弱变异测试转化的过程和转化的必要性.
对示例程序节点
|
|
Table 2 Mutation condition statements n22 表 2 变异条件语句n22 |
|
Fig. 5 Control flow graph of new program 图 5 新程序的控制流图 |
考虑到遗传算法是一种高效的测试数据生成方法, 因此选择该方法生成覆盖新的被测程序变异条件语句真分支的测试数据.以覆盖该程序的所有变异条件语句真分支为目标, 生成的测试数据集为T={[46,38,42], [31,58,25], [1,19,91], [32,1,81]}.由于变异条件语句真分支与变异体一一对应, 使用T的测试数据执行示例程序及其变异体, 在弱变异测试准则下, 杀死了M={mi, i=1, 2, …, 7}的所有变异体.
下一节通过多个被测程序的实验, 进一步说明本文方法的可行性和必要性.
3 实验本节通过实验来验证本文方法的可行性和必要性.首先给出实验需要验证的问题;然后介绍被测程序的基本信息和实验环境;在介绍实验过程之后, 给出实验结果和分析.
3.1 需要验证的问题通过验证如下两个问题, 说明所提方法的可行性和必要性:
(1) 基于本文方法, 以分支覆盖为准则生成的测试数据, 能否在弱变异测试准则下有效地杀死变异体?
(2) 采用本文方法生成的变异测试数据是否是高效的?
为了回答这两个问题, 首先, 基于转化后的新程序, 采用遗传算法生成覆盖变异条件语句真分支的测试数据, 并利用生成的测试数据, 在弱变异测试准则下对变异体进行测试, 通过考察变异体能否被杀死, 反映采用本文方法生成测试数据的可行性;然后, 通过对比采用本文方法与传统方法生成测试数据时需要执行程序或变异体的次数和时间, 反映采用本文方法生成测试数据的必要性.
3.2 被测程序和实验环境选择8个并行程序作为被测程序, 这些程序的基本信息见表 3, 其中, 程序Including的功能是判断点与多边形之间的位置关系, 该程序取自文献[39];Gcd源于文献[38]中的求取最大公约数程序, 并增加了数值对比功能;Matrix的功能是实现矩阵相乘, 并求取结果矩阵中最大的两个元素与预设值之间的关系;此外, 程序Index用于检索数组中大于某值元素的个数;Max_triangle用于求取两个数与给定值之间的最大元素, 并判断它们能否作为三角形的边, 如果能, 进一步给出它们构成三角形的类型;Compare用于对比2个数组对应元素之间的关系; Lcm的功能是求取3个数的最小公倍数;Rectangle用于判断4个数能否作为边构成矩形.在上述程序中, Including, Gcd和Matrix是典型的并行程序, 而Index, Max_triangle, Lcm, Rectangle和Compare均为串行基准程序的并行实现.
实验环境配置如下:硬件配置为Intel G630 CPU、500G硬盘、2G内存, 软件主要包括Windows 7操作系统、Visual C++ 6.0编译器以及MPI应用实现软件MPICH.
|
|
Table 3 Basic information of the programs under test 表 3 被测程序的基本信息 |
3.3 实验过程
实验过程如下.
首先, 对于每一被测程序采用不同的变异算子, 生成需要杀死的变异体.采用的变异算子包括表 1中不会引起程序死锁的MPI变异算子和其他12种方法级变异算子[40].利用这些变异算子对每一程序的进程内语句和进程间通信语句进行变异, 各程序的变异体见表 4.由该表可知, 进程内语句变异产生的变异体数量明显多于通信语句.需要说明的是:该表中的变异体不包括在弱变异测试准则下的等价变异体, 以便于计算变异得分.
|
|
Table 4 Mutants of the programs under test 表 4 被测程序的变异体 |
然后, 基于各程序和它们的变异体, 采用本文的方法形成转化后的新程序.进一步地, 基于转化后的新程序, 采用已有的分支覆盖方法生成覆盖变异条件语句真分支的测试数据, 并利用这些测试数据, 在弱变异测试准则下对各变异体进行测试, 记录变异体的杀死信息, 以验证本文方法的可行性.通过对比采用本文方法与传统方法生成的变异测试数据需要执行程序或变异体的次数和时间, 评价采用本文方法的必要性.鉴于遗传算法是一种优秀的分支覆盖测试数据生成方法, 因此, 选择该方法生成覆盖分支的测试数据.
采用遗传算法生成覆盖分支的测试数据时, 首先从未覆盖的变异条件语句真分支中选择一个作为目标分支, 并把覆盖该分支作为进化目标, 在适应度函数的引导下, 经过一系列的选择、交叉以及变异操作, 生成相应的测试数据.如果该测试数据能够覆盖目标分支或其他未覆盖的分支, 那么保留该测试数据, 将覆盖的分支标记为已覆盖分支, 并从剩下的未覆盖分支中选择一个作为新的目标分支;如果该测试数据不能覆盖目标分支, 那么该目标分支仍然保留在未覆盖的变异分支中, 直到覆盖所有的目标分支或达到最大进化代数, 遗传算法才终止.如果生成的测试数据能够覆盖新程序中全部变异条件语句真分支, 那么称生成测试数据成功;否则, 称生成测试数据失败.
遗传算法的个体采用二进制编码, 适应度函数由分支距离和层接近度构成.其中, 分支距离用于衡量变异条件语句谓词表达式为真的满足程度;层接近度用于衡量测试数据穿越的路径偏离变异条件语句所在节点的程度.分支距离和层接近度的计算方法请参见文献[41].遗传操作主要包括轮盘赌选择、单点交叉和单点变异.实验中, 种群规模为10, 交叉和变异概率分别为0.8和0.2, 最大进化代数为2 000.值得说明的是, 遗传算法的参数取值会对实验结果产生一定的影响, 这里选择的参数取值是多次实验结果的最佳值, 但不一定是该参数的最优值.
采用传统方法生成测试数据时, 以杀死全部变异体为目标, 在测试数据的搜索范围内随机生成测试数据, 并利用生成的测试数据执行原程序和各变异体, 根据原程序和变异体的执行状态判断变异体是否被杀死, 并给以标记.这一过程循环进行, 直到生成杀死所有变异体的测试数据或达到最大运行次数, 传统方法才终止.如果生成的测试数据能够杀死全部变异体, 则称生成测试数据成功;否则, 称生成测试数据失败.
为了使传统方法在最大运行次数内尽可能地生成期望的测试数据, 取最大运行次数为100 000.对于同一程序, 本文方法与传统方法的测试数据搜索范围相同, 除了程序Gcd的每一输入变量的搜索范围为[0 255]之外, 其他程序的搜索范围均为[0 127].另外, 由于本文方法需要覆盖的目标分支, 与传统方法需要杀死的变异体一一对应, 因此, 本文方法的目标分支个数与传统方法需要杀死的变异体相同.
最后, 分别记录采用本文方法和传统方法生成测试数据的实验结果并进行对比, 以验证本文方法的可行性和必要性.为了减少随机因素对实验结果的影响, 独立运行每一实验30次, 并取运行结果的平均值作为实验结果.
3.4 实验结果和分析 3.4.1 本文方法的可行性为了验证本文方法的可行性, 首先, 基于本文方法形成转化后的新程序, 并采用遗传算法生成覆盖变异条件语句真分支的测试数据;然后利用生成的测试数据, 在弱变异测试准则下对各程序的变异体进行测试, 并记录杀死变异体的个数和变异得分, 结果见表 5.
表 5中, 第1列是被测程序;第2列为基于分支覆盖生成的测试数据个数;第3列为这些测试数据覆盖的变异条件语句真分支个数;第4列为在弱变异测试准则下, 这些测试数据杀死的变异体个数;第5列为这些测试数据的变异得分.
|
|
Table 5 Generated test data and mutation score by the proposed approach 表 5 本文方法生成的测试数据及其变异得分 |
由表 5可知:
(1) 对于不同的被测程序, 生成的测试数据个数不同, 这些测试数据覆盖的变异分支个数不同, 相应地, 杀死的变异体个数也不同.生成测试数据最多的程序是Index, 为18.3, 这些测试数据杀死了78个变异体;程序Matrix生成的测试数据最少, 为4.0, 这些测试数据杀死的变异体个数为52.
(2) 不同测试数据集杀死变异体的能力不同.程序Matrix生成的每一测试数据平均杀死13个变异体, 能力最强;Rectangle生成的每一测试数据杀死变异体的能力最低, 平均仅能杀死1.8个变异体.
(3) 每一测试数据集的变异得分相同, 均为100%.
这说明, 采用本文方法将变异体杀死问题转化为变异条件语句真分支的覆盖问题之后, 采用遗传算法生成的覆盖变异分支的测试数据均能够在弱变异测试准则下杀死所有变异体.即本文提出的转化方法是可行的.
3.4.2 本文方法的必要性本节通过基于本文方法转化之后, 采用遗传算法, 能够高效地生成变异测试数据, 说明采用本文方法转化的必要性.为此, 分别基于本文方法和传统方法生成期望的测试数据, 记录生成期望的测试数据时, 两种方法生成测试数据的个数、需要执行程序或变异体的次数以及运行时间, 并计算传统方法与本文方法的测试数据个数、执行程序或变异体次数以及运行时间的比值, 分别记为测试数据个数比、执行次数比以及运行时间比, 结果见表 6~表 8.另外, 为了确定本文方法与传统方法的上述指标值之间是否具有显著差异, 采用Mann-Whitney U非参数假设检验, 取显著性水平为0.05.表 9列出了假设检验结果, 其中, 0, 1和-1分别表示针对某一性能指标值, 这两种方法没有显著差异、本文方法显著优于传统方法以及传统方法显著优于本文方法.
|
|
Table 6 Number of test data 表 6 测试数据个数 |
|
|
Table 7 Times of executing program or mutant 表 7 执行程序或变异体次数 |
|
|
Table 8 Run times (μs) 表 8 运行时间 (μs) |
|
|
Table 9 Result of nonparametric hypothesis testing 表 9 非参数假设检验结果 |
(1) 分别采用本文方法与传统方法, 生成期望测试数据的个数不完全相同.有3个程序, 即Matrix, Compare和Rectangle, 生成的期望测试数据个数相同;对于另外5个程序, 生成的测试数据个数不同.
(2) 对于某些程序, 虽然生成的期望测试数据个数不同, 但是相差不大.相差最大的是程序Index, 为2.6个测试数据;其次是Max_triangle, 仅相差0.8个.
(3) 虽然上述测试数据个数相差不大, 但是假设检验的结果表明:对于程序Index和Max_triangle而言, 这种差异却是显著的.
(1) 本文方法需要执行程序的次数, 远小于传统方法需要执行程序或变异体的次数.对于所有程序, 执行次数比均超过20, 其中, 执行次数比最大的程序是Gcd, 为63.7;最小的为21.0, 是程序Compare.
(2) 假设检验的结果表明, 本文方法的执行次数显著少于传统方法.这说明采用本文方法能够大幅度减少需要执行程序的次数, 从而提高了变异测试的效率.
(1) 对于每一被测程序, 本文方法的运行时间均少于传统方法.采用本文方法生成变异测试数据, 需要运行时间最少的是程序Lcm, 为68.03ms;最多的是程序Including, 为700.31ms;而采用传统方法, 相同程序需要的运行时间分别为989.71ms和3 485.13ms.
(2) 对于不同的被测程序, 运行时间比不同.运行时间比最大的是程序Gcd, 为16.81;最小的为3.26, 对应程序Compare.
(3) 假设检验的结果表明, 对于所有被测程序, 本文方法的运行时间均少于传统方法.可能的原因在于, 本文方法执行程序的次数远少于传统方法.
此外, 在执行程序或变异体的次数和运行时间方面, 对于每一被测程序, 本文方法的方差均小于传统方法;在测试数据个数方面, 对于程序Gcd, Matrix, Max_triangle和Compare, 本文方法的方差均小于或等于传统方法.这说明, 本文方法的稳定性总体优于传统方法.
综合以上实验结果与分析, 可以得到如下结论:与传统方法相比, 采用本文方法生成变异测试数据, 需要执行程序或变异体的次数更少、运行时间更短、生成过程更稳定, 从而生成测试数据的效率更高.这说明, 采用本文方法进行弱变异测试是非常必要的.
本节实验结果表明, 采用本文方法将弱变异测试问题转化为分支覆盖问题, 并利用已有的分支覆盖方法高效地生成变异测试数据, 对于提高变异测试效率不但是可行的, 也是必要的.
4 结束语本文研究的是消息传递并行程序的变异测试问题, 提出了适用于该类程序的弱变异测试转化方法, 目的在于提高变异测试的效率.在所提出的转化方法中, 通过分析消息传递并行程序不同类型的语句及其变异后引起的状态变化, 采用不同的策略构建相应的变异条件语句, 并进一步形成新的被测程序.利用提出的转化方法能够将原程序的弱变异测试问题转化为新程序的分支覆盖问题, 从而为采用已有的分支覆盖方法解决变异测试问题奠定了基础.
为了验证上述方法的有效性, 将所提出的方法应用于8个典型的消息传递并行程序测试中, 实验结果表明, 覆盖新程序变异条件语句真分支的测试数据能够杀死原程序的变异体;与传统的随机方法相比, 基于本文方法转化之后, 采用遗传算法生成测试数据需要执行程序或变异体的次数更少、运行时间更短, 从而提高了变异测试的效率.
值得说明的是, 本文仅考虑了原程序与变异体的关系, 没有分析不同变异体之间的关系, 也即没有分析新程序中不同变异条件语句真分支之间的关系.实际上, 这些真分支之间可能存在关联关系.如果通过分析这些变异条件语句真分支之间的关系, 采用合适的方法删除冗余的变异分支, 那么将会减少变异分支的个数, 从而提高变异测试的效率.这将是我们需要进一步研究的课题.
| [1] | Hamlet D. Software quality, software process, and software testing. Advances in Computers, 1995, 41 (8) :191–229. [doi:10.1016/S0065-2458(08)60234-X] |
| [2] | Jia Y, Harman M. An analysis and survey of the development of mutation testing. IEEE Trans. on Software Engineering, 2011, 37(5):649-678. [doi:10.1109/TSE.2010.62] |
| [3] | Madeyski L, Orzeszyna W, Torkar R, Jozala M. Overcoming the equivalent mutant problem: A systematic literature review and a comparative experiment of 2nd order mutation. IEEE Trans. on Software Engineering, 2014,40(1):23-42. [doi:10.1109/TSE.2013.44] |
| [4] | Jia Y, Harman M. Higher order mutation testing. Information and Software Technology, 2009, 51 (10) :1379–1393. [doi:10.1016/j.infsof.2009.04.016] |
| [5] | DeMillo RA, Lipton RJ, Sayward FG. Hints on test data selection: Help for the practicing programmer. Computer, 1978, 11 (4) :34–41. [doi:10.1109/C-M.1978.218136] |
| [6] | Offutt AJ, Lee SD. How strong is weak mutation? In: Howden W, ed. Proc. of the Symp. on Testing, Analysis, and Verification. New York: ACM Press, 1991. 200-213. [doi:10.1145/120807.120826] |
| [7] | Marick B. The weak mutation hypothesis. In: Howden W, ed. Proc. of the Symp. on Testing, Analysis, and Verification. New York: ACM Press, 1991. 190-199. [doi:10.1145/120807.120825] |
| [8] | Souza SRS, Brito MAS, Silva RA, Souza RSL, Zaluska E. Research in concurrent software testing: A systematic review. In: Lourenço J, Farchi E, eds. Proc. of the Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging. New York: ACM Press, 2011. 1-5. [doi:10.1145/2002962.2002964] |
| [9] | Souza PSL, Souza SRS, Zaluska E. Structural testing for message-passing concurrent programs: An extended test model. Concurrency and Computation: Practice and Experience, 2014, 26 (1) :21–50. [doi:10.1002/cpe.2937] |
| [10] | DeMilli RA, Offutt AJ. Constraint-Based automatic test data generation. IEEE Trans. on Software Engineering, 1991,17(9): 900-910. [doi:10.1109/32.92910] |
| [11] | Howden WE. Weak mutation testing and completeness of test sets. IEEE Trans. on Software Engineering, 1982,8(4):371-379. [doi:10.1109/TSE.1982.235571] |
| [12] | Girgis MR, Woodward MR. An integrated system for program testing using weak mutation and data flow analysis. In: Lehman MM, Hünke H, Boehm B, eds. Proc. of the 8th Int'l Conf. on Software Engineering. Los Alamitos: IEEE Computer Society Press, 1985. 313-319. |
| [13] | Horgan JR, Mathur AP. Weak mutation is probably strong mutation. Technical Report, SERC-TR-83-P, West Lafayette: Purdue University, 1990. |
| [14] | Offutt AJ, Lee SD. An empirical evaluation of weak mutation. IEEE Trans. on Software Engineering, 1994,20(5):337-344. [doi:10.1109/32.286422] |
| [15] | Xu SY. A method of simplifying complexity of mutation testing. Journal of Shanghai University (Natural Science Edition), 2007, 13 (5) :524–531(in Chinese with English abstract). [doi:10.3969/j.issn.1007-2861.2007.05.007] |
| [16] | Shan JH, Gao YF, Liu MH, Liu JH, Zhang L, Sun JS. A new approach to automated test data generation in mutation testing. Chinese Journal of Computers, 2008, 31 (6) :1025–1034(in Chinese with English abstract). [doi:10.3321/j.issn:0254-4164.2008.06.015] |
| [17] | Li JJ, Weiss D, Yee H. Code-Coverage guided prioritized test generation. Information and Software Technology, 2006, 48 (12) :1187–1198. [doi:10.1016/j.infsof.2006.06.007] |
| [18] | Madeyski L. The impact of test-first programming on branch coverage and mutation score indicator of unit tests: An experiment. Information and Software Technology, 2010, 52 (2) :169–184. [doi:10.1016/j.infsof.2009.08.007] |
| [19] | Murrill BW. An empirical, path-oriented approach to software analysis and testing. Journal of Systems and Software, 2008, 81 (2) :249–261. [doi:10.1016/j.jss.2007.05.008] |
| [20] | Lin JC, Yeh PL. Automatic test data generation for path testing using GAs. Information Sciences, 2001, 131 (1-4) :47–64. [doi:10.1016/S0020-0255(00)00093-1] |
| [21] | Ahmed MA, Hermadi I. GA-Based multiple paths test data generator. Computers & Operations Research, 2008, 35 (10) :3107–3124. [doi:10.1016/j.cor.2007.01.012] |
| [22] | Watkins A, Hufnagel EM. Evolutionary test data generation: A comparison of fitness functions. Software: Practice and Experience, 2006, 36 (1) :95–116. [doi:10.1002/spe.684] |
| [23] | Pargas RP, Harrold MJ, Peck RR. Test-Data generation using genetic algorithms. Software Testing Verification and Reliability, 1999, 9 (4) :263–282. [doi:10.1002/(SICI)1099-1689(199912)9:4<263::AID-STVR190>3.0.CO;2-Y] |
| [24] | Wegener J, Buhr K, Pohlheim H. Automatic test data generation for structural testing of embedded software systems by evolutionary testing. In: Langdon WB, Cantú-Paz E, Mathias KE, Roy R, Davis D, Poli R, Balakrishnan K, Honavar VG, Rudolph G, Wegener J, Bull L, Potter MA, Schultz AC, Miller JF, Burke E, Jonoska N, eds. Proc. of the Genetic and Evolutionary Computation Conf. San Francisco: Morgan Kaufmann Publishers, 2002. 1233-1240. |
| [25] | Gong DW, Zhang Y. Novel evolutionary generation approach to test data for multiple paths coverage. Acta Electronica Sinica, 2010, 38 (6) :1299–1304(in Chinese with English abstract). http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201006012.htm |
| [26] | Gong DW, Zhang WQ, Yao XJ. Evolutionary generation of test data for many paths coverage based on grouping. Journal of Systems and Software, 2011, 84 (12) :2222–2233. [doi:10.1016/j.jss.2011.06.028] |
| [27] | Papadakis M, Malevris N. Automatically performing weak mutation with the aid of symbolic execution, concolic testing and search-based testing. Software Quality Journal, 2011, 19 (4) :691–723. [doi:10.1007/s11219-011-9142-y] |
| [28] | Papadakis M, Malevris N. Mutation based test case generation via a path selection strategy. Information and Software Technology, 2012, 54 (9) :915–932. [doi:10.1016/j.infsof.2012.02.004] |
| [29] | Carver RH, Lei Y. Distributed reachability testing of concurrent programs. Concurrency and Computation: Practice and Experience, 2010, 22 (18) :2445–2466. [doi:10.1002/cpe.1573] |
| [30] | Hilbrich T, de Supinski BR, Nagel WE, Protze J, Bsier C, Müller MS. Distributed wait state tracking for runtime MPI deadlock detection. In: Gropp W, Matsuoka S, eds. Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. New York: ACM Press, 2013. 1-12.[doi:10.1145/2503210.2503237] |
| [31] | Takahashi J, Kojima H, Furukawa Z. Coverage based testing for concurrent software. In: Croll PR, ed. Proc. of the 28th Int'l Conf. on Distributed Computing Systems Workshops. Washington: IEEE Computer Society, 2008. 533-538. [doi:10.1109/ICDCS. Workshops.2008.76] |
| [32] | Tian T, Gong DW. Model of test data generation for path coverage of message-passing parallel programs and its evolution-based solution. Chinese Journal of Computers, 2013, 36 (11) :2212–2223(in Chinese with English abstract). [doi:10.3724/SP.J.1016.2013.02212] |
| [33] | Carver R. Mutation-Based testing of concurrent programs. In: Proc. of the IEEE Int'l Test Conf. on Designing, Testing, and Diagnostics. Washington: IEEE Computer Society, 1993. 845-853. [doi:10.1109/TEST.1993.470617] |
| [34] | Bradbury JS, Cordy JR, Dingel J. Mutation operators for concurrent Java (J2SE 5.0). In: Proc. of the 2nd Workshop on Mutation Analysis. Washington: IEEE Computer Society, 2006. 83-92. [doi:10.1109/MUTATION.2006.10] |
| [35] | Sen A, Abadir MS. Coverage metrics for verification of concurrent SystemC designs using mutation testing. In: Mishra P, Zilic Z, eds. Proc. of the IEEE Int'l High Level Design Validation and Test Workshop. IEEE, 2010. 75-81. [doi:10.1109/HLDVT.2010. 5496659] |
| [36] | Gligoric M, Jagannath V, Marinov D. MuTMuT: Efficient exploration for mutation testing of multithreaded code. In: Gaudel MC, Cavalli AR, Ghosh S, eds. Proc. of the 3rd Int'l Conf. on Software Testing, Verification and Validation. Washington: IEEE Computer Society, 2010. 55-64. [doi:10.1109/ICST.2010.33] |
| [37] | Gligoric M, Zhang LM, Pereira C, Pokam G. Selective mutation testing for concurrent code. In: Pezzè M, Harman M, eds. Proc. of the 2013 Int'l Symp. on Software Testing and Analysis. New York: ACM Press, 2013. 224-234. [doi:10.1145/2483760.2483773] |
| [38] | Silva RA, de Souza SRS, de Souza PSL. Mutation operators for concurrent programs in MPI. In: Champac V, Zorian Y, eds. Proc. of the 13th Latin American Test Workshop. Washington: IEEE Computer Society, 2012: 1-6. [doi:10.1109/LATW.2012.6261240] |
| [39] | Chen GL, An H, Chen L, Zheng QL, Shan JL. Parallel Algorithm Practice. Beijing: Higher Education Press, 2004 (in Chinese with English abstract). |
| [40] | Ma YS, Offutt J, Kwon YR. MuJava: A mutation system for Java. In: Osterweil LJ, Rombach D, Soffa ML, eds. Proc. of the 28th Int'l Conf. on Software Engineering. New York: ACM Press, 2006. 827-830. [doi:10.1145/1134285.1134425] |
| [41] | Yao XJ. Theory of evolutionary generation of test data for complex software and applications [Ph.D. Thesis]. Xuzhou: China University of Mining and Technology, 2011 (in Chinese with English abstract). |
| [15] | 徐拾义. 降低软件变异测试复杂性的新方法. 上海大学学报(自然科学版), 2007,13 (5) :524–531. [doi:10.3969/j.issn.1007-2861.2007.05.007] |
| [16] | 单锦辉, 高友峰, 刘明浩, 刘江红, 张路, 孙家骕. 一种新的变异测试数据自动生成方法. 计算机学报, 2008,31 (6) :1025–1034. [doi:10.3321/j.issn:0254-4164.2008.06.015] |
| [25] | 巩敦卫, 张岩. 一种新的多路径覆盖测试数据进化生成方法. 电子学报, 2010,38 (6) :1299–1304. http://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201006012.htm |
| [32] | 田甜, 巩敦卫. 消息传递并行程序路径覆盖测试数据生成问题的模型及其进化求解方法. 计算机学报, 2013,36 (11) :2212–2223. [doi:10.3724/SP.J.1016.2013.02212] |
| [39] | 陈国良, 安虹, 陈崚, 郑启龙, 单久龙. 并行算法实践. 北京: 高等教育出版社, 2004 . |
| [41] | 姚香娟.复杂软件测试数据进化生成理论及应用[博士学位论文].徐州:中国矿业大学,2011. |