Come evitare loop infiniti nella classe .NET RegEx?

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

Domanda

Ha una semplice attività per ottenere un'espressione XPath e restituire un prefisso che corrisponde al genitore del nodo che (potrebbe essere) selezionato.

Esempio: 

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

Poiché i motivi all'interno delle parentesi quadre potrebbero contenere parentesi tra virgolette, ho deciso di provare a farlo con l'uso di espressioni regolari. Ecco uno snippet di codice: 

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

Poiché i pattern sono piuttosto regolari, ho cercato '/' seguito da un identificatore seguito da un gruppo opzionale che corrisponde alla fine della stringa (....)? $

Il codice sembrava funzionare ma giocando con valori diversi per la stringa di input, ho scoperto che inserendo semplicemente uno spazio (nella posizione mostrata nel commento), la funzione .NET IsMatch entra in un ciclo infinito, prendendo tutto il CPU che ottiene.

Ora, indipendentemente dal fatto che questo modello di espressione regolare sia il migliore (lo avevo più complesso ma semplificato per mostrare il problema), questo sembra mostrare che l'uso di RegEx con qualcosa di non banale può essere molto rischioso.

Mi sto perdendo qualcosa? Esiste un modo per proteggersi da loop infiniti nelle partite di espressioni regolari?

È stato utile?

Soluzione

Ok, allora scomponiamo questo: 

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

(Suppongo che intendessi \ " nella tua stringa con escape C #, non " " ... traduzione da VB.NET?)

In primo luogo, / [a-zA-Z0-9] + si divorerà attraverso la prima parentesi quadra, lasciando: 

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

Il gruppo esterno di (\ [([^]] * (] " ")?) +])? $ " deve corrispondere se è presente 0 o 1 istanza prima dell'EOL. Quindi entriamo e vediamo se corrisponde a qualcosa.

Il " [" viene subito inghiottito, lasciandoci con: 

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

Abbattendo il modello: abbina 0 o più caratteri non ] e quindi abbina "] 0 o 1 volte e continua a farlo fino a quando non puoi . Quindi prova a trovare e divorare un ] in seguito.

Il modello corrisponde in base a [^]] * fino a quando non raggiunge il ] .

Dato che c'è uno spazio tra ] e " , non può inghiottire nessuno di quei personaggi, ma il ? dopo (] ") consente comunque di restituire true.

Ora abbiamo abbinato correttamente ([^]] * (] ")?) una volta, ma il + dice che dovremmo cercare di continuare ad abbinarlo quante volte possiamo.

Questo ci lascia con: 

Input: ] "]

Il problema qui è che questo input può corrispondere a ([^]] * (] ")?) un infinito di volte senza mai essere inghiottito, e " + " lo costringerà a continuare a provare.

In pratica stai abbinando " 1 o più " situazioni in cui è possibile abbinare " 0 o 1 " di qualcosa seguito da " 0 o 1 " di qualcos'altro. Poiché nessuno dei due sottotitoli esiste nell'input rimanente, continua a corrispondere 0 di [^]] \ * e 0 di (] ")? in un ciclo infinito .

L'input non viene mai inghiottito e il resto del pattern dopo il " + " non viene mai valutato.

(Spero di avere la SO-escape-of-regex-escape proprio sopra.)

Altri suggerimenti

  

Il problema qui è che questo input può corrispondere ([^]] * (] ")?) un'infinità di volte senza mai essere inghiottito, e " + " lo costringerà a continuare a provare.

Questo è un inferno di un bug nell'implementazione RegEx di .NET. Le espressioni regolari non funzionano così. Quando li trasformi in automi, ottieni automaticamente il fatto che una ripetizione infinita di una stringa vuota è ancora una stringa vuota.

In altre parole, qualsiasi motore regex senza buggy eseguirà questo loop infinito all'istante e continuerà con il resto del regex.

Se preferisci, le espressioni regolari sono un linguaggio così limitato che è possibile (e facile) rilevare ed evitare cicli così infiniti.

Mostra che l'uso del codice con qualsiasi cosa non banale può essere rischioso. È stato creato il codice che può provocare un ciclo infinito e il compilatore RegEx obbligato. Nulla di nuovo che non è stato fatto dai primi 20 IF X = 0 THEN GOTO 10.

Se sei preoccupato per questo in un caso limite particolare, potresti generare un thread per RegEx e poi ucciderlo dopo un tempo di esecuzione ragionevole.

Per rispondere alla domanda originale (ovvero come evitare un ciclo infinito con regex), questo è diventato facile con .Net 4.5 in quanto puoi semplicemente passare un timeout ai metodi Regex. Esiste un timer interno che interromperà il ciclo regex alla scadenza del timeout e genererà una RegexMatchTimeoutException

Ad esempio, dovresti fare quanto segue 

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));

Puoi dare un'occhiata a MSDN per maggiori dettagli

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top