如何在 PHP 中触发 Regex 拒绝服务？

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)+、(a|a?)+ 上触发 ReDOS，因为没有任何东西可以导致匹配失败并在之后触发回溯正则表达式的问题部分。

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

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

例如，给定 (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 时效果更明显。顺便说一下，这是一个匹配字符串具有最坏情况复杂度的罕见情况。

如何在 PHP 中触发 Regex 拒绝服务？

How to trigger Regex Denial-of-Service in PHP?

php

regex

security

denial-of-service

preg-match