Desempenho de regex: evite explosão de retrocesso

Desempenho de regex: uma expressão pode derrubar todo o servidor

O retrocesso catastrófico (Catastrophic Backtracking) pode fazer o tempo de correspondência de uma regex passar de milissegundos para horas.

Cenário	Regex	Comprimento da entrada	Tempo
Correspondência normal	`/^abc$/`	100	<1ms
Retrocesso linear	`/a*b/`	100	~1ms
Retrocesso exponencial	`/(a+)+b/`	30	~10s
Retrocesso exponencial	`/(a)b/`	30	~10s

I. Princípio do mecanismo de retrocesso

Como funciona o motor NFA

JavaScript usa um motor NFA (Autômato Finito Não Determinístico) com algoritmo de retrocesso:

Entrada: "aaaac"
Regex: /(a+)+c/

Processo de correspondência:
1. (a+) corresponde "aaaa" → tenta +c → não corresponde 'c'
2. Retrocesso: (a+) corresponde "aaa" → (a+) corresponde "a" → tenta +c → não corresponde
3. Retrocesso: (a+) corresponde "aa" → (a+) corresponde "aa" → tenta +c → não corresponde
4. Retrocesso: (a+) corresponde "aa" → (a+) corresponde "a" → (a+) corresponde "a" → ...
5. ... retrocesso exponencial

Cálculo do número de retrocessos

Para /(a+)+b/ correspondendo a "aaa..." (n a's):

Número de retrocessos ≈ 2^n

n=10: ~1.024 vezes
n=20: ~1.048.576 vezes
n=30: ~1.073.741.824 vezes

II. Padrões comuns de retrocesso catastrófico

Padrão 1: Quantificadores aninhados

// Retrocesso catastrófico
/(a+)+b/     // Quantificador + aninhado
/(a*)*b/     // Quantificador * aninhado
/(\w+)+@/    // \w+ aninhado

// Correção: evitar quantificadores aninhados
/a+b/        // Quantificador de camada única
/(\w+)@/     // Quantificador de camada única

Padrão 2: Alternância ordenada

// Retrocesso catastrófico: opções de alternância com prefixo comum
/(a|ab)+c/

// Com entrada "abababab..." que não corresponde, o motor tenta todas as combinações
// Número de retrocessos ≈ O(2^n)

// Correção: extrair o prefixo comum
/a(b?)+c/

Padrão 3: Quantificadores sobrepostos

// Retrocesso catastrófico
/.*.*=/

// Ambos .* podem corresponder ao mesmo conteúdo, gerando muitos retrocessos

// Correção: combinar quantificadores
/.*=/

Padrão 4: Armadilha de referência de retrocesso

// Retrocesso catastrófico
/^(b+)(a+)\1$/

// Com entrada "bbbbaaaa", \1 testa todas as subdivisões de b+

// Correção: se possível, evitar referências de retrocesso, ou limitar o alcance do quantificador
/^(b+)(a+)\1$/.test(input) // Apenas para entradas curtas

III. Técnicas de otimização

Técnica 1: Especificar classes de caracteres

// Lento: . corresponde a qualquer caractere, muito retrocesso
/.*foo/

// Rápido: [^\n]* não corresponde a quebras de linha, reduz retrocesso
/[^\n]*foo/

// Mais rápido: se souber que antes de foo só há letras
/[a-z]*foo/

Técnica 2: Ancorar para reduzir o espaço de busca

// Lento: tenta corresponder de cada posição
/foo/

// Rápido: se foo está no início da linha
/^foo/

// Rápido: se foo está no final da linha
/foo$/

// Rápido: ancorar ambos os lados
/^foo$/

Técnica 3: Uso correto de quantificadores não greedy

// Cenário: extrair conteúdo de tags <b>

// Lento: quantificador greedy + retrocesso
/<b>(.*)<\/b>/

// Rápido: quantificador não greedy (mas ainda pode haver retrocesso)
/<b>(.*?)<\/b>/

// Mais rápido: classe de caracteres exclusiva (zero retrocesso)
/<b>([^<]*)<\/b>/

Método	Correspondência `<b>hello</b><b>world</b>`	Retrocesso
`(.*)`	`hello</b><b>world`	Múltiplos
`(.*?)`	`hello`	Poucos
`([^<]*)`	`hello`	Zero

Técnica 4: Grupos atômicos (ES2024+)

// Grupo atômico (?>...) uma vez correspondido, não retrocede
const regex = /^(?>a+)+b$/;

// Equivalente a: se a+ correspondeu, não retrocede para o + externo tentar novamente
// Corresponde "aaab" → sucesso
// Corresponde "aaa" → falha imediata (sem retrocesso exponencial)

Técnica 5: Quantificadores possessivos (alguns motores)

// Quantificador possessivo a++ não libera para retrocesso após corresponder
// JavaScript não suporta, mas pode ser simulado com grupos atômicos
const regex = /^(?>(a+))b$/;

Técnica 6: Pré-compilação + reutilização

// Lento: criar novo RegExp toda vez
function validate(input) {
  return /^[\w.+-]+@[\w-]+\.[\w.]+$/.test(input);
}

// Rápido: pré-compilar
const EMAIL_REGEX = /^[\w.+-]+@[\w-]+\.[\w.]+$/;
function validate(input) {
  return EMAIL_REGEX.test(input);
}

IV. Ferramentas de análise de desempenho

Usar a ferramenta de regex do ToolsKu

Abrir Ferramenta de Expressões Regulares
Inserir a expressão regular e o texto de teste
Ver os resultados de correspondência e o tempo
Ajustar a regex, comparar o desempenho antes e depois da otimização

Medição integrada no JS

function measureRegex(regex, input, iterations = 1000) {
  const start = performance.now();
  for (let i = 0; i < iterations; i++) {
    regex.test(input);
  }
  const end = performance.now();
  return {
    totalTime: end - start,
    avgTime: (end - start) / iterations,
    iterations,
  };
}

// Comparar
const slow = measureRegex(/(a+)+b/, 'a'.repeat(25));
const fast = measureRegex(/a+b/, 'a'.repeat(25));
console.log(`Lento: ${slow.avgTime}ms, Rápido: ${fast.avgTime}ms`);

Biblioteca recheck para detectar regex perigosas

npm install recheck

import { check } from 'recheck';

const result = check(/(a+)+b/);
// { safe: false, complexity: 'exponential' }

const result2 = check(/a+b/);
// { safe: true, complexity: 'linear' }

V. Comparação de desempenho de expressões regulares comuns

Regex	Complexidade	Segura	Versão otimizada
`/(a+)+b/`	Exponencial	❌	`/a+b/`
`/(a\|ab)+c/`	Exponencial	❌	`/a(b?)+c/`
`/..=/`	Exponencial	❌	`/.*=/`
`/(\d+){1,10}/`	Polinomial	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	Linear	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	Constante	✅	—

VI. Proteção do lado do servidor

Proteção por timeout

function safeRegexTest(regex, input, timeoutMs = 100) {
  const start = Date.now();
  const result = regex.test(input);
  if (Date.now() - start > timeoutMs) {
    throw new Error('Regex timeout: possible catastrophic backtracking');
  }
  return result;
}

Motor re2 (garantia de tempo linear)

import RE2 from 're2';

// RE2 garante tempo linear, sem explosão de retrocesso
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // Seguro, não vai travar

Limitar o comprimento da entrada

function validateWithLimit(regex, input, maxLength = 1000) {
  if (input.length > maxLength) {
    throw new Error(`Input exceeds maximum length: ${maxLength}`);
  }
  return regex.test(input);
}

VII. Lista de melhores práticas

Evitar quantificadores aninhados: (a+)+ → a+
Especificar classes de caracteres: . → [^\n] ou classe mais específica
Extrair prefixos comuns: (a|ab) → a(b?)
Usar classes exclusivas em vez de não greedy: (.*?) → ([^<]*)
Ancorar para reduzir o espaço de busca: ^ / $
Pré-compilar expressões regulares: evitar criação repetida
Usar recheck para detectar: verificar automaticamente regex perigosas no CI
Proteção por timeout do servidor: prevenir DoS por regex
Limitar o comprimento da entrada: reduzir o impacto do pior caso