Question 1

Cos'è il ReDoS (Denial of Service tramite Espressioni Regolari)?

Accepted Answer

Il ReDoS è una classe di vulnerabilità denial-of-service in cui una stringa di input costruita malevolmente fa sì che un motore di espressioni regolari impieghi tempo esponenziale o polinomiale per la valutazione, bloccando o facendo crashare il processo. Nasce dalla combinazione di due fattori: (1) Il backtracking — la maggior parte dei motori regex usa il backtracking per esplorare tutti i possibili percorsi di corrispondenza quando una corrispondenza fallisce, e (2) Pattern ambigui — regex in cui più percorsi possono corrispondere agli stessi caratteri di input, causando al backtracking di esplorare esponenzialmente molte combinazioni.

Question 2

Quali pattern di regex sono più vulnerabili al ReDoS?

Accepted Answer

I pattern più pericolosi coinvolgono quantificatori annidati e alternanze dove i sotto-pattern possono sovrapporsi. L'esempio classico è (a+)+ o (a|aa)+ — entrambi hanno un'esplosione esponenziale su un input come 'aaaaaaaab'. Altri pattern rischiosi: (.*)* (stella di Kleene annidata), (a*b?c*)+ (gruppi sovrapposti), e pattern con più operatori .* o .+ adiacenti.

Question 3

Come identifica un rilevatore ReDoS i pattern vulnerabili?

Accepted Answer

Gli strumenti di analisi statica rilevano il ReDoS analizzando la struttura interna del regex — cercando specificamente: (1) Quantificatori annidati: un'espressione all'interno di un quantificatore che è essa stessa ripetuta (es. (X+)+). (2) Ambiguità esponenziale: percorsi attraverso l'NFA (Automa Finito Non Deterministico) che possono corrispondere alla stessa stringa in più modi — rilevato eseguendo l'NFA su stringhe di attacco specifiche o tramite analisi formale del grafo degli stati.

Question 4

Come correggo un regex vulnerabile al ReDoS?

Accepted Answer

Correzioni comuni: (1) Rimuovere i quantificatori annidati — riscrivere (a+)+ come a+. (2) Rendere l'alternanza non sovrapposta — invece di (cat|catch), usare catch|cat (il più lungo prima) o (cat)(?:ch)?. (3) Usare quantificatori possessivi o gruppi atomici dove il motore li supporta — (?>a+) non fa mai backtrack. (4) Usare un motore regex a tempo lineare come RE2, Hyperscan o il pacchetto regexp di Go, che garantisce la corrispondenza O(n) senza backtracking.

Question 5

Quali motori di regex di linguaggi di programmazione sono vulnerabili al ReDoS?

Accepted Answer

Motori con backtracking (vulnerabili): JavaScript (V8), Python (modulo re), Java (java.util.regex), PHP (PCRE), Ruby, .NET — tutti possono mostrare esplosione esponenziale. Motori senza backtracking (sicuri): RE2 (Google), regexp di Go, crate regex di Rust, Hyperscan — garantiscono tempo lineare O(n) ma non supportano lookaheads/lookbehinds né backreference. Per la validazione di input sensibile alla sicurezza, RE2 o motori simili a tempo lineare dovrebbero essere fortemente preferiti.

Rilevatore ReDoS regex

Domande Frequenti

Comments & Feedback