面向对象类测试的精简EFSM转换算法_面向对象 算法

　　摘要: EFSM是一个没有层次和并发结构的状态图，因此很难处理较复杂的软件系统，而且由于EFSM中存在前置条件，使得生成的测试序列有可能存在不可达性。该文提出一种将EFSM转化为精简有限状态机（FSM）的转换算法，很大程度上减少了中间产生的等价状态，并有效防止了组合间爆炸问题的出现，得到的精简FSM最小可达。
　　关键词:状态测试；扩展有限状态机；有限状态机；状态图；不可达路径
　　中图分类号：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状态图的测试在类测试中得到广泛应用。但是由于UML状态图中的状态有层次和并发结构,再加上状态之间的广播通信机制,使得传统的流分析测试技术不能直接得到应用。EFSM是一个没有层次和并发结构的状态图，因此可以先将UML状态图转化为扩展有限状态机（EFSM），消除状态图中状态的层次和并发结构与状态之间的广播通信机制,
　　再通过传统的类测试方法对类进行测试。基于EFSM测试是各种基于状态测试方法的理论基础，在文献[1]中Chourouk Bourh? fir系统地讲述了基于EFSM测试的理论基础和各种测试方法。在文献[2]中N.Coga从理论上比较了最常用的四种测试用例生成算法的故障提示能力和效率。
　　EFSM是有限状态机(FSM)的一个扩展，它在FSM的基础上增加了变量、操作以及状态移的并置条件，所以从EFSM产生的测试序列有可能存在不可达路径[3]。文献[3，4]对这个问题进行了相关的研究，并提出了解决的算法。该文通过对EFSM的研究，提出一种将EFSM转化为精简FSM的算法。通过将谓词约束的配置分裂，使转化过程中产生的等价状态大大减少，剔除了可能造成组合空间爆炸的无用状态，使得到的精减FSM最小可达。
　　图2
　　模型中，以Name: Predicate/Action来标记每一条变迁，其中Predicate为空者表示变迁谓词约束为永真（True），Action为空者表示变迁对起始状态的变量值无影响。图中共有3个状态；3个变量:布尔变量有2个，整形变量P有8个，整形变量R有8个；
　　若按配置枚举的方法进行可达性分析，将得到3*（2*8*8）=384个状态（192个可达）。显然，这个数目相对于我们的处理能力有些过大，得到的等效FSM包含了过多的状态，给最简化和检测序列都带来了麻烦。
　　当EFSM模型应用于比较复杂的系统时，因为其本身在语法上不支持层次结构，常常面临状态爆炸的问题。而UML的状态图引入超态的概念以支持层次结构解决了这个问题，在面向对象系统的建模中得到了广泛的应用。
　　在基于EFSM的测试中，把EFSM对应的程序实现看作是一个黑盒子而不考虑程序内部的细节。在基于EFSM的测试序列的生成过程中，测试序列的可执行性是一个重要问题，因为直接采用基于FSM模型生成测试序列，可能会遇到不可执行的情况。
　　对于一个EFSM来说，如果相关变量都有有限数量的取值或者有限数量的取值域，那么此EFSM的构造数量是有限的。我们可以将EFSM中的配置看作普通FSM中的状态，通过这样的替代，就可以将EFSM转化为普通的FSM。这样，测试用EFSM模型描述的系统的问题就转化为寻找等价FSM的问题。
　　由此也可以看出EFSM中状态分组有很大的不稳定因素。如图1所示：
　　图3
　　此时我们可以把EFSM的一个配置看作对应的等效FSM的一个状态。
　　在进行了EFSM至等效FSM的转换后，建立系统的测试用例集就可以应用FSM生成测试用例的方法来生成测试序列。但是由于类的封装性和类状态的复杂性，一个类对相同的输入可以有不同的反应。而且状态转换的条件也不只决定于输入，还可能取决于内存变量的谓词约束。该文中的方法如果进行配置组分裂时将可达性分析结合一起进行，则算法会更加有效。
　　[1] Bourhfir C,Dssouli R,Aboulhamid E M.Automatic Test Generation for EFSM_based Systems. .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].计算机技术与发展,2006,16(1).
　　[6]熊利,周宽久.基于使用模型的嵌入式软件测试用例生成研究[J].计算机技术与发展,2010,20(5).
　　[7]李杨,张春海,张美玲.基于UML的回归测试软件测试方法的研究与应用[J].计算机技术与发展, 2010,20(9).