Tldr

  • 检测目标:Linux 驱动
  • 程序状态:
    • 理论上是程序状态机中记录状态信息、控制状态(流)的变量;
    • 实现中是类似 ioctl、mmap 等系统调用参数下能够影响控制流的变量。

这篇文章 fuzz 的目标是 Linux 上的驱动程序。

先看一下概要:

  • 执行相同路径的代码不应被丢弃,因为它可能触发了不同的状态
  • 本文通过状态变量对程序进行建模,在 fuzzing 时跟踪这些变量的值推断程序状态,优先考虑触发新状态的测试用例
  • 实验表明可以提升代码覆盖率和状态覆盖率

那么我的问题是:

  • 可以想象到程序中有一些变量作为 StateFuzz 中的状态变量,那么它是怎么确定状态变量的呢?
  • 根据第 2.3 节,在开发的过程中开发者就会用到状态机,因此可以从状态机中选择保存状态的变量作为状态变量。
  • 那么接下来看一下程序状态的建模吧(第 3.1 节)
    • 状态变量:
      1. 生存期长,可以记录状态信息
      2. 可以由用户更新,进行状态转换
      3. 应该能够直接或间接影响控制流或内存访问指针
    • 程序状态:如果保存所有状态那数量太多,该怎么优化呢?
      1. 只考虑程序状态中的相关变量对(互相影响的变量);
      2. 将值空间转换为多个值范围,相当于是降维了。
      • 如果发现了新的值范围边缘或新的极值,则认为发现了新状态

架构

接下来看一下 StateFuzz 架构:

猜测

涂色的部分是本文的工作,简单猜测 StateFuzz 的工作流程:

  1. 对内核源码进行静态分析获得状态变量列表
  2. 将状态变量列表结合符号执行获得状态变量值的边缘(也就是默认定义一些状态)
  3. 结合状态变量列表和状态变量值范围进行状态变量的插桩而后进行 fuzzing

推测对种子进行的操作:

  • 在执行后,如果发现了新状态,那么根据状态对种子进行生成和选择。

结合一下论文验证一下猜想对不对吧。看看 3.2 节的整体概括,StateFuzz 分为三部分:

  • 程序状态识别
    • 通过分析 Linux 源码提取状态变量、值的范围和状态变量的相关性
      • 静态分析找变量
      • 符号执行找范围和相关性
  • 程序插桩
    • 通过 SVF 在编译期间识别状态变量别名,跟踪状态变量在 fuzz 中所有值的变化
  • Fuzzing 循环
    • 大概就是怎样利用程序状态去更新种子了

现在的问题是:

  • 既然程序状态这么多,作者是用什么方法选取的?

看看第 3.3 节,程序状态的识别分为三个阶段:

  1. 程序行为识别
  • 主要是识别类似 ioctl、mmap 系统调用的 flags 参数,然后识别系统调用实现中 flag 对应的操作下面的变量。作者们通过拓展 Difuze 识别的程序行为。
  1. 程序状态识别
  • 作者们识别程序调用图中的代码及访问的变量。如果变量可以回溯到全局变量或者某个结构体的字段,就标记这些变量(因为状态变量应该有较长的生命周期)
  • 筛选出所有变量后,根据程序行为进行筛除,没有被任何程序行为调用的都被排除
  1. 推断程序值的范围
  • 在 AST 阶段进行符号执行,推测是用 CSA 跑的过程间的符号执行,然后根据求解出的变量的约束划分值的范围。

一个状态变量示例实例:

简单来说就是 ioctl 参数下可以控制执行流的变量。

第 3.4 节是对 fuzzing 循环的介绍:

  • 三维反馈机制,包括代码覆盖率、取值范围和极值。
    • 问题来了,取值范围和极值有什么区别
      • 看上去极值是整个取值范围的上限和下限
  • 种子保存策略
    • 也是三层,对应三种反馈机制
  • 种子选择策略
    • 避免局部最优,让三种种子均匀地被选择

实现

  • 通过 Difuze 识别程序行为,LLVM pass 识别状态变量,CRIX 建立调用图,CSA 收集变量范围和极值;
  • SVF 查找状态变量别名,LLVM SanCov 检测覆盖率和状态;
  • 基于 Syzkaller 实现 Fuzz 核心模块

参考资料