Regex backtracking and ReDoS
Why a short pattern like (a+)+$ can freeze a program on 30 characters of input, how to see it happen without freezing this page, and the fixes that work. Every run below happens in a Worker with a time limit.
The demo matches your pattern against a repeated n times followed by !, for growing n, inside a Web Worker. A run that has not finished by the time limit is stopped by terminating the Worker, and the page carries on.
| n | Cost | Growth | Relative size |
|---|
How to use
- Choose an engine. PCRE2 reports a step count that does not depend on your computer. JavaScript and Go report elapsed milliseconds.
- Pick a pattern from the list or type your own. The input is always
arepeated n times followed by!, so patterns that needbor other letters will simply not match. - Press Run the series. The page tries n = 4, 6, 8 and so on up to your maximum. Watch the Growth column: if each row is a multiple of the last (×4, ×4, ×4 for
^(a+)+$) the cost is exponential in n. - If a run exceeds the time limit the page shows Pattern stopped, terminates the Worker and ends the series. Press Run again to start fresh.
Worked examples
Why ^(a+)+$ explodes
On input aaaa! the inner a+ can take 1, 2, 3 or 4 letters, and the outer + can then repeat the group over what is left. Every way of cutting the run of a's into pieces is a different path, and the final $ fails on the ! for each of them. OWASP counts 16 paths for four a's and says the number doubles with every additional a. This page's measurements show the same shape: with PCRE2, each two extra a's multiplies the step count by exactly 4.
Measured with PCRE2 10.48 (this site's WebAssembly build)
Input: n a's and a final !. Counts are PCRE2's match-limit counter, found by searching for the smallest limit under which the match completes.
| Pattern | Where it works | Steps, n = 10 | Steps, n = 20 | Verdict |
|---|---|---|---|---|
^(a+)+$ | every backtracking engine | 2,560 | 2,621,440 | exponential |
^(a|aa)+$ | every backtracking engine | 697 | 85,969 | exponential |
^a+$ | every backtracking engine | 2 | 2 | linear |
^(?>a+)+$ | PCRE2 (also Java, Python 3.11+) | 6 | 6 | linear |
^(?:a++)+$ | PCRE2 (also Java, Python 3.11+) | 3 | 3 | linear |
^(?:(?=(a+))\1)+$ | JavaScript (and PCRE2) | 9 | 9 | linear |
^(a+)+$: The inner a+ and the outer + can both split a run of a's in many ways. When the final $ fails on "!", the engine tries every split.^(a|aa)+$: Alternatives that overlap: "aa" can also be read as "a" then "a". Growth is exponential too, at a slower rate than the nested plus.^a+$: Remove the nesting: one repeat, one way to match a run of a's. The count stays at 2 however long the run is. Counts are PCRE2's own and are not comparable with the steps of other engines.^(?>a+)+$: An atomic group (PCRE2, Java, Python 3.11+) never gives back what it matched, so the outer + has nothing to retry.^(?:a++)+$: A possessive quantifier a++ is shorthand for (?>a+). Same effect, shorter to write.^(?:(?=(a+))\1)+$: JavaScript has neither atomic groups nor possessive quantifiers, but a lookahead is atomic, so (?=(a+))\1 behaves like (?>a+). This is a known workaround, not a documented feature; the evidence here is the measurement.
For ^(a+)+$, 10 more a's multiply the count by 1,024 (2,560 to 2,621,440), exactly 210, as the doubling rule predicts. The default PCRE2 match limit is 10 million, according to the PCRE2 documentation, so a single failed match of this pattern at n = 22 would already reach it on a default build.
The real-world case
On 2 July 2019 Cloudflare deployed a WAF rule containing a regular expression that "backtracked enormously" and exhausted CPU on its edge servers worldwide; the company reported 27 minutes of impact and described moving to an engine with a linear-time guarantee. The post-incident write-up is cited below.
The fixes, in the order to try them
- Remove the ambiguity.
^a+$says the same thing as^(a+)+$with one way to match. If two parts of a pattern can match the same characters next to each other, rewrite one of them. - Unroll loops. For quoted strings, write
"[^"\\]*(?:\\.[^"\\]*)*"instead of"(?:[^"\\]|\\.)*". The quoted-string page measures both: with 20 backslashes the naive form takes 84,374 PCRE2 steps and the unrolled form 34. - Make groups atomic where the engine has them:
(?>...)or possessivea++in PCRE2, Java, and Python 3.11+. JavaScript has neither; the lookahead trick above is the workaround. - Limit the input. Cap the length of anything you match with a backtracking engine. Cost grows with length, so a cap turns "unbounded" into "bounded".
- Use a linear-time engine for patterns you do not control (user-supplied patterns, WAF rules). RE2 and Go's regexp guarantee time linear in the input, and refuse features that would break that, such as backreferences and lookaround.
- Set a limit on the engine where one exists. PCRE2 has a match limit that returns an error instead of running forever; this page uses the same idea with a time limit and a terminated Worker.
Limits & gotchas
- Steps are engine-specific. A PCRE2 step is one iteration of its matching loop. It is not comparable with a step in another engine, and the PCRE2 documentation says the limit is used in a different way when a pattern is JIT-compiled, so counts from a JIT build would not match these.
- Times depend on your machine. The JavaScript and Go columns are wall-clock milliseconds in your browser. The clock starts after the engine file has loaded, but a slow computer or a busy tab still changes the numbers.
- Browsers may optimize. The JavaScript engine in your browser can recognise some patterns and simplify them, so a pattern that is slow in one browser can be fast in another. A pattern that is quick here is not proof that it is safe elsewhere.
- Only one input family is tried. The demo uses a's followed by one
!. Real attacks use whatever input makes your pattern fail late; this page shows the mechanism, not a security audit. - Linear is not instant. Go's guarantee is about growth with input size, not about the constant: complex patterns can still be slower than a simple backtracking match on short inputs.
- The lookahead trick is an observation, not a documented feature. It works on the PCRE2 and JavaScript engines measured here for this pattern. Test your own pattern before relying on it.
FAQ
What is catastrophic backtracking?
A backtracking engine tries one way of matching and, if the rest of the pattern fails, goes back and tries another. When a pattern can split the same input in many ways, a failing match makes the engine try nearly all of them, and the number of ways can double with every extra character. OWASP describes ^(a+)+$ on "aaaaX" as 16 paths and on a 16-letter version as 65,536.
Is it safe to run a catastrophic pattern on this page?
Yes. Every run happens in a Web Worker with a time limit. When the limit passes, the page terminates the Worker (MDN: terminate() stops the worker immediately without giving it a chance to finish) and starts a fresh one for the next run. The page itself never waits on the pattern.
Which engines are immune?
Engines that match without backtracking. RE2's documentation promises match time linear in the length of the input, and Go's regexp documentation makes the same promise. JavaScript, PCRE2, Python and Java use backtracking and can be affected; the Go engine in this page's demo is there to show the contrast.
Do atomic groups and possessive quantifiers fix it?
For nested repeats like (a+)+ they remove the retry, so the match fails quickly. They exist in PCRE2, Java and Python 3.11 and later, but not in JavaScript or Go. In JavaScript a lookahead with a backreference, (?=(a+))\1, behaves atomically; the measurements on this page show it, though MDN does not describe it as an atomic group.
Why is the PCRE2 column in steps and the other columns in milliseconds?
PCRE2 exposes a counter of matching-loop iterations through its match limit, so the page can report a machine-independent number. The browser's RegExp and Go offer no such counter, so the page reports elapsed time, which depends on your computer and on whether the engine was already loaded.
Sources
- OWASP: Regular expression Denial of Service - ReDoS Used for: Explanation of backtracking, "evil" patterns such as (a+)+$, and the doubling of paths per extra character.
- Cloudflare blog: Details of the Cloudflare outage on July 2, 2019 Used for: A real outage caused by a regular expression that backtracked enormously; remediation included moving to engines with run-time guarantees.
- PCRE2: pcre2api Used for: Match limit (PCRE2_ERROR_MATCHLIMIT), default newline, DOLLAR_ENDONLY, pcre2_substitute replacement syntax ($1, ${1}, $<name>, $0 or $&).
- PCRE2: pcre2pattern Used for: Syntax and semantics: groups, named groups, lookbehind rules, atomic groups, possessive quantifiers, \d \s \w with and without UCP, dollar and newline handling, \A \Z \z.
- Go: regexp package Used for: Linear-time guarantee, leftmost-first semantics, Expand template syntax ($1, ${name}, $name longest-name rule).
- Google RE2: README Used for: RE2 is a safe alternative to backtracking engines; linear running time; no constructs that need backtracking.
- MDN: Worker: terminate() Used for: terminate() stops a Worker immediately without letting it finish.
- MDN: Quantifier Used for: Greedy and lazy quantifiers, {n}, {n,}, {n,m}, no spaces inside braces, braces as literals in Unicode-unaware mode.
- MDN: Lookahead assertion: (?=...), (?!...) Used for: Zero-width assertions; no backtracking into a lookahead.
- Python docs: re: Regular expression operations (3.13) Used for: Syntax, (?P<name>), atomic groups and possessive quantifiers (3.11+), fixed-length lookbehind, Unicode \d \s \w, $ before trailing newline, \A \Z, re.sub replacement syntax, inline flags at start only (3.11+).
- Oracle (Java SE 21): java.util.regex.Pattern Used for: Construct table, \d \s \w without UNICODE_CHARACTER_CLASS, possessive and atomic constructs, named groups, line terminators and $, \A \Z \z.
Every document above was opened and read on 2026-10-02. Documentation changes; if a page here disagrees with the current docs, trust the docs and tell us.