php - 如何在 PHP 中触发正则表达式拒绝服务？

Question

如何使用邪恶的正则表达式(例如 (a+)+ )使用 preg_match() 函数触发 Regex-DOS？

比如我有以下情况:

preg_match('/(a+)+/',$input);

如果我可以控制$input，我如何触发DOS攻击或达到preg_的回溯限制 * PHP 中的函数？

我如何使用以下表达式来做到这一点？

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

Answer 1

无法在 (a+)+、([a-zA-Z]+)*、(a|aa) 上触发 ReDOS +、(a|a?)+ ，因为在正则表达式的有问题的部分之后没有任何东西会导致匹配失败并触发回溯。

如果稍微修改一下正则表达式，例如 adding b$ after each of the regex above ，那么您可以使用诸如 aaa...aabaa...aa 这样的输入来触发灾难性回溯。

根据引擎的实现和优化，在某些情况下我们预计会发生灾难性回溯，但引擎没有表现出任何此类行为的迹象。

例如，给定 (a+)+b 和输入 aaa...aac, PCRE fails the match outright ，因为它有一个优化，可以在开始正确匹配之前检查输入字符串中所需的字符。

了解引擎的作用，我们可以 throw off its early detection输入 aaa...aacb 并让引擎表现出灾难性的回溯。

对于(.*a){x}，有可能触发ReDOS，因为它的失败条件少于x次迭代.给定输入字符串 aaa...a (带有 x 或更多字符 a)，正则表达式保持当它从字符串末尾回溯时，尝试在字符串末尾处尝试 a 的所有排列。因此，正则表达式的复杂度为 O(2^x)。知道了这一点，我们可以看出，当 x 的数字较大时，效果更加明显，let's say 20 。顺便说一句，这是一种罕见的情况，其中匹配字符串具有最坏情况的复杂性。