@基于模型的测试-基于FSM(有限状态机)模型的测试方法

基于模型的测试——

基于FSM模型的测试方法罗殊彦摘要1.FSM的概念2.基于FSM的测试用例自动执行3.基于FSM的测试结果自动比较4.基于FSM的4种常用测试方法5.基于FSM的测试用例自动生成1.FSM的概念FSM全称是FiniteStateMachine

(有限状态机)。有限状态机是一种算法思想，简单而言，有限状态机由一组状态、一个初始状态、输入和根据输入及现有状态转换为下一个状态的转换函数组成。测试人员提供一系列输入给系统，通过观察输出来获取想要的信息。有成熟的理论基础，可以用形式语言和自动机理论来设计、操纵和分析。为什么可以基于FSM模型来设计测试用例？两种自动化方法的比较老的测试方法：

老的自动化测试工具是一种录制和回放的工具，用这种方法得到的脚本虽然逻辑上可以手工操作，并可以编辑，但由于自动化测试工具脚本语言的限制，在表示较大数据结构时，将变得很困难，而对面向对象脚本设计更不可能。当应用程序发生变化时，这些脚本的维护成本很高。FSM的测试方法：基于FSM测试用例的自动生成，必须选择真正的脚本语言，即可编程的语言（如Java语言），而不是类似于Java的脚本语言（让面向对象的脚本设计成为可能）。即先编写脚本，利用工具回放脚本，是面向多个构建版本有效使用自动化测试的方式之一。状态模型的抽象表示有限状态机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定状态的迁移。一个有限状态机M可以表示为一个有向图，用一个六元组(S，S0，δ，λ，I，O)来描述，其中:S是有限状态集合；S0∈S是初态；δ是状态转换函数；λ是输出值；I是有限输入字符集；O是有限输出字符集（λ∈O）；

M处于状态s时接收到输入x∈I后，产生输出y=λ(s，x)，并且迁移到状态s’=λ(s，x)，即产生一个迁移t，记为t(s，s’，x/y)，其中，s=head(t)，s‘=tail(t)。2.基于FSM的测试用例自动执行1.数据驱动技术数据驱动指对言语材料在感知水平上进行的加工过程。测试中所涉及到的数据项较多，如果手工进行操作较麻烦，也比较容易出错，脚本维护困难。2.同步控制问题

在测试脚本的执行过程中，重要的问题是同步。就是指测试脚本与被测应用程序之间的协调控制可以通过以下3种方法来解决同步问题：时间延迟策略测试用例的独立性设计建立完善的异常处理机制3.基于FSM的测试结果自动比较测试用例经过自动执行后产生一组实际输出，而要判定其正确与否就需要和预期的标准输出相比较。因此，实现自动比较的前提和关键是如何准确获取被测应用程序的预期输出结果。基于FSM测试并没有解决测试失效辨识，仍然要人工检查输出是否正确。通过状态验证可以解决这一问题，实现测试结果的自动比较。因为状态是内部数据的抽象，比较容易验证。两种种检验被测应用程序是否正确运行的方法:脚本可以判断是否能执行的操作不能执行，如脚本找不到所需的测试对象，脚本就停止运行。模型本身已知应用程序应该进入哪种状态，知道每种输入事件的预期目标状态，也就意味着能够创建测试准则程序来检查（在每种操作结束后）是否到达预期状态。4.基于FSM的测试方法T-MethodU-MethodD-MethodW-MethodWp-Method（了解）这些方法使用的前提条件是有限状态机是精简的、强连通的、完备的4.1T-MethodT-Method(Transitiontourmethod)：测试输入序列对应于规约说明中的状态迁移随机地产生，直到所有的状态迁移都被覆盖。该方法的测试输入序列中存在大量的冗余，此外检错能力也较差。实例1状态机状态迁移表重复序列:0→3→4→0→3→4机器内部可以避免这类循环重复序列:0→3→4→2→1→4→0→3→3→4机器内部就无法自动删除了测试序列表应用T方法可以生成如下的测试序列来覆盖所有的迁移状态机状态迁移表T方法特点：该方法的缺点是测试输入序列中存在大量的冗余，甚至可能会存在环。检错能力也较差。（因为T方法能够检测所有的输出错误，但不能检测所有状态迁移错误）4.2U-MethodU-Method：为状态机的每一个状态得到一个识别序列——唯一输入输出序列(UniqueInput/OutputSequence，UIO)，然后根据该识别序列构造测试输入序列。UIO序列可以唯一的标识M中状态，不同的状态不能有相同UIO序列。UIO序列的概念UIO序列是唯一输入/输出序列。一个UIO序列用于检测协议实现是否处于某个特定的状态，也是一个状态区别其它状态的标志，如果向协议实现输入特征序列中的输入事件，而产生的输出事件刚好是特征序列中的输出事件，则可以断定协议实现正好处于这个特定的状态。定义:对任意状态Sj，当且仅当：y/λ(Si,y)≠y/λ(Sj,y)(i≠j)，则说y/λ(Si,y)是一个UIO序列，记作UIO(Si)=y/λ(Si,y)。UIO序列可以唯一地识别一个状态，但一个状态的UIO序列并不一定是唯一的求某状态UIO序列的基本步骤:1.建立所有的边标号与输入输出集的关系；2.对每个状态求出所有长度为1的输入输出序列；3.检查它们是否唯一，如果是，该状态的UIO序列就找到了；4.否则，对没有UIO序列的状态，寻找长度为2的序列；5.从长度为K的UIO序列中继续求出长度为K+1的输入输出序列，检查它们是否唯一，直到对每个状态都找到UIO序列，或者K的长度超过2n2。UIO序列的生成方法：

对于一个有限状态机M中的每一个状态之间的变化，即边(Si，Sj)，可以用以下方法生成测试子序列来覆盖每个状态迁移：输入r(即reset，这里讨论的每个有限状态机都有重置功能)到M，使M回到初始状态S0；找到从初态S0到状态Si的最短路径SP(Si)，一般采用Dijikstra最短路径方法；输入可以使有限状态机M从状态Si转移到Sj的符号；输入状态Sj的UIO序列。实例2有限状态机中每个状态的UIO序列状态机β序列的生成：Atestsequenceforafinitestatemachine(FSM)MisasequenceofinputsymbolswhichcanbeusedintestingconformanceofimplementationsofMagainstthespecificationofM.AnoptimizedtestsequenceforMisatestsequencesuchthatnosubsequenceofitiscompletelycontainedinanyothersubsequence.Aβ-sequenceisaconcatenationoftestsubsequencesfortestingthetransitionsofM.TestsequencesgeneratedbytheU-,D-andW-methodsconsistofconcatenationoftestsubsequenceofaβ-sequenceaftersuitableoptimization.实例3

有限状态机M在输入A/B时的状态转移情况如下：有限状态机M的状态迁移表状态机状态机M的UIO序列在U方法中，对于有限状态机M的β序列如下，其中每一个状态迁移的子序列按照上述步骤进行：U方法产生对应状态迁移的β序列将上述测试序列优化可以得到使用U方法的最短测试序列:存在测试序列的条件:对象处在该状态时接受了对应的UIO序列中的输入时，所产生的输出不同于状态空间中的任何其它状态在接受此输入时所产生的输出。如果一个有限状态机不存在UIO序列，则无法应用该方法构造测试输入序列。如下图所示的有限状态机就无法使用U方法来构造测试输入序列:该有限状态机中，状态A就没有UIO序列。因为，如果在状态A时输入1，FSM转到状态C，输出为0。在状态B时输入1，FSM也会转到状态C且输出0。因而，以1开始的序列不可能是A的UIO序列；在输入0时，状态A与C也都会转到状态B，输出0，因而以0开始的序列也不可能是A的UIO序列。所以，状态A没有UIO序列，该有限状态机不能用U方法构造测试输入序列。使用UIO序列的优点主要有:由于UIO序列只是D序列或者W序列的子集，所以UIO序列要比它们短得多；在实际中，几乎所有的FSM都存在着UIO序列，除非FSM具有等价的状态。4.3D-MethodD-Method：首先对有限状态机构造一个区分序列DS(DistinguishingSequence)，然后根据该区分序列构造测试输入序列。和U方法一样，该方法只适用于存在区分序列的状态机。实例4D方法的关键是如何计算有限状态机的区分序列DS对于下图所示的有限状态机，应用相应的算法得出BB是其最短的DS。状态机M的DS序列状态机DS生成方法：D方法中β序列的生成基本上和U方法相同，只需在最后一步中将相应的UIO序列换成DS即可。将上述测试序列优化可以得到使用D方法的最短测试序列:rAAAAABBrAAAABBBrAAABBBrAABBBrABBBrBBB状态机β子序列表4.4W-MethodW-Method：基于状态机的特征集W来构造测试输入序列，由于每个精简的状态机都存在特征集，因此该方法的实用性较为普遍。特征集W是由这样一组数据组成：对于M中每个状态输入W中的数据α1，……，αk得到的最后一位输出都不同，即M|Si(α1

，……，αk)

≠M|Sj(α1，……，αk)，这里Si和Sj是M中的两个不同状态。W方法中的两个集合W方法的测试用例包含两个输入集:W集(W-set)和P集(P-set)。W集是有限状态机的特征集，这些特征集由输入消息序列组成，这些消息序列能区分状态机中的状态对。W集通过特殊的方法构造。P集代表消息序列集(包括空消息)，把状态机从初始状态转换到预期状态。P集通过遍历状态机构造测试树得到。测试序列由两个集合连接而成。W方法在要求有限状态机是最小的同时，要求该自动机存在W集，但是很多自动机特别是在规约不完全的情况下，并不具备W集。W特征集生成方法（和U方法类似）：特征集W的作用是为了识别有限状态机M中的每个状态。对于有限状态机M可以按照以下步骤生成测试序列:构造有限状态机M的特征集w，w=(α1，…，αk}，这里αi是一个输入字符，1≤i≤k。按照U方法中的步骤生成β序列，不同的是要将每个状态的UIO序列换成特征集W。SP(s)XW

=

SP(s)X{α1，……，αk}

={SP(s)Xα1，SP(s)Xα2……SP(s)Xαk}SP(s)是指从初始状态到达状态S的最短路径。对于下图所示的有限状态机M，得到其特征集W为{A，AA，B}。有限状态机M应用特征集M最后的输出实例5得到使用W方法的最短测试序列:rAAAAAAArAAAAABrAAAABAArAAAABBrAAABAArAAABBrAABAArAABBrABAArABBrBAArBB状态机应用W方法可以生成如下的β序列：4.5Wp-MethodWp-Method：对W-Method进行了简化，同时保证了与W-Method具有相同的缺陷覆盖度。Inan

等人提出了一种构造最小长度的测试输入序列的模型，该模型基于测试输入序列和状态识别以及验证序列的特性，给出了构造最短测试输入序列长度的产生式算法。4.6四种方法的比较T方法最简单。但测试输入序列中存在大量的冗余，可能会存在环，查错效率低。U方法和D方法得到的测试序列较短，但它们的应用有一定的限制，如有时不存在UIO序列或D序列。W方法的适用性较广，但