Rendimiento de regex: evitar la explosión de retroceso

Rendimiento de regex: una expresión puede colapsar todo el servidor

El retroceso catastrófico (Catastrophic Backtracking) puede hacer que el tiempo de coincidencia de una expresión regular pase de milisegundos a horas.

Escenario	Regex	Longitud de entrada	Tiempo
Coincidencia normal	`/^abc$/`	100	<1ms
Retroceso lineal	`/a*b/`	100	~1ms
Retroceso exponencial	`/(a+)+b/`	30	~10s
Retroceso exponencial	`/(a)b/`	30	~10s

I. Principio del mecanismo de retroceso

Funcionamiento del motor NFA

JavaScript usa un motor NFA (Autómata Finito No Determinista) con un algoritmo de retroceso:

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

Proceso de coincidencia:
1. (a+) coincide "aaaa" → intenta +c → no coincide 'c'
2. Retroceso: (a+) coincide "aaa" → (a+) coincide "a" → intenta +c → no coincide
3. Retroceso: (a+) coincide "aa" → (a+) coincide "aa" → intenta +c → no coincide
4. Retroceso: (a+) coincide "aa" → (a+) coincide "a" → (a+) coincide "a" → ...
5. ... retroceso exponencial

Cálculo del número de retrocesos

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

Número de retrocesos ≈ 2^n

n=10: ~1,024 veces
n=20: ~1,048,576 veces
n=30: ~1,073,741,824 veces

II. Patrones comunes de retroceso catastrófico

Patrón 1: Cuantificadores anidados

// Retroceso catastrófico
/(a+)+b/     // Cuantificador + anidado
/(a*)*b/     // Cuantificador * anidado
/(\w+)+@/    // \w+ anidado

// Corrección: evitar cuantificadores anidados
/a+b/        // Cuantificador de una sola capa
/(\w+)@/     // Cuantificador de una sola capa

Patrón 2: Alternancia ordenada

// Retroceso catastrófico: opciones de alternancia con prefijo común
/(a|ab)+c/

// Con entrada "abababab..." que no coincide, el motor prueba todas las combinaciones
// Número de retrocesos ≈ O(2^n)

// Corrección: extraer el prefijo común
/a(b?)+c/

Patrón 3: Cuantificadores superpuestos

// Retroceso catastrófico
/.*.*=/

// Ambos .* pueden coincidir con el mismo contenido, generando muchos retrocesos

// Corrección: combinar cuantificadores
/.*=/

Patrón 4: Trampa de referencia de retroceso

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

// Con entrada "bbbbaaaa", \1 prueba todas las subdivisiones de b+

// Corrección: si es posible, evitar referencias de retroceso, o limitar el rango del cuantificador
/^(b+)(a+)\1$/.test(input) // Solo para entradas cortas

III. Técnicas de optimización

Técnica 1: Especificar clases de caracteres

// Lento: . coincide con cualquier carácter, mucho retroceso
/.*foo/

// Rápido: [^\n]* no coincide con saltos de línea, reduce retroceso
/[^\n]*foo/

// Más rápido: si se sabe que antes de foo solo hay letras
/[a-z]*foo/

Técnica 2: Anclar para reducir el espacio de búsqueda

// Lento: intenta coincidir desde cada posición
/foo/

// Rápido: si foo está al inicio de línea
/^foo/

// Rápido: si foo está al final de línea
/foo$/

// Rápido: anclar ambos lados
/^foo$/

Técnica 3: Uso correcto de cuantificadores no greedy

// Escenario: extraer contenido de etiquetas <b>

// Lento: cuantificador greedy + retroceso
/<b>(.*)<\/b>/

// Rápido: cuantificador no greedy (pero aún puede haber retroceso)
/<b>(.*?)<\/b>/

// Más rápido: clase de caracteres excluyente (cero retroceso)
/<b>([^<]*)<\/b>/

Método	Coincidencia `<b>hello</b><b>world</b>`	Retroceso
`(.*)`	`hello</b><b>world`	Múltiples
`(.*?)`	`hello`	Pocos
`([^<]*)`	`hello`	Cero

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

// Grupo atómico (?>...) una vez que coincide, no retrocede
const regex = /^(?>a+)+b$/;

// Equivalente a: si a+ coincide, no retrocede para que el + externo reintente
// Coincide "aaab" → éxito
// Coincide "aaa" → falla inmediatamente (sin retroceso exponencial)

Técnica 5: Cuantificadores posesivos (algunos motores)

// Cuantificador posesivo a++ no libera para retroceso después de coincidir
// JavaScript no lo soporta, pero se puede simular con grupos atómicos
const regex = /^(?>(a+))b$/;

Técnica 6: Precompilación + reutilización

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

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

IV. Herramientas de análisis de rendimiento

Usar la herramienta de regex de ToolsKu

Abrir Herramienta de Expresiones Regulares
Ingresar la expresión regular y el texto de prueba
Ver los resultados de coincidencia y el tiempo
Ajustar la regex, comparar el rendimiento antes y después de la optimización

Medición integrada en 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 peligrosas

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. Comparación de rendimiento de expresiones regulares comunes

Regex	Complejidad	Segura	Versión optimizada
`/(a+)+b/`	Exponencial	❌	`/a+b/`
`/(a\|ab)+c/`	Exponencial	❌	`/a(b?)+c/`
`/..=/`	Exponencial	❌	`/.*=/`
`/(\d+){1,10}/`	Polinomial	⚠️	`/\d{1,10}/`
`/^[a-z]+$/`	Lineal	✅	—
`/^\d{4}-\d{2}-\d{2}$/`	Constante	✅	—

VI. Protección del lado del servidor

Protección por tiempo de espera

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 (garantía de tiempo lineal)

import RE2 from 're2';

// RE2 garantiza tiempo lineal, sin explosión de retroceso
const regex = new RE2('(a+)+b');
regex.test('a'.repeat(100)); // Seguro, no se bloqueará

Limitar la longitud de 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 mejores prácticas

Evitar cuantificadores anidados: (a+)+ → a+
Especificar clases de caracteres: . → [^\n] o una clase más específica
Extraer prefijos comunes: (a|ab) → a(b?)
Usar clases excluyentes en lugar de no greedy: (.*?) → ([^<]*)
Anclar para reducir el espacio de búsqueda: ^ / $
Precompilar expresiones regulares: evitar creación repetida
Usar recheck para detectar: verificar automáticamente regex peligrosas en CI
Protección por tiempo de espera del servidor: prevenir DoS por regex
Limitar la longitud de entrada: reducir el impacto del peor caso