消息传递并行程序的弱变异测试

摘要

变异测试是一种有效的软件测试方法，但高昂的测试代价，使其可行性和应用范围受到很大限制。消息传递并行程序是一类应用广泛的并行程序。为了保证该类程序的可靠性，有必要对其实施变异测试。消息传递并行程序不仅包含为数众多的语句类型和通信函数，其执行还具有不确定性和死锁等特征，这使得消息传递并行程序的变异测试异常困难。因此，有必要提出降低该类程序变异测试代价的理论与方法。本文针对消息传递并行程序，分别从弱变异测试转化、变异体约简，以及测试数据生成等3个方面进行研究。
　　首先，提出消息传递并行程序的弱变异测试转化方法，将变异体杀死问题转化为分支覆盖问题。为此，根据消息传递并行程序不同类型的语句，采用针对性的方法构建变异条件语句；在避免程序发生死锁的前提下，将变异条件语句插入原程序中，形成新的被测程序，从而实现消息传递并行程序的弱变异测试转化。该方法将变异体杀死问题转化为分支覆盖问题，为采用结构覆盖方法解决变异测试问题奠定了基础。
　　其次，提出基于占优度的变异体约简方法，减少需要杀死的变异体。为此，定义分支的占优度，并给出各分支之间占优度和各分支被占优度的计算方法，用于分析分支之间的相关关系；基于占优度和被占优度，给出判断冗余变异条件语句真分支的方法，并删除与冗余分支对应的变异体，以得到约简后的变异体。该方法不但能够保证变异测试的有效性，还能够提高变异测试的效率。
　　最后，针对变异测试数据生成问题，提出基于遗传算法的消息传递并行程序变异测试数据自动生成方法，以高效生成变异测试数据。为此，基于消息传递并行程序弱变异测试转化后的新程序，建立分支覆盖测试数据生成问题的数学模型；采用遗传算法求解该模型，以生成消息传递并行程序的变异测试数据。该方法能够有效提高变异测试数据生成的效率。
　　本文提出的方法，提高了消息传递并行程序变异测试的效率，扩大了变异测试的应用范围，具有重要的理论意义和实用价值。

目录

封面

声明

致谢

中文摘要

英文摘要

目录

1 绪论

1.1研究动机（Research Motivation）

1.2研究目标（Research Objectives）

1.3研究内容（Research Contents）

1.4研究方法（Research Approaches）

1.5成果意义（Research Achievements and Significance）

1.6本文结构（Structure ofThisThesis）

1.7本章小结（Conclusions of This Chapter）

2 相关工作

2.1变异测试（Mutation Testing）

2.2测试数据进化生成（Evolutionary Generation of Test Data）

2.3消息传递并行程序（Message Passing Parallel Programs）

2.4并行程序变异测试（Mutation TestingforParallel Programs）

2.5本章小结（Conclusions of This Chapter）

3 消息传递并行程序的弱变异测试及其转化1

3.1研究背景（Backgrounds of Research）

3.2变异条件语句构建（Constructing Mutation Condition Statement）

3.3 新程序形成（Forming New Program）

3.4 实验（Experiments）

3.5本章小结（Conclusions ofThis Chapter）

4 基于占优度的消息传递并行程序变异体约简2

4.1研究背景（Backgrounds of Research）

4.2 占优度（Dominance Degree）

4.3基于占优度的变异体约简（Mutant Reduction Based on Dominance Degree）

4.4 实验（Experiments）

4.5本章小结（Conclusions of This Chapter）

5 基于遗传算法的消息传递并行程序变异测试数据自动生成3

5.1研究背景（Backgrounds of Research）

5.2 分支覆盖测试数据生成问题的数学模型（ Mathematical Model of Test Data Generation with Cover Branches）

5.3基于遗传算法的变异测试数据生成（Test Data Generationfor Mutation TestingBased onGenetic Algorithms）

5.4 实验（Experiments）

5.5本章小结（Conclusions ofThis Chapter）

6 结论

6.1本文工作（Achievements of This Thesis）

6.2进一步研究工作（Future Research Topics）

参考文献

作者简历

学位论文数据集