针对并行待测行为测试的CPN模型化简方法

摘要

随着软件产业的飞速发展，并行软件系统已经成为当下主流的一种软件系统，在人们生活生产中扮演越来越重要的角色。例如常见的云计算软件、网络软件等软件系统都具有并行行为的特点。而作为保证软件质量的关键环节，软件测试则起着关键作用。然而，并行软件由于其并行特点容易导致状态空间爆炸，传统测试方法大多针对状态空间完成测试序列生成，状态爆炸时无法进行高效的软件测试，通常存在着低覆盖率、高冗余率、低测试效率等问题。通过模型化简缩减状态空间的方法可以有效降低并行软件测试的复杂度，保证化简后模型测试效果不变是化简方法研究中的关键问题。目前针对软件测试的模型化简方法主要是基于迹等价的化简，此类方法并不能够降低并发执行的复杂度，所以化简效果有限。本文围绕待测行为及其相关行为进行并行软件模型化简，针对与待测行为无关的分支进行串行化处理以及限制处理，从而实现缩减状态空间的目的，使得化简前后关于待测行为的测试效果不变。本文关于化简方法做了以下几个方面的工作:
　　(1)针对复杂并行软件模型，引入待测行为及相关行为等概念，以待测行为来描述本次测试的目的，以相关行为来描述与本次测试数据流相关的行为。在模型的化简过程中，本方法仅仅对与本次测试无关的非待测行为进行化简，因此不仅保证了本方法的正确性，而且缩减了状态空间规模，从而提升了测试的效率。
　　(2)本文提出了同源分支的概念，将同源分支划分为并发分支组或选择分支集，在并发分支组或选择分支集内部进行化简操作。由于一个并发分支组或选择分支集中的全部分支都来自于同一源节点，同源性保证了无关分支串行化处理和限制处理对于待测相关行为的测试不受影响。
　　(3)在一个并发分支组或选择分支集内部，依据支路存在待测行为和相关行为的情况，采用添加抑制弧的方式，完成待测行为无关分支的串行化操作和限制处理。通过抑制弧的方式没有修改任何模型元素，只是限制了并发顺序及部分无关分支限制处理，保证了化简后模型的正确性。并发分支的串行化和选择分支的限制处理可以大幅缩减状态空间，被串行化和限制处理的分支不含有待测行为或相关行为，所以对本次待测行为的测试效果不变。
　　最后，文章对化简算法的正确性进行了证明，并通过应用实例分析，验证了本方法的正确性以及对待测软件模型状态空间的缩减效果。

目录

声明

摘要

图表目录

第一章 绪论

1．1 论文研究背景与意义

1．2 论文研究目标与创新点

1．3 论文结构安排

第二章 相关研究介绍

2．1 并行软件测试技术研究现状

2．2 相关知识介绍

2．2．1 Petri网介绍

2．2．2 着色Petri网介绍

2．3 基于Petri网的软件测试及化简方法研究现状

2．4 论文研究问题

2．5 本章小结

第三章 针对待测行为的CPN模型化简算法预备知识

3．2．1 CPN扩展

3．2．2 模型相关定义

3．2．3 化简算法相关概念的定义

3．2．4 化简后模型分析的相关概念定义

3．3 本章小结

第四章 针对待测行为测试的TBoCPN模型化简算法

4．1 问题提出

4．2 针对待测行为的模型化简算法主要操作描述

4．3 针对待测行为的模型化简算法描述

4．4 针对模型化简算法证明

4．5 本章小结

第五章 模型化简方法应用及效果分析

5．1 算法应用

5．2 模型化简算法的化简效果分析

5．3 本章小结

第六章 总结与未来展望

6．1 总结

6．2 下一步工作

参考文献

致谢

预士期间发表论文