测试大型状态机的策略有哪些？

Question

我继承了一个庞大而相当复杂的状态机。它有31个可能的状态，所有这些状态都是真正需要的（对于重要的业务流程来说）。它具有以下输入：

• 枚举：当前状态（0->30）
• 枚举：来源（目前只有2个条目）
• 布尔值：请求
• 布尔值：类型
• 枚举：状态（3个状态）
• 枚举：处理（3个状态）
• 布尔值：已完成

将其分解为单独的状态机似乎不可行，因为每个状态都是独特的。我针对最常见的输入编写了测试，每个输入一个测试，所有输入保持不变，除了状态。

[Subject("Application Process States")]
public class When_state_is_meeting2Requested : AppProcessBase
{
    Establish context = () =>
    {
        //Setup....
    };

    Because of = () => process.Load(jas, vac);

    It Current_node_should_be_meeting2Requested = () => process.CurrentNode.ShouldBeOfType<meetingRequestedNode>();
    It Can_move_to_clientDeclined = () => Check(process, process.clientDeclined);
    It Can_move_to_meeting1Arranged = () => Check(process, process.meeting1Arranged);
    It Can_move_to_meeting2Arranged = () => Check(process, process.meeting2Arranged);
    It Can_move_to_Reject = () => Check(process, process.Reject);
    It Cannot_move_to_any_other_state = () => AllOthersFalse(process);
}

对于每种状态和输入集合，没有人完全确定输出应该是什么。我已开始为此编写测试。但是，我需要编写类似4320个测试用例（30 * 2 * 2 * 2 * 3 * 3 * 2）。

你有针对测试状态机的建议吗？

---

编辑：我正在尝试所有建议，并将在找到最佳方法时标记答案。

- Pondidum

---

你有没有尝试过全对方法呢？你找到了其他能满足你需求的方法吗？ - Lieven Keersmaekers

很不幸，我目前的工作时间表非常紧张 - 我应该在本周内有更多时间来研究这个问题。目前状态图看起来是最好的解决方案（h2g2java的），尽管我还没有完全研究所有的解决方案。 - Pondidum

我不确定我完全理解状态图的概念（实际上，我确定我不理解） - Lieven Keersmaekers

Answer 1

我看到了问题，但是我肯定会尝试将逻辑拆分出来。

在我的眼中，最大的问题区域是：

• 它有31种可能的状态。
• 它有以下输入：
• 枚举：当前状态（因此为0-30）
• 枚举：来源（目前仅有2个条目）
• 布尔值：请求
• 布尔值：类型
• 枚举：状态（3种状态）
• 枚举：处理（3种状态）
• 布尔值：已完成

这里发生的事情太多了。输入使代码难以测试。您已经说过将其拆分成更可管理的区域会很痛苦，但测试这么多逻辑一次性进行同样（如果不是更加）痛苦。在您的情况下，每个单元测试涵盖了太多内容。

这个我问过的关于测试大型方法的问题与性质类似，我发现我的单元太大了。你仍然会有很多测试，但它们会更小、更易管理，覆盖范围更小。尽管如此，这只会是一件好事。

测试遗留代码

看看Pex。你声称继承了这个代码，所以这实际上不是测试驱动开发。你只是想要单元测试来覆盖每个方面。这是一件好事，因为任何进一步的工作都将得到验证。我个人还没有充分使用Pex，但是我被我看到的视频所震撼。本质上，它将基于输入生成单元测试，而在这种情况下，输入是有限状态机本身。它将生成你没有想到的测试用例。当然，这不是TDD，但在这种情况下，测试遗留代码应该是理想的。

一旦你有了测试覆盖率，你就可以开始重构或添加新功能，并确保有良好的测试覆盖率来确保你不会破坏任何现有的功能。

- Finglas

---

我认为将其分割成可管理的区域唯一的问题是它是一个状态机。它是从一个状态到另一个状态移动的决策集合 - 我真的不知道如何将其分割。但我确实喜欢Pex的外观，即使只是一个起点，也可能会有所帮助。 - Pondidum

状态设计模式规定每个状态都应该是独立的、逻辑上的代码区域。状态机本身不应该关心它有多少个状态。如果这个状态机没有遵循这个规定，或者将状态嵌入其中（比如通过 switch 语句），那就是一个问题。http://en.wikipedia.org/wiki/State_pattern - Finglas

并不是这样的 - 其他代码仅仅查询状态机所处的状态，从而确定应该显示哪些选项等。 - Pondidum

Answer 2

全对测试

为了限制测试的组合数量，并保证覆盖最重要的组合，你应该看一下全对测试。

全对测试背后的原理是：程序中最简单的错误通常由单个输入参数触发。次简单的错误类别包括那些依赖于参数对之间相互作用的错误，这可以通过全对测试来捕获。1涉及三个或更多参数之间相互作用的错误逐渐变得不太常见2，同时通过详尽的测试找到这些错误也越来越昂贵，其极限是对所有可能的输入进行详尽的测试。

此外，还可以查看此前在此处发布的答案（厚颜无耻的插入），以获取更多信息和有关全对和 PICT 工具的链接。

示例 PICT 模型文件

给定的模型生成 93 个测试用例，覆盖了所有输入参数的所有对。

#
# This is a PICT  model for testing a complex state machine at work 
#

CurrentState  :0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
Source        :1,2
Request       :True, False
Type          :True, False
Status        :State1, State2, State3
Handling      :State1, State2, State3
Completed     :True,False

#
# One can add constraints to the model to exclude impossible 
# combinations if needed.
#
# For example:
# IF [Completed]="True" THEN CurrentState>15;
#

#
# This is the PICT output of "pict ComplexStateMachine.pict /s /r1"
#
# Combinations:    515
# Generated tests: 93

- Lieven Keersmaekers

Answer 3

你认为用多少个测试才能“完全”测试函数sum(int a, int b)？在C#中，它将需要大约18446744056529682436个测试...比您的情况要糟糕得多。

我建议以下操作：

1. 测试最可能的情况和边界条件。
2. 单独测试你的软件系统中一些关键部分。
3. 在QA或生产环境中发现漏洞时，添加测试用例。

在这种特定情况下，最好的方法是测试系统从一个状态切换到另一个状态的方式。创建DSL以测试状态机，并使用它实现最常见的用例。例如：

Start
  .UploadDocument("name1")
  .SendDocumentOnReviewTo("user1")
  .Review()
  .RejectWithComment("Not enough details")
  .AssertIsCompleted()

这里有一个为流程创建简单测试的示例：http://slmoloch.blogspot.com/2009/12/design-of-selenium-tests-for-aspnet_09.html

- Yauheni Sivukha

Answer 4

我无法想出任何简单的方法来测试这样的FSM，而不是变得非常严谨并使用证明，使用机器学习技术或者暴力破解。

暴力破解： 编写一个可以以某种声明性方式生成所有4320个测试用例的工具，其中大多数数据都是错误的。建议将此放入CSV文件中，然后使用类似NUnits参数测试的工具加载所有测试用例。 现在，这些测试用例中的大部分都会失败，因此您必须手动更新声明性文件以使其正确，并随机选择一些测试用例进行修复。

机器学习技术： 您可以采用一些向量机或MDA算法/启发式方法来尝试从上面提到的样本中学习，并教授您的ML程序FSM。然后，在所有4320个输入上运行算法，并查看两者不同之处。

- Adam Gent

Answer 5

使用 SpecExplorer 或 NModel。

- Peli

Answer 6

我为一台医疗设备构建了一个有限状态机。FSM可以通过我定义的XML格式进行配置。

为了定义一个状态机，人们必须依靠数字电路设计经验使用状态映射。您需要使用我所称的转角过渡地图。在美国东海岸，大多数高速公路被昵称为转角。转角管理部门发布转角收费价格表。如果有一个50个出口的收费区段，定价表将有一个50行x 50列的表格，详细列出所有出口作为行和列。要查找进入20号出口并退出30号出口的收费，请简单地查找第20行和第30列的交叉点。

对于由30个状态组成的状态机，转角过渡地图将是一个30x30的矩阵，按行和列列出所有30个可能的状态。让我们决定将行作为当前状态，将列作为下一个状态。

每个相交的单元格将列出从当前状态（行）到下一个状态（列）的“价格”。但是，该单元格不会引用单个$值，而是会引用输入表中的一行，我们可以将其称为转换ID。

在我开发的医疗设备FSM中，有字符串、枚举、整数等输入。输入表按列列出这些输入刺激。

要构建输入表，您需要编写一个简单的例程来列出所有可能的输入组合。但是表格将非常巨大。对于您的情况，该表将具有4320行，因此具有4320个转换ID。但是它不是繁琐的表格，因为您通过编程生成了表格。在我的案例中，我编写了一个简单的JSP，以在浏览器上列出转换输入表（和转角表）或将其下载为csv以在MS Excel中显示。

构建这两个表格有两个方向。

1. 设计方向，在此方向中，您构建转角表的所有可能转换，将非可达转换变灰。然后仅针对每个可到达转换构造预期输入的所有输入表，其中行号为转换ID。每个转换ID被转录到转角过渡地图的相应单元格中。但是，由于FSM是稀疏矩阵，因此不会在转角过渡地图的单元格中使用所有转换ID。同样，一个转换ID可以多次使用，因为相同的转换条件可能适用于多个状态更改对。

2. 测试方向则是相反的，您需要构建输入表。您必须编写全面的过渡测试通用程序。该程序将首先读取一个过渡排序表，以将状态机带到入口点状态以启动测试周期。在每个当前状态下，它准备运行通过所有4320个转换ID。在转角过渡地图的当前状态行上，将有一个有限数量的有效下一个状态的列。

您希望测试程序循环遍历从输入表读取的4320行输入，以确保未使用的转换ID不会对当前状态产生影响。您想测试所有有效的转换ID是否为有效转换。

但是您无法这样做 - 因为一旦注入有效的转换，它会将机器的状态更改为下一个状态，并阻止您完成测试先前当前状态下的其余转换ID。一旦机器改变状态，您必须重新从转换ID 0开始测试。

转换路径可以是循环的、不可逆的或在路径上具有循环和不可逆部分的组合。

在测试例程中，您需要为每个状态注册以记忆最后一个注入到该状态的转换ID。每次测试到有效的转换ID时，该转换ID都会留在该寄存器中。因此，当您完成一个周期并返回到已经遍历过的状态时，您将从大于寄存器中存储的转换ID的下一个转换ID开始迭代。

您的例程必须注意转换路径的不可逆部分，当机器被带到最终状态时，它会从入口点状态重新启动测试，从大于状态的存储的一个状态的转换ID的下一个转换ID开始重新迭代4320个输入。通过这种方式，您将能够详尽地发现机器的所有可能转换路径。

幸运的是，有限状态机是有效转换的稀疏矩阵，因为详尽的测试不会消耗过渡ID数量x可能状态数量的完整组合。但是，如果您正在处理无法将视觉或温度状态反馈到测试系统的遗留FSM，则会出现困难，在这种情况下，您必须通过目视监测每个状态来进行额外的两周测试，仅通过有效转换。

如果您的FSM允许您通过简单重置和应用转换ID来达到入口点状态，则可能不需要转换序列表（供测试例程读取以将机器带到所需的入口点）。但是，具有能够读取转换序列表的例程很有用，因为通常需要进入状态网络的中间并从那里开始测试。

您应该熟悉转换和状态映射的使用，因为它非常有用，可以检测到机器的所有可能和未记录状态，并采访用户是否实际上希望将其变灰（使转换无效并使状态不可达）。

我拥有的优势是它是一台新设备，我可以选择设计状态机控制器以读取XML文件，这意味着我可以按照任何方式改变状态机的行为，实际上是客户想要的任何方式，并且我能够确保未使用的转换ID确实是无效的。

有限状态机控制器的Java清单为http://code.google.com/p/synthfuljava/source/browse/#svn/trunk/xml/org/synthful。未包含测试例程。

- Blessed Geek

Answer 7

根据要求进行测试。如果需要在Completed为true时将某个特定状态转移到另一个特定状态，则编写一个测试，自动循环遍历所有其他输入的组合（这应该只是一些for循环），以证明其他输入被正确忽略。您应该最终得到每个转换弧的一个测试，我估计大约会有100或150个测试，而不是4000个。

- Ben Voigt

Answer 8

你可以考虑研究基于模型的测试。在这种情况下，有一些可用的工具可以帮助测试生成。我通常推荐MBT。

- breaks_software

Answer 9

暴力破解和覆盖测试似乎是一个非常初级的方法。

- Gutzofter