有限状态机器测试(过渡游览法)

测试相关概念—故障类型 行为由转换定义。 故障分为三种类型： 输出错误Output faults：错误的输出是由转换产生的。 状态转移错误State transfer faults：转移到错误的状态。 额外的状态Extra states（只有在有状态转移时才会发生故障）。

下面是一个附加状态的示例，它表示仅在状态转换时才会发生的故障情况： 让我们考虑一个简单的自动售货机。 自动售货机有以下状态：“空闲”、“接受硬币”、“分发物品”和“错误”。 这些状态之间的转换基于特定条件发生。 在这种情况下，我们可以引入一个称为“Error”的附加状态来表示仅在存在状态转换时才会发生的故障情况。 此状态表示在自动售货过程中出现了问题。

这是带有附加“错误”状态的状态转换示例：

1.空闲： - 过渡：当硬币投入并达到正确数量时，过渡到“分发物品”。 - 转换：插入无效硬币时，转换为“错误”。

2.接受硬币： - 过渡：当达到正确的数量时，过渡到“分发物品”。 - 转换：当用户按下取消按钮时，转换回“空闲”。 - 转换：如果在接受硬币时发生硬币堵塞或机器故障，则转换到“错误”。

三、配药项目： - 过渡：分配物品后，过渡回“空闲”。

4.错误： - 转换：错误条件得到解决或服务后，转换回“空闲”。

在此示例中，“错误”状态表示仅当存在与硬币接受或机器故障等问题相关的状态转换时才会发生的故障情况。 “错误”状态允许自动售货机通过进入指示发生故障的不同状态来处理异常情况并从中恢复。 请注意，这只是一个示例，自动售货机的具体实现和行为可能会有所不同。 引入附加状态来处理状态转换期间发生的故障情况的概念可以应用于需要错误处理的各种系统和场景。

找茬Finding faults 考虑前两种故障。 输出故障：可以通过简单地执行故障来发现过渡。 状态转移错误：要求我们执行转移和表明已经达到了错误的状态。 我们需要识别或分离状态的方法。 我们将看到第二个问题的解决方案（发现状态转移错误）帮助我们找到额外的状态。

区分状态–Separating Two States FSM M 的两个状态 s 和 s0 被输入分开序列 x 如果：M 对 x 的响应在状态 s 是不同的和 s0 (λ^(s, x) /= λ^(s0, x))表示状态s和s0产生的输出不相等。 如果存在这样的输入序列 x，则称 s 和 s0 是可分离的。 如果状态 s 和 s0 是等价的，则称它们是不可分离的。

区分状态示例 FSM 等价性Equivalence 和极小性Minimality 如果两个 FSM 的初始状态是等价的，则它们是等价的。 如果 FSM M 不小于（根据states数量) FSM 定义了相同的正则语言。 注意：如果 FSM M 是初始连接的，那么它是最小的，如果 且仅当 没有一对 M 的不同状态是等价的。

重置Resets 复位（或复位操作）是将 FSM 用于初始状态与当前状态无关。 可靠的重置是已知会占用系统的重置正在测试其初始状态（已正确实施）。

共同假设Common Assumptions 许多测试技术（以及我们将涵盖的所有技术）假设 FSM 规范 M 是： (1)确定性deterministic。 (2)完全指定completely-specified。 注意：我们通常可以通过完成使部分 FSM 完全指定。 (3)强连接strongly connected。 (4)最小化minimal。 注意：我们可以将任何 FSM 转换为等效的最小 FSM。 某些方法假设 M 具有可靠的复位操作

过渡游览主要与确定性有限状态机 (DFSM) 相关联 因为 DFSM 对状态和输入符号的每个组合都有定义明确且唯一的过渡。 确定性属性确保对于给定的状态和输入符号，只有一个可能的下一个状态。 过渡之旅涉及遍历 FSM 的状态和过渡，以涵盖输入和路径的所有可能组合。 过渡之旅的目的是确保 FSM 中的每个过渡都得到执行和测试，以验证其正确性和功能性。

过渡游览法Transition Tour Method 给定一个 FSM M，过渡游览方法包括： 从 M 的初始状态找到一条路径（转移序列）ρ，其中包括 M 的所有转移。 测试序列是 ρ 的标签：对应的输入/输出序列。 显然，只要没有状态转移故障,transition tour 方法可以保证找到输出故障。

生成过渡之旅 可以应用一种简单的启发式方法，例如： 在当前状态 s 中，如果从 s 有一个转移 t 还没有被包含然后添加 t 当前路径和更新当前状态。 否则，遵循从 s 将 M 移动到具有至少一个未覆盖转换的状态的最短路径。 或者，我们可以使用图形算法（我们正在寻找包含所有边的路径）。这些可以返回最佳（最短）的过渡路线在多项式时间。

观察过渡之旅 过渡之旅可能找不到状态转移错误 为了找到状态传输错误，我们需要能够检查状态。 在黑盒测试中，这需要找到合适的输入序列。 我们可以通过区分可能状态的序列来跟踪每个转换。

查看原文