Depuración regEx

pcre backtracking

Question

Estoy depurando una expresión regular ^(A+)*B sobre una cadena AAAC (ejemplo de rexegg.com) mediante dos herramientas de depuración separadas a las que tengo acceso:

1. regex101.com
2. RegexBuddy v4

A continuación se muestran los resultados (regex101 en el lado izquierdo):

La pregunta que tengo no es principalmente sobre la cantidad de pasos que también es importante para mí, sino cómo se realizan las pistas de retroceso. ¿Por qué vemos diferencias? (regex101 usa PCRE lib y configuro RegexBuddy lib igual)

Una explicación completa paso a paso está realmente a mi favor.

Answer 1

TL; DR

En resumen, "retroceso" es cuando un motor de expresiones regulares regresa a una coincidencia "flexible", intentando una ruta diferente para obtener una coincidencia exitosa.

Retroceso con alternancia

Por ejemplo, en el siguiente patrón y entrada:

foo(bar|baz)

foobaz

El motor de expresiones regulares coincidirá con "foo", luego intentará la primera de las dos opciones, haciendo coincidir "b" y luego "a", pero fallará en "r". Sin embargo, en lugar de fallar todo el partido, "rebobinará la cinta" y comenzará con la segunda alternativa, haciendo coincidir "b", luego "a" y luego "z" ... ¡éxito!

Retroceso con cuantificadores

Esto también funciona con cuantificadores. Un cuantificador es cualquier cosa que fomente que el motor coincida con un patrón de repetición, incluido ? , * , + y {n,m} (dependiendo del motor).

Un cuantificador codicioso (el valor predeterminado) coincidirá con tantas repeticiones como sea posible antes de pasar al resto del patrón. Por ejemplo, dado el patrón y la entrada a continuación:

/w+bar

foobar

El patrón /w+ comenzará con la cadena completa: "foobar". Sin embargo, cuando pasa a la b , el motor de expresiones regulares ha llegado al final de la entrada y la coincidencia falla. En lugar de simplemente darse por vencido, el motor le pedirá al último cuantificador codicioso que renuncie a una de sus repeticiones, que ahora coinciden con "fooba". La coincidencia aún falla, por lo que el motor le pide a /w+ que renuncie a la "a" (falla) y luego a la "b". Después de abandonar la "b", el motor ahora puede igualar la bar , y la coincidencia es exitosa.

Árboles y Retroceso

Otra forma de pensar en una expresión regular es como un "árbol", y el retroceso es volver a subir un nodo e intentar otra ruta. Dado el patrón foo(bar|baz) y la entrada "foobaz", el motor intentará algo como lo siguiente:

foo(bar|baz)
|/
| /
|  : f (match)
|  : o (match)
|  : o (match)
|  | (bar|baz)
|  |/
|  | /
|  |  : b (match)
|  |  : a (match)
|  |  : r (FAIL: go back up a level)
|  |  ^
|  |/
|  | /
|  |  : b (match)
|  |  : a (match)
|  |  : z (match)
|  | /
|  |/
| /
|/
SUCCESS

Contando los "Backtracks"

En cuanto a por qué ve diferencias en el "número" de pistas de retroceso ... esto probablemente tenga mucho que ver con las optimizaciones internas y el nivel de registro. Por ejemplo, RegexBuddy no parece estar registrando la coincidencia en la cadena vacía antes de ^ , mientras que regex101 lo hace. Sin embargo, al final, no importa el orden exacto en el que retrocedes (en qué orden subes el árbol) siempre y cuando obtengas el mismo resultado.

Malos regexes

Ya lo sabes, pero para el beneficio de cualquier otra persona que pase, tu expresión regular se escribió para demostrar " retroceso catastrófico " (también conocido como "expresión regular malvada"), donde el número de intentos de retroceso crece exponencialmente a medida que aumenta la longitud de la entrada. Estas expresiones regulares pueden ser explotadas para realizar ataques DoS , por lo que debe tener cuidado de no introducirlas en sus patrones (como descubrí ).

Answer 2

No confiaría ni en la cantidad de pasos ni en la depuración como prueba
de retroceso o fracaso.

En general, manténgase alejado de construcciones simples como (A+)* que no solo
retroceda el A+ interno pero retroceda también hacia el exterior (..)* .
Cada paso del externo produce una nueva serie interna de retroceso.

Obtenga un buen software de referencia como RegexFormat
y prueba una serie para un resultado de tiempo exponencial.
Un resultado lineal es lo que está buscando a medida que el contenido aumenta por igual.
cantidad.

A continuación se muestra un ejemplo de (A+)? vs (A+)* . Fijamos el objetivo a un fallo conocido.
y aumente constantemente la longitud para extender el procesamiento de ese fallo.

Si observa la expresión regular 2 (A+)* , puede notar el aumento exponencial en solo
Tres aumentos de objetivo.
Finalmente, eliminamos el objetivo para sobrecargar los recursos internos del motor.

Edición : Después de algunos análisis, publico una conclusión muy escasa sobre los pasos de retroceso.
Al analizar el tiempo de referencia a continuación, el retroceso parece ser un proceso de 2 ° N.
Donde N es el número de literales de caracteres que se vuelven atrás en caso de fallo.

Dado el caso simple de Revo, es un poco más fácil aislar el seguimiento.
Debido a que parece que% 98 del tiempo total involucrado implica solo un retroceso.

Dado ese supuesto, uno puede tomar los resultados de tiempo de 2 puntos y generar una ecuación.

La forma de la ecuación que utilicé fue f(x) = a * r^x .
Dadas las coordenadas (# de ''A''s vs. Tiempo tomado), usando puntos
(7, 1.13), (9, 4.43) que generó este f(x) = 0.009475 * 1.9799 ^ x
que es realmente este # sec''s = 0.009475 * 1.9799 ^ # letters
Corrí toda la cantidad de letras ''A'' de los puntos de referencia a continuación en esta fórmula.

#LTR''s   Bench Time
 7         1.13
 9         4.43
13        70.51

que produjo el tiempo de referencia exacto (+/- .1%).

Luego vi que 1.9799 está bastante cerca de 2.0, así que ajusté el factor ''a'' a .009 y lo ejecuté nuevamente, obteniendo esto:

f(7 letters) = 2 ^ 7 * .009 =  1.152 sec’s
f(9 letters) = 2 ^ 9 * .009 =  4.608 sec’s
f(13 letters) = 2 ^ 13 * .009 =  73.728 sec’s
f(27 letters) = 2 ^ 27 * .009 =  1207959.552 sec’s = 335 hours  

Parece bastante claro ahora que los pasos de retroceso se correlacionan con el número de
Cartas para dar marcha atrás en una relación de 2 ^ N.

También creo que es una apuesta justa que algunos motores puedan hacer esto simple matemática de 2 ^ N
Solo en escenarios simples como este. Estos parecen ser los tiempos donde
¡El motor vuelve inmediatamente y dice demasiado complejo! .
La traducción aquí es que la expresión regular es lo suficientemente simple como para que el motor pueda
detectalo Otras veces, el motor nunca vuelve,
está colgado, y puede volver en un año o dos (o diez ..).

Por lo tanto, la conclusión no es si el motor retrocederá, lo hará, sino cómo
¿Su cadena de destino afectará el retroceso?

Por lo tanto, se requiere vigilancia al escribir expresiones regulares, y debe estar en guardia contra
Cuantificadores de extremo abierto anidados.

Yo diría que la mejor apuesta es siempre golpear una expresión regular muy difícil para que falle.
Y estoy hablando de excesivos literales repetitivos en lugares sospechosos.
edición final

Aplicación de referencia

Objetivo: AAAAAAAC

Punto de referencia

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.07 s,   72.04 ms,   72040 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    1.13 s,   1126.44 ms,   1126444 µs

Objetivo: AAAAAAAAAC

Punto de referencia

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.08 s,   82.43 ms,   82426 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    4.43 s,   4433.19 ms,   4433188 µs

Objetivo: AAAAAAAAAAAAAC

Punto de referencia

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.10 s,   104.02 ms,   104023 µs


Regex2:   ^(A+)*B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    70.51 s,   70509.32 ms,   70509321 µs

Objetivo: AAAAAAAAAAAAAAAAAAAAAAAAAAAC

Punto de referencia

Regex1:   ^(A+)?B
Options:  < none >
Completed iterations:   50  /  50     ( x 1000 )
Matches found per iteration:   0
Elapsed Time:    0.18 s,   184.05 ms,   184047 µs


Regex2:   ^(A+)*B
Options:  < none >
Error:  Regex Runtime Error !!   
Completed iterations:   0  /  50     ( x 1000 )
Matches found per iteration:   -1
Elapsed Time:    0.01 s,   7.38 ms,   7384 µs


Error item 2 :  Target Operation .. 

The complexity of matching the regular expression exceeded predefined
bounds. Try refactoring the regular expression to make each choice made by
the state machine unambiguous. This exception is thrown to prevent
"eternal" matches that take an indefinite period time to locate.