CWE-1333: 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.

Submission Date :

Jan. 17, 2021, midnight

Modification Date :

2023-06-29 00:00:00+00:00

Organization :

MITRE

Extended Description

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.

Example Vulnerable Codes

Example - 1

This example attempts to check if an input string is a "sentence" [REF-1164].


var test_string = "Bad characters: $@#";var bad_pattern  = /^(\w+\s?)*$/i;var result = test_string.search(bad_pattern);

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:


var test_string = "Bad characters: $@#";var good_pattern  = /^((?=(\w+))\2\s?)*$/i;var result = test_string.search(good_pattern);

Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.

Example - 2

This example attempts to check if an input string is a "sentence" and is modified for Perl [REF-1164].


my $test_string = "Bad characters: \$\@\#";my $bdrslt = $test_string;$bdrslt =~ /^(\w+\s?)*$/i;


my $test_string = "Bad characters: \$\@\#";my $gdrslt = $test_string;$gdrslt =~ /^((?=(\w+))\2\s?)*$/i;

Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx.

Related Weaknesses

This table shows the weaknesses and high level categories that are related to this weakness. These relationships are defined to give an overview of the different insight to similar items that may exist at higher and lower levels of abstraction.

CWE-407: Inefficient Algorithmic Complexity

Go to

Visit http://cwe.mitre.org/ for more details.