On Interaction Effects in Greybox Fuzzing

1. Il Problema

Il greybox fuzzing basato su mutazione è una tecnica di testing automatizzato che genera nuovi input di prova applicando mutatori (es. inversione di bit, cancellazione di blocchi di byte) a un input seme (seed). Strumenti come AFL++ utilizzano una strategia di mutazione che seleziona i mutatori in base a probabilità fisse e predefinite, trattando ogni mutatore come indipendente dagli altri.

L'ipotesi centrale degli autori è che questa assunzione di indipendenza sia subottimale. Essi sostengono che esista un effetto di interazione tra i mutatori: l'ordine in cui vengono applicati due o più mutatori a un seme influenza la probabilità di generare un input "interessante" (ovvero, un input che copre nuovo codice o rivela bug). Le strategie attuali (come AFL++ o MOPT) ottimizzano la selezione dei singoli mutatori o usano probabilità fisse, ignorando il contesto del mutatore precedentemente applicato.

2. Metodologia

La ricerca si articola in tre fasi principali:

A. Investigazione dell'Effetto di Interazione (RQ1)

Per verificare l'esistenza dell'effetto di interazione, gli autori hanno:

1. Raccolta Dati: Eseguito AFL++ su 13 programmi target (benchmark FuzzBench) limitando la lunghezza delle sequenze di mutazione a 2 ($l=2$) e campionando i mutatori in modo uniforme per raccogliere dati su tutte le possibili coppie.
2. Modellazione Statistica: Adattato un modello lineare dove le variabili indipendenti sono i due mutatori ($i$ e $j$) e la variabile dipendente è il numero di input interessanti generati.
3. Analisi ANOVA: Eseguito un'ANOVA a due vie per testare la significatività del termine di interazione ($\gamma_{ij}$).
   • Risultato: L'analisi ha confermato che il termine di interazione spiega una porzione statisticamente significativa della varianza nei dati, dimostrando che la combinazione di certi mutatori produce più input interessanti di altre combinazioni.

B. Progettazione di MuoFuzz

Sulla base di questa scoperta, è stato sviluppato MuoFuzz, un fuzzer che apprende e utilizza le probabilità condizionate tra i mutatori. La strategia si divide in due fasi:

1. Fase di Addestramento (Training Phase): Per un periodo iniziale ($T_{train}$, es. 1 ora), MuoFuzz esegue mutazioni limitate a coppie ($l=2$) per costruire una matrice $N(i, j)$ che conta quanti input interessanti sono stati generati dalla sequenza $\langle i, j \rangle$. Da questa matrice, deriva la probabilità condizionata $P(m_n = j | m_{n-1} = i)$.
2. Fase di Mutazione Guidata (Guided Mutation Phase): Il fuzzer genera sequenze di mutatori di lunghezza arbitraria utilizzando un Random Walk (cammino casuale) su una catena di Markov. La selezione del prossimo mutatore $m_n$ dipende probabilisticamente dal mutatore precedente $m_{n-1}$, basandosi sulle probabilità apprese.

C. Valutazione Empirica

MuoFuzz è stato confrontato con:

• AFL++: Utilizza probabilità di selezione fisse.
• MOPT: Ottimizza le probabilità di selezione di ogni mutatore in isolamento (usando un algoritmo genetico), ma ignora le interazioni.

Gli esperimenti sono stati condotti su 13 programmi FuzzBench (copertura del codice) e 8 programmi MAGMA (trovata di bug), con 20-30 trial per programma per garantire validità statistica (test di Mann-Whitney U).

3. Contributi Chiave

1. Evidenza Empirica dell'Interazione: Dimostrazione statistica che l'ordine dei mutatori influisce sulle prestazioni del fuzzer, sfidando l'assunzione di indipendenza delle strategie attuali.
2. Nuova Strategia di Mutazione (MuoFuzz): Implementazione di una strategia che apprende le probabilità condizionate $P(next | previous)$, permettendo di generare sequenze di mutatori più promettenti.
3. Valutazione Comparativa: Dimostrazione che MuoFuzz supera gli stati dell'arte (AFL++ e MOPT) in termini di copertura del codice e numero di bug trovati.

4. Risultati

• Copertura del Codice: MuoFuzz ha raggiunto la copertura più alta in 10 su 13 programmi FuzzBench. In particolare, ha raggiunto la copertura finale ottenuta da AFL++ in 24 ore in soli 15 ore (in media), dimostrando un'efficienza temporale superiore.
• Scoperta di Bug:
  • MuoFuzz ha trovato 4 bug che AFL++ non ha rilevato.
  • Ha trovato 1 bug che né AFL++ né MOPT hanno rilevato.
  • Ha trovato lo stesso numero totale di bug di MOPT, ma bug diversi (ogni fuzzer ha trovato un bug unico che l'altro non ha visto), suggerendo che l'approccio basato sull'interazione esplora comportamenti del programma unici.
• Studio di Ablazione: Ha confermato che l'uso di più mutatori come contesto (es. $p=2$) peggiora le prestazioni a causa della "maledizione della dimensionalità" (sparsità dei dati), confermando che considerare solo il mutatore precedente è l'approccio ottimale. Inoltre, la selezione casuale del primo mutatore si è rivelata migliore di una selezione ponderata, poiché mantiene un livello di esplorazione più alto.

5. Significato e Implicazioni

Il lavoro dimostra che le strategie di mutazione nel greybox fuzzing possono essere significativamente migliorate passando da modelli di selezione indipendenti a modelli condizionati (simili ai modelli linguistici bigram).

• Efficienza: Riduce il tempo necessario per esplorare nuove aree del codice.
• Generalizzazione: Sebbene le probabilità apprese siano specifiche per programma, la metodologia è generale e applicabile a diversi fuzzers.
• Futuro della Ricerca: Apre la strada all'uso di tecniche di generazione di testo più avanzate (come RNN o Transformer) per la generazione di sequenze di mutazione e suggerisce di considerare non solo il mutatore precedente, ma anche la posizione nel file di input.

In sintesi, il paper stabilisce che l'interazione tra mutatori è un fattore critico e trascurato, e che sfruttarla tramite apprendimento automatico leggero (MuoFuzz) porta a un testing software più efficace ed efficiente.