基于FSM的測試用例生成算法*

蔡 璐，朱怡安，鄭 煒

(西北工業大學計算機學院，西安 710072)

1 引言

隨著系統越來越復雜，通過建立被測系統的FSM模型進行一致性測試。人們主要研究方向之一是基于FSM測試用例的生成算法，W－方法［1］利用規格FSM的狀態特征集W和遷移覆蓋集P生成測試序列，然后將測試序列應用到實現FSM中進行結果比較。Wp－方法［2］主要由兩步構成，首先利用狀態特征集W產生能覆蓋所有狀態的序列，然后利用遷移覆蓋集P和部分狀態特征集Wi產生能覆蓋所有遷移的測試序列。顯然，如果FSM滿足狀態的可達性，則遷移覆蓋必然包含了狀態覆蓋，W－方法實質上就是生成遷移覆蓋的測試序列，而Wp－方法則是將遷移覆蓋分解為狀態覆蓋和對于各個狀態的剩余遷移覆蓋，這種做法讓測試集得以減小。文獻［4］不用計算所有的狀態特征集W，而只需要部分特征集R(前提是R能將待測的FSM劃分成特定數目的狀態集合)從而減少計算W的時間，改進了W－方法，但它只是W－方法一種通用的方法。C－ 方法［3］是基于 W － 方法［1］和 G － 方法［4］，對于組合狀態機和回歸測試此算法有明顯的優勢。它們都存在測試序列重置到初始態的次數過多的問題。

此文基于它們共同的故障模型，利用模型中部分狀態特征集，在與C－方法的組合思想相反面上，從分解的思想出發提出了DC－方法，能使得用例集相對減少，同時使得每次重置到初始態的次數減少，從而節省了時間。以下章節如下安排:第二節給出了相關的定義及條件假設;第三節提出了DC－方法及相關理論證明;第四節通過實例分析DC－方法相對其他方法所具備的優勢;最后是全文總結并討論了未來可進行研究的方向。

2 相關定義及條件假設

為了更好介紹基于FSM測試用例生成技術，這里先給出一些記號和形式化定義及必需的假設前提。

2.1 相關定義

定義1:按照文獻［3］對FSM的定義:一個自動機 M=(X，Y，S，s0，δ，λ)，其中，X 是一個有限的輸入字符集，Y是一個有限的輸出字符集，S是一個有限的狀態集，s0是一個初始狀態，s0∈S，δ:X×S→S狀態遷移的映射關系，λ:X×S→Y，控制輸出的映射。X*是輸入序列的集合。若 Si，Sj∈S，x∈X，若λ(x，Si)= λ(x，Sj)，則記為 Si|x=Sj|x，若δ(x，Si)=Sj，則記為 Si∧x=Sj。

定義2:兩個集合A，B，集合中元素的個數分別為|A|和|B|

(1)連接運算符“.”上的運算，A.B={αβ|α∈A，β∈B};

(2)兩個集合A，B的外連接運算符 “·”上的運算

若|A|＞ |B|，則 A·B={αβ|?β∈B，?唯一的α∈A}∪(A－B)，滿足|A·B|=|A|;

若|A|＜ =|B|，則 A·B={αβ|?α∈A，?多個β∈B}，滿足|A·B|=|B|;

即|A·B|=max{|A|，|B|};

(3)一個三元組 R ＜S，D，Quen＞，R.S屬性為起始狀態，R.D屬性表示中止狀態，R.Quen屬性表示字符序列能使得系統從起始態遷移到相應的中止態，則定義:

兩個這樣的三元組A，B的外連接運算符“?”上的運算，A?B={(A.Quen(i))·(B.Quen(j))|A.D(i)=B.S(j)，i，j為某行元組的行標記}

定義3:Wi是Si的一個特征集，當且僅當對于S中的每一個狀態Sj(i≠j)，存在一個輸入序列p∈Wi，使得 Sj|p≠Si|p，Wi是區分當前 Si和其他狀態的最小集合。其形式化表述為:

?Sj∈S，j≠i，?p∈Wi，Sj|p≠Si|p，?x∈X，q∈X*，p=qx，Sj|q=Si|q?Wi是 Si的一個特征集。

2.2 條件假設

S和I表示兩個FSMs，S通常代表一個參考規格狀態機，I代表一個實現。S為最小FSM，有n個狀態，W是S的特征集，S和I都是確定的和完全的有窮自動機，實現FSM的狀態數為m個。對輸入字母集合X，每個狀態對X中的每個的字母輸入都有相應的響應。故障模型與文獻［3］中相同。

3 相關理論證明及DC－方法

3.1 相關證明

自動生成測試用例集的方法必須具備兩個特點:能高效地用于測試，即越少的用例集，測試越快;另一方面，檢測到的故障越多越好［5］。因為C－方法應用范圍相對較小，這個部分將證明此文提出的DC－方法同G－方法(W－方法)、Wp－方法有同等的故障檢錯能力，在這個基礎上，能生成相對較少的用例集。假設，Z=X［m －n］.W，其中，X［k］={ε}∪X∪X2∪…∪Xk(k ＞ =0)，Xk=X.X….X，一共K個X進行連接運算，PA為遷移序列，從初始狀態S0出發到達剩余的各個不同狀態的最小的輸入序列集Q，每個狀態的分支上輸入集合P。

定理1:從初始狀態S0到達每個狀態的測試序列及從S0出發的每條遷移路徑的測試序列QUE1=Q.Z∪P0.Zi(Zi={p2}.Wj)，從其他狀態出發的遷移路徑的測試序列為QUE2=.Zi(簡寫為P.Zi)，測試集∏=QUE1?QUE2，則 S與 I等價?S和I是∏－等價

證明:由文獻［5］附錄中的定理:S與I等價?S和 I是 PA.Z －等價，則 PA=P∪P.X∪P.X2∪…∪P.Xk=P∪P.P∪P.P2∪…∪P.Pk=P∪P.P∪P2.P∪…∪Pk.P，因此 S 和 I是 P.Z － 等價，類推 Pk.P.Z－等價，其中k為狀態節點所在測試樹T的層數，若T的深度為h(一個節點時 h=1)，k＜h，k∈N。由文獻［1］附錄中的引理 A.4:Ik≈ZSi?Ik≈ZiSi，其中 Zi?Z，Zi={p2}.Wj)，Wj是狀態 Sj的特征集，δ(p2，Si)=Sj，當以 Si(Si≠S0)為初始狀態時，Ti=P.X［m －n］.Wj或 Ti=P.X［m －n］，因此，S 和 I是－ 等價.Zi－ 等價，從而 S 和 I是QUE2－等價。而從真正的初始態S0到達Si，則通過輸入序列，狀態覆蓋的測試序列為Q.Z，對S0的遷移覆蓋要達到完全，則需對每個輸入Xi∈P，若Xi?Q，則產生測試序列 Xi.Zi，P0={Xi|Xi∈P，但 Xi?Q}從而以S0、I0為初始態S和I，S和I是(QUE1?QUE2)－等價，即S和I是∏－等價。證畢。

下面的定理給出DC－方法相對其他方法(G－方法、Wp－方法)生成的用例集要少。

定理2:假設G－方法生成的測試集大小為πg，Wp－方法生成的測試集πp，DC－方法生成的測試集 π，有

證明:由文獻［4］可得，當 R=W 時，πg=PA.Z;由文獻［2］可得，πp=Q.Z∪(PA －Q).Zi;而由定理1，DC－方法生成的測試集 π=(Q.Z∪P0.Zi)?(P.Zi)，其中 P0?X，|P0|＜ |X|，S0 經過輸入Q.Z∪P0.Zi的子序列QUE0后回到S0的集合大小為|QUE0|，當 |(Q.Z∪P0.Zi)|－ |QUE0|＞(P.Zi)，則|π |=|(Q.Z∪P0.Zi)|，反之，|π |=|(P.Zi)|+|QUE0|，顯然|QUE0|≤|Q.Z∪P0.Zi|，(Q∪P0)?PA，Q∩P0=φ，則|PA|＞ |Q∪P0|，|PA －Q|＞ |P0|，因此

(1)當|π|=|(Q.Z∪P0.Zi)|時，有，

(2)當|π|=|(P.Zi)|+|QUE0|時，

證畢。

3.2 DC － 方法

該方法主要思想是依標記樹逐步分解狀態機，生成針對每個狀態的測試序列，最后組合每個階段的測試序列使其從初始態觸發，具體見算法1。其中S為從需求規格中抽象出來的參考FSM，I為一種實現FSM(見圖1)，目的是檢驗兩者的一致性。

一個企業的運營與管理合理與否，終究還是人起作用。企業中人力資源部門作為管理員工的專職部門，更要在企業的經濟管理中發揮出激勵員工的作用。這要求企業要進行人力資源培訓，培養人資部門員工的責任道德意識和管理能力，使他們積極主動的進行人力資源工作。企業在進行人力資源管理時，一定要按照員工的優勢以及自身意愿將其安排在最適當的位置，使人員分布合理，使人資部門結構嚴謹，這樣才便于讓不同崗位的員工發揮各自的作用。

圖1 規格FSM S

算法1.(DC－方法生成測試用例)

輸入:S，I，n，m

輸出:測試集П

步驟:

Step1，計算每個狀態的特征集Wi及它們的全集W，利用文獻［4］的Construction 3中的算法構造測試樹T;

Step2，遍歷樹T，樹高為ht，得出從初始狀態S0出發到達剩余的各個不同狀態的最小的輸入序列集Q和每個狀態分支上的輸入集合 P，特別的，P0={ε}∪P;

Step3，若 m=n，計算∏1=Q.W，否則，計算∏1=Q.X［m －n］.W。

Step4，寬度搜索測試樹T，對任一的Si∈S，初始時vist(Si)=0，對每個被訪問的節點Si=node(i)，

1)如果 vist(Si)=0，則將 vist(Si)=1，Ti= φ，對每個 x∈P，δ(x，Si)=Sj，分兩種情況:

i)若 vist(Sj)=1，則 Ti=Ti∪{x};

ii)若 vist(Sj)=0，則 Ti=Ti∪{x}.Wj;

如果vist(Si)=1，則表明之前已經驗證過從此節點出發的所有遷移，繼續往后搜索;

2)記錄Ti中每個序列pi的起始狀態Spi和終止態Dpi，

3)若 m ＞n，對?x∈P，Ti.x 能到達的狀態 Sj，進行i)和ii)的判定

i)若 vist(Sj)=1，則 Ti=Ti∪{x};

ii)若 vist(Sj)=0，則 Ti=Ti∪{x}.Wj;

重復此步驟(m－n)次;

4)若搜索的層次j=0，則T0與∏1的并集構造一個H0級的三元組＜S，D，Quen＞，記為 H(0);否則搜索完某一個層次j≠0時，將此層新增訪問的狀態(Sk，k∈1，2，3……)遷移覆蓋序列集 Hj=∪r=kTsk，從而構造出Hj級的三元組＜S，D，Quen＞，記為H(j);

5)重復步驟4，直到所有的狀態都已經訪問過;

Step5，計算測試序列集合∏=H(0)?H(1)?……?H(j)?……H(ht－1)。

4 實例

在許多實例中隨機選取了圖1所示的參考FSM，及圖2所示的相對應的一種實現FSM，分兩種情況討論上節提出的算法。

4.1 當實現FSM的狀態數m=n

針對圖1所示的參考FSM，得到圖3(a)的測試樹 T，且 W0={a}，W1={c}，W2={b}，W={{a}，{b}，{c}}，Q={ε，b，c}，P={a，b，c}，P0={ε，a，b，c}，ht=2，∏1=Q.W={a，b，c，b.a，b.b，b.c，c.a，c.b，c.c}。接著，對 S0，vist(S0)=1，P0 － Q={a}，T0=(P0 －Q).W1={a.c}，這樣 S0 出去的遷移覆蓋已經完全覆蓋，以后從其他狀態到S0后不必再與W0做連接運算。將T0∪∏1構造出H0層測試序列如表1所示的集合A，然后如圖3(b)和(c)，第二層，對 S1，置 vist(S1)=1，S1∧a=S0，S1∧b=S2，S1∧c=S1，所以 T1={a，b.b，c.c}。同理對S2，根據它到達的每個狀態是否之前已經訪問過，得出T2={a.b，b，c}。T1∪T2 構造出 H1 層的測試序列如表2所示的集合B，已經到達葉子節點，此時，A?B，得到最終的測試序列集合∏ ={ba，cb，aa，bbb，bccc，cc，ac，cab，bbb，cac}，得到期望的輸出是:ff、ee、ef、ffe、ffff、ee、ef、efe、ffe、efe 一共 10 個測試序列。Wp－方法將產生16個測試序列，W－方法將產生27個測試序列。隨著狀態機的規模變大，這種差異將更為明顯。

圖2 待測FSM I

圖3 測試樹T的逐層訪問

表1 H0層測試序列信息

表2 H1層測試序列信息

應用上面計算出的測試集到圖2所示的FSM中，得到相應的輸出:ff，ee、ff、ffe、ffff、ee、ff、eff、ffe、eff，與期望的輸出對比，可看出，第三個、第七個、第八個、第十個測試序列產生的結果有差異，從而檢測出I0到I1當輸入為a時的操作錯誤(第三個和第七個序列)和從I2在輸入為a時遷移到I1的遷移狀態錯誤(第八個和第十個序列)，相比文獻［4］的檢測遷移錯誤能力(對于其中的遷移狀態錯誤只有一個序列能檢測出來)，增強了發現錯誤的概率。

4.2 當實現FSM的狀態數m＞n

假設 m=4，依據圖 1，n=3，所以 m － n=1，在步驟3中，∏1=Q.X［1］.W，在步驟4 中，對于 S1，置 vist(S1)=1，S1∧a=S0，S1∧b=S2，S1∧c=S1，所以 T1={a，b.b，c.c}，對 T1.P={aa，ab，ac，bba，bbb，bbc，cca，ccb，ccc}，重復 1 次即可，最終求得T1={a，bb，cc，aac，abc，acb，bbac，bbbc，bbcb，cca，ccbb，cccc}，T2={ab，b，c，aba，abb，abcb，ba，bb，bcb，ca，cbb，cc}，最終得到的用例數為 29 個，且能檢測出文獻［1］所列出的所有類型的錯誤。Wp－方法在2個階段中一共生成了53個。

5 結 束 語

綜上所述，可得出以下結論，首先，DC－方法，沒有使用測試樹的所有遷移覆蓋路徑，而是利用層次關系，自頂向下對每個節點狀態進行訪問來達到覆蓋所有路徑的目的，這樣，狀態覆蓋也完全能達到。

其次，所提出的方法對于含有參數的FSM，在覆蓋DU的準則下，利用各條DU路徑的起始狀態與之前計算的三元組集合H(0)外連接起來即可，加入到最終的測試集中。

最后，本方法雖然仍然需要在一個測試序列執行完后重置回到初始態這樣的機制，但是相對Wp－方法、G－方法來說可以減少這樣的次數，即用例比它們要少，但是并沒有降低計算的復雜度。此外，給樹結點加上訪問標記，使得測試序列的長度也有所減少。

Chow在1978年提出的算法堪稱經典，幾十年過去，研究者依然以此算法為參考，提出的新方法也是對于某些情況有大的益處或者進行擴展使算法更為通用。此文在前人的基礎上從分解的思想出發提出的新算法能達到一定的優化目的。對FSM用例生成算法的研究有一定的借鑒意義。未來的工作，將主要集中在對不確定的FSM模型及帶有時間和數據變量的混合FSM進行用例生成的優化。

［1］T S Chow.Testing software design modeled by finite －state machines［J］.IEEE Transactions on Software Engineering，1978，4(3):178 －187.

［2］S Fujiwara，G V Bochmann，F Khendek，et al.Test Selection Based on Finite － State Models［J］.IEEE Trans.Software Eng.，1991，17(6):591 －603.

［3］L L C Pedrosa，A V Moura.Testing combined?nite state machines［J/OL］.Techni－ cal Report IC －10 －01，Institute of Computing，University of Campinas，2010.Available in http://www.ic.unicamp.br/～ reltech/2010/abstracts.html.

［4］A L Bonif＇acio，A V Moura，A S Sim～ao.A generalized model－ based test generation method［C］.In Proc.of 6thIEEE Inter.Conferences on Software Engineering and Formal Methods，Cape Town，SOUTH AFRICA，NOV 10 －14，2008:139 －148.

［5］A L Bonif＇acio，A V Moura，A S Sim～ao.Exponentially more succinct test suites［J/OL］.Technical Report IC －09 － 07，Institute of Computing，University of Campinas，2009.Available in http://www.ic.unicamp.br/～reltech/2009/abstracts.html.