Una denegación de servicio de expresión regular ( ReDoS ) [1] 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 [2] 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 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. [3] [4]
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 (NFA), 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:
De los algoritmos anteriores, los dos primeros son problemáticos. La primera es problemática porque un autómata determinista podría tener hasta estados donde 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 , de modo que recorrer una entrada de longitud también tomará un tiempo exponencial. [7] Los dos últimos algoritmos, sin embargo, no exhiben un comportamiento patológico.
Tenga en cuenta que para 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. [a] La denegación de servicio de expresiones regulares ocurre cuando estas expectativas se aplican a una expresión regular proporcionada por el usuario, y las expresiones regulares maliciosas proporcionadas por el usuario desencadenan la complejidad del peor de los casos del 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 esencialmente obligan a la implementación de expresiones regulares en la mayoría de los lenguajes de programación a utilizar el retroceso.
El tipo de problema más grave ocurre con el retroceso de coincidencias de expresiones regulares, donde algunos patrones tienen un tiempo de ejecución exponencial en la longitud de la cadena de entrada. [8] Para cadenas de caracteres, el tiempo de ejecución es . Esto sucede cuando una expresión regular tiene tres propiedades:
+, *) a una subexpresión;La segunda condición se explica mejor con dos ejemplos:
(a|a)+$, la repetición se aplica a la subexpresión a|a, que puede coincidir ade dos maneras a cada lado de la alternancia.(a+)*$, la repetición se aplica a la subexpresión a+, que puede coincidir acon o aa, etc.En ambos ejemplos utilizamos $para hacer coincidir el final de la cadena, cumpliendo la tercera condición, pero también es posible usar otro carácter para esto. Por ejemplo (a|aa)*ctiene la misma estructura problemática.
Las tres expresiones regulares anteriores exhibirán un tiempo de ejecución exponencial cuando se apliquen a cadenas de la forma . Por ejemplo, si intenta compararlos con un motor de expresión de retroceso, tardará mucho en completarse y el tiempo de ejecución se duplicará aproximadamente para cada archivo adicional antes del archivo .aaaaaaaaaaaaaaaaaaaaaaaa!a!
También es posible retroceder, que es en tiempo polinómico , en lugar de exponencial. Esto también puede causar problemas durante entradas de tiempo suficiente, aunque se 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 " ", cuando la entrada es una secuencia arbitrariamente larga de " ".a*b?a*xa
Se han encontrado expresiones regulares llamadas "malvadas" o vulnerables en repositorios de expresiones regulares en línea. Tenga en cuenta que es suficiente encontrar una subexpresión vulnerable para atacar la expresión regular completa:
^([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}))$^(([a-z])+.)+[A-Z]([a-z])+$Estos dos ejemplos también son susceptibles a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.
Si la propia 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. Por lo tanto, 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 principales aplicaciones vulnerables. Alternativamente, una página maliciosa podría bloquear el navegador web del usuario o hacer que utilice cantidades arbitrarias de memoria.
Sin embargo, si ya existe una expresión regular vulnerable en el 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 intrusiones también podrían ser vulnerables.
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 cliente como en el servidor del sistema. 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. [9]
ReDoS se puede mitigar sin cambios en el motor de expresiones regulares, simplemente estableciendo un límite de tiempo para la ejecución de expresiones regulares cuando se trata de entradas que no son de confianza. [10]
ReDoS se puede evitar por completo utilizando una implementación de expresión regular no vulnerable. Después de que un PCRE ReDoS derribara el firewall de aplicaciones web (WAF) de CloudFlare en 2019, la compañía reescribió su WAF para usar la biblioteca de expresiones regulares Rust sin retroceso, utilizando un algoritmo similar a RE2 . [11] [12]
Las expresiones regulares vulnerables pueden detectarse mediante programación mediante un linter . [13] Los métodos van desde el análisis estático puro [14] [15] hasta la fuzzing . [16] 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 en ([^a]*a)+. La coincidencia posesiva y la agrupación atómica , que desactivan el retroceso de partes de la expresión, [17] también se pueden utilizar para "pacificar" las partes vulnerables. [18] [19]
{{cite web}}: Enlace externo en |author=Cuando utilice System.Text.RegularExpressions para procesar entradas que no sean de confianza, pase un tiempo de espera. Un usuario malintencionado puede proporcionar información a RegularExpressions, provocando un ataque de denegación de servicio. Las API del marco ASP.NET Core que usan RegularExpressions pasan un tiempo de espera.