一、简介
Healer 是受 Syzkaller 启发的 kernel fuzz。
与 Syzkaller 类似，Healer 使用 Syzlang 描述所提供的 syscall 信息来生成确认参数结构约束和部分语义约束的系统调用序列，并通过不断执行生成的调用序列来发现内核错误，导致内核崩溃。
与 Syzkaller 不同，Healer 不使用 choise table，而是通过动态移除最小化调用序列中的调用并观察覆盖范围变化来检测不同系统调用之间的内部关系，并利用内部关系来指导调用序列的生成和变异。此外，Healer 还使用了与 Syzkaller 不同的架构设计。
论文地址：HEALER: Relation Learning Guided Kernel Fuzzing
项目地址：github
二、概述
先上一张概述图：
初始时，Syscall 描述 + 语料将被喂入 healer中，并在其中通过 Relation Learning 来获取出不同 syscall 之间的内部关系，之后可以通过生成的内部关系来达到更好的变异与生成效果。
Relation，在这篇论文中，指代不同 syscall 之间的内部关系。
Healer 会将 testcase 放入 Executor 中执行，并获取执行的覆盖范围信息来更好的运行 Relation Learning 中的 Dynamic Learning。
该论文虽然特别的长，但实际上核心思想较为简单，只分为三部分，分别是
- Relation Learning 中的 Static Learning 和 Dynamic Learning
- 以及 Healer 如何使用 Relation 来进行变异。
三、Relation Learning
1. 定义
Healer 使用 Relatino learning 来动态感知 syscall 之间的内部关系。其中这里有个定义：
若某个 syscall $C_i$ 的执行可以影响到另一个 syscall $C_j$ 的执行路径（例如 $C_i$ 修改了内核的内部状态），则我们称 $C_i$ 对 $C_j$ 产生了影响。
Healer 使用二维表$R^{n \times n}$ （Relation Table，关系表）来记录任意 n 个 syscall 中的内部关系：
- 若 $R_{ij}$ 为1，则说明 syscall $C_i$ 可以对 $C_j$ 的执行路径产生影响。
- 反之，$R_{ij}$ 为0则说明不产生影响。
初始时，healer 没有记录下任何 syscall 之间的内部关系，因此该表格初始时全为 0。
接下来，Relation Learning 分为两部分
- Static Learning：根据 syscall 描述的输入参数类型和返回类型来获取 Relation。
- Dynamic Learning：用于找到 syscall 描述无法表达的 Relation。
2. Static Learning
初始时，Static Learning 将会根据 Syzlang 描述所提供的信息来初始化 Relation Table。其中，参数类型和返回值类型对静态分析至关重要。
当同时满足以下两个条件时，static learning 将认为 syscall $Ci$ 对 $C_j$ 产生影响，并设置 Relation Table 中的 $R{ij} = 1$：
- $C_i$的返回值类型是一种 resource 类型 $r_0$ ，或者$C_i$ 中的任何一个参数是一个具有向外数据流方向的指针。
这一条其实相当好理解，主要是限制 $C_i$ 的作用是产生向外数据流。
- $C_j$ 中至少有一个参数的类型是 具有向内数据流的 resource 类型 $r_0$或与 $r_0$相兼容的类型 $r_1$。 由于 syzlang 支持类型嵌套（或者类型兼容），因此类型 $r_1$ 也是符合要求的。
这两个条件显示约束了数据流方向，必须从$C_i\to C_j$ ，这是静态学习中所能得知的 Relation。
可以将静态学习理解成捕获两个系统调用之间的直接关系（例如数据流关系）。
3. Dynamic Learning
动态学习可以使用 syzlang 无法表达的信息来更好的更新和细化关系表，以便于生成更高质量的测试用例。
初始时， healer 会先单独收集 syscall 序列中的每个 syscall 的覆盖范围，并存储其触发的基本块和边的标识符序列，以便于在接下来的测试中发现新的覆盖范围信息。
之后，Dynamic Learning 将会使用 minimization 算法，获取到尽可能小且覆盖范围不变的系统调用序列。
这一步操作是为了过滤掉那些对新覆盖范围无用的系统调用，并加强分析效果。
minimization 算法将反向遍历系统调用序列，提取出那些没有被包含在其他最小序列中（防止重复）且生成了新覆盖范围信息（有新覆盖才有用）的系统调用。
该算法的核心思想较为简单，先上图：
简单概括一下，该算法的输入有两个，分别是
1. 系统调用序列 p（即测试样例）
2. 序列 p 中每个 syscall 所生成的**新**覆盖范围（注意**新**字）
之后，尝试从后向前依次遍历每个系统调用，
- 若某个系统调用不产生新的覆盖范围，则直接丢弃（因为不产生新覆盖所以肯定没用）
- 若某个系统调用之前被丢弃过，则也一并丢弃
- 之后循环从后向前遍历系统调用序列，并多次尝试丢弃一些系统调用。若丢弃某个系统调用后，覆盖范围没有发生改变，则该系统调用是无用的，可以被丢弃，否则则必须保留。
这一步的操作只是为了删除不影响覆盖范围的系统调用。
在完成 minimization 算法后，Dynamic Learning 将会在最小系统调用序列中，逐渐的移出单个 syscall 并检测每个移出操作对下一个 syscall 的影响，这是其具体算法描述：
其实也很简单，简单概括一下就是，
在给定的最小系统调用序列中，依次遍历该序列中的所有 syscall。
设当前遍历到了系统调用 $C_j$，且 $C_i$ 是 $C_j$ 的前一个系统调用（previous）。
若将 $Ci$ 从系统调用序列中删除，且该删除将会影响到 $C_j$ 的覆盖范围信息，则说明 $C_i$ 对 $C_j$ 产生了影响，因此可以设置 $R{ij} = 1$。
这里有个关键点需要注意一下：对于系统调用序列 $[C_0, C_1, C_2]$ 来说，若 $C_1$ 的移除影响到 $C_2$ 的覆盖范围，则我们可以确定 $C_1 \to C_2$ 存在影响关系。但是，若 $C_0$ 的移除导致了 $C_2$ 的覆盖范围发生改变，则不能说明 $C_0 \to C_2$。这是因为，$C_0$ 的移出可能导致 $C_1$ 覆盖范围的变化，进而间接影响到 $C_2$ 覆盖范围的变化。
通过上述的两个算法，healer 成功通过覆盖范围信息来指导建立起系统调用之间的内部关系信息。
可以将动态学习理解成捕获两个系统调用之间的间接关系（例如内核内部的状态改变关系）。
四、变异与生成
当 Relation Table 通过上面的算法逐步建成后，该信息将会被用于指导变异和生成。抛开那些常用的变异手法（例如随机插入 syscall 或者变异参数类型等方法），这里只讲一下 healer 如何利用 Relation table 来进行变异。
首先，Healer 对语料库现有的系统调用序列执行变异，在选择了某个变异目标后，healer 将
- 随机在系统调用序列中选择一个插入点
- 将插入点前面的子序列用作输入，执行变异算法，将该算法选择的系统调用插入至该位置。
变异算法具体描述如下：
通俗的说，就是
- 如果概率小于 $1-\alpha$，则直接随机返回一个系统调用。
- 否则，遍历传入的子序列 S，并将子序列中每个 syscall 可能产生影响的新 syscall 加入候选队列中。如果之前已经加入过一次，则增加其权重。
- 最后随机通过权重来选择一个候选 syscall。
需要注意的是，在 healer 初始启动时，Relation Table 中并没有太多的数据可以用于指导变异和生成，此时若过度使用信息不足的关系表则可能会降低测试用例的多样性；但另一方面，要是完全不使用 Relation Table，则测试用例的质量就不会太高（而且完全不使用的话，上面的工作就白做了）。
因此实际上该变异算法中的 $\alpha$ 是用来平衡这两者的一个关键：若在使用学习到的 Relations 时覆盖率信息增加，则$\alpha$也将同步增加，进一步提高使用非随机变异策略的概率。
五、评估
在24小时中的 fuzz 过程里，healer 可以获得比 syzkaller 更广的覆盖率：
需要注意的是，初始时 healer 和 syzkaller 的覆盖率曲线是重合的，这是因为此时 healer 还没有建立完备的 Relation Table，使用的仍然是随机变异。
下图显示的是建立 Relation 的全过程（图中的每个点表示不同的 syscall，有向边表示影响关系）：
初始时，Relation 是根据静态分析所得出的关系，因此此时在关系图中存在非常多的子图。
随着时间的推移，更多的隐式关系被找出，不同的子图开始慢慢相连。并到最后形成巨大的关系图。
除此之外，还发现了一些 syzkaller 没发现的新漏洞。
六、局限性
syzlang 描述本身在大多数情况下是人工编写生成的，人工成本较大，且描述的正确性和完整性也不能保证。
一个可能的解决方案是自动将 C 头文件中的定义转换为Syzlang描述，保存原始的结构定义。
七、随笔
这篇论文整体思路上并不复杂，但它确确实实能捕获到系统调用之间的关系，而且在各个思路与细节方法均考虑的十分周全，是一篇相当不错的论文。