Here is a regular expression that validates a string of letters:
^(a+)+$
It works. Test it against aaaa and it matches instantly. Test
it against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab — thirty a's and a
b — and depending on your engine and hardware, it will run for minutes,
hours, or longer than you are prepared to wait.
Nothing is broken. The engine is doing exactly what it was asked to do. It is just being asked to do an exponential amount of it.
Why it happens
Most regex engines — including JavaScript's, Python's re, Java's
and PCRE — are backtracking engines. When a pattern can match in
more than one way, they try one possibility, and if the overall match
eventually fails, they back up and try the next.
Now look at (a+)+ against a string of a's. The inner
a+ can consume any number of them, and the outer +
can repeat that group any number of times. So the a's can be divided between
the two quantifiers in an enormous number of ways: one group of thirty, two
groups of fifteen, thirty groups of one, and every arrangement in between.
For a matching string this does not matter — the first arrangement the
engine tries succeeds and it stops. The catastrophe needs a string that
almost matches. The trailing b means the
$ anchor can never be satisfied, so the engine must reject the
string — and to be certain, it has to try every possible
partition before concluding that none works.
The number of partitions grows as 2n. Thirty characters is around a billion attempts. Forty is a trillion. Adding one character doubles the work.
Why this is a security problem
If that regex validates user input in a request handler, an attacker does not need a botnet to take your service down. They need one request containing forty characters. The thread handling it stops responding, consuming CPU, until it is killed or the process dies.
This has a name — ReDoS, regular expression denial of service — and it has caused real, large outages. Cloudflare's global outage in July 2019 was caused by a single regular expression in a WAF rule containing a catastrophic backtracking pattern.
It is particularly nasty because the vulnerable pattern usually arrives through the least suspicious route: a validation regex copied from a Stack Overflow answer, applied to a field nobody thought was interesting.
The shapes to watch for
Almost all catastrophic patterns share one property: two nested quantifiers that can match the same characters. Once you know the shape it becomes easy to spot.
Nested quantifiers
(a+)+
(a*)*
(\d+)*The inner and outer quantifiers compete for the same input. This is the textbook form.
Alternation with overlap
^(a|a)+$
^(\w|\d)+$
Both branches can match the same character, so each repetition doubles the
paths to explore. \w already includes \d, which
makes the second example a slow accident rather than a deliberate one.
Adjacent overlapping quantifiers
^\s*\w*\s*$
^.*foo.*$Milder, but on a long non-matching input the engine still explores far more splits between the two quantifiers than it should.
The email regex problem
Long "RFC-compliant" email validation regexes found online are a common source, because they contain many nested optional groups over overlapping character classes. They are also unnecessary: the only reliable way to validate an email address is to send a message to it.
How to fix it
Make the parts unable to overlap
The real fix is to remove the ambiguity, so there is only one way to match.
Instead of ^(a+)+$, write ^a+$ — same language,
no nesting, linear time. Instead of ^(\w|\d)+$, write
^\w+$.
Where you need a delimiter, make the repeated part exclude it:
^(?:[^,]+,)*[^,]+$ is safe because [^,] cannot
match the comma the outer group depends on.
Anchor and bound
Anchoring with ^ and $ stops the engine retrying
from every starting offset. Replacing an unbounded + with an
explicit bound like {1,64} caps the work, and usually reflects
a real constraint you had anyway.
Limit input length first
Check the length before running the pattern. If a username cannot exceed 32 characters, rejecting anything longer costs nothing and removes the attack entirely. This is the cheapest mitigation available and it is frequently the right one.
Use an engine that cannot backtrack
RE2 — used by Go's regexp package and available for other
languages — guarantees linear time by refusing to support backreferences and
lookaround. If you are running untrusted patterns, that trade is almost
always correct.
Testing for it
The important insight is that a matching string will not reveal the problem. You have to test a near-miss: a long run of whatever the quantifier accepts, followed by one character that makes the whole pattern fail.
Take your pattern, feed it thirty repetitions of the character it loops on plus a single invalid character on the end, and see how long it takes. If it does not return immediately, you have found one.
The regex tester here runs matching in a Web Worker with a hard time limit for exactly this reason. That detail matters more than it might seem: a timeout checked inside the matching loop cannot help, because the runaway happens inside a single operation and JavaScript is single-threaded — nothing else runs until it finishes. A worker can be terminated from outside, so the page stays responsive and tells you the pattern is dangerous instead of freezing.
If you see that warning, do not ship the pattern anywhere it can meet input you do not control.