2025-11-16T07:49:19.632070

Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing

Liu, Zhang, Cheng et al.
Fuzzing has become a cornerstone technique for uncovering vulnerabilities and enhancing the security of OS kernels. However, state-of-the-art kernel fuzzers, including the de facto standard Syzkaller, struggle to generate valid syscall sequences that respect implicit Syscall Dependency Relations (SDRs). Consequently, many generated seeds either fail kernel validation or cannot penetrate deep execution paths, resulting in significant inefficiency. We hypothesize that SDRs can be effectively learned from both historic and present kernel execution data, and that incorporating these learned relations into fuzzing can substantially improve seed validity and diversity. To validate this, we propose an approach that utilizes the N-gram model to mine SDRs from the Dongting dataset-one of the largest Linux kernel execution datasets available-as well as from execution traces collected on the fly during fuzzing. The resulting model is used to continuously augment the Choice Table of Syzkaller to improve its seed generation and demonstrably increases the Shannon Entropy of the Choice Table throughout fuzzing, reflecting more empirically-grounded choices in expanding syscall sequences into valid and diverse seeds. In addition, we introduce a Random Walk strategy that instructs Syzkaller to construct seeds in a bidirectional manner to further diversify the generated seeds. We implement our approach in a prototype, Psyzkaller, built on top of Syzkaller. Experiments on three representative Linux kernel versions show that Psyzkaller improves Syzkaller's code coverage by 4.6%-7.0% in 48-hour fuzzing, while triggering 110.4%-187.2% more crashes. Moreover, our investigation shows that Psyzkaller discovered eight previously unknown kernel vulnerabilities, compared to only one found by Syzkaller.
academic

Psyzkaller: Apprendimento dai Dati di Esecuzione Storici e in Tempo Reale per la Generazione Intelligente di Semi nel Fuzzing del Kernel del Sistema Operativo

Informazioni Fondamentali

  • ID Articolo: 2510.08918
  • Titolo: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • Autori: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • Classificazione: cs.CR (Crittografia e Sicurezza)
  • Data di Pubblicazione: 13 ottobre 2025
  • Link Articolo: https://arxiv.org/abs/2510.08918v1

Riassunto

Il fuzzing è diventato una tecnologia fondamentale per scoprire vulnerabilità nel kernel del sistema operativo e migliorare la sicurezza. Tuttavia, i fuzzer kernel più avanzati, incluso lo standard de facto Syzkaller, incontrano difficoltà nel generare sequenze di chiamate di sistema efficaci che rispettino le relazioni di dipendenza implicite delle chiamate di sistema (SDRs). Di conseguenza, molti semi generati non superano la validazione del kernel o non riescono a penetrare profondamente i percorsi di esecuzione, causando inefficienze significative. Questo articolo ipotizza che gli SDRs possono essere appresi efficacemente dai dati di esecuzione del kernel storici e attuali, e che l'incorporazione di queste relazioni apprese nel fuzzing può migliorare significativamente la validità e la diversità dei semi. Per verificare questa ipotesi, gli autori propongono un metodo che utilizza modelli N-gram per estrarre gli SDRs dal dataset DongTing (uno dei più grandi dataset di esecuzione del kernel Linux) e dalle tracce di esecuzione raccolte in tempo reale durante il processo di fuzzing.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il kernel del sistema operativo è un componente critico delle piattaforme informatiche moderne, e un compromesso a livello di kernel consente agli attaccanti di ottenere il controllo completo del sistema. I problemi fondamentali affrontati dai fuzzer kernel attuali sono:

  1. Difficoltà nell'Identificazione delle Relazioni di Dipendenza delle Chiamate di Sistema (SDRs): Molte sequenze di chiamate di sistema (SCSs) generate sono invalide perché violano gli SDRs
  2. Inefficienza nella Generazione dei Semi: I casi di test invalidi falliscono prematuramente, contribuendo poco all'esplorazione del codice
  3. Difficoltà nel Raggiungimento di Percorsi di Esecuzione Profonda: Mancanza di comprensione dei vincoli semantici tra le chiamate di sistema

Limitazioni dei Metodi Esistenti

  • Syzkaller: Utilizza modelli di chiamate di sistema per forzare la correttezza sintattica, ma non riesce a catturare dipendenze più profonde
  • Metodi di Analisi Statica: Elevato costo computazionale, difficili da implementare in ambienti di fuzzing ad alto throughput
  • Metodi di Machine Learning Esistenti: Dati limitati disponibili durante il fuzzing, impossibili da catturare completamente gli SDRs

Motivazione della Ricerca

Gli autori propongono una nuova prospettiva di apprendimento degli SDRs direttamente dalle tracce di esecuzione del kernel, combinando la copertura estesa dei dati storici con l'adattabilità dell'apprendimento online.

Contributi Fondamentali

  1. Propone una nuova strategia per apprendere gli SDRs combinando dati di esecuzione del kernel storici e in tempo reale, con ampia copertura e adattabilità alla versione del kernel
  2. Sviluppa il prototipo Psyzkaller, integrando l'apprendimento degli SDRs basato su Bigram e la strategia RandomWalk nel flusso di lavoro di Syzkaller
  3. Esegue il pre-addestramento del modello Bigram utilizzando il più grande dataset storico di esecuzione del kernel Linux (DongTing)
  4. Verifica l'efficacia su tre versioni rappresentative del kernel Linux, dimostrando superiorità nella copertura dei rami e nella rilevazione di vulnerabilità

Spiegazione Dettagliata del Metodo

Definizione del Compito

Input: Dataset di esecuzione del kernel storico C e risultati di fuzzing in tempo reale Output: Tabella di Scelta Migliorata, per guidare la generazione di sequenze di chiamate di sistema più efficaci Obiettivo: Migliorare la validità dei semi, la diversità e la capacità di scoperta di vulnerabilità

Architettura del Modello

1. Selezione del Modello N-gram

Adotta il modello Bigram (N=2) per apprendere gli SDRs, basato sulle seguenti considerazioni:

  • Efficienza dei Dati: I modelli N-gram funzionano meglio dei modelli DNN su dataset piccoli
  • Efficienza Computazionale: Il costo computazionale dell'aggiornamento della matrice Bigram è minimo
  • Interpretabilità: Gli SDRs sono rappresentati come probabilità di transizione tra chiamate di sistema, facili da comprendere e verificare

Calcolo della Probabilità Bigram:

P(wj|wi) = count(wiwj) / count(wi)

2. Matrice di Probabilità delle Relazioni (RPM)

Costruisce la matrice RPM, dove RPM[i]j registra la probabilità di invocare la chiamata di sistema wj immediatamente dopo wi.

Algoritmo 1: LearnSDR

Input: C (corpus di sequenze di chiamate di sistema), CallNum (numero totale di chiamate di sistema nel kernel)
Output: M (modello N-gram appreso da C)

1. Inizializza la matrice M e l'array di conteggio Count
2. Itera su ogni sequenza sc nel corpus C:
   - Conta le coppie di chiamate di sistema che appaiono consecutivamente
   - Aggiorna le statistiche di conteggio
3. Calcola le probabilità di transizione: M[i][j] = M[i][j] / Count[i]

3. Selezione delle Fonti di Dati

Combina due tipi di dati di esecuzione:

  • Dati Storici: Dataset DongTing (85GB, 18.966 sequenze di chiamate di sistema)
    • Sequenze normali: 6.850 (provenienti da suite di test LTP, Kselftests, ecc.)
    • Sequenze anomale: 12.116 (provenienti da rapporti di crash di Syzbot)
  • Dati in Tempo Reale: Tracce di esecuzione raccolte durante il processo di fuzzing

4. Integrazione della Tabella di Scelta Migliorata

Costruisce la Tabella di Scelta Migliorata (ACT):

ACT[i][j] = CTst[i][j] + CTdyn[i][j] + DTN[i][j] + CorpusN[i][j]

Dove:

  • CTst: Valore statico (conoscenza dello sviluppatore)
  • CTdyn: Valore dinamico (feedback del kernel)
  • DTN: RPM addestrata da dati storici
  • CorpusN: RPM addestrata da dati in tempo reale

5. Strategia RandomWalk

Introduce una strategia di estensione bidirezionale per aumentare la diversità dei semi:

Algoritmo 2: GenRandomWalk

  • Data una sequenza parziale w1·w2...wk
  • Può estendersi in avanti: seleziona w tale che ACT[wk]w > 0
  • Può estendersi all'indietro: seleziona w tale che ACT[w]w1 > 0
  • Sceglie casualmente la direzione di estensione (probabilità 0,5 ciascuna)

Punti di Innovazione Tecnica

  1. Fusione di Dati Dual-Source: Prima integrazione sistematica di dati storici su larga scala e apprendimento in tempo reale
  2. Aumento dell'Entropia di Shannon: Migliora significativamente l'entropia di Shannon della Tabella di Scelta (da 1,50 a 3,30-3,50 bit)
  3. Strategia di Bilanciamento dei Pesi: Bilancia l'influenza delle tracce normali e anomale attraverso pesi configurabili
  4. Generazione di Semi Bidirezionale: La strategia RandomWalk supera i limiti dell'estensione unidirezionale tradizionale

Configurazione Sperimentale

Dataset

  • Dataset DongTing: 85GB, copre versioni del kernel Linux 4.13-5.17
  • Versioni del Kernel Testate: Linux 5.19, 6.1, 6.12
  • Pre-elaborazione: Utilizza lo strumento trace2syz per la conversione al formato Syzkaller

Metriche di Valutazione

  • Copertura dei Rami: Misura la profondità dell'esplorazione del codice
  • Numero di Crash: Valuta la capacità di scoperta di vulnerabilità
  • Entropia di Shannon: Quantifica la diversità della Tabella di Scelta
  • Scoperta di Vulnerabilità: Numero di vulnerabilità sconosciute scoperte di recente

Metodi di Confronto

  • Syzkaller: Metodo di base
  • Healer: Fuzzer kernel all'avanguardia per l'apprendimento degli SDRs

Dettagli di Implementazione

  • Durata Esperimento: 48 ore per esecuzione, media di 3 ripetizioni
  • Rapporto di Peso: Test di tre rapporti di peso tracce normali/anomale: 1:1, 1:2, 2:1
  • Ambiente Hardware: Stesso server utilizzato per diverse versioni del kernel per garantire equità

Risultati Sperimentali

Risultati Principali

Miglioramento della Copertura dei Rami

  • Rispetto a Syzkaller: Miglioramento del 4,6%-7,0%
  • Rispetto a Healer: Significativamente superiore al miglioramento dello 0,4%-4,0% di Healer

Capacità di Rilevamento dei Crash

  • Aumento del Numero di Crash: 110,4%-187,2% (1.206 vs 516)
  • Generazione di PoC: 355 PoC validi (Syzkaller solo 70)

Scoperta di Vulnerabilità

  • Scoperta di Nuove Vulnerabilità: 8 vulnerabilità sconosciute (Syzkaller solo 1)
  • Tipo di Vulnerabilità: Principalmente vulnerabilità correlate a deadlock (6/8)

Esperimenti di Ablazione

Impatto del Rapporto di Peso (RQ1)

  • Configurazione Ottimale: Rapporto di peso 1:1 mostra le migliori prestazioni su tutte le versioni del kernel
  • Effetto di Bilanciamento: Il peso uguale bilancia l'esplorazione dei percorsi e la specificità del targeting di vulnerabilità

Effetto della Combinazione di Strategie (RQ2)

  • Combinazione Ottimale: Abilitazione di tutte le strategie (C+R+D) ottiene le migliori prestazioni
  • Contributi Individuali:
    • Apprendimento in Tempo Reale (C): Copertura dei rami più elevata
    • Dati Storici (D): Più rilevamento di crash
    • RandomWalk (R): Aumenta la diversità dei semi

Analisi di Casi

Vulnerabilità di Deadlock Triplo

Una vulnerabilità tipica scoperta coinvolge tre thread che contendono per i blocchi delle risorse:

  • Thread A: blk_mq_freeze_queue → loop_reconfigure_limits
  • Thread B e C: Formano complesse relazioni di dipendenza dei blocchi
  • Condizione di Trigger: Richiede una sequenza precisa di chiamate di sistema

La scoperta di questo tipo di vulnerabilità complessa dimostra l'efficacia di Psyzkaller nell'apprendimento degli SDRs.

Lavori Correlati

Generazione di Specifiche di Chiamate di Sistema

  • DIFUZE: Analisi statica per dedurre descrizioni di interfacce di dispositivi
  • SyzGen: Combinazione di instrumentazione dinamica e analisi statica
  • SyzDescribe: Analisi della priorità dei moduli del kernel

Estrazione degli SDRs

  • HFL: Fuzzing ibrido combinato con esecuzione simbolica
  • Healer: Rimozione iterativa di chiamate di sistema per valutare l'impatto sulla copertura
  • MOCK: Modello di linguaggio neurale per guidare la mutazione dei semi
  • ACTOR: Apprendimento delle dipendenze delle chiamate di sistema su oggetti kernel condivisi

Vantaggi di Questo Articolo

Rispetto ai metodi esistenti, questo articolo fornisce:

  • Migliore interpretabilità (rappresentazione delle probabilità di transizione)
  • Maggiore efficienza computazionale (operazioni su matrice leggera)
  • Controllo a grana fine (influenza relativa dell'esecuzione normale/anomala)

Conclusioni e Discussione

Conclusioni Principali

  1. Efficacia dell'Apprendimento degli SDRs: L'apprendimento degli SDRs dai dati storici e in tempo reale migliora significativamente l'efficacia del fuzzing
  2. Vantaggi della Fusione di Dati: La strategia che combina l'ampiezza storica e l'adattabilità in tempo reale è ottimale
  3. Verifica della Praticità: Dimostra miglioramenti significativi delle prestazioni su versioni reali del kernel

Limitazioni

  1. Limitazioni della Dipendenza Semantica: Le relazioni di chiamate di sistema consecutive catturate da Bigram non sempre corrispondono a vere dipendenze semantiche
  2. Evoluzione della Versione del Kernel: L'efficacia dei dati storici su nuove versioni del kernel potrebbe diminuire
  3. Complessità Computazionale: La complessità degli N-gram cresce esponenzialmente con l'aumento di N

Direzioni Future

  1. Miglioramento della Comprensione Semantica: Combinare il codice sorgente delle chiamate di sistema e la documentazione per estrarre SDRs più accurati
  2. Espansione dell'Ambito di Applicazione: Applicare gli SDRs appresi ad altre fasi come mutazione dei semi e pianificazione
  3. Integrazione dell'Apprendimento per Rinforzo: Combinare con strategie di fuzzing basate su apprendimento per rinforzo

Valutazione Approfondita

Punti di Forza

  1. Forte Innovazione Metodologica: Prima integrazione sistematica di dati storici su larga scala e apprendimento in tempo reale
  2. Esperimenti Completi e Approfonditi: Tre versioni del kernel, molteplici configurazioni, dettagliati esperimenti di ablazione
  3. Alto Valore Pratico: Scoperta di 8 nuove vulnerabilità, dimostra valore di sicurezza effettivo
  4. Fondamenti Teorici Solidi: Utilizza l'entropia di Shannon per quantificare i miglioramenti

Insufficienze

  1. Limitazioni Metodologiche: Dipende dalle relazioni di chiamate di sistema consecutive, potrebbe perdere dipendenze a lunga distanza
  2. Dipendenza dai Dati: Fortemente dipendente dalla qualità del dataset DongTing
  3. Problemi di Scalabilità: La dimensione della matrice cresce quadraticamente con il numero di chiamate di sistema

Impatto

  1. Contributo Accademico: Fornisce un nuovo metodo guidato dai dati per il fuzzing del kernel
  2. Valore Pratico: Può essere integrato direttamente nel flusso di lavoro Syzkaller esistente
  3. Riproducibilità: Basato su strumenti open source e dataset pubblici

Scenari Applicabili

  • Test di sicurezza del kernel Linux
  • Ottimizzazione della generazione di sequenze di chiamate di sistema
  • Miglioramento degli strumenti di fuzzing del kernel
  • Ricerca sulla sicurezza del sistema operativo

Riferimenti Bibliografici

L'articolo cita 44 riferimenti correlati, che coprono:

  • Strumenti di fuzzing del kernel (Syzkaller, Healer, ecc.)
  • Metodi di machine learning (N-gram, Word2Vec, Transformers)
  • Dataset di esecuzione del kernel (DongTing, ADFA-LD, ecc.)
  • Metodi di estrazione delle relazioni di dipendenza delle chiamate di sistema

Valutazione Complessiva: Questo è un articolo di ricerca sulla sicurezza dei sistemi di alta qualità che propone un metodo innovativo guidato dai dati per risolvere problemi chiave nel fuzzing del kernel. La progettazione sperimentale è rigorosa, i risultati sono convincenti e possiede importante valore accademico e pratico significativo.