基于Petri網(wǎng)的測(cè)試路徑生成方法研究

摘要：隨著軟件規(guī)模的擴(kuò)大和復(fù)雜度的增加，如何實(shí)現(xiàn)高效的軟件測(cè)試，成為決定軟件測(cè)試效率的關(guān)鍵。Petri網(wǎng)作為一種適合于描述異步并發(fā)現(xiàn)象的系統(tǒng)模型，具有系統(tǒng)描述及強(qiáng)大的行為分析功能。本文通過(guò)對(duì)Petri網(wǎng)、可達(dá)樹特點(diǎn)的分析的基礎(chǔ)上，提出一種基于Petri網(wǎng)的軟件測(cè)試路徑生成方法，并將該方法用于等邊三角形判定程序測(cè)試路徑生成中，能夠有效的生成測(cè)試路徑并提高了軟件測(cè)試的效率。

關(guān)鍵詞：Petri網(wǎng)；可達(dá)樹；測(cè)試路徑生成

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 概述

隨著信息時(shí)代的到來(lái)，計(jì)算機(jī)軟件得到廣泛普及，人們對(duì)軟件的需求越來(lái)越高，這也就導(dǎo)致軟件的復(fù)雜度和規(guī)模越來(lái)越大。而如何對(duì)軟件進(jìn)行有效的測(cè)試就成為人們關(guān)注的焦點(diǎn)。

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

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

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

2 Petri網(wǎng)及可達(dá)樹概述

2.1 Petri網(wǎng)的定義[4]

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

滿足下列條件的三元組PN=（P，T，F(xiàn)）稱為一個(gè)Petri網(wǎng)：

1）P為非空有限的庫(kù)所組成的集合；

2）T為非空有限的變遷組成的集合；

3）[F?（P×T）?（T×P）]是庫(kù)所、變遷的流關(guān)系；

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網(wǎng)的可達(dá)樹分析方法

之所以將Petri網(wǎng)用于測(cè)試路徑的生成，很大原因是由于其具有豐富的圖形表示及分析方法。Petri網(wǎng)分析方式包括進(jìn)程網(wǎng)、狀態(tài)方程及可達(dá)樹等，此處我們采用可達(dá)樹分析法實(shí)現(xiàn)對(duì)上述生成的Petri網(wǎng)的分析。

可達(dá)樹分析法[5]是一種對(duì)Petri網(wǎng)圖和其對(duì)應(yīng)程序進(jìn)行驗(yàn)證的重要方法，Petri網(wǎng)的可達(dá)樹集合是指在使能情況下運(yùn)行Petri網(wǎng)可到達(dá)的結(jié)點(diǎn)的集合?？蛇_(dá)集由變遷點(diǎn)火產(chǎn)生的標(biāo)記來(lái)描述可達(dá)樹中的結(jié)點(diǎn)，弧標(biāo)記變遷點(diǎn)火，從源結(jié)點(diǎn)開始，產(chǎn)生樹中的每個(gè)新結(jié)點(diǎn)。下面給出產(chǎn)生可達(dá)樹的Petri網(wǎng)結(jié)構(gòu)圖（圖1）如下所示：

圖1 產(chǎn)生可達(dá)樹的Petri網(wǎng)結(jié)構(gòu)圖

下面將該P(yáng)etri網(wǎng)的可達(dá)樹生成過(guò)程介紹如下：

當(dāng)t1、t2點(diǎn)火時(shí)，產(chǎn)生的可達(dá)樹如下所示。其中（1，0，0）作為源結(jié)點(diǎn)，在源結(jié)點(diǎn)t1點(diǎn)火，產(chǎn)生標(biāo)記（1，1，0），t2點(diǎn)火，產(chǎn)生標(biāo)記（0，1，1）（圖2）。接著新產(chǎn)生的標(biāo)記（1，1，0）分別針對(duì)t1、t2點(diǎn)火產(chǎn)生標(biāo)記（1，2，0）和（0，2，1）。以此類推，產(chǎn)生該P(yáng)etri網(wǎng)圖的所有的可達(dá)樹結(jié)點(diǎn)，效果圖（圖3）如所示：

圖2 初始點(diǎn)火狀態(tài)下的結(jié)點(diǎn)變化

圖3 Petri網(wǎng)產(chǎn)生的所有可達(dá)樹結(jié)點(diǎn)效果圖

3 基于Petri網(wǎng)的測(cè)試路徑生成

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

3.1 程序基本語(yǔ)句的Petri網(wǎng)描述[6]

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

1）順序語(yǔ)句的Petri網(wǎng)描述：

語(yǔ)句1；

語(yǔ)句2；

2）If-else語(yǔ)句的Petri網(wǎng)描述：

if（條件語(yǔ)句）

語(yǔ)句1；

else

語(yǔ)句2；

3）Switch語(yǔ)句的Petri網(wǎng)描述：

switch（跳轉(zhuǎn)語(yǔ)句）

{

case 1： 語(yǔ)句1；

case 2： 語(yǔ)句2；

…

case n： 語(yǔ)句n；

case n+1： 語(yǔ)句n+1；

}

4）for的Petri網(wǎng)描述：

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

{

語(yǔ)句1；

語(yǔ)句2；

}

3.2 基于Petri網(wǎng)的三角形判定程序測(cè)試路徑生成

為方便描述，下面給出三角形判定程序的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（"請(qǐng)輸入三角形的三個(gè)邊："）；

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ù)據(jù)有錯(cuò)誤，請(qǐng)輸入大于0的數(shù)！"）；}}}

對(duì)于以上的三角形判定程序?qū)嵤窃趯?duì)程序數(shù)據(jù)流及控制流分析的基礎(chǔ)上，描繪出該段程序的Petri網(wǎng)圖（如圖4所示）。下一步需要對(duì)該段程序的Petri網(wǎng)圖進(jìn)行分析得出其可達(dá)標(biāo)識(shí)集，再結(jié)合變遷的引發(fā)序列來(lái)表示每條路徑是否被測(cè)試到，即得到該段測(cè)試程序的測(cè)試路徑集，最終完成整個(gè)軟件的測(cè)試。

圖4 三角形判定程序?qū)?yīng)的Petri網(wǎng)圖

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

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

[路徑產(chǎn)生標(biāo)準(zhǔn)＼&產(chǎn)生的路徑（測(cè)試路徑）＼&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)往復(fù)以上路徑，因設(shè)定終止條件，可完成路徑的全覆蓋＼&]

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 李柱，丁曉明.用于測(cè)試用例生成的遺傳算法改進(jìn)[J].科學(xué)技術(shù)與工程， 2011，11（5）：990-991.

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

[3] 趙磊，倫立軍.基于軟件體系結(jié)構(gòu)的測(cè)試路徑生成方法[J].微電子學(xué)與計(jì)算機(jī)， 2008，25（1）：177-180.

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

[5] 翟長(zhǎng)勇.基于Petri網(wǎng)的Web應(yīng)用軟件測(cè)試技術(shù)研究[D].貴州大學(xué)，2011：14-17.

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