2233
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: Perl (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.
Observed Examples
Reference Description
CVE-2020-5243 server allows ReDOS with crafted User-Agent strings, due to overlapping
capture groups that cause excessive backtracking.
https://www.cve.org/CVERecord?id=CVE-2020-5243
CVE-2021-21317 npm package for user-agent parser prone to ReDoS due to overlapping
capture groups
https://www.cve.org/CVERecord?id=CVE-2021-21317
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.
https://www.cve.org/CVERecord?id=CVE-2019-16215
CVE-2019-6785 Long string in a version control product allows DoS due to an inefficient regex.
https://www.cve.org/CVERecord?id=CVE-2019-6785
CVE-2019-12041 Javascript code allows ReDoS via a long string due to excessive backtracking.
https://www.cve.org/CVERecord?id=CVE-2019-12041
CVE-2015-8315 ReDoS when parsing time.
https://www.cve.org/CVERecord?id=CVE-2015-8315
CVE-2015-8854 ReDoS when parsing documents.
https://www.cve.org/CVERecord?id=CVE-2015-8854
CVE-2017-16021 ReDoS when validating URL.
https://www.cve.org/CVERecord?id=CVE-2017-16021
MemberOf Relationships
This MemberOf relationships table shows additional CWE Catgeories and Views that reference this
weakness as a member. This information is often useful in understanding where a weakness fits
within the context of external information sources.
Nature Type ID Name Page
MemberOf 1416 Comprehensive Categorization: Resource Lifecycle
Management
1400 2545
Related Attack Patterns
CAPEC-ID Attack Pattern Name
492 Regular Expression Exponential Blowup
References
[REF-1180]Scott A. Crosby. "Regular Expression Denial of Service". 2003 August. < https://
web.archive.org/web/20031120114522/http://www.cs.rice.edu/~scrosby/hash/slides/USENIXRegexpWIP.
2.ppt >.
[REF-1162]Jan Goyvaerts. "Runaway Regular Expressions: Catastrophic Backtracking". 2019
December 2. < https://www.regular-expressions.info/catastrophic.html >.
CWE Version 4.14
CWE-1334: Unauthorized Error Injection Can Degrade Hardware Redundancy
CWE-1334: Unauthorized Error Injection Can Degrade Hardware Redundancy