Détail du CWE-1333

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:

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

Modes d'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.

Plateformes applicables

Langue

Class: Not Language-Specific (Undetermined)

Conséquences courantes

Exemples observés

Mesures d’atténuation potentielles

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.

Méthodes de détection

Automated Static Analysis

Automated static analysis, commonly referred to as Static Application Security Testing (SAST), can find some instances of this weakness by analyzing source code (or binary/compiled code) without having to execute it. Typically, this is done by building a model of data flow and control flow, then searching for potentially-vulnerable patterns that connect "sources" (origins of input) with "sinks" (destinations where the data interacts with external components, a lower layer such as the OS, etc.)
Efficacité : High

Notes de cartographie des vulnérabilités

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.
Commentaire : 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.

Modèles d'attaque associés

Références

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

Soumission

Modifications