FSM 在任何时候都可以处于一种状态。状态集是有限的。当有限自动机从一种状态变为另一种状态时，就会发生转换。有限机器的一个例子是咖啡机，它根据用户的选择分配特定类型的咖啡。
前面提到，正则表达式比较可以通过构造FSM来完成。正则表达式也可以轻松地从有限自动机转换为非确定性自动机，特别是对于每个接收到的输入有多个可能的下一个状态的表达式。在这种情况下，在转换之后，正则表达式引擎可以使用多种算法来确定接下来的状态。然而，我们将重点关注最有问题的算法：
引擎尝试所有可能的路径，直到找到匹配项或所有路径都已尝试 分时度假业主名单 但失败（“回溯”）。这是有问题的，因为对于长度为 n 的输入，会遍历指数数量的路径，因此在最坏的情况下，运行时间为 O(n)=2^n。
引擎反过来尝试从非确定性自动化切换到确定性自动化。这是有问题的，因为根据执行路径，转换可能需要指数级的时间。
因此，当这两种算法中的任何一种应用于特定的正则表达式时，就会发生正则表达式拒绝服务。恶意用户可以利用此漏洞触发这两个条件中的任何一个，从而导致正则表达式引擎的运行时复杂性最差。
让我们考虑一个容易受到 DoS 攻击的正则表达式的示例。我们使用 CLI 工具 gnomon 在运行时分析命令。
启动您选择的控制台并安装它：
假设我们有一个模式，/^(\w+\s?)*$/其中包含一组单词，每个单词后面有一个可选空格。量词^and$指的是行首和行尾的单词。
现在让我们尝试一组没有特殊字符的单词。
我们看到单词匹配，并且在终端上运行此正则表达式花了 0.0058 秒。
现在让我们尝试造一个在最后一个单词末尾带有特殊字符的句子：
正如预期的那样，返回了 false，正则表达式的执行时间约为 0.0061 秒。
完美，一切正常。然而，问题在于正则表达式引擎可能需要很长时间才能执行包含特殊字符的较长句子的正则表达式。
让我们看看实际情况。在终端中运行以下命令：
此命令预计不会产生任何结果...如果我们打开任务管理器，我们可以看到相关进程正在使用很大一部分 CPU 来执行此正则表达式。事实上，我们应该看到当前总体 CPU 使用率急剧增加。