CWE-1333 Detail

CWE-1333

Inefficient Regular Expression Complexity
High
Draft
2021-03-15
00h00 +00:00
2023-06-29
00h00 +00:00
CWE Mitre.org
Notifications for a CWE
Stay informed of any changes for a specific CWE.
Notifications manage

Name: Inefficient Regular Expression Complexity

The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.

CWE 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.

General Informations

Modes Of Introduction

Implementation : A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of excessive backtracking.

Applicable Platforms

Language

Class: Not Language-Specific (Undetermined)

Common Consequences

Scope Impact Likelihood
AvailabilityDoS: Resource Consumption (CPU)High

Observed Examples

References 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.

Potential Mitigations

Phases : Architecture and Design
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Phases : System Configuration
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.
Phases : Implementation
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Phases : Implementation
Limit the length of the input that the regular expression will process.

Vulnerability Mapping Notes

Justification : 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.
Comment : 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.

Related Attack Patterns

CAPEC-ID Attack Pattern Name
CAPEC-492 Regular Expression Exponential Blowup
An adversary may execute an attack on a program that uses a poor Regular Expression(Regex) implementation by choosing input that results in an extreme situation for the Regex. A typical extreme situation operates at exponential time compared to the input size. This is due to most implementations using a Nondeterministic Finite Automaton(NFA) state machine to be built by the Regex algorithm since NFA allows backtracking and thus more complex regular expressions.

References

REF-1180

Regular Expression Denial of Service
Scott A. Crosby.
https://web.archive.org/web/20031120114522/http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt

REF-1162

Runaway Regular Expressions: Catastrophic Backtracking
Jan Goyvaerts.
https://www.regular-expressions.info/catastrophic.html

REF-1163

Regular expression Denial of Service - ReDoS
Adar Weidman.
https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

REF-1164

Catastrophic backtracking
Ilya Kantor.
https://javascript.info/regexp-catastrophic-backtracking

REF-1165

Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers
Cristian-Alexandru Staicu, Michael Pradel.
https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-staicu.pdf

REF-1166

The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale
James C. Davis, Christy A. Coghlan, Francisco Servant, Dongyoon Lee.
https://fservant.github.io/papers/Davis_Coghlan_Servant_Lee_ESECFSE18.pdf

REF-1167

The Regular Expression Denial of Service (ReDoS) cheat-sheet
James Davis.
https://levelup.gitconnected.com/the-regular-expression-denial-of-service-redos-cheat-sheet-a78d0ed7d865

Submission

Name Organization Date Date release Version
Anonymous External Contributor 2021-01-17 +00:00 2021-03-15 +00:00 4.4

Modifications

Name Organization Date Comment
CWE Content Team MITRE 2021-07-20 +00:00 updated References
CWE Content Team MITRE 2021-10-28 +00:00 updated Description
CWE Content Team MITRE 2022-04-28 +00:00 updated Observed_Examples, Potential_Mitigations
CWE Content Team MITRE 2022-10-13 +00:00 updated Observed_Examples, Relationships
CWE Content Team MITRE 2023-01-31 +00:00 updated Demonstrative_Examples, Observed_Examples
CWE Content Team MITRE 2023-04-27 +00:00 updated References, Relationships
CWE Content Team MITRE 2023-06-29 +00:00 updated Mapping_Notes