「Paper Reading」：AFL++：Combine Incremental Steps of Fuzzing Research

   Paper 31 minutes read (About 4631 words) 0 visits

今天给大家分享的论文是一篇基于AFL的工作：AFL++：Combine Incremental Steps of Fuzzing Research，发表在USENIX Workshop。分享时的slides

目录

Introduction

Fuzzing已经成为软件测试强有力的工具，通过大量的非预期的输入，检测软件的运行状态，以发现软件的隐藏性漏洞。

而AFL是最具盛名的fuzzing工具，基于AFL的研究也层出不穷，但这些技术往往是正交式、独立地发展。

因此：

  1. 将这些前沿新颖的fuzzing技术结合起来是一件很困难的事情
  2. 而评估这些不同维度的fuzzing技术也是一件很困难的事

AFL++这个工作就致力于解决这个问题：

  1. AFL++提供了一个可用的fuzzing工具，结合了许多前沿fuzzing技术
  2. AFL++还提供了一种新颖的可自定义的变异API（Custom Mutator API），研究人员能够轻松将自己设计的Mutator应用到AFL++上，或和其他Mutators结合起来。
  3. 这篇论文还评估了许多结合起来的fuzzing技术组合，评估结果体现了fuzzing技术的target-dependency.

State-of-the-Art

在正式介绍AFL++ 之前，很有必要介绍一下afl++结合的其他fuzzing技术。

除了AFL的主要特点，afl++主要结合了三方面的技术，分别是：

调度上的。包括AFLFast的种子调度和MOpt的变异调度。

绕过fuzzing中的一些roadblocks，包括LAF- Intel和Red Queen。

针对一些复杂的结构化输入的变异。

AFL

首先介绍一下AFL的工作原理和主要特征。

AFL是一种基于覆盖率反馈（coverage- guided）的fuzz工具。

AFL的工作流程如图所示：

cUSNqA.png
  1. 编译时对源码进行插桩，以记录代码覆盖率（Code Coverage）
  2. 初始化一些输入文件，加入到输入队列（queue）
  3. 在队列中按照一定策略选择种子（seed），并进行大量的突变（mutation），得到大量的变异文件
  4. 如果该变异文件触发了新的执行路径，则将其保存下来，加入到队列中。
  5. goto 2

上述过程会一直进行下去，其中触发的crash会被记录下来，以便后面分析程序漏洞。

Coverage Guided Feedback

AFL是一种使用边覆盖率作为反馈的灰盒fuzzer。

什么是边覆盖率呢？

在介绍边覆盖率之前，先介绍一下块覆盖率：

cNjrnI.png

如上图，将一个程序划分为一个一个的程序块，一个程序块中的指令要么都执行，要么都不执行。

将上述程序拖到IDA中，得到下图，因此可以用程序块之间的跳转表示边。所以

cNvCE6.png

A -> B -> C -> D -> E (tuples: AB, BC, CD, DE)

A -> B -> D -> C -> E (tuples: AB, BD, DC, CE)

这两条执行路径的覆盖率不同。

实现上，就是给每一个块分配一个编译随机值，通过上一个块和当前块的运算的值来表示该边，再进行统计。

Mutation

AFL中的Mutation主要分为两种，一种是deterministic stage，从下表的变异中选择一个mutation进行连续变异。

cUS38O.png

而havoc stage 则是每次选择一堆变异，工作作用在seed上。

Fork Server

由于AFL会大量运行目标程序，因此为了减少fuzzer的执行开销，AFL使用了一种forkserver的技术。

forkserver的工作原理如下图所示:

cNjBjA.png

当fuzzer在执行目标程序前，会先执行fork()命令，得到一个子进程。

子进程再通过execv()指令执行目标程序，而execv()命令有一个很特别的地方，他会用这个目标程序的映像覆盖掉子进程的映像。

因此，此时的fuzzer fork()出的子进程就变成了插过桩的目标程序，也就是forkserver。

The exec() family of functions replaces the current process image with a new process image.

当fuzzer想要执行目标程序时，就和forkserver通信，将fork目标程序的任务交给forkserver，这样就极大的提高了fuzzer的执行效率。

Persistent Mode

AFL另一个提高效率的功能是Persistent Mode。

使用Persistent Mode，只需要对程序做一点小小的改动，即对程序patch一个循环，就像这样：

cNjw1H.png

Persistent Mode允许单个进程重复输入，极大减少了fork的开销。

Smart Scheduling

AFLFast

基于AFL的另一个改进领域是调度问题，一个是种子调度，如何选种子的问题；另一个是变异调度，如何选mutation的问题。

AFLFast主要是从种子调度的方向改进AFL。

AFLFast观察到种子大多数生成的输入都经历了相同的高频路径，因此想要设计一些策略能够focus on一些低频路径。

因此，AFLFast设计了两种策略：

  • Search Strategy：关于在队列中如何选种子的问题，决定种子挑选顺序。

  • Power Schedule：关于选出的种子可以被fuzz多少次，即可以生成多少变异文件，而这个数量被定义为种子的energy。

    seed’s energy: the amount of generated inputs from each seed

AFL

其实在AFL中也有相应的策略，我们先来看AFL中的种子策略是这样的：

  • 如何挑选种子：

    在AFL中，update_bitmap_score 函数中维护了一个变量fav_factor ，这个值越小意味值种子越favored，而这个值其实是由程序的执行时间(exec_us)和种子的长度(len)决定的。

    cNjd9e.png

  • 如何给种子分配energy：

    在AFL中，calculate_score 函数中维护了一个变量perf_score ，这个值越大意味着会给种子分配更多的energy，这个种子就有更多的机会被fuzz，而这个值主要由执行时间(exec_us)、程序的执行路(bitmap_size)、发现该种子的困难度(handicap)以及种子的深度(depth)共同决定的。

    cUSaVI.png

    其中handicap，困难度，可以这样来理解，这个值越大，说明发现这个种子经过了很长轮数，来之不易，所以希望能更focus on在这些来之不易的种子上。

AFLFast

而AFLFast中，不管是决定如何挑选种子，还是觉得如何给种子分配energy，AFLFast都还考虑了另外两个变量。

对每个种子，定义两个变量：

一个是f(i) ，表示该种子被fuzz的总次数，也叫做频率。

另一个是s(i) ，表示该种子在队列挑选中，被挑选了多少次。

cNjcAf.png

AFLFast-Power Schedule

这里主要介绍一下AFLFast的Power Schedule：

AFLFast提供了6中Power Schedule：

定义p(i)为分配的energy。

  1. EXPLOIT：p(i) = AFL

    EXPLOIT模式下的power schedule，就是之前提到的AFL的原生策略。

  2. EXPLORE：p(i) = AFL / const

    EXPLORE模式下，对AFL中计算出的energy除以了一个常数。

    看这样的一个例子：

    cNjydHP.png

    程序需要依次匹配到这些字符，才可以找到crash。

    如果规定每个种子的energy是一个常数，即p = $2^{16}$ ，那总共分配 $2^{18}$ 的energy才能找到crash。

    cNj24S.png

    但如果把这个种子的转移过程用马尔可夫链建模，可以发现如果从b*** 转移到ba** ，fuzz的转移概率为 $2^{-10}$ （从4个字符中选择一个字节，每个字节有 $2^{8}$ 中情况）

    cNjgN8.png

    因此，可以得到从i 种子转移到j 种子需要的energy的期望是 $E[X_{ij}]=\frac{1}{p_{ij}}$

    那么找到bad! 状态，所需要的总energy的期望和为 : $E[X_{01}]+E[X_{12}]+E[X_{23}]+E[X_{34}]=4 \cdot 2^{10}=4k$

    因此，我们总是分配所需期望energy更多的值，所以在AFLFast模式，会对energy除以一个常数。

剩下这四种策略都是从不同的方式抑制高频边被fuzz。

cNjW9g.png

MOpt

与种子调度相对的是变异调度，MOpt这个工作就是从变异调度的角度提升fuzz的效率。

MOpt工作的主要贡献有：

首先是观察到：很多有效的变异如bitflip，执行的时间却很少。

论文中统计了在deterministic stage不同变异产生的interesting test cases的数量，发现bitlip表现优异。

cNjf3Q.png

但从变异执行时间的角度，发现这些变异效率高的变异，执行时间比较短。

cNjhcj.png

所以MOpt的motivation是：希望能花更多的时间在那些变异效率高的变异上。

PSO

MOpt使用粒子群优化算法来对问题建模。

定义粒子（particle），即变异（mutation）。粒子的位置，就是该变异被选择的概率。

每一个粒子群（swarm），则是所有mutations的概率分布。

而MOpt与原始PSO算法不同，MOpt使用的是多个群（multiple swarms），每一个群都是一个概率分布。

在MOpt的工作流程中，主要有两个核心模块。

cNj4js.png

一个是Pilot模块，另一个是Core模块。

Pilot模块：评估每一个粒子群，也就是该mutations的概率分布的fuzz效率。

Core模块：使用Pilot模块评估出的效率最高的mutation策略 来fuzz。

Bypassing Roadblocks

fuzzing中有时会遇到一些roadblocks。

LAF- Intel

LAF-Intel解决的fuzzing中遇到的一些困难比较语句，如下图：

cNjIun.png

即使当输入为0xabad1dee时，已经非常接近正确答案了，fuzzer也会认为他是错误的。

因此LAF- Intel的思路是，把这些比较难的、比较一连串字符的比较划分为 多个单字节的比较。

这样可以让程序块的划分粒度更细，当你每匹配到一个字节时，就被认为是interesting，被保存到队列中，以后可以继续fuzz，这样，fuzzer就可以一步一步的解决这个roadblock。

另外，LAF-Intel是基于LLVM架构的，所以LAF- Intel实现了三种Pass：

  • The split-compares-pass：划分为单字节比较，并全部转换为<, >, ==, !=和无符号数的比较。
  • The compare-transform-pass：重写了strcmp和memcmp，将其全部转换为单字节比较。
  • The split-switches-pass：将switch比较转换为单字节比较的if串。

RedQueen

RedQueen解决的roadblocks：

  • magic number：和上文LAF-Intel解决的roadblocks类似。

    cNjoBq.png

  • nested checksum：而校验和/嵌套校验和的情况就像下图所示：

    cNjTH0.png

    代码如下图所绘：

    cUStrd.png

RedQueen这篇工作的贡献是：

首先他观察到种子的输入，有时是和程序的运行状态直接相关的，这种关联定义为Input-to-State联系。

比如下图：

cNjHEV.png

hook住cmp指令，运行时，观察到eax的值为VALU ，与之比较的值为ABCD（都是小端序）。

而VALU在输入中也有出现，所以这里观察到的VALU大概率就是输入的VALU，如果能将输入的VALU换成ABCD，就有较大可能绕过这个roadblock。

RedQueen就是利用这样的Input-to-State的关系来解决这些roadblocks。

Magic Bytes

解决Magic Bytes的方法就是上文提到的那样，希望能找到一系列的可替换对。

cNjHEV.png

具体流程为：

  1. 跟踪：将所有的cmp指令hook住，尝试运行一下，把指令比较的操作数都提取出来。
  2. 变化：对比较指令的操作数做变异操作，比如加一或减一的操作，因为从该条指令并不能得到源码中的比较关系，源码的比较逻辑可能是大于、小于等。
  3. 编码：对得到的替换对进行编码操作，如小端序、hex、base-64等，像刚刚的例子就是小端序的编码。
  4. 应用：将得到的这些替换对< pattern -> repl >应用到输入中，即在输入中找pattern，替换为repl，试运行。

在执行上述流程之前，RedQueen执行了一个操作，该操作极大提高了绕过的效率。

如果替换对为(0x00, 0x04)，并且输入文件像下面左图这样：

cNjbNT.png

输入文件中出现大量的0x00，就像产生了碰撞一样，其实很多位置并不和那条程序指令相关，这样就会花费大量时间。

如果输入是像上图右边这样的，比较colorful，那RedQueen的效率就会很高。

所以RedQueen在进行绕过之前，会对输入做染色（Colorization）的操作，在保证种子执行路径不变的情况下，增大输入的熵值。

Nested Checksum

而对checksum的绕过，这其实是一件很难的事情，因此RedQueen会选择先忽略掉这些困难，后面再来修正。

具体操作：

  1. 对输入进行染色

  2. 根据指定条件，识别这些像checksum比较的指令，hook住。

  3. 然后就用cmp al, al patch原程序，这样就让这些checksum的判断一定为正。

    cNjq4U.png

    但这样的patch就会带来false positive，即这些输入的执行路径可能并不是这样的。

  4. RedQueen就会在之后进行输入验证，并修复他们。

  5. 在fix阶段，其实就是用magic bytes的方法，对checksum的位置进行替换。

    不过如果对于嵌套的校验和指令，就需要按照拓扑序（Topological Sort），一个一个的fix。

Mutate Structure Inputs:AFLSmart

对于输入复杂的、结构性强的程序，fuzzer通常会生成大量的无效输入。

因此AFLSmart将AFL和Peach结合起来，AFLSmart的输入为Peach pits格式，一种xml文件。

AFLSmart 将种子都表示为Peach pits格式，这样，就可以基于这些块进行变异，而不需要基于比特级的 变异。

cNjjgJ.png

AFL++

AFL++就将上述提到的诸多fuzzing技术都结合在一起，并提供了一种可供扩展的API。

Seed Scheduling

AFL++的Seed Scheduling就是基于AFLFast的种子调度。

AFL++的Power Schedules除了AFLFast提到的6种，还有另外两种，Mmopt和Rare。

Mmopt主要关注那些最新发现的种子

而Rare主要关注那些具有罕见边的种子。

cNjX34.png

Mutators

AFL++集成了许多mutator，包括RedQueen的Input-to-State mutator，包括Mopt mutator。

因此，AFL++就像一个框架，提供了一个自定义的mutator接口规范，实现这些接口，就可以将自己的mutator缝合到AFL++上，或者将不同的mutator缝合在一起。

AFL++除了提供了mutator的接口规范，还提供了trimming的借口规范。

Input-To-State Mutator

这个mutator是基于RedQueen的input-to-state.

这里主要介绍他和RedQueen不同的地方：

  • Colorization
    • RedQueen在染色时是保持程序执行路径不变，即hash of bitmap不变。
    • 而AFL++除了保持程序的执行路径不变，还对程序的执行时间做了一定控制，规定了程序的执行时间下界为2x slowdown
  • Bypass Comparison
    • AFL++采用的是一种probabilistic fuzzing。即如果这个roadblock，使用替换的方法，或者修复的方法失败了，那fuzzer下一次就会以较小概率尝试绕过他。（当下解决不了的困难，先放一放zzzz）
    • 不过其实RedQueen中也有相应的设计，RedQueen是使用的虚拟机断点hook cmp指令。因此，如果这个断电被hit的次数比较少，就将这个断点去掉。
  • CmpLog Instrumentation
    • RedQueen中采用的是虚拟机断点hook的cmp指令，当断点被hit时，再提取指令操作数。
    • 而AFL++则是使用的一种共享表，每一个指令都记录他的前256次执行的操作数。

MOpt

AFL++中也缝合了MOpt的Pilot和Core模块。

并且可以和Input-to-State结合。

Instrumentation

在插桩上，AFL++首先解决了边hit count溢出的问题。

因为在AFL中，边只会记录到255。

cNjOCF.png

有两种方法可以解决：

  1. NeverZero，加一个进位标志。NeverZero可以提高fuzzer的表现性能。
  2. Saturated Counters：当计数超过255时，就停在255。这个做法，不推荐，反而会让fuzzer的性能变差。

除了使用NeverZero，AFL++还使用了Ngram优化边覆盖率的统计。

AFL原生的统计边覆盖率的代码是：

1
2
3
cur_location = <COMPILE_TIME_RANDOM>; 
shared_mem[cur_location ^ prev_location]++; 
prev_location = cur_location >> 1;

AFL只考虑了上一个基本块和当前基本块，这样的计算速度更快，但会带来更多的碰撞。

而Ngram则是考虑当前基本块和前N-1个基本块表示该边，这样能部分碰撞，实验结果也表明Ngram能提高实验的性能。

AFL++实现了多种后端的插桩，具体实现的区别如下：

cNjzuR.png

Evaluation

略，具体可见slides 。

Reference

  1. AFL：https://afl-1.readthedocs.io/en/latest/

  2. AFLFast: https://mboehme.github.io/paper/CCS16.pdf

    https://github.com/mboehme/aflfast

  3. RedQueen:https://react-h2020.eu/m/filer_public/6d/86/6d869f98-f544-49cc-8221-b380c593888f/ndss19-redqueen.pdf

    https://hexgolems.com/talks/redqueen.pdf

  4. MOpt:https://www.usenix.org/system/files/sec19-lyu.pdf

  5. AFLSmart: https://thuanpv.github.io/publications/TSE19_aflsmart.pdf

  6. AFL++:https://aflplus.plus/papers/

    https://github.com/AFLplusplus/AFLplusplus

「Paper Reading」：AFL++：Combine Incremental Steps of Fuzzing Research

https://f7ed.com/2021/04/09/aflpp/

Author

f7ed

Posted on

2021-04-09

Updated on

2021-04-09

Licensed under

CC BY-NC-SA 4.0

 

Like this article? Support the author with

Comments

Email me
×