CWE-1333

Inefficient Regular Expression Complexity
AI Translation Available

The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.

Status
draft
Abstraction
base
Likelihood
high

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.

Common Consequences

availability
Impacts
dos: resource consumption (cpu)

Detection Methods

automated static analysis

Potential Mitigations

Phases:
architecture and design system configuration implementation
Descriptions:
• 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.
• Limit the length of the input that the regular expression will process.
• Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
• Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.