我怎样才能认出一个邪恶的正则expression式？
我最近才意识到正则expression式拒绝服务攻击，并决定在我的代码库中find所谓的“邪恶”正则expression式模式，或者至less那些在用户input中使用的模式。 上面的OWASP链接和维基百科上给出的例子是有帮助的，但是他们并没有用简单的术语来解释这个问题。
邪恶的正则expression式的描述，从维基百科 ：
- 正则expression式将复制（“+”，“*”）应用于复杂的子expression式;
- 对于重复的子expression式，存在一个匹配，也是另一个有效匹配的后缀。
再用wikipedia的例子：
(a+)+-
([a-zA-Z]+)* -
(a|aa)+ -
(a|a?)+ -
(.*a){x}for x> 10
这是一个没有简单解释的问题吗？ 我正在寻找一些能够在编写正则expression式时避免这个问题，或者在现有的代码库中find它们的东西。
为什么邪恶的正则expression式是一个问题？
因为电脑完全按照你的意思去做，即使这不是你的意思，也不是完全不合理的。 如果你要求一个正则expression式引擎来certificate，对于一些给定的input，对于一个给定的模式，或者是或者不是匹配，那么引擎就会尝试这样做，不pipe有多less个不同的组合必须被testing。
这是一个简单的模式，受到OP的第一个例子的启发：
^((ab)*)+$
鉴于input：
abababababababababababab
正则expression式引擎尝试类似于(abababababababababababab)并在第一次尝试中find匹配项。 这就像要求生物学家certificate马不存在一样。 生物学家可以迅速提供证据，certificate问题已经解决。
但是，我们把这只猴子扳手放在：
abababababababababababab a
引擎将首先尝试(abababababababababababab)但由于多余的a失败。 这就像要求生物学家certificate独angular兽不存在一样，这更难。 生物学家必须search每个可能的地点，一个独angular兽可能存在，只能宣布，如果所有地点certificate是空的，他们不存在。 对于我们的正则expression式引擎，看起来像这样：
(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)– Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab)– Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab)
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)– Nope
(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)
可能的组合的数量与input的长度成指数关系，在你知道它之前，正则expression式引擎正在耗尽你所有的系统资源来试图解决这个问题，直到用尽了所有可能的组合条件，它终于放弃了报告“没有匹配”。 同时你的服务器已经变成了一堆熔化的金属。 （有趣的是，这基本上是一个密码暴力破解者的工作原理，因为这是同一类问题 。）
如何发现邪恶的正则expression式
这实际上非常棘手。 我自己也写了一对夫妇，尽pipe我知道他们是什么，一般来说如何避免他们。 看Regex花了很长时间 。 包装一切你可以在一个primefaces组可以帮助防止回溯问题。 它基本上告诉正则expression式引擎不要重新访问给定的expression式 – “locking你在第一次尝试时匹配的任何东西”。 但是请注意，primefacesexpression式不会阻止expression式中的回溯，所以(?>.*.*)仍然是危险的，但是(?>.*)(?>.*)是安全的。
不幸的是，一旦它被写入，实际上很难立即或迅速地发现一个正则expression式的问题。 最后， 认识到一个糟糕的正则expression式就像识别其他任何不好的代码一样 – 这需要花费大量的时间和经验和/或一个灾难性的事件。
我将其归纳为“重复重复”。 你列出的第一个例子是一个很好的例子，因为它表示“字母a，连续一次或多次，这可能再次发生一次或多次”。
在这种情况下要查找的是量词的组合，如*和+。
要注意的是第三和第四个更微妙的东西。 这些例子包含一个OR操作，双方都可以是真实的。 这与expression式的量词相结合可能会导致大量的潜在匹配取决于inputstring。
总结起来，TLDR式：
请小心如何与其他操作员一起使用量词。
我有惊人的发现ReDOS不less次执行源代码评论。 我build议的一件事是使用任何正则expression式引擎，您正在使用超时。
例如，在C＃中，我可以使用TimeSpan属性创build正则expression式。
string pattern = @"^<([az]+)([^<]+)*(?:>(.*)<\/\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"); }
这个正则expression式容易受到拒绝服务，没有超时会旋转和吃资源。 在超时之后，它会在给定的超时之后抛出一个RegexMatchTimeoutException ，并且不会导致导致拒绝服务条件的资源使用情况。
您将需要尝试超时值，以确保它适用于您的使用。
你所说的“邪恶的”正则expression式是一种performance出灾难性回溯的正则expression式。 链接页面（我写的）详细解释了这个概念。 基本上，灾难性的回溯发生在正则expression式不匹配时，同一个正则expression式的不同排列可以find部分匹配。 正则expression式引擎然后尝试所有这些排列。 如果你想检查你的代码并检查你的正则expression式，这些是需要看到的三个关键问题：
-
替代品必须是相互排斥的。 如果多个选项可以匹配相同的文本，那么如果正则expression式的其余部分失败，引擎将尝试这两个选项。 如果替代scheme是在一个重复的组中，那么就会出现灾难性的回溯。 一个经典的例子是
(.|\s)*匹配正则expression式中没有“点匹配换行符”模式的任意数量的文本。 如果这是一个较长的正则expression式的一部分，那么一个足够长的空间运行（由.和\s匹配）的主题string将打破正则expression式。 解决方法是使用(.|\n)*使替代方法相互排斥，甚至更好地明确哪些字符是真正允许的，例如ASCII printables的[\r\n\t\x20-\x7E]，制表符和换行符。 -
量化的令牌必须是相互排斥的，或者是相互排斥的。 否则，两者都可以匹配相同的文本，当正则expression式的其余部分不匹配时，将尝试两个量词的所有组合。 一个典型的例子是
a.*?b.*?c匹配三个事物与他们之间的“任何事物”。 当c不能匹配第一个.*?将逐字符扩展直到行或文件的结尾。 对于每个扩展第二.*?将逐字符扩展以匹配行或文件的其余部分。 解决的办法是意识到你不能有他们之间的“任何东西”。 第一次运行需要停在b，第二次运行需要停在c。 对于单个字符a[^b]*+b[^c]*+c是一个简单的解决scheme。 既然我们现在停止了分隔，我们可以使用占有量词来进一步提高性能。 -
包含带有量词的标记的组必须没有自己的量词，除非组内的量化标记只能与其他与其互斥的其他标记匹配。 这确保了内部量词具有更多迭代的外部量词的更less迭代可以与相同文本与外部量词的更多迭代相匹配，而内部量词的迭代更less。 JDB的答案就是这个问题。
当我在写我的答案时，我决定这在我的网站上有一篇完整的文章 。 这现在也在线上。
我不认为你能认识到这样的正则expression式，至less不是所有这些正则expression式都没有限制性的expression。 如果你真的关心ReDoS，我会尝试对它们进行沙盒（sandbox），并在超时后终止处理。 也有可能有RegEx的实现，让你限制他们的最大回溯量。
我会说这与正在使用的正则expression式引擎有关。 你可能并不总是能够避免这些types的正则expression式，但是如果你的正则expression式引擎是正确的，那么它就不是什么问题。 看到这个博客系列有关正则引擎主题的大量信息。
请注意文章底部的警告，回溯是一个NP完全问题。 目前没有办法有效地处理它们，你可能想在你的input中禁止它们。
有一些方法我可以想到，你可以通过在小的testinginput上运行它们或分析正则expression式的结构来实现一些简化规则。
-
(a+)+可以减less使用某种规则来取代冗余运算符(a+) -
([a-zA-Z]+)*也可以用我们的新的冗余组合规则简化为([a-zA-Z]*)
计算机可以通过运行正则expression式的小子expression式来对相关字符或字符序列的随机生成的序列进行运行testing，并查看它们都结束了什么组。对于第一个，计算机就像是，正则expression式想要一个，所以让我们尝试与6aaaxaaq 。 然后它看到所有的a，只有第一个小组落在一个小组中，并且得出结论：无论放多less个a，都不会有问题，因为+都是在小组中。 第二个是，嘿，正则expression式需要一串字母，所以让我们用-fg0uj=来-fg0uj= ，然后再看到每一串都在一个组中，所以它最终摆脱了+ 。
现在我们需要一个新的规则来处理下一个规则：消除不相关的选项规则。
-
用
(a|aa)+，计算机看看它，就像我们喜欢那个大的第二个，但是我们可以用第一个填补更多的空白，让我们尽可能多的aa，看看如果我们完成后我们可以得到任何其他的东西。 它可以运行在另一个testingstring上，比如`eaaa @ a〜aa'。 以确定。 -
你可以通过让计算机意识到string与
(a|a?)+匹配， 是不是我们正在寻找的机器人，因为它可以随时随地匹配，我们决定，我们不喜欢像(a?)+东西，并把它扔出去。 -
我们用
(.*a){x}来保护它们，使其认识到由a匹配的字符已经被抢占了。 然后，我们抛出该部分，并使用另一个规则来replace(.*){x}的冗余量词。
虽然实施这样的系统会非常复杂，但这是一个复杂的问题，可能需要一个复杂的解决scheme。 你也应该使用其他人提出的技术，比如仅仅允许正则expression式中的一些有限的执行资源，如果它没有完成就被杀死。
我知道两个开源工具试图回答这个问题。
rxxr2是一个学术项目。 safe-refex是一个开源项目。
这些工具都不是准确的，每一个都能识别出真正的弱势正则expression式，而另一些则没有。 我在最近的论文中提供了一些提示。
