Para cada expresión 'malvada', ¿existe una alternativa no malvada, o el demonio está en la gramática?

Aparentemente, los ataques ReDos explotan las características de algunas expresiones regulares (de otro modo útiles) ... esencialmente causando una explosión de posibles caminos a través del gráfico definido por la NFA.

¿Es posible evitar tales problemas escribiendo una expresión regular 'no malvada' equivalente? Si no (por lo tanto, la gramática no puede ser manejada en el espacio / tiempo práctico por un NFA), ¿qué enfoques de análisis serían mejores? ¿Por qué?

Depende de si tienes una expresión regular o una expresión regular: las expresiones regulares son malvadas, pero las expresiones regulares son algo bello y nunca te volverán malvado.

Por regexp, me refiero a una expresión regular moderna: es decir, una expresión regular con características modernas adicionales tales como referencias inversas, por ejemplo, una expresión regular compatible con Perl. Esto es más poderoso que una expresión regular clásica de un libro de texto de teoría formal de lenguajes / autómatas, ya que las expresiones regulares clásicas no permiten referencias posteriores, mirar hacia adelante, mirar hacia atrás, etc.

$n$$O(n)$

Esto depende de la implementación del comparador de expresiones regulares. Si tiene una implementación ingenua o deficiente del emparejador, la correspondencia podría llevar un tiempo exponencial; Ciertamente hay algoritmos con esa propiedad. Pero la mejor respuesta a eso es probablemente no cambiar la expresión regular; Probablemente sea mejor elegir un mejor emparejador, si le preocupan los ataques de denegación de servicio.

En comparación, algunas expresiones regulares modernas son inevitablemente malvadas. Si tiene una expresión regular moderna, la coincidencia puede requerir un tiempo exponencial. En particular, las expresiones regulares con referencias inversas pueden reconocer lenguajes NP-hard. En consecuencia, bajo supuestos plausibles, existe una clase de expresiones malvadas en las que la prueba de un partido lleva un tiempo exponencial. Por lo tanto, algunas expresiones regulares modernas son inevitablemente malvadas: no hay una manera factible de encontrar una expresión regular equivalente que no cause una explosión exponencial en el tiempo de ejecución para que coincida.

(Tal equivalente podría existir e incluso podría encontrarse en teoría, pero bajo supuestos plausibles, encontrar la expresión regular equivalente tomará un tiempo exponencial, lo cual no es factible en la práctica. Si tuviera un procedimiento sistemático para encontrar la expresión regular equivalente en tiempo polinómico , entonces podría resolver el problema NP-hard en tiempo polinomial, demostrando que P = NP. No sirve de mucho que exista una expresión regular equivalente si no hay forma de encontrarla en su vida).

Antecedentes y fuentes:

• ¿Qué idiomas reconocen las expresiones regulares compatibles con Perl? y la expresividad de las expresiones regulares modernas proporcionan referencias para justificar que las expresiones regulares modernas pueden reconocer lenguajes NP-hard.

• ¿Cómo simular referencias traseras, lookaheads y lookbehinds en autómatas de estado finito? y cuando una expresión regular no es una expresión regular? Puede ser útil para comprender la diferencia entre expresiones regulares y expresiones regulares.

• Este artículo de Russ Cox tiene una buena explicación de dos formas diferentes de construir un emparejador de expresiones regulares, y explica por qué el tiempo de ejecución si usa el algoritmo adecuado es lineal en la longitud de la cadena de entrada (cuando la expresión regular se mantiene fija y su longitud se trata como una constante). En particular, el algoritmo basado en NFA, también conocido como algoritmo Thompson, tiene un tiempo de ejecución lineal en el peor de los casos. También muestra cómo algunos lenguajes populares tienen implementaciones de expresiones regulares que pueden ser exponenciales en algunas expresiones regulares, y analiza qué aspectos de las expresiones regulares modernas pueden introducir tiempos de ejecución exponenciales.

• En esta publicación, supongo que P! = NP. Más concretamente, cuando me refiero a "supuestos plausibles", me refiero a la hipótesis del tiempo exponencial .

Esta respuesta tendrá una visión más general de esta situación transversal inusual, donde la teoría de la complejidad es aplicable a la ciberseguridad y el ejemplo contiene algunos de los matices / sutilezas importantes que pueden ocurrir en esta área. Esto es esencialmente similar a un "ataque de inyección" en el que ciertas entradas inesperadas causan un comportamiento patológico que bloquea un sistema o lleva un tiempo anormalmente largo.

Wikipedia tiene 15 categorías de ataques de denegación de servicio y este ataque cae en "inundaciones de nivel de aplicación" en esa lista. Otro ejemplo algo similar es un ataque que llena los registros de aplicaciones.

Una solución para los ataques de inyección es "limpiar la entrada". El diseñador de la aplicación puede reevaluar si es necesario compilar expresiones regulares arbitrarias proporcionadas por un usuario potencialmente malicioso. Simplemente quitar expresiones anidadas en la expresión regular o alguna otra limitación similar probablemente sería suficiente para evitar este ataque. Si bien son intrínsecos a una gran cantidad de software moderno, se pueden proporcionar grandes cantidades de funcionalidad sin evaluar las expresiones regulares. El contexto es importante, algunas aplicaciones no requieren tal seguridad.

Otro enfoque para mejorar la tolerancia / resistencia a fallas que es aplicable aquí son los tiempos de espera especificados en diferentes niveles de la pila / jerarquía de software. La idea sería especificar un límite de tiempo / CPU o instrucción en una evaluación de expresión regular "promedio" y finalizar antes si se supera. Se pueden implementar con soluciones personalizadas, pero no mucho software o lenguajes de programación tienen tiempos de espera o marcos integrados para este propósito.

Aquí hay un buen ejemplo del uso de tiempos de espera para mejorar la tolerancia a fallas y muestra un diseño / arquitectura / pov de alto nivel para mitigar tales problemas: Tolerancia a fallas en un sistema distribuido / Netflix de alto volumen . No tiene nada específicamente conectado a expresiones regulares, pero ese es el punto aquí: prácticamente cualquier / toda lógica de nivel de aplicación puede encajar en este marco o algo similar.

Este artículo señala cómo el retroceso en particular puede conducir a una lenta coincidencia de expresiones regulares. Las expresiones regulares tienen muchas características diferentes y uno podría intentar evaluar cuáles conducen al peor de los casos.

Aquí hay una buena encuesta científica sobre este tema en particular con las soluciones de análisis estático propuestas:

• Análisis estático para el tiempo de ejecución exponencial de expresión regular a través de lógica estructural / Rathnayake, Thielecke

  La coincidencia de expresiones regulares con el seguimiento puede tener un tiempo de ejecución exponencial, lo que lleva a un ataque de complejidad algorítmica conocido como REDoS en la literatura de seguridad de sistemas. En este artículo, nos basamos en un análisis estático publicado recientemente que detecta si una expresión regular dada puede tener un tiempo de ejecución exponencial para algunas entradas. Construimos sistemáticamente un análisis más preciso formando poderes y productos de las relaciones de transición y, por lo tanto, reduciendo el problema de REDoS a accesibilidad. La exactitud del análisis se demuestra utilizando un cálculo subestructural de árboles de búsqueda, donde la ramificación del árbol que causa la explosión exponencial se caracteriza como una forma de no linealidad.