¿Por qué mi regex es tan lenta? Retroceso catastrófico y ReDoS

Tienes una regex que funciona. Pasa todas las pruebas que le lanzaste, se publica y durante semanas nadie nota nada raro. Hasta que un día llega una entrada un poco más larga —un párrafo pegado, una URL malformada, una línea de log con una ristra larga de espacios— y la pestaña se bloquea. La CPU se clava al 100 %. En un servidor, el proceso de Node.js entero deja de responder a las peticiones. Nada lanzó un error; la regex sigue siendo, técnicamente, correcta. Solo que nunca termina.

Conviene precisar de qué clase de «lento» hablamos, porque no toda regex lenta es el mismo animal. Algunas son solo polinómicas —cuadráticas, pongamos, así que el doble de entrada supone alrededor de cuatro veces el trabajo, molesto pero llevadero—; otras son lentas únicamente porque la entrada es genuinamente enorme, o porque la llamas dentro de un bucle apretado. Este artículo no va de esas: esas son optimización corriente. Va de la clase mucho más fea en la que un aumento pequeño de la entrada hace explotar el tiempo de ejecución: el trabajo crece de forma exponencial, así que añadir un puñado de caracteres convierte microsegundos en minutos y luego en nunca. Eso tiene nombre —retroceso catastrófico (catastrophic backtracking)— y cuando alguien te manda esa entrada a propósito para tumbar tu servicio, se llama ataque ReDoS (denegación de servicio por expresión regular).

La buena noticia es que esto no tiene nada de misterioso. Sale directamente de cómo trabaja un motor de retroceso, que el primer artículo de esta serie desgranó en detalle. Si entiendes que el motor come con voracidad y retrocede cuando se atasca, el retroceso catastrófico no es más que ese mismo mecanismo descontrolado. Este artículo retoma justo ahí: qué hace explotar el trabajo, cómo reconocer las formas peligrosas a simple vista, dónde se esconden en el código real y —dado que JavaScript casi no te da barandillas— cómo reescribir para salir del apuro.

De dónde viene la explosión

El modelo del motor del primer artículo, comprimido en una frase: un motor de retroceso, cuando un cuantificador voraz no consigue completar la coincidencia, rebobina y prueba otro reparto —devuelve caracteres y busca otro camino hacia delante— y solo se rinde cuando ha agotado todas las posibilidades. El retroceso catastrófico es lo que ocurre cuando «todas las posibilidades» resulta ser un número astronómico.

El disparador de manual es un cuantificador anidado: un grupo que se repite y que, a su vez, se repite.

(a+)+$

Leído literalmente, es redundante. «Una o más tandas de una o más aes, ancladas al final de la cadena» describe exactamente el mismo conjunto de cadenas que un simple a+$. Pero el motor no sabe que son equivalentes, y esa redundancia es precisamente lo que lo hunde: el a+ interno y el + externo pueden reclamar los mismos caracteres, así que una tanda de aes se puede trocear en grupos de más de una manera, y el motor se siente obligado a probarlas todas antes de darse por vencido.

Míralo con solo cuatro caracteres, aaaX. La jugada de apertura del motor es la voraz: el a+ interno se traga las tres aes en un único grupo, (aaa). Ahora quiere $, pero el cursor está plantado sobre la X —fallo. Así que retrocede. El a+ interno devuelve una a y deja (aa); el + externo aprovecha para abrir un segundo grupo, y el a+ interno recoge la que sobra, formando (aa)(a); prueba $, sigue la X, fallo. Retrocede otra vez: (a)(aa), fallo; (a)(a)(a), fallo. Solo después de probar y rechazar las cuatro maneras de agrupar tres aes se le permite al motor abandonar esta posición de inicio, desplazarse un carácter a la derecha y empezar todo el suplicio de nuevo.

Que tres aes den cuatro agrupaciones no es casualidad: una tanda de n aes tiene 2ⁿ⁻¹ maneras de partirse en grupos ordenados, y la fatídica $ —que jamás se cumple delante de esa X— obliga al motor a recorrerlas una por una antes de ceder. Diez aes son 512 intentos; veinte, más de medio millón; treinta, más de quinientos millones. Por eso el bloqueo no es gradual sino repentino: cada a que añades duplica aproximadamente el trabajo. No es lento, es exponencial, y una curva exponencial parece plana justo hasta el instante en que se vuelve vertical.

No te molestes en buscar la longitud exacta que lo desborda; eso cambia con tu navegador, tu hardware y la implementación del motor. Lo que importa es la forma de la curva, y una propiedad más que convierte una manía de rendimiento en un arma: el caso patológico es el caso que falla. Un patrón así parece perfectamente rápido en las pruebas, porque las entradas con las que pruebas coinciden rápido y barato. Son las casi coincidencias —entradas que coinciden casi hasta el final y fallan en el último paso— las que arrastran al motor por la búsqueda exponencial completa. Los atacantes lo saben, y por eso una carga ReDoS se fabrica para casi coincidir: una tanda larga de aes y luego el único carácter que la echa a perder al final.

Las formas peligrosas, a simple vista

No hace falta trazar el motor cada vez: los patrones peligrosos tienen un puñado de siluetas reconocibles. Pero conviene ser preciso sobre cuán peligrosos, porque bajo la etiqueta «ReDoS» se meten dos curvas de coste muy distintas, y solo una es la bomba de verdad.

Las formas exponenciales, las bombas de verdad. Son aquellas en las que el coste se duplica aproximadamente con cada carácter añadido, tal como lo trazamos arriba. La firma es repetición sobre repetición donde ambas capas pueden coincidir con los mismos caracteres, de modo que una sola tanda se puede partir de un número exponencial de maneras:

(a+)+$       (a*)*$       (\w+)*$       ([\w.]+)+@

La alternancia solapada bajo un cuantificador es la misma enfermedad con otra piel: cuando dos ramas pueden coincidir con el mismo texto, cada carácter tiene más de una ruta y el cuantificador las multiplica.

(a|a)*$      (\w|\d)*$

\d es un subconjunto de \w, así que (\w|\d)* tiene dos rutas para cada dígito; contra una cadena larga de dígitos que acaba fallando, eso son 2ⁿ caminos. (Las ramas tienen que solaparse sobre los mismos caracteres. (a|ab)*, cuyas ramas consumen longitudes distintas, es un caso más sutil, normalmente polinómico, no una bomba garantizada.)

Las formas polinómicas: lentas, ocasionalmente explotables. Cuantificadores sin límite adyacentes, o un .* amplio a la caza de algo que no está, no detonan de forma exponencial, pero aun así pueden quemar O(n²) o más y colgarse con entradas lo bastante grandes:

.*.*=        \s*.*\s*$        a.*b.*c

También merecen arreglo, pero son otra categoría de gravedad. Conocer la línea te evita gritar «¡exponencial!» ante cada .*.

Lo perezoso no desactiva nada de esto. «Cambia voraz por perezoso» circula como truco de rendimiento; no lo es. La pereza solo invierte el orden en que el motor prueba los repartos —el más corto primero en vez del más largo— y, en una coincidencia que falla, los visita todos igualmente. (a+?)+$ es exactamente tan exponencial como (a+)+$. No confundas *? con una función de seguridad.

Una salvedad gobierna ambos niveles: una forma peligrosa solo muerde de verdad cuando la coincidencia falla. Que sea explotable depende de que exista una entrada capaz de forzar la búsqueda completa —normalmente un prefijo largo que se repite seguido de un carácter que rompe un ancla o un sufijo obligatorio— y de cuánto pueda alargar esa entrada un atacante. La forma te dice que el riesgo existe; el camino de fallo y la longitud de la entrada te dicen cuán grave es.

Si quieres sentir la diferencia, suéltalas en el probador de regex y deja que su análisis de ReDoS opine: corre en segundo plano y te señala una forma vulnerable. Lo que no debes hacer es pegar una cadena de ataque larga solo para ver cómo se congela la página: la coincidencia corre en el hilo principal del navegador, así que lo único que lograrías es colgar tu propia pestaña para demostrar algo que el analizador ya demostró.

Dónde se esconde de verdad

Nadie escribe (a+)+$ en producción a propósito. El retroceso catastrófico se publica porque se esconde dentro de patrones de aspecto perfectamente razonable, y en concreto dentro de los validadores: las regex que apuntamos a la entrada de usuario no confiable, justo el peor sitio para tenerlo.

Validación de correo y URL. Los validadores de direcciones hechos a mano arrastran una larga lista de CVE de ReDoS reales, y los vulnerables comparten una forma: un grupo repetido cuyo contenido se solapa con la repetición que lo envuelve. Toma una comprobación de la parte local escrita como ^([a-zA-Z0-9]+[._-]?)+@. Tiene pinta de estar bien pensada —«letras y dígitos, un separador opcional, repetido»—. Pero dale una tanda larga de letras sin separador y sin @, y el [._-]? opcional coincide con vacío en cada pasada, colapsando todo a ([a-zA-Z0-9]+)+: la forma exponencial de arriba, solo que disfrazada. (Ojo: el ^([a-zA-Z0-9]+\.)+[a-zA-Z]{2,}$, de aspecto deliberadamente inofensivo, no es este fallo: su clase interna no puede coincidir con el ., y cada repetición externa tiene que consumir un . literal, así que no hay forma de volver a repartir los mismos caracteres. Lo que importa es el solape, no la mera presencia de un + anidado.)

Patrones de espacios repetidos. Aquí conviene ir despacio, porque un trim de aspecto temible suele ser inofensivo. El cotidiano ^\s+|\s+$ no es un riesgo de ReDoS: son dos tandas ancladas simples, sin anidamiento ni solape, así que sigue usándolo. El peligro está en la forma anidada: (\s+)+, (\s*)* o (\s|\t)+ bajo un cuantificador externo, que reintroduce el solape. Como la normalización de espacios tiende a correr sobre todo lo que un usuario envía, una anidada es un blanco de primera, pero no te pongas a borrar trims normales presa del pánico.

Cualquier cosa con (.*,)* o grupos repetidos —analizar una lista separada por comas, una serie de pares clave-valor, atributos HTML repetidos, una ruta con segmentos repetidos—. En cuanto escribas «uno o más de (algo que a su vez contiene uno o más)», párate y comprueba lo único que lo decide: ¿pueden la parte interna y la externa consumir los mismos caracteres? Si cada repetición está clavada a su propio separador, o la entrada no puede crecer, en el peor caso es un coste de rendimiento que conviene medir, no una bomba. Solo es un candidato real a ReDoS cuando el solape existe de verdad y es posible una entrada larga que falle.

El patrón detrás del patrón: las regex con más probabilidades de esconder una bomba de retroceso son exactamente las que corres contra entrada no confiable, porque los validadores son donde los cuantificadores anidados surgen de forma natural. Ese solape entre «forma vulnerable» y «entrada controlada por el atacante» es toda la amenaza ReDoS.

Cómo arreglarlo: reescribir, porque JavaScript no te va a salvar

Algunos motores de regex te dan un interruptor directo para apagar el retroceso. Los grupos atómicos (?>...) le dicen al motor «una vez que hayas coincidido con esto, no lo devuelvas nunca», y los cuantificadores posesivos a++, a*+ hacen lo mismo para un único cuantificador. Apúntalos a la parte ambigua y la búsqueda exponencial queda cerrada en el origen.

Aquí va el límite duro que conviene grabarse: JavaScript no tiene ninguno de los dos. Ni grupos atómicos ni cuantificadores posesivos, a día de hoy. (Java, PCRE, Ruby y .NET los tienen todos; JS es la excepción llamativa.) Así que en JavaScript la única palanca que tienes es reescribir el patrón para que la ambigüedad no exista —quita el solape y no queda nada por lo que retroceder—. Esta es la caja de herramientas, más o menos ordenada según la frecuencia con que es la respuesta:

1. Usa una clase de caracteres negada en vez de .* o .*?. Es el arreglo de mayor valor, y es el que el primer artículo no dejaba de anticipar. [^"]* no puede cruzar una comilla, así que cuando escribes "[^"]*" hay exactamente una manera de coincidir con el contenido: sin tanteo de ida y vuelta. Compara ".*" (demasiado voraz: el .* se come la comilla de cierre y luego tiene que devolverla —un poco de retroceso lineal, no una catástrofe por sí solo) con "[^"]*" (inequívoco, frontera dura). Por sí sola, la ganancia es precisión y corrección; y lo que de verdad importa para este artículo es que una frontera dura no puede formar el tipo de solape que se vuelve exponencial en cuanto anidas la construcción dentro de otro cuantificador. Siempre que puedas nombrar el carácter que termina una tanda, coincide con «cualquier cosa menos ese carácter» en lugar de «cualquier cosa, con pereza».

".*?"    →    "[^"]*"
\w+@.*   →    \w+@[^\s@]+

Ese segundo ejemplo no es una equivalencia a ciegas: \w+@.* y \w+@[^\s@]+ no coinciden con lo mismo. [^\s@]+ acota a propósito la cola a «una parte de dominio sin espacios y sin un segundo @», que suele ser lo que de verdad querías. Elige el conjunto negado según tu intención real, no solo para esquivar el retroceso.

2. Haz las ramas de la alternancia mutuamente excluyentes. Si tus alternativas se solapan, reorganiza para que a cada carácter le coincida exactamente una rama. (\w|\d)* se convierte en \w* a secas (porque \d ya estaba dentro de \w). El solape es el enemigo; elimínalo.

3. Ancla para recortar posiciones de inicio, pero conoce el límite. Añadir ^/$ o un delimitador concreto entre grupos repetidos impide que el motor reintente toda la coincidencia en cada posición de inicio, lo que elimina el factor externo lineal o polinómico. Lo que no hace es desactivar una explosión exponencial interna: (a+)+$ ya está anclado, y esa $ es justo lo que fuerza el fallo exponencial. Anclar ayuda con los casos polinómicos; no es una cura para una bomba de solape anidado.

4. Acota la entrada como defensa en profundidad, no como el arreglo. Un tope de longitud duro en la capa de negocio —rechazar entradas de más de n caracteres antes de que la regex las vea— vale de verdad la pena, y {1,64} en vez de + pone un techo a la profundidad del anidamiento. Pero no confundas un tope con eliminar la vulnerabilidad: {1,64} todavía permite hasta 2⁶⁴ caminos, algo astronómicamente inejecutable. Los topes contienen el radio de la explosión; eliminar el solape es lo que de verdad quita la bomba.

5. Deja de usar una regex. Algunos trabajos —estructuras anidadas, cualquier cosa que se parezca a una gramática de verdad, analizar HTML o JSON— no son lenguajes regulares, y forzar una regex sobre ellos es precisamente así como acabas engendrando estos monstruos. Un bucle a mano sobre la cadena, un String.split con un delimitador de texto (no split(/regex/), que sigue ejecutando una regex) o un analizador de verdad suele ser más simple, más rápido y además inmune a toda esta clase de fallo.

Tras cada reescritura, confirma dos cosas: que sigue coincidiendo con todo lo que debe (las regresiones adoran esconderse en las reescrituras «más seguras») y que ya no dispara la comprobación de ReDoS. Comprobar las dos cosas es cuestión de pegarlas en el probador de regex: pon el patrón viejo y el nuevo lado a lado contra la misma entrada de casi coincidencia.

El ángulo de seguridad: por qué esto es un DoS y no solo un bug

Vale la pena decir sin rodeos por qué el retroceso catastrófico asciende de «molestia de rendimiento» a «vulnerabilidad de seguridad», porque el salto es específico de cómo corren los servidores.

Node.js ejecuta JavaScript en un único hilo. Cuando una regex entra en retroceso catastrófico, ese hilo queda capturado por completo: no cede, no atiende otras peticiones, gira dentro del motor de regex. Así que una sola entrada bien fabricada no solo ralentiza la petición que la trajo; congela ese proceso entero para todos los usuarios a los que sirve. Y aquí está el aguijón: un tiempo de espera de petición puesto con setTimeout no te salva, porque la retrollamada del temporizador solo puede dispararse cuando el bucle de eventos queda libre, y la regex desbocada es precisamente lo que tiene el bucle de eventos secuestrado. Node no puede interrumpir una regex síncrona que ya está corriendo; el hilo capturado sigue capturado hasta que la coincidencia termina por su cuenta, lo cual puede ser prácticamente nunca.

Hasta dónde se extiende esa onda expansiva depende de tu despliegue: un servidor de un solo proceso se apaga del todo, mientras que varios procesos o hilos de trabajo, un tiempo de espera en la pasarela que corta la conexión y la limitación de tasa reducen el radio. Pero la asimetría de fondo sobrevive a todo eso —coste trivial para atacar, coste desproporcionado para absorber—, y por eso ReDoS aparece con tanta regularidad en los informes de CVE contra bibliotecas populares.

Esto también resuelve un enigma que señaló el primer artículo: por qué el mismo patrón peligroso corre al instante bajo ripgrep y cuelga Node. Herramientas como ripgrep (la crate regex de Rust) y el regexp de Go están construidas sobre autómatas finitos, una arquitectura de motor distinta que convierte la coincidencia en un único barrido lineal sin retroceso alguno. Son inmunes al retroceso catastrófico por construcción, a cambio de renunciar a funciones como las retrorreferencias, que necesitan retroceso por naturaleza. La clase de motor sobre la que corres decide si esta amenaza siquiera te aplica. En los motores de retroceso —JavaScript, Python, PCRE, Java— vaya que sí aplica.

Aquí hay un corolario práctico específico de Node. Cuando un patrón no se puede reescribir de forma segura de ninguna manera —o simplemente no te fías de acertar con cada uno a mano— puedes correrlo sobre un motor lineal en vez del integrado. RE2, de Google, es un motor de autómatas finitos con exactamente esa garantía lineal, y el binding de npm re2 es un reemplazo casi directo de RegExp en Node. El precio son las funciones que necesitan retroceso por naturaleza: RE2 no admite ningún tipo de aserción de contexto —ni anticipación ni retrospección— ni retrorreferencias. A cambio, el tiempo de coincidencia crece linealmente con la longitud de la entrada (un patrón más complejo solo significa un factor constante mayor), nunca de forma exponencial, le dé lo que le dé un atacante. Para una regex que tiene que correr contra datos no confiables, suele ser el trato correcto.

Cázalo antes de publicarlo

El mejor momento para encontrar una bomba de retroceso es antes de que llegue a producción, y no tienes que revisar cada patrón a ojo. El probador de regex de este sitio corre un análisis de ReDoS sobre tu patrón de forma asíncrona: pega la regex y comprueba en segundo plano si hay estructura vulnerable. Cuando encuentra un problema te muestra una cadena de ataque concreta —la entrada que reventaría el patrón de verdad—, para que veas el fallo en vez de creerlo a ciegas. Y cuando el análisis no llega a un veredicto definitivo, también te lo dice, con claridad, sin fingir que todo va bien. Todo corre localmente en tu navegador; el patrón nunca sale de la página.

Trátalo como un detector de humo, no como un certificado. Un resultado limpio es buena señal, pero no es una prueba de seguridad, y una prueba de rendimiento de verdad a tu escala real de entrada sigue siendo la última palabra. Lo que te compra la comprobación es la detección barata y temprana: la oportunidad de reconocer ([a-zA-Z0-9]+[._-]?)+@ como la bomba que es antes de que esté custodiando un formulario de login en producción.

Una lista que sí puedes seguir

Cuando una regex se cuelga, o antes de publicar una que toca entrada de usuario, pasa por esto:

1. ¿Se cuelga en cuanto corre, con la CPU clavada? Eso es retroceso catastrófico, no lentitud corriente. No lo optimices por los lados: el patrón es exponencial y hay que reescribirlo.
2. Busca primero las formas exponenciales. (a+)+, (\w+)*, ([\w.]+)+, (a|a)*: repetición sobre repetición, o alternancia solapada, donde ambas capas agarran los mismos caracteres. Estas son las bombas de verdad.
3. Luego las polinómicas. .*.*, \s*.*\s*: cuantificadores sin límite adyacentes. Más lentas de lo que deberían y ocasionalmente explotables, pero no la misma emergencia.
4. No cuentes con lo perezoso. (a+?)+ es tan peligroso como (a+)+; *? cambia el orden de la búsqueda, no su tamaño.
5. Mira con más lupa tus validadores. Los patrones de correo, URL y espacios repetidos son donde se esconde el solape y donde aterriza la entrada no confiable. Confirma que el trim que te preocupa es de verdad anidado ((\s+)+) y no el inofensivo ^\s+|\s+$.
6. Arregla quitando el solape, no parcheando alrededor. Prefiere una clase de caracteres negada ([^"]*) a .*?; haz las ramas excluyentes; suelta la regex por un analizador cuando el trabajo no sea regular. Anclas y topes de entrada ayudan a contener el daño, pero no desactivan una bomba anidada, y JavaScript no tiene grupos atómicos ni cuantificadores posesivos, así que la reescritura es todo el juego. Cuando de verdad no puedas reescribir, córrelo sobre RE2.
7. Verifica que la reescritura sigue coincidiendo y luego vuelve a comprobar ReDoS. El patrón viejo y el nuevo, lado a lado, contra la entrada de casi coincidencia.

El retroceso catastrófico parece un rincón oscuro de las regex hasta que lo ves como el mismo motor de retroceso del primer artículo haciendo exactamente lo que hace siempre, solo que demasiadas veces. Una vez que «come con voracidad, retrocede al atascarte» lo llevas en los huesos, las formas peligrosas se encienden a simple vista y el arreglo es casi siempre el mismo gesto callado: traza la frontera de forma explícita y no le dejes al motor nada que dudar.