English
Français
Light
Dark
System

Alert System

Stay informed at all times
Create an account Open a free account Login Manage your alerts

CWE-1333 Detail

CWE-1333

Inefficient Regular Expression Complexity
HIGH
Draft
2021-03-15 00:00 +00:00
2023-06-29 00:00 +00:00
CWE Mitre.org

Alerte pour un CWE

Stay informed of any changes for a specific CWE.
Alert management

Inefficient Regular Expression Complexity

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.

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

Reference Description
CVE-2020-5243server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
CVE-2021-21317npm package for user-agent parser prone to ReDoS due to overlapping capture groups
CVE-2019-16215Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages.
CVE-2019-6785Long string in a version control product allows DoS due to an inefficient regex.
CVE-2019-12041Javascript code allows ReDoS via a long string due to excessive backtracking.
CVE-2015-8315ReDoS when parsing time.
CVE-2015-8854ReDoS when parsing documents.
CVE-2017-16021ReDoS 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

Rationale : 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.
Comments : 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

More information
Click on the button to the left (OFF), to authorize the inscription of cookie improving the functionalities of the site. Click on the button to the left (Accept all), to unauthorize the inscription of cookie improving the functionalities of the site.