php-regex / regex-redos

2.x-dev 2026-10-05 22:20 UTC

Requires

• php: >=8.2
• php-regex/regex-parser: ^2.0

MIT

• Younes ENNAJI

• security
• regex
• PCRE
• redos
• backtracking

Published on Packagist.org on 2026-10-05 22:21 UTC

README

PHPRegex Redos

Proves a pattern safe from catastrophic backtracking (ReDoS), or hands you the input that triggers it — and can replay that input on the engine.

Requires PHP 8.2+. MIT licensed.

Features

• One verdict per pattern, read straight from the AST: safe, low, medium, high or critical — or unknown, with the error, when the analysis itself fails.
• A backtracking model proves the cost of one match attempt — linear, polynomial (with its degree) or exponential — and the verdict says who decided: proven, heuristic, budget_exceeded or not_analyzed.
• Every proven vulnerable verdict carries a witness: the prefix, pump and suffix of the input family that drives the worst case.
• Confirmation adds runtime evidence: the witness replayed pump by pump, or growing inputs — always without the JIT, under the limits you set, with the failing evidence named.
• Outside the model, structural heuristics decide and say so: confidence level, false-positive risk, one Finding per risk with its message and suggested rewrite.
• The verdict serializes to JSON with the PCRE2 release and the analysis version; Hotspot objects pin each risk to byte offsets, for Heatmap to paint.

Installation

composer require php-regex/regex-redos

php-regex/regex-parser (^2.0) is pulled in automatically. To scan a whole code base instead of one pattern at a time, use the linter.

Configuration

new RedosAnalyzer() takes named arguments: ignoredPatterns (array<string>, patterns skipped by value, with or without their delimiters), threshold (RedosSeverity::High, the lowest severity that triggers a confirmation run) and options (a RedosOptions).

RedosOptions is the budget of the backtracking model, counted in states and steps, never in time — the same pattern gets the same verdict on every machine:

Option	Default	Role
maxStates	2000	states the pattern's automata may hold
maxSteps	250_000	states created, product pairs visited, class scans and the memory they take
boundedRepeatCutoff	16	largest bounded-repeat maximum unrolled; past it, {m,n} is analyzed as {m,}

ConfirmationOptions drives the runtime probe:

Option	Default	Role
minInputLength, maxInputLength, steps	16, 128, 3	subject lengths probed, doubling up to the maximum
iterations, timeoutMs	3, 50.0	runs per length, and the average duration that stops one
backtrackLimit, recursionLimit	100_000, 10_000	engine limits during the probe
previewLength	64	subject bytes kept per sample; 0 keeps none

analyze() also takes threshold (the constructor one by default), mode and confirmOptions. RedosMode::Off skips the analysis, RedosMode::Theoretical reads the AST only, RedosMode::Confirmed runs the confirmation for you.

Usage

The first verdict:

use PHPRegex\Redos\RedosAnalyzer;

$analysis = (new RedosAnalyzer())->analyze('/(\w+\s?)+$/');

echo $analysis->severity->value, "\n";   // critical
echo $analysis->complexity->value, "\n"; // exponential
echo $analysis->proof->value, "\n";      // proven

Proven safe, and polynomial with its degree:

$analyzer = new RedosAnalyzer();

var_dump($analyzer->analyze('/^\d{4}-\d{2}-\d{2}$/')->isProvenSafe()); // bool(true)

$adjacent = $analyzer->analyze('/\w+\w+!/');
echo $adjacent->severity->value, ' ', $adjacent->complexity->value, ' ', $adjacent->degree, "\n";
// medium polynomial 2

The witness — the input family that drives the worst case — and the headline every consumer prints:

$vuln = (new RedosAnalyzer())->analyze('/(a+)+b/');

echo $vuln->headline(), "\n";        // Exponential backtracking (proven)
echo $vuln->witness->render(), "\n"; // "a" x n . "!b"
echo $vuln->witness->build(3), "\n"; // aaa!b

Confirmed mode replays an exponential witness on the running engine; it tries several candidate suffixes and publishes the one that made preg_match() exhaust the backtrack limit:

use PHPRegex\Redos\RedosMode;

$replayed = (new RedosAnalyzer())->analyze('/(a+)+b/', mode: RedosMode::Confirmed);

echo $replayed->witness->render(), "\n";         // "a" x n . "!b"
var_dump($replayed->replayed);                   // bool(true)
echo $replayed->confidenceLevel()->value, "\n"; // high

What the model analysed differently from the pattern, and the budget it ran under:

use PHPRegex\Redos\RedosOptions;

$bounded = (new RedosAnalyzer())->analyze('/(a{1,20})+$/');
echo $bounded->abstractions[0], "\n"; // {1,20} at offset 1 analysed as {1,}

$small = new RedosAnalyzer(options: new RedosOptions(maxStates: 100, maxSteps: 5_000));
echo $small->analyze('/^(?:\d{1,16}|[a-f]{1,16})+$/')->proof->value, "\n"; // budget_exceeded

The confirm step, with your own limits on the probe:

use PHPRegex\Redos\ConfirmationOptions;
use PHPRegex\Redos\ConfirmationRunner;

$analysis = (new RedosAnalyzer())->analyze('/(\w+\s?)+$/');

$confirmation = (new ConfirmationRunner())->confirm(
    '/(\w+\s?)+$/',
    $analysis,
    new ConfirmationOptions(backtrackLimit: 50_000),
);

var_dump($confirmation->confirmed); // bool(true)
echo $confirmation->evidence, "\n"; // backtrack_limit

Documentation

• Quick start — where the ReDoS check sits in the opening tour
• ReDoS guide — the verdict and its guarantee, the witness, confirmed mode and the mitigations
• ReDoS deep dive — how backtracking explodes, shape by shape, and how the model finds it
• API reference — the analyzer's options and the aggregate analysis report
• Backward compatibility — what stays stable across releases

Resources

• Documentation
• All PHPRegex packages — one repo, one version number
• Changelog
• Report issues and send pull requests in the main PHPRegex repository

Sponsors

If PHPRegex saves you time, consider sponsoring its maintenance.

License

MIT. See LICENSE.