993
Relevant to the view "Research Concepts" (CWE-1000)
Nature Type ID Name Page
ChildOf 405 Asymmetric Resource Consumption (Amplification) 986
ParentOf 1333 Inefficient Regular Expression Complexity 2230
Relevant to the view "Weaknesses for Simplified Mapping of Published
Vulnerabilities" (CWE-1003)
Nature Type ID Name Page
ParentOf 1333 Inefficient Regular Expression Complexity 2230
Applicable Platforms
Language : Not Language-Specific (Prevalence = Undetermined)
Alternate Terms
Quadratic Complexity : Used when the algorithmic complexity is related to the square of the
number of inputs (N^2)
Likelihood Of Exploit
Low
Common Consequences
Scope Impact Likelihood
Availability DoS: Resource Consumption (CPU)
DoS: Resource Consumption (Memory)
DoS: Resource Consumption (Other)
The typical consequence is CPU consumption, but
memory consumption and consumption of other resources
can also occur.
Demonstrative Examples
Example 1:
This example attempts to check if an input string is a "sentence" [REF-1164].
Example Language: JavaScript (Bad)
var test_string = "Bad characters: $@#";
var bad_pattern = /^(\w+\s?)*$/i;
var result = test_string.search(bad_pattern);
The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be
triggered to cause a Denial of Service by processing particular phrases.
To fix the backtracking problem, backtracking is removed with the ?= portion of the expression
which changes it to a lookahead and the \2 which prevents the backtracking. The modified example
is:
Example Language: JavaScript (Good)
var test_string = "Bad characters: $@#";
var good_pattern = /^((?=(\w+))\2\s?)*$/i;
var result = test_string.search(good_pattern);
Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within
the RegEx.
Observed Examples
CWE Version 4.14
CWE-407: Inefficient Algorithmic Complexity
CWE-407: Inefficient Algorithmic Complexity