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: OSカーネルファジングにおける履歴データとオンザフライ実行データからの学習による高度なシード生成

基本情報

  • 論文ID: 2510.08918
  • タイトル: Psyzkaller: Learning from Historical and On-the-Fly Execution Data for Smarter Seed Generation in OS kernel Fuzzing
  • 著者: Boyu Liu, Yang Zhang, Liang Cheng, Yi Zhang, Junjie Fan, Yu Fu
  • 分類: cs.CR（暗号化とセキュリティ）
  • 発表日: 2025年10月13日
  • 論文リンク: https://arxiv.org/abs/2510.08918v1

概要

ファジングはOSカーネルの脆弱性発見とセキュリティ強化の基本技術となっています。しかし、事実上の標準であるSyzkallerを含む最先端のカーネルファザーは、暗黙的なシステムコール依存関係（SDRs）を尊重する有効なシステムコール列の生成に困難を抱えています。そのため、生成されたシードの多くはカーネル検証に失敗するか、実行パスを深く進むことができず、著しい非効率性をもたらします。本論文は、SDRsが履歴データと現在のカーネル実行データから効果的に学習でき、これらの学習された関係をファジングに組み込むことで、シード有効性と多様性を大幅に向上させることができるという仮説を立てています。これを検証するため、著者らはN-gramモデルを使用して、DongTingデータセット（Linuxカーネル実行データの最大級のデータセットの一つ）およびファジングプロセス中にリアルタイムで収集された実行トレースからSDRsを抽出する方法を提案しています。

研究背景と動機

問題定義

OSカーネルは現代の計算プラットフォームの重要なコンポーネントであり、カーネルレベルのセキュリティ侵害により、攻撃者はシステムの完全な制御を獲得できます。現在のカーネルファザーが直面する中核的な問題は以下の通りです：

  1. システムコール依存関係（SDRs）の識別の困難さ：生成されたシステムコール列（SCSs）の多くがSDRsに違反するため無効
  2. シード生成効率の低さ：無効なテストケースが早期に失敗し、コード探索への貢献が少ない
  3. 深い実行パスへのアクセスの困難さ：システムコール間の意味的制約に対する理解の欠如

既存方法の限界

  • Syzkaller：システムコールテンプレートを使用して構文の正確性を強制しますが、より深い依存関係をキャプチャできません
  • 静的解析方法：計算オーバーヘッドが大きく、高スループットのファジング環境での展開が困難
  • 既存の機械学習方法：ファジング中に利用可能なデータが限定的で、SDRsを包括的にキャプチャできません

研究動機

著者らは、カーネル実行トレースから直接SDRsを学習する新しい視点を提案し、履歴データの広範なカバレッジとオンライン学習の適応性を組み合わせています。

核心的貢献

  1. 履歴データとリアルタイムカーネル実行データを組み合わせてSDRsを学習する新しい戦略を提案し、広範なカバレッジとカーネルバージョン適応性を実現
  2. Psyzkallerプロトタイプを開発し、Bigram ベースのSDR学習とRandomWalk戦略をSyzkallerワークフローに統合
  3. 最大規模の履歴Linuxカーネル実行データセット（DongTing）を使用してBigram モデルを事前学習
  4. 3つの代表的なLinuxカーネルバージョンで有効性を検証し、分岐カバレッジと脆弱性検出における優位性を実証

方法の詳細

タスク定義

入力：履歴カーネル実行データセットCとリアルタイムファジング結果 出力：強化されたChoice Table、より有効なシステムコール列生成をガイド 目標：シード有効性、多様性、脆弱性発見能力の向上

モデルアーキテクチャ

1. N-gramモデルの選択

Bigram モデル（N=2）を採用してSDRsを学習します。以下の理由に基づいています：

  • データ効率：DNN モデルと比較して、N-gramは小規模データセットでより良いパフォーマンスを発揮
  • 計算効率：Bigram行列の更新計算コストが最小
  • 解釈可能性：SDRsはシステムコール間の遷移確率として表現され、理解と検査が容易

Bigram確率計算：

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

2. 関係確率行列（RPM）

RPM行列を構築します。RPM[i]jはシステムコールwiの直後にwjが呼び出される確率を記録します。

アルゴリズム1: LearnSDR

入力: C（システムコール列コーパス）、CallNum（カーネル内のシステムコール総数）
出力: M（Cから学習されたN-gramモデル）

1. 行列Mとカウント配列Countを初期化
2. コーパスC内の各列scを反復処理：
   - 連続して出現するシステムコール対を統計
   - カウント統計を更新
3. 遷移確率を計算: M[i][j] = M[i][j] / Count[i]

3. データソースの選択

2種類の実行データを組み合わせます：

  • 履歴データ：DongTingデータセット（85GB、18,966個のシステムコール列）
    • 正常列：6,850個（LTP、Kselftestsなどのテストスイートから）
    • 異常列：12,116個（Syzbotレポートのクラッシュから）
  • リアルタイムデータ：ファジングプロセス中に収集された実行トレース

4. 強化Choice Table統合

強化Choice Table（ACT）を構築します：

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

ここで：

  • CTst：静的値（開発者の知識）
  • CTdyn：動的値（カーネルフィードバック）
  • DTN：履歴データから学習されたRPM
  • CorpusN：リアルタイムデータから学習されたRPM

5. RandomWalk戦略

双方向拡張戦略を導入してシード多様性を向上させます：

アルゴリズム2: GenRandomWalk

  • 部分列w1·w2...wkが与えられた場合
  • 前方拡張可能：ACT[wk]w > 0となるwを選択
  • 後方拡張可能：ACT[w]w1 > 0となるwを選択
  • 拡張方向をランダムに選択（各確率0.5）

技術的革新点

  1. 双源データ融合：初めて履歴大規模データとリアルタイム学習を体系的に組み合わせ
  2. シャノンエントロピー向上：SDR学習を通じてChoice Tableのシャノンエントロピーを大幅に向上（1.50から3.30-3.50 bitsへ）
  3. 重み付けバランス戦略：設定可能な重みを通じて正常と異常トレースの影響をバランス
  4. 双方向シード生成：RandomWalk戦略が従来の単方向拡張の制限を突破

実験設定

データセット

  • DongTingデータセット：85GB、Linux 4.13-5.17バージョンをカバー
  • テスト対象カーネルバージョン：Linux 5.19、6.1、6.12
  • 前処理：trace2syzツールを使用してSyzkaller形式に変換

評価指標

  • 分岐カバレッジ：コード探索の深さを測定
  • クラッシュ数：脆弱性発見能力を評価
  • シャノンエントロピー：Choice Tableの多様性を定量化
  • 脆弱性発見：発見された未知の脆弱性の数

比較方法

  • Syzkaller：ベースライン方法
  • Healer：最先端のSDR学習カーネルファザー

実装の詳細

  • 実験期間：各実験48時間、3回繰り返して平均値を取得
  • 重み比：正常/異常トレースの重み比として1:1、1:2、2:1の3つをテスト
  • ハードウェア環境：異なるカーネルバージョンで同じサーバーを使用して公平性を確保

実験結果

主要結果

分岐カバレッジの向上

  • Syzkallerと比較：4.6%-7.0%の向上
  • Healerと比較：Healerの0.4%-4.0%の向上を大幅に上回る

クラッシュ検出能力

  • クラッシュ数の増加：110.4%-187.2%（1,206 vs 516）
  • PoC生成：355個の有効なPoC（Syzkallerはわずか70個）

脆弱性発見

  • 新規脆弱性発見：8個の未知の脆弱性（Syzkallerはわずか1個）
  • 脆弱性タイプ：主にデッドロック関連の脆弱性（8個中6個）

アブレーション実験

重み比の影響（RQ1）

  • 最適構成：1:1の重み比がすべてのカーネルバージョンで最良のパフォーマンスを発揮
  • バランス効果：等しい重みが経路探索と脆弱性指向性のバランスを取る

戦略組み合わせの効果（RQ2）

  • 最適な組み合わせ：すべての戦略を有効にした場合（C+R+D）が最高のパフォーマンスを達成
  • 個別の貢献：
    • リアルタイム学習（C）：より高い分岐カバレッジ
    • 履歴データ（D）：より多くのクラッシュ検出
    • RandomWalk（R）：シード多様性の強化

ケーススタディ

三重デッドロック脆弱性

発見された典型的な脆弱性は、3つのスレッドがリソースロックを争う状況を含みます：

  • スレッドA：blk_mq_freeze_queue → loop_reconfigure_limits
  • スレッドBとC：複雑なロック依存関係を形成
  • トリガー条件：正確なシステムコール順序が必要

このような複雑な脆弱性の発見は、PsyzkallerがSDRsを学習する有効性を示しています。

関連研究

システムコール仕様生成

  • DIFUZE：デバイスインターフェース記述を推論する静的解析
  • SyzGen：動的計測と静的解析を組み合わせ
  • SyzDescribe：カーネルモジュール優先度を分析

SDR抽出

  • HFL：ハイブリッドファジングと記号実行を組み合わせ
  • Healer：カバレッジ影響を評価するためのシステムコール反復削除
  • MOCK：神経言語モデルがシード変異をガイド
  • ACTOR：共有カーネルオブジェクト上のシステムコール依存関係を学習

本論文の利点

既存方法と比較して、本論文は以下を提供します：

  • より優れた解釈可能性（遷移確率表現）
  • より高い計算効率（軽量行列操作）
  • 細粒度制御（正常/異常実行の相対的影響）

結論と考察

主要な結論

  1. SDR学習の有効性：履歴データとリアルタイムデータからSDRsを学習することで、ファジングの効果が大幅に向上
  2. データ融合の利点：履歴の広さとリアルタイム適応性を組み合わせた戦略が最適
  3. 実用性の検証：実際のカーネルバージョンで著しいパフォーマンス向上を実証

限界

  1. 意味的依存の制限：Bigramがキャプチャする連続システムコール関係が、常に真の意味的依存に対応するとは限らない
  2. カーネルバージョン進化：履歴データの新しいカーネルバージョンでの有効性が低下する可能性
  3. 計算複雑性：Nの増加に伴い、N-gramの複雑性が指数関数的に増加

今後の方向性

  1. 意味的理解の強化：システムコールソースコードとドキュメントを組み合わせてより正確なSDRsを抽出
  2. 適用範囲の拡張：学習されたSDRsをシード変異、スケジューリングなど他の段階に適用
  3. 強化学習の統合：強化学習ベースのファジング戦略と組み合わせ

深度評価

長所

  1. 方法の革新性が強い：初めて履歴大規模データとリアルタイム学習を体系的に組み合わせ
  2. 実験が充分で包括的：3つのカーネルバージョン、複数の構成、詳細なアブレーション実験
  3. 実用的価値が高い：8個の新規脆弱性を発見し、実際のセキュリティ価値を実証
  4. 理論的基礎が堅実：シャノンエントロピーを使用して改善効果を定量化

不足点

  1. 方法の限界：連続システムコール関係に依存し、長距離依存を見落とす可能性
  2. データ依存性：DongTingデータセットの品質に大きく依存
  3. スケーラビリティの問題：行列サイズがシステムコール数の二乗で増加

影響力

  1. 学術的貢献：カーネルファジング分野にデータ駆動型の新しい方法を提供
  2. 実用的価値：既存のSyzkallerワークフローに直接統合可能
  3. 再現性：オープンソースツールと公開データセットに基づく

適用シーン

  • Linuxカーネルセキュリティテスト
  • システムコール列生成の最適化
  • カーネルファジングツールの改善
  • OSセキュリティ研究

参考文献

論文は44篇の関連文献を引用しており、以下を含みます：

  • カーネルファジングツール（Syzkaller、Healerなど）
  • 機械学習方法（N-gram、Word2Vec、Transformersなど）
  • カーネル実行データセット（DongTing、ADFA-LDなど）
  • システムコール依存関係抽出方法

総合評価：これは高品質なシステムセキュリティ研究論文であり、カーネルファジングの重要な問題を解決するための革新的なデータ駆動型方法を提案しています。実験設計は厳密で、結果は説得力があり、学術的価値と実用的意義が重要です。