摘要：隨著軟件規(guī)模的擴大和復雜度的增加，如何實現(xiàn)高效的軟件測試，成為決定軟件測試效率的關鍵。Petri網作為一種適合于描述異步并發(fā)現(xiàn)象的系統(tǒng)模型，具有系統(tǒng)描述及強大的行為分析功能。本文通過對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 概述

隨著信息時代的到來，計算機軟件得到廣泛普及，人們對軟件的需求越來越高，這也就導致軟件的復雜度和規(guī)模越來越大。而如何對軟件進行有效的測試就成為人們關注的焦點。

軟件測試的關鍵一步就是軟件測試路徑的生成，目前已有很多測試路徑的生成方法，作者本人曾將遺傳算法用于測試用例的生成并進行了改進[1]；李鵬、彭祥偉等提出一種基于狀態(tài)圖的測試路徑自動生成方法[2]，并可實現(xiàn)對路徑的優(yōu)化；趙磊、倫立軍等提出一種基于軟件體系結構的測試路徑生成方法[3]，該方法在Wright語言的基礎上，根據BG圖構造基于覆蓋準則的測試路徑，生成測試數(shù)據。

然而，以上測試路徑生成方法仍有一些不足：（1）路徑生成方法過于復雜，不便于操作；（2）生成的路徑存在循環(huán)路徑，沒有進行約束，導致工作量增加。

Petri網是Carl Adam Petri 在其論文“Kommunikation mit Automaten”中首次提出，是一種描述異步、并發(fā)計算機系統(tǒng)模型。Petri網既可采用數(shù)學表述方式，也可利用直觀的圖形表達方式，其豐富的系統(tǒng)描述手段和系統(tǒng)行為分析技術為計算機科學的部分學科的發(fā)展提供了堅實的理論基礎。因此本文將Petri網用于測試路徑的生成，并利用可達樹進行論證，保證了測試路徑生成的效率及效果。

2 Petri網及可達樹概述

2.1 Petri網的定義[4]

Petri網是一種圖形化的形式化語言表示法，它采用具有形式語義的圖形語言，而圖形化表示法便于理解，適合各種水平人員的使用，成為一種通用的形式化語言表達方法。下面給出Petri網的基本定義：

滿足下列條件的三元組PN=（P，T，F(xiàn)）稱為一個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網分析方式包括進程網、狀態(tài)方程及可達樹等，此處我們采用可達樹分析法實現(xiàn)對上述生成的Petri網的分析。

可達樹分析法[5]是一種對Petri網圖和其對應程序進行驗證的重要方法，Petri網的可達樹集合是指在使能情況下運行Petri網可到達的結點的集合。可達集由變遷點火產生的標記來描述可達樹中的結點，弧標記變遷點火，從源結點開始，產生樹中的每個新結點。下面給出產生可達樹的Petri網結構圖（圖1）如下所示：

圖1 產生可達樹的Petri網結構圖

下面將該Petri網的可達樹生成過程介紹如下：

當t1、t2點火時，產生的可達樹如下所示。其中（1，0，0）作為源結點，在源結點t1點火，產生標記（1，1，0），t2點火，產生標記（0，1，1）（圖2）。接著新產生的標記（1，1，0）分別針對t1、t2點火產生標記（1，2，0）和（0，2，1）。以此類推，產生該Petri網圖的所有的可達樹結點，效果圖（圖3）如所示：

圖2 初始點火狀態(tài)下的結點變化

圖3 Petri網產生的所有可達樹結點效果圖

3 基于Petri網的測試路徑生成

軟件測試的定義各種各樣，但簡而言之，軟件測試即貫穿于整個軟件開發(fā)生命周期中的對軟件進行分析、設計、程序驗證（verifiCation）和確認（validation）的活動過程，其目的是通過發(fā)現(xiàn)軟件的缺陷和錯誤，以提高軟件的質量并驗證軟件的質量滿足用戶的需求的程度。

3.1 程序基本語句的Petri網描述[6]

軟件測試成敗的關鍵就是測試路徑的生成，鑒于Petri網在異步并發(fā)及形式化描述方面的優(yōu)勢，很多專家學者將其應用于軟件測試路徑的生成?；赑etri網的測試路徑生成，首先需要將被測程序轉化為其對應的Petri網圖。為便于描述，下面利用Petri模擬工具PIPE2.5將軟件程序常用基本語言及其Petri網描述如下：

1）順序語句的Petri網描述：

語句1；

語句2；

2）If-else語句的Petri網描述：

if（條件語句）

語句1；

else

語句2；

3）Switch語句的Petri網描述：

switch（跳轉語句）

{

case 1： 語句1；

case 2： 語句2；

…

case n： 語句n；

case n+1： 語句n+1；

}

4）for的Petri網描述：

for（初始語句；循環(huán)語句；結束語句）

{

語句1；

語句2；

}

3.2 基于Petri網的三角形判定程序測試路徑生成

為方便描述，下面給出三角形判定程序的Java程序代碼，如下所示：

import java.util.Scanner；

public class SanJiao{

public static void main（String[] args） {

int n=100；

for（int i=1；i

Scanner sc=new Scanner（System.in）；

System.out.println（"請輸入三角形的三個邊："）；

double a=sc.nextDouble（）；

double b=sc.nextDouble（）；

double c=sc.nextDouble（）；

if（a>0&&b>0&&c>0）{

if（（a+b<=c）||（a+c<=b）||（b+c<=a））{

System.out.println（"這不是三角形！"）；

}else if（a==b && b==c）{

System.out.println（"這是等邊三角形！"）；

}else if（a==b||b==c||a==c）{

System.out.println（"這是等腰三角形！"）；

}else if（a*a==b*b+c*c || b*b==a*a+c*c || c*c==a*a+b*b）{

System.out.println（"這是直角三角形！"）； }

else System.out.println（"這是一般三角形！"）；

}else System.out.println（"輸入數(shù)據有錯誤，請輸入大于0的數(shù)！"）；}}}

對于以上的三角形判定程序實是在對程序數(shù)據流及控制流分析的基礎上，描繪出該段程序的Petri網圖（如圖4所示）。下一步需要對該段程序的Petri網圖進行分析得出其可達標識集，再結合變遷的引發(fā)序列來表示每條路徑是否被測試到，即得到該段測試程序的測試路徑集，最終完成整個軟件的測試。

圖4 三角形判定程序對應的Petri網圖

由可達樹的產生過程我們可以看出，新結點產生的過程是可以循環(huán)往復的，可能造成可達樹是無窮的。因此，我們需要一種限制可達樹規(guī)模的方法，我們約定：當一個結點沒有變遷產生時（稱為終止結點），不允許其產生新的結點；可達樹中出現(xiàn)過的結點（稱為重復結點），不考慮它的后續(xù)結點。

下面我們結合可達樹生成方法及三角形判定程序生成的Petri網得到該程序的基于數(shù)據流的結點可達集，即程序測試路徑，詳見下表：

[路徑產生標準＼&產生的路徑（測試路徑）＼&Petri-all-path（路徑全覆蓋）路徑1＼&p0--t0--p1--t1--p2-- t2--p7 ＼&Petri-all-path（路徑全覆蓋）路徑2＼&p0-- t0--p1--t1--p2--t3--p4--t4--p7＼&Petri-all-path（路徑全覆蓋）路徑3＼&p0--t0--p1-- t1--p2--t3--p4--t5--p6--t6--p7＼&Petri-all-path（路徑全覆蓋）路徑4＼&p0--t0--p1--t1--p2--t3--p4--t5--p6--t7--p8--t7--p7＼&Petri-all-path（路徑全覆蓋）路徑5＼&p0--t0--p1--t1--p2--t3--p4--t5--p6--t7--p8--t9--p10--t10--p7＼&…＼&＼&Petri-all-path（路徑全覆蓋）路徑n＼&循環(huán)往復以上路徑，因設定終止條件，可完成路徑的全覆蓋＼&]

至此，我們完成了三角形判定程序所有測試路徑的覆蓋，而以上路徑則能夠完成程序的完全覆蓋，達到程序測試的目的，其他程序的測試均可采用此方法進行路徑覆蓋。

4 結束語

本文將Petri網用于軟件測試程序路徑的生成中，將被測程序進行分析得出其Petri網圖，然后利用可達樹分析法，對Petri網圖中存在的路徑進行分析提取，實現(xiàn)對被測程序路徑的完全覆蓋，最終得到測試路徑。

參考文獻：

[1] 李柱，丁曉明.用于測試用例生成的遺傳算法改進[J].科學技術與工程， 2011，11（5）：990-991.

[2] 李鵬，彭祥偉，周喜，等.基于狀態(tài)圖的測試路徑自動生成 [J].計算機工程，2011，37（2）：25-26.

[3] 趙磊，倫立軍.基于軟件體系結構的測試路徑生成方法[J].微電子學與計算機， 2008，25（1）：177-180.

[4] 霍敏霞.基于Petri網的并發(fā)程序測試路徑生成[D].西南大學，2012：7-8.

[5] 翟長勇.基于Petri網的Web應用軟件測試技術研究[D].貴州大學，2011：14-17.

[6] 鄭艷艷.基于Petri網的模型的GUI軟件測試用例生成研究 [D].華中師范大學，2010：17-19.