A regular expression that works on every normal input can still take a server down, because the damage depends on the shape of the pattern and on one kind of hostile input, not on traffic. The engine in Node and in browsers tries alternatives one after another, and for some patterns the number of alternatives doubles with every extra character. A text that fails to match is the worst case, since the engine will not give up until it has explored every way of splitting the text. A visitor who sends one long, almost-valid string can keep a process busy for minutes. Below you will find the mechanism, the pattern shapes that cause trouble, rewrites that leave the accepted set untouched, and a verification step that is able to fail. The name for the failure is catastrophic backtracking, and the attack that exploits it is called ReDoS.

Why one request stops everyone

Node runs your JavaScript callbacks on one main thread. The Node.js documentation says that while this thread is busy with one client it cannot serve any other, and that a malicious client able to find an input that blocks it has a ready-made denial of service (Node.js, Don't Block the Event Loop). The same page names vulnerable regular expressions as a common way to block that thread, and points out something worth remembering: a match usually comes back fast, even for a bad pattern on a long text. The blowup happens on a mismatch, because the engine cannot be sure until it has tried many paths.

That explains why these bugs survive review and testing. Test cases are mostly valid values, and the few invalid ones are short. The pattern only misbehaves on long text that fails near the end, which nobody wrote a test for.

What the engine is doing

OWASP describes the engine as a state machine that, wherever several next steps are possible, tries them one by one and returns to the last choice when a path fails. Its example is the pattern ^(a+)+$: for a short string of a's followed by an X there are 16 possible paths, and for a longer one there are 65,536, with the count doubling for every additional character (OWASP, ReDoS). At that rate, a few dozen characters are enough to outlast most request timeouts.

This is a property of backtracking engines. Node's documentation names the RE2 engine as an alternative, and says that backreferences cannot be promised linear time by any engine (Node.js, Don't Block the Event Loop).

It has happened to a large network

In July 2019 a single firewall rule containing a pattern that backtracked enormously used up the processors serving web traffic, and visitors to every domain behind that network saw error pages. The write-up lists several causes that lined up, among them a pattern that could backtrack, a regex engine without complexity guarantees, and a test suite that could not notice heavy processor use. The fixes that followed included profiling every rule's cost in tests and moving to engines with run-time guarantees (Cloudflare, outage details). One lesson for a small service is that a guarantee built into the engine is a stronger protection than the care of each author.

Shapes worth searching for

OWASP calls a pattern "evil" when it has a repeated group and, inside that group, either another repetition or alternatives that overlap. Its examples include (a+)+$, ([a-zA-Z]+)*$ and (a|aa)+$ (OWASP, ReDoS). In real code the same ideas are harder to see:

  • A repeated group whose content is itself a run, such as (\w+\s?)*. The space is optional, so two runs can sit side by side, and one stretch of letters can be split between the loop passes in a huge number of ways.
  • Alternatives that begin with the same character, such as (\d+|\d+\.\d+)+. Each position offers a choice that leads to the same place.
  • A greedy dot inside a repeat, such as (.*,)*end, where every comma can close any of the groups.
  • A fixed repeat count around a run, such as (a+){8}, which lets eight runs share one stretch of a's in many splits. The growth here is polynomial rather than exponential, but still steep.
  • A backreference to a group that holds arbitrary text, which no engine can guarantee to run quickly.

A quick way to read a pattern is to ask, at each character of a failing input, how many different parts of the pattern could have consumed it. If the answer is ever more than one for the same stretch, the number of paths multiplies.

Rewrite so each character has one owner

The reliable cure is to state in plain words which texts are accepted, then build a new pattern where each character has just one possible owner. Typical moves:

  • Flatten nested repetition. (a+)* accepts exactly what a* accepts.
  • Merge alternatives into a class, so (x|y|z)+ becomes [xyz]+.
  • Put the separator between items instead of after each item. A list of numbers with optional commas, ^(\d+,?)+$, accepts digit runs separated by single commas with an optional comma at the end. The safe version is ^\d+(?:,\d+)*,?$: each comma must be followed by digits, so the two parts of the pattern can never compete for the same character.
  • Swap a greedy dot ahead of a fixed character for a negated class that cannot swallow that character, where the accepted set allows it.
  • When you only call test() and the pattern has no anchor, a long run before a fixed character can often shrink to one character, because the answer is already yes once the shortest example appears.

Keep the anchors and flags exactly as they were. Adding or dropping an anchor changes the accepted set, and so does a change of flags. Do not reach for atomic groups or possessive quantifiers either: JavaScript has neither, and a lazy quantifier reorders the attempts without reducing how many there are.

Contain what you cannot rewrite

Some patterns cannot be repaired, and some belong to other people. Three containment steps help:

  1. Cap the length of any text before it reaches a pattern. Most fields have a sensible maximum, and a cap turns an exponential problem into a small one.
  2. For simple needs, skip the regex. Node's documentation suggests plain indexOf for an ordinary substring search, since it is cheaper and never worse than linear (Node.js, Don't Block the Event Loop).
  3. For patterns you must keep, use an engine with a run-time guarantee. The same page mentions the RE2 engine through the node-re2 module, with a warning that it is not fully compatible and that very complicated patterns are unsupported, so retest after swapping.

Also never build a pattern from user input. Otherwise a hostile user can supply the evil pattern themselves. Escape the text, or use a plain string search.

A check that can fail

Run two checks on every pattern you change. They take a few minutes and catch the usual mistakes.

First, timing. Build a long near-miss: a stretch of valid characters followed by one stray character that spoils the match. Time it at a few lengths, adding two characters per step. For a vulnerable pattern the time keeps multiplying; for a safe one it creeps up slowly, in proportion to the size of the input. Run the same script on a long input that does match, as a control (the last column in the script below): if that one is also slow, your timer or your sample is measuring something else.

function time(re, text) {
  const t = process.hrtime.bigint();
  re.test(text);
  return Number(process.hrtime.bigint() - t) / 1e6;
}
for (const n of [18, 20, 22, 24]) {
  const bad = "a".repeat(n) + "!";
  console.log(n, time(/^(a+)+$/, bad).toFixed(1), time(/^a+$/, bad).toFixed(1), time(/^(a+)+$/, "a".repeat(n)).toFixed(1));
}

Second, equivalence. Generate every string over a small alphabet up to a modest length, and compare the verdicts of the original and the replacement on each one. Make sure the set includes the empty string, a leading separator, a trailing one and a doubled one, because hand-made rewrites go wrong there most often. Break the new pattern on purpose once, for example by dropping the optional trailing comma, and confirm that the comparison goes red. A comparison that stays green when the rewrite is wrong tests nothing.

When this does not apply

Everything here concerns backtracking engines such as the ones in Node and browsers. Engines built on automata, such as RE2, do not have this problem, though they lack features like backreferences. The timing loop is a rough tool: results vary by machine and engine version, and a pattern that is slow only for some rare shape of input needs a fuzzer or a static analyser to find it, neither of which is covered here. Some requirements describe a set that cannot be written as a plain pattern at all, for instance that the same arbitrary word appears twice; for these the honest answer is to parse the text in code instead. No new experiments were run for the text you are reading: the facts come from the three pages cited, and the examples are illustrations, not measurements. Our rewrite examples are small, and a rewrite of a large real-world pattern needs the equivalence check above before it ships.

Trusting a pattern with untrusted text is the same kind of slip as the loose rules we describe in our article on browser cross-site permissions, where one permissive line gives access to anyone who knows how to ask.

Rewriting the pattern with a skill

When a JavaScript pattern of yours hangs and you want help repairing it, our redos-regex-rewrite skill reads the pattern and its flags and answers with a replacement as JSON. The replacement is meant to give an identical verdict on every input while its work stays proportional to the input size. The flags stay as given, a pattern that is already safe comes back untouched, and where the original depends on a backreference comparing arbitrary pieces of text, the skill states that no equivalent exists rather than guessing. Widening the rules is outside its job.

Read this post as Markdown: /blog/redos-regex-locks-server.md · Atom feed.