Regular Expression Denial of Service (ReDoS) is one of the most underappreciated vulnerability classes. A single regex pattern with catastrophic backtracking can consume minutes of CPU time on a modestly sized input string. When that regex runs on your web server processing user input, one request can tie up a worker thread indefinitely.
The worst part is that ReDoS vulnerabilities often hide in dependencies you have never reviewed. Validation libraries, URL parsers, and input sanitizers all use regular expressions internally, and many contain patterns vulnerable to catastrophic backtracking.
How ReDoS Works
Most regex engines use backtracking to handle patterns with alternation and quantifiers. When a pattern like (a+)+$ is matched against the string aaaaaaaaaaaaaaaaab, the engine tries every possible way to partition the a characters between the inner and outer groups before determining that the string does not match (because of the trailing b).
For a string of length n, this creates 2^n possible partitions to try. A string of 30 characters generates over a billion backtracking steps. A string of 50 characters will not finish in your lifetime.
The vulnerable pattern (a+)+ is obviously contrived. But real-world vulnerable patterns are surprisingly common:
^([a-zA-Z0-9])(([._-])?([a-zA-Z0-9]+))*$ -- email local part validation
(.*a){20} -- repeated greedy matching
(\d+\.)+\d+$ -- version string matching
These patterns are found in production libraries. CVE-2016-4055 was a ReDoS in the moment.js date parsing library. CVE-2017-16137 was a ReDoS in the debug npm package's enabled function. CVE-2018-16492 was a ReDoS in string npm package.
Impact
ReDoS is a denial-of-service vulnerability. A single crafted request can:
- Consume 100% CPU on one core for an extended period
- Block an event loop thread (particularly devastating in Node.js)
- Exhaust the worker pool in thread-per-request servers
- Cascade into timeouts and failures across dependent services
The impact scales with the regex complexity and input length. Some vulnerable patterns can be triggered with input strings as short as 50 characters.
Where ReDoS Hides in Dependencies
Validation libraries. Email validators, URL validators, and form validation libraries extensively use regex patterns. These are often the first point of contact with user input.
Routing libraries. Web framework routers compile URL patterns into regular expressions. Complex route patterns can be vulnerable.
Content-Type parsing. HTTP Content-Type header parsers use regex to extract media type and parameters.
Syntax highlighters. Code highlighting libraries use complex regex patterns for language parsing. If they process user-supplied code, they are ReDoS targets.
Markdown parsers. Markdown-to-HTML converters use regex for inline markup detection. Complex nested markup can trigger exponential backtracking.
User-Agent parsers. Libraries that parse browser User-Agent strings use regex matching. Crafted User-Agent values can trigger ReDoS.
Detection
Static analysis tools can detect vulnerable regex patterns:
safe-regex(npm) checks patterns for exponential backtracking riskvuln-regex-detectortests patterns with crafted inputs- Semgrep and CodeQL have rules for detecting vulnerable regex patterns
redos-checkerperforms formal analysis of regex complexity
Fuzzing with long, repetitive strings against your regex patterns can reveal backtracking behavior. If a pattern takes significantly longer with slightly longer inputs, it likely has superlinear complexity.
Runtime monitoring can detect ReDoS in production. If a request handler's CPU time suddenly spikes on a specific input pattern, ReDoS is a likely cause. Timeouts on regex operations prevent individual requests from consuming unbounded resources.
Prevention
Use atomic grouping or possessive quantifiers where available. These tell the engine to commit to a match without backtracking. Most regex engines support (?>...) atomic groups.
Use non-backtracking regex engines. Go's regexp package uses a non-backtracking algorithm (RE2-based) that guarantees linear-time matching. Rust's regex crate uses the same approach. Node.js does not, but the re2 npm package wraps Google's RE2 library.
Set timeouts on regex execution. .NET supports regex timeouts via RegexOptions.MatchTimeout. For other languages, wrap regex matching in a function with a wall-clock timeout.
Validate regex patterns before deployment. Include regex complexity checking in your CI pipeline. Any new or modified regex pattern should be tested for backtracking behavior.
Simplify patterns. Many vulnerable patterns can be rewritten to be safe. Avoid nested quantifiers ((a+)+). Avoid overlapping alternation in quantified groups. When possible, use simpler string operations instead of regex.
Audit dependencies for known ReDoS. Check your dependency tree for libraries with known ReDoS vulnerabilities. Many npm packages have been affected and patched.
How Safeguard.sh Helps
Safeguard.sh monitors your dependencies for known ReDoS vulnerabilities. When a library in your dependency tree has a ReDoS CVE, Safeguard.sh alerts you with the affected projects, the vulnerable pattern, and the version that includes the fix. For applications that process untrusted input through dependency-provided regex patterns, this monitoring catches a vulnerability class that traditional security tools often miss.