¿Cómo puedo reconocer una malévola expresión regular?

Hace poco me enteré de los ataques de denegación de servicio de expresión regular y decidí eliminar los llamados patrones de expresiones regex ‘malignas’ siempre que pude encontrarlos en mi base de código, o al menos los que se usan con la entrada del usuario. Los ejemplos proporcionados en el enlace de OWASP arriba y en la wikipedia son útiles, pero no explican el problema en términos simples.

Una descripción de expresiones malignas malvadas, 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 desde wikipedia :

  • (a+)+
  • ([a-zA-Z]+)*
  • (a|aa)+
  • (a|a?)+
  • (.*a){x} para x> 10

¿Es esto un problema que simplemente no tiene una explicación más simple? Estoy buscando algo que haría más fácil evitar este problema al escribir expresiones regulares, o encontrarlos dentro de una base de código existente.

¿Por qué Erex Regexes es un problema?

Porque las computadoras hacen exactamente lo que les dice que hagan, incluso si no es lo que usted quiso decir o si es totalmente irracional. Si le pide a un motor Regex que pruebe que, para alguna entrada dada, existe una coincidencia o no 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 de OP:

 ^((ab)*)+$ 

Dada la entrada:

abababababababababababab

El motor de (abababababababababababab) regulares intenta algo como (abababababababababababab) y se encuentra una coincidencia en el primer bash.

Pero luego lanzamos la llave inglesa en:

ababababababababababab a

El motor probará primero (abababababababababababab) pero eso falla debido a ese extra a . Esto causa un rastreo catastrófico, porque nuestro patrón (ab)* , en una muestra de buena fe, lanzará una de sus capturas (se “revertirá”) y permitirá que el patrón externo intente de nuevo. Para nuestro motor de expresiones regulares, se ve así:

(abababababababababababab) – Nope
(ababababababababababab)(ab) – Nope
(abababababababababab)(abab) – Nope
(abababababababababab)(ab)(ab) – Nope
(ababababababababab)(ababab) – Nope
(ababababababababab)(abab)(ab) – Nope
(ababababababababab)(ab)(abab) – Nope
(ababababababababab)(ab)(ab)(ab) – Nope
(abababababababab)(abababab) – Nope
(abababababababab)(ababab)(ab) – Nope
(abababababababab)(abab)(abab) – Nope
(abababababababab)(abab)(ab)(ab) – Nope
(abababababababab)(ab)(ababab) – Nope
(abababababababab)(ab)(abab)(ab) – Nope
(abababababababab)(ab)(ab)(abab) – Nope
(abababababababab)(ab)(ab)(ab)(ab) – Nope
(ababababababab)(ababababab) – Nope
(ababababababab)(abababab)(ab) – Nope
(ababababababab)(ababab)(abab) – Nope
(ababababababab)(ababab)(ab)(ab) – Nope
(ababababababab)(abab)(abab)(ab) – Nope
(ababababababab)(abab)(ab)(abab) – Nope
(ababababababab)(abab)(ab)(ab)(ab) – Nope
(ababababababab)(ab)(abababab) – Nope
(ababababababab)(ab)(ababab)(ab) – Nope
(ababababababab)(ab)(abab)(abab) – Nope
(ababababababab)(ab)(abab)(ab)(ab) – Nope
(ababababababab)(ab)(ab)(ababab) – Nope
(ababababababab)(ab)(ab)(abab)(ab) – Nope
(ababababababab)(ab)(ab)(ab)(abab) – Nope
(ababababababab)(ab)(ab)(ab)(ab)(ab) – Nope

(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abababab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab)(ab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(abab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab)(ab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ababab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab)(ab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(abab) – Nope
(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab)(ab) – Nope

El número de combinaciones posibles aumenta exponencialmente con la longitud de la entrada y, antes de que te des cuenta, el motor regex 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, tu servidor se ha convertido en una stack ardiente de metal fundido. (Curiosamente, esto es básicamente cómo funciona una contraseña brute-forcer, ya que se trata de la misma clase de problemas ).

Cómo detectar Evil Regexes

En realidad es muy complicado. He escrito un par, aunque sé cuáles son y, en general, cómo evitarlos. Ver Regex tomando sorprendentemente mucho tiempo . Envolver todo lo que pueda en un grupo atómico puede ayudar a prevenir el problema de retroceso. Básicamente le dice al motor de expresiones regulares que no vuelva a visitar una expresión determinada: “bloquea lo que corresponda en el primer bash”. Sin embargo, tenga en cuenta que las expresiones atómicas no impiden el retroceso dentro de la expresión, por lo que ^(?>((ab)*)+)$ sigue siendo peligroso, pero ^(?>(ab)*)+$ es seguro ( combinará (abababababababababababab) y luego se negará a renunciar a ninguno de sus caracteres coincidentes, lo que evitará retrocesos catastróficos).

Desafortunadamente, una vez que está escrito, en realidad es muy difícil encontrar de inmediato o rápidamente un problema de expresión regular. Al final, reconocer una mala expresión regular es como reconocer cualquier otro código incorrecto : lleva mucho tiempo y experiencia y / o un único evento catastrófico.


Curiosamente, desde que se escribió esta respuesta, un equipo de la Universidad de Texas en Austin publicó un documento 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 los progtwigs de Java, pero sospecho que en los próximos años veremos más herramientas desarrolladas en torno a analizar y detectar patrones problemáticos en JavaScript y en otros idiomas, especialmente a medida que la tasa de ataques ReDoS continúe aumentando .

Detección estática de vulnerabilidades DoS en progtwigs que usan expresiones regulares
Valentin Wüstholz, Oswaldo Olivo, Marijn JH Heule e Isil Dillig
La Universidad de Texas en Austin

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 también puede ocurrir una o más veces seguidas”.

Lo que hay que buscar en este caso es la combinación de los cuantificadores, como * y +.

Algo más sutil a tener en cuenta es el tercero y el cuarto. Esos ejemplos contienen una operación OR, en la cual ambos lados pueden ser verdaderos. Esto combinado con un cuantificador de la expresión puede dar como resultado MUCHAS coincidencias potenciales dependiendo de la cadena de entrada.

Para resumir, estilo TLDR:

Tenga cuidado de cómo se usan los cuantificadores en combinación con otros operadores.

Lo que usted llama una expresión regular “malvada” es una expresión regular que exhibe un retroceso catastrófico . La página enlazada (que escribí) explica el concepto en detalle. Básicamente, el retroceso catastrófico ocurre cuando una expresión regular no coincide y las diferentes permutaciones de la misma expresión regular pueden encontrar una coincidencia parcial. El motor de expresiones regulares luego prueba todas esas permutaciones. Si desea revisar su código e inspeccionar sus expresiones regulares, estas son las 3 cuestiones clave a tener en cuenta:

  1. Las alternativas deben ser mutuamente excluyentes. Si múltiples alternativas pueden coincidir con el mismo texto, el motor probará ambas si falla el rest de la expresión regular. Si las alternativas están en un grupo que se repite, usted tiene un retroceso catastrófico. Un ejemplo clásico es (.|\s)* para hacer coincidir cualquier cantidad de texto cuando el sabor de la expresión regular no tiene el modo “punto coincide con los saltos de línea”. Si esto forma parte de una expresión regular más larga, una cadena de asunto con una cantidad de espacios suficientemente larga (que coincida con ambos y con \s ) romperá la expresión regular. La solución es usar (.|\n)* para que las alternativas sean mutuamente exclusivas o incluso mejores para ser más específicos sobre qué caracteres están realmente permitidos, como [\r\n\t\x20-\x7E] para los imprimibles ASCII , tabs y saltos de línea.

  2. Los tokens cuantificados que están en secuencia deben ser mutuamente excluyentes entre sí o ser mutuamente excluyentes de 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 rest de la expresión regular no coincida. Un ejemplo clásico es a.*?b.*?c para unir 3 cosas con “cualquier cosa” entre ellas. Cuando c no puede coincidir con el primero .*? expandirá carácter por carácter hasta el final de la línea o archivo. Para cada expansión, ¿el segundo .*? se expandirá carácter por carácter para que coincida con el rest de la línea o archivo. La solución es darse cuenta de que no se puede tener “nada” entre ellos. La primera ejecución debe detenerse en b y la segunda ejecución debe detenerse en c . Con caracteres simples a[^b]*+b[^c]*+c es una solución fácil. Como ahora nos detenemos en el delimitador, podemos usar cuantificadores posesivos para boost aún más el rendimiento.

  3. 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 algo que sea mutuamente exclusivo 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.

No creo que puedas reconocer tales expresiones regulares, al menos no todas ellas o no sin limitar restrictivamente su expresividad. Si realmente te importan los ReDoS, trataré de guardarlos en la arena y matar su procesamiento con un tiempo de espera excedido. También podría ser posible que existan implementaciones RegEx que le permitan limitar su cantidad máxima de rastreo.

Sorprendentemente me he encontrado con ReDOS bastantes veces realizando revisiones de código fuente. Una cosa que recomendaría es utilizar un tiempo de espera con cualquier motor de expresión regular que esté utilizando.

Por ejemplo, en C # puedo crear la expresión regular con un atributo TimeSpan .

 string pattern = @"^<([az]+)([^<]+)*(?:>(.*)<\/\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á una RegexMatchTimeoutException después del tiempo de espera dado y no causará el uso de recursos que conducen 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.

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 se construye correctamente, entonces no es un problema. 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 en la parte inferior del artículo, en ese retroceso es un problema NP-Complete. Actualmente no hay forma de procesarlos de manera eficiente, y es posible que desee deshabilitarlos en su entrada.

Detectando expresiones malignas malvadas

Pruebe el proyecto RegexStaticAnalysis de Nicolaas Weideman.

Reglas de juego

Las expresiones negativas malvadas siempre se deben a la ambigüedad en el NFA correspondiente, que se puede visualizar con herramientas como regexper .

Aquí hay algunas formas de ambigüedad. No los uses en tus expresiones regulares.

  1. Los cuantificadores de anidamiento como (a+)+ (también conocido como “altura de estrella> 1”). Esto puede causar una explosión exponencial. Ver la herramienta safe-regex substack.
  2. Disyunciones superpuestas cuantificadas como (a|a)+ . Esto puede causar una explosión exponencial.
  3. Evite las adyacencias superpuestas cuantificadas como \d+\d+ . Esto puede causar explosión polinomial.

Hay algunas maneras en que puedo pensar 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 utilizando algún tipo de regla para reemplazar operadores redundantes por solo (a+)
  • ([a-zA-Z]+)* también podría simplificarse con nuestra nueva regla de combinación de redundancia a ([a-zA-Z]*)

La computadora podría ejecutar pruebas ejecutando las subexpresiones pequeñas de la expresión regular contra secuencias generadas aleatoriamente de los personajes o secuencias de caracteres relevantes, y viendo en qué grupos terminan. Para la primera, la computadora es como, hey la expresión regular quiere a’s, entonces 6aaaxaaq con 6aaaxaaq . Luego ve que todos los a’s, y solo el primer grupom terminan en un grupo, y concluye que no importa cuántas A’s se pongan, no importará, ya que + obtiene todo en el grupo. El segundo, es como, hey, la expresión regular quiere un montón de letras, así que intentemos con -fg0uj= , y luego ve que cada grupo está todo en un grupo, por lo que se deshace del + al final .

Ahora necesitamos una nueva regla para manejar las siguientes: la regla eliminar-opciones irrelevantes.

  • Con (a|aa)+ , la computadora lo mira y es como, nos gusta ese gran segundo, pero podemos usar ese primero para llenar más huecos, obtener ans aa’s como podamos, y ver si podemos obtener algo más después de que hayamos terminado. Podría ejecutarlo contra otra cadena de prueba, como `eaaa @ a ~ aa. ‘ para determinar eso.

  • Puede protegerse de (a|a?)+ Haciendo que la computadora se dé cuenta de que las cuerdas coinciden con a? no son los droides que estamos buscando, porque como siempre pueden coincidir en cualquier lugar, decidimos que no nos gustan las cosas como (a?)+ , y lo tiramos.

  • Protegemos de (.*a){x} al hacer que se dé cuenta de que los caracteres con a coincidencia ya habrían sido capturados por .* . Luego descartamos 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 han mencionado, como permitirle a la expresión regular cierta cantidad limitada de recursos de ejecución antes de matarla si no termina.