首页> 中文学位 >消息传递并行程序测试数据进化生成理论与应用
【6h】

消息传递并行程序测试数据进化生成理论与应用

代理获取

目录

封面

声明

致谢

中文摘要

英文摘要

目录

图清单

表清单

变量注释表

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 of the Dissertation)

1.7 本章小结(Conclusions of This Chapter)

2 相关工作

2.1 软件测试(Software Testing)

2.2 基于覆盖的测试数据生成技术(Test Data Generation Based on Coverage Criteria)

2.3 测试数据进化生成技术(Evolutionary Generation of Software Test Data)

2.4 合作型协同进化遗传算法( Cooperative Co-evolutionary Genetic Algorithms)

2.5 串行程序(Serial Programs)

2.6 消息传递并行程序(Message Passing Parallel Programs)

2.7 并行程序测试技术(Parallel Program Testing)

2.8 本章小结 (Conclusions of This Chapter)

3 单路径覆盖测试数据协同进化生成1

3.1 研究背景(Backgrounds of Research)

3.2 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

3.3 基于协同进化遗传算法的测试数据生成( Generating Test Data Based on the Co-Evolutionary Genetic Algorithm)

3.4 性能分析(Performance Analysis)

3.5 在并行程序测试中的应用(Applications in Testing Parallel Programs)

3.6 本章小结 (Conclusions of This Chapter)

4 单路径覆盖测试数据进化生成2

4.1 研究背景(Backgrounds of Research)

4.2 等价路径(Equivalent Paths)

4.3 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

4.4 基于遗传算法的测试数据生成(Test Data Generation Based on the Genetic Algorithm)

4.5 在并行程序测试中的应用(Applications in Testing Parallel

4.6 本章小结(Conclusions of This Chapter)

5 基于覆盖难度选择目标路径的测试数据进化生成3

5.1 研究背景(Backgrounds of Research)

5.2 路径覆盖难度度量(Measuring the Complexity of Covering a Path)

5.3 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

5.4 基于遗传算法的测试数据生成(Test Data Generation Based

5.5 在并行程序测试中的应用(Applications in Testing Parallel

5.6 本章小结(Conclusions of This Chapter)

6 多路径覆盖测试数据进化生成4

6.1 研究背景(Backgrounds of Research)

6.2 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

6.3 基于遗传算法的测试数据生成(Test Data Generation Based on the Genetic Algorithm)

6.4 在并行程序测试中的应用(Applications in Testing Parallel Programs)

6.5 本章小结(Conclusions of This Chapter)

7 串行程序很多路径覆盖测试数据并行进化生成的目标路径分组5

7.1 研究背景(Backgrounds of Research)

7.2 基本概念(Basic Concepts)

7.3 目标路径分组(Grouping Target Paths)

7.4 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

7.5 基于并行遗传算法的测试数据生成( Test Data Generation Based on the Parallel Genetic Algorithm)

7.6 性能分析(Performance Analysis)

7.7 在基准程序和工业用例测试中的应用( Applications in Testing Benchmark and Industrial Programs)

7.8 本章小结(Conclusions of This Chapter)

8 基于分组的很多路径覆盖测试数据进化生成6

8.1 研究背景(Backgrounds of Research)

8.2 目标路径分组(Grouping Target Paths)

8.3 测试数据生成问题的数学模型( Mathematical Model of Generating Test Data)

8.4 基于并行遗传算法的测试数据生成( Test Data Generation Based on the Parallel Genetic Algorithm)

8.5 在并行程序测试中的应用(Applications in Testing Parallel Programs)

8.6 本章小结(Conclusions of This Chapter)

9 结论

9.1 本文工作(Achievements of This Dissertation)

9.2 需要进一步解决的问题(Issues to be Further Addressed)

参考文献

附录1

附录2

作者简历

学位论文数据集

展开▼

摘要

随着并行计算技术的发展,越来越多的大规模高精度的科学问题,如图像处理、生物信息、分子动力学模拟,以及天气预报等,可以通过并行程序得到有效解决。并行程序的多个进程并行执行,进程之间通过共享存储或者消息传递的方式进行交互,协同完成计算任务。与串行程序相比,并行程序更加复杂,可靠性要求更高,这意味着并行程序的测试尤为关键。已有学者提出了多种方法,着重测试并行程序进程之间的交互序列,检测死锁、资源冲突和数据竞争等问题。在正确通信的前提下,为了测试程序的其他内部细节,有必要研究并行程序的结构覆盖,以进一步提高并行程序的可靠性。而结构覆盖的关键是使用有效的理论和方法,生成满足一定准则的测试数据。在软件测试领域,尽管遗传算法已经成为一种生成测试数据的重要方法,但是,已有工作主要面向串行程序。本文针对路径覆盖问题,研究消息传递并行程序测试数据进化生成理论及其应用。
  首先,研究了用于路径覆盖测试数据生成的协同进化解决方案。针对一类确定执行的并行程序,建立测试数据生成问题的数学模型;根据某一进程路径与程序输入的相关性,提出一种新的协同进化遗传算法。该方法中,包含多个子种群和一个合作团体群,每个子种群用来优化与某一进程路径相关的输入分量,基于这些种群的优良个体,合作团体群优化所有的输入分量。通过多个子种群与合作团体群的交替协同进化,求解上述优化模型,进而高效生成期望的测试数据,同时也为协同进化方法在软件测试中的应用提供新的思路。
  其次,考虑程序执行过程的不确定性,研究了并行程序单路径覆盖测试数据进化生成方法。当程序中使用一些不确定的通信语句时,由于任务划分、进程调度和网络延迟等原因,并行程序的执行过程也具有的一定的不确定性,这给并行程序的测试数据生成带来很大挑战。对于此类程序,为了降低不确定性执行给测试数据生成带来的影响,定义目标路径的等价路径,并给出判定方法,基于目标路径及其等价路径,建立有针对性的测试数据生成问题的数学模型,并采用遗传算法求解该模型。为不确定执行并行程序的测试数据生成问题,提供合理的解决途径。为了减少测试数据生成过程中的计算量,进一步提出了一种基于覆盖难度选择待覆盖路径的测试数据进化生成方法。该方法首先通过影响路径执行的变量、路径关键条件的复杂度,以及Halstead测度等,在目标路径和等价路径中,选择待覆盖路径,以降低路径覆盖的难度;然后,采用遗传算法生成覆盖相应路径的测试数据,以提高测试数据生成的效率。
  再次,为了有效解决多路径覆盖问题,研究了多路径覆盖测试数据进化生成方法。建立多路径覆盖测试数据生成问题的数学模型,并提出有针对性的进化求解方案。首先,基于每条给定路径及其等价路径,将多路径覆盖测试数据生成问题建模为一个包含多个目标的优化问题,每一个目标与一条目标路径及其等价路径相关;然后,设计评价个体的适应度函数,提出采用遗传算法求解该模型的方法。在测试数据生成过程中,同时考虑所有的目标路径和等价路径,使得一次运行遗传算法生成所有期望的测试数据。
  最后,针对很多路径覆盖的测试数据生成问题,研究了基于路径分组的多种群进化求解方案。该方法高效生成测试数据的前提是对目标路径合理分组。为此,首先,研究了用于串行程序很多路径覆盖测试数据并行生成的目标路径分组问题,提出一种新的目标路径分组方法。该方法根据可以利用的计算资源和路径相似程度,将待覆盖的目标路径分成若干组,使得不同组包含的目标路径条数相差很小,且属于同一组的目标路径具有很大的相似程度。以此为基础的测试数据并行生成方法能够充分利用并行计算资源,改进测试数据的生成效率。然后,在该分组方法的基础上,考虑并行程序多进程并行执行的特性,根据计算资源和程序包含的进程数两个因素,确定路径的分组数和每组包含的路径数,综合考虑程序所有进程路径的相似度,将目标路径进行分组。基于每一组路径,建立很多路径覆盖测试数据生成问题的数学模型,并采用多种群遗传算法进行求解,进一步提高了测试数据的生成效率。
  本文的研究工作在一定程度上,丰富了并行程序测试理论,大大提高了测试数据的生成效率,拓宽了进化算法的应用范围,具有重要的理论意义和应用价值。

著录项

相似文献

  • 中文文献
  • 外文文献
  • 专利
代理获取

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号