flawopen.com/ReDoS/Explained
Most regex engines backtrack: when a match fails they retry other ways of splitting the input. Certain patterns make the number of ways to try grow exponentially with input length, so a few dozen carefully chosen characters can pin a CPU core for minutes or hours. One request takes down a server.
# Nested quantifier ^(a+)+$ # Alternation with overlap, quantified ^(a|a)*$ ^(\w|\d)*$ # The classic "validate an email" ^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z0-9]{2,4})+$ # Input that triggers it: a long run # of matching chars followed by ONE # character that makes the match fail # "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!"
# 1. Remove the ambiguity — one way # only to match any given string ^a+$ # 2. Anchor and bound the length ^[a-z0-9]{1,64}$ # 3. Check length BEFORE matching if len(value) > 256: reject() # 4. Use a non-backtracking engine # (Go regexp, Rust regex — both # are linear time by design) # 5. Don't use a regex for email. # Use a parser, or just send mail.
A pattern like (a+)+ is ambiguous: the string aaaa can be divided among the inner and outer quantifiers in many different ways, and all of them match. That is harmless while the overall match succeeds, because the engine stops at the first success.
The attack appends a character that makes the whole pattern fail. Now the engine must prove no division works — so it enumerates every one of them. The number of divisions grows exponentially in the length of the run, which is why adding a handful of characters can move the runtime from milliseconds to years.
Input validation is the obvious place, but the higher-risk cases are often less visible: parsing User-Agent or other request headers, log processing pipelines, Markdown and syntax highlighting, URL routing rules, content filters and WAF rules, and any library that runs a regex over a field you pass it. Several widely used packages have shipped ReDoS advisories for exactly this reason, so your dependency tree matters as much as your own patterns.
Those with backtracking engines — JavaScript, Python, Java, .NET, PHP, Ruby, Perl. Go's regexp and Rust's regex crate use finite-automaton approaches with linear-time guarantees and are not vulnerable to this class, at the cost of not supporting backreferences and lookaround.
It is the single most effective cheap mitigation, because the blow-up depends on input length. Bound it tightly — a limit of 100 characters still permits a very long computation with a badly ambiguous pattern, so fix the pattern too.
Static analysers exist for this specifically, and several linters flag known-dangerous shapes. As a manual heuristic, look for a quantifier applied to a group that itself contains a quantifier or an alternation whose branches can match the same text.
.NET supports a regex match timeout and it is worth setting. Most other runtimes have no built-in equivalent, and running the match in a separate process or worker purely to time it out is usually more complexity than fixing the pattern.