regex patologico che esplode (tempo e memoria)?

Cos'è un'espressione regolare patologica che fa esplodere molti parser (entrambi nel tempo di memoria &)? e quali parser? I punti bonus sono più basilari e standard della regex, e più è probabile che un utente non malintenzionato possa inventarlo innocentemente. Sentiti libero di pubblicare i dati relativi a tempo e memoria e la versione parser.regex patologico che esplode (tempo e memoria)?

(mi sembra di ricordare che affermazioni eccessive lookbehind o (EDIT:) backtracking in PERL sono detto di fare questo, o per lo meno di una volta ogni altra cosa.?)

fonte

2011-03-15 smci

La tua idea di tornare indietro, quasi tutti i motori regex basati su NFA possono essere ingannati in un backtrack quasi infinito se puoi controllare sia il soggetto che il modello. I motori basati su DFA non hanno bisogno di fare il backtracking, quindi non subiscono il trabocchetto. La risposta alle domande successive è "Perché un DFA in genere non supporta le funzionalità che un NFA può". –

Tratto dal primo esempio in questo articolo Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...):

perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))'

Quale prende 40+ secondi sul mio sistema. Quindi fai $n++ per aumentare in modo esponenziale il divertimento ...

fonte

2011-03-15 03:51:36

È strano che ogni motore regex non lo ottimizzi. Ridurre 'a? A?' A 'a {, 2}' è così basilare che è insegnato nelle classi. –

Esempio sintetico ma saggio utile con confronti tra lingue. – smci

Da Russ Cox di eccellente article: $ perl -e '("a" x 100000) =~ /^(ab?)*$/;'. Questo a quanto pare causa un segfault. Ce ne sono di più nell'articolo.

fonte

2011-03-15 03:22:57 MAK

Python e GNU grep non hanno problemi con questo. 're.match (r '^ (ab?) * $', 'a' * 10000000)' –

Questo non ha causato un problema con il mio installazione perl 5.10.1, e sembra funzionare bene su codepad che è 5.8 http: //codepad.org/hFlqUWk8 –

@Eric Strom: Penso che l'autore stia provando contro perl 5.8.7. – MAK

Io uso sempre questo regex per abbinare stringhe all'interno PHP o codice sorgente JavaScript in PHP:

~'(\\.|[^'])*'|"(\\.|[^"])*"~s

Ed è quasi sempre fallire su una stringa molto lunga (circa 50000 caratteri lunga farà).

fonte

2011-03-15 03:30:21 Thai

Questo utilizza delimitatore ~ perché contiene entrambi i tipi di virgolette; ho provato a convertirlo in una regex di Python per testarlo ma l'escape mi fa impazzire. Qualcuno può convertirlo? – smci

L'ho convertito principalmente usando [questo approccio a causa di Tim Peters] (http://stackoverflow.com/questions/1472047/regex-for-triple-quote) ad eccezione del modificatore s (punto corrisponde a ogni carattere?) ... Sospetto che peggiori le cose. – smci

[questo poster] (http://stackoverflow.com/questions/7004023/translate-the-intent-of-this-php-regex-for-multiline-strings-into-python-perl/7006231#7006231) ha migliorato il efficienza della tua regex, dai un'occhiata! – smci

regex patologico che esplode (tempo e memoria)?

risposta

Problemi correlati