Regular Expression Denial of Service (ReDoS)
A regular expression applied to user input can take exponential time on crafted input, letting a few requests tie up the server's processing capacity.
| Severity | Medium |
| CVSS 3.1 | 5.3 CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L Open in the calculator |
| CVSS 4.0 | 6.9 CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N Open in the calculator |
| CWE | CWE-1333: Inefficient Regular Expression Complexity |
| MITRE ATT&CK | T1499.004 Application or System Exploitation |
| Category | Input Validation |
Description
The application validates or parses user-supplied input with a regular expression whose matching time can grow exponentially, or polynomially to a high degree, with the length of the input. Most regular expression engines in common use, including those in JavaScript, Java, .NET, Python and PCRE, work by backtracking. When part of a pattern can match the same characters in many different ways, for example through nested quantifiers such as (a+)+ or overlapping alternatives such as (a|aa)*, a string that almost matches but then fails forces the engine to try every combination before giving up.
A short input of a few dozen characters can therefore keep a processor core busy for seconds, minutes or longer, so an unauthenticated attacker can degrade or deny service to all users by sending a small number of crafted requests, with little bandwidth and no special tooling. The effect is most severe on single-threaded runtimes such as Node.js, where one slow match blocks the event loop and every other request waits, so a single request can make the whole application unresponsive; on any platform a handful of concurrent requests can occupy all worker threads. The effect usually lasts only while the attack continues, platforms that scale automatically may add capacity and cost, and the weakness does not expose or change data. Where the vulnerable pattern is reachable only after authentication, or input length is already tightly limited, the practical impact is lower.
The issue is identified by reviewing patterns applied to untrusted input, in validation code, routing, parsers and third-party libraries, by static analysis tools that flag catastrophic backtracking, and by sending crafted near-matching strings of increasing length while measuring response times. Testing is normally limited to demonstrating a measurable slowdown rather than an outage.
Remediation
- Rewrite vulnerable patterns so that each part of the input can be matched in only one way: remove nested quantifiers and overlapping alternatives, anchor the pattern, and use possessive quantifiers or atomic groups where the engine supports them.
- Where available, use a linear-time engine for untrusted input, such as RE2 and its bindings, the Go
regexppackage, the Rustregexcrate orRegexOptions.NonBacktrackingin .NET 7 and later. - Enforce a maximum input length before any pattern is applied.
- Set a match timeout where the platform supports one, such as the
matchTimeoutargument of the .NETRegexconstructor, and treat a timeout as a validation failure. - Prefer well-tested library validators for common formats such as email addresses and URLs over hand-written patterns, and keep third-party libraries up to date, as many ReDoS flaws are fixed in library releases.
- Add a regular expression linter or static analysis rule to the build to catch new vulnerable patterns.
Rate limiting reduces the effect while patterns are corrected but does not remove it. Confirm the fix by repeating the crafted inputs and checking that response times stay flat as input length grows.
References
Add This Finding to Your Library
In Pental this write-up is in Settings, Library. Add to my library copies it into your own, rated in your firm's CVSS version, ready to put in your own words.
Free trialYour trial starts when your portal goes live, not when you sign up, so the time you spend setting up does not count. · No card required
Only need the reporting? Our reporting tool is free and open source, with the same library.