Backtracking Catastrófico

O backtracking catastrófico é um fenômeno em expressões regulares onde o motor leva um tempo excessivo para avaliar certos padrões, resultando em degradação significativa de desempenho — às vezes segundos, minutos, ou efetivamente para sempre. Isso acontece porque o motor tenta combinar partes da string de muitas formas diferentes antes de desistir, e o número de combinações exploradas cresce exponencialmente com o comprimento da entrada.

Esta página aborda o que desencadeia o problema, como reconhecer um padrão perigoso e técnicas concretas para reescrever uma regex de modo que permaneça rápida. Pressupõe que você está confortável com quantificadores e a diferença entre correspondência gulosa e preguiçosa.

Por que isso importa: Uma única regex lenta aplicada a entradas fornecidas pelo usuário é um vetor real de negação de serviço (frequentemente chamado de "ReDoS"). Um atacante precisa apenas enviar uma string curta elaborada para maximizar o backtracking e travar o event loop do Node.js.

O Que Causa o Backtracking Catastrófico?

O backtracking catastrófico ocorre tipicamente com quantificadores aninhados — um quantificador dentro de um grupo que também é quantificado, como (a+)+. O perigo surge quando duas partes do padrão podem corresponder aos mesmos caracteres, de modo que o motor tem muitas formas sobrepostas de dividir a entrada. Quando a correspondência finalmente falha, o motor deve tentar todas essas divisões antes de concluir que nada corresponde. Aqui está o exemplo clássico:

Se não demorar muito no seu computador, você pode adicionar mais um caractere a à str. Então por que está levando tanto tempo? Vamos analisar. O padrão /^(a+)+$/ é composto por:

• ^ que afirma a posição no início da string.
• (a+) que corresponde a um ou mais caracteres a.
• + que permite que o grupo anterior (a+) se repita uma ou mais vezes.
• $ que afirma a posição no final da string.

Agora, o processo de correspondência é:

1. Correspondência Inicial: O motor começa no início da string (^).
2. Correspondência do Primeiro Grupo: O motor corresponde ao primeiro a+, consumindo todos os caracteres a (aaa...).
3. Quantificador Externo: O + externo permite que o motor repita o grupo (a+).

Quando o motor alcança o ponto de exclamação (!), ele não consegue correspondê-lo com o padrão, causando falha na correspondência. Neste ponto, o backtracking começa:

1. Tentativa de Backtracking: O motor retrocede para dividir repetidamente os caracteres a correspondidos entre os quantificadores a+ interno e + externo. Ele reavalia cada divisão para ver se uma partição diferente pode corresponder ao padrão até o final da string.
2. Crescimento Exponencial: Esse processo de backtracking pode crescer exponencialmente à medida que o motor tenta todas as formas possíveis de particionar a string de caracteres a em diferentes grupos que poderiam corresponder a (a+)+.

Para uma string de n caracteres a, o a+ interno e o + externo podem dividir esses caracteres em grupos de aproximadamente 2^(n-1) formas diferentes. Quando o ! no final faz a correspondência falhar, o motor precisa tentar todas elas. É por isso que adicionar um único a extra à entrada aproximadamente dobra o tempo de execução — a marca característica da explosão exponencial. A correspondência abaixo é bem-sucedida rapidamente porque não há cauda de falha que force uma exploração completa:

A lição: o backtracking catastrófico só ocorre quando um padrão pode corresponder de muitas formas e a correspondência geral eventualmente falha. Entradas de falha elaboradas são exatamente o que um atacante envia.

Identificando Padrões Propensos ao Backtracking Catastrófico

Como uma lista de verificação mental rápida, um padrão está em risco quando possui esses três traços: uma repetição, dentro de outra repetição, sobre caracteres que se sobrepõem. Sinais de alerta comuns:

• Quantificadores aninhados, ex.: (a+)+, (\d*)*, (\w+)*.
• Grupos quantificados contendo uma alternância que se sobrepõe, ex.: (a|a)+ ou (\w|\d)+ (\w já inclui \d).
• Um .* ou .+ guloso entre duas coisas que também podem corresponder aos mesmos caracteres, ex.: <.+>.*<.+>.
• Padrões sem âncoras em entradas longas, que reexperimentam toda a correspondência em cada posição inicial.

Se as repetições de um grupo quantificado podem corresponder à mesma substring, você tem ambiguidade, e a ambiguidade é o que o backtracking explora.

Estratégias para Prevenir o Backtracking Catastrófico

O objetivo de cada correção abaixo é o mesmo: remover a ambiguidade que permite ao motor dividir a entrada de mais de uma forma. Mudar de guloso para preguiçoso (+?, *?) não ajuda aqui — ambos ainda exploram todas as divisões; o preguiçoso apenas as explora em uma ordem diferente. Você precisa mudar a estrutura do padrão, não sua gulodice.

1. Eliminar o Quantificador Aninhado

(a+)+ é quase sempre equivalente a um único quantificador. Se você só precisa de "um ou mais a", basta escrever a+. Há exatamente uma forma de corresponder isso, de modo que o motor não pode retroceder a uma explosão combinatória.

2. Emular um Grupo Atômico com Lookahead

JavaScript não possui grupos atômicos (?>...) nativos nem quantificadores possessivos (a++) como alguns outros dialetos de regex. Você pode reproduzir o mesmo comportamento de "corresponder isso uma vez e nunca devolver" com um lookahead mais uma referência retroativa: (?=(a+))\1. O lookahead corresponde a+ de forma gulosa, captura-o, e \1 consome exatamente esse texto — mas como o grupo capturado estava dentro de um lookahead, o motor não irá reparticioná-lo no backtracking.

3. Usar Classes de Caracteres Específicas e Não Sobrepostas

O backtracking explode quando partes adjacentes de um padrão podem corresponder aos mesmos caracteres. Faça com que cada parte corresponda a um conjunto distinto para que haja apenas uma forma de dividir a entrada. Por exemplo, prefira \d+\.\d+ a [\d.]+\.[\d.]+, onde ambos os grupos [\d.]+ competem pelo mesmo ponto.

4. Ancorar e Limitar o Padrão

Ancoragem com ^ e $ permite que o motor falhe rapidamente em vez de tentar a correspondência em cada posição da string. Colocar um limite superior explícito em um quantificador (a{1,20} em vez de a+) limita quanto trabalho qualquer repetição única pode gerar.

Exemplos Práticos e Soluções

Exemplo 1: Correspondência de Tags HTML Aninhadas

Um caso de uso comum para regex é corresponder tags HTML aninhadas, o que pode facilmente levar ao backtracking catastrófico se não for tratado corretamente. Nota: Expressões regulares são geralmente inadequadas para analisar estruturas HTML arbitrárias ou profundamente aninhadas; use um parser HTML adequado para documentos complexos.

Padrão Problemático

Padrão Melhorado

Substitua o .* guloso (que pode engolir o documento inteiro e depois rastejar de volta) por uma classe que não pode cruzar o colchete de fechamento. [^<]* corresponde a tudo até o próximo <, de modo que não há sobreposição pela qual retroceder.

Exemplo 2: Validando uma Lista de Identificadores

Padrão Problemático

([a-zA-Z0-9_]+)+ é a mesma armadilha que (a+)+: o + interno e o + externo ambos se repetem sobre os mesmos caracteres, de modo que uma entrada longa sem correspondência desencadeia o backtracking exponencial.

Uma Alternância Segura

Nem todo grupo quantificado é perigoso. (?:ab|cd)+e está correto: ab e cd são disjuntos, de modo que o motor nunca precisa reconsiderar como dividiu a entrada. Use um grupo não capturante (?:...) quando você não precisa do texto capturado — é ligeiramente mais rápido e mais claro, mesmo que não altere o comportamento de backtracking aqui.

Conclusão

O backtracking catastrófico pode travar uma aplicação JavaScript — e como é desencadeado por entradas, é um risco genuíno de segurança, não apenas de desempenho. A correção é quase sempre remover a ambiguidade: achatar quantificadores aninhados, fazer com que partes adjacentes do padrão correspondam a conjuntos de caracteres disjuntos, ancorar com ^/$, limitar suas repetições ou emular um grupo atômico com (?=(...))\1. Mudar para quantificadores preguiçosos não ajuda.

Quando você escreve uma regex que será executada contra entradas não confiáveis, teste-a com strings longas de falha (ex.: cem as seguidos de !) e observe o tempo. Se adicionar mais um caractere aumenta visivelmente o tempo, o padrão é exponencial e precisa de reestruturação.

Para se aprofundar, revise os capítulos relacionados sobre quantificadores, quantificadores gulosos e preguiçosos, grupos de captura e classes de caracteres.

Prática