regex patológico que explota (tiempo y memoria)?

¿Qué es una regex patológica que explota muchos analizadores (ambos en el tiempo & de memoria)? y qué analizadores sintácticos? Los puntos de bonificación son los más básicos y estándar de la expresión regular, y es más probable que un usuario no malintencionado pueda encontrarlos inocentemente. Siéntase libre de publicar datos de tiempo y memoria reales, y la versión del analizador.regex patológico que explota (tiempo y memoria)?

(me parece recordar que las afirmaciones excesiva de búsqueda hacia atrás o (EDIT:) dar marcha atrás en Perl se dice que hacer esto, o al menos solían ser cualquier otra cosa.?)

Fuente

2011-03-15 smci

Su pensamiento de retroceder, casi cualquier motor de expresiones regulares basado en NFA puede ser engañado en un retroceso casi infinito si puede controlar tanto el sujeto como el patrón. Los motores basados en DFA no necesitan hacer un backtracking, por lo que no sufren esa trampa. La respuesta a las siguientes preguntas es "Debido a que un DFA generalmente no puede soportar las características que puede tener un NFA". –

Adaptado del primer ejemplo en el artículo de Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...):

perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))'

que tiene más de 40 segundos en mi sistema. Luego haga $n++ para aumentar la diversión de forma exponencial ...

Fuente

2011-03-15 03:51:36

Es extraño que cada motor regex no optimice esto. Reducir 'a? A?' A 'a {, 2}' es tan básico que se enseña en clases. –

Ejemplo sintético pero ensayo útil con comparaciones entre idiomas. – smci

De Russ Cox excelente article: $ perl -e '("a" x 100000) =~ /^(ab?)*$/;'. Esto aparentemente causa una segfault. Hay más en el artículo.

Fuente

2011-03-15 03:22:57 MAK

Python y GNU grep no tienen problemas con esto. 're.match (r '^ (ab?) * $', 'a' * 10000000)' –

Esto no causó ningún problema con mi instalación de perl 5.10.1, y parece funcionar bien en el teclado, que es 5.8 http: //codepad.org/hFlqUWk8 –

@Eric Strom: Creo que el autor estaba probando contra Perl 5.8.7. – MAK

Siempre lo uso de expresiones regulares para que coincida con cuerdas dentro de PHP o JavaScript código fuente en PHP:

~'(\\.|[^'])*'|"(\\.|[^"])*"~s

Y casi siempre fallan en una cadena muy larga (aproximadamente 50000 caracteres de largo lo harán).

Fuente

2011-03-15 03:30:21 Thai

Esto usa ~ delimitador porque contiene ambos tipos de comillas; Intenté convertirlo en una expresión regular de Python para probarlo, pero el escape me vuelve loco. ¿Alguien puede convertirlo? – smci

Lo convertí principalmente usando [este enfoque debido a Tim Peters] (http://stackoverflow.com/questions/1472047/regex-for-triple-quote) excepto por el modificador s (¿el punto coincide con cada carácter?) ... Sospecho que eso empeora las cosas. – smci

[Este póster] (http://stackoverflow.com/questions/7004023/translate-the-intent-of-this-php-regex-for-multiline-strings-into-python-perl/7006231#7006231) mejoró el eficiencia de su expresión regular, ¡compruébalo! – smci

regex patológico que explota (tiempo y memoria)?

Respuesta

Cuestiones relacionadas