CWE-1333: Inefficient Regular Expression Complexity | Glexia
CWE-1333 (Inefficient Regular Expression Complexity) weakness overview with consequences, detection methods, mitigations, related CVEs and MITRE ATT&CK context.
Glexia's Take · Automated analysis
CWE-1333: ReDoS
Inefficient Regular Expression Complexity represents a recurring weakness pattern that can create exploitable paths when design, validation, or implementation controls are missing.
Executive Impact
- Availability: DoS: Resource Consumption (CPU): 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.
Developer Pattern
CWE-1333 is the kind of defect developers can usually prevent with explicit validation, safer framework defaults, and tests that exercise hostile input or unsafe state transitions.
Automation confidence
high confidence from CWE-1333, 4.20.
Generated from the cited source records. This long-tail analysis has not been individually reviewed by a named human.
Official CWE Definition
CWE-1333: Inefficient Regular Expression Complexity
The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.
Developer And Remediation Guidance
How teams prevent and detect this weakness
Causes
- This example attempts to check if an input string is a "sentence" [REF-1164]. The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases. To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \2 which prevents the backtracking. The modified example is: Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.
- This example attempts to check if an input string is a "sentence" and is modified for Perl [REF-1164]. The regular expression has a vulnerable backtracking clause inside (\w+\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases. To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \2 which prevents the backtracking. The modified example is: Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.
Remediation
- Architecture and Design: Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
- 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.
- Implementation: Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
- Implementation: Limit the length of the input that the regular expression will process.
Detection
- 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.)
Mappings
Related CVEs, CWEs, and ATT&CK context
ATT&CK Relevance
ATT&CK relevance is shown only when reviewed or responsibly inferred.