我最近意识到正则表达式拒绝服务攻击，并决定在我的代码库中找到所谓的“邪恶”正则表达式模式——或者至少是那些用于用户输入的模式。上面的OWASP 链接和维基百科中给出的示例很有帮助，但它们并不能很好地用简单的术语解释问题。
来自维基百科的邪恶正则表达式的描述：
再举个例子，来自维基百科：
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+(.*a){x}对于 x > 10这是一个没有更简单解释的问题吗？我正在寻找一些可以在编写正则表达式时更容易避免这个问题的东西，或者在现有代码库中找到它们。
因为计算机完全按照你告诉他们的去做，即使这不是你的意思或者完全不合理。如果您要求正则表达式引擎证明，对于某些给定的输入，给定模式匹配或不匹配，那么无论必须测试多少不同的组合，引擎都会尝试这样做。
这是一个简单的模式，灵感来自 OP 帖子中的第一个示例：
^((ab)*)+$
给定输入：
abababababababababababab
正则表达式引擎尝试类似的东西，(abababababababababababab)并在第一次尝试时找到匹配项。
但随后我们把活动扳手扔进去：
ababababababababababababa _
引擎将首先尝试(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)- 没有
(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 Turing 证明无法解决的停机问题。我自己写了有问题的正则表达式，尽管我知道它们是什么以及通常如何避免它们。将你能做的一切都包装在一个原子组中有助于防止回溯问题。它基本上告诉正则表达式引擎不要重新访问给定的表达式 - “锁定第一次尝试匹配的任何内容”。但是请注意，原子表达式不会阻止表达式内的回溯，因此^(?>((ab)*)+)$仍然很危险，但^(?>(ab)*)+$很安全（它会匹配(abababababababababababab)然后拒绝放弃任何匹配的字符，从而防止灾难性的回溯）。
不幸的是，一旦编写完成，实际上很难立即或快速找到有问题的正则表达式。最后，识别错误的正则表达式就像识别任何其他错误代码一样- 它需要大量时间和经验和/或单个灾难性事件。
有趣的是，自从第一次写出这个答案以来，德克萨斯大学奥斯汀分校的一个团队发表了一篇论文，描述了一种能够对正则表达式进行静态分析的工具的开发，其明确目的是发现这些“邪恶”模式。该工具是为分析 Java 程序而开发的，但我怀疑未来几年我们会看到更多工具围绕分析和检测 JavaScript 和其他语言中的问题模式而开发，尤其是在ReDoS 攻击率持续攀升的情况下。
静态检测使用正则表达式的程序中的 DoS 漏洞
Valentin Wüstholz、Oswaldo Olivo、Marijn JH Heule 和 Isil Dillig
德克萨斯大学奥斯汀分校
What you call an "evil" regex is a regex that exhibits catastrophic backtracking. The linked page (which I wrote) explains the concept in detail. Basically, catastrophic backtracking happens when a regex fails to match and different permutations of the same regex can find a partial match. The regex engine then tries all those permutations. If you want to go over your code and inspect your regexes these are the 3 key issues to look at:
Alternatives must be mutually exclusive. If multiple alternatives can match the same text then the engine will try both if the remainder of the regex fails. If the alternatives are in a group that is repeated, you have catastrophic backtracking. A classic example is (.|\s)* to match any amount of any text when the regex flavor does not have a "dot matches line breaks" mode. If this is part of a longer regex then a subject string with a sufficiently long run of spaces (matched by both . and \s) will break the regex. The fix is to use (.|\n)* to make the alternatives mutually exclusive or even better to be more specific about which characters are really allowed, such as [\r\n\t\x20-\x7E] for ASCII printables, tabs, and line breaks.
Quantified tokens that are in sequence must either be mutually exclusive with each other or be mutually exclusive what comes between them. Otherwise both can match the same text and all combinations of the two quantifiers will be tried when the remainder of the regex fails to match. A classic example is a.*?b.*?c to match 3 things with "anything" between them. When c can't be matched the first .*? will expand character by character until the end of the line or file. For each expansion the second .*? will expand character by character to match the remainder of the line or file. The fix is to realize that you can't have "anything" between them. The first run needs to stop at b and the second run needs to stop at c. With single characters a[^b]*+b[^c]*+c is an easy solution. Since we now stop at the delimiter, we can use possessive quantifiers to further increase performance.
A group that contains a token with a quantifier must not have a quantifier of its own unless the quantified token inside the group can only be matched with something else that is mutually exclusive with it. That ensures that there is no way that fewer iterations of the outer quantifier with more iterations of the inner quantifier can match the same text as more iterations of the outer quantifier with fewer iterations of the inner quantifier. This is the problem illustrated in JDB's answer.
While I was writing my answer I decided that this merited a full article on my website. This is now online too.
邪恶的正则表达式总是由于相应的 NFA 中的歧义，您可以使用regexper等工具对其进行可视化。
这里有一些模棱两可的形式。不要在你的正则表达式中使用这些。
(a+)+（又名“星高 > 1”）。这可能会导致指数级爆炸。请参阅子堆栈的safe-regex工具。(a|a)+. 这可能会导致指数级爆炸。\d+\d+. 这可能导致多项式爆炸。我写了这篇关于超线性正则表达式的论文。它包括对其他正则表达式相关研究的大量参考。
我将其总结为“重复的重复”。您列出的第一个示例是一个很好的示例，因为它指出“字母 a，连续出现一次或多次。这可能会再次连续发生一次或多次”。
在这种情况下要查找的是量词的组合，例如 * 和 +。
需要注意的更微妙的事情是第三个和第四个。这些示例包含一个 OR 操作，其中双方都可以为真。这与表达式的量词相结合可以根据输入字符串产生大量潜在匹配。
总而言之，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 问题。目前没有办法有效地处理它们，您可能希望在输入中禁止它们。
我不认为你可以识别这样的正则表达式，至少不是所有的，或者在没有限制性地限制它们的表达性的情况下。如果您真的关心 ReDoS，我会尝试将它们沙箱化并在超时时终止它们的处理。也可能存在允许您限制其最大回溯量的 RegEx 实现。
我可以想到一些方法，您可以通过在小型测试输入上运行它们或分析正则表达式的结构来实现一些简化规则。
(a+)+可以使用某种规则将冗余运算符替换为仅(a+)([a-zA-Z]+)*也可以使用我们新的冗余组合规则简化为([a-zA-Z]*)计算机可以通过针对随机生成的相关字符序列或字符序列运行正则表达式的小子表达式来运行测试，并查看它们最终都属于哪些组。对于第一个，计算机就像，嘿，正则表达式想要一个，所以让我们尝试一下6aaaxaaq。然后它看到所有的 a，只有第一个 groupm 最终在一个组中，并得出结论，无论有多少 a，都没有关系，因为+get all 在组中。第二个，就像，嘿，正则表达式想要一堆字母，所以让我们尝试一下-fg0uj=，然后它再次看到每一束都在一个组中，所以它在+最后去掉了。
现在我们需要一个新规则来处理下一个规则：消除无关选项规则。
有了(a|aa)+，计算机看了看它，就像，我们喜欢第二个大的，但我们可以用第一个来填补更多的空白，让我们尽可能多地获得 aa，看看我们是否能获得其他任何东西在我们完成之后。它可以针对另一个测试字符串运行它，例如“eaaa@a~aa”。来确定。
您可以(a|a?)+通过让计算机意识到匹配的字符串a?不是我们正在寻找的机器人来保护自己，因为它总是可以匹配任何地方，我们决定我们不喜欢类似的东西(a?)+，然后把它扔掉。
我们(.*a){x}通过让它意识到匹配的字符a已经被.*. 然后我们丢弃那部分并使用另一个规则来替换 中的冗余量词(.*){x}。
虽然实现这样的系统会非常复杂，但这是一个复杂的问题，可能需要复杂的解决方案。您还应该使用其他人提出的技术，例如只允许正则表达式有限数量的执行资源，然后如果它没有完成则杀死它。