面向?qū)ο箢悳y試的精簡EFSM轉(zhuǎn)換算法

吳靜莉 李素娟

摘要: EFSM是一個沒有層次和并發(fā)結(jié)構(gòu)的狀態(tài)圖，因此很難處理較復雜的軟件系統(tǒng)，而且由于EFSM中存在前置條件，使得生成的測試序列有可能存在不可達性。該文提出一種將EFSM轉(zhuǎn)化為精簡有限狀態(tài)機（FSM）的轉(zhuǎn)換算法，很大程度上減少了中間產(chǎn)生的等價狀態(tài)，并有效防止了組合間爆炸問題的出現(xiàn)，得到的精簡FSM最小可達。

關(guān)鍵詞:狀態(tài)測試；擴展有限狀態(tài)機；有限狀態(tài)機；狀態(tài)圖；不可達路徑

中圖分類號：TP313文獻標識碼：A文章編號：1009-3044(2012)18-4490-02

An Transformed Algorithm of Simple EFSM in Object-oriented Class Testing

WU Jing-li,LI Su-juan

(Electronic Informational Engineering College, Hebi College of Vocation And Technology, Hebi 458030, China)

Abstract: Based on Extended Finite State Machine (EFSM) is a variety of state testing the theoretical basis of the test method. By the ex? tended finite state machine definition.Internal state variables caused by the migration of uncertainty is based on the EFSM test difficulty.It is necessary to eliminate this uncertainty. Starting from any one state makes changes in the internal environment variables are not subject to the constraints.This paper presents a transformed arithmetic from EFSM to simple FSM. Reducing the equivalence states and avoiding effec? tively combined explosion problem. As a result, minimal reachable graph of FSM can be gained. This makes sure the EFSM converted into changes determined EFSM.

Key words: statement testing; extended finite state machine; finite state machine; statechart diagrams; infeasible paths

目前,基于UML狀態(tài)圖的測試在類測試中得到廣泛應用。但是由于UML狀態(tài)圖中的狀態(tài)有層次和并發(fā)結(jié)構(gòu),再加上狀態(tài)之間的廣播通信機制,使得傳統(tǒng)的流分析測試技術(shù)不能直接得到應用。EFSM是一個沒有層次和并發(fā)結(jié)構(gòu)的狀態(tài)圖，因此可以先將UML狀態(tài)圖轉(zhuǎn)化為擴展有限狀態(tài)機（EFSM），消除狀態(tài)圖中狀態(tài)的層次和并發(fā)結(jié)構(gòu)與狀態(tài)之間的廣播通信機制,

再通過傳統(tǒng)的類測試方法對類進行測試?；贓FSM測試是各種基于狀態(tài)測試方法的理論基礎(chǔ)，在文獻[1]中Chourouk Bourh? fir系統(tǒng)地講述了基于EFSM測試的理論基礎(chǔ)和各種測試方法。在文獻[2]中N.Coga從理論上比較了最常用的四種測試用例生成算法的故障提示能力和效率。

EFSM是有限狀態(tài)機(FSM)的一個擴展，它在FSM的基礎(chǔ)上增加了變量、操作以及狀態(tài)移的并置條件，所以從EFSM產(chǎn)生的測試序列有可能存在不可達路徑[3]。文獻[3，4]對這個問題進行了相關(guān)的研究，并提出了解決的算法。該文通過對EFSM的研究，提出一種將EFSM轉(zhuǎn)化為精簡FSM的算法。通過將謂詞約束的配置分裂，使轉(zhuǎn)化過程中產(chǎn)生的等價狀態(tài)大大減少，剔除了可能造成組合空間爆炸的無用狀態(tài)，使得到的精減FSM最小可達。

圖2

模型中，以Name: Predicate/Action來標記每一條變遷，其中Predicate為空者表示變遷謂詞約束為永真（True），Action為空者表示變遷對起始狀態(tài)的變量值無影響。圖中共有3個狀態(tài)；3個變量:布爾變量有2個，整形變量P有8個，整形變量R有8個；

若按配置枚舉的方法進行可達性分析，將得到3*（2*8*8）=384個狀態(tài)（192個可達）。顯然，這個數(shù)目相對于我們的處理能力有些過大，得到的等效FSM包含了過多的狀態(tài)，給最簡化和檢測序列都帶來了麻煩。

當EFSM模型應用于比較復雜的系統(tǒng)時，因為其本身在語法上不支持層次結(jié)構(gòu)，常常面臨狀態(tài)爆炸的問題。而UML的狀態(tài)圖引入超態(tài)的概念以支持層次結(jié)構(gòu)解決了這個問題，在面向?qū)ο笙到y(tǒng)的建模中得到了廣泛的應用。

在基于EFSM的測試中，把EFSM對應的程序?qū)崿F(xiàn)看作是一個黑盒子而不考慮程序內(nèi)部的細節(jié)。在基于EFSM的測試序列的生成過程中，測試序列的可執(zhí)行性是一個重要問題，因為直接采用基于FSM模型生成測試序列，可能會遇到不可執(zhí)行的情況。

對于一個EFSM來說，如果相關(guān)變量都有有限數(shù)量的取值或者有限數(shù)量的取值域，那么此EFSM的構(gòu)造數(shù)量是有限的。我們可以將EFSM中的配置看作普通FSM中的狀態(tài)，通過這樣的替代，就可以將EFSM轉(zhuǎn)化為普通的FSM。這樣，測試用EFSM模型描述的系統(tǒng)的問題就轉(zhuǎn)化為尋找等價FSM的問題。

由此也可以看出EFSM中狀態(tài)分組有很大的不穩(wěn)定因素。如圖1所示：

圖3

此時我們可以把EFSM的一個配置看作對應的等效FSM的一個狀態(tài)。

在進行了EFSM至等效FSM的轉(zhuǎn)換后，建立系統(tǒng)的測試用例集就可以應用FSM生成測試用例的方法來生成測試序列。但是由于類的封裝性和類狀態(tài)的復雜性，一個類對相同的輸入可以有不同的反應。而且狀態(tài)轉(zhuǎn)換的條件也不只決定于輸入，還可能取決于內(nèi)存變量的謂詞約束。該文中的方法如果進行配置組分裂時將可達性分析結(jié)合一起進行，則算法會更加有效。

[1] Bourhfir C,Dssouli R,Aboulhamid E M.Automatic Test Generation for EFSM_based Systems. http://citeseer.nj.nec.com.

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

[3] Hierons Rm,Kim Th,Ural H.Expanding an Extended Finite State Machine to aid Test ability [A].Proceedings of the 26thAnnual Interna? tional Computer Software and Applications Conference(COMPSACp02)[C].IEEE Computer Society Press,2002.

[4] Duale Ay,Uyar Mu.A Method Enabling Feasible Conformance Test Sequence Generation for EFSMModels[J].IEEE Transactions on Computers,2004,53(5):614-627.

[5]尚冬娟,郝克剛,葛瑋,等.軟件測試中的測試用例及復用研究[J].計算機技術(shù)與發(fā)展,2006,16(1).

[6]熊利,周寬久.基于使用模型的嵌入式軟件測試用例生成研究[J].計算機技術(shù)與發(fā)展,2010,20(5).

[7]李楊,張春海,張美玲.基于UML的回歸測試軟件測試方法的研究與應用[J].計算機技術(shù)與發(fā)展, 2010,20(9).