我最近意识到正则表达式拒绝服务攻击，并决定根除所谓的"邪恶"正则表达式模式，只要我在我的代码库中找到它们 - 或者至少那些用于用户输入的模式。上面OWASP链接和维基百科上给出的例子很有帮助，但它们在用简单的术语解释问题方面做得不好。
来自维基百科的邪恶正则表达式的描述：
- 正则表达式将重复("+"、"*")应用于复杂子表达式;
- 对于重复的子表达式，存在一个匹配项，该匹配项也是另一个有效匹配项的后缀。
举个例子，再次来自维基百科：
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+- x> 10 的
(.*a){x}
这是一个没有更简单解释的问题吗？我正在寻找一些东西，以便在编写正则表达式时更容易避免此问题，或者在现有代码库中找到它们。
为什么邪恶的正则表达式是一个问题？
因为计算机完全按照你告诉它们做的事情去做，即使这不是你的意思或完全不合理。如果您要求正则表达式引擎证明，对于某些给定的输入，给定模式匹配或不匹配，那么无论必须测试多少种不同的组合，引擎都会尝试这样做。
这是一个受OP帖子中第一个示例启发的简单模式：
^((ab)*)+$
给定输入：
阿巴
正则表达式引擎尝试类似(abababababababababababab)的东西，并在第一次尝试时找到匹配项。
但随后我们把猴子扳手扔进去：
阿巴
引擎将首先尝试(abababababababababababab)但由于额外的a而失败。这会导致灾难性的回溯，因为我们的模式(ab)*，为了表示诚意，将释放其捕获之一(它将"回溯")并让外部模式重试。对于我们的正则表达式引擎，它看起来像这样：
(abababababababababababab)- 不(ababababababababababab)(ab)- 不(abababababababababab)(abab)- 不(abababababababababab)(ab)(ab)- 不(ababababababababab)(ababab)- 不(ababababababababab)(abab)(ab)- 不(ababababababababab)(ab)(abab)- 不(ababababababababab)(ab)(ab)(ab)- 不(abababababababab)(abababab)- 不(abababababababab)(ababab)(ab)- 不<"br/>(abababababababab)(abab)(abab)- 不(abababababababab)(abab)(ab)(ab)- 不(abababababababab)(ab)(ababab)- 不(abababababababab)(ab)(abab)(ab)- 不(abababababababab)(ab)(ab)(abab)- 不(abababababababab)(ab)(ab)(ab)(ab)- 不(ababababababab)(ababababab)- 不(ababababababab)(abababab)(ab)- 不>(ababababababab)(ababab)(abab)- 不(ababababababab)(ababab)(ab)(ab)- 不(ababababababab)(abab)(abab)(ab)- 不(ababababababab)(abab)(ab)(abab)- 不(ababababababab)(abab)(ab)(ab)(ab)- 不(ababababababab)(ab)(abababab)- 不(ababababababab)(ab)(ababab)(ab)- 不(ababababababab)(ab)(abab)(abab)- 不(ababababababab)(ab)(abab)(ab)(ab)- 不(ababababababab)(ab)(ab)(ababab)- 不(ababababababab)(ab)(ab)(abab)(ab)- 不(ababababababab)(ab)(ab)(ab)(abab)- 不(ababababababab)(ab)(ab)(ab)(ab)(ab)- 不
...(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)- 不(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)- 不可能的组合数量与输入的长度呈指数级增长，在您知道之前，正则表达式引擎正在消耗您试图解决这个问题的所有系统资源，直到用尽了所有可能的术语组合，它最终放弃并报告"没有匹配"。 与此同时，您的服务器已经变成了一堆燃烧的熔融金属。
如何发现邪恶的正则表达式
这实际上非常棘手。现代正则表达式引擎中的灾难性回溯在性质上类似于 Alan Tuuring 证明无法解决的停止问题。我自己写过有问题的正则表达式，即使我知道它们是什么以及如何避免它们。将所有内容包装在一个原子组中有助于防止回溯问题。它基本上告诉正则表达式引擎不要重新访问给定的表达式 - "锁定您在第一次尝试时匹配的任何内容"。但是请注意，原子表达式不会阻止表达式中的回溯，因此^(?>((ab)*)+)$仍然是危险的，但^(?>(ab)*)+$是安全的(它会匹配(abababababababababababab)然后拒绝放弃任何匹配的字符，从而防止灾难性的回溯)。
不幸的是，一旦编写出来，实际上很难立即或快速找到有问题的正则表达式。最后，识别一个错误的正则表达式就像识别任何其他错误的代码一样- 它需要大量的时间和经验和/或单个灾难性事件。
有趣的是，自从这个答案首次被写出来以来，德克萨斯大学奥斯汀分校的一个团队发表了一篇论文，描述了一种能够对正则表达式进行静态分析的工具的开发，其明确目的是找到这些"邪恶"模式。该工具是为分析Java程序而开发的，但我怀疑在未来几年，我们将看到围绕分析和检测JavaScript和其他语言中的问题模式开发更多工具，特别是随着ReDoS攻击率的不断攀升。
静态检测 中的 DoS 漏洞 使用正则表达式的程序
Valentin Wüstholz、Oswaldo Olivo、Marijn J. H. Heule 和 Isil Dillig
德克萨斯大学奥斯汀分校
检测恶意正则表达式
- 试试Nicolaas Weideman的RegexStaticAnalysis项目。
- 试试我的集成风格的vuln-regex-detector，它有一个用于Weideman工具和其他工具的CLI。
经验法则
邪恶的正则表达式总是由于相应 NFA 中的歧义，您可以使用正则表达式等工具将其可视化。
以下是一些形式的歧义。不要在正则表达式中使用这些。
- 嵌套量词，如
(a+)+(又名"星高> 1")。这可能会导致指数爆炸。请参阅子堆栈的safe-regex工具。 - 量化的重叠析取，如
(a|a)+.这可能会导致指数爆炸。 - 避免量化的重叠邻接，如
d+d+。这可能会导致多项式爆炸。
其他资源
我写了这篇关于超线性正则表达式的论文。它包括对其他正则表达式相关研究的大量引用。
你所说的"邪恶"正则表达式是一个表现出灾难性回溯的正则表达式。 链接页面(我写的)详细解释了这个概念。 基本上，当正则表达式不匹配并且同一正则表达式的不同排列可以找到部分匹配时，就会发生灾难性回溯。 然后，正则表达式引擎会尝试所有这些排列。 如果您想检查代码并检查正则表达式，以下是要考虑的 3 个关键问题：
-
备选办法必须是相互排斥的。 如果多个替代项可以匹配相同的文本，那么如果正则表达式的其余部分失败，引擎将尝试两者。 如果替代方案位于重复的组中，则会出现灾难性的回溯。 一个经典的例子是
(.|s)*当正则表达式风格没有"点匹配换行符"模式时匹配任意数量的任何文本。 如果这是较长正则表达式的一部分，那么具有足够长的空格(由.和s匹配)的主题字符串将破坏正则表达式。 解决方法是使用(.|n)*使替代项相互排斥，甚至更好地更具体地说明真正允许的字符，例如 ASCII 可打印内容、制表符和换行符的[rntx20-x7E]。 -
按顺序排列的量化代币必须彼此互斥，或者它们之间相互排斥。 否则，两者都可以匹配相同的文本，并且当正则表达式的其余部分不匹配时，将尝试两个量词的所有组合。 一个典型的例子是
a.*?b.*?c将 3 个事物与它们之间的"任何东西"相匹配。当c不匹配时，第一个.*?将逐个字符展开，直到行或文件的末尾。 对于每个扩展，第二个.*?将逐个字符扩展以匹配行或文件的其余部分。 解决方法是要意识到它们之间不能有"任何东西"。 第一次运行需要在b处停止，第二次运行需要在c处停止。 使用单个字符a[^b]*+b[^c]*+c是一个简单的解决方案。 由于我们现在停在分隔符处，因此我们可以使用所有格量词来进一步提高性能。 -
包含带有量词的令牌的组不得具有自己的量词，除非组中的量化令牌只能与与其互斥的其他内容匹配。 这确保了外部量词的较少迭代与内部量词的更多迭代无法与外部量词的更多迭代与内部量词的较少迭代匹配相同的文本。 这是JDB的回答中说明的问题。
当我写我的答案时，我决定这值得在我的网站上写一篇完整的文章。 现在也在线了。
我会把它总结为"重复的重复"。您列出的第一个例子是一个很好的例子，因为它指出"字母a，连续一次或多次。这种情况可能再次连续发生一次或多次"。
在这种情况下要寻找的是量词的组合，例如 * 和 +。
需要注意的更微妙的事情是第三个和第四个。这些示例包含一个 OR 操作，其中双方都可以为 true。这与表达式的量词相结合可能会导致大量潜在匹配项，具体取决于输入字符串。
总结一下，TLDR风格：
请注意量词与其他运算符结合使用的方式。
我惊讶地遇到过很多次 ReDOS 执行源代码审查。我建议的一件事是对您正在使用的任何正则表达式引擎使用超时。
例如，在 C# 中，我可以创建具有TimeSpan属性的正则表达式。
string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)</1>|s+/>)$";
Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0));
try
{
string noTags = regexTags.Replace(description, "");
System.Console.WriteLine(noTags);
}
catch (RegexMatchTimeoutException ex)
{
System.Console.WriteLine("RegEx match timeout");
}
此正则表达式容易受到拒绝服务的攻击，如果没有超时，将旋转并消耗资源。超时时，它将在给定超时后抛出RegexMatchTimeoutException，并且不会导致资源使用导致拒绝服务情况。
您需要试验超时值，以确保它适合您的使用。
我会说这与正在使用的正则表达式引擎有关。您可能并不总是能够避免这些类型的正则表达式，但是如果您的正则表达式引擎构建正确，那么问题就不大了。有关正则表达式引擎主题的大量信息，请参阅此博客系列。
请注意文章底部的警告，因为回溯是一个NP-Complete问题。目前无法有效地处理它们，您可能希望在输入中禁止它们。
我认为您无法识别此类正则表达式，至少不是全部，或者不会限制它们的表现力。如果你真的关心 ReDoSs，我会尝试将它们沙盒化并通过超时来终止它们的处理。也可能有一些正则表达式实现允许您限制其最大回溯量。
我能想到的一些方法可以通过在小型测试输入上运行它们或分析正则表达式的结构来实现一些简化规则。
- 可以使用某种规则来减少
(a+)+，以将冗余运算符替换为仅(a+) ([a-zA-Z]+)*也可以通过我们新的冗余组合规则来简化([a-zA-Z]*)
计算机可以通过针对随机生成的相关字符序列或字符序列运行正则表达式的小子表达式来运行测试，并查看它们最终都属于哪些组。 对于第一个，计算机就像，嘿正则表达式想要一个，所以让我们用6aaaxaaq试试。 然后，它看到所有的a，只有第一个分组m最终在一个组中，并得出结论，无论有多少a被放置，都无关紧要，因为+在组中得到所有。 第二个，就像，嘿，正则表达式想要一堆字母，所以让我们用-fg0uj=试试，然后它再次看到每堆字母都在一组中，所以它最后去掉了+。
现在我们需要一个新规则来处理下一个规则：消除不相关的选项规则。
-
有了
(a|aa)+，计算机看了一眼，就像，我们喜欢第二个大，但我们可以使用第一个来填补更多的空白，让我们尽可能多地得到很多aa，看看我们完成后是否可以得到其他东西。 它可以针对另一个测试字符串运行它，如'eaaa@a~aa.'来确定这一点。 -
您可以通过让计算机意识到
a?匹配的字符串不是我们正在寻找的机器人来保护自己免受(a|a?)+，因为既然它总是可以在任何地方匹配，我们决定我们不喜欢像(a?)+这样的东西，然后把它扔掉。 -
我们通过让它意识到与
a匹配的角色已经被.*抓住来防止(.*a){x}。 然后我们抛弃该部分并使用另一个规则来替换(.*){x}中的冗余量词。
虽然实现这样的系统会非常复杂，但这是一个复杂的问题，可能需要复杂的解决方案。 您还应该使用其他人提出的技术，例如只允许正则表达式使用有限数量的执行资源，如果它没有完成，则在杀死它之前。