¿Cómo evitar los bucles infinitos en la clase RegEx de .NET?

Question

Obtuvo una tarea sencilla para obtener una expresión XPath y devolver un prefijo que coincida con el padre del nodo que (podría estar) seleccionado.

Ejemplo:

/aaa/bbb       =>   /aaa
/aaa/bbb/ccc   =>   /aaa/bbb
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

Debido a que los patrones dentro de los corchetes pueden contener corchetes dentro de las comillas, decidí intentar lograr esto con el uso de expresiones regulares. Aquí hay un fragmento de código:

string input =
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
                                            //  ^-- remove space for no loop
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;

System.Text.RegularExpressions.Regex re =
    new System.Text.RegularExpressions.Regex(pattern);
bool ismatch = re.IsMatch(input); // <== Infinite loop in here
// some code based on the match

Debido a que los patrones son bastante regulares, busqué '/' seguido de un identificador seguido de un grupo opcional que coincide al final de la cadena (...)? $

El código parece funcionar pero jugando con diferentes valores para la cadena de entrada, encontré que simplemente insertando un espacio (en la ubicación que se muestra en el comentario), la función .NET IsMatch entra en un bucle infinito, tomando todo el CPU lo consigue.

Ahora, independientemente de si este patrón de expresión regular es el mejor (tuve más complejo pero lo simplifiqué para mostrar el problema), esto parece mostrar que el uso de RegEx con algo que no sea trivial puede ser muy riesgoso.

¿Me estoy perdiendo algo? ¿Hay alguna forma de protegerse contra los bucles infinitos en las coincidencias de expresiones regulares?

Answer 1

Ok, analicemos esto entonces:

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "]
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

(Supongo que quiso decir \ " en su cadena escapada con C #, no " " ... traducción de VB.NET?)

Primero, / [a-zA-Z0-9] + engullirá hasta el primer corchete, dejando:

Input: [@x='1' and @y="/aaa[name='z'] "]

El grupo externo de (\ [([^]] * (] " " ")?) +])? $ " debe coincidir si hay 0 o 1 instancia antes del EOL. Así que entremos y veamos si coincide con algo.

El " [" se engulle de inmediato, dejándonos con:

Input: @x='1' and @y="/aaa[name='z'] "]
Pattern: ([^]]*(]")?)+]

Desglosando el patrón: coincida con 0 o más caracteres que no sean ] y luego haga coincidir "] 0 o 1 veces, y siga haciendo esto hasta que no pueda . Luego, intente encontrar y engullir un ] después.

Las coincidencias de patrones basadas en [^]] * hasta que llegan a ] .

Ya que hay un espacio entre ] y " , no puede engullir ninguno de esos caracteres, pero ¿? después de (] ") le permite devolver verdadero de todos modos.

¿Ahora hemos coincidido con éxito ([^]] * (] ")? una vez, pero + dice que deberíamos intentar seguir haciéndolo. número de veces que podemos.

Esto nos deja con:

Input: ] "]

El problema aquí es que esta entrada puede coincidir con ([^]] * (] ")? un infinito de veces sin que se haya devuelto, y " + " Lo forzará a seguir intentando.

Básicamente estás haciendo coincidir " 1 o más " situaciones en las que puedes hacer coincidir " 0 o 1 " de algo seguido de " 0 o 1 " de algo mas Dado que ninguno de los dos subpatrones existe en la entrada restante, sigue coincidiendo con 0 de [^]] \ * y 0 de (] ")? en un bucle sin fin .

La entrada nunca se devora, y el resto del patrón después de " + " nunca se evalúa.

(Ojalá obtuve el SO-escape-of-regex-escape justo arriba.)

Answer 2

  

El problema aquí es que esta entrada puede coincidir ([^]] * (] ")?) un infinito de veces sin que nunca se la haya devuelto, y " + " Lo forzará a seguir intentando.

Eso es un error de error en la implementación RegEx de .NET. Las expresiones regulares no funcionan así. Cuando los conviertes en autómatas, obtienes automáticamente el hecho de que una repetición infinita de una cadena vacía sigue siendo una cadena vacía.

En otras palabras, cualquier motor de expresiones regulares sin errores ejecutará este bucle infinito al instante y continuará con el resto de la expresión regular.

Si lo prefiere, las expresiones regulares son un lenguaje tan limitado que es posible (y fácil) detectar y evitar tales bucles infinitos.

Answer 3

Muestra que usar código con cualquier cosa que no sea trivial puede ser riesgoso. Usted creó un código que puede resultar en un bucle infinito, y el compilador RegEx está obligado. Nada nuevo que no se haya hecho desde los primeros 20 IF X = 0 ENTONCES GOTO 10.

Si está preocupado por esto en un caso particular, podría generar un subproceso para RegEx y luego eliminarlo después de un tiempo de ejecución razonable.

Answer 4

Para responder a la pregunta original (es decir, cómo evitar un bucle infinito con expresiones regulares), esto se ha vuelto fácil con .Net 4.5, ya que simplemente puede pasar un tiempo de espera a los métodos Regex. Hay un temporizador interno que detendrá el ciclo de expresiones regulares cuando expire el tiempo de espera y generará una excepción RegexMatchTimeoutException

Por ejemplo, harías lo siguiente

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]";
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?<*>quot;;
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

Puede consultar MSDN para más detalles