Denegación de servicio mediante expresiones regulares (ReDoS) y retroceso catastrófico

Las expresiones regulares son increíblemente poderosas, pero sería difícil encontrar a alguien que crea que son muy intuitivas. Claro, está ese desarrollador que conoces que es excelente en esto, pero la mayoría de los desarrolladores sabe lo suficiente como para meterse en problemas. Por desgracia, el nivel de riesgo relacionado con las expresiones regulares y la seguridad es bastante alto. No entender bien las expresiones regulares puede facilitar que los atacantes dejen tu sitio fuera de servicio. Tomemos la siguiente expresión regular como ejemplo:

regex = /A(B|C+)+D/

Si la desglosamos, esto es lo que hace la expresión regular:

• A La cadena debe comenzar con la letra ‘A’

• (B|C+)+ A continuación, la cadena debe incluir después de la letra A la letra ‘B’ o una o más apariciones de la letra ‘C’ (el + coincide una o más veces). El + al final de esta sección indica que podemos buscar una o más coincidencias de esta sección.

• D Por último, verificamos que esta sección de la cadena termine con una ‘D’.

La expresión coincidiría con entradas como las siguientes:

ABBD
ABCCCCD
ABCBCCCD
ACCCCCD

Por lo general, un motor de expresiones regulares encuentra una coincidencia en poco tiempo. Por ejemplo, veamos qué ocurre cuando la probamos con la siguiente cadena de 30 caracteres: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD”.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCD")'
0.04s user 0.01s system 95% cpu 0.052 total

Como era de esperarse, la cadena coincide y lo hace rápidamente. Todo el proceso tarda alrededor de 52 ms (en una MacBook Air). Ahora veamos qué ocurre cuando probamos otra cadena de 30 caracteres. Esta vez, en lugar de proporcionar una cadena válida, proporcionaremos una no válida, reemplazando la “D” final por una “X”: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
1.79s user 0.02s system 99% cpu 1.812 total

De pronto, completar la prueba tarda casi dos segundos: ¡más de diez veces lo que tardó probar una cadena válida! La enorme diferencia se debe a la forma en que se evalúan las expresiones regulares. En pocas palabras, no les gusta darse por vencidas.

Cómo funcionan los motores de expresiones regulares

Los motores de expresiones regulares varían, pero la mayoría funciona de manera muy similar. El motor buscará la primera forma posible de aceptar el carácter actual y luego pasará al siguiente. Si no logra encontrar una coincidencia para el siguiente carácter, retrocederá para ver si había otra forma de procesar el carácter anterior. Si avanza demasiado por un camino sin salida y al final descubre que la cadena no coincide, y si muchos caracteres tienen varias rutas válidas en la expresión regular, la cantidad de pasos de retroceso puede ser muy grande. Esto da lugar a lo que se conoce como retroceso catastrófico. Veamos cómo nuestra expresión llega a este problema con una cadena más corta: “ACCCX”. Aunque parece bastante sencillo, el motor aún tiene cuatro formas distintas de hacer coincidir esas tres C:

1. CCC

2. CC+C

3. C+CC

4. C+C+C.

El motor debe probar cada una de esas combinaciones para ver si alguna podría coincidir con la expresión. Si lo combinamos con los demás pasos que debe ejecutar el motor, podemos usar el depurador RegEx 101 para ver que debe realizar un total de 38 pasos antes de determinar que la cadena no coincide. A partir de ahí, la cantidad de pasos que el motor necesita para validar una cadena sigue aumentando.

Cuando la cadena contiene 14 C, el motor debe realizar más de 65,000 pasos solo para determinar si es válida. Ahora imagina este proceso aplicado a nuestra cadena original: “ACCCCCCCCCCCCCCCCCCCCCCCCCCCCX”. Puedes ver cómo este retroceso puede salirse de control muy rápidamente. La siguiente captura de pantalla muestra solo una pequeña parte del trabajo que realizó el motor, según el informe del depurador RegEx101.

Al considerar cómo evalúa el motor una expresión regular, queda más claro por qué aumenta tanto el tiempo necesario para procesar una expresión no válida: existe una relación exponencial entre la longitud de la cadena y la cantidad de rutas que el motor debe evaluar. Si agregamos solo un carácter más a nuestra secuencia no válida, el tiempo de evaluación casi se duplica.

$ time node -e '/A(B|C+)+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
3.51s user 0.06s system 95% cpu 3.732 total

Node y ReDoS

Los atacantes pueden aprovechar la complejidad del análisis de expresiones regulares al pasar una cadena larga y compleja que haga que el motor tarde demasiado en evaluarla. Esto da lugar a lo que se conoce como un ataque de denegación de servicio mediante expresiones regulares (ReDoS).

Eso no es ideal en ningún entorno, pero es aún peor en entornos JavaScript, incluido Node. Como explicamos cuando hablamos de ataques de temporización en una publicación anterior, Node.js (y JavaScript en general) se basa en eventos.

Esto significa que, si una solicitud ReDoS exitosa ocupa un hilo, bloqueará todo el bucle de eventos y la aplicación no podrá realizar ningún otro procesamiento.

Un ejemplo del mundo real

Veamos un ejemplo reciente del mundo real que se encontró en la popular moment biblioteca. moment se usa para analizar, validar, manipular y dar formato a fechas. Con esta herramienta, puedes especificar el formato de la fecha de salida mediante el método format():

moment().format('MMM Do YY');

//example output: Nov 22nd 16

Cuando defines el formato, moment usa una expresión regular para verificarlo. En versiones de moment anteriores a la 2.15.2, la expresión regular se ve así:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/;

La clave aquí es la parte (\[[^\[\]]*\]|\s+)+ de la expresión. Cabe destacar que \s+ busca la presencia de uno o más espacios. Sin embargo, el + justo después de ese grupo también significa que el grupo entre paréntesis puede aparecer una o más veces. Esto implica que, si el formato contiene muchos espacios, el motor de expresiones regulares puede intentar agrupar estos caracteres de muchas formas distintas para encontrar una coincidencia. Puede agruparlos todos juntos como un solo grupo, separarlos en grupos individuales o elegir cualquier opción intermedia. Como resultado, evaluar una cadena que casi es válida puede tardar mucho tiempo.

Considera este ejemplo que publicamos cuando encontramos la vulnerabilidad:

var m = require("moment");
m.locale("be");
m().format("D                               MMN MMMM");
// Normal date format, other than the 31 spaces included in the string

En este caso, pasamos una cadena de 40 caracteres con numerosos espacios. Al ejecutarla en una laptop estándar, vimos que la expresión bloqueaba el bucle de eventos durante unos 20 segundos.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s+)+MMMM?/.test("D                               MMN MMMM");'
21.24s user 0.14s system 96% cpu 22.079 total

Después de que divulgamos la vulnerabilidad a moment, el autor preparó una solución (puedes probarla ahora para ver si el parche se aplica en tu caso) que elimina el operador + innecesario de los paréntesis:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/;

Al hacerlo, eliminas los dos grupos de coincidencia distintos que podían incluir desde uno hasta todos los espacios. Como el operador + ya no aparece después de s, solo puede coincidir con un espacio a la vez. Si vuelves a probar la cadena con la nueva expresión regular, el motor tarda apenas unos milisegundos en determinar que no hay coincidencia.

$ time node -e '/D[oD]?(\[[^\[\]]*\]|\s)+MMMM?/.test("D                               MMN MMMM");'
0.05s user 0.02s system 53% cpu 0.135 total

Cómo evitar el retroceso catastrófico

Para evitar el retroceso catastrófico, debes prestar atención cada vez que uses los operadores ‘+’ o ‘*’ cerca uno del otro. Si lo haces, es probable que terminen en un tira y afloja que provoque un retroceso catastrófico. Asegúrate de que ambos operadores sean realmente necesarios. También puedes considerar reemplazar uno de ellos por un conjunto limitado. Si recuerdas la vulnerabilidad ReDoS en moment, la corregimos eliminando uno de los operadores ‘+’. También podríamos haber reemplazado uno por un rango para limitar la cantidad de espacios permitidos en una cadena válida:

var MONTHS_IN_FORMAT = /D[oD]?(\[[^\[\]]*\]|\s+){0,10}MMMM?/;

El análisis de expresiones regulares es bastante ingenuo, pero algunos lenguajes han incorporado funciones avanzadas que pueden ayudar a evitar el retroceso catastrófico. Por ejemplo, consideremos la expresión simplificada con la que comenzamos:

regex = /A(B|C+)+D/

Grupos atómicos

Como explicamos, la expresión puede provocar un retroceso catastrófico. El analizador de expresiones regulares compatible con Node.js no tiene una función nativa que podamos usar para eliminar el problema. En algunos otros lenguajes, sí existe. Tomemos Ruby como ejemplo. Ruby admite algo llamado grupos atómicos. Los grupos atómicos permiten indicarle al analizador de expresiones regulares que no retroceda cuando un grupo haya coincidido. Para hacerlo, se agrega ?> antes del grupo, así:

/A(?>B|C+)+D/

Al agregar ?> al grupo que busca una cantidad de “C”, lo convertimos en un grupo atómico. Antes, el analizador de expresiones regulares debía considerar dos operadores en conflicto. La “C” dentro del grupo puede coincidir cualquier cantidad de veces, o el grupo en sí puede coincidir cualquier cantidad de veces. Por eso, si se pasa una expresión no válida que contiene muchas “C”, el analizador queda atrapado en una batalla entre los dos grupos y vuelve a intentar una y otra vez encontrar alguna combinación mágica que haga válida la expresión.

Sin embargo, al aplicar la agrupación atómica, el analizador fija la coincidencia de ese grupo. En este caso, coincidirá con la cantidad de “C” que haya. Si la expresión no es válida, no podrá retroceder sobre ese grupo: a partir de ese momento, queda fijado. Al no tener que distribuir las “C” entre los dos posibles operadores de coincidencia, una expresión no válida se detectará muy rápidamente y se evitará el retroceso catastrófico.

LookAhead

Aunque JavaScript no admite grupos atómicos, sí admite LookAhead, que puede lograr el mismo efecto general que la agrupación atómica.

A(?=(B|C+))\1+D

En este caso, usamos ?= para especificar un LookAhead. Esto significa que la expresión regular coincidirá con ese grupo solo si va seguido inmediatamente del siguiente grupo. Al usar \1, capturamos el grupo coincidente y, en la práctica, creamos un grupo atómico. En este punto, el analizador tratará esta coincidencia como si fuera un grupo atómico y evitará cualquier retroceso catastrófico.

Si ahora probamos nuestra cadena con la expresión usando LookAhead, veremos que el tiempo para determinar que la cadena no es válida se reduce drásticamente (de 1.8 segundos sin LookAhead a 94 ms con esta función):

$ time node -e '/A(?=(B|C+))\1+D/.test("ACCCCCCCCCCCCCCCCCCCCCCCCCCCCCX")'
0.05s user 0.02s system 51% cpu 0.094 total

La desventaja es la complejidad. Evitas el retroceso catastrófico, pero agregas complejidad a la expresión, lo que no solo dificulta que otras personas de tu equipo la entiendan, sino que también facilita cometer errores. Si puedes identificar la combinación de operadores que podría provocar retrocesos (en este caso, los dos +), quizá sea mejor rehacer la expresión por completo para que sea más clara y fácil de leer.

Resumen

Los ataques ReDoS pueden paralizar una aplicación. Esto es especialmente cierto en el mundo de Node.js, donde el bucle de eventos amplifica el impacto del retroceso catastrófico.

Para prevenir vulnerabilidades ReDoS, debes monitorear tus expresiones regulares y probar tus dependencias para detectar vulnerabilidades ReDoS.

Se han hecho algunos intentos por crear herramientas que detecten automáticamente las expresiones vulnerables a ataques ReDoS (la más conocida es safe-regex), pero incluso en pruebas limitadas encontramos varios falsos positivos, así como algunas expresiones que se consideraron seguras cuando no lo eran.

Probar tus dependencias es más sencillo: eso es algo que Snyk puede hacer por ti.

En cualquier caso, vale la pena experimentar. Usar una herramienta como el depurador de RegEx101 es una excelente manera de probar distintas expresiones y entender mejor los pasos que seguirá el analizador de expresiones regulares al intentar encontrar una coincidencia.

Quién sabe: si dedicas suficiente tiempo a experimentar, quizá algún día tú seas quien llegue a salvar el día gracias a tus profundos conocimientos sobre expresiones regulares.