基于LLVM分析Pass实现令牌捕获

日期：2016年11月27日
作者：Axel “0vercl0k” Souchet
分类：杂项
标签：模糊测试, clang, llvm, 分析pass, pass

引言

大约三年前，LLVM框架开始因为多种原因引起我的兴趣。这个工业级编译器技术集合，正如Latner在2008年所说，采用了高度模块化的设计方式。它似乎拥有许多有趣的功能，可以应用于多个不同领域：代码优化（如反混淆）、（架构无关的）代码混淆、静态代码插桩（如消毒器）、静态分析、运行时软件利用缓解（如CFI、SafeStack）、驱动模糊测试框架（如libFuzzer）等等。

这个庞大库的强大功能部分源于它主要在三个阶段进行操作，并且你可以在任何阶段自由挂接代码：前端、中端和后端。其他优势包括：大量的后端支持、完善的文档、C/C++ API、活跃的社区、以及相比GCC更易用（参见kcc的演示）等。

前端部分接收源代码并生成LLVM中间语言（IL）代码，中端操作LLVM IL，最后后端接收LLVM IL以输出汇编代码和/或可执行文件。

在本文中，我们将逐步介绍一个简单的LLVM Pass，它既不进行优化，也不进行混淆，而是作为模糊测试的令牌查找器。

背景

灵感来源

如果你还没有听说过lcamtuf的新覆盖引导模糊测试器（AFL），很可能是因为你在过去一两年里生活在山洞里，因为它基本上无处不在（现在在这个博客上也提到了！）。如果你想了解更多并跟踪其开发，源代码、文档和afl-users群组是非常棒的资源。

本文需要了解的是，该模糊测试器生成测试用例，并根据它们执行的代码覆盖率来挑选和保留有趣的用例。你最终会得到一组覆盖代码不同部分的测试用例，并且可以花更多时间锤击和变异少量文件，而不是无数个文件。它还包含了许多巧妙的技巧，使其成为当今最常用/易用的模糊测试器之一（不要问我证据来支持这个说法）。

为了测量代码覆盖率，AFL的第一个版本会挂接到编译器工具链中，并在gcc生成的.S文件中插桩基本块。插桩会翻转位图中的一位，表示“我已经执行了这部分代码”。这种基于每个块的静态插桩（与基于DBI的插桩相反）使其非常快，并且可以在模糊测试时使用而不会产生太多开销。一段时间后，设计了一个基于LLVM的版本（由László Szekeres和lcamtuf设计），以减少黑客性、架构无关（编写Pass时免费获得的奖励）并且非常优雅（不再需要读取/修改原始的.S文件）。实现方式是通过挂接到中端，静态添加afl-fuzz所需的额外插桩，以获得代码覆盖率反馈。这现在被称为afl-clang-fast。

稍后，谷歌群组上的一些讨论让读者相信，了解库使用的“魔法值”会使模糊测试更高效。如果我了解所有魔法值并有办法检测它们在测试用例中的位置，那么我可以使用它们而不是位翻转，并希望这会导致“更好”的模糊测试。这个“魔法值”列表被称为字典。而我刚才所说的“魔法值”就是“令牌”。你可以通过-X选项向afl提供这样的字典（令牌列表）。为了简化、自动化半自动生成字典文件的过程，lcamtuf开发了一个基于LD_PRELOAD和插桩内存比较例程（如strcmp、memcmp等）调用的运行时解决方案。如果其中一个参数来自只读节，那么它很可能是一个令牌，并且很可能是字典的好候选。这被称为afl-tokencap。

afl-llvm-tokencap

如果不依赖运行时解决方案，该方案要求你：

构建足够完整的语料库以执行暴露令牌的代码，
使用一组额外选项重新编译目标，告诉编译器不要使用strcmp/strncmp/etc的内置版本，
通过新的二进制文件运行每个测试用例，并使用LD_PRELOAD加载libtokencap。

我们在编译时构建字典。背后的想法是，让另一个Pass挂接构建过程，在编译时查找令牌，并构建一个字典，供你的第一次模糊测试运行使用。感谢LLVM，这可以用不到400行代码编写。它易于阅读、编写，并且是架构无关的，因为它甚至在后端之前运行。

这就是我将在本文中带你解决的问题，也就是另一个LLVM Pass的例子。无论如何，这是一个回归博客的机会，有人甚至可能会说！

在深入之前，以下是我们希望Pass实际做的事情：

遍历编译的每条指令，找到所有函数调用，
当函数调用目标是感兴趣的函数之一（strcmp、memcmp等）时，我们提取参数，
如果其中一个参数是硬编码字符串，那么我们将其保存为编译时构建的字典中的令牌。

afl-llvm-tokencap-pass.so.cc

如果你已经非常熟悉LLVM及其Pass机制，这里是afl-llvm-tokencap-pass.so.cc和afl.patch - 它大约有300行C++代码，并且非常容易理解。

现在，对于所有其他想浏览源代码的人，让我们开始吧。

AFLTokenCap类

这个文件最重要的部分是AFLTokenCap类，它遍历LLVM IL指令以查找令牌。LLVM在编写Pass时给你提供了在不同粒度级别上工作的可能性（从最细粒度到最粗粒度）：BasicBlockPass、FunctionPass、ModulePass等。注意，这些并不是唯一的，还有相当多其他工作方式略有不同的：MachineFunctionPass、RegionPass、LoopPass等。

当你编写Pass时，你编写一个继承Pass父类的类。这样做意味着你期望实现不同的虚拟方法，这些方法将在特定情况下被调用 - 但基本上你有三个函数：doInitialization、runOn和doFinalization。第一个和最后一个很少使用，但它们可以为你提供一种在所有基本块运行之前或之后执行代码的方式。不过runOn*函数很重要：这是一个将使用LLVM对象调用的函数，你可以自由遍历（根据LLVM命名法为分析Pass）或修改（转换Pass）它。正如我上面所说，LLVM对象基本上是Module/Function/BasicBlock实例。如果不太明显，一个Module（一个.c文件）由Functions组成，一个Function由BasicBlocks组成，而一个BasicBlock是一组Instructions。我还建议你查看LLVM wiki的HelloWorld Pass，它应该给你另一个简单的例子来理解Pass的概念。

对于今天的用例，我选择继承BasicBlockPass，因为我们的分析不需要除了BasicBlock之外的任何东西。这是因为我们主要对捕获传递给某些函数调用的某些参数感兴趣。以下是LLVM IR世界中函数调用的样子：

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


%retval = call i32 @test(i32 %argc)
call i32 (i8*, ...)* @printf(i8* %msg, i32 12, i8 42)   ; yields i32
%X = tail call i32 @foo()                               ; yields i32
%Y = tail call fastcc i32 @foo()                        ; yields i32
call void %foo(i8 97 signext)

%struct.A = type { i32, i8 }
%r = call %struct.A @foo()             ; yields { i32, i8 }
%gr = extractvalue %struct.A %r, 0     ; yields i32
%gr1 = extractvalue %struct.A %r, 1    ; yields i8
%Z = call void @foo() noreturn         ; indicates that %foo never returns normally
%ZZ = call zeroext i32 @bar()          ; Return value is %zero extended

每次调用AFLTokenCap::runOnBasicBlock时，LLVM中端都会调用我们的分析Pass（无论是静态链接到clang/opt中还是动态加载）并传递一个引用传递的BasicBlock。从那里，我们可以迭代基本块中包含的指令集并找到调用指令。每条指令都继承顶层的llvm::Instruction类 - 为了过滤，你可以使用dyn_cast模板函数，它类似于dynamic_cast操作符，但不依赖RTTI（并且更高效 - 根据LLVM编码标准）。与BasicBlock对象上的基于范围的for循环结合使用，你可以迭代所有你想要的指令。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


bool AFLTokenCap::runOnBasicBlock(BasicBlock &B) {

  for(auto &I_ : B) {

    /* Handle calls to functions of interest */
    if(CallInst *I = dyn_cast<CallInst>(&I_)) {

      // [...]
    }
  }
}

一旦我们找到了一个llvm::CallInst实例，我们需要：

获取被调用函数的名称，假设它不是间接目标：llvm::CallInst::getCalledFunction
仅当它是感兴趣的函数时才进一步分析：strcmp、strncmp、strcasecmp、strncasecmp、memcmp
提取传递给函数的参数：llvm::CallInst::getNumArgOperands、llvm::CallInst::getArgOperand
检测硬编码字符串（我们将其中一部分视为令牌）

不确定你是否已经注意到，但我们正在处理的所有对象不仅继承自llvm::Instruction。你还必须处理llvm::Value，这是一个更顶层的类（llvm::Instruction是llvm::Value的子类）。但llvm::Value也用于表示常量：考虑硬编码字符串、整数等。

检测硬编码字符串

为了检测传递给函数调用的参数中的硬编码字符串，我决定过滤掉llvm::ConstantExpr。正如其名称所示，这个类处理“使用其他常量值的表达式初始化的常量值”。

最终目标是找到llvm::ConstantDataArrays并检索它们的原始值 - 这些将是我们要找的硬编码字符串。

1
2
3
4
5


/home/over/workz/afl-2.35b/afl-clang-fast -c -W -Wall -O3 -funroll-loops   -fPIC -o png.pic.o png.c
[...]
afl-llvm-tokencap-pass 2.35b by <0vercl0k@tuxfamily.org>
[...]
[+] Call to memcmp with constant "\x00\x00\xf6\xd6\x00\x01\x00\x00\x00\x00\xd3" found in png.c/png_icc_check_header

此时，Pass基本上完成了令牌捕获库能够做的事情。

收集整数立即数

不过在libpng上玩了一会儿之后，我很快想知道为什么Pass没有提取我在afl已经生成和提供的字典中找到的所有常量：

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


// png.dict
section_IDAT="IDAT"
section_IEND="IEND"
section_IHDR="IHDR"
section_PLTE="PLTE"
section_bKGD="bKGD"
section_cHRM="cHRM"
section_fRAc="fRAc"
section_gAMA="gAMA"
section_gIFg="gIFg"
section_gIFt="gIFt"
section_gIFx="gIFx"
section_hIST="hIST"
section_iCCP="iCCP"
section_iTXt="iTXt"
...

其中一些可以在pngpread.c文件中的png_push_read_chunk函数中找到，例如：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


//png_push_read_chunk
#define png_IHDR PNG_U32( 73,  72,  68,  82)
// ...
if (chunk_name == png_IHDR)
{
  if (png_ptr->push_length != 13)
      png_error(png_ptr, "Invalid IHDR length");

  PNG_PUSH_SAVE_BUFFER_IF_FULL
  png_handle_IHDR(png_ptr, info_ptr, png_ptr->push_length);
}
else if (chunk_name == png_IEND)
{
  PNG_PUSH_SAVE_BUFFER_IF_FULL
  png_handle_IEND(png_ptr, info_ptr, png_ptr->push_length);

  png_ptr->process_mode = PNG_READ_DONE_MODE;
  png_push_have_end(png_ptr, info_ptr);
}
else if (chunk_name == png_PLTE)
{
  PNG_PUSH_SAVE_BUFFER_IF_FULL
  png_handle_PLTE(png_ptr, info_ptr, png_ptr->push_length);
}

为了也捕获这些家伙，我决定添加对带有整数立即数的比较指令的支持（在其中一个操作数中）。再次感谢LLVM，这真的很容易实现：我们只需要找到llvm::ICmpInst指令。唯一要记住的是误报。为了降低误报率，我选择仅当整数立即数完全是ASCII（如上面的libpng令牌）时才将其视为令牌。

我们甚至可以更进一步，通过相同的策略处理switch语句。唯一的额外步骤是从switch语句中检索每个case：llvm::SwitchInst::cases。

1
2
3
4
5
6
7
8


/* Handle switch/case with integer immediates */
else if(SwitchInst *SI = dyn_cast<SwitchInst>(&I_)) {
  for(auto &CIT : SI->cases()) {

    ConstantInt *CI = CIT.getCaseValue();
    dump_integer_token(CI);
  }
}

局限性

主要的局限性是，由于你应该在编译过程中运行Pass，它很可能会最终编译库附带的测试或实用程序。现在，这很烦人，因为它可能会给你的令牌添加一些噪音 - 特别是实用程序。这些通常解析输入参数，有些使用带有硬编码字符串的strcmp类函数来进行解析。

我实现的部分解决方案（如，它减少了噪音，但没有完全消除）只是不处理任何名为main的函数。我见过的大多数情况（样本集相当小，我不会说谎>:]），这种参数解析是在main函数中完成的，并且通过黑名单很容易不处理它，如下所示：

1
2
3
4
5
6
7


bool AFLTokenCap::runOnBasicBlock(BasicBlock &B) {
// [...]
  Function *F = B.getParent();
  m_FunctionName = F->hasName() ? F->getName().data() : "unknown";

  if(strcmp(m_FunctionName, "main") == 0)
    return false;

我想实验但没有实验的另一件事是提供一个类似正则表达式的字符串（考虑“test/*”），并且不处理匹配它的每个文件/路径。你可以通过这个轻松黑名单整个测试目录。

演示

我没有花太多时间在很多代码库上尝试它（不过如果你在你的代码库上运行它，请随时向我发送反馈！），但这里有一些示例结果，具有不同程度的成功..或不成功。从libpng开始：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57


over@bubuntu:~/workz/lpng1625$ AFL_TOKEN_FILE=/tmp/png.dict make
cp scripts/pnglibconf.h.prebuilt pnglibconf.h
/home/over/workz/afl-2.35b/afl-clang-fast -c -I../zlib  -W -Wall -O3 -funroll-loops   -o png.o png.c
afl-clang-fast 2.35b by <lszekeres@google.com>
afl-llvm-tokencap-pass 2.35b by <0vercl0k@tuxfamily.org>
afl-llvm-pass 2.35b by <lszekeres@google.com>
[+] Instrumented 945 locations (non-hardened mode, ratio 100%).
[+] Found alphanum constant "acsp" in png.c/png_icc_check_header
[+] Call to memcmp with constant "\x00\x00\xf6\xd6\x00\x01\x00\x00\x00\x00\xd3" found in png.c/png_icc_check_header
[+] Found alphanum constant "RGB " in png.c/png_icc_check_header
[+] Found alphanum constant "GRAY" in png.c/png_icc_check_header
[+] Found alphanum constant "scnr" in png.c/png_icc_check_header
[+] Found alphanum constant "mntr" in png.c/png_icc_check_header
[+] Found alphanum constant "prtr" in png.c/png_icc_check_header
[+] Found alphanum constant "spac" in png.c/png_icc_check_header
[+] Found alphanum constant "abst" in png.c/png_icc_check_header
[+] Found alphanum constant "link" in png.c/png_icc_check_header
[+] Found alphanum constant "nmcl" in png.c/png_icc_check_header
[+] Found alphanum constant "XYZ " in png.c/png_icc_check_header
[+] Found alphanum constant "Lab " in png.c/png_icc_check_header
[...]

over@bubuntu:~/workz/lpng1625$ sort -u /tmp/png.dict
"abst"
"acsp"
"bKGD"
"cHRM"
"gAMA"
"GRAY"
"hIST"
"iCCP"
"IDAT"
"IEND"
"IHDR"
"iTXt"
"Lab "
"link"
"mntr"
"nmcl"
"oFFs"
"pCAL"
"pHYs"
"PLTE"
"prtr"
"RGB "
"sBIT"
"sCAL"
"scnr"
"spac"
"sPLT"
"sRGB"
"tEXt"
"tIME"
"tRNS"
"\x00\x00\xf6\xd6\x00\x01\x00\x00\x00\x00\xd3"
"XYZ "
"zTXt"

在sqlite3上（sqlite.dict）：

1
2
3
4
5
6


over@bubuntu:~/workz/sqlite3$ AFL_TOKEN_FILE=/tmp/sqlite.dict [/home/over/workz/afl-2.35b/afl-clang-fast stub.c sqlite3.c -lpthread -ldl -o a.out
[...]
afl-llvm-tokencap-pass 2.35b by <0vercl0k@tuxfamily.org>
afl-llvm-pass 2.35b by <lszekeres@google.com>
[+] Instrumented 47546 locations (non-hardened mode, ratio 100%).
[+] Call to strcmp with constant "unix-excl" found