简介

  • 2022CCS即将发表的最新成果
  • Rust开发，快速、多平台、no_std兼容，可跨内核和计算机进行扩展
  • 这是一个框架，可以把所有fuzzer模块化整合到一起，实现不同fuzzer之间的有机融合

特性

  • 运行时开销低
  • 可扩展（本机、网络）
  • 可定制（更换自定义模块）
  • 跨平台（Windows、MacOS、Linux、Android）
  • 支持无源码二进制模糊测试

论文阅读

ccs22_fioraldi.pdf

ABSTRACT

  • 现在的问题：模糊测试的生态碎片化（很多Fork自AFL），将不同的Fuzzer结合工程开销巨大
  • 解决：用于构建模块化、可重用Fuzzer的框架——LibAFL

INTRODUCTION

  • 什么是Fuzzer：对一个目标程序应用大量自动生成的输入

  • Fuzzer的目标：发现有问题的状态（通常与漏洞相关）

  • 通用的Fuzzer：AFL、AFL++、HONGGFUZZ、LibFuzzer

  • 上述Fuzzer的问题：对专业用户而言局限性突出——测试的应用多种多样（操作系统内核、设备驱动、嵌入式设备…）

  • 之前的解决方法：Fork AFL/AFL++，定制自己的Fuzzer——导致大量不兼容的Fuzzer

  • 问题的根源：现在的所有Fuzzing框架都不是可扩展的，即便是AFL++这种高度可配置的Fuzzing架构也不够通用，无法模块化

  • 为解决上述问题，作者提出了Fuzzing的新框架——LibAFL(由Rust编写)

    • 组件化、可扩展
    • 构建自定义Fuzzer

Contributions

  • 区分、建模现代Fuzzer的通用模块
  • 提出LibAFL
  • 模块构建
  • 评估之前的15种技术以及它们的组合
  • 差分Fuzzer案例

BACKGROUND

  • 模糊测试的概念不应与BUG联系在一起

  • 模糊测试：一系列测试技术，反复向目标系统提供机器生成的输入，目的是找到满足特定目标的输入

  • 模糊测试的分类

    • 根据从目标获取的信息

      • 黑盒：近乎是随机测试，可能需要输入用例的格式
      • 白盒：利用目标内提供的信息（可能是代码覆盖率）
      • 灰盒：收集少量目标信息，保持较低性能开销

    • 根据如何产生输入用例

      • 基于模型（输入用例格式）
      • 基于变异

  • 反馈

    • 代码覆盖率
    • 比较指令两侧值的距离的最小化

AFL++

  • 最接近本文要求的Fuzzer——聚合各种技术，具有一定的可扩展性

    • custom mutators——自定义突变、最小化测试用例
    • 各种钩子

  • fork自AFL，受到了一些AFL的内在限制

  • 事实上，对大部分任务而言（除了突变器）

    • 独立的C代码仓库
    • 组件并未分离

  • 随着AFL++相关学术论文的发布，大量的工作成果被加入AFL++，使其越来越难以维护

  • 为避免AFL++的上述问题，从头开始编写了LibAFL

现代模糊测试的实体

定义了9个基本实体

  • Input

    • 程序输入(或程序输入的一部分)的内部表示
    • 最简单的情况下是字节数组
    • 其它种类：AST（执行前被序列化为字节序列）、编码成的整数、编程语言的中间表示
    • AFL的做法：直接存储和操作字节数组，执行时直接交给目标程序

  • Corpus

    • Input及其元数据的存储

    • 主要的存储方法

      • 内存

        • 速度快但空间有限

      • 磁盘

        • 主流Fuzzer采用
        • 允许用户检查Fuzzer状态，但有IO瓶颈。影响可扩展性，需要标准库执行IO操作

    • 本文提供的模型需要两个独立的语料库

      • 存储感兴趣的输入：用于生成新的测试用例
      • 存储满足目标的输入（例如程序崩溃）

  • Scheduler

    • 与语料库绑定
    • 从语料库中抽取一个测试用例来Fuzz
    • 简单的实现：FIFO或随机选择
    • 复杂的实现：基于Fuzzer内省统计的概率算法
    • 避免过于灵敏的反馈导致语料库爆炸
    • 优先考虑感兴趣的测试用例

  • Stage

    • 定义对语料库中单个测试用例的操作

    • 通常scheduler取出一个测试用例交给fuzzer执行

    • 含义广泛的实体

      • 对一个输入执行多次突变
      • 对白盒测试进行污点跟踪来收集信息
      • 测试用例最小化

  • Observer

    • 提供对目标程序单次执行的信息

    • 例子

      • coverage map

  • Executor

    • 根据fuzzer提供的输入执行目标程序

    • 根据fuzzer的类型区别较大

      • 驻内存的fuzzer：call to a harness function
      • 基于hypervisor的fuzzer：需要完整的操作系统，每次执行时从快照恢复

    • 告知程序fuzzer对本次执行希望的输入

      • 写入内存地址
      • 为harness function传参

    • 每次执行与一些Observers相联系

  • Feedback

    • 判断程序执行的结果我们是否感兴趣

      • 用于决定是否加入语料库
      • 寻找满足特定目标的solutions

    • 与Observer紧密相关

  • Mutator

    • 根据1个或多个输入生成新的输入

  • Generator

    • 从0开始生成新的输入

FRAMEWORK ARCHITECTURE

  • 目标：可重用组件、模块化设计

全局设计与原则

  • 关键性的三个原则

    • 可扩展性（组件）

    • 可移植性

      • 核心库以独立于操作系统的方式开发
      • 核心组件不依赖于任何标准库

    • 可伸缩性（多核心/多机）

      • 基于事件的接口

  • 现有的fuzzing框架的问题

    • 并不是完全可扩展的

    • 不能在没有标准库的系统上编译

    • 可伸缩性差

    • AFL及其衍生品基于磁盘IO和代价高的系统调用（如fork）

      • 导致多核运行时效果很差

    • HonggFuzz可伸缩性稍好些，但基于系统调用来控制目标，并在所有并行线程之间维护共享状态，这会导致锁的竞争问题

    • LibFuzzer可伸缩性最好，但不同节点在Fuzz时不能通信，在自定义的时间间隔后合并语料库，然后重启fuzzer

  • 为实现三个目标，LibAFL基于三个核心库

    • LibAFL Core

      • 主库，包含模糊测试组件及其实现
      • 大部分只依赖于Rust core+alloc，可以在没有标准库的情况下运行

    • LibAFL Targets

      • 包含要插入目标程序中的代码，如用于追踪代码覆盖率的运行时库

    • LibAFL CC

      • 提供编写LibAFL编译器的包装器的功能（通过提供一系列关于插桩的编译器扩展）

  • LibAFL还包含几个插桩后端（Instrumentation Backends），提供了将LibAFL连接到不同执行引擎的能力（QEMU、Frida）

  • 这些库都是用于创建fuzzer前端（Fuzzer Frontends）的工具集

    • 已经有一些可用的fuzzer前端#不理解#前端和后端分别指什么？
    • LibAFL Sugar提供了高层次的一些API，可以用几行代码快速构建一个Frontends
    • 为Sugar提供python绑定，以便在无需重新编译的情况下快速创建Fuzzer原型

核心库

  • 架构图中的组件与现代模糊测试的实体中定义的实体大多是一一对应的，另外，还有三个组件集State、Fuzzer和Events Manager
  • 每个组件都对应一个Rust通用trait，可以与其它无关的组件组合使用

  • 在不明显损失性能的前提下实现了组件的抽象

    • 不适用面向对象，而是使用Rust中的通用trait，由此，编译器可以进行明显的优化

    • 在一个通用trait中相关组件被看作是通用参数

    • 可以通过组合来派生出新的组件

    • 组件之间在编译时进行连接

    • 使用编译时列表来指定多个对象#不理解#编译时列表是个什么概念？

      • 可以检索在内存中的某个对象，比如feedback可以访问observers，以判断当前执行是否有些我们感兴趣的东西

    • 基于Rust强大的编译时机制，我们的代码优化程度很高，并且可以有效地内联

  • 使用State保存非易失性数据

    • 非易失性数据如执行次数、伪随机数生成器状态、语料库
    • 目的：使用Rust的序列化功能实现暂停fuzz和随后继续进行fuzz，而无需重新执行整个语料库

  • Fuzzer组件中包含了fuzzer能够执行的所有操作

    • 如Feedbacks、Objectives、Scheduler等所有可能影响fuzzer状态的操作
    • 如何处理单个输入用例、如何评估一个新的输入

  • Events Manager

    • 用于产生和处理事件，可以用于同步多节点之间的并行fuzz，或者仅仅作为运行日志
    • 不会引入新的瓶颈，因为每个fuzzer都运行在独立的数据集，而且事件会延迟到特定的时间点
    • 例子

  • Metadata System#不理解#

    • Fuzzing算法通常需要推断关于测试用例或fuzzer整体状态或的信息，LibAFL必须提供对测试用例或State数据的扩展方法

    • 在LibAFL中，任何实现SerdeAny trait的结构体都可以被用作metadata

      • 测试用例和State都维护一个自身类型的映射表#不理解#从什么到什么的映射？

    • LibAFL唯一引入了一小部分运行开销的地方，主要是查找映射表

  • 可组合的Feedbacks

    • LibAFL支持对feedbacks进行逻辑运算

  • Monitor

插桩后端

  • LibAFL可以轻松地与任何插桩后端结合，如二进制转换器或编译插桩器，默认提供LLVM、SanitizerCoverage、QEMU usermode和Frida

  • SanCov的使用——添加一个编译器标志位即可，允许用户创建兼容非C/C++但支持SanCov的前端，如python的Atheris和Rust的cargo-fuzz

  • LibAFL CC提供一系列基于LLVM的方法来扩展基于LLVM的编译器（如Clang）用以跟踪各种代码覆盖率

  • LibAFL QEMU为Rust提供了模拟器API的Hook能力，从而能够控制目标的执行

    • 该库公开了一些结构，如excutors和helpers，用来安装默认hook

  • LibAFL Frida

    • 与LibAFL QEMU类似，但没有清晰的host-guest划分
    • 不仅限于Linux，可以在各种操作系统上工作

  • LibAFL Concolic#不理解#是将fuzz与符号执行相结合了吗？

APPLICATIONS AND EXPERIMENTS

  • 关注四个问题

    • roadblocks bypassing
    • structure-aware fuzzing
    • corpus scheduling
    • energy assignment

Bypassing Roadblocks

  • 2016年LibFuzzer最先提出value-profile，即通过将比较指令两操作数之间的匹配位数最大化来解决二进制数比较的roadblock

    • 在LibAFL中，使用map observer和feedback来解决这个问题，称为MaxMapFeedback

  • LibAFL提供了AFL++中的cmplog技术

    • 基于REDQUEEN和WEIZZ
    • 在比较指令和任何以两个指针作为参数的函数上插桩，在运行时将相关值记录在map中

  • LibAFL提供了AFL++中的autotokens技术

    • 从比较指令和有立即数的函数中提取token，编码成二进制
    • 基于LibAFL的fuzzer能获取这些token，加入到State的元数据中，随后将这些数据应用到突变器中
    • 没有什么额外的开销，所以没有理由不采用

  • 衍生出了四种选项：plain、value_profile、cmplog、value_profile_cmplog

    • 在测试中，cmplog表现最好，其余依次为value_profile_cmplog、plain、value_profile

Structure-aware Fuzzing

  • 在不知道输入格式的情况下学习输入格式

  • Nautilus——基于语法的覆盖率导向的fuzzer，使用语法树作为语料库，有相应的突变器

    • LibAFL实现了语法树的输入格式，引入ScheduledMutator

  • Gramatron——使用grammar-to-automatad的转换技术来实现快速的突变器

    • LibAFL提供类似的工具，与NAUTILUS的结构和底层实现不同

  • Grimoire——使用不怎么改变代码覆盖率的输入部分来生成类似语法树的结构，执行类似语法树的突变

    • LibAFL中有相关的实现
  • Nautilus整体表现最好

Corpus Scheduling

  • 如何从语料库中选择下一个测试用例

  • AFL——维护一个favored种子集

    • LibAFL中的实现——MinimizerScheduler，根据map的feedback计算minset

  • AFL++——基于概率抽样

    • LibAFL中有相关的实现

  • TortoiseFuzz——基于三个指标（块内存操作、函数内存操作、循环回边计数）

    • 需要自定义插桩，在LibAFL CC中基于LLVM和一个新的相关的Observer实现

  • AFL++中的方法效果最好，AFL次之，但总的来说即便与随机选择相比也差别不大

    • 可能与目标执行的速度有关，对于执行较慢的目标可能影响会大一些

Energy Assignment

  • 决定语料库中的一个属于要突变多少次

  • 最简单的方法——指定一个常数

  • 最常用的方法——在一定时间间隔内为每个种子随机赋值

    • LibAFL中的plain算法（1~128）

  • AFLFast提供了6中不同的算法

    • LibAFL中基于元数据实现了AFLFast中的6种算法
  • explore效果最好，fast次之
  • 要看具体的目标程序

A Generic Bit-level Fuzzer

  • 与AFL++、HonggFuzz等对比，LibAFL表现很突出

Differential Fuzzing

  • 可以采用不基于代码覆盖率的feedback

    • type hash

Third-Party Applications

LIMITATIONS AND FUTURE WORK

  • 定向fuzzing
  • concolic tracing API
  • 可伸缩性的验证

LibAFL book阅读

汉化版：https://libafl-book-zh.zu1k.com/

简介

  • LibAFL不只是一个fuzzer，而是一个可重复使用的个体fuzzer的集合

入门

Crates

  • crate: 一个模块的树形结构，是一个独立的可编译单元

  • LibAFL中的crate

    • libafl

      • 主crate，包含了构建fuzzer所需的所有组件

    • libafl_sugar

      • 不灵活但层次高，易于使用

    • libafl_derive

      • 与libafl配对的proc-macro板块
      • 暴露derive宏，可以用来定义Metadata结构

    • libafl_targets

      • 提供与目标交互的代码

    • libafl_cc

      • 包装编译器和创建源码级fuzzer

    • libafl_frida

      • 将LibAFL与Frida作为插桩分析的后端连接起来
      • 支持Linux/MacOS/Windows/Android
      • 支持Cmplog和ASAN插桩

    • libafl_qemu

      • 将LibAFL与QEMU用户模式连接起来
      • 支持Linux
      • 支持钩子和插桩选项

fuzzer示例

核心概念

Observer

  • 向Fuzzer提供在目标程序执行期间观察到的信息
  • 在不同的执行过程中信息是不被保留的，是对程序的动态属性的观察
  • 可以结合Hook做到修改Fuzzer状态等

Executor

  • 定义如何执行目标及所有与目标的单次运行有关的易失性操作

  • LibAFL默认实现了一些Executor

    • InProcessExecutor

    • ForkserverExecutor

      • 通过环境变量告诉fork的子进程map在哪里
      • 在Fuzzer中可以将map传递给Observer，从而获得与Feedback相结合的覆盖率反馈

    • InprocessForkExecutor

      • 与InprocessForkExecutor唯一的区别：在运行约束函数之前进行fork

Feedback

  • 将目标程序的执行结果分类为是否有趣

    • 有趣→添加到语料库中

  • 处理一个或多个Observer报告的信息，以决定是否有趣

Input

  • 从外部来源获取的影响程序行为的数据，在LibAFL抽象出的Fuzz模型中定义为程序输入（或一部分）的内部表示
  • 通常是字节数组，但在语法Fuzzer中可能是抽象语法树
  • 只能由可序列化的结构来实现

Corpus

  • 存储测试用例的地方

    • 测试用例的定义：一个输入和一组相关的元数据（如执行时间）
    • 磁盘上/内存中/…

  • 有趣的测试用例会被添加到一个语料库中，还有一个语料库用来存储实现目标的测试用例

  • Fuzzer从语料库中挑选下一个测试用例进行Fuzz，LibAFL中决定挑选测试用例策略的方法是CorpusScheduler

Mutator

  • 接受一个或多个输入并生成一个新的派生输入的实体
  • 一个Mutator可以包含多种类型的突变，例如对于字节流输入而言，比特翻转、随机替换一个字节的块等

Generator

  • 从头生成输入的组件
  • 随机发生器：生成随机输入

Stage

  • 定义对语料库中得到的单一输入进行的操作

  • 有很多种Stage

    • 突变阶段：给定输入，应用一个突变器并执行一次或多次生成的输入
    • 分析阶段
    • 修剪阶段：减少测试用例的大小

设计

架构

  • 围绕实体建立，允许代码重用、低成本抽象

  • 代码重用基于组件而不是子类，但库中仍有一些面向对象的模式

  • 另外引入Testcase和State实体

    • Testcase是语料库中输入及其元数据的容器，也就是说语料库中存储的单元其实是Testcase

    • State包含Fuzzer运行时变化的所有元数据，包括语料库

      • State包含的都是可序列化的自有对象
      • State本身也是可序列化的，从而可以暂停和继续Fuzz

元数据

  • 从代码实现的角度而言，被定义为在SerdeAny寄存器中注册的Rust结构

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

    #![allow(unused)]
    fn main() {
    extern crate libafl;
    extern crate serde;

    use libafl::SerdeAny;
    use serde::{Serialize, Deserialize};

    #[derive(Debug, Serialize, Deserialize, SerdeAny)]
    pub struct MyMetadata {
        //...
    }
    }

  • 必须是静态结构，不能有对借用对象的引用

  • 主要用于SerdeAnyMap和NamedSerdeAnyMap中

  • 默认情况下Testcase和State实现了HasMetadata trait，并持有一个SerdeAnyMap测试用例

消息传递

  • 主要用途：多核Fuzz

安装

安装依赖

建议先安装Clang和LLVM再安装Rust

构建libAFL

1
2
3
4
5
6
7
git clone https://github.com/AFLplusplus/LibAFL
cargo build --release
# 构建API文档，在2022.8.25时Windows端不可用，会报错
cargo doc
# 浏览libAFL文档
cargo install mdbook
cd docs && mdbook serve

使用提供的fuzzer示例

  • 跟随fuzzers目录下任何一个fuzzer中的README文档即可复现