论文部分内容阅读
摘要：随着软件规模的扩大和复杂度的增加，如何实现高效的软件测试，成为决定软件测试效率的关键。Petri网作为一种适合于描述异步并发现象的系统模型，具有系统描述及强大的行为分析功能。本文通过对Petri网、可达树特点的分析的基础上，提出一种基于Petri网的软件测试路径生成方法，并将该方法用于等边三角形判定程序测试路径生成中，能够有效的生成测试路径并提高了软件测试的效率。
关键词：Petri网；可达树；测试路径生成
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）20-0026-03
Research on the Method of Test Path Generation Based on Petri Net
LI Zhu
（Chongqing Jiaotong University， Chongqing 400074， China）
Abstract： With the expansion of software scale and complexity of software， how to achieve high efficiency of software testing is the key to determine the efficiency of software testing. As a kind of system model which is suitable for describing asynchronous and concurrent phenomena， Petri net has the function of system description and powerful behavior analysis. Based on Petri nets and reachability tree analysis ，this paper proposed a software testing path generation method based on Petri net， and used the method for an equilateral triangle decision procedure test path generation， can effectively generate test paths and improve software test efficiency.
Keywords： Petri net ； reachability tree； test path generation.
1 概述
随着信息时代的到来，计算机软件得到广泛普及，人们对软件的需求越来越高，这也就导致软件的复杂度和规模越来越大。而如何对软件进行有效的测试就成为人们关注的焦点。
软件测试的关键一步就是软件测试路径的生成，目前已有很多测试路径的生成方法，作者本人曾将遗传算法用于测试用例的生成并进行了改进[1]；李鹏、彭祥伟等提出一种基于状态图的测试路径自动生成方法[2]，并可实现对路径的优化；赵磊、伦立军等提出一种基于软件体系结构的测试路径生成方法[3]，该方法在Wright语言的基础上，根据BG图构造基于覆盖准则的测试路径，生成测试数据。
然而，以上测试路径生成方法仍有一些不足：（1）路径生成方法过于复杂，不便于操作；（2）生成的路径存在循环路径，没有进行约束，导致工作量增加。
Petri网是Carl Adam Petri 在其论文“Kommunikation mit Automaten”中首次提出，是一种描述异步、并发计算机系统模型。Petri网既可采用数学表述方式，也可利用直观的图形表达方式，其丰富的系统描述手段和系统行为分析技术为计算机科学的部分学科的发展提供了坚实的理论基础。因此本文将Petri网用于测试路径的生成，并利用可达树进行论证，保证了测试路径生成的效率及效果。
2 Petri网及可达树概述
2.1 Petri网的定义[4]
Petri网是一种图形化的形式化语言表示法，它采用具有形式语义的图形语言，而图形化表示法便于理解，适合各种水平人员的使用，成为一种通用的形式化语言表达方法。下面给出Petri网的基本定义：
满足下列条件的三元组PN=（P，T，F）称为一个Petri网：
1）P为非空有限的库所组成的集合；
2）T为非空有限的变迁组成的集合；
3）[F?（P×T）?（T×P）]是库所、变迁的流关系；
4）[dom（F）?cod（F）=P?T]
其中：
[dom（F）=x∈P?T|?y∈P?T：（x，y）∈F] [cod（F）=x∈P?T|?y∈P?T：（y，x）∈F]
2.2 Petri网的可达树分析方法
之所以将Petri网用于测试路径的生成，很大原因是由于其具有丰富的图形表示及分析方法。Petri网分析方式包括进程网、状态方程及可达树等，此处我们采用可达树分析法实现对上述生成的Petri网的分析。
可达树分析法[5]是一种对Petri网图和其对应程序进行验证的重要方法，Petri网的可达树集合是指在使能情况下运行Petri网可到达的结点的集合。可达集由变迁点火产生的标记来描述可达树中的结点，弧标记变迁点火，从源结点开始，产生树中的每个新结点。下面给出产生可达树的Petri网结构图（图1）如下所示：
图4 三角形判定程序对应的Petri网图
由可达树的产生过程我们可以看出，新结点产生的过程是可以循环往复的，可能造成可达树是无穷的。因此，我们需要一种限制可达树规模的方法，我们约定：当一个结点没有变迁产生时（称为终止结点），不允许其产生新的结点；可达树中出现过的结点（称为重复结点），不考虑它的后续结点。
下面我们结合可达树生成方法及三角形判定程序生成的Petri网得到该程序的基于数据流的结点可达集，即程序测试路径，详见下表：
[路径产生标准＼
关键词：Petri网；可达树；测试路径生成
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2015）20-0026-03
Research on the Method of Test Path Generation Based on Petri Net
LI Zhu
（Chongqing Jiaotong University， Chongqing 400074， China）
Abstract： With the expansion of software scale and complexity of software， how to achieve high efficiency of software testing is the key to determine the efficiency of software testing. As a kind of system model which is suitable for describing asynchronous and concurrent phenomena， Petri net has the function of system description and powerful behavior analysis. Based on Petri nets and reachability tree analysis ，this paper proposed a software testing path generation method based on Petri net， and used the method for an equilateral triangle decision procedure test path generation， can effectively generate test paths and improve software test efficiency.
Keywords： Petri net ； reachability tree； test path generation.
1 概述
随着信息时代的到来，计算机软件得到广泛普及，人们对软件的需求越来越高，这也就导致软件的复杂度和规模越来越大。而如何对软件进行有效的测试就成为人们关注的焦点。
软件测试的关键一步就是软件测试路径的生成，目前已有很多测试路径的生成方法，作者本人曾将遗传算法用于测试用例的生成并进行了改进[1]；李鹏、彭祥伟等提出一种基于状态图的测试路径自动生成方法[2]，并可实现对路径的优化；赵磊、伦立军等提出一种基于软件体系结构的测试路径生成方法[3]，该方法在Wright语言的基础上，根据BG图构造基于覆盖准则的测试路径，生成测试数据。
然而，以上测试路径生成方法仍有一些不足：（1）路径生成方法过于复杂，不便于操作；（2）生成的路径存在循环路径，没有进行约束，导致工作量增加。
Petri网是Carl Adam Petri 在其论文“Kommunikation mit Automaten”中首次提出，是一种描述异步、并发计算机系统模型。Petri网既可采用数学表述方式，也可利用直观的图形表达方式，其丰富的系统描述手段和系统行为分析技术为计算机科学的部分学科的发展提供了坚实的理论基础。因此本文将Petri网用于测试路径的生成，并利用可达树进行论证，保证了测试路径生成的效率及效果。
2 Petri网及可达树概述
2.1 Petri网的定义[4]
Petri网是一种图形化的形式化语言表示法，它采用具有形式语义的图形语言，而图形化表示法便于理解，适合各种水平人员的使用，成为一种通用的形式化语言表达方法。下面给出Petri网的基本定义：
满足下列条件的三元组PN=（P，T，F）称为一个Petri网：
1）P为非空有限的库所组成的集合；
2）T为非空有限的变迁组成的集合；
3）[F?（P×T）?（T×P）]是库所、变迁的流关系；
4）[dom（F）?cod（F）=P?T]
其中：
[dom（F）=x∈P?T|?y∈P?T：（x，y）∈F] [cod（F）=x∈P?T|?y∈P?T：（y，x）∈F]
2.2 Petri网的可达树分析方法
之所以将Petri网用于测试路径的生成，很大原因是由于其具有丰富的图形表示及分析方法。Petri网分析方式包括进程网、状态方程及可达树等，此处我们采用可达树分析法实现对上述生成的Petri网的分析。
可达树分析法[5]是一种对Petri网图和其对应程序进行验证的重要方法，Petri网的可达树集合是指在使能情况下运行Petri网可到达的结点的集合。可达集由变迁点火产生的标记来描述可达树中的结点，弧标记变迁点火，从源结点开始，产生树中的每个新结点。下面给出产生可达树的Petri网结构图（图1）如下所示：
由可达树的产生过程我们可以看出，新结点产生的过程是可以循环往复的，可能造成可达树是无穷的。因此，我们需要一种限制可达树规模的方法，我们约定：当一个结点没有变迁产生时（称为终止结点），不允许其产生新的结点；可达树中出现过的结点（称为重复结点），不考虑它的后续结点。
下面我们结合可达树生成方法及三角形判定程序生成的Petri网得到该程序的基于数据流的结点可达集，即程序测试路径，详见下表：
[路径产生标准＼