CWE-1333: Inefficient Regular Expression Complexity

Description

The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.

Potential Impact

Availability

DoS: Resource Consumption (CPU)

Demonstrative Examples

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

Bad

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

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.

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

Bad

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

Good

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.

Mitigations & Prevention

Architecture and Design High

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

System Configuration Moderate

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.

Implementation High

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

Implementation Moderate

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

Detection Methods

Automated Static Analysis High — 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 sea

Real-World CVE Examples

CVE ID	Description
CVE-2020-5243	server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.
CVE-2021-21317	npm package for user-agent parser prone to ReDoS due to overlapping capture groups
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.
CVE-2015-8315	ReDoS when parsing time.
CVE-2015-8854	ReDoS when parsing documents.
CVE-2017-16021	ReDoS when validating URL.

Frequently Asked Questions

What is CWE-1333?

CWE-1333 (Inefficient Regular Expression Complexity) is a software weakness identified by MITRE's Common Weakness Enumeration. It is classified as a Base-level weakness. The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.

How can CWE-1333 be exploited?

Attackers can exploit CWE-1333 (Inefficient Regular Expression Complexity) to dos: resource consumption (cpu). This weakness is typically introduced during the Implementation, Implementation phase of software development.

How do I prevent CWE-1333?

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

What is the severity of CWE-1333?

CWE-1333 is classified as a Base-level weakness (Medium abstraction). It has been observed in 8 real-world CVEs.