Guide

ReDoS Explained: Find Catastrophic Backtracking in Regex

Short answer: ReDoS (regular expression denial of service) happens when a regex takes exponentially or polynomially longer as the input grows, so one crafted string can freeze a server or a browser tab. Look for repeated groups whose contents can match the same text in more than one way, such as (a+)+$. Test your pattern in the Regex Tester, whose Safety check and timed test run it off the main thread with a 1.5-second limit.

What ReDoS is

Most regex engines (JavaScript, Python, Java, PCRE) are backtracking engines. Some add protection: Ruby 3.2 and later cache intermediate results, which makes many patterns run in linear time, and .NET offers an optional non-backtracking mode. Do not rely on that unless you have checked your own version. When a match fails, they go back and try every other way to split the input among the pattern's parts. For most patterns that search is short. For some patterns the number of ways grows explosively with input length. This weakness is catalogued as CWE-1333 (inefficient regular expression complexity).

The classic example:

^(a+)+$     tested against   aaaaaaaaaaaaaaaaaaaaaaaaaaaaX

The string ends in X, so the match must fail, but the engine first tries every possible way to divide the run of a characters between the inner and outer +. Each extra a roughly doubles the work.

Why it matters

  • Server outages. A single request with a crafted string can pin a CPU. Because Node.js runs JavaScript on one main thread, one slow match blocks every other request.
  • Browser freezes. The same happens in a web page that validates input.
  • It hides in ordinary code. Usernames, emails, URLs, log parsers and "trim whitespace" patterns are common victims.
  • It is not only exponential. Patterns like x+x+ or .*.* are polynomial (often quadratic). They are slower to explode but can still be abused with long inputs.

The shapes to look for

Shape Example Why it is slow
Nested quantifiers on text that can split several ways (a+)+, (a*)*, (.*)* Many ways to divide the same run
Repeated alternation with overlapping branches (a\|aa)+ The same text matches different branches
Adjacent quantified tokens matching the same characters .*.*, x+x+ Many split points between the two
Greedy .* with no ^ anchor, followed by required text .*foo on long input without foo The engine retries from every start position

A common real-world example is an email pattern such as ^\w+([.-]?\w+)*@\w+([.-]?\w+)*(\.\w{2,3})+$, which contains nested quantifiers.

How to fix a vulnerable regex

  1. Remove the ambiguity. Make sure each part of the pattern matches different characters. Replace (a|aa)+ with a+.
  2. Avoid nesting quantifiers. (\w+\s?)* can often be rewritten as [\w\s]* or split into two steps in code.
  3. Anchor the pattern with ^ and $ so the engine does not retry from every position.
  4. Limit input length before you run the regex. A 200-character username cannot hurt much.
  5. Prefer simpler validation. For emails, a loose pattern like ^[^\s@]+@[^\s@]+\.[^\s@]+$ plus a confirmation email is safer than a complex one.
  6. Use a linear-time engine such as RE2 (or Rust's regex crate) for untrusted input, when your platform allows it. These engines do not backtrack.
  7. Use atomic groups or possessive quantifiers where your engine supports them. JavaScript does not, so on Node.js and browsers rely on the steps above.
  8. Set a timeout where your platform supports one.

How to use the Regex Tester and its Safety check

  1. Open the Regex Tester.
  2. Enter the pattern (without surrounding slashes), choose flags (g, i, m, s, u) and type a test string. Matches are highlighted, with a table of position, text and groups.
  3. Open the Safety check. The pattern is read into a small syntax tree and checked for the shapes in the table above. Each finding shows its position, why it is slow and, where one is obvious, a safer rewrite.
  4. Run the timing test. It runs the pattern in a background worker on generated strings (for example, 30 to 40 repetitions of one character followed by a character that makes the match fail) and reports the time. A run longer than 1.5 seconds is stopped, so the page does not freeze.
  5. Use the Test cases and Test table features to confirm the rewritten pattern still accepts what it should and rejects what it should not.
  6. Check the Generated code section, which flags where another language's regex engine would behave differently.

Limits to know

  • The Safety check is a heuristic, not proof of safety. It can miss dangerous patterns that do not fit its shapes, and it can flag harmless ones, for example when the surrounding text can never be reached.
  • The tester runs the JavaScript (ECMAScript) engine. Python's re, PCRE, Java and RE2 behave differently. A pattern that is fine in one may be dangerous in another.
  • The timing test uses generated inputs. Your real attack string may be different. Treat a slow result as a clear warning and a fast result as encouraging, not as a guarantee.
  • Regexes inside your own trusted code are less urgent than regexes that run on user-supplied input. Prioritise those, and review AI-written patterns with extra care (see insecure patterns in AI-generated code).

Frequently asked questions

What is catastrophic backtracking? When a failed match makes the engine try an enormous number of alternative ways to match the input, so the time grows exponentially.

How do I know if my regex is vulnerable? Check for nested quantifiers, overlapping alternations and adjacent quantifiers, then run a timing test on long near-matching inputs.

Is ReDoS only a problem for exponential patterns? No. Quadratic patterns such as .*.* can also cause denial of service with long inputs.

Does limiting input length fix it? It greatly reduces the risk and is a good safeguard, but fixing the pattern is better.

Which engines are safe? Linear-time engines such as RE2 and Rust's regex crate do not backtrack, which is why they suit untrusted input.

Related tools and guides

Sources and further reading