用于并行程序蜕变测试的蜕变关系优先级排序方法

摘要

用于并行程序蜕变测试的蜕变关系优先级排序方法。应用蜕变测试技术于并行程序的软件测试,先对构造的蜕变关系进行优先级排序，旨在尽早地发现程序中的错误，从而提高解决存在于软件测试中的Oracle问题的效率。该优先级排序策略利用蜕变关系产生的衍生测试用例及原始测试用例，以它们之间的相似度为依据估计其执行程序所覆盖路径的相似度，进而估计蜕变关系基于已有测试用例的检错范围，并基于此对蜕变关系进行优先级排序。具体步骤如下：(1)评估蜕变关系的各个进程检错能力；(2)设置各个进程的权值，以反映蜕变关系的各个进程检错能力，对评估其对整个程序检错能力所占的权重；(3)评估蜕变关系的程序检错能力,并确定各个蜕变关系的优先级；(4)检测程序。

说明书

技术领域

本发明涉及计算机软件测试领域，设计了一种针对并行程序的蜕变关系优先级排序方法，可用于提高蜕变测试技术应用于并行程序的测试效率。

背景技术

并行程序由于具有高效的问题解决能力，因此，在实际的问题中得到了广泛的应用，如油气勘探、生物信息处理，以及互联网服务等。在诸多并行程序开发方式中，最常用的当属使用消息传递环境扩展串行程序的方式，该方式能够减少额外编程负担，提高并行程序开发的效率。典型的消息传递环境有：并行虚拟机、消息传递接口、Express，以及CM信息传递库等。其中，前两种是公用软件，且具有很好的兼容性。随着网络技术的快速发展和单处理机性能的不断提高，消息传递接口和并行虚拟机也成为最流行的消息传递库。与串行程序相比，并行程序更加复杂，且可靠性要求更高。这意味着，对并行程序的测试非常必要。

软件测试通过分析或执行程序，以发现程序中存在的错误，是提高软件质量的重要手段。传统的测试技术多通过比较测试用例的执行结果与预期输出，以判断程序的正确性。但是，在很多情况下，测试人员很难甚至无法得到某测试用例的预期输出，该问题被称为Oracle问题。为了解决这类问题，Chen等提出了蜕变测试。该方法基于已有的测试用例，通过蜕变关系构造衍生的测试用例，并考察这些测试用例的执行结果是否满足某一特定的关系。如果不满足，那么，该程序包含错误。由于不需要被测程序的预期输出，因此，蜕变测试具有广阔的应用前景。

记被测程序为P，该程序的输入为x，输出为f(x)。对于n个程序输入x₁,x₂,...,x_n(n＞1)，其对应的程序输出分别为f(x₁),f(x₂),...,f(x_n)。这n个程序输入可能具有一定的关系，记为R。如果程序P正确，那么，与之对应的程序输出也将具有一定的关系，记为R_f，即

$>R(x_1,x_2,...,x_n)\Rightarrow R_f\left(f\right(x_1),f(x_2),...,f(x_n\left)\right)---\left(1\right)$>

称(R,R_f)为P的蜕变关系。

基于蜕变关系的测试，称为蜕变测试。在蜕变测试中，给定的测试用例，称为原始测试用例；基于该测试用例，利用关系R生成的测试用例，称为原始测试用例的衍生测试用例。

对于功能为计算正弦函数的程序，由于sin(x)＝sin(180-x)反映了程序不同输入之间的关系，因此，是该程序的一条蜕变关系。对于一个原始测试用例x＝46.8，其程序输出为P(x)＝0.7213。如果难以确定sin(46.8)的真实值，那么，将无法判断这一程序输出是否正确。但是，可以通过该原始测试用例及其蜕变关系sin(x)＝sin(180-x)，生成一个衍生的测试用例x'＝180-46.8＝135.，2再用x'执行该程序。如果P(x')≠P(x)，即不满足蜕变关系sin(x)＝sin(180-x)，那么，该程序将存在错误。

自提出以来，蜕变测试得到了学者们的高度关注，并取得了丰硕的成果。Hu等的实验结果表明，蜕变测试的成本低，并具有很强的检错能力。Chen等考察了多种蜕变关系，指出不同的蜕变关系具有不同的检错能力，使得选择合适的蜕变关系，成为蜕变测试的关键。Mayer等通过具体的程序，给出了评价蜕变关系性能的4条准则。为了能够循环地产生原始测试用例，Wu等人提出了迭代蜕变测试算法(IMT)。但该算法具有较高的复杂性，基于路径分析，Dong等人对IMT做了进一步改进。此外，为了说明蜕变测试的充分性，Dong等基于路径分析技术，提出了3种蜕变测试准则。但是，上述工作均针对串行程序。

经查阅相关文献，目前还不存在应用蜕变测试技术于并行程序时关于蜕变关系优先级排序的方法，这严重影响了蜕变测试在并行程序的应用。

发明内容

本发明首先考察蜕变关系的程序检错能力；然后，基于此对蜕变关系进行排序。

本发明所要解决的技术问题：克服现有技术的不足，将并行程序的设计理念与蜕变测试的原理相结合，根据测试用例间的相关性，提出一种蜕变关系优先级排序方法，优先选取程序检错能力强的蜕变关系，尽早发现错误，提高测试效率。

本发明的技术方案：提出了一种用于并行程序的蜕变关系优先级排序方法。

其特征在于步骤如下：

步骤1：考察蜕变关系的进程检错能力

容易理解，对于相同的测试用例，不同的蜕变关系生成了不同的衍生测试用例。不同的测试用例覆盖的路径往往不同，而错误往往存在于这些路径上，因此，不同的蜕变关系具有不同的检错能力，且衍生测试用例覆盖的路径与原测试用例差异大的蜕变关系，具有更强的检错能力。

假如某测试用例覆盖的路径为p＝1,2,3,5,6,8，数字1,2,...为程序的一个节点，可以是一或多条语句。存在两个蜕变关系MR₁与MR₂衍生的测试用例覆盖的路径分别为p'＝1,2,3,5,7,8与p"＝1,2,4,5,7,8。将两条路径均包含的节点个数与包含节点数较多的路径对应的节点个数的比值作为它们的相似度。那么，p'与p覆盖路径的相似度为p"与p覆盖路径的相似度为因此，后者的路径差异度大于前者。此时，蜕变关系MR₁只能检测位于节点{1,2,3,5,6,7,8}上的错误；而MR₂却能够检测位于节点{1,2,3,4,5,6,7,8}上的错误。与MR₁相比，MR₂具有更强的检错能力。

对于并行程序而言，程序的一条路径由多个子路径构成。此时，路径差异度的估计，可以通过子路径差异度的估计实现。由于不同进程涉及的变量可能不同，因此，子路径差异度的估计，可以通过涉及变量的差异实现。事实上，在进行优先级排序之前，并没有蜕变关系衍生测试用例的路径覆盖信息。前已指出，相似的测试用例往往覆盖相似的路径。鉴于此，本发明通过测试用例间，进程所涉及变量的相似度，估计它们在该进程中覆盖的子路径的相似度，进而估计这些子路径的差异度，最后评估蜕变关系的进程检错能力。

步骤2：评估蜕变关系的程序检错能力

一个并行程序尽管包含多个进程，但是，不同进程出错的概率并不完全相同。比如，一个包含代码行数多的进程，往往比包含代码行数少的进程具有更大的出错概率。鉴于此，本发明指出评估蜕变关系对整个程序的检错能力时，应对不同的进程设置不同的权值，以反映蜕变关系的各个进程检错能力，对整个程序检错能力的权重。该权重的取值可根据进程包含的代码行数或(和)路径个数等确定。

本发明提出的评估蜕变关系的程序检错能力的方法如下：记蜕变关系MR_s对于程序P的检错能力为C^s0，MR_s对进程P_i的检错能力为以及进程P_i的权值为ω_i，则n为进程数。

步骤3：蜕变关系的优先级排序

根据步骤2得到的蜕变关系的程序检错能力，按优先级从高到低的顺序排序蜕变关系。具体方法如下：

[1]:从待排序的蜕变关系集中选择一个蜕变关系并移除；

[2]:基于步骤2评估出的该蜕变关系的程序检错能力，确定其在已取出的蜕变关系中的优先级；

[3]:判断待排序的蜕变关系集是否为空，若为空，排序结束，否则，重复[1]与[2]。

本发明的主要贡献在于：(1)提出评估蜕变关系的进程检错能力的方法；(2)提出评估蜕变关系的程序检错能力的方法；(3)提出蜕变关系优先级排序的方法。

附图说明

图1本发明的总体流程图

图2示例程序进程0的源代码

图3示例程序进程1和2的源代码

图4示例程序进程3的源代码

具体实施方式

本发明用以排序蜕变关系，旨在应用蜕变测试技术于并行程序的软件测试,尽早地发现程序中的错误，从而提高解决存在于软件测试中的Oracle问题的效率。该优先级排序策略利用蜕变关系产生的衍生测试用例及原始测试用例，以它们之间的相似度为依据估计其执行程序所覆盖路径的相似度，进而估计蜕变关系基于已有测试用例的检错范围，并基于此对蜕变关系进行优先级排序。

该部分结合具体附图，对本发明的实施方式做详细说明。所提出方法的流程图如图1所示，具体实施步骤亦根据该图拟定，下面对本发明的技术方案做进一步详细描述。

步骤1：考察蜕变关系的进程检错能力

由于一个并行程序由多个进程组成，因此，蜕变关系对并行程序的检错能力，取决于其对每一进程的检错能力。为了考察蜕变关系的进程检错能力，首先说明程序的输入变量对进程的影响关系。为此，引入如下2个概念。对于并行程序P，包含的进程记为P₀,P₁,…,P_n-1，其中，n为进程的个数。此外，记程序的输入X＝(x₁,x₂,…,x_m)，其中，m为程序输入包含的变量个数。考虑进程P_i，如果某程序输入变量x_k直接影响P_i的至少一个子路径，那么，称x_k直接影响P_i。如果P_i有通信语句接收来自另一进程，记为P_j，的中间变量y，且y直接影响P_i的至少一个子路径，y的值在进程P_j中受输入变量x_l影响，那么，称x_l间接影响P_i。

对于某一进程，比较测试用例和基于某蜕变关系衍生的测试用例的相似度。一般的，如果二者包含的直接或间接影响该进程的不同变量越多，那么，这2个测试用例覆盖的该进程子路径的差异度越大，从而该蜕变关系对该进程的检错能力越强。此外，不同的变量影响进程关系，对蜕变关系检错能力的影响不同，且直接影响进程的变量，比间接影响具有更高的比重。

基于此，接下来给出如下的蜕变关系进程检错能力估计方法。考虑进程P_i，假设有m'个程序的输入变量直接影响该进程，此外，P_i还有若干通信语句接收来自其它进程的k个中间变量。由于影响P_i的(中间)变量共有m'+k个，因此，评估蜕变关系的进程检错能力(记为C_i)时，每一直接影响P_i的程序输入变量的贡献度为对于这m'个变量，如果衍生的测试用例与原测试用例有α个不同，那么，C_i的值增加考虑第l个中间变量，l＝1,2,…,k，影响该中间变量的程序输入变量有β_l个，此时，评估蜕变关系的进程检错能力时，这β_l个输入变量中，每一变量的贡献度为对于这β_l个变量，如果衍生的测试用例与原测试用例有γ个不同，那么，C_i的值增加

步骤2：评估蜕变关系的程序检错能力

一个消息传递并行程序尽管包含多个进程，但是，不同进程出错的概率是并不完全相同。比如，一个包含代码行数多的进程，往往比包含代码行数少的进程具有更大的出错概率。鉴于此，评估蜕变关系对整个程序的检错能力时，应对不同的进程设置不同的权值，以反映蜕变关系对进程的检错能力，对整个程序检错能力的权重。该权重的取值可根据进程包含的代码行数或(和)路径个数等确定。

记蜕变关系MR_s对于程序P的检错能力为C^s0，MR_s对进程P_i的检错能力为以及进程P_i的权值为ω_i，则n为进程数。

步骤3：蜕变关系的优先级排序

现在给出蜕变关系的优先级排序方法。记并行程序P的所有蜕变关系形成的集合为MR＝{MR₁,MR₂,…,MR_S}，其中，S为蜕变关系的个数。步骤如下:

步骤301:从MR中寻找优先级最高的蜕变关系

为此，考虑MR_s，根据衍生测试用例与原测试用例变量之间的差异度，计算MR_s对进程P_i的检错能力，记为基于进程P_i的权值，记为ω_i，计算MR_s对于程序P的检错能力，记为C^s0，那么，记优先级最高的蜕变关系为¹MR，那么，

$>M_{1}R=\arg \underset{s\in \{1,2,...,S\}}{max}{C}^{s0}---\left(2\right)$>

步骤302:从MR中寻找优先级次高的蜕变关系

如果某蜕变关系衍生的测试用例，与¹MR衍生的测试用例穿越的路径差异度很小，那么，该蜕变关系衍生的测试用例新覆盖的程序元素将很少。因此，寻找优先级次高的蜕变关系时，不仅需要考虑蜕变关系的衍生测试用例与原测试用例之间变量的差异度，还需要考虑其与¹MR衍生的测试用例之间变量的差异度。对于MR-¹MR中的蜕变关系MR_s衍生的测试用例，根据该测试用例与¹MR衍生的测试用例变量之间的差异度，计算MR_s对于程序P的检错能力，记为C^s1。记优先级次高的蜕变关系为²MR，那么，

$>M_{2}R=\arg \underset{s\in \{1,2,...,S\}}{max}\min \{C^{s0},C^{s1}\}---\left(3\right)$>

步骤303:确定其它蜕变关系的优先级

采用与步骤2类似的方法。记最高、次高、…、第I高优先级的蜕变关系分别为¹MR,²MR,...,^IMR。对于中的蜕变关系MR_s衍生的测试用例，根据该测试用例与ⁱMR衍生的测试用例变量之间的差异度，计算MR_s对于程序P的检错能力，记为C^si。那么，第I+1高优先级的蜕变关系为：

$>M_{I+1}R=\arg \underset{s\in \{1,2,...,S\}}{max}min\{C^{s0},C^{s1},...,C^{sI}\}---\left(4\right)$>

步骤304：判断是否为空

若为空，转向步骤4；否则，重复步骤303，直到所有的蜕变关系都分配优先级为止。

步骤4：检测程序

从排序好的蜕变关系集中选择优先级最高的蜕变关系检测程序，并从集合中移除，若发现程序有错，则操作结束；否则，重复步骤4选择下一个优先级最高的蜕变关系检测程序，直至蜕变关系集合为空。

步骤5：实例分析

选择程序Max-triangle作为被测程序，其代码在附图中，基于变异分析，评价所提方法的性能。该程序的功能是，求4个输入变量的最大数，并计算前3个输入变量能构成三角形时的面积，程序的输入为X＝{x,y,z,w}。该程序包含3个进程，其中，进程1求x,y和z构成三角形的面积，并将结果传递给进程0；进程2求y,z和w的最大数，并将结果传递给进程0；基于进程2的结果，进程0进一步求取X的最大数，并输出该最大数以及由前3个变量构成三角形时的面积。

本发明从如下2方面反映蜕变关系的检错能力：(1)基于蜕变关系衍生的测试用例集的变异得分，体现蜕变关系的检错范围；(2)基于蜕变关系衍生的测试用例集的平均变异得分，体现蜕变关系的检错效率。这里，测试用例集的变异得分指它们杀死的变异体数目占非等价变异体总数的比例；平均变异得分指，平均一个测试用例所可获得的变异得分。

根据程序Max-triangle的功能，构造3个蜕变关系，如表1所列。

表1 程序Max-triangle的蜕变关系

由表1可知，相比原始测试用例{x,y,z,w}，蜕变关系MR₁衍生的测试用例中输入变量x,y存在差异；MR₂衍生的测试用例中输入变量x,z存在差异；MR₃衍生的测试用例中输入变量y,z存在差异。

应用发明内容中所提方法，计算表1中蜕变关系对各个进程的进程检错能力。结果如表2所列。

表2 蜕变关系对各个进程的进程检错能力

由表2可知，(1)对于进程0，MR₃的进程检错能力要低于MR₁和MR₂的；(2)对于进程1，三个蜕变关系的进程检错能力相同；(3)对于进程2，MR₃的进程检错能力要高于MR₁和MR₂的。

采用数据语句变更(DSA)、算术符号替代(ARO)等几种基本的变异算子，生成程序Max-triangle的10个变异体，使得每一进程子路径至少出现一个错误。这些变异体的信息如下：

变异体1：进程0中语句12与语句13的代码互换；

变异体2：进程1中语句8替换为“p＝10；”；

变异体3：进程1中语句11替换为“p＝(sqrt(3.0)*x*x)+4.0；”；

变异体4：进程1中语句15替换为“p＝(z*p)*2.0；”；

变异体5：进程1中语句19替换为“p＝(z*p)+2.0；”；

变异体6：进程1中语句23代码中的“/2”替换为“*2”；

变异体7：进程1中语句25替换为“p＝(x+y+z)*2；”；

变异体8：进程2中语句6替换为“x＝++x；”；

变异体9：进程2中语句8替换为“x＝z；”；

变异体10：进程2中语句10替换为“x＝y；”。

选择原始的测试用例时，采用特殊值结合随机值的方法，使得原始的测试用例中包括有最大数位于输入X中的任一变量，以及前3个变量构成的三角形为等边三角形、等腰三角形、一般三角形和不构成三角形类型，其中，等腰三角形及不等边三角形又分为直角三角形和非直角三角形等2类。因为直角三角形的面积容易计算，因此，前3个变量构成直角三角形的测试用例选择很少。

基于上述准则，选择20个原始的测试用例，其中，有4个不能构成三角形，3个构成等边三角形，8个构成等腰三角形，5个构成一般三角形。基于这些原始的测试用例，采用表1的蜕变关系，得到衍生的测试用例。统计在不同进程下，每个蜕变关系衍生的测试用例的变异得分和平均变异得分，结果如表3所列。

表3 蜕变关系衍生测试用例集的变异得分和每一测试用例的平均变异得分(％)

由表3可知，(1)对于进程0，三个蜕变关系衍生的测试用例集具有相同的变异得分，均为100％，但是，使用蜕变关系MR₁和MR₂衍生的每一测试用例的平均变异得分分别为60％和55％，远高于使用蜕变关系MR₃衍生的每一测试用例；(2)对于进程1，三个蜕变关系衍生的测试用例集也具有相同的变异得分33.3％，均低于进程0，但是，使用蜕变关系MR₁、MR₂和MR₃衍生的每一测试用例的平均变异得分分别为8.3％、8.3％和10％，不同的蜕变关系相差不大；(3)对于进程2，蜕变关系MR₁和MR₂衍生的测试用例集的变异得分远低于MR₃，对于每一测试用例的平均变异得分，也是如此。

表2及表3说明本发明提出的蜕变关系进程检错能力估计方法是可行的。

这里采用变异分析，评价蜕变关系的检错能力。将进程中植入变异体的个数与整个程序的比，作为该进程的权值ω_i。由于程序Max-triangle植入的变异体一共10个，其中，进程0植入1个，进程1植入6个，进程2植入3个，因此，这3个进程的权值分别为：和

将本发明提出的蜕变关系优先级排序方法应用于程序Max-triangle中，基于原测试用例，各蜕变关系对程序的检错能力为因此，蜕变关系MR₃的优先级最高。进一步，基于MR₃衍生的测试用例和原测试用例，计算MR₁与MR₂的检错能力。由于相比MR₃衍生的测试用例，MR₁和MR₂衍生的测试用例变量中，x,y,z均发生改变，因此，从而MR₁和MR₂的程序检错能力不变。这说明，选择蜕变关系MR₃检测程序Max-triangle之后，MR₁和MR₂对程序Max-triangle的检错能力相同，从而可以从它们中随机选择一个，作为次高优先级的蜕变关系。至此，蜕变关系优先级排序完成。

基于前面20个原测试用例，按所排序的蜕变关系检错程序Max-triangle，依次执行每一蜕变关系生成的衍生测试用例集，考察变异得分的变化。该变化通过变异得分的增加量和平均增加量体现。这里，变异得分的增加量指，某蜕变关系生成的衍生测试用例所杀死的之前处于存活状态的变异体数占非等价变异体总数的比例；平均增加量指，平均一个测试用例获得的变异得分的增加量。在此外，通过随机顺序获得某一检错程序的蜕变关系序列作对比，依次执行每一蜕变关系生成的衍生测试用例集，记录变异得分的变化。结果如表4所列。

表4 衍生的测试用例集对变异得分的影响

由表4可知，(1)从本发明方法和随机方法得到的蜕变关系序列分别选择优先级最高的蜕变关系检错程序后，前者所得的变异得分为60％，高于后者的40％，且前者每个测试用例取得的平均变异得分为15.5％，要比后者高；(2)从本发明方法和随机方法得到的蜕变关系序列分别选择优先级最高的蜕变关系检错程序后，前者所得的变异得分为70％，而后者仅为60％，且前者每个测试用例所取得变异得分的平均增量为2.5％，同样高于后者的2％；(3)对于两种方法得到的蜕变关系序列，所有蜕变关系均检错程序后，取得的变异得分均达到70％。

由此可以看出，相比随机排序得到的蜕变关系序列，按照本发明方法所得的序列依次选择蜕变关系，生成的衍生测试用例执行程序所得到的变异得分上升的速度更快，且位于排序后序列前面的蜕变关系所生成的衍生测试用例中，每个测试用例所能杀死的之前存活的变异体效率更高。上述实验结果表明，本发明提出的蜕变关系优先级排序方法是有效的。