Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 38 ยท Performance and ReDoS

Catastrophic Backtracking and ReDoS

Learn how nested quantifiers and overlapping alternations cause exponential regex time, how ReDoS attacks take servers down, and how to recognize and fix evil patterns safely.

Most patterns run in microseconds. A few can run for years. Catastrophic backtracking happens when a pattern gives the engine exponentially many ways to split the input and the match fails, so the engine tries every one. When an attacker can choose the input, this becomes ReDoS (regular expression denial of service): one small request that pins a CPU core. A single-threaded server like Node.js stops answering everyone.

Real incidents include outages at major sites and vulnerabilities reported in popular libraries, all from innocent-looking patterns for emails, URLs or whitespace trimming. This lesson shows the shape of the problem so you can spot it in review.

The classic example

Consider /^(a+)+$/ against aaaa...ab. The pattern says "one or more groups of one or more a's, then end". For an input of n letters a, there are 2^(n-1) ways to divide them into groups. The final b makes the match fail, so the engine tries every division before it gives up.

Node.js Exponential time, measured

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Run it and watch the times climb (exact numbers depend on your machine). Adding two characters multiplies the time by about four, and at 40 characters the match would take hours. The input has no special characters. It is an ordinary string.

flowchart TD
  I["Input: aaab (3 a's then b)"] --> A1["(aaa)+  then fail on b"]
  I --> A2["(aa)(a)  then fail"]
  I --> A3["(a)(aa)  then fail"]
  I --> A4["(a)(a)(a)  then fail"]
  A1 & A2 & A3 & A4 --> R["Every split fails; engine reports no match"]

Four splits for three letters; the count doubles with each additional letter.

The three evil shapes

Almost all ReDoS patterns fall into one of these:

  1. Nested quantifiers: a quantified group whose content can match in several ways, such as (a+)+, (a*)*, (\w+\s?)*, (.*a){20}.
  2. Overlapping alternation under a quantifier: (a|aa)+, (\d|\d\d)+, (.|\s)*. Both branches match the same text.
  3. Adjacent quantifiers over overlapping classes: \d+\d+$, \s*\s*, .*.*=.*. The boundary between the two is ambiguous, so the number of splits is polynomial (nยฒ, nยณ), which is slower than linear but still dangerous on large inputs.

The common ingredient is ambiguity: more than one way to match the same text. A failing match with ambiguity explores all of them.

Node.js Ambiguous alternation and polynomial blow-up

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

Real-looking vulnerable patterns

These look normal and are all risky when run on untrusted input:

JavaScript
/^(\w+\s?)*$/          // nested quantifier over overlapping content
/^([a-zA-Z0-9]+)*@/     // email local part, nested +*
/(.*)(.*)(.*)(.*)=/     // many adjacent dots
/^(([a-z])+.)+[A-Z]([a-z])+$/   // a known real-world case

For (\w+\s?)*, the optional space makes \w+\w+ splits possible: the engine can cut a word abcd into abc+d, ab+cd, and so on, then fail at an invalid final character.

How to fix

The cure is to remove ambiguity so each piece of text can be matched in only one way.

Node.js Evil pattern versus fixed pattern

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with node:readline or process.stdin), it gets the next line from this box.

General fixes, in order of preference:

  1. Flatten: (a+)+ is just a+. Many nested quantifiers are redundant.
  2. Make branches disjoint: write \d+(?:\.\d+)? rather than (\d|\.|\d\.)+.
  3. Separate with a required delimiter: (?:\w+\s)* is unambiguous because each word must be followed by one space.
  4. Bound repetition: \w{1,64} limits the damage.
  5. Limit input length before matching: reject strings over a few hundred characters for form fields.
  6. Use an engine without backtracking for untrusted patterns or inputs: RE2, Go, Rust, .NET with NonBacktracking. See hardening.

Finding vulnerable patterns

  • Look for a quantifier on a group that itself contains a quantifier or an alternation.
  • Ask: "if this fails at the very end, how many ways could the engine have split the input?"
  • Test with a long almost-matching input (valid prefix, invalid last character), as above.
  • Use a ReDoS checker in CI (several open-source tools analyze patterns statically) and treat any flagged pattern as a bug.
  • Regard patterns that users can upload as hostile code: never run them on a shared thread without limits.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is /^(a+)+$/ dangerous on the input aaaaaaaaaaaaaaaaaaaaaaaaab?

    The nested quantifier gives the engine 2^(n-1) ways to group the letters, and the final b makes every one fail.
  2. 2. Which pattern is ambiguous and therefore risky?

    Both alternatives can match the same letters, so there are many ways to cover a run of a characters.
  3. 3. What is a good first fix for (\w+\s?)* validating a sentence?

    Requiring the delimiter means each word can be matched in only one way, so a failure is detected after one pass.
  4. 4. Why is ReDoS especially harmful in Node.js?

    Node runs JavaScript on one thread, so a long regex match blocks every other request until it finishes.

Summary

  • Catastrophic backtracking comes from ambiguity: many ways to match the same text, all explored on failure.
  • The classic shapes are nested quantifiers, overlapping alternation under a quantifier, and adjacent quantifiers over the same characters.
  • ReDoS lets an attacker choose input that takes seconds or years to reject.
  • Fix by flattening, making branches disjoint, requiring delimiters, bounding repetition and limiting input size.
  • Test with long, almost-matching inputs and use a linear engine for untrusted data.

Next: Optimizing and Hardening Regex