上一个主题解释了灾难性回溯，并从尝试让正则表达式在自己的电脑上正常工作并获得良好性能的人的角度提供了实际示例。在阅读本主题之前，您应该理解这些示例。

在您的电脑上发生灾难性回溯时会很烦人。但当它发生在具有多个并发用户的服务器应用程序中时，它确实会造成灾难。运行表现出灾难性回溯的正则表达式的用户过多会导致整个服务器崩溃。而“过多”只需要和服务器中的 CPU 内核数量一样少即可。

如果服务器接受用户的正则表达式，则用户可以轻松地提供一个在任何主题上表现出灾难性回溯的正则表达式。如果服务器接受用户的主题数据，则用户可能能够提供触发服务器使用的正则表达式中灾难性回溯的主题，如果这些正则表达式容易发生灾难性回溯。当用户可以执行上述任一操作时，服务器容易受到正则表达式拒绝服务 (ReDoS) 的影响。当足够多的用户（或一个冒充多个用户的参与者）提供恶意正则表达式和/或要匹配的主题时，服务器将花费几乎所有 CPU 周期来尝试匹配这些正则表达式。

处理用户提供的正则表达式

如果您的应用程序允许用户提供自己的正则表达式，那么您唯一真正的防御措施是使用文本定向正则表达式引擎。这些引擎不会回溯。它们的性能取决于主题字符串的长度，而不是正则表达式的复杂性。但它们也不支持依赖于回溯且许多用户期望的反向引用等功能。

如果您的应用程序使用带有用户提供的正则表达式的回溯引擎，那么您只能减轻灾难性回溯的后果。而且您真的需要这样做。对于正则表达式技能有限的人来说，很容易意外地制作出退化为灾难性回溯的正则表达式。

您需要使用一个正则表达式引擎，当发生灾难性回溯时中止匹配尝试，而不是一直运行直到脚本崩溃或操作系统将其终止。您可以轻松地测试这一点。当正则表达式 (x\w{1,10})+y 在不断增长的 x 字符串上尝试时，正则表达式引擎放弃的时间应该有一个合理的限制。理想情况下，您的引擎将允许您根据自己的目的配置此限制。例如，.NET 引擎允许您将超时传递给 Regex() 构造函数。PCRE 引擎允许您设置递归限制。限制越低，对 ReDoS 的保护就越好，但中止会找到有效匹配的合法正则表达式的风险就越高，即使给它更多时间。较低的递归限制可能会阻止较长的正则表达式匹配。较低的超时可能会过早地中止对大文件的搜索。

如果您的正则表达式引擎没有此类功能，您可以实现自己的超时。生成一个单独的线程来执行正则表达式。使用超时等待线程。如果线程在等待超时之前完成，则处理其结果。否则，终止线程并告诉用户正则表达式太复杂。safe_regexp 包为 Ruby 实现了这一点。

审查应用程序中的正则表达式

如果服务器仅使用应用程序中硬编码的正则表达式，那么您可以完全防止基于正则表达式的拒绝服务攻击。您需要确保您的正则表达式不会表现出灾难性回溯，无论它们用于哪些主题。对于一个牢固掌握正则表达式的人来说，这并不是特别困难。但这确实需要小心和注意。仅仅测试正则表达式是否匹配有效主题是不够的。您需要通过独立于任何主题数据查看正则表达式来确保同一正则表达式的多个排列不可能匹配相同的事物。

当您给正则表达式一个选择时，就会发生排列。您可以使用 交替 和 量词 来实现这一点。因此，这些是您需要检查的正则表达式标记。占有 量词除外，因为它们从不回溯。

交替

备选方案必须互斥。如果多个备选方案可以匹配相同的文本，那么如果正则表达式的其余部分失败，引擎将尝试两者。如果备选方案在重复的组中，则会出现灾难性回溯。

一个经典的例子是 (.|\s)*，它在正则表达式风格没有“点匹配换行符”模式时匹配任意数量的任意文本。如果这是更长正则表达式的一部分，那么包含足够长空格运行的主题字符串会破坏正则表达式。引擎将尝试 . 或 \s 匹配的空格的每种可能组合。例如，3 个空格可以匹配为 ...、..\s、.\s.、.\s\s、\s..、\s.\s、\s\s. 或 \s\s\s。这是 2^N 个排列。解决方法是使用 (.|\n)* 使备选方案互斥。最好更具体地说明哪些字符确实允许，例如 [\r\n\t\x20-\x7E]*，用于 ASCII 可打印字符、制表符和换行符。

两个备选方案部分匹配相同文本是可以接受的。 [0-9]*\.[0-9]+|[0-9]+ 完全可以匹配具有可选整数部分和可选分数部分的浮点数。虽然仅由数字组成的主题最初由 [0-9]* 匹配，并且在 \. 失败时确实会导致一些回溯，但此回溯永远不会变得灾难性。即使你将其放入更长正则表达式中的组中，该组也只会执行最少量的回溯。（但该组不能有量词，否则它将违反嵌套量词的规则。）

序列中的量词

按顺序排列的量化标记必须相互排斥，或与它们之间的内容相互排斥。否则，两者都可以匹配相同的文本，并且当正则表达式的其余部分无法匹配时，将尝试这两个量词的所有组合。交替组中的标记仍然与组之前或之后的任何标记按顺序排列。

一个经典的例子是 a.*?b.*?c，用于匹配 3 个内容，它们之间有“任何内容”。当无法匹配 c 时，第一个 .*? 将逐个字符扩展，直到行尾或文件尾。对于每次扩展，第二个 .*? 将逐个字符扩展，以匹配行尾或文件尾的其余部分。解决办法是意识到它们之间不能有“任何内容”。第一次运行需要在 b 处停止，第二次运行需要在 c 处停止。对于单个字符，a[^b]*b[^c]*c 是一个简单的解决方案。取反的字符类保证重复在分隔符处停止。如果您的正则表达式风格支持 占有量词，那么您可以使用 a[^b]*+b[^c]*+c 进一步提高性能。

有关更复杂的示例和解决方案，请参阅前一个主题中的 匹配完整的 HTML 文件。这解释了如何在更复杂的情况下使用原子分组来防止回溯。

嵌套量词

包含带量词的标记的组不能有自己的量词，除非组内的量化标记只能与与其互斥的其他内容匹配。这可确保不会出现外层量词的较少迭代与内层量词的较多迭代匹配与外层量词的较多迭代与内层量词的较少迭代匹配相同文本的情况。

正则表达式 (x\w{1,10})+y 匹配一个或多个以 x 开头，后跟 1 到 10 个单词字符，最后跟一个 y 的代码序列。只要能匹配 y，一切都没问题。当 y 缺失时，会发生回溯。如果字符串没有太多 x，那么回溯会非常快。只有当主题包含一个很长的 x 序列时，情况才会变得灾难性。x 和 x 不是互斥的。因此，重复组可以在一次迭代中匹配 xxxx，如 x\w\w\w，或在两次迭代中匹配 x\wx\w。

要解决这个问题，首先需要考虑是否允许在 x 和 y 之后的 1 到 10 个字符中出现。排除 x 可以消除大部分回溯。剩下的不会造成灾难。可以使用 字符类减法 来排除它，如 (x[\w-[x]]{1,10})+y，或者使用 字符类交集 来排除它，如 (x[\w&&[^x]]{1,10})+y。如果没有这些功能，则需要拼出要允许的字符：(x[a-wyz0-9_]{1,10})+y。

如果允许 x，那么唯一的解决方案就是以同样的方式禁止 y。然后，可以使组原子化或使量词所有化以消除回溯。

如果在 1 到 10 个字符的序列中都允许 x 和 y，那么就没有仅使用正则表达式的解决方案。不能使组原子化或使量词所有化，因为这样 \w{1,10} 会匹配最终的 y，从而导致 y 失败。

其他防御技术

除了防止灾难性回溯（如上所述）之外，还应尽可能严格地制定正则表达式。正则表达式越严格，执行的回溯就越少，因此性能越好。即使无法衡量性能差异，因为正则表达式在短字符串上使用频率很低，但正确的技术是一种习惯。它还可以减少经验较少的开发人员在以后扩展正则表达式时引入灾难性回溯的可能性。

尽可能将包含备选方案的组设为原子组。使用 \b(?>one|two|three)\b 匹配一个单词列表。

尽可能使量词占有。如果一个重复标记与后续内容互斥，请使用占有量词强制执行。

使用（否定）字符类而不是点。很少需要真正允许“任何内容”。例如，一个双引号字符串不能包含“任何内容”。它不能包含未转义的双引号。因此，使用 "[^"\n]*+" 而不是 ".*?"。尽管两者在单独使用时找到完全相同的匹配项，但当粘贴到较长的正则表达式中时，后者会导致灾难性的回溯。无论正则表达式需要匹配什么其他内容，前者永远不会回溯。

为什么要使用正则表达式？

有些人肯定会争辩说，上述内容只表明正则表达式很危险，不应使用。然后，他们会强迫开发人员使用过程代码来完成这项工作。用于匹配非平凡模式的过程代码很快变得冗长而复杂，增加了出现错误的可能性以及开发和维护代码的成本。许多模式匹配问题都可以通过递归自然解决。当无法匹配一个较大的主题字符串时，失控的递归会导致堆栈溢出，从而使应用程序崩溃。

开发人员需要学会正确使用他们的工具。这对正则表达式与其他任何事物没有什么不同。