CWE-1333, Inefficient Regular Expression Complexity, is the weakness behind ReDoS. A regular expression with worst-case exponential or otherwise inefficient complexity meets an input built to trigger it, and the CPU stays busy for far longer than anyone planned.
Any service that runs a regex on data it does not control can be hit: web servers parsing headers, markdown renderers, user-agent parsers, version control tools. In a single-threaded runtime one slow match can stop everything else.
How it happens
Many regex engines use backtracking. When a pattern can match the same text in several ways, the engine tries each way before it concludes there is no match. If the pattern has overlapping or nested quantifiers, the number of ways can grow explosively with input length.
A classic example in JavaScript:
// Vulnerable: nested quantifiers cause catastrophic backtracking
const re = /^(a+)+$/;
// Matches quickly
re.test("aaaaaaaaaaaaaaaaaaaaaaaa");
// Fails after enormous work, because the final "!" forces the engine
// to try every way of splitting the a's between the groups
re.test("aaaaaaaaaaaaaaaaaaaaaaaa!");
Add a few more a characters and the second call takes noticeably longer each time. The input is tiny. The cost is not.
The record lists observed CVEs where this appeared in real software:
- CVE-2020-5243: a server allows ReDoS through crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
- CVE-2021-21317: an npm user-agent parser prone to ReDoS for the same reason, overlapping capture groups.
- CVE-2019-16215: a markdown parser uses an inefficient regex on a message, so a user can cause CPU consumption and delay processing of other messages.
- CVE-2019-6785: a long string in a version control product allows denial of service because of an inefficient regex.
Two of those four are parsers for headers or text, which tells you where to look first: anything that takes user-agent strings, markdown, version strings or free text.
What an attacker gains
The consequence in the record is availability: a crafted input makes the regex use excessive backtracking and CPU spikes. There is no data theft here. The cost is that a small number of cheap requests can make a service slow or unresponsive for everyone, which is why ReDoS is also a cost-efficient attack.
How to find it
MITRE says static analysis (SAST) can find some instances by modeling data flow, and pattern analysis can flag risky regex shapes.
Practical checks:
- Search for nested quantifiers such as
(a+)+,(a*)*and alternations with overlapping branches like(a|aa)+. - Review every regex that runs on data from a request, a file or a network message, especially ones that are anchored at both ends.
- Test candidate patterns with long inputs that almost match, and time them.
- Check your dependencies. In the observed CVEs the vulnerable regex sits inside a library, not in application code. A scan of your lockfile against known advisories will surface those, and the free in-browser scanner at gold.safeguard.sh/scan (no login, file stays on your machine, up to 100 dependencies) is a quick first look. Reachability analysis then tells you whether your code actually calls the affected function.
How to fix it
From the record, with the effectiveness MITRE gives:
- Use regular expressions that do not support backtracking, for example by removing nested quantifiers. Rated high, and MITRE notes it is one of the few effective options when users supply their own regular expressions.
- Do not use regular expressions on untrusted input. If you must, avoid backtracking in the expression. Rated high.
- Limit the length of the input the regex will process. Rated moderate.
- Set backtracking limits in the regex implementation configuration, such as PHP's
pcre.backtrack_limit, and consider time limits on the process. Rated moderate.
A rewrite and a length cap for the earlier example:
// Safer: no nested quantifier, plus an input length cap
const re = /^a+$/;
function isAllA(input) {
if (input.length > 256) return false;
return re.test(input);
}
The rewritten pattern accepts the same strings as the original and has linear behavior.
Some engines, such as RE2 and the Rust regex crate, guarantee linear time matching by design and do not support features that need backtracking. If your language offers one, using it for untrusted input removes this class of bug.
Try it yourself
Pick a regex from your own codebase that runs on request data. Build a string that almost matches, double its length three times, and time each run. Linear growth is fine. Rapid growth means you have found one.
Quick check
Why does a short input cause such a long run time?
With nested or overlapping quantifiers, the number of ways to match grows exponentially with length, and a failed match makes the engine try them all.
What if users can submit their own regular expressions?
MITRE says using an engine or pattern style without backtracking is one of the few effective solutions in that case.
Is limiting input length enough?
It helps, rated moderate, but the better fix is a pattern that cannot backtrack catastrophically.
