ReDoS (Regular Expression Denial of Service): When Regex Becomes a Weapon

Regular Expression Denial of Service (ReDoS) is a vulnerability where a crafted input string causes a regular expression engine to enter catastrophic backtracking, consuming exponential CPU time and effectively freezing the application. A single malicious request can hang a server thread for minutes or hours, causing denial of service.

Mapped to CWE-1333 (Inefficient Regular Expression Complexity) and classified under denial of service attacks, ReDoS exploits the computational behavior of NFA (Nondeterministic Finite Automaton) based regex engines used by JavaScript, Python, Java, and most other languages. These engines try multiple matching paths and backtrack when a path fails—a process that becomes exponential with certain patterns and inputs.

ReDoS is particularly insidious because the vulnerable regex may work correctly for all legitimate inputs. The vulnerability only manifests when an attacker provides a specifically crafted input designed to maximize backtracking.

Catastrophic backtracking occurs when a regex contains ambiguous quantifiers that allow the engine to match the same characters in multiple ways. Consider this regex for validating email-like strings:

/^([a-zA-Z0-9]+)+@/

The nested quantifier ([a-zA-Z0-9]+)+ creates ambiguity: for the input aaaa, the engine can split the characters across groups in exponentially many ways: (aaaa), (aaa)(a), (aa)(aa), (aa)(a)(a), (a)(aaa), and so on.

When followed by a character that prevents the overall match (like an input of aaaaaaaaaaaaaaaaX), the engine tries every possible grouping before concluding the match fails. With 16 repetitions, there are 2^16 = 65,536 combinations. With 30 repetitions, the engine cannot finish in any reasonable time.

Vulnerable Patterns

Three regex constructs are most commonly vulnerable:

• Nested quantifiers: (a+)+, (a*)*, (a+)*
• Overlapping alternatives: (a|a)+, (\d+|\d+\.\d+)
• Adjacent quantifiers with overlap: \d+\d+, .*.*

In JavaScript (Node.js), regex executes on the main event loop. A ReDoS attack blocks the entire server, affecting all concurrent requests—not just the attacker's request.

• Cloudflare Outage (2019): A WAF rule with a vulnerable regex caused catastrophic backtracking, taking down Cloudflare's entire global network for 27 minutes. A single regex brought down a CDN serving millions of websites.
• Stack Overflow (2016): A regex in the server-side Markdown renderer caused a 34-minute outage when processing a specific post, locking up web server threads.
• npm packages: Numerous widely-used npm packages including ua-parser-js, moment (date parsing), and color-string have had ReDoS vulnerabilities disclosed, affecting millions of downstream applications.

These incidents demonstrate that ReDoS is not theoretical—it causes real production outages at massive scale, and the vulnerable patterns are commonly found in input validation, URL parsing, and data processing code.

CodeSlick identifies ReDoS-vulnerable regular expressions in JavaScript, TypeScript, and Python code:

• Nested quantifiers that create exponential backtracking: (a+)+, (a*)*, (a+)*
• Overlapping alternation groups that multiply matching paths
• Regex patterns applied to user-controlled input without length limits

ReDoS findings include CWE-1333 classification and severity scoring based on the input context (user-controlled input is rated higher). CodeSlick's AI-powered fixes suggest safe regex alternatives, atomic grouping where supported, and input length validation as a defense-in-depth measure.