Recientemente me di cuenta de los ataques de denegación de servicio de expresión regular y decidí eliminar los llamados patrones de expresiones regulares 'malvados' dondequiera que pudiera encontrarlos en mi código base, o al menos aquellos que se usan en la entrada del usuario. Los ejemplos dados en el enlace OWASP anterior y wikipedia son útiles, pero no hacen un gran trabajo al explicar el problema en términos simples.
Una descripción de las expresiones regulares malignas, de wikipedia :
- la expresión regular aplica repetición ("+", "*") a una subexpresión compleja;
- para la subexpresión repetida, existe una coincidencia que también es un sufijo de otra coincidencia válida.
Con ejemplos, nuevamente de wikipedia :
(a+)+([a-zA-Z]+)*(a|aa)+(a|a?)+(.*a){x}para x> 10
¿Es este un problema que simplemente no tiene una explicación más simple? Estoy buscando algo que facilite evitar este problema al escribir expresiones regulares, o encontrarlas dentro de una base de código existente.
Respuestas:
¿Por qué las expresiones regulares malvadas son un problema?
Porque las computadoras hacen exactamente lo que les dices que hagan, incluso si no es lo que querías decir o es totalmente irrazonable. Si le pide a un motor Regex que demuestre que, para una entrada determinada, existe o no una coincidencia para un patrón determinado, entonces el motor intentará hacerlo sin importar cuántas combinaciones diferentes deban probarse.
Aquí hay un patrón simple inspirado en el primer ejemplo en la publicación del OP:
Dada la entrada:
El motor de expresiones regulares intenta algo como
(abababababababababababab)y se encuentra una coincidencia en el primer intento.Pero luego tiramos la llave inglesa:
El motor lo intentará primero,
(abababababababababababab)pero eso falla debido a ese extraa. Esto provoca un seguimiento catastrófico, porque nuestro patrón(ab)*, en una muestra de buena fe, liberará una de sus capturas ("retrocederá") y dejará que el patrón externo vuelva a intentarlo. Para nuestro motor de expresiones regulares, se parece a esto:El número de combinaciones posibles escala exponencialmente con la longitud de la entrada y, antes de que te des cuenta, el motor de expresiones regulares está consumiendo todos los recursos de tu sistema tratando de resolver esto hasta que, habiendo agotado todas las combinaciones posibles de términos, finalmente se da por vencido y informa "No hay coincidencia". Mientras tanto, su servidor se ha convertido en una pila ardiente de metal fundido.
Cómo detectar expresiones regulares malvadas
De hecho, es muy complicado. Yo mismo he escrito un par, aunque sé cuáles son y, en general, cómo evitarlos. Vea Regex tomando un tiempo sorprendentemente largo . Envolver todo lo que pueda en un grupo atómico puede ayudar a prevenir el problema del retroceso. Básicamente, le dice al motor de expresiones regulares que no vuelva a visitar una expresión determinada: "bloquee lo que haya coincidido en el primer intento". Sin embargo, tenga en cuenta que las expresiones atómicas no evitan el retroceso dentro de la expresión, por
^(?>((ab)*)+)$lo que sigue siendo peligroso, pero^(?>(ab)*)+$seguro (coincidirá(abababababababababababab)y luego se negará a ceder cualquiera de sus caracteres coincidentes, evitando así un retroceso catastrófico).Desafortunadamente, una vez que está escrito, en realidad es muy difícil encontrar inmediatamente o rápidamente una expresión regular problemática. Al final, reconocer una expresión regular incorrecta es como reconocer cualquier otro código incorrecto : se necesita mucho tiempo y experiencia y / o un solo evento catastrófico.
Curiosamente, desde que se escribió esta respuesta por primera vez, un equipo de la Universidad de Texas en Austin publicó un artículo que describe el desarrollo de una herramienta capaz de realizar análisis estáticos de expresiones regulares con el propósito expreso de encontrar estos patrones "malvados". La herramienta fue desarrollada para analizar programas Java, pero sospecho que en los próximos años veremos más herramientas desarrolladas para analizar y detectar patrones problemáticos en JavaScript y otros lenguajes, especialmente a medida que la tasa de ataques ReDoS continúa aumentando .
fuente
Lo que usted llama una expresión regular "malvada" es una expresión regular que exhibe un retroceso catastrófico . La página vinculada (que escribí) explica el concepto en detalle. Básicamente, el retroceso catastrófico ocurre cuando una expresión regular no coincide y diferentes permutaciones de la misma expresión regular pueden encontrar una coincidencia parcial. El motor de expresiones regulares intenta todas esas permutaciones. Si desea revisar su código e inspeccionar sus expresiones regulares, estos son los 3 problemas clave a tener en cuenta:
Las alternativas deben ser mutuamente excluyentes. Si varias alternativas pueden coincidir con el mismo texto, el motor probará ambas si falla el resto de la expresión regular. Si las alternativas están en un grupo que se repite, tiene un retroceso catastrófico. Un ejemplo clásico es
(.|\s)*hacer coincidir cualquier cantidad de texto cuando el tipo de expresión regular no tiene un modo "el punto coincide con los saltos de línea". Si esto es parte de una expresión regular más larga, una cadena de asunto con una serie de espacios lo suficientemente larga (emparejados por ambos.y\s) romperá la expresión regular. La solución es utilizar(.|\n)*para hacer que las alternativas sean mutuamente excluyentes o incluso mejor para ser más específico sobre qué caracteres están realmente permitidos, como[\r\n\t\x20-\x7E]para imprimibles ASCII, pestañas y saltos de línea.Los tokens cuantificados que están en secuencia deben ser mutuamente excluyentes entre sí o ser mutuamente excluyentes lo que se interpone entre ellos. De lo contrario, ambos pueden coincidir con el mismo texto y se probarán todas las combinaciones de los dos cuantificadores cuando el resto de la expresión regular no coincida. Un ejemplo clásico es
a.*?b.*?chacer coincidir 3 cosas con "cualquier cosa" entre ellas. Cuandocno se puede igualar, el primero.*?se expandirá carácter por carácter hasta el final de la línea o archivo. Para cada expansión, la segunda.*?se expandirá carácter por carácter para coincidir con el resto de la línea o archivo. La solución es darse cuenta de que no puede haber "nada" entre ellos. La primera carrera debe detenerse enby la segunda carrera debe detenerse enc. Con personajes únicosa[^b]*+b[^c]*+ces una solución fácil. Dado que ahora nos detenemos en el delimitador, podemos usar cuantificadores posesivos para aumentar aún más el rendimiento.Un grupo que contiene un token con un cuantificador no debe tener un cuantificador propio a menos que el token cuantificado dentro del grupo solo se pueda emparejar con otra cosa que sea mutuamente excluyente con él. Eso asegura que no hay forma de que menos iteraciones del cuantificador externo con más iteraciones del cuantificador interno puedan coincidir con el mismo texto que más iteraciones del cuantificador externo con menos iteraciones del cuantificador interno. Este es el problema ilustrado en la respuesta de JDB.
Mientras escribía mi respuesta, decidí que esto merecía un artículo completo en mi sitio web . Esto ahora también está en línea.
fuente
Lo resumiría como "Una repetición de una repetición". El primer ejemplo que enumeró es bueno, ya que dice "la letra a, una o más veces seguidas. Esto puede volver a suceder una o más veces seguidas".
Lo que debe buscar en este caso es una combinación de cuantificadores, como * y +.
Una cosa algo más sutil a tener en cuenta es la tercera y cuarta. Esos ejemplos contienen una operación OR, en la que ambos lados pueden ser verdaderos. Esto, combinado con un cuantificador de la expresión, puede resultar en MUCHAS coincidencias potenciales dependiendo de la cadena de entrada.
En resumen, estilo TLDR:
Tenga cuidado con cómo se utilizan los cuantificadores en combinación con otros operadores.
fuente
Sorprendentemente, me he encontrado con ReDOS varias veces realizando revisiones de código fuente. Una cosa que recomendaría es usar un tiempo de espera con cualquier motor de expresión regular que esté usando.
Por ejemplo, en C # puedo crear la expresión regular con un
TimeSpanatributo.string pattern = @"^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$"; Regex regexTags = new Regex(pattern, RegexOptions.None, TimeSpan.FromSeconds(1.0)); try { string noTags = regexTags.Replace(description, ""); System.Console.WriteLine(noTags); } catch (RegexMatchTimeoutException ex) { System.Console.WriteLine("RegEx match timeout"); }Esta expresión regular es vulnerable a la denegación de servicio y, sin el tiempo de espera, girará y consumirá recursos. Con el tiempo de espera, lanzará un
RegexMatchTimeoutExceptiondespués del tiempo de espera dado y no provocará el uso de recursos que conduzca a una condición de Denegación de servicio.Querrá experimentar con el valor de tiempo de espera para asegurarse de que funcione para su uso.
fuente
Detectando expresiones regulares malvadas
Reglas de juego
Las expresiones regulares malvadas siempre se deben a la ambigüedad en el NFA correspondiente, que puede visualizar con herramientas como la expresión regular .
A continuación se muestran algunas formas de ambigüedad. No los use en sus expresiones regulares.
(a+)+(también conocido como "altura de estrella> 1"). Esto puede provocar una explosión exponencial. Vea lasafe-regexherramienta de la sub-pila .(a|a)+. Esto puede provocar una explosión exponencial.\d+\d+. Esto puede provocar la explosión de un polinomio.Recursos adicionales
Escribí este artículo sobre expresiones regulares súper lineales. Incluye un montón de referencias a otras investigaciones relacionadas con las expresiones regulares.
fuente
Yo diría que esto está relacionado con el motor de expresiones regulares en uso. Es posible que no siempre pueda evitar este tipo de expresiones regulares, pero si su motor de expresiones regulares está construido correctamente, entonces es un problema menor. Consulte esta serie de blogs para obtener una gran cantidad de información sobre el tema de los motores de expresiones regulares.
Tenga en cuenta la advertencia al final del artículo, en el sentido de que retroceder es un problema NP-Completo. Actualmente no hay forma de procesarlos de manera eficiente y es posible que desee rechazarlos en su entrada.
fuente
a*a*no utiliza referencias inversas. Ahora, el motor de expresiones regulares usa retroceso , que es, quizás, lo que quisiste decir. En cuyo caso, todos los motores modernos utilizan el retroceso. Puede desactivar fácilmente el retroceso a través de(?>...), pero eso a menudo no cambiará el significado de su expresión (y en algunos casos puede eludirse).No creo que puedas reconocer tales expresiones regulares, al menos no todas o no sin limitar restrictivamente su expresividad. Si realmente le importan los ReDoS, trataría de aislarlos y eliminar su procesamiento con un tiempo de espera. También es posible que existan implementaciones de RegEx que le permitan limitar su cantidad máxima de retroceso.
fuente
a*o\*ser "vulnerable".a*no es vulnerable en absoluto. Mientras tanto,a{0,1000}a{0,1000}hay una expresión regular catastrófica esperando que suceda. Inclusoa?a?puede tener resultados desagradables en las condiciones adecuadas.a*b*c*$es seguro, peroa*b*[ac]*$peligroso, porquea*podría ceder caracteres a[ac]*sibestá ausente y la coincidencia inicial falla (paaaaaaaaaaaccccccccccd. Ej .).Hay algunas formas en las que puedo pensar en que podría implementar algunas reglas de simplificación ejecutándolas en pequeñas entradas de prueba o analizando la estructura de la expresión regular.
(a+)+se puede reducir usando algún tipo de regla para reemplazar operadores redundantes(a+)([a-zA-Z]+)*también podría simplificarse con nuestra nueva regla de combinación de redundancia para([a-zA-Z]*)La computadora podría ejecutar pruebas ejecutando las pequeñas subexpresiones de la expresión regular contra secuencias generadas aleatoriamente de los caracteres relevantes o secuencias de caracteres, y ver en qué grupos terminan todos. Para la primera, la computadora es como, oye la expresión regular quiere unos, así que intentémoslo
6aaaxaaq. Luego ve que todas las a, y solo el primer grupom terminan en un grupo, y concluye que no importa cuántas a se pongan, no importará, ya que se+pone todo en el grupo. El segundo es como, oye, la expresión regular quiere un montón de letras, así que intentémoslo con-fg0uj=, y luego ve que nuevamente cada grupo está en un grupo, por lo que se deshace del+al final.Ahora necesitamos una nueva regla para manejar las siguientes: la regla de eliminar opciones irrelevantes.
Con
(a|aa)+, la computadora le echa un vistazo y dice, nos gusta ese gran segundo, pero podemos usar ese primero para llenar más espacios, obtengamos tantos aa como podamos, y veamos si podemos obtener algo más. después de que terminemos. Podría ejecutarlo contra otra cadena de prueba, como `eaaa @ a ~ aa '. para determinar eso.Puede protegerse
(a|a?)+haciendo que la computadora se dé cuenta de que las cadenas que coinciden cona?no son los droides que estamos buscando, porque como siempre puede coincidir en cualquier lugar, decidimos que no nos gustan las cosas como(a?)+y las desechamos.Protegemos
(.*a){x}al hacer que se dé cuenta de que los personajes emparejados poraya habrían sido capturados.*. Luego desechamos esa parte y usamos otra regla para reemplazar los cuantificadores redundantes en(.*){x}.Si bien implementar un sistema como este sería muy complicado, este es un problema complicado y puede ser necesaria una solución complicada. También debe usar técnicas que otras personas hayan mencionado, como permitirle a la expresión regular una cantidad limitada de recursos de ejecución antes de matarla si no termina.
fuente