基于FSM的測(cè)試用例生成算法*

蔡 璐，朱怡安，鄭 煒

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，西安 710072)

1 引言

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

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

2 相關(guān)定義及條件假設(shè)

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

2.1 相關(guān)定義

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

定義2:兩個(gè)集合A，B，集合中元素的個(gè)數(shù)分別為|A|和|B|

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

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

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

若|A|＜ =|B|，則 A·B={αβ|?α∈A，?多個(gè)β∈B}，滿(mǎn)足|A·B|=|B|;

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

(3)一個(gè)三元組 R ＜S，D，Quen＞，R.S屬性為起始狀態(tài)，R.D屬性表示中止?fàn)顟B(tài)，R.Quen屬性表示字符序列能使得系統(tǒng)從起始態(tài)遷移到相應(yīng)的中止態(tài)，則定義:

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

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

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

2.2 條件假設(shè)

S和I表示兩個(gè)FSMs，S通常代表一個(gè)參考規(guī)格狀態(tài)機(jī)，I代表一個(gè)實(shí)現(xiàn)。S為最小FSM，有n個(gè)狀態(tài)，W是S的特征集，S和I都是確定的和完全的有窮自動(dòng)機(jī)，實(shí)現(xiàn)FSM的狀態(tài)數(shù)為m個(gè)。對(duì)輸入字母集合X，每個(gè)狀態(tài)對(duì)X中的每個(gè)的字母輸入都有相應(yīng)的響應(yīng)。故障模型與文獻(xiàn)［3］中相同。

3 相關(guān)理論證明及DC－方法

3.1 相關(guān)證明

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

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

證明:由文獻(xiàn)［5］附錄中的定理:S與I等價(jià)?S和 I是 PA.Z －等價(jià)，則 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 － 等價(jià)，類(lèi)推 Pk.P.Z－等價(jià)，其中k為狀態(tài)節(jié)點(diǎn)所在測(cè)試樹(shù)T的層數(shù)，若T的深度為h(一個(gè)節(jié)點(diǎn)時(shí) h=1)，k＜h，k∈N。由文獻(xiàn)［1］附錄中的引理 A.4:Ik≈ZSi?Ik≈ZiSi，其中 Zi?Z，Zi={p2}.Wj)，Wj是狀態(tài) Sj的特征集，δ(p2，Si)=Sj，當(dāng)以 Si(Si≠S0)為初始狀態(tài)時(shí)，Ti=P.X［m －n］.Wj或 Ti=P.X［m －n］，因此，S 和 I是－ 等價(jià).Zi－ 等價(jià)，從而 S 和 I是QUE2－等價(jià)。而從真正的初始態(tài)S0到達(dá)Si，則通過(guò)輸入序列，狀態(tài)覆蓋的測(cè)試序列為Q.Z，對(duì)S0的遷移覆蓋要達(dá)到完全，則需對(duì)每個(gè)輸入Xi∈P，若Xi?Q，則產(chǎn)生測(cè)試序列 Xi.Zi，P0={Xi|Xi∈P，但 Xi?Q}從而以S0、I0為初始態(tài)S和I，S和I是(QUE1?QUE2)－等價(jià)，即S和I是∏－等價(jià)。證畢。

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

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

證明:由文獻(xiàn)［4］可得，當(dāng) R=W 時(shí)，πg(shù)=PA.Z;由文獻(xiàn)［2］可得，πp=Q.Z∪(PA －Q).Zi;而由定理1，DC－方法生成的測(cè)試集 π=(Q.Z∪P0.Zi)?(P.Zi)，其中 P0?X，|P0|＜ |X|，S0 經(jīng)過(guò)輸入Q.Z∪P0.Zi的子序列QUE0后回到S0的集合大小為|QUE0|，當(dāng) |(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)當(dāng)|π|=|(Q.Z∪P0.Zi)|時(shí)，有，

(2)當(dāng)|π|=|(P.Zi)|+|QUE0|時(shí)，

證畢。

3.2 DC － 方法

該方法主要思想是依標(biāo)記樹(shù)逐步分解狀態(tài)機(jī)，生成針對(duì)每個(gè)狀態(tài)的測(cè)試序列，最后組合每個(gè)階段的測(cè)試序列使其從初始態(tài)觸發(fā)，具體見(jiàn)算法1。其中S為從需求規(guī)格中抽象出來(lái)的參考FSM，I為一種實(shí)現(xiàn)FSM(見(jiàn)圖1)，目的是檢驗(yàn)兩者的一致性。

一個(gè)企業(yè)的運(yùn)營(yíng)與管理合理與否，終究還是人起作用。企業(yè)中人力資源部門(mén)作為管理員工的專(zhuān)職部門(mén)，更要在企業(yè)的經(jīng)濟(jì)管理中發(fā)揮出激勵(lì)員工的作用。這要求企業(yè)要進(jìn)行人力資源培訓(xùn)，培養(yǎng)人資部門(mén)員工的責(zé)任道德意識(shí)和管理能力，使他們積極主動(dòng)的進(jìn)行人力資源工作。企業(yè)在進(jìn)行人力資源管理時(shí)，一定要按照員工的優(yōu)勢(shì)以及自身意愿將其安排在最適當(dāng)?shù)奈恢?，使人員分布合理，使人資部門(mén)結(jié)構(gòu)嚴(yán)謹(jǐn)，這樣才便于讓不同崗位的員工發(fā)揮各自的作用。

圖1 規(guī)格FSM S

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

輸入:S，I，n，m

輸出:測(cè)試集П

步驟:

Step1，計(jì)算每個(gè)狀態(tài)的特征集Wi及它們的全集W，利用文獻(xiàn)［4］的Construction 3中的算法構(gòu)造測(cè)試樹(shù)T;

Step2，遍歷樹(shù)T，樹(shù)高為ht，得出從初始狀態(tài)S0出發(fā)到達(dá)剩余的各個(gè)不同狀態(tài)的最小的輸入序列集Q和每個(gè)狀態(tài)分支上的輸入集合 P，特別的，P0={ε}∪P;

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

Step4，寬度搜索測(cè)試樹(shù)T，對(duì)任一的Si∈S，初始時(shí)vist(Si)=0，對(duì)每個(gè)被訪問(wèn)的節(jié)點(diǎn)Si=node(i)，

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

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

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

如果vist(Si)=1，則表明之前已經(jīng)驗(yàn)證過(guò)從此節(jié)點(diǎn)出發(fā)的所有遷移，繼續(xù)往后搜索;

2)記錄Ti中每個(gè)序列pi的起始狀態(tài)Spi和終止態(tài)Dpi，

3)若 m ＞n，對(duì)?x∈P，Ti.x 能到達(dá)的狀態(tài) Sj，進(jìn)行i)和ii)的判定

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

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

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

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

5)重復(fù)步驟4，直到所有的狀態(tài)都已經(jīng)訪問(wèn)過(guò);

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

4 實(shí)例

在許多實(shí)例中隨機(jī)選取了圖1所示的參考FSM，及圖2所示的相對(duì)應(yīng)的一種實(shí)現(xiàn)FSM，分兩種情況討論上節(jié)提出的算法。

4.1 當(dāng)實(shí)現(xiàn)FSM的狀態(tài)數(shù)m=n

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

圖2 待測(cè)FSM I

圖3 測(cè)試樹(shù)T的逐層訪問(wèn)

表1 H0層測(cè)試序列信息

表2 H1層測(cè)試序列信息

應(yīng)用上面計(jì)算出的測(cè)試集到圖2所示的FSM中，得到相應(yīng)的輸出:ff，ee、ff、ffe、ffff、ee、ff、eff、ffe、eff，與期望的輸出對(duì)比，可看出，第三個(gè)、第七個(gè)、第八個(gè)、第十個(gè)測(cè)試序列產(chǎn)生的結(jié)果有差異，從而檢測(cè)出I0到I1當(dāng)輸入為a時(shí)的操作錯(cuò)誤(第三個(gè)和第七個(gè)序列)和從I2在輸入為a時(shí)遷移到I1的遷移狀態(tài)錯(cuò)誤(第八個(gè)和第十個(gè)序列)，相比文獻(xiàn)［4］的檢測(cè)遷移錯(cuò)誤能力(對(duì)于其中的遷移狀態(tài)錯(cuò)誤只有一個(gè)序列能檢測(cè)出來(lái))，增強(qiáng)了發(fā)現(xiàn)錯(cuò)誤的概率。

4.2 當(dāng)實(shí)現(xiàn)FSM的狀態(tài)數(shù)m＞n

假設(shè) m=4，依據(jù)圖 1，n=3，所以 m － n=1，在步驟3中，∏1=Q.X［1］.W，在步驟4 中，對(duì)于 S1，置 vist(S1)=1，S1∧a=S0，S1∧b=S2，S1∧c=S1，所以 T1={a，b.b，c.c}，對(duì) T1.P={aa，ab，ac，bba，bbb，bbc，cca，ccb，ccc}，重復(fù) 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}，最終得到的用例數(shù)為 29 個(gè)，且能檢測(cè)出文獻(xiàn)［1］所列出的所有類(lèi)型的錯(cuò)誤。Wp－方法在2個(gè)階段中一共生成了53個(gè)。

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

綜上所述，可得出以下結(jié)論，首先，DC－方法，沒(méi)有使用測(cè)試樹(shù)的所有遷移覆蓋路徑，而是利用層次關(guān)系，自頂向下對(duì)每個(gè)節(jié)點(diǎn)狀態(tài)進(jìn)行訪問(wèn)來(lái)達(dá)到覆蓋所有路徑的目的，這樣，狀態(tài)覆蓋也完全能達(dá)到。

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

最后，本方法雖然仍然需要在一個(gè)測(cè)試序列執(zhí)行完后重置回到初始態(tài)這樣的機(jī)制，但是相對(duì)Wp－方法、G－方法來(lái)說(shuō)可以減少這樣的次數(shù)，即用例比它們要少，但是并沒(méi)有降低計(jì)算的復(fù)雜度。此外，給樹(shù)結(jié)點(diǎn)加上訪問(wèn)標(biāo)記，使得測(cè)試序列的長(zhǎng)度也有所減少。

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

［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(xiàn) 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.