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

基本信息

  • 论文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 (Cryptography and Security)
  • 发表时间: October 13, 2025
  • 论文链接: https://arxiv.org/abs/2510.08918v1

摘要

模糊测试已成为发现操作系统内核漏洞和增强安全性的基石技术。然而，包括事实标准Syzkaller在内的最先进内核模糊器在生成尊重隐式系统调用依赖关系（SDRs）的有效系统调用序列方面存在困难。因此，许多生成的种子要么未能通过内核验证，要么无法深入执行路径，导致显著的低效率。本文假设SDRs可以从历史和当前内核执行数据中有效学习，并且将这些学习到的关系纳入模糊测试可以显著提高种子有效性和多样性。为验证这一点，作者提出了一种利用N-gram模型从DongTing数据集（最大的Linux内核执行数据集之一）以及模糊测试过程中实时收集的执行轨迹中挖掘SDRs的方法。

研究背景与动机

问题定义

操作系统内核是现代计算平台的关键组件，内核级的安全妥协允许攻击者获得系统的完全控制权。当前的内核模糊器面临的核心问题是：

  1. 系统调用依赖关系（SDRs）识别困难：许多生成的系统调用序列（SCSs）因违反SDRs而无效
  2. 种子生成效率低下：无效的测试用例过早失败，对代码探索贡献很少
  3. 深度执行路径难以到达：缺乏对系统调用间语义约束的理解

现有方法局限性

  • Syzkaller：使用系统调用模板强制语法正确性，但无法捕获更深层的依赖关系
  • 静态分析方法：计算开销大，难以在高吞吐量模糊测试环境中部署
  • 现有机器学习方法：模糊测试期间可用数据有限，无法全面捕获SDRs

研究动机

作者提出从内核执行轨迹直接学习SDRs的新视角，结合历史数据的广泛覆盖和在线学习的适应性。

核心贡献

  1. 提出了结合历史和实时内核执行数据学习SDRs的新策略，兼具广泛覆盖和内核版本适应性
  2. 开发了Psyzkaller原型，集成基于Bigram的SDR学习和RandomWalk策略到Syzkaller工作流中
  3. 使用最大的历史Linux内核执行数据集（DongTing）预训练Bigram模型
  4. 在三个代表性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的概率。

Algorithm 1: LearnSDR

输入: C (系统调用序列语料库), CallNum (内核中系统调用总数)
输出: M (从C学习的N-gram模型)

1. 初始化矩阵M和计数数组Count
2. 遍历语料库C中的每个序列sc:
   - 统计连续出现的系统调用对
   - 更新计数统计
3. 计算转移概率: M[i][j] = M[i][j] / Count[i]

3. 数据源选择

结合两类执行数据：

  • 历史数据：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策略

引入双向扩展策略增加种子多样性：

Algorithm 2: GenRandomWalk

  • 给定部分序列w1·w2...wk
  • 可向前扩展：选择w使得ACT[wk]w > 0
  • 可向后扩展：选择w使得ACT[w]w1 > 0
  • 随机选择扩展方向（概率各0.5）

技术创新点

  1. 双源数据融合：首次系统性结合历史大规模数据和实时学习
  2. Shannon熵提升：通过SDR学习显著提高Choice Table的Shannon熵（从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格式

评价指标

  • 分支覆盖率：衡量代码探索深度
  • 崩溃数量：评估漏洞发现能力
  • Shannon熵：量化Choice Table多样性
  • 漏洞发现：新发现的未知漏洞数量

对比方法

  • Syzkaller：基线方法
  • Healer：最先进的SDR学习内核模糊器

实现细节

  • 实验时长：每次48小时，重复3次取平均值
  • 权重比例：测试1:1、1:2、2:1三种正常/异常轨迹权重比
  • 硬件环境：不同内核版本使用相同服务器确保公平性

实验结果

主要结果

分支覆盖率提升

  • 相比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个）
  • 漏洞类型：主要为死锁相关漏洞（6/8）

消融实验

权重比例影响（RQ1）

  • 最优配置：1:1权重比在所有内核版本上表现最佳
  • 平衡效果：等权重平衡了路径探索和漏洞针对性

策略组合效果（RQ2）

  • 最佳组合：启用所有策略（C+R+D）获得最佳性能
  • 单独贡献：
    • 实时学习（C）：更高分支覆盖率
    • 历史数据（D）：更多崩溃检测
    • RandomWalk（R）：增强种子多样性

案例分析

三重死锁漏洞

发现的一个典型漏洞涉及三个线程争夺资源锁：

  • Thread A：blk_mq_freeze_queue → loop_reconfigure_limits
  • Thread 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. 实用价值高：发现8个新漏洞，展示了实际安全价值
  4. 理论基础扎实：使用Shannon熵量化改进效果

不足

  1. 方法局限性：依赖连续系统调用关系，可能遗漏长距离依赖
  2. 数据依赖性：严重依赖DongTing数据集质量
  3. 可扩展性问题：矩阵大小随系统调用数量二次增长

影响力

  1. 学术贡献：为内核模糊测试领域提供新的数据驱动方法
  2. 实用价值：可直接集成到现有Syzkaller工作流
  3. 可复现性：基于开源工具和公开数据集

适用场景

  • Linux内核安全测试
  • 系统调用序列生成优化
  • 内核模糊测试工具改进
  • 操作系统安全研究

参考文献

论文引用了44篇相关文献，涵盖：

  • 内核模糊测试工具（Syzkaller、Healer等）
  • 机器学习方法（N-gram、Word2Vec、Transformers）
  • 内核执行数据集（DongTing、ADFA-LD等）
  • 系统调用依赖关系提取方法

总体评价：这是一篇高质量的系统安全研究论文，提出了创新的数据驱动方法解决内核模糊测试中的关键问题。实验设计严谨，结果令人信服，具有重要的学术价值和实用意义。