CWE-407 describes code whose worst-case running time is much worse than its typical running time, where an attacker can choose inputs that reach the worst case. The input is small. The bill in CPU time is large.
Anything that parses, sorts, matches or hashes untrusted data can be affected: web servers, parsers, email validators, image libraries and language runtimes.
How it happens
Most code is tested with friendly data. A loop that is fine for 100 items becomes a problem at 100,000 if it does work proportional to the square of the input. MITRE's observed examples show the pattern repeating across very different products:
- A C++ image metadata library re-parsed the input every time it hit an invalid character, which gives quadratic behavior (CVE-2021-32617).
- Python's conversion of a string with many digits in unexpected bases was quadratic (CVE-2020-10735).
- A server was exposed to regular expression denial of service through crafted User-Agent strings, because overlapping capture groups caused heavy backtracking (CVE-2020-5243).
- A Perl email address parser had quadratic behavior on a string that was not a valid address (CVE-2014-1474).
Regular expressions are the classic case. Nested quantifiers let the engine try an exponential number of ways to match.
import re
# Vulnerable: nested quantifier backtracks badly on "aaaa...!"
pattern = re.compile(r"^(a+)+$")
pattern.match("a" * 40 + "!") # can run for a very long time
Another common form is a quadratic loop that looks harmless:
# Vulnerable: list membership is a linear scan, inside a loop
seen = []
for item in untrusted_items:
if item not in seen:
seen.append(item)
What an attacker gains
The record lists availability as the consequence. The typical effect is CPU exhaustion, though memory and other resources can also be consumed. One request can tie up a worker, so a modest stream of them can starve real users.
How to find it
The MITRE record lists no detection methods for this weakness, so these are practical checks:
- Review code that handles untrusted input for nested loops and nested regex quantifiers.
- Feed oversized and repetitive inputs in tests and watch the time curve. If doubling the input quadruples the time, you have quadratic behavior.
- Check your dependencies. Several of the examples above are library bugs, not application bugs. A free dependency scan runs in your browser, keeps your file on your machine and covers up to 100 dependencies.
How to fix it
Bound the work before you do it.
- Cap input size and length at the edge, before parsing.
- Use data structures with the right complexity, such as a set for membership checks.
- Use regex engines with linear time guarantees for untrusted input, or rewrite patterns to remove nested quantifiers.
- Set timeouts and per-request CPU limits so one slow input cannot hold a worker forever.
- Update libraries when a complexity fix ships, and use reachability analysis to learn whether your code actually calls the affected function.
# Fixed: set gives constant time membership
seen = set()
for item in untrusted_items:
seen.add(item)
# Fixed: reject oversized input first, and avoid nested quantifiers
if len(value) > 1000:
raise ValueError("too long")
re.compile(r"^a+$").match(value)
Quick check
Why is the attacker's input usually small?
Because the cost comes from the algorithm, not the size. A short crafted string can force exponential or quadratic work.
Is a size limit enough on its own?
It helps a lot, but pair it with the right algorithm and a timeout. A limit that is too generous can still be slow.
