Inefficient Regular Expression Complexity

Opis

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

Inne nazwy

ReDoS

ReDoS is an abbreviation of "Regular expression Denial of Service".

Regular Expression Denial of Service

While this term is attack-focused, this is commonly used to describe the weakness.

Catastrophic backtracking

This term is used to describe the behavior of the regular expression as a negative technical impact.

Skutki

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

Zapobieganie

• Architecture and Design

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

  Skuteczność: High

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

  Skuteczność: Moderate

• Implementation

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

  Skuteczność: High

• Implementation

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

  Skuteczność: Moderate

Przykłady podatności

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

Słabość nadrzędna

• CWE-407 Inefficient Algorithmic Complexity

Kiedy powstaje

• Implementation — A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of excessive backtracking.
• Implementation — Backtracking becomes a weakness if all of these conditions are met: - The number of possible backtracking attempts is exponential relative to the length of the input. - The input can fail to match the regular expression. - The input can be long enough.

Dotyczy

Not Language-Specific

Źródła

1. Regular Expression Denial of Service — Scott A. Crosby, 2003
2. Runaway Regular Expressions: Catastrophic Backtracking — Jan Goyvaerts, 2019
3. Regular expression Denial of Service - ReDoS — Adar Weidman
4. Catastrophic backtracking — Ilya Kantor, 2020
5. Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers — Cristian-Alexandru Staicu, Michael Pradel, USENIX Security Symposium, 2018
6. The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem Scale — James C. Davis, Christy A. Coghlan, Francisco Servant, Dongyoon Lee, 2018
7. The Regular Expression Denial of Service (ReDoS) cheat-sheet — James Davis, 2020