A ReDoS vulnerability turns a regular expression into a denial-of-service weapon. Most regex engines — including the ones built into JavaScript, Python, Java, and PHP — use backtracking to evaluate patterns with nested or overlapping quantifiers, like (a+)+$ or ([a-zA-Z]+)*$. Against a crafted input, that backtracking can explode from linear time into exponential time: a 30-character string can trigger over a billion internal matching steps, and a 40-character string can take longer to evaluate than the age of the universe. Attackers don't need SQL injection or a buffer overflow to take down a service — they need a single HTTP request with the right string in a form field, a URL, or a User-Agent header. ReDoS has shipped in moment.js (CVE-2016-4055), debug (CVE-2017-16137), and dozens of other widely used packages, which is why it's a routine finding in dependency scans rather than a rare edge case.
What Makes a Regex Vulnerable to ReDoS?
A regex becomes ReDoS-vulnerable when it contains nested quantifiers or overlapping alternation that force the backtracking engine to try many equivalent ways to fail a match. The canonical example is (a+)+$: matched against "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" (30 a's followed by a non-matching character), a backtracking engine tries every way to partition the a's between the outer and inner + groups before concluding there's no match — 2^30, or roughly 1.07 billion, partitions. Other common vulnerable shapes include (.*a){x} for repeated greedy matching and (\d+\.)+\d+$ for version-string parsing. These aren't academic constructs; they show up in email validators, URL parsers, and log-format matchers because developers write + and * next to each other without checking for ambiguity.
How Fast Does a ReDoS Attack Actually Escalate?
A ReDoS attack escalates exponentially with input length, not linearly, which is what makes it so cheap for an attacker and so damaging for a defender. Security researcher James Davis's 2019 study of npm packages found that regex complexity for real-world vulnerable patterns typically follows O(2^n) or O(n^2) to O(n^3) growth relative to input length. In practical terms: a vulnerable pattern that takes 10 milliseconds to evaluate against a 20-character string can take over 1,000 seconds against a 40-character string — a 100,000x increase in CPU time for doubling the input size. An attacker can automate a scan that pads the malicious substring by one character at a time and watch response latency climb until a single request pins a CPU core indefinitely, at essentially zero cost to send.
Which Real CVEs Show ReDoS Is a Practical, Not Theoretical, Risk?
ReDoS is a practical risk because it has produced dozens of CVEs in mainstream libraries, several with CVSS scores of 7.5 or higher. CVE-2021-23364 affected browserslist, a package with tens of millions of weekly npm downloads that ships transitively inside Autoprefixer and most modern JavaScript build tooling. CVE-2021-3807 hit ansi-regex, used to strip ANSI color codes from terminal output across the Node.js ecosystem, and was rated CVSS 7.5. CVE-2017-16137 was found in the enabled function of the debug package — a logging library present in the dependency tree of a large share of all npm projects at the time. In each case, the fix was a version bump, but identifying every transitive path that pulled in the vulnerable version required walking the full dependency graph, not just the top-level package.json.
Which Regex Engines Are Actually Safe from Catastrophic Backtracking?
Regex engines built on finite automata rather than backtracking — RE2, Go's regexp package, and Rust's regex crate — guarantee linear-time matching regardless of the pattern, making them immune to catastrophic backtracking. Node.js, Python's re, Java's java.util.regex, PCRE, and PHP's preg_* functions all use backtracking engines by default and are exposed to ReDoS unless a specific pattern happens to avoid ambiguity. Google's RE2 library, available for Node.js via the re2 npm package, trades a small set of unsupported features (like backreferences) for that linear-time guarantee. .NET's regex engine sits in between: it still backtracks, but supports a built-in RegexOptions.MatchTimeout that can cap worst-case execution at the cost of failing legitimate requests during an attack rather than hanging indefinitely.
How Do You Detect a ReDoS Pattern Before It Ships?
You detect a ReDoS pattern before it ships by running static complexity analysis on every regex literal at commit time, rather than waiting for a production incident. Tools like the npm safe-regex package and Semgrep's regex-complexity rules flag patterns with nested quantifiers or ambiguous alternation without needing to execute them. CodeQL includes a dedicated js/redos query that has been used to find ReDoS bugs across open-source JavaScript repositories on GitHub's own security lab research. For patterns that pass static checks but still warrant confirmation, targeted fuzzing — feeding a candidate pattern strings of increasing length (10, 20, 30, 40 characters) and timing each match — reveals superlinear behavior directly: if evaluation time roughly doubles when input length increases by a fixed increment, the growth is exponential and the pattern needs to be rewritten or timeout-bounded.
How Safeguard Helps
Safeguard's reachability analysis determines whether a ReDoS-vulnerable regex in your dependency tree — like the ones behind CVE-2021-23364 or CVE-2021-3807 — is actually invoked on attacker-controlled input, or sitting in a code path your application never exercises, so triage is based on exploitability rather than raw CVSS score. Griffin AI, Safeguard's remediation engine, correlates that reachability signal against your live SBOM to prioritize the ReDoS findings that matter and opens auto-fix PRs with the patched version pinned, including overrides/resolutions entries for transitive dependencies that would otherwise stay vulnerable after a top-level bump. Safeguard both generates SBOMs from source and ingests existing CycloneDX/SPDX documents, so the dependency graph used for that correlation stays accurate as your build tooling and transitive packages change. The result: your team spends time merging a tested fix instead of manually tracing which of your dozens of services actually import the vulnerable regex.