Backtracking catastrófico: por qué una regex puede colgarse

La mayoría de las regex terminan en microsegundos. Unas pocas, con la entrada equivocada, tardan segundos, minutos o más, con un núcleo de la CPU al máximo todo ese tiempo. Se llama backtracking catastrófico, y ha tumbado sitios web reales.

La buena noticia es que los patrones peligrosos tienen una forma reconocible, y los arreglos suelen ser pequeños. Este artículo muestra la forma, los números y las reescrituras.

01Cómo funciona el backtracking

JavaScript, Python, Java, PHP y la mayoría de los lenguajes usan un motor con backtracking (vuelta atrás). Cuando un patrón ofrece opciones (cuántos caracteres se queda un +, qué lado de un | probar), el motor elige una y sigue. Si más adelante la coincidencia falla, vuelve atrás y prueba la siguiente opción.

Con un patrón como ^a+$ sobre aaaa!, no hay mucho que probar: a+ se queda las cuatro a, $ falla en el !, el motor devuelve las a de una en una y cada intento falla enseguida. Un puñado de pasos y luego “no coincide”.

02La forma que explota

Ahora mete un cuantificador dentro de otro cuantificador:

(a+)+ significa “uno o más grupos, cada uno de una o más a”. Cuatro a se pueden repartir en grupos de ocho maneras: aaaa, aaa|a, a|aaa, aa|aa, aa|a|a, etc. Cuando el ! hace fallar la coincidencia, el motor prueba todos los repartos antes de rendirse. Cada a extra duplica el número de repartos.

Así se ve en Node 23 en un portátil normal, con una cadena de a seguida de !:

Longitud	^(a+)+$	^a+$
24 a	0,12 s	menos de 0,01 ms
26 a	0,5 s	menos de 0,01 ms
28 a	2 s	menos de 0,01 ms
40 a	más de dos horas (estimado)	menos de 0,01 ms

Las mismas cadenas coinciden, con un coste radicalmente distinto. El peligro siempre es una coincidencia que falla: cuando la entrada coincide, el primer camino suele funcionar.

La forma general que hay que vigilar es un grupo repetido cuyo interior puede coincidir con el mismo texto de más de una manera:

• Cuantificadores anidados: (a+)+, (\w+)*, (\d*)+
• Alternativas que se solapan, repetidas: (a|a)+, (\w|\d)+, (.*,)*
• Varios .* seguidos sobre el mismo texto: .*=.*=.*

03Ha pasado en producción

Stack Overflow, julio de 2016. Una publicación contenía unos 20 000 espacios en blanco seguidos en mitad de una línea. Una regex pensada para recortar los espacios del final de una línea, básicamente \s+$, intentó una coincidencia empezando en cada uno de esos espacios. Cada intento llegaba hasta el final de los espacios, se encontraba más texto en lugar del final de la línea y fallaba. Eso es trabajo cuadrático, unos 200 millones de pasos, y dejó el sitio caído 34 minutos.

Cloudflare, julio de 2019. Una nueva regla del cortafuegos contenía un patrón con .*(?:.*=.*). Todos los servidores que ejecutaban la regla llegaron al 100 % de CPU, y la red de Cloudflare perdió tráfico en todo el mundo durante unos 27 minutos.

Ninguno de los dos patrones parecía peligroso a simple vista. Los dos iban bien con entradas normales.

04Arreglo 1: haz que las opciones sean exclusivas

El arreglo más limpio es un patrón en el que cada carácter solo puede coincidir de una manera. Quita el anidamiento:

Un ejemplo real: números separados por comas. La versión arriesgada anida un grupo repetido alrededor de otro cuantificador y deja la coma como opcional, así que una serie de dígitos se puede repartir de muchas maneras:

La versión segura hace obligatoria la coma entre elementos, así que cada dígito solo puede ocupar un lugar:

05Arreglo 2: di lo que no puede aparecer

.* suele ser el culpable porque puede coincidir con cualquier cosa, incluido el texto que necesita la parte siguiente. Una clase negada es exclusiva por construcción:

06Arreglo 3: grupos atómicos y cuantificadores posesivos

Un grupo atómico (?>…) coincide una vez y nunca devuelve nada. Un cuantificador posesivo (a++, \d*+) hace lo mismo con un solo cuantificador. Cualquiera de los dos elimina las alternativas que el motor volvería a probar.

Python admite los dos desde la 3.11. Java, PCRE y PHP también los tienen. JavaScript no tiene ninguno, pero un lookahead con una referencia inversa se comporta como un grupo atómico: (?=(a+))\1 coincide con las a una vez y no se puede repartir.

07Arreglo 4: limita la entrada, o el motor

• Limita la longitud de la entrada antes de buscar coincidencias. Muchos patrones explosivos son inofensivos con 200 caracteres.
• Usa un motor de tiempo lineal con entradas no fiables. RE2 de Google (con bindings para Node, Python, Go y más) y el crate regex de Rust nunca hacen backtracking, así que no pueden explotar. No admiten referencias inversas ni lookarounds: ese es el precio.
• Pon un tiempo límite donde la plataforma lo permita. El Regex de .NET acepta un matchTimeout.

08Pruébalo

Escribe la versión segura de una lista de números separados por comas:

09Lista de comprobación

• Señal de peligro: un grupo cuantificado cuyo interior puede coincidir con el mismo texto de varias maneras: (a+)+, (\w|\d)+, (.*,)*.
• El coste aparece en las coincidencias que fallan, y puede duplicarse con cada carácter.
• Haz que cada carácter solo pueda coincidir de una manera: separadores obligatorios, sin anidamiento.
• Prefiere [^x]* a .* cuando la parte siguiente empieza por x.
• Usa grupos atómicos o cuantificadores posesivos donde puedas (Python 3.11+, Java, PCRE).
• Con entradas no fiables, limita su longitud o usa RE2.

10Sigue practicando

• La sección de rendimiento de la guía trata esto con más ejemplos.
• El artículo sobre cuantificadores codiciosos y perezosos explica cómo eligen los cuantificadores lo que se quedan.
• La cantera de cuantificadores es un pack de práctica para dominar los cuantificadores al detalle.