我如何识别邪恶的正则表达式？

Question

我最近意识到正则表达式拒绝服务攻击,并决定在我的代码库中找到所谓的"邪恶"正则表达式模式 - 或者至少在用户输入上使用它们.上面的OWASP链接和维基百科提供的示例很有帮助,但他们并没有很好地用简单的术语解释问题.

来自维基百科的邪恶正则表达式的描述:

• 正则表达式将重复("+","*")应用于复杂的子表达式;
• 对于重复的子表达式,存在一个匹配,它也是另一个有效匹配的后缀.

通过示例,再次来自维基百科:

• (a+)+
• ([a-zA-Z]+)*
• (a|aa)+
• (a|a?)+
• (.*a){x} 对于x> 10

这是一个没有更简单解释的问题吗？我正在寻找能够在编写正则表达式时更容易避免这个问题,或者在现有代码库中找到它们的东西.

Answer 1

为什么邪恶的正则表达式是一个问题？

因为计算机完全按照你的要求去做,即使它不是你的意思,也不完全是不合理的.如果您要求正则表达式引擎证明,对于某些给定的输入,要么存在或不匹配给定模式,那么无论必须测试多少种不同的组合,引擎都会尝试这样做.

这是一个简单的模式,受到OP帖子中第一个例子的启发:

^((ab)*)+$

鉴于输入:

abababababababababababab

正则表达式引擎尝试类似的东西,(abababababababababababab)并在第一次尝试时找到匹配.

但是我们把猴子扳手扔进:

abababababababababababab a

引擎将首先尝试,(abababababababababababab)但由于这个额外的失败a.这会导致灾难性的包围,因为我们的模式(ab)*,在善意的展示中,将释放其中一个捕获(它将"回溯")并让外部模式再次尝试.对于我们的正则表达式引擎,看起来像这样:

(abababababababababababab)- Nope
(ababababababababababab)(ab)- Nope
(abababababababababab)(abab)- Nope
(abababababababababab)(ab)(ab)- Nope
(ababababababababab)(ababab)- Nope
(ababababababababab)(abab)(ab)- Nope
(ababababababababab)(ab)(abab)- Nope
(ababababababababab)(ab)(ab)(ab)- Nope
(abababababababab)(abababab)- Nope
(abababababababab)(ababab)(ab)- Nope
(abababababababab)(abab)(abab)- Nope
(abababababababab)(abab)(ab)(ab)- Nope
(abababababababab)(ab)(ababab)- Nope
(abababababababab)(ab)(abab)(ab)- Nope
(abababababababab)(ab)(ab)(abab)- Nope
(abababababababab)(ab)(ab)(ab)(ab)- Nope
(ababababababab)(ababababab)- Nope
(ababababababab)(abababab)(ab)- Nope
(ababababababab)(ababab)(abab)- Nope
(ababababababab)(ababab)(ab)(ab)- Nope
(ababababababab)(abab)(abab)(ab)- Nope
(ababababababab)(abab)(ab)(abab)- Nope
(ababababababab)(abab)(ab)(ab)(ab)- Nope
(ababababababab)(ab)(abababab)- Nope
(ababababababab)(ab)(ababab)(ab)- Nope
(ababababababab)(ab)(abab)(abab)- Nope
(ababababababab)(ab)(abab)(ab)(ab)- Nope
(ababababababab)(ab)(ab)(ababab)- Nope
(ababababababab)(ab)(ab)(abab)(ab)- Nope
(ababababababab)(ab)(ab)(ab)(abab)- Nope
(ababababababab)(ab)(ab)(ab)(ab)(ab)- Nope
                              ...
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab) - Nope
(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)- Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)- Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)- Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)- Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)- Nope

可能的组合数量随着输入的长度呈指数级增长,在您知道它之前,正则表达式引擎正在耗尽所有系统资源,试图解决这个问题,直到用尽所有可能的术语组合,它最终放弃了报告"没有匹配." 与此同时,你的服务器变成了一堆燃烧的熔融金属.(有趣的是,这基本上是密码暴力破解程序的工作方式,因为这是同一类问题.)

如何发现邪恶的正则表达

这实际上非常棘手.我自己写了几个,尽管我知道它们是什么,一般如何避免它们.看到Regex花了很长时间.在原子组中包装所有内容可以帮助防止回溯问题.它基本上告诉正则表达式引擎不要重新访问给定的表达式 - "锁定你在第一次尝试时匹配的内容".但是请注意,该原子表达式不会阻止回溯内表达,所以^(?>((ab)*)+)$仍是危险的,但是^(?>(ab)*)+$是安全的(它会匹配(abababababababababababab),然后拒绝放弃任何它匹配的字符,从而避免灾难性的回溯).

不幸的是,一旦写完,实际上很难立即或快速找到问题正则表达式.最后,认识到一个糟糕的正则表达式就像识别任何其他不良代码一样 - 它需要大量的时间和经验和/或一个灾难性的事件.

有趣的是,由于这个答案是第一次写的,德克萨斯大学奥斯汀分校的一个团队发表了一篇论文,描述了一个能够对正则表达式进行静态分析的工具的开发,其明确目的是找到这些"邪恶"模式.该工具是为了分析Java程序而开发的,但我怀疑在未来几年中我们会看到更多的工具围绕分析和检测JavaScript和其他语言中的问题模式而开发,尤其是当ReDoS攻击的速度不断攀升时.

使用正则表达式的程序中的DoS漏洞的静态检测
ValentinWüstholz,Oswaldo Olivo,Marijn JH Heule和Isil Dillig
德克萨斯大学奥斯汀分校

Answer 2

检测邪恶的正则表达式

1. 试试 Nicolaas Weideman 的RegexStaticAnalysis项目。
2. 试试我的集成式vuln-regex-detector，它有一个用于 Weideman 工具和其他工具的 CLI。

经验法则

邪恶的正则表达式总是由于相应 NFA 中的歧义，您可以使用诸如regexper 之类的工具进行可视化。

这里有一些形式的歧义。不要在你的正则表达式中使用这些。

1. Nesting quantifiers like (a+)+ (aka "star height > 1"). This can cause exponential blow-up. See substack's safe-regex tool.
2. Quantified Overlapping Disjunctions like (a|a)+. This can cause exponential blow-up.
3. Avoid Quantified Overlapping Adjacencies like \d+\d+. This can cause polynomial blow-up.

Additional resources

I wrote this paper on super-linear regexes. It includes loads of references to other regex-related research.

Answer 3

你所谓的"邪恶"正则表达式是一个表现出灾难性回溯的正则表达式.链接页面(我写的)详细解释了这个概念.基本上,当正则表达式无法匹配并且相同正则表达式的不同排列可以找到部分匹配时,会发生灾难性的回溯.然后正则表达式引擎尝试所有这些排列.如果您想查看代码并检查正则表达式,这些是需要关注的3个关键问题:

1. 替代品必须互相排斥.如果多个替代方案可以匹配相同的文本,那么如果正则表达式的其余部分失败,则引擎将尝试两者.如果备选方案属于重复的组,则会发生灾难性的回溯.一个典型的例子是(.|\s)*当正则表达式没有"点匹配换行符"模式时匹配任何数量的任何文本.如果这是较长正则表达式的一部分,那么具有足够长的空格(由两者.和两者匹配\s)的主题字符串将打破正则表达式.该修复程序(.|\n)*用于使备选方案互斥或甚至更好地更具体地确定哪些字符是真正允许的,例如[\r\n\t\x20-\x7E]ASCII printables,制表符和换行符.

2. 按顺序排列的量化标记必须相互排斥,或者相互排斥它们之间的标记.否则两者都可以匹配相同的文本,并且当正则表达式的其余部分无法匹配时,将尝试两个量词的所有组合.一个典型的例子就是a.*?b.*?c将3个东西与它们之间的"任何东西"相匹配.当c无法匹配时,第一个.*?将逐字符扩展,直到行或文件的末尾.对于每个扩展,第二个.*?扩展将逐字符扩展以匹配行或文件的其余部分.修复是要意识到你不能在它们之间有"任何东西".第一次运行需要停止,b第二次运行需要停止c.单个字符a[^b]*+b[^c]*+c是一个简单的解决方案.由于我们现在停在分隔符处,我们可以使用占有量词来进一步提高性能.

3. 包含带有量词的标记的组必须不具有自己的量词,除非组内的量化标记只能与其相互排斥的其他内容匹配.这确保了内部量词的更​​多迭代的外部量词的更​​少次迭代不能与外部量词的更​​多迭代匹配相同的文本而内部量词的迭代更少.这是JDB答案中说明的问题.

在我写答案的时候,我决定在我的网站上写一篇完整的文章.这也是在线的.

Answer 4

我会把它总结为"重复重复".你列出的第一个例子很好,因为它表示"字母a,连续一次或多次.这可以连续发生一次或多次".

在这种情况下要寻找的是量词的组合,例如*和+.

值得注意的是第三和第四个更微妙的事情.这些示例包含OR操作,其中双方都可以为真.这与表达式的量词相结合可能会导致很多潜在的匹配,具体取决于输入字符串.

总结一下,TLDR风格:

小心如何将量词与其他运算符结合使用.

Answer 5

令人惊讶的是，我在执行源代码审查时多次遇到过 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在给定的超时后抛出 a并且不会导致资源使用导致拒绝服务条件。

您将需要试验超时值以确保它适合您的使用。