Regular Expression With Catastrophic Backtracking
ID |
javascript.regex_catastrophic_backtracking |
Severity |
high |
Remediation Complexity |
medium |
Remediation Risk |
low |
Remediation Effort |
medium |
Resource |
Efficiency |
Language |
JavaScript |
Tags |
CWE:1333, efficiency, regex, reliability |
Description
Reports a regular expression whose structure lets the matcher split the same input in an explosive number of ways. A subject that almost matches then takes seconds or minutes where a match takes microseconds.
Two shapes are reported, both decided from the pattern’s own token stream:
-
nested repetition — a group whose whole body is one repeated atom, itself repeated with no upper bound:
(a+)+,(\d*)*,([a-z]?)+. Every character can be attributed to the inner or to the outer repetition, so the number of splits grows exponentially with the length of the subject. -
adjacent repetition over overlapping sets — two unbounded repetitions side by side whose character sets provably contain one another:
\d+\w+,\s*\s*,[a-z]+[a-z0-9]*. Every boundary between them is a candidate split, which is quadratic rather than exponential but still enough to stall a request.
Both are judged on the pattern alone, wherever the subject comes from, so a pattern applied to input that is trusted today is reported too.
Rationale
// Bad
const IDENTIFIER = /^(\w+)+$/;
IDENTIFIER.test("aaaaaaaaaaaaaaaaaaaaaaaaaaa"); // matches at once
IDENTIFIER.test("aaaaaaaaaaaaaaaaaaaaaaaaaaa!"); // never returns in practice-
The inner
\w+and the outer+compete for the same characters. With the trailing!no split can ever match, and the matcher tries all of them — roughly two to the power of the subject’s length. -
The cost is paid on the failing input, which is the one an attacker controls and the one a validation regex sees most.
-
Nothing about the pattern looks slow. It passes every test written with matching input, and the first evidence is a request that stops responding.
Remediation
Repeat a unit that cannot be split more than one way, or bound the outer repetition.
// Good
const IDENTIFIER = /^\w+$/; // the outer repetition was redundant
const CSV_ROW = /^(\w+,)+$/; // each repetition must end with a comma
const SHORT_RUN = /^(\w+){1,8}$/; // bounded, so the search cannot explodeFor two adjacent repetitions, merge them or make the character sets disjoint:
// Good
const CODE = /^\w+$/; // was /^\d+\w+$/
const PLATE = /^\d+[a-z]+$/; // the two sets cannot claim the same character