A regex que trava o navegador — backtracking catastrófico explicado

Um padrão que funciona até parar de funcionar

Você escreve uma expressão regular para validar algo parecido com um nome de host, testa com alguns exemplos e coloca em produção:

const name = /^([a-z0-9]+\.?)+$/;

name.test("api.example.com"); // true, na hora
name.test("not valid!");      // false, na hora

Semanas depois alguém cola um valor comprido com um caractere estranho no fim, e a aba para de responder. No servidor, o mesmo padrão consegue prender um núcleo da CPU e impedir um processo Node.js de atender qualquer outra requisição. Não há nada de errado com a entrada. O problema é o padrão, e ele tem nome: backtracking catastrófico.

Este guia explica por que isso acontece, como reconhecer os formatos perigosos e como corrigir, com exemplos para colar no testador de regex.

Como funciona um motor com backtracking

Os motores de expressão regular do JavaScript, do Python, do Java, do PHP e da maioria das linguagens usam backtracking. Quando uma parte do padrão pode casar de mais de um jeito, o motor escolhe uma opção, segue em frente e, se o resto do padrão falhar depois, volta para tentar a próxima.

Quase sempre isso é barato. Pegue a+b contra aaab: o a+ consome os três a, o b casa e pronto. Contra aaac, o a+ consome os três a, o b falha, o motor devolve um a e tenta de novo, depois outro. Em poucos passos ele conclui que não há match.

O problema começa quando o número de jeitos de dividir a entrada cresce de forma exponencial.

Quantificadores aninhados: a armadilha clássica

Olhe para (a+)+$. O a+ de dentro casa um ou mais a, e o + de fora repete esse grupo uma ou mais vezes. Uma sequência de quatro a pode ser dividida como aaaa, aaa a, aa aa, a aaa, aa a a e assim por diante: para n caracteres existem cerca de 2 elevado a n - 1 divisões.

Quando a entrada é só de a, a primeira divisão já funciona e o match é instantâneo. Quando a entrada termina com algo que faz o match falhar, como aaaaaaaaaaaaaaaaaaaaaaaaaa!, o motor precisa provar que nenhuma divisão funciona, e para isso tenta todas.

Rodando /(a+)+$/ contra uma sequência de a seguida de ! num notebook comum, os tempos foram estes:

• 20 caracteres: cerca de 9 ms;
• 22 caracteres: cerca de 34 ms;
• 24 caracteres: cerca de 136 ms;
• 26 caracteres: cerca de 400 ms.

Cada dois caracteres a mais multiplicam o tempo por quatro, mais ou menos. Com 30 caracteres você já espera segundos; com 40 a página praticamente congela. Os números exatos mudam com o motor e a máquina, mas a curva é a mesma.

O padrão de nome de host do começo tem o mesmo formato. ([a-z0-9]+\.?)+ é um grupo com + dentro e + fora, e como o ponto é opcional, uma sequência de letras pode ser repartida entre as repetições de um número exponencial de jeitos. Com 26 letras e um ! no fim, ele levou cerca de 350 ms no mesmo teste.

Os formatos que pedem atenção

Você não precisa analisar cada padrão na mão. Basta aprender a reconhecer alguns formatos:

• Grupo com quantificador que contém outro quantificador: (a+)+, (\d*)*, (\w+\s?)+. É o caso mais comum.
• Alternativas que se sobrepõem: (a|aa)+ ou (\w|\d)+. Se dois ramos casam o mesmo texto, o motor pode escolher entre eles em cada posição.
• Separador opcional entre partes repetidas: (\w+\.?)+ ou (\w+-?)+. Deixar o separador opcional permite repartir os mesmos caracteres entre as repetições.
• Quantificadores vizinhos disputando os mesmos caracteres: \d+\d+$ ou .*.*=. Menos explosivo, mas ainda lento com entrada longa.

O ponto em comum é a ambiguidade: o mesmo trecho de texto pode casar de mais de um jeito.

Como corrigir

O objetivo é fazer cada caractere casar de um jeito só.

Torne o separador obrigatório dentro da repetição. Em vez de um ponto opcional depois de cada palavra, descreva a estrutura direto: uma palavra e depois zero ou mais grupos de "ponto mais palavra".

// lento com entrada ruim
const slow = /^([a-z0-9]+\.?)+$/;

// rápido: cada caractere pertence a um lugar só
const fast = /^[a-z0-9]+(\.[a-z0-9]+)*$/;

O segundo padrão aceita os mesmos nomes com pontos, como api.example.com, e recusa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! em bem menos de um milissegundo, porque só existe um jeito de ler a entrada. De quebra, ele é mais rigoroso: o original deixava passar um ponto no final sem querer, e este não deixa.

Tire o quantificador redundante. (a+)+ casa exatamente o mesmo que a+. A repetição de fora só acrescenta ambiguidade.

Deixe as alternativas exclusivas. Reescreva (a|aa)+ como a+, e (\w|\d)+ como \w+, já que \w inclui dígitos.

Use classes de caracteres específicas em vez de .*. "[^"]*" lê um texto entre aspas numa passada só, enquanto ".*" faz o motor testar cada aspa possível como fim.

Limite a entrada. Um campo que deveria ter um nome de host não tem motivo para aceitar 10 mil caracteres. Conferir o tamanho antes de rodar a expressão limita o pior caso.

Use um motor sem backtracking onde fizer diferença. Alguns motores, como o RE2 do Google e a crate regex do Rust, garantem tempo linear porque não oferecem recursos que dependem de backtracking, como retrovisores. Para padrões que vêm do usuário, a troca vale a pena.

Por que isso importa fora do navegador

No navegador, uma regex lenta trava uma aba. No servidor, pode derrubar o serviço inteiro. O Node.js roda o JavaScript numa thread só, então uma requisição que dispara backtracking catastrófico bloqueia todas as outras até terminar. Essa classe de falha se chama ReDoS, negação de serviço por expressão regular, e já afetou pacotes populares e sites grandes. Um padrão usado para validar entrada é exatamente onde um atacante miraria.

É por isso também que o Testador de Regex deste site roda cada padrão num Web Worker com limite de um segundo. Se a expressão demorar mais, o worker é encerrado e você vê um aviso em vez de uma página travada. Teste (a+)+$ com uma sequência longa de a seguida de !, depois a versão corrigida, e compare.

Checklist rápido

Antes de colocar uma expressão regular em produção, principalmente uma que roda sobre entrada do usuário:

1. Procure um quantificador dentro de um grupo quantificado e alternativas que casam o mesmo texto.
2. Teste com uma entrada longa que quase casa: caracteres válidos com um caractere ruim no fim.
3. Reescreva as partes ambíguas para cada caractere casar de um jeito só.
4. Limite o tamanho da entrada antes de rodar o match.
5. Para padrões vindos de fora ou entradas muito grandes, considere um motor de tempo linear.

Resumo

O backtracking catastrófico acontece quando um padrão permite casar o mesmo texto de muitos jeitos e a entrada obriga o motor a testar todos antes de falhar. Os sinais de alerta são quantificadores aninhados, alternativas sobrepostas e separadores opcionais dentro de repetições. Tirar a ambiguidade, limitar a entrada e testar com textos que quase casam mantém as suas expressões regulares rápidas, no navegador e no servidor.