2231
The product uses a regular expression with an inefficient, possibly exponential worst-case
computational complexity that consumes excessive CPU cycles.
Extended Description
Some regular expression engines have a feature called "backtracking". If the token cannot match,
the engine "backtracks" to a position that may result in a different token that can match.
Backtracking becomes a weakness if all of these conditions are met:
• The number of possible backtracking attempts are exponential relative to the length of the
input.
• The input can fail to match the regular expression.
• The input can be long enough.
Attackers can create crafted inputs that intentionally cause the regular expression to use excessive
backtracking in a way that causes the CPU consumption to spike.
Relationships
The table(s) below shows the weaknesses and high level categories that are related to this
weakness. These relationships are defined as ChildOf, ParentOf, MemberOr and give insight to
similar items that may exist at higher and lower levels of abstraction. In addition, relationships such
as PeerOf and CanAlsoBe are defined to show similar weaknesses that may want to be explored.
Relevant to the view "Research Concepts" (CWE-1000)
Nature Type ID Name Page
ChildOf 407 Inefficient Algorithmic Complexity 992
Relevant to the view "Weaknesses for Simplified Mapping of Published
Vulnerabilities" (CWE-1003)
Nature Type ID Name Page
ChildOf 407 Inefficient Algorithmic Complexity 992
Relevant to the view "Software Development" (CWE-699)
Nature Type ID Name Page
MemberOf 1226 Complexity Issues 2481
Applicable Platforms
Language : Not Language-Specific (Prevalence = Undetermined)
Alternate Terms
ReDoS : ReDoS is an abbreviation of "Regular expression Denial of Service".
Regular Expression Denial of Service : While this term is attack-focused, this is commonly used
to describe the weakness.
Catastrophic backtracking : This term is used to describe the behavior of the regular expression
as a negative technical impact.
Likelihood Of Exploit
High
Common Consequences
Scope Impact Likelihood
Availability DoS: Resource Consumption (CPU) High
Potential Mitigations
Phase: Architecture and Design
CWE Version 4.14
CWE-1333: Inefficient Regular Expression Complexity
CWE-1333: Inefficient Regular Expression Complexity