CWE-1333: Inefficient Regular Expression Complexity

Some regular-expression engines use backtracking to try alternative parses when a token does not match. If an expression permits an exponential number of backtracking attempts relative to input length, a long input designed to fail can force excessive computation. The weakness commonly arises during implementation when easy-to-write patterns with unbounded matching characters are used without considering backtracking cost. This behavior is commonly called ReDoS or catastrophic backtracking.

The weakness commonly appears in expressions that create many possible backtracking paths, especially through nested quantifiers or overlapping capture groups. In engines that support backtracking, a failed token can cause the engine to return to an earlier position and try another matching path. The risk becomes significant when the number of attempts grows exponentially with input length, the input can fail to match, and the input can be sufficiently long. The record identifies this as not language-specific and also lists Go as an applicable platform.

The primary consequence is an availability impact through CPU resource consumption. An attacker can provide crafted input that triggers excessive backtracking, causing CPU usage to spike and potentially delaying or preventing processing of other requests or messages. The record characterizes this as denial of service.

• Architecture and design: Prefer regular-expression implementations that do not support backtracking, for example by removing nested quantifiers. This is one of the few highly effective options when regular expressions are supplied by users.
• System configuration: Configure backtracking limits for the regular-expression implementation, such as PHP's pcre.backtrack_limit, and consider limiting the process execution time.
• Implementation: Do not apply regular expressions to untrusted input where this can be avoided. When regular expressions are necessary, avoid backtracking in the expression.
• Input handling: Limit the length of input processed by the regular expression.

Automated static analysis, commonly called Static Application Security Testing (SAST), can identify some instances by analyzing source code or binary/compiled code without execution. It typically builds data-flow and control-flow models, then searches for potentially vulnerable patterns connecting input sources with regular-expression processing or external components. This approach may not identify every expression with excessive backtracking, so assessment should also consider the expression structure and input-length limits.

Representative examples in the record include:

• CVE-2020-5243: a server could be subjected to ReDoS through crafted User-Agent strings because overlapping capture groups caused excessive backtracking.
• CVE-2021-21317: an npm user-agent parser package was susceptible to ReDoS due to overlapping capture groups.
• CVE-2019-16215: a Markdown parser used an inefficient regular expression, allowing CPU consumption and delays that prevented other messages from being processed.
• CVE-2019-6785: a long string in a version-control product could cause denial of service through an inefficient regular expression.
• CVE-2019-12041: JavaScript code permitted ReDoS through a long string because of excessive backtracking.
• CVE-2015-8315: ReDoS occurred while parsing time.
• CVE-2015-8854: ReDoS occurred while parsing documents.
• CVE-2017-16021: ReDoS occurred while validating a URL.

These are curated representative examples from the record, not an exhaustive list of vulnerabilities.