MCP server ReDoS: Regular Expression Denial of Service in input validation
Regular Expression Denial of Service (ReDoS) is a denial-of-service attack that exploits catastrophic backtracking in certain regex patterns. When a carefully crafted input string is matched against a vulnerable regex, the matching algorithm may take exponential time — seconds, minutes, or indefinitely — rather than the linear time expected. For MCP servers that use regex in input validation, a single malicious tool argument can hang the server process entirely.
How catastrophic backtracking works
Most regex engines use backtracking algorithms that explore multiple possible match paths when they encounter ambiguity. A regex like (a+)+ applied to a string of a's followed by a non-matching character triggers exponential backtracking: the engine tries matching a+ as the entire string, fails, then tries splitting it into two a+ groups, fails, then into three groups, and so on — the number of attempts grows as 2^n where n is the string length. On a modern CPU, a 40-character input can take minutes to evaluate against this pattern.
The pattern is general: any regex where (1) one quantifier can match multiple ways to match the same substring, and (2) a suffix can cause the match to fail, creates exponential backtracking risk. Common examples: (a|a)+$, ([a-zA-Z]+)*$, (a*)*$.
High-risk regex patterns in MCP server input validation
MCP server validation code commonly uses regex for: email address validation, URL validation, username/slug validation, domain name validation, and phone number validation. Many common regex patterns for these formats are ReDoS-vulnerable. Email validation is particularly dangerous — the RFC-compliant email regex is notoriously complex and catastrophically backtracking on certain inputs. URL validation regex with optional protocol prefixes and nested optional groups is also commonly vulnerable.
Test your validation regex with a tool like safe-regex (npm) or regexploit (Python) before deploying. Both analyze regex patterns for exponential backtracking potential without requiring actual attack strings.
Safe alternatives to vulnerable validation regex
For most validation use cases, you do not need a complex regex: email validation — parse with your language's URL/email library and check the domain exists via DNS; URL validation — parse with the WHATWG URL API and check the protocol and host; slug/username validation — use a simple character class without nested quantifiers (^[a-z0-9-]{3,64}$); phone number validation — use libphonenumber rather than a regex. The pattern: prefer purpose-built parsing libraries over general-purpose regex for complex format validation.
If you must use regex, follow these rules: no nested quantifiers ((a+)+ style), no overlapping alternatives that match the same characters ((a|aa)+), no patterns that can match the same string in multiple ways. Use possessive quantifiers or atomic groups where your regex engine supports them — these disable backtracking for that group.
Runtime defenses: timeouts and input length limits
Even if you cannot immediately replace all validation regex, two runtime controls reduce ReDoS impact: (1) input length limits — enforce a maximum length on all string arguments before applying regex validation. ReDoS impact is roughly exponential in input length, so a 256-character limit turns a potential hours-long hang into a few milliseconds; (2) regex execution timeouts — some runtime environments support regex execution timeouts (Node.js --jitless + worker threads with timeout, Python signal.alarm, Java Pattern.matcher with executor timeouts). This is a defense-in-depth measure, not a primary fix.
What SkillAudit checks for ReDoS
SkillAudit's Security axis includes static analysis for ReDoS-vulnerable patterns:
- Regex literals in tool argument validation code are analyzed for nested quantifiers and overlapping alternatives — flags HIGH when catastrophic backtracking potential is detected
- Email validation using custom regex (rather than a library) — flags MEDIUM (high probability of vulnerable pattern)
- URL validation using complex regex — flags MEDIUM
- Missing string length limits before regex application — flags MEDIUM (amplifies ReDoS impact)
- Known-vulnerable regex patterns from the ReDoS vulnerability database — flags HIGH with the specific CVE or advisory reference