Tag Archives: Inefficient Regular Expression Complexity

CWE-1333 – Inefficient Regular Expression Complexity

Read Time:1 Minute, 29 Second

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:

Modes of Introduction:

– Implementation

 

Likelihood of Exploit: High

 

Related Weaknesses

CWE-407
CWE-185

 

Consequences

Availability: DoS: Resource Consumption (CPU)

 

Potential Mitigations

Phase: Architecture and Design

Effectiveness: High

Description: 

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

This is one of the few effective solutions when using user-provided regular expressions.

Phase: System Configuration

Effectiveness: Moderate

Description: 

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

Effectiveness: High

Description: 

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

Phase: Implementation

Effectiveness: Moderate

Description: 

Limit the length of the input that the regular expression will process.

CVE References

  • CVE-2020-5243
    • server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
  • CVE-2019-16215
    • Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages.
  • CVE-2019-6785
    • Long string in a version control product allows DoS due to an inefficient regex.
  • CVE-2019-12041
    • Javascript code allows ReDoS via a long string due to excessive backtracking.