Retroceso Catastrófico

El retroceso catastrófico es un fenómeno en las expresiones regulares donde el motor tarda una cantidad excesiva de tiempo en evaluar ciertos patrones, lo que provoca una degradación significativa del rendimiento — a veces segundos, minutos, o prácticamente para siempre. Ocurre porque el motor intenta hacer coincidir partes de la cadena de muchas formas diferentes antes de rendirse, y el número de combinaciones que explora crece exponencialmente con la longitud de la entrada.

Esta página cubre qué desencadena el problema, cómo reconocer un patrón peligroso y técnicas concretas para reescribir una expresión regular de modo que se mantenga rápida. Se asume que estás familiarizado con los cuantificadores y la diferencia entre la coincidencia codiciosa y perezosa.

Por qué importa: Una sola expresión regular lenta aplicada a la entrada del usuario es un vector real de denegación de servicio (a menudo llamado "ReDoS"). Un atacante solo necesita enviar una cadena corta diseñada para maximizar el retroceso y congelar el bucle de eventos de Node.js.

¿Qué Causa el Retroceso Catastrófico?

El retroceso catastrófico ocurre típicamente con cuantificadores anidados — un cuantificador dentro de un grupo que a su vez está cuantificado, como (a+)+. El peligro aparece cuando dos partes del patrón pueden coincidir con los mismos caracteres, de modo que el motor tiene muchas formas superpuestas de dividir la entrada. Cuando la coincidencia finalmente falla, el motor debe probar cada una de esas divisiones antes de poder concluir que nada coincide. Aquí está el ejemplo clásico:

Si no tarda mucho en tu ordenador, puedes añadir otro carácter a a str. ¿Por qué tarda tanto? Analicémoslo. El patrón /^(a+)+$/ está compuesto por:

• ^ que aserta la posición al inicio de la cadena.
• (a+) que coincide con uno o más caracteres a.
• + que permite que el grupo anterior (a+) se repita una o más veces.
• $ que aserta la posición al final de la cadena.

Ahora el proceso de coincidencia es:

1. Coincidencia inicial: El motor comienza al principio de la cadena (^).
2. Primera coincidencia de grupo: El motor hace coincidir el primer a+, consumiendo todos los caracteres a (aaa...).
3. Cuantificador externo: El + externo permite que el motor repita el grupo (a+).

Cuando el motor llega al signo de exclamación (!), no puede hacerlo coincidir con el patrón, provocando que la coincidencia falle. En este momento comienza el retroceso:

1. Intento de retroceso: El motor retrocede para dividir repetidamente los caracteres a coincidentes entre los cuantificadores a+ interno y + externo. Reevalúa cada división para ver si una partición diferente puede hacer coincidir el patrón hasta el final de la cadena.
2. Crecimiento exponencial: Este proceso de retroceso puede crecer exponencialmente a medida que el motor prueba cada forma posible de dividir la cadena de caracteres a en diferentes grupos que podrían coincidir con (a+)+.

Para una cadena de n caracteres a, el a+ interno y el + externo pueden dividir esos caracteres en grupos de aproximadamente 2^(n-1) formas diferentes. Cuando el ! final hace que la coincidencia falle, el motor tiene que probar todas ellas. Por eso añadir un solo a extra a la entrada aproximadamente duplica el tiempo de ejecución — la señal característica de la explosión exponencial. La coincidencia a continuación tiene éxito rápidamente porque no hay una cola fallida que fuerce una exploración completa:

La lección: el retroceso catastrófico solo muerde cuando un patrón puede coincidir de muchas formas y la coincidencia global finalmente falla. La entrada fallida diseñada es exactamente lo que envía un atacante.

Identificar Patrones Propensos al Retroceso Catastrófico

Como lista de verificación mental rápida, un patrón está en riesgo cuando tiene las tres características siguientes: una repetición, dentro de otra repetición, sobre caracteres que se solapan. Señales de alerta comunes:

• Cuantificadores anidados, p. ej. (a+)+, (\d*)*, (\w+)*.
• Grupos cuantificados que contienen una alternancia que se solapa, p. ej. (a|a)+ o (\w|\d)+ (\w ya incluye \d).
• Un .* o .+ codicioso entre dos cosas que también pueden coincidir con los mismos caracteres, p. ej. <.+>.*<.+>.
• Patrones sin anclas en entradas largas, que reintentan la coincidencia completa en cada posición de inicio.

Si las repeticiones de un grupo cuantificado pueden coincidir con la misma subcadena, hay ambigüedad, y la ambigüedad es lo que el retroceso explora.

Estrategias para Prevenir el Retroceso Catastrófico

El objetivo de cada corrección a continuación es el mismo: eliminar la ambigüedad que permite al motor dividir la entrada de más de una forma. Cambiar de codicioso a perezoso (+?, *?) no ayuda aquí — ambos siguen explorando cada división; el perezoso solo las explora en un orden diferente. Es necesario cambiar la estructura del patrón, no su codicia.

1. Eliminar el Cuantificador Anidado

(a+)+ es casi siempre equivalente a un solo cuantificador. Si solo necesitas "uno o más a", simplemente escribe a+. Hay exactamente una forma de hacer eso coincidir, de modo que el motor no puede retroceder hacia una explosión combinatoria.

2. Emular un Grupo Atómico con Lookahead

JavaScript no tiene grupos atómicos incorporados (?>...) ni cuantificadores posesivos (a++) como algunos otros sabores de expresiones regulares. Puedes reproducir el mismo comportamiento de "coincidir esto una vez y nunca devolverlo" con un lookahead más una referencia posterior: (?=(a+))\1. El lookahead hace coincidir a+ de forma codiciosa, lo captura, y \1 consume exactamente ese texto — pero debido a que el grupo capturado estaba dentro de un lookahead, el motor no lo reparticionará al retroceder.

3. Usar Clases de Caracteres Específicas y No Solapadas

El retroceso explota cuando partes adyacentes de un patrón pueden coincidir con los mismos caracteres. Haz que cada parte coincida con un conjunto distinto para que solo haya una forma de dividir la entrada. Por ejemplo, prefiere \d+\.\d+ sobre [\d.]+\.[\d.]+, donde ambos grupos [\d.]+ compiten por el mismo punto.

4. Anclar y Limitar el Patrón

Anclar con ^ y $ permite que el motor falle rápidamente en lugar de reintentar la coincidencia en cada posición de la cadena. Poner un límite superior explícito en un cuantificador (a{1,20} en lugar de a+) limita cuánto trabajo puede generar cualquier repetición individual.

Ejemplos Prácticos y Soluciones

Ejemplo 1: Coincidencia de Etiquetas HTML Anidadas

Un caso de uso común para las expresiones regulares es hacer coincidir etiquetas HTML anidadas, lo que puede provocar fácilmente un retroceso catastrófico si no se maneja correctamente. Nota: Las expresiones regulares son generalmente inadecuadas para analizar estructuras HTML arbitrarias o profundamente anidadas; usa un analizador HTML adecuado para documentos complejos.

Patrón Problemático

Patrón Mejorado

Reemplaza el .* codicioso (que puede engullir todo el documento y luego retroceder lentamente) con una clase que no pueda cruzar el corchete de cierre. [^<]* coincide con todo hasta el siguiente <, por lo que no hay solapamiento a través del cual retroceder.

Ejemplo 2: Validar una Lista de Identificadores

Patrón Problemático

([a-zA-Z0-9_]+)+ es la misma trampa que (a+)+: el + interno y el + externo repiten sobre los mismos caracteres, por lo que una entrada larga sin coincidencia desencadena un retroceso exponencial.

Una Alternancia Segura

No todos los grupos cuantificados son peligrosos. (?:ab|cd)+e está bien: ab y cd son disjuntos, por lo que el motor nunca tiene que dudar sobre cómo dividió la entrada. Usa un grupo no capturador (?:...) cuando no necesites el texto capturado — es ligeramente más rápido y más claro, aunque no cambia el comportamiento de retroceso aquí.

Conclusión

El retroceso catastrófico puede congelar una aplicación JavaScript — y como lo desencadena la entrada, es un riesgo de seguridad genuino, no solo de rendimiento. La solución casi siempre consiste en eliminar la ambigüedad: aplanar cuantificadores anidados, hacer que partes adyacentes del patrón coincidan con conjuntos de caracteres disjuntos, anclar con ^/$, limitar las repeticiones o emular un grupo atómico con (?=(...))\1. Cambiar a cuantificadores perezosos no ayuda.

Cuando escribas una expresión regular que se ejecute contra entradas no confiables, pruébala con cadenas largas que fallen (p. ej. cien as seguidas de !) y observa el tiempo. Si añadir un carácter más aumenta notablemente el tiempo, el patrón es exponencial y necesita reestructurarse.

Para profundizar, revisa los capítulos relacionados sobre cuantificadores, cuantificadores codiciosos y perezosos, grupos de captura y clases de caracteres.

Práctica