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 : Apprentissage à partir de données d'exécution historiques et en temps réel pour une génération de graines plus intelligente dans le fuzzing du noyau OS

Informations de base

  • ID de l'article : 2510.08918
  • Titre : Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • Auteurs : Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • Classification : cs.CR (Cryptographie et Sécurité)
  • Date de publication : 13 octobre 2025
  • Lien de l'article : https://arxiv.org/abs/2510.08918v1

Résumé

Le fuzzing est devenu une technique fondamentale pour découvrir les vulnérabilités du noyau du système d'exploitation et renforcer la sécurité. Cependant, les fuzzer de noyau les plus avancés, y compris Syzkaller qui est la norme de facto, éprouvent des difficultés à générer des séquences d'appels système efficaces qui respectent les dépendances implicites des appels système (SDRs). Par conséquent, de nombreuses graines générées échouent soit à la validation du noyau, soit ne parviennent pas à explorer profondément les chemins d'exécution, ce qui entraîne une inefficacité significative. Cet article suppose que les SDRs peuvent être apprises efficacement à partir de données d'exécution du noyau historiques et actuelles, et que l'intégration de ces relations apprises dans le fuzzing peut améliorer considérablement la validité et la diversité des graines. Pour valider cette hypothèse, les auteurs proposent une méthode utilisant des modèles N-gram pour extraire les SDRs à partir de l'ensemble de données DongTing (l'un des plus grands ensembles de données d'exécution du noyau Linux) ainsi que des traces d'exécution collectées en temps réel pendant le processus de fuzzing.

Contexte et motivation de la recherche

Définition du problème

Le noyau du système d'exploitation est un composant critique des plates-formes informatiques modernes, et un compromis au niveau du noyau permet aux attaquants d'obtenir un contrôle total du système. Les problèmes fondamentaux auxquels font face les fuzzer de noyau actuels sont :

  1. Difficulté d'identification des dépendances des appels système (SDRs) : De nombreuses séquences d'appels système (SCS) générées sont invalides car elles violent les SDRs
  2. Inefficacité de la génération de graines : Les cas de test invalides échouent prématurément et contribuent peu à l'exploration du code
  3. Difficulté d'atteindre les chemins d'exécution profonds : Manque de compréhension des contraintes sémantiques entre les appels système

Limitations des méthodes existantes

  • Syzkaller : Utilise des modèles d'appels système pour imposer la correction syntaxique, mais ne peut pas capturer les dépendances plus profondes
  • Méthodes d'analyse statique : Coût computationnel élevé, difficiles à déployer dans un environnement de fuzzing à haut débit
  • Méthodes d'apprentissage automatique existantes : Données limitées disponibles pendant le fuzzing, incapables de capturer complètement les SDRs

Motivation de la recherche

Les auteurs proposent une nouvelle perspective pour apprendre les SDRs directement à partir des traces d'exécution du noyau, combinant la couverture étendue des données historiques et l'adaptabilité de l'apprentissage en ligne.

Contributions principales

  1. Proposition d'une nouvelle stratégie combinant l'apprentissage des SDRs à partir de données d'exécution du noyau historiques et en temps réel, offrant à la fois une couverture étendue et une adaptabilité aux versions du noyau
  2. Développement du prototype Psyzkaller, intégrant l'apprentissage des SDRs basé sur Bigram et la stratégie RandomWalk dans le flux de travail Syzkaller
  3. Pré-entraînement du modèle Bigram en utilisant le plus grand ensemble de données d'exécution historiques du noyau Linux (DongTing)
  4. Validation de l'efficacité sur trois versions représentatives du noyau Linux, démontrant la supériorité en termes de couverture de branches et de détection de vulnérabilités

Détails de la méthode

Définition de la tâche

Entrée : Ensemble de données d'exécution du noyau historiques C et résultats de fuzzing en temps réel Sortie : Table de choix améliorée pour guider une génération de séquences d'appels système plus efficace Objectif : Améliorer la validité des graines, la diversité et la capacité de découverte de vulnérabilités

Architecture du modèle

1. Sélection du modèle N-gram

Adoption d'un modèle Bigram (N=2) pour apprendre les SDRs, basée sur les considérations suivantes :

  • Efficacité des données : Les modèles N-gram fonctionnent mieux que les modèles DNN sur les petits ensembles de données
  • Efficacité computationnelle : Le coût de calcul de la mise à jour de la matrice Bigram est minimal
  • Interprétabilité : Les SDRs sont représentées comme des probabilités de transition entre appels système, faciles à comprendre et à vérifier

Calcul de la probabilité Bigram :

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

2. Matrice de probabilité de relation (RPM)

Construction de la matrice RPM, où RPM[i]j enregistre la probabilité que l'appel système wj soit appelé immédiatement après wi.

Algorithme 1 : LearnSDR

Entrée : C (corpus de séquences d'appels système), CallNum (nombre total d'appels système dans le noyau)
Sortie : M (modèle N-gram appris à partir de C)

1. Initialiser la matrice M et le tableau de comptage Count
2. Parcourir chaque séquence sc dans le corpus C :
   - Compter les paires d'appels système consécutifs
   - Mettre à jour les statistiques de comptage
3. Calculer les probabilités de transition : M[i][j] = M[i][j] / Count[i]

3. Sélection des sources de données

Combinaison de deux types de données d'exécution :

  • Données historiques : Ensemble de données DongTing (85 Go, 18 966 séquences d'appels système)
    • Séquences normales : 6 850 (provenant des suites de test LTP, Kselftests, etc.)
    • Séquences anormales : 12 116 (provenant des rapports de crash Syzbot)
  • Données en temps réel : Traces d'exécution collectées pendant le processus de fuzzing

4. Intégration de la table de choix améliorée

Construction de la table de choix améliorée (ACT) :

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

Où :

  • CTst : Valeurs statiques (connaissances des développeurs)
  • CTdyn : Valeurs dynamiques (retours du noyau)
  • DTN : RPM entraînée à partir de données historiques
  • CorpusN : RPM entraînée à partir de données en temps réel

5. Stratégie RandomWalk

Introduction d'une stratégie d'extension bidirectionnelle pour augmenter la diversité des graines :

Algorithme 2 : GenRandomWalk

  • Étant donnée une séquence partielle w1·w2...wk
  • Peut s'étendre vers l'avant : sélectionner w tel que ACT[wk]w > 0
  • Peut s'étendre vers l'arrière : sélectionner w tel que ACT[w]w1 > 0
  • Choisir aléatoirement la direction d'extension (probabilité 0,5 chacune)

Points d'innovation technique

  1. Fusion de données bidirectionnelles : Première combinaison systématique de données historiques à grande échelle et d'apprentissage en temps réel
  2. Amélioration de l'entropie de Shannon : Augmentation significative de l'entropie de Shannon de la table de choix (de 1,50 à 3,30-3,50 bits) grâce à l'apprentissage des SDRs
  3. Stratégie d'équilibrage des poids : Équilibrage de l'influence des trajectoires normales et anormales par des poids configurables
  4. Génération de graines bidirectionnelle : La stratégie RandomWalk dépasse les limitations de l'extension unidirectionnelle traditionnelle

Configuration expérimentale

Ensemble de données

  • Ensemble de données DongTing : 85 Go, couvrant les versions du noyau Linux 4.13-5.17
  • Versions du noyau testées : Linux 5.19, 6.1, 6.12
  • Prétraitement : Utilisation de l'outil trace2syz pour la conversion au format Syzkaller

Métriques d'évaluation

  • Couverture de branches : Mesure de la profondeur d'exploration du code
  • Nombre de crash : Évaluation de la capacité de découverte de vulnérabilités
  • Entropie de Shannon : Quantification de la diversité de la table de choix
  • Découverte de vulnérabilités : Nombre de vulnérabilités inconnues nouvellement découvertes

Méthodes de comparaison

  • Syzkaller : Méthode de base
  • Healer : Fuzzer de noyau d'apprentissage des SDRs de pointe

Détails de mise en œuvre

  • Durée des expériences : 48 heures par exécution, répétées 3 fois et moyennes
  • Ratios de poids : Test de trois ratios de poids trajectoires normales/anormales : 1:1, 1:2, 2:1
  • Environnement matériel : Utilisation du même serveur pour différentes versions du noyau pour assurer l'équité

Résultats expérimentaux

Résultats principaux

Amélioration de la couverture de branches

  • Par rapport à Syzkaller : Amélioration de 4,6 % à 7,0 %
  • Par rapport à Healer : Significativement supérieur à l'amélioration de 0,4 % à 4,0 % de Healer

Capacité de détection de crash

  • Augmentation du nombre de crash : 110,4 % à 187,2 % (1 206 vs 516)
  • Génération de PoC : 355 PoC valides (Syzkaller n'en a que 70)

Découverte de vulnérabilités

  • Découverte de nouvelles vulnérabilités : 8 vulnérabilités inconnues (Syzkaller n'en a découvert que 1)
  • Types de vulnérabilités : Principalement des vulnérabilités liées aux interblocages (6/8)

Expériences d'ablation

Impact du ratio de poids (RQ1)

  • Configuration optimale : Le ratio de poids 1:1 offre les meilleures performances sur toutes les versions du noyau
  • Effet d'équilibrage : L'équipondération équilibre l'exploration des chemins et la ciblage des vulnérabilités

Effet de la combinaison de stratégies (RQ2)

  • Meilleure combinaison : L'activation de toutes les stratégies (C+R+D) obtient les meilleures performances
  • Contributions individuelles :
    • Apprentissage en temps réel (C) : Couverture de branches plus élevée
    • Données historiques (D) : Détection de crash plus importante
    • RandomWalk (R) : Amélioration de la diversité des graines

Analyse de cas

Vulnérabilité d'interblocage triple

Une vulnérabilité typique découverte implique trois threads en compétition pour les verrous de ressources :

  • Thread A : blk_mq_freeze_queue → loop_reconfigure_limits
  • Threads B et C : Formation de relations de verrous complexes
  • Condition de déclenchement : Nécessite une séquence précise d'appels système

La découverte de ces vulnérabilités complexes démontre l'efficacité de Psyzkaller dans l'apprentissage des SDRs.

Travaux connexes

Génération de spécifications d'appels système

  • DIFUZE : Inférence d'analyse statique des descriptions d'interfaces de périphériques
  • SyzGen : Combinaison d'instrumentation dynamique et d'analyse statique
  • SyzDescribe : Analyse des priorités des modules du noyau

Extraction des SDRs

  • HFL : Fuzzing hybride combiné avec exécution symbolique
  • Healer : Suppression itérative d'appels système évaluant l'impact sur la couverture
  • MOCK : Modèle de langage neuronal guidant la mutation des graines
  • ACTOR : Apprentissage des dépendances des appels système sur les objets du noyau partagés

Avantages de cet article

Par rapport aux méthodes existantes, cet article fournit :

  • Meilleure interprétabilité (représentation par probabilités de transition)
  • Efficacité computationnelle plus élevée (opérations matricielles légères)
  • Contrôle granulaire (influence relative des exécutions normales/anormales)

Conclusion et discussion

Conclusions principales

  1. Efficacité de l'apprentissage des SDRs : L'apprentissage des SDRs à partir de données historiques et en temps réel améliore significativement l'efficacité du fuzzing
  2. Avantages de la fusion de données : La stratégie combinant l'étendue historique et l'adaptabilité en temps réel est optimale
  3. Validation de la praticité : Démonstration de l'amélioration significative des performances sur les versions réelles du noyau

Limitations

  1. Limitation des dépendances sémantiques : Les relations d'appels système consécutifs capturées par Bigram ne correspondent pas toujours aux véritables dépendances sémantiques
  2. Évolution des versions du noyau : L'efficacité des données historiques peut diminuer sur les nouvelles versions du noyau
  3. Complexité computationnelle : La complexité des N-gram croît exponentiellement avec l'augmentation de N

Directions futures

  1. Amélioration de la compréhension sémantique : Combinaison du code source et de la documentation des appels système pour extraire des SDRs plus précises
  2. Extension du champ d'application : Application des SDRs apprises à d'autres étapes telles que la mutation des graines et l'ordonnancement
  3. Intégration de l'apprentissage par renforcement : Combinaison avec des stratégies de fuzzing basées sur l'apprentissage par renforcement

Évaluation approfondie

Points forts

  1. Forte innovativité de la méthode : Première combinaison systématique de données historiques à grande échelle et d'apprentissage en temps réel
  2. Expériences complètes et exhaustives : Trois versions du noyau, multiples configurations, expériences d'ablation détaillées
  3. Valeur pratique élevée : Découverte de 8 nouvelles vulnérabilités, démontrant la valeur de sécurité réelle
  4. Fondations théoriques solides : Utilisation de l'entropie de Shannon pour quantifier les améliorations

Insuffisances

  1. Limitations de la méthode : Dépendance des relations d'appels système consécutifs, risque de manquer les dépendances à longue distance
  2. Dépendance aux données : Dépendance sérieuse de la qualité de l'ensemble de données DongTing
  3. Problèmes d'extensibilité : La taille de la matrice croît quadratiquement avec le nombre d'appels système

Impact

  1. Contribution académique : Fournit une nouvelle méthode basée sur les données pour le domaine du fuzzing du noyau
  2. Valeur pratique : Peut être directement intégrée dans le flux de travail Syzkaller existant
  3. Reproductibilité : Basée sur des outils open-source et des ensembles de données publics

Scénarios d'application

  • Test de sécurité du noyau Linux
  • Optimisation de la génération de séquences d'appels système
  • Amélioration des outils de fuzzing du noyau
  • Recherche en sécurité des systèmes d'exploitation

Références

L'article cite 44 références pertinentes, couvrant :

  • Outils de fuzzing du noyau (Syzkaller, Healer, etc.)
  • Méthodes d'apprentissage automatique (N-gram, Word2Vec, Transformers)
  • Ensembles de données d'exécution du noyau (DongTing, ADFA-LD, etc.)
  • Méthodes d'extraction des dépendances des appels système

Évaluation globale : Ceci est un article de recherche en sécurité des systèmes de haute qualité qui propose une méthode innovante basée sur les données pour résoudre les problèmes clés du fuzzing du noyau. La conception expérimentale est rigoureuse, les résultats sont convaincants, et l'article possède une valeur académique et pratique importante.