Backtracking Catastrofico

Il backtracking catastrofico è un fenomeno nelle espressioni regolari in cui il motore impiega un tempo eccessivo per valutare certi pattern, causando una significativa degradazione delle prestazioni — a volte secondi, minuti o praticamente un'attesa infinita. Si verifica perché il motore prova a trovare corrispondenze per parti della stringa in molti modi diversi prima di arrendersi, e il numero di combinazioni esplorate cresce esponenzialmente con la lunghezza dell'input.

Questa pagina tratta cosa innesca il problema, come riconoscere un pattern pericoloso e tecniche concrete per riscrivere una regex in modo che rimanga veloce. Si presuppone che tu abbia familiarità con i quantificatori e la differenza tra corrispondenza greedy e lazy.

Perché è importante: Una singola regex lenta applicata a input fornito dall'utente è un vero vettore di denial-of-service (spesso chiamato "ReDoS"). Un attaccante deve solo inviare una stringa breve costruita per massimizzare il backtracking per bloccare l'event loop di Node.js.

Cosa Causa il Backtracking Catastrofico?

Il backtracking catastrofico si verifica tipicamente con i quantificatori annidati — un quantificatore all'interno di un gruppo che è a sua volta quantificato, come (a+)+. Il pericolo si manifesta quando due parti del pattern possono corrispondere agli stessi caratteri, quindi il motore ha molti modi sovrapposti per dividere l'input. Quando la corrispondenza alla fine fallisce, il motore deve provare ognuna di quelle divisioni prima di poter concludere che niente corrisponde. Ecco l'esempio classico:

Se non impiega molto tempo sul tuo computer, puoi aggiungere un altro carattere a alla str. Quindi perché impiega così tanto tempo? Analizziamolo. Il pattern /^(a+)+$/ è composto da:

• ^ che asserisce la posizione all'inizio della stringa.
• (a+) che corrisponde a uno o più caratteri a.
• + che permette al gruppo precedente (a+) di ripetersi una o più volte.
• $ che asserisce la posizione alla fine della stringa.

Il processo di corrispondenza è:

1. Corrispondenza Iniziale: Il motore parte dall'inizio della stringa (^).
2. Prima Corrispondenza del Gruppo: Il motore corrisponde al primo a+, consumando tutti i caratteri a (aaa...).
3. Quantificatore Esterno: Il + esterno permette al motore di ripetere il gruppo (a+).

Quando il motore raggiunge il punto esclamativo (!), non riesce a trovare una corrispondenza con il pattern, causando il fallimento della corrispondenza. A questo punto inizia il backtracking:

1. Tentativo di Backtracking: Il motore fa backtracking per dividere ripetutamente i caratteri a trovati tra il quantificatore interno a+ e quello esterno +. Rivaluta ogni divisione per vedere se una partizione diversa può corrispondere al pattern fino alla fine della stringa.
2. Crescita Esponenziale: Questo processo di backtracking può crescere esponenzialmente mentre il motore prova ogni modo possibile per partizionare la stringa di caratteri a in gruppi diversi che potrebbero potenzialmente corrispondere a (a+)+.

Per una stringa di n caratteri a, il a+ interno e il + esterno possono dividere quei caratteri in gruppi in circa 2^(n-1) modi diversi. Quando il ! finale fa fallire la corrispondenza, il motore deve provarli tutti. Ecco perché aggiungere un singolo a extra all'input raddoppia approssimativamente il tempo di esecuzione — il segno distintivo dell'esplosione esponenziale. La corrispondenza seguente ha successo rapidamente perché non c'è una coda che fallisce e che forza un'esplorazione completa:

La lezione: il backtracking catastrofico morde solo quando un pattern può corrispondere in molti modi e la corrispondenza complessiva alla fine fallisce. Un input fallace costruito ad arte è esattamente quello che un attaccante invia.

Identificare i Pattern Soggetti al Backtracking Catastrofico

Come rapida lista di controllo mentale, un pattern è a rischio quando presenta tutte e tre queste caratteristiche: una ripetizione, all'interno di un'altra ripetizione, su caratteri che si sovrappongono. Segnali d'allarme comuni:

• Quantificatori annidati, ad es. (a+)+, (\d*)*, (\w+)*.
• Gruppi quantificati contenenti un'alternanza che si sovrappone, ad es. (a|a)+ o (\w|\d)+ (\w include già \d).
• Un .* o .+ greedy tra due elementi che possono anch'essi corrispondere agli stessi caratteri, ad es. <.+>.*<.+>.
• Pattern non ancorati su input lungo, che ritentano l'intera corrispondenza a ogni posizione di partenza.

Se le ripetizioni di un gruppo quantificato possono ciascuna corrispondere alla stessa sottostringa, hai ambiguità, e l'ambiguità è ciò che il backtracking esplora.

Strategie per Prevenire il Backtracking Catastrofico

L'obiettivo di ogni soluzione qui sotto è lo stesso: rimuovere l'ambiguità che permette al motore di dividere l'input in più di un modo. Passare da greedy a lazy (+?, *?) non aiuta — entrambi esplorano ancora ogni divisione; lazy le esplora solo in un ordine diverso. Devi cambiare la struttura del pattern, non la sua greediness.

1. Eliminare il Quantificatore Annidato

(a+)+ è quasi sempre equivalente a un singolo quantificatore. Se hai bisogno solo di "uno o più a", scrivi semplicemente a+. C'è esattamente un modo per corrispondere a questo, quindi il motore non può fare backtracking in un'esplosione combinatoria.

2. Emulare un Gruppo Atomico con il Lookahead

JavaScript non dispone di gruppi atomici (?>...) o quantificatori possessivi (a++) integrati come alcune altre varianti di regex. Puoi riprodurre lo stesso comportamento "corrispondi una volta e non cedere mai" con un lookahead più un backreference: (?=(a+))\1. Il lookahead corrisponde a a+ in modo greedy, lo acquisisce, e \1 consuma esattamente quel testo — ma poiché il gruppo acquisito era all'interno di un lookahead, il motore non lo ripartizionerà durante il backtracking.

3. Usare Classi di Caratteri Specifiche e Non Sovrapposte

Il backtracking esplode quando parti adiacenti di un pattern possono corrispondere agli stessi caratteri. Rendi ogni parte corrispondente a un insieme distinto così c'è un solo modo per dividere l'input. Ad esempio, preferisci \d+\.\d+ a [\d.]+\.[\d.]+, dove entrambi i gruppi [\d.]+ competono per lo stesso punto.

4. Ancorare e Limitare il Pattern

Ancorare con ^ e $ permette al motore di fallire rapidamente invece di ritentare la corrispondenza a ogni posizione nella stringa. Inserire un limite superiore esplicito su un quantificatore (a{1,20} invece di a+) limita il lavoro che ogni singola ripetizione può generare.

Esempi Pratici e Soluzioni

Esempio 1: Corrispondenza di Tag HTML Annidati

Un caso d'uso comune per le regex è la corrispondenza di tag HTML annidati, che può facilmente portare al backtracking catastrofico se non gestita correttamente. Nota: Le espressioni regolari sono generalmente inadatte per il parsing di strutture HTML arbitrarie o profondamente annidate; usa un parser HTML appropriato per documenti complessi.

Pattern Problematico

Pattern Migliorato

Sostituisci il .* greedy (che può inghiottire l'intero documento e poi retrocedere lentamente) con una classe che non può attraversare la parentesi angolare di chiusura. [^<]* corrisponde a tutto fino al < successivo, quindi non c'è sovrapposizione su cui fare backtracking.

Esempio 2: Validazione di una Lista di Identificatori

Pattern Problematico

([a-zA-Z0-9_]+)+ è la stessa trappola di (a+)+: il + interno e il + esterno si ripetono entrambi sugli stessi caratteri, quindi un input lungo senza corrispondenza innesca il backtracking esponenziale.

Un'Alternanza Sicura

Non ogni gruppo quantificato è pericoloso. (?:ab|cd)+e va bene: ab e cd sono disgiunti, quindi il motore non deve mai dubitare di come ha diviso l'input. Usa un gruppo non acquisiente (?:...) quando non hai bisogno del testo acquisito — è leggermente più veloce e più chiaro, anche se non cambia il comportamento del backtracking qui.

Conclusione

Il backtracking catastrofico può bloccare un'applicazione JavaScript — e poiché è innescato dall'input, è un vero rischio per la sicurezza, non solo un problema di prestazioni. La soluzione consiste quasi sempre nel rimuovere l'ambiguità: appiattire i quantificatori annidati, far corrispondere le parti adiacenti del pattern a insiemi di caratteri disgiunti, ancorare con ^/$, limitare le ripetizioni, o emulare un gruppo atomico con (?=(...))\1. Passare a quantificatori lazy non aiuta.

Quando scrivi una regex che viene eseguita su input non attendibile, testala con stringhe lunghe che falliscono (ad es. cento a seguite da !) e osserva i tempi. Se aggiungere un carattere in più aumenta notevolmente il tempo, il pattern è esponenziale e necessita di ristrutturazione.

Per approfondire, consulta i capitoli correlati su quantificatori, quantificatori greedy e lazy, gruppi acquisenti e classi di caratteri.

Esercitazione