2232
Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Effectiveness = High
This is one of the few effective solutions when using user-provided regular expressions.
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.
Effectiveness = Moderate
Phase: Implementation
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid
using backtracking in the expression.
Effectiveness = High
Phase: Implementation
Limit the length of the input that the regular expression will process.
Effectiveness = Moderate
Demonstrative Examples
Example 1:
This example attempts to check if an input string is a "sentence" [REF-1164].
Example Language: JavaScript (Bad)
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:
Example Language: JavaScript (Good)
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].
Example Language: Perl (Bad)
my $test_string = "Bad characters: \$\@\#";
my $bdrslt = $test_string;
$bdrslt =~ /^(\w+\s?)*$/i;
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.
CWE Version 4.14
CWE-1333: Inefficient Regular Expression Complexity
CWE-1333: Inefficient Regular Expression Complexity