Skip to content

docs: add guidance on avoiding catastrophic backtracking#4667

Merged
theseion merged 4 commits into
mainfrom
docs/redos-backtracking-guidance
Jun 18, 2026
Merged

docs: add guidance on avoiding catastrophic backtracking#4667
theseion merged 4 commits into
mainfrom
docs/redos-backtracking-guidance

Conversation

@fzipi

@fzipi fzipi commented Jun 15, 2026

Copy link
Copy Markdown
Member

what

  • add a new subsection Avoiding Catastrophic Backtracking (Ambiguity) to the "Writing Regular Expressions" part of CONTRIBUTING.md

why

  • the existing guidance covers lazy quantifiers and the RE2 (non-backtracking) restrictions, but does not explain the actual root cause of catastrophic backtracking in CRS regexes: ambiguity inside a quantified group, not greediness. since CRS cannot use atomic groups or possessive quantifiers, writing unambiguous expressions is the only available defense.
  • the new subsection documents the guiding principle (inside a quantified group, every input character should be consumable by exactly one branch/position, and each whitespace run in exactly one place), the two ambiguous shapes that show up most often (a \s branch next to a comment body that also matches whitespace; a token wrapped in \s* on both sides inside a repeated group), and a before/after example.
  • it also records two CRS-specific testing notes that are easy to get wrong: test with . matching newlines (DOTALL, as ModSecurity runs @rx), and treat PCRE2 exceeding its backtracking limit (which errors and makes the rule fail to match) as the meaningful signal, rather than a checker's theoretical "exponential" label (RE2 is immune; PCRE2's required-literal optimization tames many theoretically-ambiguous cases).

refs

  • documentation only; no rule or test changes

ai disclosure

  • tools used: Claude (Opus 4.8)
  • assisted with: drafting the CONTRIBUTING.md subsection wording and the before/after example
  • review performed: the principle and examples were derived from empirical analysis of existing CRS rules (measuring backtracking growth under DOTALL on Python re and PCRE2 grep -P); the before/after example is a real de-ambiguation verified to be flat on both engines while preserving functional matches

Document the root cause of ReDoS in CRS regexes (ambiguity inside a
quantified group, not greediness) and how to avoid it, since CRS cannot
use atomic groups or possessive quantifiers.

Add a "Avoiding Catastrophic Backtracking (Ambiguity)" subsection with the
guiding principle, the two common ambiguous shapes (a `\s` branch next to a
comment body that also matches whitespace; a token wrapped in `\s*` on both
sides inside a repeated group), a before/after example, and two
CRS-specific testing notes: test with `.` matching newlines (DOTALL, as
ModSecurity runs it), and treat PCRE2 exceeding its backtracking limit (an
error that makes the rule fail) as the meaningful signal rather than a
checker's theoretical complexity label.
@fzipi
fzipi requested a review from theseion June 15, 2026 17:59
@fzipi fzipi added release:ignore Ignore for changelog release 📖 documentation Improvements or additions to documentation labels Jun 15, 2026
@theseion

Copy link
Copy Markdown
Contributor

This should also be documented on the website, where our regex docs live.

Comment thread CONTRIBUTING.md Outdated
Comment thread CONTRIBUTING.md Outdated
@theseion
theseion added this pull request to the merge queue Jun 18, 2026
Merged via the queue into main with commit 2e898c4 Jun 18, 2026
4 checks passed
@theseion
theseion deleted the docs/redos-backtracking-guidance branch June 18, 2026 05:43
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

📖 documentation Improvements or additions to documentation release:ignore Ignore for changelog release

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants