Fix regex "Catastrophic backtracking"

What the error means

Catastrophic backtracking is not a compile error; the pattern is valid. It is what happens at match time when a backtracking engine — which is every JavaScript engine — has to explore an exponential number of ways to divide the input between quantifiers before it can conclude that there is no match. The tester detects a match that is taking far too long and stops it, because an unchecked one would freeze the tab, and on a server the same pattern is a denial-of-service vector known as ReDoS.

The example is the textbook case. Against aaaaaaaaaaaaaaaaaaaaaaaaaaaaX the engine tries every way to split the run of as between the inner a+ and the outer + before giving up at the X. With 25 as that is tens of millions of attempts; each extra a doubles it.

Why it happens

• Nested quantifiers: (a+)+, (\w*)*, (.*)*. The inner and outer repetition can both claim the same characters, so there are exponentially many partitions to try.
• Overlapping alternatives under a quantifier: (a|aa)+, (\d|\d+)*. Same effect, harder to see.
• Ambiguous separators: (\w+\s?)* lets \w+ and the optional \s? trade characters back and forth.
• A non-matching input. Successful matches are usually fast; the blow-up happens when the engine must prove failure, which is exactly the input an attacker supplies.

How to fix it

1. Paste the pattern into the tester above with a long non-matching input, such as thirty as followed by X. If the tester aborts, the pattern is vulnerable.
2. Remove the nesting. (a+)+ matches exactly what a+ matches; (\w+\s?)* is usually better written as \w+(\s\w+)*, where the separator is mandatory between words and the engine has one way to proceed.
3. Anchor the pattern (^ and $) so the engine does not retry from every starting position.
4. Make quantified alternatives mutually exclusive: (\d+|[a-z]+) cannot overlap, (\d|\d+) can.
5. Test again with the same hostile input. A safe pattern fails in microseconds.

The corrected example:

^a+$

If it still fails

• JavaScript has no possessive quantifiers or atomic groups; where the pattern really needs them, restructure it, or validate the input's length and shape before running the regex.
• Patterns that parse untrusted input on a server deserve a timeout or a linear-time engine (RE2-style) rather than trust.
• Regex Generator produces patterns for common formats that have already been written to avoid these shapes; compare its output with yours using Diff Checker to see where the nesting crept in.