CWE-1333 Inefficient Regular Expression Complexity

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

• Availability: DoS: Resource Consumption (CPU) — 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.

• [Architecture and Design] Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers. • [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. • [Implementation] Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression. • [Implementation] Limit the length of the input that the regular expression will process.

• Automated Static Analysis: 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 searching for potentially-vulnerable patterns that connect "sources" (origins of input) with "sinks" (destinations where the data interacts with external components, a lower layer such as the OS, etc.)

• 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.