混合模糊测试的分析与研究

2022-05-12 约 362 字预计阅读 2 分钟

模糊测试(Fuzz)介绍

模糊测试是一种漏洞发现的手段，通过用一些方式构造一些输入数据自动化地发送给程序，同时监测程序是否出现异常，将造成crash的输入数据返回给测试人员以达到发现漏洞的目的。

这里仅讨论白盒测试。

LLVM简介

LLVM是一款非常流行的开源编译器框架，支持多种语言和底层硬件。

在使用 LLVM 进行代码优化以及插桩时，我们必须要先了解 LLVM 的基础架构。经典编译器架构主要分为前端、中间层和后端三个部分。而我们常用的 GCC 在设计之初就导致前后端耦合度非常高，因此支持一个新的架构或编程语言对 GCC 来说都是非常难的一件事。为了避免强耦合的情况发生，LLVM 采用了非常简洁明了的三段式设计，架构如下所示：

其中LLVM的前端会对高级语言进行编译，生成能被LLVM解析并利用的中间件LLVM-IR。该IR在经过LLVM优化器进行一定程度的优化之后，被送到LLVM的后端，根据处理器的不同最终编译成可被执行的二进制文件。

目前而言的大部分研究都会以 LLVM IR 作为工具进行程序代码的静态分析。我们知道 LLVM IR 会在优化阶段进行相应的优化，LLVM 也在优化阶段允许用户自定义一些对 IR 的操作，从而达到静态分析的效果，这种自定义模块叫做 LLVM Pass。

传统Fuzz常用工具介绍与工作原理分析

AFL/AFL++(American Fuzzy Loop)

整体架构

在Fuzz开始前AFL首先通过afl-gcc/afl-clang等编译器的wrapper来对待测程序源代码进行插桩并编译。其中插桩用于记录分支信息（如被触发次数等），用于进一步分析。

整体工作流程图如下：

首先AFL从用户提供的一组输入开始，并尝试对输入进行一些变异（详见下文）。若这些变异之后的输入数据触发了新的执行路径，则加入“输入队列”，成为新的输入数据并重复上述过程。

输入变异策略

（其实是按顺序进行的）

一些不具有随机性的操作

bitflip

bitflip按照一些的步长对bit进行一些翻转。

在这个过程中，AFL同时会生成token和effector map。

>>token

判断规则：如果连续多个bytes的最低位被翻转后，程序的执行路径都未变化，而且与原始执行路径不一致，那么就把这一段连续的bytes判断是一条token。

例如，众所周知，在PNG文件中使用IHDR作为一个起始块的标识。当翻转I的最高位时，该标识被破坏，此时程序的执行路径必定与原本不相同。这样AFL就得到了一个可能的token：IHDR，为后面的变异做准备。

>>effector map

说人话就是判断有效字节。

具体地，在对每个byte进行翻转时，如果其造成执行路径与原始路径不一致，就将该byte在effector map中标记为1，即“有效”的，否则标记为0，即“无效”的。

如果一个byte完全翻转，都无法带来执行路径的变化，那么这个byte很可能是“无效”的，对整个fuzzing的意义不大。所以，在随后的一些变异中，会参考effector map，跳过那些“无效”的byte，从而节省了执行资源。

arithmetic

按照一些步长进行一些加减变换。同时参照effector map和bitflip生成过的东西剪个枝。

interest

按照一些步长进行一些替换。用于替换的数一般是-128，-32768等等容易造成溢出的数。

dictionary

尝试把用户提供的token和bitflip中自动检测到的token替换到源文件中。

一些具有随机性的操作

havoc

随机选取某个bit进行翻转

随机选取某个byte，将其设置为随机的interesting value

随机选取某个word，并随机选取大、小端序，将其设置为随机的interesting value

随机选取某个dword，并随机选取大、小端序，将其设置为随机的interesting value

随机选取某个byte，对其减去一个随机数

随机选取某个byte，对其加上一个随机数

随机选取某个word，并随机选取大、小端序，对其减去一个随机数

随机选取某个word，并随机选取大、小端序，对其加上一个随机数

随机选取某个dword，并随机选取大、小端序，对其减去一个随机数

随机选取某个dword，并随机选取大、小端序，对其加上一个随机数

随机选取某个byte，将其设置为随机数

随机删除一段bytes

随机选取一个位置，插入一段随机长度的内容，其中75%的概率是插入原文中随机位置的内容，25%的概率是插入一段随机选取的数

随机选取一个位置，替换为一段随机长度的内容，其中75%的概率是替换成原文中随机位置的内容，25%的概率是替换成一段随机选取的数

随机选取一个位置，用随机选取的token（用户提供的或自动生成的）替换

随机选取一个位置，用随机选取的token（用户提供的或自动生成的）插入

就是把前面的组合一下进行一些随机变换。

splice

把一些输入拼接在一起然后做一些havoc变换

优化速度的一些操作

除此之外，AFL还会进行剔除语料库、修建输入文件等操作用于提高效率，在这里不展开叙述。

AFL++

AFL++ 可以看作是升级版的 AFL。其增加了用户自定义变异器的功能，从而极大方便了我们将 Fuzzer 和符号执行工具结合在一起。此外，AFL++ 还优化了主 Fuzz 逻辑，提高了 Fuzz 效率。

LibFuzzer

相比AFL，LibFuzzer是一种更具有针对性的模糊测试工具。它不重复启动进程，而是在单个进程中直接将数据投放在内存中，执行了所有模糊测试。

同时，LibFuzzer是以代码覆盖率为引导的——它对每一个输入都进行代码覆盖率的计算，不断累积这些测试用例使代码覆盖率达到最大。同时，它会根据代码的覆盖率回馈进行变异。其变异算法和AFL大同小异，这里不再赘述。

传统模糊测试弊端分析

通过上面对AFL的工作原理分析我们可以看到，传统Fuzzing生成的输入样例策略具有很强的随机性，质量较低，对于一些比较难以触发的深度较深或条件约束比较复杂的分支，传统Fuzzing就难以成功触发。

符号执行

符号执行是一种静态的白盒分析技术，并未实际地执行程序，而是分析程序的执行路径。符号执行的最终目的和Fuzz相同——找到一组或几组能触发程序异常的输入数据，达到发现漏洞的目的。

静态符号执行(Symbolic execution)

工作原理概述

符号执行的关键思想是：把输入变为符号值，那么程序计算的输出值就是一个符号输入值的函数。一个程序执行的路径通常是true和false条件的序列，这些条件是在分支语句处产生的。在序列的第i位置如果值是true，那么意味着第i个条件语句走的是then这个分支；反之如果是false就意味着程序执行走的是else分支。形象化地，程序执行的路径可以表示为一棵“执行树”，而符号执行便是要生成一些输入的集合，探索所有的路径。

符号执行会在全局维护两个变量：符号状态$\sigma$和符号化路径约束PC。

通俗地说，符号状态$\sigma$是一个映射，保存了所有变量和符号之间的关系，形如： $$ \sigma = { x \rightarrow x_0, y \rightarrow y_0, z \rightarrow 2y_0 } $$ 其中$x_0$和$y_0$是两个未被约束的符号值，通常是由用户输入的数据。而x、y、z则是程序中的一些变量。

而符号化路径约束PC是一个无量词一阶公式。它代表着执行到某个程序分支的约束条件，形如： $$ (x_0=2y_0)∧(x_0>y_0+10) $$ $\sigma$和PC会随着符号执行的进度进行更新，更新方法详见下文。

毛了一个例子来：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void testme(int x, int y){
	z = y*2; 
	if(z == x){
		if(x > y+10)
			ERROR;
	}
}

/* simple driver exercising testme() with sym inputs */
int main(){
    x = sym_input();
    y = sym_input();
    testme(x, y);
    return 0;
}

我们以这个为例来阐述符号执行的具体过程。

在符号执行开始前，$\sigma$被初始化为一个空映射，PC被初始化为true。

当遇到一个输入语句x=sym_input();时，创建一个未约束的符号值并建立映射。执行完main的前两行得到的符号状态是$\sigma={x \rightarrow x_0, y \rightarrow y_0}$

当遇到一个赋值语句z=y*2时，计算符号的表达式并且建立映射。执行完testme的第一行得到的符号状态是$\sigma={x \rightarrow x_0, y \rightarrow y_0, z \rightarrow 2y_0}$

当遇到一个分支语句if(z==x)时，将条件计算成符号的表达式\sigma(e)，将PC更新为$PC∧\sigma(e)$表示then分支。同时建立一个新的路径约束PC'，初始化为$PC∧\neg \sigma(e)$表示else分支。如果PC和PC’都可能被满足，就新开一个符号执行实例走else分支继续执行。如果都不能满足则会直接终止。

例如，第7行建立了两个不同的符号执行实例，路径约束分别是 $x_0=2y_0$ 和 $x_0 \not = 2y_0$ 。在第8行，又建立了两个符号执行实例，路径约束分别是 $(x_0=2y_0) \wedge (x_0 > y_0 + 10)$和 $(x_0=2y_0) \wedge (x_0 \leq y_0 + 10)$.

这样的执行结束后，我们会得到每个分支的一些路径约束，用约束求解器进行一个求解就可以获得每个分支的对应输入。

问题分析

看看这个

1
2
3
4
5
6
7
8


void testme_inf() {          
    int sum = 0;
    int N = sym_input();      
    while (N > 0) {
        sum = sum + N
        N = sym_input();
    }
}

不难发现，这样的程序在符号执行时会有无限量的路径。

同时，若符号路径约束包含了不能由约束求解器高效求解的约束（如：$x_0=y_0^2\ mod\ 50$），静态符号执行就无法产生输入。

动态符号执行(Concolic Execution)

为了解决上述的问题，动态执行选择了将实际执行和静态符号执行混合起来。

动态执行维护一个实际状态和一个符号化状态：实际状态将所有变量映射到实际值，符号状态只映射那些有非实际值的变量。动态符号执行首先用一些给定的或者随机的输入来执行程序，收集执行过程中条件语句对输入的符号化约束，然后使用约束求解器去推理输入的变化，从而将下一次程序的执行导向另一条执行路径。

简单地说，就是在已有实际输入得到的路径上，对分支路径条件进行取反，就可以让执行走向另外一条路径。这个过程会不断地重复，理论上可以覆盖到程序能达到的所有分支。

由于程序的分支可能会有很多，动态符号执行有时会使用启发式的方法寻找路径，同时在约束求解方面进行一些优化和剪枝来优化效率。

动态符号执行弊端分析

与传统Fuzz恰好相反，动态符号执行能产生高质量的输入数据，能探索复杂路径，但是在约束求解等地方耗费的时间比较多，时间开销较大。

混合模糊测试（Hybrid fuzzing）

混合模糊测试概述

混合模糊测试其实就是把传统模糊测试和动态符号执行结合起来，以达成高效、高质量的模糊测试。动态符号执行可以帮助 Fuzzing 求解复杂的约束条件，Fuzzing 可以为动态符号执行快速探索程序路径。

为了叙述方便，下面把传统模糊测试简称为“Fuzz”，动态符号执行简称为“符号执行”。

混合模糊测试的几种策略

需求分发策略

一种简单的混合模糊测试策略：先启用Fuzz，在Fuzz卡住（不能继续发现新分支）的时候启用符号执行，常用的Driller工具就是基于这一策略的。

但这种策略存在一些难以解决的问题。

首先Fuzz“卡住”是一种很难判断的状态——万一下一秒就好了呢？到底“卡住”多久才算卡住？

当Fuzz卡住的时候，怎么知道到底卡在哪里了？如何找出卡住Fuzz的是程序的那个分支约束条件？

就算找到了让Fuzz卡住的地方，使用符号执行就一定更优吗？有没有一种可能，就是说其实把用于符号执行的时间拿来继续Fuzz能更快地找到能覆盖这个分支的输入？

Fuzz产生了大量的输入，如果要使用符号执行，很显然全部执行一遍是不现实的。如何判断哪些输入更值得被交给符号执行处理？

除此以外，Fuzz和符号执行的这种异步处理方式也造成了很大的时间浪费。

Optimal Switch策略

对每一条程序路径，分别评估使用Fuzz探索的代价和使用符号执行探索的代价，选择“性价比”更高的一种探索方式。

这种方法虽然理论可行，但是Fuzz和符号执行探索的方法难以量化。即使能进行量化，也会造成更加重量级的开销。

DigFuzz

相比于对每条路径评估Fuzz和符号执行的代价，DigFuzz选择评估每条路径的“探索难度”，把探索难度较低的交给Fuzz，其余交给符号执行。

估计方法是“基于蒙特卡洛的路径概率排序模型”。

蒙特卡洛方法其实就是这个↓

（我也刚刚知道这种方法的名字）

具体来说，就是把Fuzz的过程看成随机取样，统计每条路径被覆盖到的概率，每次把被覆盖概率最低的路径交给符号执行进行处理。

Savior

在论文SAVIOR: Towards Bug-Driven Hybrid Testing中，提出了两个问题：

1、存在漏洞的代码是少数，以代码覆盖率为导向并不是最优的策略。

2、即使能够到达存在漏洞的代码位置，很多漏洞由于不满足条件，无法触发漏洞。

如下面这个例子（来自论文Intriguer: Field-Level Constraint Solving for Hybrid Fuzzing）

触发15行整数溢出漏洞的约束：

1、$width>0x5FFF$

2、$height>0x5FFF$

3、$width*height*8>0xFFFFFFFF$

其中第三条约束是一个较为严苛的条件，而且动态符号执行无法得到这样的约束，因此即使达到了代码位置也无法触发漏洞。

因此Savior提出了一种用输入未探索路径上的未定义行为的数量来评估输入价值的混合Fuzz方法。同时，将这些未定义行为的路径约束拿出来进行一个求解，来达到“以bug为导向”的模糊测试。

摸了，后续懒得更到blog上了。感兴趣可以看一下我在5.21腾讯科恩技术沙龙上的演讲。（B站上应该有）

https://www.bilibili.com/video/BV1Ua41177at

目录