CWE-1333
Inefficient Regular Expression Complexity
HIGH
Draft
2021-03-15 00:00 +00:00
2023-06-29 00:00 +00:00
Alerte pour un CWE
Restez informé de toutes modifications pour un CWE spécifique.
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:
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 |
|---|---|---|
| Availability | DoS: Resource Consumption (CPU) | High |
Observed Examples
| Reference | Description |
|---|---|
| server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking. | |
| npm package for user-agent parser prone to ReDoS due to overlapping capture groups | |
| Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages. | |
| Long string in a version control product allows DoS due to an inefficient regex. | |
| Javascript code allows ReDoS via a long string due to excessive backtracking. | |
| ReDoS when parsing time. | |
| ReDoS when parsing documents. | |
| ReDoS when validating URL. |
Potential Mitigations
Phases : Architecture and DesignUse 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 ServiceScott 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 BacktrackingJan Goyvaerts.
https://www.regular-expressions.info/catastrophic.html
REF-1163
Regular expression Denial of Service - ReDoSAdar Weidman.
https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
REF-1164
Catastrophic backtrackingIlya Kantor.
https://javascript.info/regexp-catastrophic-backtracking
REF-1165
Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web ServersCristian-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 ScaleJames 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-sheetJames 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 | 4.4 |
Modifications
| Name | Organization | Date | Comment |
|---|---|---|---|
| CWE Content Team | MITRE | updated References | |
| CWE Content Team | MITRE | updated Description | |
| CWE Content Team | MITRE | updated Observed_Examples, Potential_Mitigations | |
| CWE Content Team | MITRE | updated Observed_Examples, Relationships | |
| CWE Content Team | MITRE | updated Demonstrative_Examples, Observed_Examples | |
| CWE Content Team | MITRE | updated References, Relationships | |
| CWE Content Team | MITRE | updated Mapping_Notes |
2024©
tesweb SA
