ReDos attacca le caratteristiche di sfruttamento di alcune espressioni regolari (altrimenti utili) ... causando essenzialmente un'esplosione di possibili percorsi attraverso il grafico definito dalla NFA.
Quindi usare un parser ricorsivo-discendente (come ANTLR) evita necessariamente il problema?
Necessariamente ? No.
I parser decenti ricorsivi possono essere implementati tanto ingenuamente quanto l'algoritmo di espressione regolare (si potrebbe implementare l'NFA tramite decente ricorsivo, per esempio). Probabilmente hanno maggiori probabilità di avere il problema perché di solito hanno a che fare con grammatiche context free, che consentono una gamma più ampia di complessità e quindi una gamma più ampia di possibili usi sfruttabili.
Ogni espressione regolare definisce un linguaggio normale . Un'espressione regolare può essere tradotta in un automa finito non deterministico (NFA) che riconosce la sua lingua. Ogni NFA può essere tradotto in un automa finito deterministico (DFA) che riconosce la stessa lingua in tempo lineare. Ogni DFA può essere tradotto in una grammatica regolare (vedi ad esempio qui ) che genera lo stesso normale linguaggio. Una grammatica regolare è un particolare tipo di grammatica senza contesto, il che implica che tutte le lingue regolari sono anche prive di contesto.
Quindi, se la lingua che si desidera riconoscere è regolare, è possibile utilizzare un parser ricorsivo-discendente per analizzarlo, ma non si otterrebbe nulla in termini di complessità temporale.
Per quanto ho capito, gli attacchi che hai citato nella tua domanda sono relativi a
Il caso 1 è facilmente risolvibile usando un'implementazione non ingenua che viene eseguita in tempo lineare: non c'è bisogno di parser ricorsivi-discendenti.
Il caso 2 dipende dalle estensioni che vuoi supportare. Se si desidera utilizzare il parser di discesa ricorsivo, la lingua deve essere libera dal contesto, quindi è necessario innanzitutto verificare se le lingue definite da espressioni regolari con estensioni come i riferimenti precedenti sono prive di contesto.
Queste lingue non sono prive di contesto (vedere la risposta al domanda parallela sul sito di Computer Science per un ottimo background sull'argomento). La mia intuizione sul perché non siano prive di contesto è che una grammatica context free dovrebbe essere in grado di generare stringhe con sottostringhe disgiunte arbitrariamente lunghe. Probabilmente puoi utilizzare pompare il lemma per le lingue context free per mostrare che una grammatica context free non può farlo.
In conclusione: i parser di discendenza ricorsiva non sono utili per questo tipo di estensioni.
Una soluzione pragmatica è innanzitutto eseguire l'algoritmo DFA veloce e ripristinare l'algoritmo potenzialmente esponenziale solo se viene rilevato un riferimento all'indietro nell'espressione regolare. Questo è citato qui nella Sezione Implementazioni e tempi di esecuzione . Sfortunatamente ci sono poche informazioni su questo approccio nella pagina di Wikipedia. Se trovo altri dettagli da qualche altra parte, li aggiungerò a questa risposta.
Leggi altre domande sui tag parsing