Sono a conoscenza di Denial of Service con espressione regolare (ReDoS). Esiste un modo ragionevole per consentire agli utenti di creare regex personalizzate garantendo al tempo stesso che non inviino pattern in modo esponenziale lento?
Il problema con le espressioni regolari non è la regex stessa, ma il motore regex che ha tutti i tipi di caratteristiche "convenienti" come backtracking. Pertanto, l'utilizzo di un motore regex senza queste caratteristiche evita.
Le espressioni regolari del concetto di informatica possono sempre essere abbinate in tempo lineare dopo che sono state compilate su una macchina a stati finiti. Quindi un motore regex basato sullo stato macchina non può essere usato per ReDoS. Tuttavia, le macchine di stato necessarie possono diventare piuttosto grandi in esempi patologici. Ma limitare la memoria disponibile tende ad essere più semplice di limitare il tempo di calcolo disponibile.
Il motore RE2 è stato sviluppato specificamente per gestire espressioni regex non attendibili ed è stato progettato per l'esecuzione in tempo lineare.
Un'altra alternativa è assemblare te stesso regex da una notazione semplificata. Ad esempio, puoi consentire agli utenti di utilizzare pattern glob (come *.txt ). È quindi possibile analizzarlo in un modo che impedisce il backtracking, ad es. impedendo il nesting e usando solo quantificatori avidi. Per molti casi d'uso, una notazione semplificata del modello è completamente sufficiente.
Analizzando un'espressione regolare per vedere se sarà lenta o meno, senza che l'analisi diventi lenta da sola , equivale a risolvere il problema dell'arresto. In altre parole, è non possibile trovare una soluzione corretta e completa.
Ovviamente puoi trovare una soluzione corretta e in completa. Ad esempio, è possibile lavorare con una lista bianca restrittiva di funzioni che sono sicure da usare (ad esempio classi di caratteri sì, ripetizione no ...). Questo ti permetterebbe di passare un sacco di espressioni regolari acritiche, rifiutare tutte quelle critiche e (a torto) rifiutarne alcune che sono ok, ma troppo complicate per dimostrarle automaticamente.
Come autore di re parser per progetto lazarus direi che non ci sono modi per capire per una determinata espressione regolare quali risorse consumerà su un dato testo.
Senza spendere le stesse risorse intendo (almeno nel significato di big-O).
Quindi l'approccio migliore: esegui re parser in thread separati e uccidilo dopo il timeout.
Oltre alle altre risposte, una soluzione potrebbe anche essere quella di eseguire il rollover della propria libreria regex, che consente la strumentazione delle prestazioni durante l'esecuzione e, quindi, fornire i mezzi per uccidere l'esecuzione a metà se alcuni criteri vengono soddisfatti.
Allo stesso modo, potresti eseguire le espressioni rege su un altro thread e uccidere i thread se impiegano troppo tempo.
Leggi altre domande sui tag regular-expressions