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: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing

Grundlegende Informationen

  • Papier-ID: 2510.08918
  • Titel: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • Autoren: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • Klassifizierung: cs.CR (Kryptographie und Sicherheit)
  • Veröffentlichungsdatum: 13. Oktober 2025
  • Papierlink: https://arxiv.org/abs/2510.08918v1

Zusammenfassung

Fuzzing hat sich als Grundlagentechnologie zur Entdeckung von Betriebssystem-Kernel-Schwachstellen und zur Verbesserung der Sicherheit etabliert. Allerdings haben hochmoderne Kernel-Fuzzer, einschließlich des De-facto-Standards Syzkaller, Schwierigkeiten bei der Generierung effektiver Systemaufrufssequenzen, die implizite Systemaufrufs-Abhängigkeitsbeziehungen (SDRs) respektieren. Folglich schlagen viele generierte Seeds entweder bei der Kernel-Validierung fehl oder können Ausführungspfade nicht tiefgreifend durchdringen, was zu erheblicher Ineffizienz führt. Dieses Papier geht davon aus, dass SDRs effektiv aus historischen und aktuellen Kernel-Ausführungsdaten gelernt werden können und dass die Einbeziehung dieser gelernten Beziehungen in das Fuzzing die Seed-Validität und -Vielfalt erheblich verbessern kann. Um dies zu überprüfen, schlagen die Autoren eine Methode vor, die N-gram-Modelle nutzt, um SDRs aus dem DongTing-Datensatz (einem der größten Linux-Kernel-Ausführungsdatensätze) sowie aus während des Fuzzing-Prozesses in Echtzeit erfassten Ausführungsspuren zu extrahieren.

Forschungshintergrund und Motivation

Problemdefinition

Der Betriebssystem-Kernel ist eine kritische Komponente moderner Computersysteme, und eine Sicherheitskompromittierung auf Kernel-Ebene ermöglicht es Angreifern, die vollständige Kontrolle über das System zu erlangen. Die Kernprobleme, mit denen aktuelle Kernel-Fuzzer konfrontiert sind, sind:

  1. Schwierigkeiten bei der Identifizierung von Systemaufrufs-Abhängigkeitsbeziehungen (SDRs): Viele generierte Systemaufrufssequenzen (SCSs) sind ungültig, da sie SDRs verletzen
  2. Ineffiziente Seed-Generierung: Ungültige Testfälle schlagen frühzeitig fehl und tragen wenig zur Code-Exploration bei
  3. Schwer erreichbare tiefe Ausführungspfade: Mangelndes Verständnis für semantische Einschränkungen zwischen Systemaufrufen

Einschränkungen bestehender Methoden

  • Syzkaller: Verwendet Systemaufrufs-Templates zur Erzwingung syntaktischer Korrektheit, kann aber tiefere Abhängigkeitsbeziehungen nicht erfassen
  • Statische Analysemethoden: Hohe Rechenkosten, schwierig in hochdurchsatzigen Fuzzing-Umgebungen einzusetzen
  • Bestehende Machine-Learning-Methoden: Begrenzte verfügbare Daten während des Fuzzing, können SDRs nicht umfassend erfassen

Forschungsmotivation

Die Autoren schlagen eine neue Perspektive vor, SDRs direkt aus Kernel-Ausführungsspuren zu lernen und dabei die umfassende Abdeckung historischer Daten mit der Adaptivität des Online-Lernens zu verbinden.

Kernbeiträge

  1. Vorschlag einer neuen Strategie zur Kombination historischer und Echtzeit-Kernel-Ausführungsdaten zum Lernen von SDRs, die sowohl umfassende Abdeckung als auch Kernel-Versions-Adaptivität bietet
  2. Entwicklung des Psyzkaller-Prototyps, der auf Bigram basierende SDR-Lernvorgänge und RandomWalk-Strategien in den Syzkaller-Workflow integriert
  3. Vortraining des Bigram-Modells mit dem größten historischen Linux-Kernel-Ausführungsdatensatz (DongTing)
  4. Validierung der Wirksamkeit auf drei repräsentativen Linux-Kernel-Versionen, die Überlegenheit bei Branch-Abdeckung und Schwachstellenerkennung demonstriert

Methodische Details

Aufgabendefinition

Eingabe: Historischer Kernel-Ausführungsdatensatz C und Echtzeit-Fuzzing-Ergebnisse Ausgabe: Erweiterte Choice Table zur Anleitung effektiverer Systemaufrufssequenz-Generierung Ziel: Verbesserung der Seed-Validität, -Vielfalt und Schwachstellenerkennungsfähigkeit

Modellarchitektur

1. N-gram-Modellauswahl

Verwendung eines Bigram-Modells (N=2) zum Lernen von SDRs, basierend auf folgenden Überlegungen:

  • Dateneffizienz: N-gram-Modelle zeigen bessere Leistung auf kleinen Datensätzen im Vergleich zu DNN-Modellen
  • Recheneffizienz: Minimale Rechenkosten für die Aktualisierung der Bigram-Matrix
  • Interpretierbarkeit: SDRs werden als Übergangwahrscheinlichkeiten zwischen Systemaufrufen dargestellt, leicht verständlich und überprüfbar

Bigram-Wahrscheinlichkeitsberechnung:

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

2. Beziehungswahrscheinlichkeitsmatrix (RPM)

Konstruktion einer RPM-Matrix, wobei RPM[i]j die Wahrscheinlichkeit aufzeichnet, dass Systemaufrufs wj unmittelbar nach wi aufgerufen wird.

Algorithmus 1: LearnSDR

Eingabe: C (Systemaufrufssequenz-Korpus), CallNum (Gesamtzahl der Systemaufrufe im Kernel)
Ausgabe: M (aus C gelerntes N-gram-Modell)

1. Initialisiere Matrix M und Zählarray Count
2. Durchlaufe jede Sequenz sc im Korpus C:
   - Zähle aufeinanderfolgend auftretende Systemaufrufspaare
   - Aktualisiere Zählstatistiken
3. Berechne Übergangwahrscheinlichkeiten: M[i][j] = M[i][j] / Count[i]

3. Datenquellenauswahl

Kombination zweier Arten von Ausführungsdaten:

  • Historische Daten: DongTing-Datensatz (85GB, 18.966 Systemaufrufssequenzen)
    • Normale Sequenzen: 6.850 (aus LTP, Kselftests und anderen Test-Suites)
    • Anomale Sequenzen: 12.116 (aus Syzbot-gemeldeten Abstürzen)
  • Echtzeit-Daten: Während des Fuzzing-Prozesses erfasste Ausführungsspuren

4. Integration erweiterter Choice Table

Konstruktion einer erweiterten Choice Table (ACT):

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

wobei:

  • CTst: Statische Werte (Entwicklerwissen)
  • CTdyn: Dynamische Werte (Kernel-Feedback)
  • DTN: RPM trainiert auf historischen Daten
  • CorpusN: RPM trainiert auf Echtzeit-Daten

5. RandomWalk-Strategie

Einführung einer bidirektionalen Erweiterungsstrategie zur Erhöhung der Seed-Vielfalt:

Algorithmus 2: GenRandomWalk

  • Gegeben eine Teilsequenz w1·w2...wk
  • Kann nach vorne erweitert werden: Wähle w, so dass ACT[wk]w > 0
  • Kann nach hinten erweitert werden: Wähle w, so dass ACT[w]w1 > 0
  • Wähle zufällig Erweiterungsrichtung (Wahrscheinlichkeit jeweils 0,5)

Technische Innovationspunkte

  1. Dual-Source-Datenfusion: Erstmalige systematische Kombination historischer großflächiger Daten und Online-Lernens
  2. Shannon-Entropie-Verbesserung: Signifikante Erhöhung der Shannon-Entropie der Choice Table durch SDR-Lernvorgänge (von 1,50 auf 3,30-3,50 Bits)
  3. Gewichtungsausgleichsstrategie: Konfigurierbare Gewichte zum Ausgleich der Auswirkungen normaler und anomaler Spuren
  4. Bidirektionale Seed-Generierung: RandomWalk-Strategie überwindet Beschränkungen traditioneller unidirektionaler Erweiterung

Experimentelle Einrichtung

Datensätze

  • DongTing-Datensatz: 85GB, Abdeckung der Linux-Versionen 4.13-5.17
  • Test-Kernel-Versionen: Linux 5.19, 6.1, 6.12
  • Vorverarbeitung: Verwendung des trace2syz-Tools zur Konvertierung in Syzkaller-Format

Bewertungsmetriken

  • Branch-Abdeckung: Messung der Code-Explorations-Tiefe
  • Absturzanzahl: Bewertung der Schwachstellenerkennungsfähigkeit
  • Shannon-Entropie: Quantifizierung der Choice-Table-Vielfalt
  • Schwachstellenerkennung: Anzahl neu entdeckter unbekannter Schwachstellen

Vergleichsmethoden

  • Syzkaller: Baseline-Methode
  • Healer: Hochmoderner SDR-Lernungs-Kernel-Fuzzer

Implementierungsdetails

  • Experimentdauer: Jeweils 48 Stunden, dreifache Wiederholung mit Mittelwertbildung
  • Gewichtsverhältnisse: Test von 1:1, 1:2, 2:1 Gewichtsverhältnissen normaler/anomaler Spuren
  • Hardware-Umgebung: Gleicher Server für verschiedene Kernel-Versionen zur Gewährleistung von Fairness

Experimentelle Ergebnisse

Hauptergebnisse

Branch-Abdeckungsverbesserung

  • Im Vergleich zu Syzkaller: Verbesserung um 4,6%-7,0%
  • Im Vergleich zu Healer: Signifikant besser als Healers Verbesserung um 0,4%-4,0%

Absturzerkennung

  • Anstieg der Absturzanzahl: 110,4%-187,2% (1.206 vs. 516)
  • PoC-Generierung: 355 gültige PoCs (Syzkaller nur 70)

Schwachstellenerkennung

  • Neue Schwachstellen entdeckt: 8 unbekannte Schwachstellen (Syzkaller nur 1)
  • Schwachstellentypen: Hauptsächlich Deadlock-bezogene Schwachstellen (6/8)

Ablationsstudien

Auswirkung des Gewichtsverhältnisses (RQ1)

  • Optimale Konfiguration: 1:1-Gewichtsverhältnis zeigt auf allen Kernel-Versionen beste Leistung
  • Ausgleichseffekt: Gleichgewichtung balanciert Pfaderkundung und Schwachstellen-Zielgerichtetheit

Effekt der Strategiekombination (RQ2)

  • Beste Kombination: Aktivierung aller Strategien (C+R+D) erreicht beste Leistung
  • Einzelne Beiträge:
    • Online-Lernvorgänge (C): Höhere Branch-Abdeckung
    • Historische Daten (D): Mehr Absturzerkennung
    • RandomWalk (R): Verbesserte Seed-Vielfalt

Fallstudien

Triple-Deadlock-Schwachstelle

Eine typische entdeckte Schwachstelle betrifft drei Threads, die um Ressourcensperren konkurrieren:

  • Thread A: blk_mq_freeze_queue → loop_reconfigure_limits
  • Thread B und C: Bilden komplexe Sperrabhängigkeitsbeziehungen
  • Auslösebedingung: Erfordert präzise Systemaufrufsreihenfolge

Die Entdeckung solch komplexer Schwachstellen demonstriert die Wirksamkeit des Psyzkaller-SDR-Lernens.

Verwandte Arbeiten

Systemaufrufs-Spezifikationsgenerierung

  • DIFUZE: Statische Analyse zur Inferenz von Geräteschnittstellen-Beschreibungen
  • SyzGen: Kombination dynamischer Instrumentierung und statischer Analyse
  • SyzDescribe: Analyse von Kernel-Modul-Prioritäten

SDR-Extraktion

  • HFL: Hybrid-Fuzzing kombiniert mit symbolischer Ausführung
  • Healer: Iteratives Entfernen von Systemaufrufen zur Bewertung von Abdeckungsauswirkungen
  • MOCK: Neuronale Sprachmodelle zur Anleitung von Seed-Mutation
  • ACTOR: Lernvorgänge für Systemaufrufs-Abhängigkeiten auf gemeinsamen Kernel-Objekten

Vorteile dieses Papiers

Im Vergleich zu bestehenden Methoden bietet dieses Papier:

  • Bessere Interpretierbarkeit (Übergangwahrscheinlichkeitsdarstellung)
  • Höhere Recheneffizienz (leichte Matrixoperationen)
  • Feinkörnige Kontrolle (relative Auswirkungen normaler/anomaler Ausführungen)

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Wirksamkeit des SDR-Lernens: Das Lernen von SDRs aus historischen und Echtzeit-Daten verbessert die Fuzzing-Leistung erheblich
  2. Vorteile der Datenfusion: Die Strategie, die historische Breite mit Echtzeit-Adaptivität kombiniert, ist optimal
  3. Praktizitätsvalidierung: Demonstriert signifikante Leistungsverbesserungen auf echten Kernel-Versionen

Einschränkungen

  1. Semantische Abhängigkeitsbeschränkungen: Bigram-erfasste aufeinanderfolgende Systemaufrufsbeziehungen entsprechen nicht immer echten semantischen Abhängigkeiten
  2. Kernel-Versions-Evolution: Gültigkeit historischer Daten auf neuen Kernel-Versionen kann abnehmen
  3. Rechenkomplexität: Mit zunehmendem N wächst die N-gram-Komplexität exponentiell

Zukünftige Richtungen

  1. Verbesserte semantische Erfassung: Kombination von Systemaufrufs-Quellcode und Dokumentation zur Extraktion genauerer SDRs
  2. Erweiterung des Anwendungsbereichs: Anwendung gelernter SDRs auf Seed-Mutation, Planung und andere Phasen
  3. Verstärkungslernintegration: Kombination mit auf Verstärkungslernen basierenden Fuzzing-Strategien

Tiefgehende Bewertung

Stärken

  1. Starke Methodische Innovation: Erstmalige systematische Kombination historischer großflächiger Daten und Online-Lernens
  2. Umfassende Experimente: Drei Kernel-Versionen, mehrere Konfigurationen, detaillierte Ablationsstudien
  3. Hoher praktischer Wert: Entdeckung von 8 neuen Schwachstellen, Demonstration tatsächlichen Sicherheitswerts
  4. Solide theoretische Grundlagen: Verwendung von Shannon-Entropie zur Quantifizierung von Verbesserungen

Mängel

  1. Methodische Einschränkungen: Abhängigkeit von aufeinanderfolgenden Systemaufrufsbeziehungen, kann Fernabhängigkeiten übersehen
  2. Datenabhängigkeit: Starke Abhängigkeit von DongTing-Datensatzqualität
  3. Skalierungsprobleme: Matrixgröße wächst quadratisch mit der Anzahl der Systemaufrufe

Auswirkungen

  1. Akademischer Beitrag: Bietet neue datengesteuerte Methoden für das Kernel-Fuzzing-Forschungsgebiet
  2. Praktischer Wert: Kann direkt in bestehende Syzkaller-Workflows integriert werden
  3. Reproduzierbarkeit: Basiert auf Open-Source-Tools und öffentlich verfügbaren Datensätzen

Anwendungsszenarien

  • Linux-Kernel-Sicherheitstests
  • Optimierung der Systemaufrufssequenz-Generierung
  • Verbesserung von Kernel-Fuzzing-Tools
  • Betriebssystem-Sicherheitsforschung

Referenzen

Das Papier zitiert 44 verwandte Literaturquellen, die folgende Bereiche abdecken:

  • Kernel-Fuzzing-Tools (Syzkaller, Healer usw.)
  • Machine-Learning-Methoden (N-gram, Word2Vec, Transformers)
  • Kernel-Ausführungsdatensätze (DongTing, ADFA-LD usw.)
  • Methoden zur Extraktion von Systemaufrufs-Abhängigkeitsbeziehungen

Gesamtbewertung: Dies ist ein hochqualitatives Forschungspapier im Bereich Systemsicherheit, das eine innovative datengesteuerte Methode zur Lösung kritischer Probleme beim Kernel-Fuzzing vorschlägt. Das Experimentdesign ist rigoros, die Ergebnisse sind überzeugend und das Papier hat bedeutende akademische und praktische Relevanz.