Catastrophic backtracking, with no backreference anywhere¶

One line: An ordinary nested quantifier — (a+)+, (a|a)*, ^(\w+\s?)*$, almost every hand-written email validator — never answers in Python 3 or JavaScript, answers in Perl 5.42, Ruby 4.0 and Java 25 until the subject or the shape is changed slightly, and cannot happen at all in Go regexp or Rust regex; and the subject that triggers it is one that fails to match, which is why your tests never found it.

Level: 301 · you write patterns that untrusted input reaches

Keywords on this page: * + ? · {n,m} · | · (?>…) · *+ · (*SKIP)(*F) · (*UCP) — Topics: Security · Performance · Testing patterns

What a backreference costs is about a feature you have to ask for. This page is the other half: the same explosion, reached by a pattern that uses nothing exotic at all, written by someone who was trying to be careful.

The shape to recognise¶

A quantifier wrapped around something that can match the same text more than one way. That is the whole diagnosis. If a run of characters can be divided between an inner repetition and an outer one in more than one arrangement, a backtracking engine may have to try every arrangement before it can say "no".

Pattern	The ambiguity
`(a+)+`	120 `a`s can be split between the inner `+` and the outer `+` in 2¹¹⁹ ways.
`(a\|a)*`	Every iteration has two branches that consume the identical character.
`(\s*\|\t)+`	A tab matches both branches, and `\s*` can also match nothing.
`^(\w+\s?)*$`	`\s?` is optional, so a word of n characters is `n` different sequences of iterations.
`([a-z]{2,4})+`	A run of letters can be cut into groups of 2, 3 or 4 in a great many ways.

That last one is not a toy. It is the tail of the email pattern that has been copied into production for twenty years:

^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z]{2,4})+$

The + after ([a-zA-Z]{2,4}) is the bug, and it looks like a typo you would skim past — {2,4} already says "two to four", so the outer + adds nothing but ambiguity. Every engine on this page that can be made to explode is exploded by that pattern.

Why the failing subject is the expensive one¶

An engine stops the moment it finds a match. The whole search only happens when there is no match to find — and the cheapest way to guarantee no match is one trailing character that cannot possibly belong.

That is the trap. aaa…aaa is a valid input to ^(a+)+$ and is answered instantly. aaa…aaa! is an invalid input and is answered never. Your unit tests are full of valid inputs and a handful of short invalid ones, and neither finds this. The person who finds it is the one typing into your form.

How this page measures it¶

No timing is recorded anywhere below, because a timing is not a fact two machines agree on. Each probe runs under a fixed cap and the answer key holds one of four words — match, no match, no answer, still searching. The two subject sizes sit far either side of the cliff on purpose: the small one costs a few thousand steps on any machine, the large one more steps than any machine will ever take.

Python and JavaScript run each probe in a child process that is killed after three seconds. Perl abandons the match with an alarm. Java uses no clock at all — it hands the engine a CharSequence that counts every character read and gives up after a fixed budget. Ruby uses its own Regexp.timeout.

The versions that recorded these keys are Python 3.14, node 20, Perl 5.42, Ruby 4.0, Java 25, Go 1.25, and the regex 1.13 / fancy-regex 0.16 crates. CI re-runs all of them on Linux against somewhat older Python, Perl and Ruby and holds the output to the same bytes, so a row whose answer depended on a point release would not have survived the push that published this page.

Python 3¶

Verified output of redos_cliff_py.py — regenerated by tools/run_examples.py, never hand-typed.

"no answer" means the child was still searching after 3 seconds and was killed.

patterns with no backreference, python re:
  ^(a+)+$                  16 a's then '!'        no match
  ^(a+)+$                  120 a's                match
  ^(a+)+$                  120 a's then '!'       no answer
  ^(a|a)*$                 120 a's then '!'       no answer
  ^(\s*|\t)+$              120 spaces then '!'    no answer
  ^(\w+\s?)*$              120 a's then '!'       no answer
  ^([a-z]{2,4})+$          120 a's then '!'       no answer
  the email regex          a@a. 20 a's then '!'   no match
  the email regex          a@a. 120 a's then '!'  no answer

the same engine, with the pattern changed instead:
  ^(?>a+)+$                120 a's then '!'       no match
  ^(a++)+$                 120 a's then '!'       no match
  ^a+$                     120 a's then '!'       no match
  the email regex, fixed   a@a. 120 a's then '!'  no match

Every shape in the table blows up, including the email pattern, and the second row is the one to stare at: the matching subject of the same length comes back immediately. Python's re has no cache and no limit; the match runs until it finishes, on whichever thread called it.

The second table is the fix, and it needs no new engine. (?>a+) is an atomic group and a++ is a possessive quantifier; both say "having matched this, never give any of it back", which deletes the ambiguity rather than searching through it. Python has had both since 3.11. ^a+$ is better still: it is what the pattern meant all along.

JavaScript¶

Verified output of redos_cliff_js.js — regenerated by tools/run_examples.py, never hand-typed.

"no answer" means the child was still searching after 3 seconds and was killed.

patterns with no backreference, node:
  ^(a+)+$                  16 a's then '!'        no match
  ^(a+)+$                  120 a's                match
  ^(a+)+$                  120 a's then '!'       no answer
  ^(a|a)*$                 120 a's then '!'       no answer
  ^(\s*|\t)+$              120 spaces then '!'    no answer
  ^(\w+\s?)*$              120 a's then '!'       no answer
  ^([a-z]{2,4})+$          120 a's then '!'       no answer
  the email regex          a@a. 20 a's then '!'   no match
  the email regex          a@a. 120 a's then '!'  no answer

the same engine, with the pattern changed instead:
  ^a+$                     120 a's then '!'       no match
  the email regex, fixed   a@a. 120 a's then '!'  no match
  atomic, emulated         120 a's then '!'       no match

The same cliff, on the engine least able to survive it. Node has one thread serving every request, and a browser has one thread serving the user; a regular expression that does not return takes the whole thing with it.

And JavaScript has neither (?>…) nor a++ — that is measured on the engines page, where it is the only one of the five probed engines missing both. The last row is the standard stand-in: (?=(a+))\1 lets a lookahead capture the whole run and a backreference re-consume exactly that run, leaving nothing to back off into. It works, it is unreadable, and it is a reason to prefer the rewrite on the row above it.

Perl¶

Verified output of redos_cache_pl.pl — regenerated by tools/run_examples.py, never hand-typed.

"no answer" means the match was still running after 3 seconds and was abandoned.

patterns with no backreference, perl:
  ^(a+)+$                  120 a's then '!'       no match
  ^(a|a)*$                 120 a's then '!'       no match
  ^(\s*|\t)+$              120 spaces then '!'    no match
  ^(\w+\s?)*$              120 a's then '!'       no match
  ^([a-z]{2,4})+$          120 a's then '!'       no match
  the email regex          a@a. 120 a's then '!'  no match

the same patterns, on a field a user filled with a megabyte:
  ^(a+)+$                  1000000 a's then '!'   no answer
  ^(?>a+)+$                1000000 a's then '!'   no match
  ^a+$                     1000000 a's then '!'   no match

This is the first result that contradicted the draft of this page. Perl 5.42 answers every one of these, including the email pattern. Its engine stops a repetition re-exploring a position it has already failed from, which turns the exponential search into a polynomial one. Perl's own documentation does not promise this, so treat it as measured behaviour and not as a contract.

And polynomial is not the same as safe. The second table is the bill: the identical ^(a+)+$ on a field a user filled with a megabyte is still running after three seconds, because quadratic work on 10⁶ characters is 10¹² steps. The atomic version and the un-nested version answer the same megabyte at once. "It does not explode" and "it is bounded" are different claims, and only the second one is worth relying on.

Ruby¶

Verified output of redos_guard_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

Regexp.timeout is 2.0 seconds; hitting it is reported as the exception class.

patterns with no backreference, ruby:
  ^(a+)+$                  120 a's then '!'       no match
  ^(a|a)*$                 120 a's then '!'       no match
  ^(\s*|\t)+$              120 spaces then '!'    no match
  ^(\w+\s?)*$              120 a's then '!'       no match
  ^([a-z]{2,4})+$          120 a's then '!'       Regexp::TimeoutError
  the email regex          a@a. 120 a's then '!'  Regexp::TimeoutError

the same engine, with the pattern changed instead:
  ^(?>a+)+$                120 a's then '!'       no match
  ^([a-z]{2,4})++$         120 a's then '!'       no match
  the email regex, fixed   a@a. 120 a's then '!'  no match

Ruby is the only engine here that ships a guard you can simply turn on. Regexp.timeout= (Ruby 3.2 and later) bounds every match in the process and raises Regexp::TimeoutError instead of holding the thread; Regexp.timeout on a single pattern object bounds just that one. Set it once at boot and the worst case becomes an exception you can log.

The same release also made the search remember states it has already failed in, which is why the first four rows answer at all — but look at row five. ^([a-z]{2,4})+$ still explodes, and so does the email pattern built on it. The optimisation is not a guarantee and the counted repetition is where it runs out, which is exactly the argument for turning the timeout on rather than trusting the engine to be clever.

Java¶

Verified output of redos_budget_java.java — regenerated by tools/run_examples.py, never hand-typed.

the budget is 20000000 character reads per match; running out is reported as "still searching".

patterns with no backreference, java:
  ^(a+)+$                  120 a's then '!'       no match
  ^(a|a)*$                 120 a's then '!'       no match
  ^(\s*|\t)+$              120 spaces then '!'    no match
  ^(\w+\s?)*$              120 a's then '!'       no match
  ^([a-z]{2,4})+$          120 a's then '!'       no match
  the email regex          a@a. 120 a's then '!'  no match

the same patterns, on a field a user filled with a megabyte:
  ^(a+)+$                  1000000 a's then '!'   still searching
  ^(?>a+)+$                1000000 a's then '!'   no match
  ^a+$                     1000000 a's then '!'   no match
  the email regex, fixed   a@a. then a megabyte   no match

and the control, so the budget above is not mistaken for a guarantee:
  ^(a+)+\1$                28 a's then '!'        still searching

The bigger surprise. ReDoS advisories name Java services constantly, and ^(a+)+$ is the example in half the write-ups — but Java 25 answers every backreference-free pattern on this page, well inside a budget of twenty million character reads. Whatever shortcut java.util.regex is taking is not something the Pattern javadoc names, so the honest summary is the measurement and not a mechanism.

The last two blocks are what stops this being good news. A megabyte of a exhausts a twenty-million-character budget, so Java is in Perl's position: polynomial, not exponential, and still an outage on a large enough field. And the control line at the bottom — the one pattern here with a \1 in it — is still searching after the same budget on 28 characters, which is both a check that the harness works and a reminder that the shortcut stops where the sibling lesson begins.

Java has (?>…) and a++, and Pattern has no built-in limit at all, so a bound has to come from your side — a budgeted CharSequence like the one in this example, or a timeout around the call.

Go and Rust: the question does not arise¶

Verified output of redos_re2_go.go — regenerated by tools/run_examples.py, never hand-typed.

patterns with no backreference, go regexp:
  ^(a+)+$                  120 a's then '!'       no match
  ^(a+)+$                  1000000 a's then '!'   no match
  ^(a|a)*$                 1000000 a's then '!'   no match
  ^(\s*|\t)+$              1000000 spaces, '!'    no match
  ^(\w+\s?)*$              1000000 a's then '!'   no match
  ^([a-z]{2,4})+$          1000000 a's then '!'   no match
  the email regex          a@a. then a megabyte   no match

the fixes the other engines need, handed to RE2:
  ^(?>a+)+$                error parsing regexp: invalid or unsupported Perl syntax: `(?>`
  ^(a++)+$                 error parsing regexp: invalid nested repetition operator: `++`

A megabyte, every shape on the page, answered. RE2 compiles the pattern to an automaton and makes one pass; the nesting that costs a backtracker 2¹¹⁹ attempts costs it nothing, because it never makes a choice it has to regret.

The second block is the trade stated plainly: the two constructs every backtracking engine on this page uses to cut its search are rejected by RE2. You cannot write (?>a+)+ in Go, and you do not need to.

Verified output of redos_lookahead_rs_sh.sh — regenerated by tools/run_examples.py, never hand-typed.

patterns with no backreference, rust:
  regex        ^(a+)+$           120 a's then '!'       no match
  regex        ^(a+)+$           100000 a's then '!'    no match
  regex        the email regex   100000 a's then '!'    no match
  fancy-regex  ^(?=a)(a+)+$      120 a's then '!'       no match
  fancy-regex  ^((?=a)a+)+$      120 a's then '!'       Error executing regex: Max limit for backtracking count exceeded
  fancy-regex  ^((?=a)(?>a+))+$  120 a's then '!'       no match

Rust's regex is the same automaton and gives the same answers. fancy-regex is the interesting one, and the two middle rows are the lesson: it hands any part of a pattern it has no special feature for straight to regex, so a lookahead in front of the loop leaves the loop delegated and linear — and moving the identical lookahead inside the loop leaves nothing to delegate, at which point the nesting explodes and the backtrack limit fires. There is no backreference in either pattern. A fancy-regex pattern is fast or bounded depending on where you put a construct that has nothing to do with the cost.

PCRE2, and therefore ABAP¶

PCRE2 counts the steps a match takes and stops at a built-in match limit, so it fails rather than hangs:

Real run — PCRE2 10.48 (pcre2grep), macOS 26.6.2 x86-64, 2026-09-22. small.txt holds 16 as and a !; big.txt holds 30 as and a !.

$ pcre2grep -c '^(a+)+$' small.txt
0

$ pcre2grep -c '^(a+)+$' big.txt
pcre2grep: pcre2_match() gave error -47 while matching this text:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!

pcre2grep: Error -46, -47, -53 or -63 means that a resource limit was exceeded.
pcre2grep: Check your regex for nested unlimited loops.
0

$ pcre2grep -c '^(a++)+$' big.txt
0

Thirty characters is already past the limit, and pcre2grep says the quiet part out loud: check your regex for nested unlimited loops. Error -47 is the match limit; --match-limit and --depth-limit move it, which is almost never what you want, because a limit you raise until the pattern passes is a limit you have disabled. One possessive + and the error is gone.

ABAP's PCRE addition (7.55 and later) is this library in the kernel, so this is ABAP's behaviour too: a work process that returns an error, not one that spins. The ABAP documentation names CX_SY_REGEX_TOO_COMPLEX for the case; nothing here can run ABAP, so that is a pointer to verify on your own system rather than a measurement.

z_redos_guard.prog.abap in full — pasted here by tools/run_examples.py from the file CI runs.

REPORT z_redos_guard.

" ABAP's PCRE addition (7.55 and later) is the PCRE2 library in the kernel, so
" this page's question -- what happens to a nested quantifier on a subject built
" to fail -- is really a question about PCRE2. Nothing in this repository can
" run ABAP, so this file is checked by abaplint and printed as source only;
" there is no recorded output beside it. What PCRE2 itself does is on the page,
" as a dated pcre2grep run.

" 120 a's and then one character that cannot match. The a's can be split
" between the inner + and the outer + in 2**119 ways, and a backtracking engine
" has to refuse every one of them before it can say "no".
DATA(hostile) = repeat( val = `a` occ = 120 ) && `!`.

" PCRE2 counts the steps a match takes and stops at a built-in match limit
" rather than running until the work process is killed. ABAP surfaces that as a
" catchable exception, so the shape to write is a TRY, not a longer timeout.
TRY.
    FIND FIRST OCCURRENCE OF PCRE `^(a+)+$` IN hostile.
    WRITE / |nested quantifier: sy-subrc = { sy-subrc }|.
  CATCH cx_sy_regex_too_complex.
    WRITE / |nested quantifier: the engine gave up|.
ENDTRY.

" The same question, with the inner repetition made possessive. `a++` matches
" the whole run of a's and never gives any of it back, so there is only one way
" to split the subject and nothing to search. No limit to hit, no exception to
" catch, and the answer is the same one.
FIND FIRST OCCURRENCE OF PCRE `^(a++)+$` IN hostile.
WRITE / |possessive:         sy-subrc = { sy-subrc }|.

" An atomic group says the same thing about a sub-expression rather than about
" one quantifier, and PCRE2 has had both for as long as ABAP has had PCRE.
FIND FIRST OCCURRENCE OF PCRE `^(?>a+)+$` IN hostile.
WRITE / |atomic group:       sy-subrc = { sy-subrc }|.

" Better than either: stop nesting. This pattern asks the same question of the
" same subject and gives a backtracker nothing to choose between.
FIND FIRST OCCURRENCE OF PCRE `^a+$` IN hostile.
WRITE / |not nested at all:  sy-subrc = { sy-subrc }|.

The measured summary¶

Every cell below is a row from one of the programs on this page. — means that question was not asked of that engine, not that the answer is good.

Engine and version	`^(a+)+$` on a failing subject	Counted repeat, `([a-z]{2,4})+`	A megabyte of `a`	A bound you can set
Python 3 `re`	no answer at 120 characters	no answer at 120	—	none
node (V8)	no answer at 120 characters	no answer at 120	—	none
Perl 5.42	answers at 120	answers at 120	no answer	none built in
Ruby 3.2+	answers at 120	`Regexp::TimeoutError`	—	`Regexp.timeout=`
Java 25	answers at 120	answers at 120	budget exhausted	none built in
PCRE2 10.48, ABAP `PCRE`	resource-limit error at 30	—	—	match and depth limits
Rust `fancy-regex` 0.16	delegated to `regex`; backtrack limit once it cannot delegate	—	—	backtrack limit, returned as `Err`
Go `regexp`, Rust `regex`	answers at 1000000	answers at 1000000	answers	not needed

Two things fall out of that table that are worth more than the table itself. "Regular expressions are exponential" is not a true sentence in 2026 — it is true of Python and JavaScript, and false of Perl, Ruby and Java for most of these shapes. And the engines that are fine on the classic shapes are not fine on all shapes: Ruby's cleverness stops at {2,4}, and Perl's and Java's stop at a big enough subject. The only way to know about your pattern in your engine is to run it, which is what the programs beside this page do.

Fixing the pattern rather than the engine¶

In rough order of preference:

Stop nesting. ^a+$ answers the same question as ^(a+)+$ and gives a backtracker nothing to choose between. Ask what the outer quantifier is for; in the email pattern above, the + after ([a-zA-Z]{2,4}) is for nothing at all.
Make alternatives mutually exclusive. (a|a)* and (\s*|\t)+ are ambiguous because their branches overlap. [\s]+ covers both and cannot be split two ways.
Anchor, and make each repetition end on something fixed. (([a-zA-Z0-9\-])+\.)+ is not catastrophic, even though it looks like (X+)+, because every iteration must end on a literal . — the split points are forced. A separator inside the loop is the cheapest defence there is.
Cut the search with an atomic group or a possessive quantifier. (?>a+)+ and a++ both mean "having matched this, never give it back". Available in Perl, PCRE2 (so ABAP), Java, Ruby and Python 3.11+; absent from JavaScript, Go and Rust's regex. See atomic groups and possessive quantifiers.
Bound it from outside. Regexp.timeout= in Ruby, --match-limit in PCRE2, a budgeted CharSequence or a timeout in Java, a worker thread or a subprocess elsewhere. Treat a bound being hit as a bug report about the pattern, not as a tuning problem.
Change engine for anything untrusted. Go's regexp and Rust's regex cannot do this to you, and neither can a hand-written parser. That is the move the input validation on your public form actually deserves.

How to audit a pattern you already have¶

Five minutes per pattern, no tools:

Find the quantifiers that contain quantifiers. (X+)+, (X*)*, (X+)*, (X{2,4})+, (X?)+ — and remember that * and ? and {m,n} all count. A quantifier directly inside a quantified group is the whole signature.
Ask whether the inner thing can match the same text two ways. If each iteration must end on a delimiter the inner part cannot match — a ., a ,, a / — you are fine. If the inner part can absorb the delimiter too, you are not.
Check the alternations. Can two branches match the same string? (a|a), (\s*|\t), (\w|[a-z]) — all ambiguous.
Build the hostile subject. Take the longest run the ambiguous part accepts, make it long, and append one character that cannot match — for an anchored pattern, anything not in the final class. Do not build a subject that matches; it will be instant and prove nothing.
Run it under a cap, in a child process, at two sizes. The programs beside this page are the template: something small enough that it must answer, and something so large that no machine could. If the answer flips between the two, the pattern is a vulnerability and the size where it flips is irrelevant — a determined caller picks the size.

Then look at where the pattern is used. A pattern applied to a config file you wrote is a performance question. The same pattern applied to a header, a filename, a search box or a User-Agent is a security question, and it has a name — ReDoS.