CWE-1333

Base Abstraction Level
Pillar — Highest-level weakness category
Class — Abstract, language-independent
Base — Specific enough to detect
Variant — Tied to specific technology
Compound — Requires multiple weaknesses Draft MITRE CWE Status
Stable — Fully reviewed and complete
Draft — Under development, may change
Incomplete — Partially defined by MITRE
Deprecated — No longer recommended
Obsolete — Replaced by another CWE Exploit: High
Inefficient Regular Expression Complexity

Description

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.

Consequences

Availability — DoS: Resource Consumption (CPU)

Mitigations

Phase: Architecture and Design

Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.

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

Phase: Implementation

Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.

Phase: 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.)