基于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.