Perl-Compatible Regular Expressions use recursion in order to process strings using a given regular expression. Depending on whether the regular expression can be arbitrarily chosen by an attacker, a ReDoS could be performed by consuming enough stack that would result in an unavoidable stack overflow - although *nix systems provide configurable limits to prevent such occurrences. The PCRE library is well-aware of the issue of using recursion and provides the ability to compile PCRE to use the heap (under FreeBSD, it is as easy as de-selecting the recursion-related option when recompiling the port); however, the heap is also much slower, especially for string-manipulations where one would hope for speedy results.

In case stack recursion is used, then PCRE conveniently allows the programmer to set the recursion depth. Unfortunately, even wide-spread linkers such as PHP that use PCRE, set the recursion limit to some bogus value that usually oversteps the system-wide stack size limitation. In doing so, this unavoidably leads to PHP overstepping the system-wide stack size limitation which makes the operating system terminate the process.

From the official PCRE documentation, the recursion stack memory usage can be determined by using the pcretest utility:

pcretest -m -C

This should yield, amongst others, the memory consumed by a single stack frame during recursion:

Match recursion uses stack: approximate frame size = 496 bytes

to which, the documentation suggests that that about more bytes should be added.

This means that for every level of the recursion, every stack frame should consume an approximate value of 500 bytes.

For libraries or tools that use PCRE, the recursion depth is often set inadequately - for instance, looking at the PHP PCRE documentation, the recursion depth is set by default at which would result in the usage of bytes or that will exceed the system-wide stack size limit on most Linux distributions - to find out, also issue:

ulimit -s

which, usually yields 8192 bytes ().

The result is that if PCRE is used by a library or an utility such as PHP to process arbitrary user-input, a well-chosen input could result in overstepping the system-wide stack size limit.

In order to avoid this issue (especially in PHP - where it tends to hurt most), one would issue:

ulimit -s

and jot down the stack size - let's assume that the result is ; as it is on most end-user Linux systems. Next, issue:

pcretest -m -C

and the last line should give you the frame size as per the previous example.

Assuming that the frame size is and that the system-wide stack size limit is , then the formula becomes:

which, in this example would yield a rounded-down value of - this value represents the maximal recursion depth that PCRE should be set to.

If the computed recursion depth value is too small, then the only option is to increase the stack size using ulimit.

To set the maximal recursion depth for PHP, locate and edit php.ini in order to add or amend the line:

pcre.recursion_limit=16

in this instance, we have set the value to which is the value computed in the previous example that corresponds to an 8MB system-wide stack size limit.