一種基于狀態(tài)圖類測(cè)試用例的轉(zhuǎn)換算法

吳靜莉 李素娟

摘要：在面對(duì)復(fù)雜的系統(tǒng)時(shí)，EFSM模型在語法上的欠缺，非層次結(jié)構(gòu)會(huì)導(dǎo)致狀態(tài)爆炸。針對(duì)EFSM中存在的狀態(tài)遷移不確定性問題進(jìn)行改進(jìn)，對(duì)狀態(tài)圖中存在的超態(tài)結(jié)構(gòu)，提出一種轉(zhuǎn)化方法來消除狀態(tài)圖中的層次和并發(fā)狀態(tài)，將其轉(zhuǎn)化為EFSM后，用基于擴(kuò)展有限狀態(tài)機(jī)的測(cè)試用例生成方法來生成系統(tǒng)的測(cè)試用例。

關(guān)鍵詞：測(cè)試用例；EFSM；狀態(tài)圖

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）25-0168-02

A Transformation Algorithm for Test Case Based on State Diagram

WU Jing-li， LI Su-juan

（Electronic Informational Engineering College， Hebi Polytechnic， Hebi 458030， China）

Abstract：In the face of complex systems， the EFSM model is deficient in grammar， and the non hierarchy can lead to the state explosion. In view of the problem of the existence of the state transfer in EFSM， the super state structure is proposed to eliminate the hierarchical and concurrent state of the state diagram. The test case of the system is transformed into EFSM.

Key words： test case； Extended Finite State Machine； statechart diagram

面向?qū)ο蟮能浖y(cè)試是目前研究的重點(diǎn)，其主要研究方向包括基于規(guī)約的測(cè)試，文獻(xiàn)[1]中總結(jié)了各種基于規(guī)約的測(cè)試方法，目前最廣泛應(yīng)用的基于狀態(tài)的測(cè)試是以擴(kuò)展有限狀態(tài)機(jī)（EFSM）為基礎(chǔ)的測(cè)試。在面對(duì)復(fù)雜的系統(tǒng)時(shí)，EFSM模型在語法上對(duì)層次結(jié)構(gòu)的不支持，狀態(tài)爆炸問題不可避免，雖然在物理結(jié)構(gòu)上對(duì)狀態(tài)空間進(jìn)行分解處理，但系統(tǒng)整體性受到影響。因此將超態(tài)概念引入到UML狀態(tài)圖中，解決了層次結(jié)構(gòu)問題，在面向?qū)ο蠼Ｖ幸驳玫搅藦V泛應(yīng)用。

本文針對(duì)狀態(tài)遷移不確定性問題進(jìn)行改進(jìn)，針對(duì)狀態(tài)圖中存在的超態(tài)結(jié)構(gòu)，提出一種轉(zhuǎn)化方法來消除狀態(tài)圖中的層次和并發(fā)狀態(tài)，將其轉(zhuǎn)化為EFSM后，用基于擴(kuò)展有限狀態(tài)機(jī)的測(cè)試用例生成方法來生成系統(tǒng)的測(cè)試用例。

1 有層次和并發(fā)狀態(tài)的UML狀態(tài)圖

UML狀態(tài)圖也稱為擴(kuò)展的有限狀態(tài)機(jī)，但UML狀態(tài)圖進(jìn)行了擴(kuò)展，并支持和時(shí)間有關(guān)的轉(zhuǎn)換。圖1是一有層次和并發(fā)結(jié)構(gòu)的UML狀態(tài)圖例子。其中S2是AND-狀態(tài)，S0、S3、S4是OR-狀態(tài)，其余為BASIC-狀態(tài)。t1是層內(nèi)遷移、t2是層間遷移。

2 狀態(tài)圖向擴(kuò)展有限狀態(tài)機(jī)的轉(zhuǎn)換

為了簡(jiǎn)化討論難度，設(shè)EFSM是一個(gè)三元結(jié)構(gòu){GStates，C0，GTrans}。GStates 是全局狀態(tài)（globe states ）的集合[3]，C0是全局狀態(tài)的初始狀態(tài)，GTrans是全局轉(zhuǎn)換路徑（globe transitions）的集合。如圖2所示的就是一個(gè)三元結(jié)構(gòu)的EFSM。

將UML狀態(tài)圖圖轉(zhuǎn)換為EFSM圖只需消除UML狀態(tài)圖的層次、并發(fā)和廣播消息。UML狀態(tài)圖將以以下方法轉(zhuǎn)換為EFSM（對(duì)應(yīng)將圖1轉(zhuǎn)換為圖2）。

2.1 生成EFSM的狀態(tài)

因?yàn)楦窬郑╟onfigurations）是同時(shí)運(yùn)行的最大狀態(tài)集，所以Gstates對(duì)應(yīng)的是UML狀態(tài)圖的格局（configurations）。

求全局狀態(tài)的步驟如下：

1）由狀態(tài)圖產(chǎn)生狀態(tài)樹（圖4）；

2）搜索UML狀態(tài)圖的所有狀態(tài)，找到根狀態(tài)root；

3）從根狀態(tài)開始進(jìn)行深度優(yōu)先搜索所有的狀態(tài)，如果狀態(tài)Si是葉子結(jié)點(diǎn)，則把該結(jié)點(diǎn)和其所有的父狀態(tài)一起作為一個(gè)全局狀態(tài)；

由圖1的UML狀態(tài)圖產(chǎn)生的EFSM中的五個(gè)全局狀態(tài)為：C1：S0，S1；C2：S0，S2，S3，S5，S4，S7；C3：S0，S2，S3，S6，S4，S7；C4：S0，S2，S3，S5，S4，S8；C5：S0，S2， S3，S6，S4，S8；

其中，產(chǎn)生狀態(tài)樹的步驟如下：

1）將狀態(tài)圖的根狀態(tài)作為狀態(tài)樹的根狀態(tài)root；

2）對(duì)狀態(tài)圖進(jìn)行廣度優(yōu)先搜索，將其子狀態(tài)作為root的孩子結(jié)點(diǎn)；

3）繼續(xù)對(duì)孩子結(jié)點(diǎn)進(jìn)行第二步操作，直到?jīng)]有孩子結(jié)點(diǎn)，即搜索到葉子結(jié)點(diǎn)。

由圖1中UML狀態(tài)圖產(chǎn)生的狀態(tài)樹如圖3 （圖4為改進(jìn)后的狀態(tài)樹）。

對(duì)狀態(tài)樹中的兄弟結(jié)點(diǎn)的關(guān)系進(jìn)行改進(jìn)：

a）如果在狀態(tài)樹中，兄弟之間是或狀態(tài)的關(guān)系，則不用改變。

b）如果在狀態(tài)樹中，兄弟之間是與狀態(tài)的關(guān)系，將其中一個(gè)兄弟和其所有的孩子結(jié)點(diǎn)作為另一個(gè)兄弟的所有葉子結(jié)點(diǎn)的孩子。

2.2 生成EFSM中的轉(zhuǎn)換

求全局轉(zhuǎn)換的路徑算法如下：

1）檢查根轉(zhuǎn)換，即檢查root到任一個(gè)全局狀態(tài)的葉子結(jié)點(diǎn)在原狀態(tài)圖中有沒有轉(zhuǎn)換，如果有則加入到全局轉(zhuǎn)換路徑中。

2）任取兩個(gè)全局狀態(tài)C1和C2。

3）依次搜索C1和C2中的葉子狀態(tài)有沒有自轉(zhuǎn)換，如果有作為全局狀態(tài)的自轉(zhuǎn)換。

4）搜索狀態(tài)圖中所有的轉(zhuǎn)換，得到以C1中的某個(gè)狀態(tài)為源狀態(tài)、C2中的某個(gè)狀態(tài)為目標(biāo)狀態(tài)的轉(zhuǎn)換，并且不是C2中的自轉(zhuǎn)換，這個(gè)轉(zhuǎn)換作為從C1到C2的全局轉(zhuǎn)換。

5）依次循環(huán)所有的全局狀態(tài)，直到搜索完所有的轉(zhuǎn)換為止。

在得到全局狀態(tài)和全局轉(zhuǎn)換之后，由UML狀態(tài)圖就生成了EFSM狀態(tài)轉(zhuǎn)換圖，即圖2所示的EFSM。

3 測(cè)試用例的生成

將UML狀態(tài)圖轉(zhuǎn)換成EFSM后，消除了層次和并發(fā)結(jié)構(gòu)。擴(kuò)展有限狀態(tài)機(jī)也可以看作是一種特殊的圖，狀態(tài)圖的測(cè)試?yán)碚摲椒芍苯討?yīng)用進(jìn)行測(cè)試，這樣類的輸入和狀態(tài)就實(shí)現(xiàn)了并行測(cè)試，如果產(chǎn)品可靠性發(fā)生改變，簡(jiǎn)單廣度搜索和深度搜索構(gòu)建出覆蓋標(biāo)準(zhǔn)，并產(chǎn)生測(cè)試用例。

通過數(shù)據(jù)定義和路徑標(biāo)識(shí)的EFSM圖可構(gòu)建基于數(shù)據(jù)流的測(cè)試案例，實(shí)現(xiàn)了數(shù)據(jù)流的測(cè)試。

4 結(jié)束語

文章實(shí)現(xiàn)并改進(jìn)了基于UML狀態(tài)圖在類測(cè)試用例的生成方法，對(duì)含有層次結(jié)構(gòu)和并發(fā)結(jié)構(gòu)的狀態(tài)圖，提出一種改進(jìn)思想，將不含父狀態(tài)的葉子結(jié)點(diǎn)作為新狀態(tài)，然后依據(jù)原狀態(tài)圖中的轉(zhuǎn)換來構(gòu)造新狀態(tài)之間的新轉(zhuǎn)換，得到擴(kuò)展有限狀態(tài)機(jī)，并采用基于EFSM的測(cè)試方法或基于狀態(tài)圖的測(cè)試用例生成方法來生成所需的測(cè)試用例。

參考文獻(xiàn)：

[1] Cavalli A R， Favereau J P， Phalippou M. Formal Methods in Conformance Testing： Result and Perspecrives[EB/OL].http：//snad.ncsl.gov/madvtg/Papers/iwpts93.pdf.

[2] Coga N， Comparing Tor X， Autolink. TVG and UIO Test Algorithms[M]. Springer-verlag Berlin Heidelberg. 2001.

[3] 張慶， 雷航. 一種基于UML狀態(tài)圖的面向?qū)ο箢惣?jí)測(cè)試模型[J]. 計(jì)算機(jī)工程， 2005， 21（31）： 76.

[4] 張毅坤. 基于UML狀態(tài)圖的類測(cè)試用例自動(dòng)生成方法[J]. 計(jì)算機(jī)工程， 2003， 21（29）： 76.

[5] 吳靜莉， 李素娟. 面向?qū)ο箢悳y(cè)試的精簡(jiǎn)EFSM轉(zhuǎn)換算法[J]. 電腦知識(shí)與技術(shù)， 2012（18）.