Writing regular expressions that do not hang

A regular expression can be correct, readable and still capable of freezing a server. The failure mode is not obvious from reading the pattern, and it has a name: catastrophic backtracking. Understanding it takes about five minutes and prevents an entire class of outage.

The flags, briefly

Most confusion about regex behaviour is really confusion about flags.

• g — find every match rather than stopping at the first. Its absence is the single most common “why does it only find one” complaint.
• i — case insensitive.
• m — multiline, which makes ^ and $ match at every line break rather than only at the start and end of the whole string.
• s — dotAll, which lets . match a newline. By default it does not, which is why a pattern that works on one line fails across two.
• u — Unicode mode, needed for \p{...} property escapes and correct handling of characters outside the basic plane.

Greedy and lazy quantifiers

By default, quantifiers are greedy: they consume as much as possible and then give characters back until the rest of the pattern matches. That is why the classic HTML-tag mistake behaves as it does.

Text:    <b>bold</b> and <i>italic</i>

/<.+>/   matches:  <b>bold</b> and <i>italic</i>   ← the whole line
/<.+?>/  matches:  <b>                              ← just the tag

Adding ? makes a quantifier lazy: take as little as possible. Better still is to exclude the terminator entirely — /<[^>]+>/ — which cannot overshoot in the first place and is faster because it never needs to backtrack.

Why a pattern hangs

JavaScript, like Perl, Python, Java and .NET, uses a backtracking engine. When a match fails it returns to the last choice point and tries a different split. Usually there are few choice points. Sometimes there are exponentially many.

/(a+)+$/ tested against "aaaaaaaaaaaaaaaaaaaaaaaaaaX"

The inner a+ can match one a, or two, or all of them, and the outer + can repeat that grouping any number of times. For a string of n letters there are exponentially many ways to divide it, and because the trailing X means nothing can ever succeed, the engine tries all of them. Twenty-five characters is enough to take longer than you will wait; a few more and the tab is gone.

The shape to look for

The danger sign is nested repetition where the inner and outer parts can match the same characters. Three examples that look harmless:

• (a+)+ — the textbook case
• (a|aa)+ — alternatives that overlap
• ^(\w+\s?)*$ — a very common “words separated by optional spaces” pattern, and a genuine hazard, because \w and \s? can both consume in ways that overlap

This is a real availability risk. Denial of service through a crafted input to a vulnerable pattern is a recognised vulnerability class, and it has taken down production services at well-known companies.

How to write patterns that cannot blow up

1. Avoid nesting quantifiers. If you find yourself writing (x+)+ or (x*)*, restructure.
2. Use negated character classes. [^"]* instead of .*? when scanning to a delimiter. It is both faster and unambiguous.
3. Anchor where you can. ^ and $ cut the search space dramatically.
4. Bound your repetition. {1,64} instead of + puts a ceiling on the work.
5. Test with input that fails. Backtracking blows up on near-misses, not on matches. Test a long string that almost matches.
6. Do not build a pattern from user input without escaping it. That is regex injection, and it hands an attacker the ability to author the pattern.

The right tool for the job

Some things should not be matched with a regular expression at all. Parsing HTML is the famous one — nested structures are beyond what regular expressions can describe, so use a parser. Email validation is another: the full specification is far more permissive than any pattern people actually write, and the only reliable check is to send a message and see whether it arrives. Checking for an @ with something either side is enough for a form.

Test before you deploy

The regular expression tester runs your pattern against sample text using the browser’s own engine, so what you see is what JavaScript will do. Test three things every time: input that should match, input that should not, and input that almost matches. The third one is where both correctness bugs and performance disasters show up.

One caveat that matters when copying patterns from the internet: regex dialects differ. Lookbehind, named groups, recursion and possessive quantifiers vary between JavaScript, PCRE, Python, Go and Java. A pattern verified in one is not verified in another.