How do I know if my pattern is vulnerable?

Look for a quantifier inside a quantified group — (a+)+, (a*)*, (\d+)* and similar — and for alternations where branches can match the same text. Then test with a long string that ALMOST matches, since near-misses are what trigger the exponential path.

Why is it fast when it matches and slow when it does not?

Because the engine can stop at the first success but must exhaust every possibility before declaring failure. With nested quantifiers the number of possibilities doubles per character, so the failing case is the only one that ever gets explored fully.

Regex Tester

Test regular expressions with match highlighting.

Pattern

Flags

Test string

All calculations performed locally in your browser. No data sent to server.

Results are for informational purposes. Verify results with other sources.

A 26-character string can take 368 ms to fail against the wrong pattern

Regular expressions usually run in time proportional to the input. Nest a quantifier inside a quantified group and that stops being true: /^(a+)+$/ takes about 23 ms to reject 22 characters, 95 ms for 24 and 368 ms for 26. Each extra character roughly doubles the work, so a slightly longer input does not slow the match down — it stops it finishing.

How it works

Tests a pattern against sample text and shows every match with its capture groups.
Explains what each part of the expression does, since the syntax is dense by design.
Lets you try the failing cases, which is where the performance problems live.

the dangerous shape: a quantifier inside a quantified group
  (a+)+   (a*)*   (a|a)*   (\d+)+

n characters can be split among the groups in exponentially many ways,
and the engine must try all of them before it can report no match

safe equivalent: a+   — one quantifier, linear time

Worked example

Timing /^(a+)+$/ against strings of a-s followed by a single ! that cannot match.

22 characters → about 23 ms
24 characters → about 95 ms
26 characters → about 368 ms
the same 26 a-s with no ! → matches in under 0.01 ms
the safe form /^a+$/ on 100,000 characters → 0.12 ms

Rejecting 26 characters costs three thousand times more than accepting 100,000. Success is instant and failure is exponential, which is why this never shows up in testing — the happy path is always fast.

Reading the result

This is a denial-of-service vector wherever user input reaches a pattern. An attacker does not need a long string; thirty or forty characters is enough to occupy a request thread for minutes, and a handful of such requests takes a server down.
The fix is almost always to remove the nesting rather than to optimise around it. (a+)+ and a+ match exactly the same language, so the vulnerable version buys nothing at all — it is a mistake, not a trade-off.
Timings are from one machine and vary by engine, but the shape does not. Any backtracking implementation — JavaScript, Python, Java, PCRE — behaves this way. RE2 and Go's regexp do not, because they refuse the features that make it possible.
Test your patterns against input that fails, not just input that matches. The catastrophic case only appears when the engine has to exhaust every possibility before concluding there is no match.

Common questions

How do I know if my pattern is vulnerable?: Look for a quantifier inside a quantified group — (a+)+, (a*)*, (\d+)* and similar — and for alternations where branches can match the same text. Then test with a long string that ALMOST matches, since near-misses are what trigger the exponential path.
Why is it fast when it matches and slow when it does not?: Because the engine can stop at the first success but must exhaust every possibility before declaring failure. With nested quantifiers the number of possibilities doubles per character, so the failing case is the only one that ever gets explored fully.

Sources

OWASP — Regular expression Denial of Service (ReDoS)