Cómo manejar las coincidencias interminables de expresiones regulares enviadas por el usuario

Question

Consideremos las dos líneas siguientes en C # (usando framework .NET 3.5)

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)<*>quot;, RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

(lo siento, es un programa en francés :))

Cuando se ejecutan, el proceso se bloquea en el método Match () y nunca sale. Supongo que hay un problema con el espacio en blanco en el patrón de expresiones regulares, pero lo que me gustaría hacer es no cambiar el patrón (en realidad está establecido fuera del programa, por los usuarios finales de mi herramienta), pero poder detener el proceso. (con un tiempo de espera, por ejemplo).

¿Alguien sabe si este es un problema bien conocido con .NET Regular Expression y si hay una manera fácil de solucionarlo o tengo que enlazar estas líneas y abortarlas si es necesario? (definitivamente no me gustaría para hacer eso).

Answer 1

Creo que simplemente debes iniciar la coincidencia de Regex en un hilo separado y permitir que se cancele si se alcanza un cierto límite de tiempo máximo.

Answer 2

Si ingreso la expresión en Regexbuddy, aparecerá el siguiente mensaje

  

El intento de emparejamiento fue abortado temprano   porque la expresión regular es demasiado   complejo. El motor de expresiones regulares que planea   utilizarlo con no poder manejar   Es en absoluto y se estrellan. Buscar   " retroceso catastrófico " en el   Archivo de ayuda para aprender a evitar esto.   situación.

Buscando retroceso catastrófico da la siguiente explicación

  

Runaway Regular Expressions: Retroceso catastrófico
  Considera la expresión regular (x + x +) + y.   Antes de gritar de horror y decir   este ejemplo artificial debe ser   escrito como xx + y para que coincida exactamente con la   mismo sin esos terriblemente anidados   cuantificadores: solo asuma que cada " x "   representa algo más complejo,   con ciertas cuerdas siendo emparejadas por   ambos " x " ;. Vea la sección en HTML   archivos a continuación para un ejemplo real.

     

Veamos que pasa cuando aplicas   este regex a xxxxxxxxxxy El primero   x + coincidirá con todos los 10 x caracteres. los   segundo x + falla. La primera x + luego   retrocede a 9 partidos, y la   la segunda recoge el x restante.   El grupo ahora ha emparejado una vez. los   El grupo se repite, pero falla en la primera.   x +. Ya que una repetición fue   Basta, el grupo coincide. y   coincide con y y una coincidencia general es   encontró. Se declara la expresión regular   Funcional, el código se envía al   Cliente, y su computadora explota.   Casi.

     

La expresión regular anterior se vuelve fea cuando la y   falta en la cadena de asunto.   Cuando y falla, el motor de expresiones regulares   atrasos El grupo tiene uno   iteración en la que puede retroceder. los   el segundo x + igualó solo un x, por lo que   no puede retroceder Pero el primer x + puede   renunciar a una x El segundo x + puntualmente   coincide con xx. El grupo vuelve a tener uno.   iteración, falla la siguiente, y la   y falla. Retrocediendo de nuevo, el   segundo x + ahora tiene un retroceso   posición, reduciéndose a si mismo a x.   El grupo intenta una segunda iteración.   Los primeros x + partidos pero el segundo es   Atascado al final de la cadena.   Backtracking de nuevo, el primer x + en   La primera iteración del grupo se reduce.   En sí de 7 caracteres. El segundo x +   coincide con xxx. A falta y, la segunda x +   Se reduce a xx y luego a x. Ahora el   grupo puede coincidir con una segunda iteración,   con una x para cada x +. Pero esto   (7,1), (1,1) la combinación también falla. Asi que   va a (6,4) y luego (6,2) (1,1)   y luego (6,1), (2,1) y luego   (6,1), (1,2) y luego creo que empiezas   para obtener la deriva.

     

Si prueba esta expresión regular en una cadena 10x   en el depurador de RegexBuddy, tomará   2558 pasos para averiguar la final y   Está perdido. Para una cadena 11x,   Necesita 5118 pasos. Para 12, lleva   10238 pasos. Claramente tenemos una   Complejidad exponencial de O (2 ^ n) aquí.   A los 21x el depurador cede a 2.8   Millones de pasos, diagnosticando un mal caso.   de retroceso catastrófico.

     

RegexBuddy perdona en eso   detecta que va en círculos , y   aborta el intento de emparejamiento. Otra expresión regular   Los motores (como .NET) seguirán funcionando.   para siempre , mientras que otros se estrellarán con   un desbordamiento de pila (como Perl, antes   versión 5.10). Desbordamientos de pila son   particularmente desagradable en Windows, ya que   Tienden a hacer tu solicitud.   Desaparecer sin rastro ni explicación.   Ten mucho cuidado si corres una web   Servicio que permite a los usuarios suministrar   sus propias expresiones regulares. Gente   con poca experiencia regex tener   sorprendente habilidad para llegar a   exponencialmente complejo regular   expresiones.

Supongo que vas a tener que manejarlo en código. Le sugiero que se ponga en contacto con el autor de Regexbuddy y pregunte qué se necesita para detectar este escenario.

Answer 3

En general, las expresiones regulares pueden tomar más tiempo de lo esperado. Debes experimentar con la expresión regular ajustando una herramienta como Regulator.

Answer 4

El problema es que ha anidado " bucles " en tu Regex, lo que lo hace terriblemente ineficiente (por lo que básicamente toma una eternidad debido a la complejidad de la expresión).

Si dices lo que te gustaría hacer coincidir, puedo tratar de encontrar una expresión regular más eficiente para eso.

Answer 5

Me parece que es un caso en el que la coincidencia de expresiones regulares crece exponencialmente. Consulte el blog de BCL .

La mejor solución es establecer un tiempo de espera en la expresión regular, sin perder el tiempo con subprocesos.

Vea aquí cómo eliminar las cadenas con tiempo de espera .