The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
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:
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.
ReDoS is an abbreviation of "Regular expression Denial of Service".
While this term is attack-focused, this is commonly used to describe the weakness.
This term is used to describe the behavior of the regular expression as a negative technical impact.
| Nature | Mapping | Type | ID | Name |
|---|---|---|---|---|
| ChildOf | Allowed-with-Review | C | 407 | Inefficient Algorithmic Complexity |
| Nature | Mapping | Type | ID | Name |
|---|---|---|---|---|
| MemberOf | Prohibited | C | 1226 | Complexity Issues |
| MemberOf | Prohibited | C | 1416 | Comprehensive Categorization: Resource Lifecycle Management |
| Nature | Mapping | Type | ID | Name |
|---|---|---|---|---|
| MemberOf | Prohibited | BS | BOSS-274 | High likelihood of exploit |
| MemberOf | Prohibited | BS | BOSS-294 | Not Language-Specific Weaknesses |
| MemberOf | Prohibited | BS | BOSS-314 | DoS: Resource Consumption (CPU) (impact) |
| Nature | Mapping | Type | ID | Name |
|---|---|---|---|---|
| MemberOf | Prohibited | C | 1226 | Complexity Issues |
| Scope | Likelihood | Impact | Note |
|---|---|---|---|
| Availability | High | DoS: Resource Consumption (CPU) | N/A |
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
This is one of the few effective solutions when using user-provided regular expressions.
Set backtracking limits in the configuration of the regular expression implementation, such as PHP's pcre.backtrack_limit. Also consider limits on execution time for the process.
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Limit the length of the input that the regular expression will process.
A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of excessive backtracking.
This example attempts to check if an input string is a "sentence" [REF-1164].
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:
Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.
This example attempts to check if an input string is a "sentence" and is modified for Perl [REF-1164].
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:
Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.
| Reference | Description |
|---|---|
| CVE-2020-5243 | server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking. |
| CVE-2021-21317 | npm package for user-agent parser prone to ReDoS due to overlapping capture groups |
| CVE-2019-16215 | Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages. |
| CVE-2019-6785 | Long string in a version control product allows DoS due to an inefficient regex. |
| CVE-2019-12041 | Javascript code allows ReDoS via a long string due to excessive backtracking. |
| CVE-2015-8315 | ReDoS when parsing time. |
| CVE-2015-8854 | ReDoS when parsing documents. |
| CVE-2017-16021 | ReDoS when validating URL. |
| Ordinality | Description |
|---|
This CWE entry is at the Base level of abstraction, which is a preferred level of abstraction for mapping to the root causes of vulnerabilities.
Carefully read both the name and description to ensure that this mapping is an appropriate fit. Do not try to 'force' a mapping to a lower-level Base/Variant simply to comply with this preferred level of abstraction.
| Taxonomy Name | Entry ID | Fit | Entry Name |
|---|