Skip to main content

Matching a string is not free

Most engineers treat str.match(pattern) as a primitive with no cost. It is not a primitive. It is an algorithm with a worst case, and for the regex engine in almost every mainstream language, that worst case is exponential in the length of an input someone else chooses.

Two well-documented outages make the point better than any synthetic example, and both are useful precisely because neither was an attack. Ordinary traffic was enough.

Two outages​

Cloudflare, 2 July 2019​

A newly deployed managed rule for the web application firewall contained the fragment .*(?:.*=.*).

Read that as three unbounded greedy matches over the same text. The engine (PCRE) had no runaway protection, the rule was pushed globally with no staged rollout, and a CPU-usage safeguard that would have contained the blast radius had been removed during an earlier refactor.

CPU was exhausted on the cores handling HTTP and HTTPS traffic across the network. Per Cloudflare's own postmortem, global traffic dropped by 82 percent and the outage lasted 27 minutes, taking a large share of the sites behind the network down with it.

No attacker was involved. Legitimate requests hit the pathological path all by themselves.

Stack Overflow, 20 July 2016​

A single malformed post contained roughly 20,000 consecutive whitespace characters. A trimming regular expression, ^[\s\u200c]+|[\s\u200c]+$, was run over it.

The trailing half of that pattern is anchored at the end but not at the start. The engine therefore tries to begin a match at every position inside the run, and from each starting position it scans forward through all the remaining whitespace to find out whether the run reaches the end of the string. That is 20000 + 19999 + ... + 1 character-class checks. Stack Overflow's postmortem put the total at about 199,990,000.

This is the quadratic case, not the exponential one, and it was still enough. The post reached the home page, the home page was what the load balancer used as its health check, the servers failed that check, and the site was down for 34 minutes. The fix was to stop using a regex and use a plain substring trim.

If you take one thing from this guide, take that: the merely quadratic case brought down one of the highest-traffic sites on the web. You do not need the spectacular exponential blowup to have a real outage.

How a backtracking engine actually works​

There are two fundamentally different ways to implement regular expression matching, and almost every language you reach for by default picked the dangerous one.

The backtracking family includes PCRE and PCRE2, Perl, Python's re, the JavaScript engines, Java's java.util.regex, .NET's default Regex, Ruby's Onigmo, and PHP (which uses PCRE). They dominate because backtracking is the straightforward way to support the features people expect: backreferences, lookahead and lookbehind, atomic groups, possessive quantifiers.

The mental model. The engine compiles your pattern into a small program and walks the input with a cursor. When it reaches a quantifier such as a* or .*, it makes a greedy choice and consumes as much as it possibly can. Then it continues with the rest of the pattern. If the rest fails, the engine does not give up: it backs up, hands one character back to the quantifier, and tries again.

Match a.*c against axbxc:

1. `a` matches `a`.               cursor at index 1
2. `.*` is greedy, swallows `xbxc`.  cursor at end
3. pattern needs `c`, cursor is past the end.  fail
4. backtrack: `.*` gives back one char, now holds `xbx`
5. `c` matches the final character.  done

That give-back-and-retry loop is backtracking. For an unambiguous pattern there is very little of it and the whole thing runs in effectively linear time.

Why ambiguity turns linear into exponential​

The trouble starts when more than one arrangement of the pattern can match (or fail to match) the same span of text. Nest a quantifier inside another, or place two quantifiers side by side that can match the same characters, and you have created ambiguity. On failure, the engine has to try all of the arrangements before it can conclude that none of them works.

The canonical example is ^(a+)+$: one or more groups, each of one or more a characters, and nothing else on the line. Feed it twenty a characters followed by a !:

^(a+)+$   against   aaaaaaaaaaaaaaaaaaaa!

The ! guarantees the match must fail. But to prove failure the engine must rule out every way of dividing that run of twenty into ordered, non-empty groups: one group of twenty, nineteen plus one, ten plus ten, twenty groups of one, and so on. The number of such divisions (the compositions of n) is 2 to the power of n minus 1. The engine walks essentially all of them, each ending at the same dead !.

Every additional a roughly doubles the work. Twenty characters is instant. Forty is a wall.

Note what this means for testing. The pattern passes every functional test you write, because functional tests use strings that match, and a matching string finds its answer on the first path. Only a near-miss triggers the disaster: a long run that almost works and then fails at the very end. Nobody writes that test unless they already know about this.

Shapes worth recognising in review:

  • (a+)+, (a*)*, (a|a)*, (.*)*: nested quantifiers over overlapping content.
  • (\d+)*$, (\w+\s?)*$: extremely common in hand-rolled input validators.
  • (x+x+)+y: adjacent quantifiers over the same class inside an outer quantifier.
  • Email and URL validators assembled from long chains of optional groups. A large share of the most-copied "validate an email address with one regex" snippets are exponential on the right adversarial input.

A working heuristic: if two parts of your pattern can both match the same character, and one of them or an enclosing group is quantified, you probably have ambiguity. Ambiguity plus greedy quantifiers plus a failing suffix equals blowup.

Why this is worse in modern stacks​

One request can pin one core. On a runtime with a single-threaded event loop, such as Node.js, a match that runs for several seconds stalls the entire process, including every other in-flight request, because the loop cannot advance while the match is running.

The dangerous pattern is usually not yours. It lives in a validation library, a markdown renderer, a log-parsing pipeline, a user-agent parser, a routing table, or a firewall rule. Attacker-controlled text arrives via a header, a form field, a filename, a URL, or a chat message, and finds it.

The economics are absurd. A few dozen kilobytes of request body can buy minutes of server CPU. There is no rate limit that makes that trade favourable to you.

The wider family​

ReDoS is one member of a class called algorithmic complexity attacks: send a small input that forces a large amount of work by steering some library straight into its pathological case. Three siblings are worth knowing, because recognising the shape in one place teaches you to see it everywhere.

Hash flooding. Hash tables give amortised constant-time insert only when keys spread across buckets. An attacker who knows the hash function can craft many distinct keys that all land in one bucket, degrading the table to a linked list and making n insertions cost n squared. At the 28th Chaos Communication Congress in 2011, Alexander Klink and Julian Wälde showed this against nearly every mainstream web platform of the day, because HTTP form and query parameters land directly in a dictionary keyed by attacker-supplied names. The durable fix was randomised, keyed hashing: SipHash, published by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, is now the hash-table hash in Python, Ruby, Perl and Rust.

Decompression bombs. The classic recursive bomb, 42.zip, is about 42 kilobytes on disk and expands to roughly 4.5 petabytes if a tool recurses all the way down. The modern version does not even need recursion: David Fifield's 2019 paper A better zip bomb overlaps files so that many zip entries share one compressed kernel, defeating DEFLATE's per-stream ratio ceiling. His published files include a 42 kilobyte archive that expands to 5.5 gigabytes and a 10 megabyte archive that expands to about 281 terabytes. Tools that only guard against nesting are still fooled.

Entity expansion. Define an XML entity as ten copies of the previous one, nine levels deep, and a few hundred bytes of document expands to a billion copies of a short string. Same skeleton: the parser faithfully executes the attacker's expansion instructions.

Four different libraries, one shape: a cheap-looking operation, a hidden worst case, and an input the attacker controls that steers the operation into it.

The other kind of engine​

There is a completely different implementation strategy that cannot blow up on genuinely regular patterns. Instead of trying one path and rewinding, it simulates a finite automaton and tracks all possible states at once, so the work is bounded by input length times pattern size, with no partitioning to retry and therefore no exponential.

This is the RE2 approach, and Go's regexp package and Rust's regex crate both take it. Feed either of them (a+)+$ and a million near-miss characters and they finish in linear time.

The trade-off is real and it is why the world did not simply standardise on these engines: linear-time automaton engines do not support backreferences or arbitrary lookaround, because those features are not regular in the formal sense. General matching with backreferences is NP-hard, so no engine can promise both. RE2 and the Rust crate deliberately drop the features to keep the guarantee. Russ Cox's Regular Expression Matching Can Be Simple And Fast is the canonical write-up, and in practice most patterns do not need backreferences. If yours does, that is a decent signal that a real parser is the better tool.

What to check in your own codebase​

Find every regex that touches text from outside. Request bodies, query strings, headers, uploaded filenames, webhook payloads, log lines you re-parse, user-generated content you render. Include the ones inside your dependencies: validation libraries and markdown renderers are the usual carriers.

Look for the ambiguity shapes above, particularly nested quantifiers and adjacent quantifiers over overlapping character classes, and particularly in anything described as an email, URL, phone, or date validator.

Bound the input before you match it. A length cap is the crudest defence and often the most effective one, because the attack needs length to buy time. Reject a 200 kilobyte "email address" before the regex ever sees it.

Bound the match itself where your platform lets you. .NET accepts a matchTimeout on Regex. PCRE2 exposes a backtracking limit. Java's Pattern has no timeout at all, which is why the JVM shows up repeatedly as a ReDoS victim, and Node has no per-call timeout either, so teams run the match in a worker with a watchdog.

Rewrite for unambiguity. Anchor the pattern, replace unbounded + with a bounded {1,64} where the domain allows it, and use atomic groups or possessive quantifiers so the engine cannot re-partition what it already matched.

Or delete the regex. Both incidents at the top of this guide were fixed by doing less. Stack Overflow replaced a trimming regex with a substring trim. A startsWith, a split, or thirty lines of hand-written scanner is frequently faster, clearer, and immune.

Apply the same question to the neighbours. Cap decompression output size and ratio, disable DTD processing in XML parsers, and check that your JSON and YAML parsers have depth limits. Before you call any library on data a stranger can shape, know its worst case and know what input triggers it. If you cannot answer that, you have not finished reading the documentation.

Where the record is thin​

Both incidents here are unusually well documented, because both companies published detailed postmortems naming the pattern, the mechanism and the duration. The figures above come from those postmortems rather than from third-party estimates, which is why this guide carries harder numbers than most.

What is not established, and what we are not going to imply, is any estimate of economic cost for either outage. Neither company published one, and the third-party figures that circulate for outages of this kind are consultancy models rather than measurements.

Sources​

Where Vulkro fits​

Vulkro reads the regular expressions in your source for the ambiguity shapes above and reports the ones that are reachable from a route handler, which is the distinction between a pattern that is theoretically pathological and one an outsider can actually steer. It also flags the routes with no bound on how much work a caller may buy. Both run offline, on your machine.

Read next:

Last updated on