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

Question

How can I trigger a Regex-DOS using the preg_match() function using an evil regular expression (e.g. (a+)+ )?

For example, I have the following situation:

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

If I have control over $input, how could I trigger a DOS attack or reach the backtrack limit of the preg_* functions in php?

How could I do this with the following expressions?

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

Answer 1

There is no way to trigger ReDOS on (a+)+, ([a-zA-Z]+)*, (a|aa)+, (a|a?)+ , since there is nothing that can cause match failure and trigger backtracking after the problematic part of the regex.

If you modify the regex a bit, for example, adding b$ after each of the regex above, then you can trigger catastrophic backtracking with an input like aaa...aabaa...aa.

Depending on the engine's implementation and optimization, there are cases where we expect catastrophic backtracking, but the engine doesn't exhibit any sign of such behavior.

For example, given (a+)+b and the input aaa...aac, PCRE fails the match outright, since it has an optimization that checks for required character in the input string before starting the match proper.

Knowing what the engine does, we can throw off its early detection with the input aaa...aacb and get the engine to exhibit catastrophic backtracking.

As for (.*a){x}, it is possible to trigger ReDOS, since it has a failing condition of less than x iterations. Given the input string aaa...a (with x or more of character a), the regex keeps trying all permutations of a's at the end of the string as it backtracks away from the end of the string. Therefore, the complexity of the regex is O(2^x). Knowing that, we can tell that the effect is more visible when x is larger number, let's say 20. By the way, this is one rare case where a matching string has the worst case complexity.