COMMON WEAKNESS ENUMERATIONDraft

CWE-1333

Inefficient Regular Expression Complexity

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

Soyutlama

Base

Yapı

Simple

Sömürü İhtimali

High

Problemi anla

Problem nedir?

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

Terminoloji

Alternatif adlar ve kullanım biçimleri

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.

Kök neden

Problem nasıl ve ne zaman oluşur?

Yaşam döngüsü evresi

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.

Yaşam döngüsü evresi

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.
Some regular expression engines have a feature called "backtracking". If the token cannot match, the engine "backtracks" to a position that may result in a different token that can match.

Risk

Başarılı sömürü neye yol açar?

DoS: Resource Consumption (CPU)

Etkilenen güvenlik alanları: Availability

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.

Savunma

Nasıl önlenir ve çözülür?

Architecture and Design

Mimari ve tasarım yaklaşımı

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

Etkinlik: High

This is one of the few effective solutions when using user-provided regular expressions.

System Configuration

Güvenli yapılandırma yaklaşımı

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

Etkinlik: Moderate

Implementation

Uygulama aşaması savunması

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

Etkinlik: High

Implementation

Uygulama aşaması savunması

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

Etkinlik: Moderate

Doğrulama

Nasıl tespit edilir?

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

MITRE görseli

Zafiyet ilişkisi ve akışı

CWE-1333 MITRE diagramı