Protección de la entrada del usuario de expresiones regulares contra ataques

Soy consciente de la Denegación de servicio de expresión regular (ReDoS). ¿Hay alguna forma razonable de permitir a los usuarios crear expresiones regulares personalizadas y garantizar que no presenten un patrón exponencialmente lento?

El problema con las expresiones regulares no es la expresión regular en sí misma, sino que es el motor de expresión regular que tiene todo tipo de características "convenientes" como retroceder. Por lo tanto, el uso de un motor regex sin estas características evita.

Expresiones regulares el concepto de informática siempre puede coincidir en tiempo lineal después de que se compilan en una máquina de estados finitos. Por lo tanto, un motor de expresiones regulares basado en máquinas de estado no se puede utilizar para ReDoS. Sin embargo, las máquinas de estado necesarias pueden volverse bastante grandes en ejemplos patológicos. Pero limitar la memoria disponible tiende a ser más fácil que limitar el tiempo de cálculo disponible.

El motor RE2 se desarrolló específicamente para tratar expresiones regulares no confiables y se diseñó para la ejecución en tiempo lineal.

Otra alternativa es ensamblar las expresiones regulares usted mismo a partir de una notación simplificada. Por ejemplo, puede permitir que los usuarios usen patrones globales (como *.txt). Luego puede analizarlo de una manera que evite el retroceso, por ejemplo, al no permitir el anidamiento y solo usando cuantificadores codiciosos. Para muchos casos de uso, una notación de patrón simplificada es completamente suficiente.

Analizar una expresión regular para ver si será lenta o no, sin que el análisis se vuelva lento , equivale a resolver el problema de detención. En otras palabras, no es posible encontrar una solución correcta y completa.

Puede, por supuesto, encontrar una solución que es correcto y en completa. Por ejemplo, podría trabajar con una lista blanca restrictiva de características que son seguras de usar (por ejemplo, clases de caracteres sí, repetición no ...). Esto le permitiría pasar muchas expresiones regulares no críticas, rechazar todas las críticas y (erróneamente) rechazar algunas que estén bien, pero que sean demasiado complicadas para demostrar que son seguras automáticamente.

Como autor del analizador para el proyecto Lazarus , diría que no hay formas de comprender para una expresión regular determinada qué recursos consumirá en un texto dado.

Sin gastar los mismos recursos, quiero decir (al menos en el significado de O grande).

Entonces, el mejor enfoque: ejecutar el analizador en un hilo separado y eliminarlo después del tiempo de espera.

Además de las otras respuestas, una solución también puede ser rodar su propia biblioteca de expresiones regulares, que permite la instrumentación de rendimiento durante la ejecución y, por lo tanto, proporciona los medios para matar la ejecución a la mitad si se cumplen algunos criterios.

Del mismo modo, puede ejecutar las expresiones regulares en otro hilo y matar los hilos si tardan demasiado.