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

摘要

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

主权项

评估蜕变关系的进程检错能力的方法，其特征如下：由于一个并行程序由多个进程组成，因此，蜕变关系对并行程序的检错能力，取决于其对每一进程的检错能力；为了考察蜕变关系的进程检错能力，首先说明程序的输入变量对进程的影响关系；为此，引入如下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的值增加