# ReDoS

Una denegación de servicio de expresión regular o regular expression denial of service (ReDoS), por sus siglas en inglés. Es un ataque de complejidad algorítmica que produce una denegación de servicio al proporcionar una expresión regular y/o una entrada que tarda mucho tiempo en evaluarse. El ataque aprovecha el hecho de que muchas implementaciones de expresiones regulares tienen una complejidad superlineal en el peor de los casos; en ciertos pares de entradas y expresiones regulares, el tiempo necesario puede crecer polinomial o exponencialmente en relación con el tamaño de la entrada. Por lo tanto, un atacante puede hacer que un programa dedique mucho tiempo proporcionando una expresión regular o una entrada especialmente diseñada. Entonces el programa se ralentizará o dejará de responder.

## Descripción

La coincidencia de expresiones regulares ("regex") se puede realizar construyendo un autómata de estados finitos. Las expresiones regulares se pueden convertir fácilmente en autómatas no deterministas (NFAs), en los que para cada estado y símbolo de entrada, puede haber varios estados siguientes posibles. Una vez construido el autómata existen varias posibilidades:
* El motor puede convertirlo en un autómata determinista de estado finito (DFA) y ejecutar la entrada a través del resultado.
* El motor puede probar una por una todas las rutas posibles hasta que se encuentre una coincidencia o se intenten todas las rutas y fallen ("backtracking o retroceso").
* El motor puede considerar todos los caminos posibles a través del autómata no determinista en paralelo.
* El motor puede convertir el autómata no determinista en uno de estado finito (DFA) de forma perezosa (es decir, sobre la marcha, durante la coincidencia).
De los algoritmos anteriores, los dos primeros son problemáticos. La primera es problemática porque un autómata determinista podría tener hasta $2^{m}$ estados posibles, donde $m$ es el número de estados en el autómata no determinista; por lo tanto, la conversión de NFA a DFA puede llevar un tiempo exponencial. El segundo es problemático porque un autómata no determinista podría tener un número exponencial de caminos de longitud $n$, de modo que caminar a través de una entrada de longitud $n$ también tomará un tiempo exponencial.Los dos últimos algoritmos, sin embargo, no presentan un comportamiento patológico.
Hay que tener en cuenta que para las expresiones regulares no patológicas, los algoritmos problemáticos suelen ser rápidos y, en la práctica, se puede esperar que "compilen" una expresión regular en tiempo O(m) y la igualen en tiempo O(n); en cambio, la simulación de un NFA y el cálculo diferido del DFA tienen una complejidad de O (m$^2$n) en el peor de los casos. La denegación de servicio de expresiones regulares ocurre cuando estas expectativas se aplican a una expresión regular proporcionada por el usuario, y este tipo de expresiones regulares maliciosas desencadenan la complejidad del peor de los casos en el comparador de expresiones regulares.
Si bien los algoritmos de expresiones regulares se pueden escribir de manera eficiente, la mayoría de los motores de expresiones regulares que existen amplían los lenguajes de expresiones regulares con construcciones adicionales que no siempre se pueden resolver de manera eficiente. Estos patrones extendidos hacen necesario utilizar el backtracking en una implementación de expresiones regulares en la mayoría de los lenguajes de programación.

## Ejemplos
### Backtracking exponencial

El tipo de problema más grave ocurre con el backtracking de coincidencia de expresiones regulares, donde algunos patrones tienen un tiempo de ejecución exponencial en la longitud de la cadena de entrada. Para cadenas de textos de $n$ caracteres, el tiempo de ejecución es $O(2^{n})$ . Esto sucede cuando una expresión regular tiene tres propiedades:
* La expresión regular aplica la repetición (+, *) a una subexpresión.
* La subexpresión puede coincidir con la misma entrada de múltiples formas, o puede coincidir con una entrada de una cadena te texto que es un prefijo de la coincidencia más larga posible.
* Y después de la subexpresión repetida, hay una expresión que coincide con algo que la subexpresión no coincide.
La segunda condición se explica mejor con dos ejemplos:
* En (a|a)+$, la repetición se aplica a la subexpresión a|a, que puede coincidir con a de dos maneras en cada lado de la alternancia.
* En (a+)*$, la repetición se aplica a la subexpresión a+, que puede coincidir a o aa, etc.
En ambos ejemplos usamos $ para hacer coincidir el final de la cadena, satisfaciendo la tercera condición. Pero también es posible usar otro carácter para esto. Por ejemplo (a|aa)*c tiene la misma estructura problemática.
Las epresiones regulares anteriores exhibirán un tiempo de ejecución exponencial cuando se apliquen a las cadenas de texto de la forma $a...a!$ . Por ejemplo, si intentas compararlos con aaaaaaaaaaaaaaaaaaaaaaaa! en un motor de expresión de backtracking, tardará mucho tiempo en completarse y el tiempo de ejecución se duplicará aproximadamente por cada a adicional antes de !.
También es posible tener backtracking, que es tiempo polinomial. $O(n^{x})$, en lugar de exponencial. Esto también puede causar problemas durante entradas lo suficientemente largas, aunque se le ha prestado menos atención a este problema, ya que las entradas maliciosas deben durar mucho más tiempo para tener un efecto significativo. Un ejemplo de tal patrón es "a*b?a*x ", cuando la entrada es una secuencia arbitrariamente larga de "a".

### Expresiones regulares vulnerables en repositorios en línea

Se han encontrado expresiones regulares llamadas "malvadas" o vulnerables en repositorios de expresiones regulares en línea. Tenga en cuenta que es suficiente con encontrar una subexpresión vulnerable para atacar la expresión regular completa:
* RegExLib, id=1757 (validación de correo electrónico) - ver la parte roja: ^([a-zA-Z0-9])(([\-.]|[_]+)?([a-zA-Z0-9]+))*(@){1}[a-z0-9]+[.]{1}(([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))$
* Repositorio de expresiones regulares de validación de OWASP - nombre de clase Java - ver la parte roja: ^(([a-z])+.(([a-z])+.[A-Z]([a-z])+$
Estos dos ejemplos también son susceptibles a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

### Ataques

Si la misma expresión regular se ve afectada por la entrada del usuario, como un servicio web que permite a los clientes proporcionar un patrón de búsqueda, entonces un atacante puede inyectar una expresión regular maliciosa para consumir los recursos del servidor. Entonces, en la mayoría de los casos, la denegación de servicio mediante expresiones regulares se puede evitar eliminando la posibilidad de que el usuario ejecute patrones arbitrarios en el servidor. En este caso, las aplicaciones web y las bases de datos son las más vulnerables. Por otro lado, también es posible que una página maliciosa pueda bloquear el navegador web del usuario o hacer que utilice cantidades arbitrarias de memoria.
Sin embargo, si ya existe una expresión regular vulnerable del lado del servidor, entonces un atacante puede proporcionar una entrada que desencadene su peor comportamiento. En este caso, los escáneres de correo electrónico y los sistemas de detección de intrusos también podrían ser vulnerables. Afortunadamente, en la mayoría de los casos, las expresiones regulares problemáticas se pueden reescribir como patrones "no malvados". Por ejemplo, (.*a)+ se puede reescribir como ([^a]*a)+.
En el caso de una aplicación web, el programador puede utilizar la misma expresión regular para validar la entrada tanto en el lado del cliente como en el lado del servidor. Un atacante podría inspeccionar el código del cliente, buscar expresiones regulares malignas y enviar información manipulada directamente al servidor web para bloquearlo.