💻 computer science

PUFFERDOS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

Questo articolo introduce PUFFERDOS, uno strumento innovativo che genera stringhe di attacco ReDoS pratiche ed efficaci sintetizzando input basati su tre pattern vulnerabili formalmente verificati e perfezionandoli attraverso l'esecuzione concolica composizionale per garantire l'esprimibilità nel mondo reale entro budget di lunghezza realistici.

Autori originali: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Pubblicato 2026-06-19

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Shangzhi Xu, Ziqi Ding, Xiao Cheng, Yuekang Li, Nan Sun, Benjamin Turnbull, Shuangxiang Kan, Siqi Ma

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di avere un guardia giurata molto intelligente, ma leggermente ossessivo, alla porta di un edificio. Il suo compito è controllare se la tua carta d'identità (l'input) corrisponde a un modello specifico (l'espressione regolare, o "regex"). Di solito, questo è veloce e facile.

Ma c'è un trucco. Se fornisci al guardia una carta d'identità molto specifica e confondente, il suo cervello si incastra in un loop. Inizia a controllare ogni singola modalità possibile in cui la tua carta potrebbe corrispondere al modello, ancora e ancora, finché non esaurisce le energie e sviene. Questo è chiamato un attacco ReDoS (Regular Expression Denial of Service). È come truccare una calcolatrice per farle fare calcoli all'infinito in modo che si blocchi.

Per molto tempo, i ricercatori di sicurezza hanno cercato di trovare queste trappole e di creare "ID di test" per dimostrare che il guardia è difettoso. Tuttavia, i vecchi metodi avevano due grandi problemi:

Gli ID erano troppo lunghi: richiedevano input così enormi (come un intero libro di testo) che nessun vero sito web li accetterebbe mai.
Non si adattavano all'edificio: testavano il guardia in isolamento, ignorando il fatto che in un vero edificio ci sono altri guardie (filtri) che potrebbero fermare la tua carta d'identità prima ancora che raggiunga la porta principale.

Ecco PUFFERDOS. Pensa a PUFFERDOS come a un maestro fabbro che non si limita a scassinare la serratura; capisce esattamente come camminare attraverso l'intero edificio per arrivare alla serratura, usando la chiave più corta e più efficiente possibile.

Ecco come funziona PUFFERDOS, suddiviso in semplici passaggi:

1. La strategia del "Punto di Arresto" (Far lavorare di più il guardia)

I ricercatori si sono resi conto che per far congelare il guardia non serve solo un modello confondente; serve un modello dove il guardia debba compiere passi minuscoli e inefficienti.

L'analogia: Immagina che il guardia stia camminando in un corridoio. Se lo costringi a fermarsi ad ogni singolo pollice per controllare il pavimento, si stancherà velocemente. Se si ferma solo ogni 3 metri, si stancherà più lentamente.
La soluzione: PUFFERDOS crea "chiavi" (stringhe di attacco) che costringono il guardia a fermarsi a ogni singolo millimetro. Lo fa scegliendo accuratamente caratteri specifici e disponendoli in modo che il guardia debba tornare indietro (backtrack/tornare indietro per controllare di nuovo) il più spesso possibile. Questo rende l'attacco migliaia di volte più veloce rispetto ai metodi precedenti perché ottiene lo stesso effetto di "congelamento" con una chiave molto più corta.

2. I tre modelli di "Trappola"

Il team ha scoperto che la maggior parte delle serrature rotte appartiene a tre forme specifiche. PUFFEDOS ha una ricetta speciale per ciascuna:

La Trappola a Un Solo Loop: Un singolo modello che può essere letto in modi multipli e confondenti. PUFFEDOS sceglie il carattere più corto e confondente da ripetere.
La Trappola a Due Loop: Due modelli vicini che possono leggere lo stesso carattere. PUFFEDOS usa un carattere che entrambi i modelli possono leggere, costringendoli a discutere su chi debba elaborarlo.
La Trappola a Multi-Loop: Una lunga catena di modelli. PUFFEDOS costruisce una chiave che costringe il guardia a controllare ogni singolo anello della catena individualmente.

3. Il "Percorso nel Mondo Reale" (Esecuzione Concolic)

Questa è la parte più importante. I vecchi strumenti testavano la serratura nel vuoto. PUFFEDOS simula l'intero edificio.

L'analogia: Immagina di avere una chiave che apre una porta, ma la porta si trova dietro un checkpoint di sicurezza, un receptionist e un labirinto. I vecchi strumenti ti mostravano solo che la chiave funziona sulla porta. PUFFEDOS ti guida attraverso il labirinto, controlla se il receptionist ti lascia passare e si assicura che tu raggiunga effettivamente la porta.
Il metodo: Utilizza una tecnica chiamata "esecuzione concolic composizionale". Pensa a questo come a un riassunto della mappa. Invece di percorrere ogni singolo passo dell'edificio ogni volta, PUFFEDOS crea un "foglio di trucchi" per ogni stanza (funzione) dell'edificio. Chiede: "Se do a questa stanza una chiave confondente, la passa alla stanza successiva o la scarta?".
Usando questi fogli di trucchi, PUFFEDOS può capire rapidamente se una chiave corta ed efficiente raggiungerà effettivamente la serratura vulnerabile in un programma reale, o se verrà bloccata da un filtro prima del processo.

I Risultati

Il team ha testato PUFFEDOS su migliaia di programmi reali e su vulnerabilità note (CVE).

Velocità: Ha generato stringhe di attacco che erano da 97 a 3.800 volte più efficienti rispetto al precedente miglior strumento. Poteva congelare un sistema con una stringa minuscola invece di una enorme.
Tasso di successo: Ha ricreato con successo il 96,8% delle vulnerabilità note (rispetto al 77,4% del vecchio strumento).
Nuove scoperte: Quando hanno testato PUFFEDOS su 12 popolari progetti software reali, hanno trovato 59 nuove vulnerabilità, precedentemente sconosciute, che i vecchi strumenti avevano mancato perché non riuscivano a generare un attacco realistico e abbastanza corto per dimostrare che la vulnerabilità esisteva.

In breve: PUFFEDOS è un modo più intelligente e pratico per trovare e dimostrare che un sistema informatico può essere bloccato da un modello confondente. Non si limita a trovare la serratura; trova la chiave più corta e realistica per incastrarla, dimostrando che il pericolo è reale e deve essere risolto.

Riepilogo Tecnico: PUFFERDOS

Definizione del Problema

Gli attacchi di Regular Expression Denial of Service (ReDoS) sfruttano il comportamento patologico del caso peggiore di esecuzione dei motori regex basati su backtracking, costringendo l'engine a esplorare un numero superlineare o esponenziale di percorsi di corrispondenza. Ciò consuma risorse della CPU in modo eccessivo, portando alla degradazione del servizio o all'indisponibilità. Sebbene esistano numerosi strumenti di rilevamento per identificare regex vulnerabili e generare stringhe di prova di concetto (PoC), gli approcci attuali soffrono di due criticità fondamentali che ne ostacolano l'effettiva esploitabilità pratica:

Lunghezze di Input Impraticabili: Gli strumenti esistenti spesso generano stringhe di attacco irrealisticamente lunghe (ad esempio, richiedendo centinaia di migliaia di caratteri) per innescare un rallentamento significativo. Nelle implementazioni reali, i vincoli di input (come i limiti degli header HTTP) spesso troncano queste stringhe prima che possano raggiungere la regex vulnerabile, rendendo l'attacco inefficace.
Mancanza di Validazione a Livello di Programma: Molte stringhe generate vengono validate solo rispetto alla regex in isolamento. Esse non tengono conto dei vincoli di flusso dei dati, della logica di filtraggio o della troncatura dell'input all'interno del programma ospite. Di conseguenza, queste stringhe spesso non riescono a raggiungere la regex vulnerabile in un contesto di esecuzione reale, portando gli sviluppatori a scartare le vulnerabilità segnalate come a bassa severità o non sfruttabili.

Metodologia

Gli autori propongono PUFFERDOS, un framework ibrido progettato per sintetizzare stringhe di attacco che siano sia efficienti (massimizzando il costo di corrispondenza entro budget di lunghezza realistici) sia efficaci (validate per raggiungere la regex vulnerabile nel programma effettivo). La metodologia consiste in tre componenti principali:

1. Analisi Formale e Tassonomia dei Pattern

Gli autori formalizzano innanzitutto la relazione tra la struttura della stringa di attacco e il costo di corrispondenza. Attraverso prove formali (Lemmi 3.2–3.4 e Teorema 3.5), stabiliscono che il costo di corrispondenza aumenta quando:

Le unità di ripetizione sono il più brevi possibile.
Le unità di ripetizione sono selezionate dall'intersezione degli alfabeti di espressioni di loop (LE) adiacenti, permettendo a più LE di consumare lo stesso sottostring.
I punti di arresto (indici in cui le LE terminano) sono separati piuttosto che intercalati, costringendo l'engine a rielaborare segmenti di input più lunghi durante il backtracking.

Sulla base di ciò, definiscono tre pattern vulnerabili per guidare la generazione delle stringhe:

Exponential One-Loop (EOL): Una singola LE con sottorex di srotolamento (unfolding) aventi alfabeti sovrapposti.
Loop-Intersect-Loop (LIL): Due LE adiacenti separate da un segmento non-loop che può essere corrisposto da entrambe le LE.
Polynomial Multi-Loop (PML): LE adiacenti con alfabeti o separatori disgiunti che non possono essere consumati da entrambe.

2. Generazione di Stringhe di Attacco Guidata dalla Struttura

PUFFERDOS analizza le regex vulnerabili in un albero di sintassi astratta (rAST) per identificare il pattern vulnerabile specifico (EOL, LIL o PML). Successivamente sintetizza stringhe di attacco candidate ( $s_a = x \cdot y^q \cdot z$ ) utilizzando regole specifiche per il pattern:

Generazione dell'Infix: Seleziona l'unità di ripetizione più breve ( $y$ ) dall'intersezione dell'alfabeto delle LE rilevanti. Per i pattern con più LE, concatena unità ripetute indipendentemente per garantire che i punti di arresto siano separati, massimizzando i passaggi di backtracking.
Costruzione di Prefisso/Suffisso: Deriva il prefisso ( $x$ ) dal prefisso non-loop della regex e il suffisso ( $z$ ) dal suffisso non-loop, assicurando che la stringa finale sia rifiutata dalla regex per innescare un backtracking esaustivo.

3. Raffinamento Concolico Composizionale Specifico per ReDoS

Per garantire che la stringa generata raggiunga la regex vulnerabile in un programma reale, PUFFERDOS impiega una strategia di esecuzione concolica composizionale:

Estrazione del Percorso: Costruisce un grafo delle chiamate per identificare i percorsi fattibili dai punti di ingresso del programma fino alla regex vulnerabile.
Summarization delle Funzioni: Esegue il testing concolico unitario sulle funzioni lungo il percorso per generare riassunti funzionali (function summaries) specifici per ReDoS. A differenza dei riassunti tradizionali, questi sono potati per mantenere solo i comportamenti rilevanti per la propagazione della stringa di attacco (ad esempio, trasformazioni identiche o ritorni costanti), scartando il ragionamento regex non correlato che causa l'esplosione dei percorsi.
Raffinamento a Livello di Sistema: Utilizza i riassunti per guidare l'esecuzione concolica a livello di sistema, risolvendo i vincoli interprocedurali per raffinare la stringa di attacco in modo da superare i filtri e raggiungere la regex target senza eccedere i budget di lunghezza dell'input realistici.

Contributi Chiave

Prova Formale di Efficienza: Il documento prova formalmente che la selezione di caratteri specifici e il loro ordinamento per separare i punti di arresto nelle LE adiacenti amplifica significativamente il costo di corrispondenza della regex. Ciò porta alla derivazione di tre pattern di regex vulnerabili e di regole di generazione provabilmente efficienti.
Framework PUFFERDOS: Lo sviluppo di un generatore ibrido che integra regole di generazione formali con il raffinamento concolico composizionale specifico per ReDoS. Questo approccio colma il divario tra il rilevamento teorico e l'effettiva esploitabilità, garantendo che le stringhe siano abbastanza brevi per i vincoli del mondo reale e valide all'interno del flusso di dati del programma.
Valutazione Esaustiva: Lo strumento è valutato su un corpus su larga scala di 17.962 regex vulnerabili, 31 CVE noti e 12 popolari progetti open-source.

Risultati

La valutazione dimostra miglioramenti significativi rispetto allo stato dell'arte rappresentato dallo strumento RENGAR:

Efficienza: PUFFERDOS genera stringhe di attacco che sono da 97,2× a 3.872,4× più corte di quelle prodotte da RENGAR, pur raggiungendo le stesse soglie di tempo di corrispondenza (0,1s, 1s e 10s).
Riproduzione di CVE: PUFFERDOS ha riprodotto con successo il 96,8% degli exploitati CVE di tipo ReDoS, rispetto al 77,4% di RENGAR.
Nuove Vulnerabilità: Applicato a 12 popolari progetti open-source, PUFFERDOS ha scoperto 59 istanze di ReDoS sfruttabili (25 in più rispetto a RENGAR). Gli sviluppatori di sei di questi progetti hanno validato 21 dei risultati trovati.
Impatto nel Mondo Reale: In un esempio motivante riguardante una libreria di evidenziazione della sintassi, PUFFERDOS ha generato una stringa di 1.000 caratteri che ha causato un blocco del sistema superiore a 4.000 secondi, mentre i metodi tradizionali richiedevano 500.000 caratteri e non riuscivano a innescare un blocco a causa della troncatura dell'input nel programma effettivo.

Significato

Il documento sostiene che l'utilità pratica del rilevamento ReDoS è attualmente limitata perché le stringhe di attacco generate sono spesso troppo lunghe o non riescono a propagarsi attraverso la logica del programma. Affrontando queste specifiche carenze, PUFFERDOS fornisce un meccanismo per generare prove di vulnerabilità praticamente sfruttabili. Ciò è significativo perché affronta direttamente il motivo per cui gli sviluppatori spesso ignorano i report ReDoS (percependo li come a bassa severità o non sfruttabili). Fornendo stringhe di attacco brevi e valide, PUFFERDOS consente una valutazione del rischio più accurata e facilita la rimedio delle vulnerabilità ReDoS nei sistemi software reali.