AFL插桩（二）LLVM模式插桩

————

一、LLVM模式插桩概述

AFL的 llvm_mode 可以实现编译器级别的插桩，可以替代 afl-gcc 或 afl-clang 使用的比较“粗暴”的汇编级别的重写的方法

优点：

编译器可以进行很多优化以提升效率
可以实现CPU无关，可以在非 x86 架构上进行fuzz
可以更好地处理多线程目标

AFL的 llvm_mode 文件夹下包含3个文件：

afl-llvm-rt.o.c 文件主要是重写了 afl-as.h 文件中的 main_payload 部分，方便调用
afl-llvm-pass.so.cc 文件主要是当通过 afl-clang-fast 调用 clang 时，这个pass被插入到 LLVM 中，告诉编译器添加与 afl-as.h 中大致等效的代码
afl-clang-fast.c 文件本质上是 clang 的 wrapper，最终调用的还是 clang 。但是与 afl-gcc 一样，会进行一些参数处理。

llvm_mode 的插桩思路就是通过编写pass来实现信息记录，对每个基本块都插入探针，具体代码在 afl-llvm-pass.so.cc 文件中，初始化和forkserver操作通过链接完成

Clang 编译器，从源码至机器码的流程如下：

代码首先由编译器前端clang处理后得到中间代码IR，然后经过各 LLVM Pass 进行优化和转换，最终交给编译器后端生成机器码，其中LLVM Pass 可以在中间过程处理 IR 、用户自定义的内容，可以用来遍历、修改 IR 以达到插桩、优化、静态分析等目的。

AFL进入llvm_mode进行编译afl-clang-fast（注意：llvm和clang版本要一致）

一个坑：最开始使用的llvm和clang版本是14版本，但编译会报错；改为11版本可以正常编译

# root @ zzz in ~/Desktop/AFL/llvm_mode on git:master o [14:18:42] C:2
$ make all
[*] Checking for working 'llvm-config'...
[*] Checking for working 'clang'...
[*] Checking for '../afl-showmap'...
[+] All set and ready to build.
clang -O3 -funroll-loops -Wall -D_FORTIFY_SOURCE=2 -g -Wno-pointer-sign -DAFL_PATH=\"/usr/local/lib/afl\" -DBIN_PATH=\"/usr/local/bin\" -DVERSION=\"2.57b\"  afl-clang-fast.c -o ../afl-clang-fast 
ln -sf afl-clang-fast ../afl-clang-fast++
clang++ `llvm-config --cxxflags` -Wl,-znodelete -fno-rtti -fpic -O3 -funroll-loops -Wall -D_FORTIFY_SOURCE=2 -g -Wno-pointer-sign -DVERSION=\"2.57b\" -Wno-variadic-macros -shared afl-llvm-pass.so.cc -o ../afl-llvm-pass.so `llvm-config --ldflags` 
clang -O3 -funroll-loops -Wall -D_FORTIFY_SOURCE=2 -g -Wno-pointer-sign -DAFL_PATH=\"/usr/local/lib/afl\" -DBIN_PATH=\"/usr/local/bin\" -DVERSION=\"2.57b\"  -fPIC -c afl-llvm-rt.o.c -o ../afl-llvm-rt.o
[*] Building 32-bit variant of the runtime (-m32)... failed (that's fine)
[*] Building 64-bit variant of the runtime (-m64)... success!
[*] Testing the CC wrapper and instrumentation output...
unset AFL_USE_ASAN AFL_USE_MSAN AFL_INST_RATIO; AFL_QUIET=1 AFL_PATH=. AFL_CC=clang ../afl-clang-fast -O3 -funroll-loops -Wall -D_FORTIFY_SOURCE=2 -g -Wno-pointer-sign -DAFL_PATH=\"/usr/local/lib/afl\" -DBIN_PATH=\"/usr/local/bin\" -DVERSION=\"2.57b\"  ../test-instr.c -o test-instr 
../afl-showmap -m none -q -o .test-instr0 ./test-instr < /dev/null
echo 1 | ../afl-showmap -m none -q -o .test-instr1 ./test-instr
[+] All right, the instrumentation seems to be working!
[+] All done! You can now use '../afl-clang-fast' to compile programs.

# root @ zzz in ~/Desktop/AFL/llvm_mode on git:master o [14:19:27] 
$ llvm-config --version     
11.1.0

# root @ zzz in ~/Desktop/AFL/llvm_mode on git:master o [14:19:41] 
$ clang --version
Ubuntu clang version 11.1.0-6
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bi

二、afl-clang-fast

afl-clang-fast实际上是CC/CXX的wrapper。它定义了一些宏，设置了一些参数，最终调用真正的编译器（CC指代C语言编译器，CXX指代C++编译器）

/* Main entry point */

int main(int argc, char** argv) {
  if (isatty(2) && !getenv("AFL_QUIET")) {
#ifdef USE_TRACE_PC
    SAYF(cCYA "afl-clang-fast [tpcg] " cBRI VERSION  cRST " by <lszekeres@google.com>\n");
#else
    SAYF(cCYA "afl-clang-fast " cBRI VERSION  cRST " by <lszekeres@google.com>\n");
#endif /* ^USE_TRACE_PC */
  }
  if (argc < 2) {

    SAYF("\n"
        "This is a helper application for afl-fuzz. It serves as a drop-in replacement\n"
        "for clang, letting you recompile third-party code with the required runtime\n"
        "instrumentation. A common use pattern would be one of the following:\n\n"

        "  CC=%s/afl-clang-fast ./configure\n"
        "  CXX=%s/afl-clang-fast++ ./configure\n\n"

        "In contrast to the traditional afl-clang tool, this version is implemented as\n"
        "an LLVM pass and tends to offer improved performance with slow programs.\n\n"

        "You can specify custom next-stage toolchain via AFL_CC and AFL_CXX. Setting\n"
        "AFL_HARDEN enables hardening optimizations in the compiled code.\n\n",
        BIN_PATH, BIN_PATH);

    exit(1);

  }
#ifndef __ANDROID__
  // 查找必备库'afl-llvm-rt.o' 或 'afl-llvm-pass.so'
  find_obj(argv[0]);
#endif
  // 设置CC或者CXX的参数
  edit_params(argc, argv);
  // 调用execvp来执行CC或者CXX
  execvp(cc_params[0], (char**)cc_params);
  FATAL("Oops, failed to execute '%s' - check your PATH", cc_params[0]);
  return 0;
}

三、afl-llvm-pass

afl-llvm-pass.so.cc实现了 LLVM-mode 下的一个插桩 LLVM Pass

llvm_mode是怎么插桩的呢？答：IRBuilder

afl-llvm-pass中，只有一个pass : AFLCoverage 该pass会在每一个基础块的第一个可插入指令处插桩，检测 控制流的覆盖程度
class AFLCoverage : public ModulePass {

runOnModule函数首先找出当前线程上下文中所对应的IntegerType，并且打印banner

bool AFLCoverage::runOnModule(Module &M) {

  LLVMContext &C = M.getContext();

  IntegerType *Int8Ty  = IntegerType::getInt8Ty(C);
  IntegerType *Int32Ty = IntegerType::getInt32Ty(C);

  /* Show a banner */

  char be_quiet = 0;

  if (isatty(2) && !getenv("AFL_QUIET")) {

    SAYF(cCYA "afl-llvm-pass " cBRI VERSION cRST " by <lszekeres@google.com>\n");

  } else be_quiet = 1;

之后获取预设的插桩密度（插桩率）

/* Decide instrumentation ratio */
// 获取代码的插桩率（0-100）
char* inst_ratio_str = getenv("AFL_INST_RATIO");
unsigned int inst_ratio = 100;

if (inst_ratio_str) {

  if (sscanf(inst_ratio_str, "%u", &inst_ratio) != 1 || !inst_ratio ||
      inst_ratio > 100)
    FATAL("Bad value of AFL_INST_RATIO (must be between 1 and 100)");
}

获取全局变量中指向共享内存的指针，以及上一个基础块的编号；这个共享内存上存放着各个控制流流经次数的计数器

/* Get globals for the SHM region and the previous location. Note that
   __afl_prev_loc is thread-local. */
// 指向  用于输出控制流覆盖次数的共享内存  的指针
GlobalVariable *AFLMapPtr =
    new GlobalVariable(M, PointerType::get(Int8Ty, 0), false,
                       GlobalValue::ExternalLinkage, 0, "__afl_area_ptr");

// AFLPrevLoc 用来表示前一个基本块的编号
GlobalVariable *AFLPrevLoc = new GlobalVariable(
    M, Int32Ty, false, GlobalValue::ExternalLinkage, 0, "__afl_prev_loc",
    0, GlobalVariable::GeneralDynamicTLSModel, 0, false);

获取上述这些信息后，for循环开始遍历所有基本块，进行插桩：

首先寻找BB中适合插入桩代码的位置，然后通过初始化 IRBuilder 实例执行插入：

/* Instrument all the things! */
int inst_blocks = 0;

for (auto &F : M)
  for (auto &BB : F) {
    // 在每一个基础块前都插入代码。先查找插入点
    BasicBlock::iterator IP = BB.getFirstInsertionPt();
    IRBuilder<> IRB(&(*IP));

    // 根据代码插桩率，随机插桩
    if (AFL_R(100) >= inst_ratio) continue;

插入load指令，获取当前基础块与上一个基础块的编号

// 随机获取当前的基础块编号
unsigned int cur_loc = AFL_R(MAP_SIZE);
ConstantInt *CurLoc = ConstantInt::get(Int32Ty, cur_loc);

/* Load prev_loc */
// 加载上一个基础块的编号
LoadInst *PrevLoc = IRB.CreateLoad(AFLPrevLoc);
// Metadata在这里可以看作是一种调试信息
PrevLoc->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
Value *PrevLocCasted = IRB.CreateZExt(PrevLoc, IRB.getInt32Ty());

插入load指令，获取共享内存地址；并通过上述两个编号，调用 CreateGEP 函数获取共享内存中指定index的地址

/* Load SHM pointer */
  // 获取指向共享内存的指针
  LoadInst *MapPtr = IRB.CreateLoad(AFLMapPtr);
  MapPtr->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
  // GEP: GetElementPtr
  // 根据当前基础块与上一个基础块的编号，计算指向特定地址的指针
  Value *MapPtrIdx =
      IRB.CreateGEP(MapPtr, IRB.CreateXor(PrevLocCasted, CurLoc));

插入load指令，获取对应index地址的值；同时插入add指令，使该地址上的计数器递增；再插入store指令写入新值，并更新共享内存

/* Update bitmap */

// 该指针上的counter值自增一
LoadInst *Counter = IRB.CreateLoad(MapPtrIdx);
Counter->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
Value *Incr = IRB.CreateAdd(Counter, ConstantInt::get(Int8Ty, 1));
IRB.CreateStore(Incr, MapPtrIdx)
    ->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));

右移cur_loc ，插入store指令，设置__afl_prev_loc，作为下一个插桩基础块的 “上一个基础块编号”

/* Set prev_loc to cur_loc >> 1 */

// 将当前基础块的编号右移1位后，存入AFLPrevLoc
StoreInst *Store =
    IRB.CreateStore(ConstantInt::get(Int32Ty, cur_loc >> 1), AFLPrevLoc);
Store->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));

inst_blocks++;

之所以要将当前基础块编号右移一位，是因为当基础块跳转A->A和B->B，或A->B和B->A，它们的编号做异或后的结果是相同的，无法区分，所以其中一个编号要右移一位。

当前基础块插桩完成，开始遍历下一个基础块

当插桩完成后，输出相关信息并返回

/* Say something nice. */
// 完成插桩
if (!be_quiet) {

  if (!inst_blocks) WARNF("No instrumentation targets found.");
  else OKF("Instrumented %u locations (%s mode, ratio %u%%).",
           inst_blocks, getenv("AFL_HARDEN") ? "hardened" :
           ((getenv("AFL_USE_ASAN") || getenv("AFL_USE_MSAN")) ?
            "ASAN/MSAN" : "non-hardened"), inst_ratio);

}
return true;

总结：

该pass插桩主要完成以下几点：
- 随机计算出当前基础块的编号
- 通过当前基础块编号与上一个基础块编号，计算出共享内存中对应的索引值idx 这块共享内存的实质就是一个hashtable
- __afl_area_ptr[idx]++
- 设置__afl_prev_loc为当前的基础块编号，当前基础块插桩结束，准备插桩下一个基础块
作用：
- 当有控制流到达当前基础块时，其共享内存对应位置，用于计数的值就会加一
- 而AFL可以根据该共享内存上的数据来判断控制流的覆盖程度，调整输入样本，使控制流能够覆盖更多的基础块

缺点：

编号存在碰撞。不过根据AFL文档中的介绍，对于不是很复杂的目标，碰撞概率还是可以接受的

Branch cnt | Colliding tuples | Example targets
------------+------------------+-----------------
      1,000 | 0.75%            | giflib, lzo
      2,000 | 1.5%             | zlib, tar, xz
      5,000 | 3.5%             | libpng, libwebp
     10,000 | 7%               | libxml
     20,000 | 14%              | sqlite
     50,000 | 30%              | -

示例设置export AFL_PATH=/root/Desktop/AFL，使其可以找到afl-llvm-rt.o 和 afl-llvm-pass.so 使用afl-clang-fast，对源码进行插桩，得到插桩后的IR指令

root@zzZ:/home/zzz/Desktop/AFL# ./afl-clang-fast -S -emit-llvm test.c 
afl-clang-fast 2.57b by <lszekeres@google.com>
afl-llvm-pass 2.57b by <lszekeres@google.com>
[+] Instrumented 5 locations (non-hardened mode, ratio 100%).
root@zzZ:/home/zzz/Desktop/AFL# gedit test.ll

其中，源码test.c：

//test.c
#include <stdio.h>
#include <unistd.h>

int main(int argc, char *argv[]) {
  char buffer[3] = {0};
  int i;
  int *null = 0;

  read(0, buffer, 3);
  if (buffer[0] == '6' && buffer[1] == '2' && buffer[2] == 'a') {
    i = *null;
  }

  puts("No problem");
}

插桩后的IR指令：

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [11 x i8] c"No problem\00", align 1
@__afl_area_ptr = external global i8*
@__afl_prev_loc = external thread_local global i32

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main(i32 %0, i8** %1) #0 !dbg !7 {
  %3 = load i32, i32* @__afl_prev_loc, align 4, !nosanitize !2
  %4 = load i8*, i8** @__afl_area_ptr, align 8, !nosanitize !2
  %5 = xor i32 %3, 3216
  %6 = getelementptr i8, i8* %4, i32 %5
  %7 = load i8, i8* %6, align 1, !nosanitize !2
  %8 = add i8 %7, 1
  store i8 %8, i8* %6, align 1, !nosanitize !2
  store i32 1608, i32* @__afl_prev_loc, align 4, !nosanitize !2
  %9 = alloca i32, align 4
  %10 = alloca i32, align 4
  %11 = alloca i8**, align 8
  %12 = alloca [3 x i8], align 1
  %13 = alloca i32, align 4
  %14 = alloca i32*, align 8
  store i32 0, i32* %9, align 4
  store i32 %0, i32* %10, align 4
  call void @llvm.dbg.declare(metadata i32* %10, metadata !14, metadata !DIExpression()), !dbg !15
  store i8** %1, i8*** %11, align 8
  call void @llvm.dbg.declare(metadata i8*** %11, metadata !16, metadata !DIExpression()), !dbg !17
  call void @llvm.dbg.declare(metadata [3 x i8]* %12, metadata !18, metadata !DIExpression()), !dbg !22
  %15 = bitcast [3 x i8]* %12 to i8*, !dbg !22
  call void @llvm.memset.p0i8.i64(i8* align 1 %15, i8 0, i64 3, i1 false), !dbg !22
  call void @llvm.dbg.declare(metadata i32* %13, metadata !23, metadata !DIExpression()), !dbg !24
  call void @llvm.dbg.declare(metadata i32** %14, metadata !25, metadata !DIExpression()), !dbg !27
  store i32* null, i32** %14, align 8, !dbg !27
  %16 = getelementptr inbounds [3 x i8], [3 x i8]* %12, i64 0, i64 0, !dbg !28
  %17 = call i64 @read(i32 0, i8* %16, i64 3), !dbg !29
  %18 = getelementptr inbounds [3 x i8], [3 x i8]* %12, i64 0, i64 0, !dbg !30
  %19 = load i8, i8* %18, align 1, !dbg !30
  %20 = sext i8 %19 to i32, !dbg !30
  %21 = icmp eq i32 %20, 54, !dbg !32
  br i1 %21, label %22, label %53, !dbg !33

22:                                               ; preds = %2
  %23 = load i32, i32* @__afl_prev_loc, align 4, !dbg !34, !nosanitize !2
  %24 = load i8*, i8** @__afl_area_ptr, align 8, !dbg !34, !nosanitize !2
  %25 = xor i32 %23, 40101, !dbg !34
  %26 = getelementptr i8, i8* %24, i32 %25, !dbg !34
  %27 = load i8, i8* %26, align 1, !dbg !34, !nosanitize !2
  %28 = add i8 %27, 1, !dbg !34
  store i8 %28, i8* %26, align 1, !dbg !34, !nosanitize !2
  store i32 20050, i32* @__afl_prev_loc, align 4, !dbg !34, !nosanitize !2
  %29 = getelementptr inbounds [3 x i8], [3 x i8]* %12, i64 0, i64 1, !dbg !34
  %30 = load i8, i8* %29, align 1, !dbg !34
  %31 = sext i8 %30 to i32, !dbg !34
  %32 = icmp eq i32 %31, 50, !dbg !35
  br i1 %32, label %33, label %53, !dbg !36

33:                                               ; preds = %22
  %34 = load i32, i32* @__afl_prev_loc, align 4, !dbg !37, !nosanitize !2
  %35 = load i8*, i8** @__afl_area_ptr, align 8, !dbg !37, !nosanitize !2
  %36 = xor i32 %34, 39935, !dbg !37
  %37 = getelementptr i8, i8* %35, i32 %36, !dbg !37
  %38 = load i8, i8* %37, align 1, !dbg !37, !nosanitize !2
  %39 = add i8 %38, 1, !dbg !37
  store i8 %39, i8* %37, align 1, !dbg !37, !nosanitize !2
  store i32 19967, i32* @__afl_prev_loc, align 4, !dbg !37, !nosanitize !2
  %40 = getelementptr inbounds [3 x i8], [3 x i8]* %12, i64 0, i64 2, !dbg !37
  %41 = load i8, i8* %40, align 1, !dbg !37
  %42 = sext i8 %41 to i32, !dbg !37
  %43 = icmp eq i32 %42, 97, !dbg !38
  br i1 %43, label %44, label %53, !dbg !39

44:                                               ; preds = %33
  %45 = load i32, i32* @__afl_prev_loc, align 4, !dbg !40, !nosanitize !2
  %46 = load i8*, i8** @__afl_area_ptr, align 8, !dbg !40, !nosanitize !2
  %47 = xor i32 %45, 25417, !dbg !40
  %48 = getelementptr i8, i8* %46, i32 %47, !dbg !40
  %49 = load i8, i8* %48, align 1, !dbg !40, !nosanitize !2
  %50 = add i8 %49, 1, !dbg !40
  store i8 %50, i8* %48, align 1, !dbg !40, !nosanitize !2
  store i32 12708, i32* @__afl_prev_loc, align 4, !dbg !40, !nosanitize !2
  %51 = load i32*, i32** %14, align 8, !dbg !40
  %52 = load i32, i32* %51, align 4, !dbg !42
  store i32 %52, i32* %13, align 4, !dbg !43
  br label %53, !dbg !44

53:                                               ; preds = %44, %33, %22, %2
  %54 = load i32, i32* @__afl_prev_loc, align 4, !dbg !45, !nosanitize !2
  %55 = load i8*, i8** @__afl_area_ptr, align 8, !dbg !45, !nosanitize !2
  %56 = xor i32 %54, 59797, !dbg !45
  %57 = getelementptr i8, i8* %55, i32 %56, !dbg !45
  %58 = load i8, i8* %57, align 1, !dbg !45, !nosanitize !2
  %59 = add i8 %58, 1, !dbg !45
  store i8 %59, i8* %57, align 1, !dbg !45, !nosanitize !2
  store i32 29898, i32* @__afl_prev_loc, align 4, !dbg !45, !nosanitize !2
  %60 = call i32 @puts(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str, i64 0, i64 0)), !dbg !45
  %61 = load i32, i32* %9, align 4, !dbg !46
  ret i32 %61, !dbg !46
}

; Function Attrs: nounwind readnone speculatable willreturn
declare void @llvm.dbg.declare(metadata, metadata, metadata) #1

; Function Attrs: argmemonly nounwind willreturn writeonly
declare void @llvm.memset.p0i8.i64(i8* nocapture writeonly, i8, i64, i1 immarg) #2

declare dso_local i64 @read(i32, i8*, i64) #3

declare dso_local i32 @puts(i8*) #3

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind readnone speculatable willreturn }
attributes #2 = { argmemonly nounwind willreturn writeonly }
attributes #3 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.dbg.cu = !{!0}
!llvm.module.flags = !{!3, !4, !5}
!llvm.ident = !{!6}

!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "Ubuntu clang version 11.1.0-6", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
!1 = !DIFile(filename: "test.c", directory: "/root/Desktop/AFL")
!2 = !{}
!3 = !{i32 7, !"Dwarf Version", i32 4}
!4 = !{i32 2, !"Debug Info Version", i32 3}
!5 = !{i32 1, !"wchar_size", i32 4}
!6 = !{!"Ubuntu clang version 11.1.0-6"}
/// other informations

可以看到插入了的IR代码：

%1 = load i32* @__afl_prev_loc, align 4, !nosanitize !25
%2 = load i8** @__afl_area_ptr, align 8, !nosanitize !25
%3 = xor i32 %1, 47106
%4 = sext i32 %3 to i64
%5 = getelementptr i8* %2, i64 %4
%6 = load i8* %5, align 1, !nosanitize !25
%7 = add i8 %6, 1
store i8 %7, i8* %5, align 1, !nosanitize !25
store i32 23553, i32* @__afl_prev_loc, align 4, !nosanitize !25

其中，47106是当前基本块的随机编号（key），23553是47106 >> 1 的结果