Come gestire le partite infinite dei regex inviati dagli utenti

Question

Consideriamo le due seguenti righe in 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 ");

(scusate se è un programma francese :))

Quando vengono eseguiti, il processo si blocca nel metodo Match () e non termina mai. Immagino che ci sia qualche problema con lo spazio bianco nel pattern regex ma quello che vorrei fare non è cambiare il pattern (in realtà è impostato fuori dal programma, dagli utenti finali del mio strumento) ma essere in grado di interrompere il processo (con un timeout per esempio).

Qualcuno sa se questo è un problema ben noto con .NET Regular Expression e se esiste un modo semplice per aggirare il problema o devo infilare queste righe e interromperle se necessario (sicuramente non mi piacerebbe per farlo).

Answer 1

Penso che dovresti semplicemente lanciare la partita Regex su un thread separato e consentire che venga interrotta se viene raggiunto un certo limite di tempo massimo.

Answer 2

Se inserisco l'espressione in Regexbuddy, presenta il seguente messaggio

  

Il tentativo di incontro è stato interrotto in anticipo   perché anche l'espressione regolare   complesso. Il motore regex che prevedi   usarlo con potrebbe non essere in grado di gestirlo   tutto e crash. Consultare   "backtracking catastrofico" nel   file di aiuto per imparare come evitarlo   situazione.

Cercare backtracking catastrofico fornisce la seguente spiegazione

  

Espressioni regolari in fuga: catastrofico backtracking
  Considera l'espressione regolare (x + x +) + y.   Prima di urlare di orrore e dire   questo esempio inventato dovrebbe essere   scritto come xx + y per corrispondere esattamente a   lo stesso senza quelli terribilmente nidificati   quantificatori: supponi solo che ciascuno di "quot" x "   rappresenta qualcosa di più complesso,   con determinate stringhe corrispondenti   entrambi " x " ;. Vedi la sezione su HTML   file di seguito per un esempio reale.

     

Vediamo cosa succede quando si applica   questa regex a xxxxxxxxxxy. Il primo   x + corrisponderà a tutti i 10 caratteri x. Il   il secondo x + fallisce. Il primo x + quindi   torna a 9 partite e il   il secondo raccoglie la rimanente x.   Il gruppo ora ha abbinato una volta. Il   il gruppo si ripete, ma all'inizio fallisce   x +. Dal momento che una ripetizione era   sufficiente, il gruppo corrisponde. y   corrisponde a y e una corrispondenza generale è   trovato. La regex è dichiarata   funzionale, il codice viene spedito al   cliente e il suo computer esplode.   Quasi.

     

Il regex sopra diventa brutto quando y   manca dalla stringa dell'oggetto.   Quando y fallisce, il motore regex   marcia indietro. Il gruppo ne ha uno   iterazione in cui può tornare indietro. Il   la seconda x + corrisponde a una sola x, quindi   non posso tornare indietro. Ma il primo x + può   rinunciare a una x. Il secondo x + prontamente   corrisponde a xx. Il gruppo ha di nuovo uno   iterazione, fallisce il prossimo e il   y fallisce. Backtracking di nuovo, il   il secondo x + ora ha un backtracking   posizione, riducendo se stesso per abbinare x.   Il gruppo tenta una seconda iterazione.   Il primo x + corrisponde ma il secondo è   bloccato alla fine della corda.   Backtracking di nuovo, il primo x + in   la prima iterazione del gruppo si riduce   stesso a 7 caratteri. Il secondo x +   corrisponde a xxx. In mancanza di y, il secondo x +   viene ridotto a xx e quindi x. Ora il   il gruppo può corrispondere a una seconda iterazione,   con una x per ogni x +. Ma questo   Anche la combinazione (7,1), (1,1) fallisce. Così   va a (6,4) e poi (6,2) (1,1)   e poi (6,1), (2,1) e poi   (6,1), (1,2) e poi penso che inizi   per ottenere la deriva.

     

Se provi questo regex su una stringa 10x   nel debugger di RegexBuddy, ci vorrà   2558 passi per capire l'ultimo y   manca. Per una stringa 11x, esso   ha bisogno di 5118 passaggi. Per 12, ci vuole   10238 passi. Chiaramente abbiamo un   complessità esponenziale di O (2 ^ n) qui.   A 21x il debugger si inchina a 2.8   milioni di passi, diagnosticare un brutto caso   di backtracking catastrofico.

     

RegexBuddy sta perdonando in questo   rileva che sta andando in cerchio e   interrompe il tentativo di incontro. Altra regex   i motori (come .NET) continueranno a funzionare   per sempre , mentre altri andranno in crash   uno stack overflow (come Perl, prima   versione 5.10). Gli overflow dello stack sono   particolarmente brutto su Windows, da allora   tendono a fare la tua domanda   svanire senza lasciare traccia o spiegazione.   Fai molta attenzione se gestisci un web   servizio che consente agli utenti di fornire   le loro espressioni regolari. Persone   con poca esperienza regex hanno   abilità sorprendente a venire con   regolare esponenzialmente complesso   espressioni.

Suppongo che dovrai gestirlo nel codice. Ti suggerirei di contattare l'autore di Regexbuddy e chiedere cosa è necessario per rilevare questo scenario.

Answer 3

In generale, le espressioni regolari possono richiedere più tempo del previsto. Dovresti sperimentare l'espressione regolare hjusing uno strumento come Regulator.

Answer 4

Il problema è che hai annidato " loop " nel tuo Regex, che lo rende terribilmente inefficiente (in modo che in pratica richieda per sempre a causa della complessità dell'espressione).

Se dici quello che vorresti abbinare, posso provare a trovare un Regex più efficiente per quello.

Answer 5

Mi sembra un caso il match di regex che cresce in modo esponenziale. Vedi il blog BCL .

La soluzione migliore è impostare un timeout sul regex, senza fare confusione con i thread.

Vedi qui come rimuovere le stringhe con timeout .