ReDoS

El tipo de problema más grave ocurre con las coincidencias de expresiones regulares de retroceso, donde algunos patrones tienen un tiempo de ejecución que es exponencial en la longitud de la cadena de entrada. ^{[ 8 ]} Para cadenas de${\displaystyle n}$personajes, el tiempo de ejecución es${\displaystyle O(2^{n})}$Esto ocurre cuando una expresión regular tiene tres propiedades:

• La expresión regular aplica repetición ( +, *) a una subexpresión;
• La subexpresión puede coincidir con la misma entrada de varias maneras, o bien puede coincidir con una cadena de entrada que sea un prefijo de una coincidencia posible más larga;
• y después de la subexpresión repetida, hay una expresión que coincide con algo con lo 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 ade dos maneras en cada lado de la alternancia.
• En (a+)*$, la repetición se aplica a la subexpresión a+, que puede coincidir con ao 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)*ctiene la misma estructura problemática.

Las tres expresiones regulares anteriores mostrarán un tiempo de ejecución exponencial cuando se apliquen a cadenas de la forma${\displaystyle a...ax}$. Por ejemplo, al intentar compararlos con aaaaaaaaaaaaaaaaaaaaaaaaxun motor de expresiones de retroceso, tardará un tiempo significativamente largo en completarse, y el tiempo de ejecución se duplicará aproximadamente por cada adicional aantes del x.

También es posible tener retroceso, que es de tiempo polinomial.${\displaystyle O(n^{x})}$, en lugar de exponencial. Esto también puede causar problemas para entradas suficientemente largas, aunque se le ha prestado menos atención a este problema ya que una entrada maliciosa debe ser mucho más larga para tener un efecto significativo. Un ejemplo de tal patrón es " a*b?a*c", cuando la entrada es una secuencia arbitrariamente larga de " a"s.

Se han encontrado expresiones regulares denominadas "malvadas" o vulnerables en repositorios de expresiones regulares en línea. Cabe destacar que basta con encontrar una subexpresión vulnerable para atacar la expresión regular completa:

1. RegExLib, id=1757 (validación de correo electrónico) – ver 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}))$
2. Repositorio de expresiones regulares de validación de OWASP , nombre de clase Java: ver la parte roja.^(([a-z])+.)+[A-Z]([a-z])+$

Estos dos ejemplos también son susceptibles a la entrada aaaaaaaaaaaaaaaaaaaaaaaa!.

Si la expresión regular se ve afectada por la entrada del usuario, como en un servicio web que permite a los clientes introducir un patrón de búsqueda, 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 por 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 del usuario o provocar un consumo excesivo de memoria.

Sin embargo, si ya existe una expresión regular vulnerable en el servidor, un atacante podría proporcionar una entrada que desencadene su comportamiento más crítico. 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 usar la misma expresión regular para validar la entrada tanto en el lado del cliente como en el del servidor. Un atacante podría inspeccionar el código del cliente, buscando expresiones regulares maliciosas, y enviar datos manipulados directamente al servidor web para bloquearlo. ^{[ 9 ]}

Si bien algunas bibliotecas de expresiones regulares no cuentan con defensa integrada contra ataques ReDoS, como la biblioteca estándar de C++<regex> , la biblioteca C POSIX <regex.h>^{[ 20 ]} o Boostboost.regex (que utilizan retroceso, lo que conlleva un tiempo exponencial), otras bibliotecas de expresiones regulares están diseñadas para prevenir ataques de denegación de servicio basados ​​en expresiones regulares. Esto se logra mediante autómatas finitos deterministas, que se ejecutan en tiempo lineal en relación con el tamaño de la entrada.

Utilizando la biblioteca RE2 de Google para C++ : ^{[ 21 ]}

import < re2 / re2 . h > ; import std ;using std :: string_view ; using re2 :: RE2 ;constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ; constexpr string_view PATTERN = "^(a+)+$" ;int main ( int argc , char * argv []) { bool isMatch = RE2 :: FullMatch ( TEXT , PATTERN ); std :: println ( "Resultado de la coincidencia: {}" , isMatch ); }

Uso de la regexbiblioteca para Rust : ^{[ 22 ]}

usar regex :: Regex ;const TEXTO : & str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ; PATRÓN constante : & str = r"^(a+)+$" ;fn main () { // Regex::new() devuelve Result<Regex, Error> y debe ser unwrapped match Regex :: new ( PATTERN ) { Ok ( re ) => { let is_match : bool = re . is_match ( TEXT ); println! ( "Resultado de la coincidencia: {}" , is_match ); } Err ( err ) => { eprintln! ( "Error al desempaquetar la expresión regular: {}" , err ); } } }

Los tiempos de espera pueden utilizarse para cancelar tareas de expresiones regulares si tardan demasiado.

Los tiempos de espera están integrados en la biblioteca estándar de .NET , ya que la clase System.Text.RegularExpressions.Regexadmite una propiedad MatchTimeout. ^{[ 23 ]} El siguiente es un ejemplo en C# :

espacio de nombres Wikipedia.Ejemplos ;using System ; using System.Text.RegularExpressions ;public class Example { private const string Text = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ; private const string Pattern = @"^(a+)+$" ;static void Main ( string [] args ) { try { Regex re = new ( Pattern , RegexOptions.None , TimeSpan.FromMilliseconds ( 100 ) ); bool isMatch = re.IsMatch ( Text ); Console.WriteLine ( $"Resultado de la coincidencia: {isMatch}" ) ; } catch ( RegexMatchTimeoutException ex ) { Console.WriteLine ( $ " ¡ La operación de Regex ha expirado! {ex.Message}" ) ; } } }

Las expresiones regulares de compilación trasladan el análisis sintáctico y la validación al tiempo de compilación , eliminando la sobrecarga del tiempo de ejecución . Sin embargo, las expresiones regulares de compilación solo son útiles cuando el patrón se puede proporcionar en tiempo de compilación.

La biblioteca de expresiones regulares en tiempo de compilación de C++ ( ctre ), de Hana Dusíková, proporciona un ctre::match<>functor que realiza el análisis de expresiones regulares en tiempo de compilación. ^{[ 24 ]} Si un patrón en tiempo de compilación provoca que la compilación supere el constexprlímite de pasos de evaluación, la compilación fallará. Se ha propuesto para la biblioteca estándar de C++ , pero aún no se ha incluido. ^{[ 25 ]}

import < ctre.hpp > ; import std ;​​usando std :: string_view ;constexpr string_view TEXT = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ;int main ( int argc , char * argv []) { // ctre::match<> es un tipo ctre::regex_results<> // la lógica de coincidencia se realiza en tiempo de compilación cuando se marca constexpr constexpr bool isMatch = ctre :: match < "^(a+)+$" > ( TEXT ); std :: println ( "Resultado de la coincidencia: {}" , isMatch ); }

El lenguaje de programación D ofrece std.regex.ctRegex, que es una expresión regular en tiempo de compilación. ^{[ 26 ]}

En Rust, las expresiones regulares en tiempo de compilación se pueden lograr mediante algunas bibliotecas de terceros, como lazy_regex , ctreg y regex-automata , que ofrecen varias macros para la validación de expresiones regulares en tiempo de compilación. ^{[ 27 ]}

En C#, existe un System.Text.RegularExpressions.GeneratedRegexAttributeatributo que genera una implementación de una expresión regular mediante la generación de código fuente en un partialmétodo. ^{[ 28 ]}

espacio de nombres Wikipedia.Ejemplos ;using System ; using System.Text.RegularExpressions ;public partial class Example { [GeneratedRegex(@"^(a+)+$")] private static partial Regex Pattern ();const privada string Texto = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!" ;static void Main ( string [] args ) { // La lógica de IsMatch() se ejecuta en tiempo de ejecución bool isMatch = Pattern (). IsMatch ( Text ); Console.WriteLine ( $"Resultado de la coincidencia: {isMatch}" ); } }