3.2.2　基于FSM的软件测试技术

1956年，Moore建立了一个有限状态测试的框架，定义了区别（Distinguishing）和引导（Homing）实验的概念，并给出了确定状态等价的算法和构造引导序列的算法，这是介绍基于有限状态机测试的最早的文献之一。

目前，基于有限状态机的测试方法中有四种经典测试方法，分别是T方法、U方法、D方法、W方法。

·T方法：假定一个有限状态机是强连通的。测试输入序列对应规约说明中的状态迁移随机地产生，直到所有的状态迁移都被覆盖。T方法较为简单，缺点是测试输入序列中存在大量冗余，甚至可能存在环。另外其检错能力也较差，只能检测迁移是否存在，而不能检测迁移所到达的状态。

·U方法：假定一个最小的、强连通的并且是完备的有限状态机。该方法需要得到该有限状态机中每一个状态的一个识别序列，该序列叫作单一输入/输出（Unique Input/Output，UIO）序列。UIO序列可以唯一标识有限状态机中的状态，不同的状态不能有相同的UIO序列。但并不是所有的有限状态机都存在UIO序列，如果一个有限状态机不存在UIO序列，则无法应用该方法构造测试输入序列。对于有限状态机中每一个状态之间的变化，可用以下方法生成每个迁移的测试子序列：①输入r（即reset，这里讨论的每个有限状态机都有重置功能）到有限状态机，使有限状态机回到初始状态；②找到从初态到状态S _i 的最短路径SP(S _i )；③输入可以使有限状态机从状态S _i 迁移到S _j 的符号；④输入状态S _j 的UIO序列。

·D方法：假定一个最小的、强连通的并且是完备的有限状态机。该方法首先对有限状态机构造一个区分序列DS（Distinguishing Sequence），然后根据该区分序列构造测试输入序列。和U方法一样，并不是所有的状态机都存在区分序列，所以该方法的应用也有一定的限制。

·W方法：假定一个最小的、强连通的并且是完备的有限状态机。该方法要求首先生成有限状态机的特征集W，然后在特征集W的基础上构造测试输入序列。只要状态机是最小的、完备的，就存在特征集，所以该方法的适用性较强。特征集W是由这样一组数据组成的：对于有限状态机中的每个状态，输入W中的数据α1,…,αk，得到的最后一位输出都不同，即M|S _i (α1,…,αk)≠M|S _j (α1,…,αk)（M即有限状态机），这里S _i 和S _j 是有限状态机中的两个不同状态。应用W方法进行测试的原理和U方法类似，特征集W的作用是识别有限状态机中的每个状态。对于有限状态机，可以按照以下步骤生成测试序列：①构造有限状态机的特征集W，W={α1,…,αk}，这里αi是一个输入字符，1≤i≤k；②按照U方法中的步骤生成β序列，不同的是要将每个状态的UIO序列换成特征集W。 +pxRuJt7rtY5Fz/GasvvYZDLdR+UeiEhxtgDXRZy4AaeFxGPt6ntaEOrZ8TaghBg