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

发布时间：2018-03-10 00:19

本文选题：并行软件　切入点：着色Petri网　出处：《内蒙古大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着软件产业的飞速发展,并行软件系统己经成为当下主流的一种软件系统,在人们生活生产中扮演越来越重要的角色。例如常见的云计算软件、网络软件等软件系统都具有并行行为的特点。而作为保证软件质量的关键环节,软件测试则起着关键作用。然而,并行软件由于其并行特点容易导致状态空间爆炸,传统测试方法大多针对状态空间完成测试序列生成,状态爆炸时无法进行高效的软件测试,通常存在着低覆盖率、高冗余率、低测试效率等问题。通过模型化简缩减状态空间的方法可以有效降低并行软件测试的复杂度,保证化简后模型测试效果不变是化简方法研究中的关键问题。目前针对软件测试的模型化简方法主要是基于迹等价的化简,此类方法并不能够降低并发执行的复杂度,所以化简效果有限。本文围绕待测行为及其相关行为进行并行软件模型化简,针对与待测行为无关的分支进行串行化处理以及限制处理,从而实现缩减状态空间的目的,使得化简前后关于待测行为的测试效果不变。本文关于化简方法做了以下几个方面的工作:(1)针对复杂并行软件模型,引入待测行为及相关行为等概念,以待测行为来描述本次测试的目的,以相关行为来描述与本次测试数据流相关的行为。在模型的化简过程中,本方法仅仅对与本次测试无关的非待测行为进行化简,因此不仅保证了本方法的正确性,而且缩减了状态空间规模,从而提升了测试的效率。(2)本文提出了同源分支的概念,将同源分支划分为并发分支组或选择分支集,在并发分支组或选择分支集内部进行化简操作。由于一个并发分支组或选择分支集中的全部分支都来自于同一源节点,同源性保证了无关分支串行化处理和限制处理对于待测相关行为的测试不受影响。(3)在一个并发分支组或选择分支集内部,依据支路存在待测行为和相关行为的情况,采用添加抑制弧的方式,完成待测行为无关分支的串行化操作和限制处理。通过抑制弧的方式没有修改任何模型元素,只是限制了并发顺序及部分无关分支限制处理,保证了化简后模型的正确性。并发分支的串行化和选择分支的限制处理可以大幅缩减状态空间,被串行化和限制处理的分支不含有待测行为或相关行为,所以对本次待测行为的测试效果不变。最后,文章对化简算法的正确性进行了证明,并通过应用实例分析,验证了本方法的正确性以及对待测软件模型状态空间的缩减效果。
[Abstract]:With the rapid development of software industry, parallel software system has become a mainstream software system, playing a more and more important role in people's daily production, such as common cloud computing software, Network software and other software systems all have the characteristics of parallel behavior. As a key link to guarantee software quality, software testing plays a key role. However, parallel software can easily lead to state space explosion because of its parallelism. Most of the traditional test methods are based on the state space to complete the test sequence generation, state explosion can not carry out efficient software testing, usually there is a low coverage rate, high redundancy rate. The complexity of parallel software testing can be effectively reduced by reducing the state space by model simplification. It is a key problem in the research of simplification method to ensure that the effect of model test is unchanged after simplification. At present, the modeling simplification method for software testing is mainly based on trace equivalence reduction, and this kind of method can not reduce the complexity of concurrent execution. Therefore, the effect of simplification is limited. In this paper, parallel software modeling is carried out around the behavior to be tested and related behaviors, and serialization and restriction processing are carried out for the branches independent of the behavior to be tested, so as to achieve the purpose of reducing the state space. In this paper, we do the following work on the simplification method: 1) for the complex parallel software model, we introduce the concepts of the behavior to be tested and the related behavior. The purpose of the test is described by the behavior to be tested, and the behavior related to the data flow is described by the related behavior. In the process of simplification of the model, the method only simplifies the untested behavior which is independent of this test. Therefore, not only the correctness of this method is guaranteed, but also the scale of state space is reduced, thus the efficiency of testing is improved. In this paper, the concept of homology branch is proposed, which is divided into concurrent branch group or select branch set. Simplify within a concurrent branch group or select branch set. Because all the branches of a concurrent branch group or selected branch set come from the same source node, Homology ensures that independent branching serialization and restriction processing are not affected for testing related behaviors to be tested) within a concurrent branch group or selected branch set, depending on the existence of untested behavior and related behavior in the branch. By adding suppression arcs, the serialization operation and restriction processing of the non-branching of the behavior to be tested is completed. No model elements are modified by the suppression arc, but the concurrency order and the partially independent branch restriction processing are restricted. The serialization of concurrent branches and the limited processing of selecting branches can greatly reduce the state space, and the branches of serialization and restriction processing do not contain untested or related behaviors. Finally, the correctness of the simplification algorithm is proved, and the validity of the method and the reduction effect of the test software model state space are verified by an application example.
【学位授予单位】：内蒙古大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.53

【参考文献】