flawopen.com/O que é ReDoS/Explained

O que é ReDoS (backtracking catastrófico)?

CWE-1333: Inefficient Regular Expression ComplexityPágina de referência

Resposta curta

Uma engine regex com backtracking pode tentar dividir a mesma entrada de outras formas após uma falha. Em alguns padrões ambíguos, as tentativas crescem exponencialmente com a entrada. O atraso depende da regex, da engine, do tamanho da entrada, da concorrência e dos limites de recursos; solicitações caras repetidas podem esgotar a capacidade do serviço.

PADRÕES VULNERÁVEIS

# Nested quantifier
^(a+)+$

# Overlapping alternatives, quantified
^(a|aa)+$

# A long matching prefix plus a final mismatch can
# force extensive retries in vulnerable engines.
# Do not benchmark this with attacker-sized input.

MAIS SEGURO

# Bound input before matching, then use a simple
# full-string identifier rule with no nested ambiguity.
import re

IDENTIFIER = re.compile(r"[a-z0-9]{1,64}\Z")

def valid_identifier(value: str) -> bool:
    if not isinstance(value, str) or len(value) > 64:
        return False
    return IDENTIFIER.fullmatch(value) is not None

# A bound reduces worst-case work; still set request
# size, concurrency, and execution-time limits.

Por que o backtracking explode

Um padrão como ^(a+)+$ é ambíguo em uma engine com backtracking: aaaa pode ser dividido de várias formas entre quantificadores aninhados. Um caractere final incompatível pode fazer a engine explorar alternativas antes de rejeitar a string inteira.

Para padrões com essa ambiguidade, os caminhos explorados podem crescer exponencialmente com o tamanho do prefixo que corresponde antes da falha. Isso depende da combinação específica entre padrão e engine, não de toda regex ou falha. Entradas menores também importam com solicitações concorrentes; limite tamanho, concorrência e tempo.

Onde entradas não confiáveis chegam a uma regex

Validação é um caso óbvio, mas há riscos menos visíveis: processamento de User-Agent e outros cabeçalhos, logs, Markdown e realce de sintaxe, roteamento de URL, filtros de conteúdo e regras WAF, além de bibliotecas que aplicam regex a campos recebidos. Pacotes populares já publicaram avisos de ReDoS; dependências importam tanto quanto os padrões próprios.

Perguntas frequentes

Which languages are affected?

O risco depende da engine e do padrão, não apenas da linguagem. Engines comuns com backtracking podem explorar alternativas em excesso para certos padrões. A documentação de regexp do Go garante tempo linear no tamanho da entrada. A crate regex do Rust documenta O(m·n) por busca (m é o tamanho do padrão e n o da entrada), linear em n para um padrão fixo; iteradores de busca repetida têm outros limites. Essas engines omitem recursos como backreferences, que impedem as mesmas garantias.

Is a length limit enough on its own?

Um limite restringe o trabalho de cada correspondência, mas o valor seguro depende do padrão, da engine, da taxa de solicitações e do orçamento do serviço. Corrija padrões ambíguos e aplique limites antes de analisar ou comparar a entrada.

How do I find vulnerable patterns?

Use um analisador estático com detecção de ReDoS e avalie os resultados para a engine real. Procure grupos repetidos que contenham repetição ou alternativas com prefixos sobrepostos; depois teste entradas limitadas com timeout estrito em ambiente isolado.

Can I add a timeout instead?

O suporte a timeout varia conforme runtime e API. No .NET, defina um timeout explícito para correspondências com entradas não confiáveis. Em outros ambientes, consulte os controles documentados da engine específica; escolha uma engine mais segura ou redesenhe o padrão se não houver timeout aplicável. Timeout complementa limites de entrada e concorrência; não torna eficiente um padrão ambíguo.

Referências

Veja também ReDoS no Node.js: regex e CVE-2026-83606