Quick answer: ReDoS (Regular Expression Denial of Service) is when a poorly designed regular expression runs for an excessively long time on a carefully chosen short input, exhausting the server's CPU. The root cause is "catastrophic backtracking": some regex engines try an exponential number of paths relative to input length to find a match in patterns with nested and ambiguous repetition (for example (a+)+$). An input of 30 to 40 characters can lock a single request onto a CPU core for seconds or minutes; a few concurrent requests stall the whole server. The fix is to use a linear-time regex engine that does not backtrack (for example RE2), put a timeout on regex execution, limit input length, and weed out dangerous patterns (nested quantifiers, overlapping alternation).

ReDoS is a quiet flaw, less visible than injection, yet a single bad line can bring an entire service to its knees. Its most dangerous aspect is that the harmful regex usually looks completely innocent and causes no trouble with normal inputs; the flaw is triggered only by an input the attacker carefully crafts. This guide explains what causes catastrophic backtracking, which patterns and inputs are dangerous, how it is detected, and the lasting defense.

Why catastrophic backtracking happens

Most traditional regex engines work with "backtracking": when a match attempt fails, the engine goes back and tries another possibility. For most patterns this is fast. But if the pattern contains nested or overlapping ambiguous repetition, the number of paths the engine must try grows exponentially with input length.

The classic example is the pattern (a+)+$. When the input is aaaa...aaaX (with a character at the end that breaks the match), the engine tries an astronomical number of combinations for how to split the "a"s into groups, all of which fail, and it backtracks for each one. With 20 "a"s it is unnoticeable, with 30 "a"s it can take seconds, with 40 "a"s minutes. The input is short but the processing time explodes. This is called exponential ReDoS. Non-nested but overlapping alternation (like (a|a)*) shows a milder but still dangerous growth.

The key point: this is not a logic error, it is a natural consequence of how the engine works. The pattern is not wrong, but the work the engine does for that pattern is expensive.

Which patterns and inputs are dangerous

Risk signal Example pattern Note
Nested quantifier (a+)+, (a*)* The most dangerous, exponential
Grouped repetition + suffix (\d+)*$, (.*a){10} Explodes with a breaking character
Overlapping alternation (a|a)*, (|a)+ Produces ambiguity
Greedy .* chains something like (.*,){20} Slow on long input
Regex compiled from user input user supplies a regex Also an injection risk

The danger is often in unexpected places: email validation regexes, URL parsers, input-sanitization rules, log parsing, and regexes inside third-party libraries. A single weak regex in an old version of a library can expose your application to ReDoS even if your own code is flawless; this is why dependency currency matters and aligns with the discipline we cover in our patch management article.

How it is detected

There are two ways to detect it. The static way is to use tools that scan all regexes in the code base and flag dangerous patterns such as nested quantifiers and overlapping alternation; this is the most effective method during development. The dynamic way is to send malicious inputs of increasing length to an endpoint and watch whether the response time diverges quickly from linear: if the time grows exponentially as input length increases, ReDoS is confirmed.

A caution for dynamic testing: ReDoS is a direct DoS attack, so it must be done only in an authorized test environment and with controlled input lengths; the goal is to prove the flaw, not to actually crash the target. We cover the general defense of the denial-of-service class in our DDoS attack and defense article; ReDoS is an "application-layer" DoS that happens with a single bad input and needs no network volume.

The lasting defense: engine, timeout, input limit

The fix for ReDoS is to both correct the pattern and constrain the engine and the input:

  • Use a linear-time engine. A regex engine that does not backtrack and runs linearly with input length (for example RE2) ends ReDoS at the root, because exponential explosion becomes impossible. Where possible, prefer such an engine on critical paths.
  • Put a timeout on regex execution. If your platform supports it, give every regex match a time limit; an operation that exceeds it is cancelled. This way a single bad input cannot lock a core indefinitely.
  • Limit input length. Always cut the data entering a regex at a reasonable upper bound (for example a few hundred characters for an email); the attacker needs a certain length for exponential explosion, and short input shrinks the risk.
  • Weed out dangerous patterns. Rewrite nested quantifiers ((a+)+) and overlapping alternation; in most cases the same goal can be expressed with a pattern that does not produce ambiguity.
  • Do not accept regexes from users. Compiling and running a user-supplied regex on the server carries both ReDoS and logic risk; if needed, do it with strict limits and a safe engine.
  • Keep dependencies up to date. Known ReDoS flaws in libraries are closed with regular patching; do not leave old versions.

The KAOS and DSET approach

At DSET we treat ReDoS as part of application-layer denial-of-service testing, because a single bad regex can take down your service without any need for a volumetric DDoS. In our tests we send malicious inputs of increasing length to input-validation and search endpoints and measure whether the response time diverges exponentially, and we do not merely detect the flaw but verify it by proving the time-length relationship and showing which regex is responsible; we always keep the test controlled and within limits that will not crash the target. Our KAOS tool flags dangerous regex patterns such as nested quantifiers in code and dependencies, but it ties the final verdict to measured behavior. To have your application tested against ReDoS and application-layer DoS, contact DSET and reach our team at Ankara Hacettepe Teknokent.

Frequently asked questions

Is ReDoS a real risk, or a theoretical one? It is a real risk, exploited in the field. ReDoS flaws have been found and patched again and again in large libraries and popular applications. Because a single bad regex can keep a single-threaded request busy for minutes, a few concurrent requests make the whole server unresponsive. Its impact is high while its cost is low, which makes it attractive to attackers.

Is every regex open to ReDoS? No. The risk arises in patterns that contain nested or overlapping ambiguous repetition; flat regexes with no ambiguity are safe. In addition, if you use a linear-time engine (like RE2), there is no exponential explosion whatever the pattern. The risk comes from the combination of a backtracking engine and an ambiguous pattern.

Is limiting input length enough on its own? It reduces the risk but is not a guarantee on its own, because some patterns slow down seriously even with short inputs and even a "reasonable" limit may be large enough. The most robust fix is layered: a linear-time engine or a timeout as the primary defense, with input limits and rewriting of dangerous patterns as complements. Do not rely on a single measure.

Sources

  • OWASP, Regular Expression Denial of Service (ReDoS) explanation.
  • CWE-1333 (inefficient regular expression complexity).
  • Google RE2 linear-time regex engine and technical references on catastrophic backtracking.
  • DSET blog: DDoS attack and defense and patch management.