Description
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:
Modes of Introduction:
– Implementation
Likelihood of Exploit: High
Related Weaknesses
Consequences
Availability: DoS: Resource Consumption (CPU)
Potential Mitigations
Phase: Architecture and Design
Effectiveness: High
Description:
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.
Phase: System Configuration
Effectiveness: Moderate
Description:
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.
Phase: Implementation
Effectiveness: High
Description:
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Phase: Implementation
Effectiveness: Moderate
Description:
Limit the length of the input that the regular expression will process.
CVE References
- CVE-2020-5243
- server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
- 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.