一种基于状态图类测试用例的转换算法

吴静莉 李素娟

摘要：在面对复杂的系统时，EFSM模型在语法上的欠缺，非层次结构会导致状态爆炸。针对EFSM中存在的状态迁移不确定性问题进行改进，对状态图中存在的超态结构，提出一种转化方法来消除状态图中的层次和并发状态，将其转化为EFSM后，用基于扩展有限状态机的测试用例生成方法来生成系统的测试用例。

关键词：测试用例；EFSM；状态图

中图分类号：TP311 文献标识码：A 文章编号：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

面向對象的软件测试是目前研究的重点，其主要研究方向包括基于规约的测试，文献[1]中总结了各种基于规约的测试方法，目前最广泛应用的基于状态的测试是以扩展有限状态机（EFSM）为基础的测试。在面对复杂的系统时，EFSM模型在语法上对层次结构的不支持，状态爆炸问题不可避免，虽然在物理结构上对状态空间进行分解处理，但系统整体性受到影响。因此将超态概念引入到UML状态图中，解决了层次结构问题，在面向对象建模中也得到了广泛应用。

本文针对状态迁移不确定性问题进行改进，针对状态图中存在的超态结构，提出一种转化方法来消除状态图中的层次和并发状态，将其转化为EFSM后，用基于扩展有限状态机的测试用例生成方法来生成系统的测试用例。

1 有层次和并发状态的UML状态图

UML状态图也称为扩展的有限状态机，但UML状态图进行了扩展，并支持和时间有关的转换。图1是一有层次和并发结构的UML状态图例子。其中S2是AND-状态，S0、S3、S4是OR-状态，其余为BASIC-状态。t1是层内迁移、t2是层间迁移。

2 状态图向扩展有限状态机的转换

为了简化讨论难度，设EFSM是一个三元结构{GStates，C0，GTrans}。GStates 是全局状态（globe states ）的集合[3]，C0是全局状态的初始状态，GTrans是全局转换路径（globe transitions）的集合。如图2所示的就是一个三元结构的EFSM。

将UML状态图图转换为EFSM图只需消除UML状态图的层次、并发和广播消息。UML状态图将以以下方法转换为EFSM（对应将图1转换为图2）。

2.1 生成EFSM的状态

因为格局（configurations）是同时运行的最大状态集，所以Gstates对应的是UML状态图的格局（configurations）。

求全局状态的步骤如下：

1）由状态图产生状态树（图4）；

2）搜索UML状态图的所有状态，找到根状态root；

3）从根状态开始进行深度优先搜索所有的状态，如果状态Si是叶子结点，则把该结点和其所有的父状态一起作为一个全局状态；

由图1的UML状态图产生的EFSM中的五个全局状态为：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；

其中，产生状态树的步骤如下：

1）将状态图的根状态作为状态树的根状态root；

2）对状态图进行广度优先搜索，将其子状态作为root的孩子结点；

3）继续对孩子结点进行第二步操作，直到没有孩子结点，即搜索到叶子结点。

由图1中UML状态图产生的状态树如图3 （图4为改进后的状态树）。

对状态树中的兄弟结点的关系进行改进：

a）如果在状态树中，兄弟之间是或状态的关系，则不用改变。

b）如果在状态树中，兄弟之间是与状态的关系，将其中一个兄弟和其所有的孩子结点作为另一个兄弟的所有叶子结点的孩子。

2.2 生成EFSM中的转换

求全局转换的路径算法如下：

1）检查根转换，即检查root到任一个全局状态的叶子结点在原状态图中有没有转换，如果有则加入到全局转换路径中。

2）任取两个全局状态C1和C2。

3）依次搜索C1和C2中的叶子状态有没有自转换，如果有作为全局状态的自转换。

4）搜索状态图中所有的转换，得到以C1中的某个状态为源状态、C2中的某个状态为目标状态的转换，并且不是C2中的自转换，这个转换作为从C1到C2的全局转换。

5）依次循环所有的全局状态，直到搜索完所有的转换为止。

在得到全局状态和全局转换之后，由UML状态图就生成了EFSM状态转换图，即图2所示的EFSM。

3 测试用例的生成

将UML状态图转换成EFSM后，消除了层次和并发结构。扩展有限状态机也可以看作是一种特殊的图，状态图的测试理论方法可直接应用进行测试，这样类的输入和状态就实现了并行测试，如果产品可靠性发生改变，简单广度搜索和深度搜索构建出覆盖标准，并产生测试用例。

通过数据定义和路径标识的EFSM图可构建基于数据流的测试案例，实现了数据流的测试。

4 结束语

文章实现并改进了基于UML状态图在类测试用例的生成方法，对含有层次结构和并发结构的状态图，提出一种改进思想，将不含父状态的叶子结点作为新状态，然后依据原状态图中的转换来构造新状态之间的新转换，得到扩展有限状态机，并采用基于EFSM的测试方法或基于状态图的测试用例生成方法来生成所需的测试用例。

参考文献：

[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状态图的面向对象类级测试模型[J]. 计算机工程， 2005， 21（31）： 76.

[4] 张毅坤. 基于UML状态图的类测试用例自动生成方法[J]. 计算机工程， 2003， 21（29）： 76.

[5] 吴静莉， 李素娟. 面向对象类测试的精简EFSM转换算法[J]. 电脑知识与技术， 2012（18）.