Prova le espressioni regolari con evidenziazione delle corrispondenze.
I risultati hanno carattere informativo. Verificali con altre fonti.
Una stringa di 26 caratteri può impiegare 368 ms per fallire contro il pattern sbagliato
Le espressioni regolari girano di solito in un tempo proporzionale all'input. Annida un quantificatore dentro un gruppo quantificato e questo smette di valere: /^(a+)+$/ impiega circa 23 ms per rifiutare 22 caratteri, 95 ms per 24 e 368 ms per 26. Ogni carattere in più raddoppia all'incirca il lavoro, quindi un input un po' più lungo non rallenta la ricerca: le impedisce di concludersi.
Come funziona
- Prova un pattern su un testo di esempio e mostra ogni corrispondenza con i suoi gruppi di cattura.
- Spiega che cosa fa ciascuna parte dell'espressione, dato che la sintassi è densa per costruzione.
- Permette di provare i casi che falliscono, ed è lì che vivono i problemi di prestazioni.
la forma pericolosa: un quantificatore dentro un gruppo quantificato (a+)+ (a*)* (a|a)* (\d+)+ n caratteri si possono ripartire fra i gruppi in un numero esponenziale di modi, e il motore deve provarli tutti prima di poter dichiarare l'assenza di corrispondenza equivalente sicuro: a+ — un solo quantificatore, tempo lineare
Esempio pratico
Misurazione di /^(a+)+$/ su stringhe di a seguite da un ! che non può corrispondere.
- 22 caratteri → circa 23 ms
- 24 caratteri → circa 95 ms
- 26 caratteri → circa 368 ms
- le stesse 26 a senza il ! → corrispondenza in meno di 0,01 ms
- la forma sicura /^a+$/ su 100.000 caratteri → 0,12 ms
Rifiutare 26 caratteri costa tremila volte più che accettarne 100.000. Il successo è istantaneo e il fallimento esponenziale, ed è per questo che non emerge mai nei test: il percorso felice è sempre veloce.
Come leggere il risultato
- È un vettore di negazione del servizio ovunque l'input dell'utente raggiunga un pattern. Un attaccante non ha bisogno di una stringa lunga: trenta o quaranta caratteri bastano a occupare un thread di richiesta per minuti, e una manciata di richieste simili mette giù un server.
- La correzione consiste quasi sempre nel togliere l'annidamento anziché ottimizzarci intorno. (a+)+ e a+ riconoscono esattamente lo stesso linguaggio, quindi la versione vulnerabile non porta assolutamente nulla: è un errore, non un compromesso.
- Le misurazioni provengono da una macchina e variano da motore a motore, ma la forma del fenomeno no. Qualsiasi implementazione con backtracking — JavaScript, Python, Java, PCRE — si comporta così. RE2 e il regexp di Go no, perché rifiutano le funzionalità che lo rendono possibile.
- Prova i tuoi pattern su input che falliscono, non solo su quelli che corrispondono. Il caso catastrofico compare solo quando il motore deve esaurire ogni possibilità prima di concludere che non c'è corrispondenza.
Domande frequenti
- Come faccio a sapere se il mio pattern è vulnerabile?
- Cerca un quantificatore dentro un gruppo quantificato — (a+)+, (a*)*, (\d+)* e simili — e alternative i cui rami possano riconoscere lo stesso testo. Poi prova con una stringa lunga che QUASI corrisponde, perché sono i quasi-successi a innescare il percorso esponenziale.
- Perché è veloce quando corrisponde e lento quando non corrisponde?
- Perché il motore può fermarsi al primo successo ma deve esaurire ogni possibilità prima di dichiarare un fallimento. Con quantificatori annidati il numero di possibilità raddoppia per carattere, quindi il caso che fallisce è l'unico che venga mai esplorato per intero.