1. 编译时程序插桩(Compile-time Instrument)
程序插桩是在保证被测程序原有逻辑完整性的基础上在程序中插入一些探针代码，以在程序动态执行时收集内部运行信息，用于进行程序分析或安全分析。典型地，可以通过插桩获取程序的控制流（例如代码覆盖情况）和数据流（例如运行时变量值）信息。代表性的基于程序插桩的工具/框架有LLVM DataSanitizer、American Fuzzy Lop、SymCC等，对程序分析、软件安全测试具有重要意义。
程序插桩主要有三类方案，适用于不同的目标和场景：
- 编译时插桩：适用于有源码的白盒情况，通常在中间语言上进行插桩，插桩的代码能够从编译优化中收益，是开销最低的插桩方案。
- 动态二进制插桩：适用于无源码的黑盒情况。大多数动态二进制插桩框架都有三种执行模式：解释模式（ Interpretation mode）、探测模式（probe mode）和JIT模式（just-in-time mode）。JIT模式是最常用的实现方式，例如Intel Pin。但同时，相比编译时插桩，无论解释还是JIT都引入了更多的额外开销。
- 静态二进制插桩：适用于无源码的黑盒情况。静态二进制插桩主要是通过二进制重写技术来实现的，即在汇编语言的级别上进行插桩，插桩的代码是直接写入目标程序的二进制文件中的。静态二进制插桩的效率通常认为高于动态二进制插桩，但低于编译插桩。目前Linux平台上二进制重写技术比较成熟，但windows平台上的静态二进制插桩框架还比较少（WinAFL就应用了静态二进制插桩技术来提升效率）。
程序插桩技术广泛应用于程序分析/自动化漏洞挖掘研究与实践中，例如：
- 基于覆盖率反馈的模糊测试（AFL）
- 污点分析（LLVM Dsan， Angora）
- 符号执行（SymCC）
- ...
LLVM框架在编译时允许用户编写自己的LLVM Pass，在中间语言（LLVM IR）级别进行程序插桩，结合LLVM IR提供的丰富程序信息，可以结合静态分析更好地进行插桩。
个人认为学习LLVM编译插桩最好的途径是找到应用该技术的一些开源项目，例如AFL，结合官方文档进行学习。以下，仅分享一些我们之前工作中用到的有意思的API的示例代码
2. 插桩分支代码：BranchInst
2.1 splitblockandinsertifthenelse（）
见stackoverflow
2.2 SplitBlockAndInsertIfThen()
或者仅仅想插桩if ... then ...的逻辑，就可以用SplitBlockAndInsertIfThen()，其使用相对简单些，一个例子如下：
1 2 3 4 5 6 7 8 9 | Value* val_c = NULL;
IRBuilder<> IRB(InsertPoint);
Value* cmp = IRB.CreateICmpEQ(val_a, val_b);
BranchInst *BI = cast<BranchInst>(
SplitBlockAndInsertIfThen(cmp, InsertPoint, false, CallWeights));
/* Instrument at new basic block */
IRBuilder<> ThenB(BI);
val_c = ThenB.CreateAdd(val_a, val_b);
val_c = IRB.CreateSub(val_a, val_b);
|
上述插桩将在目标程序中插入如下代码：
1 2 3 4 | if (val_a == val_b) {
val_c = val_a + val_b;
}
val_c = val_a - val_b;
|
值得注意的是，splitblockandinsertifthenelse()的第三个参数可以由用户可选地提供一个branch weight的参数，指定该分支的通过概率以便于进行优化（类似unlikely?）。
3. getIntNTy()
LLVM IR中惯用的IntegerType主要是：
- Int8Ty
- Int16Ty
- Int32Ty
- Int64Ty
但是，今天注意到了一个有意思的API:
1 | static IntegerType * getIntNTy (LLVMContext &C, unsigned N)
|
从而，我们可以定义任意长度的IntegerType，能够更加灵活地使用LLVM玩出花样。以下给出一个例子，在这个例子中，我们希望提取字符串的前N字节（N <= 8）。
3.1 一个小练习
原始程序demo.c：
1 2 3 4 5 6 7 8 9 | unsigned long long str2hex(char *buf) {
return 0;
}
int main() {
char buf[32];
scanf("%s", buf);
printf("Hex: %8llx\n", str2hex(buf));
return 0;
}
|
我们的目标是插桩democ.c的str2hex()函数，使该函数返回char *buf的前N = 6个字节的Hex形式。
为了实现该目标，我们需要编写一个LLVM Pass，其中主要逻辑如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | for (llvm::Function &F : M) {
if (F.getName() != "str2hex") continue;
IntegerType *IntNTy = IntegerType::getIntNTy(C, 48); // 6 * 8 = 48 bits
IntegerType *Int64Ty = IntegerType::getInt64Ty(C);
BasicBlock::iterator IP = F.getEntryBlock().getFirstInsertionPt();
Value* arg = &(*F.arg_begin());
IRBuilder<> IRB(&(*IP));
Value *ptr = IRB.CreateBitCast(IRB.CreateGEP(arg, ConstantInt::get(Int64Ty, 0)), IntNTy->getPointerTo());
Value *hex = IRB.CreateLoad(ptr);
hex = IRB.CreateZExt(hex, Int64Ty);
for (auto &I : *IP->getParent()) {
if (dyn_cast<llvm::ReturnInst>(&I)) {
llvm::ReturnInst *new_inst = llvm::ReturnInst::Create(m->getContext(), hex);
ReplaceInstWithInst(&I, new_inst);
break;
}
}
}
|
插桩后的demo.ll如下：
1 2 3 4 5 6 7 8 9 | define i64 @str2hex(i8*)
%2 = getelementptr i8, i8* %0, i64 0
%3 = bitcast i8* %2 to i48*
%4 = load i48, i48* %3
%5 = zext i48 %4 to i64
%6 = alloca i8*, align 8
store i8* %0, i8** %6, align 8
ret i64 %5
}
|
3.2 IntNTy在x86上的实现方式
之所以LLVM IR中的Int8Ty、Int16Ty、Int32Ty更常用，是因为它们对应了Byte、Word、Dword等类型，可以直接通过汇编指令表示。为了探究IntNTy，即任意长度的整型在x86汇编中的实现，我们将上一小节中的demo.c编译成可执行文件，并通过gdb反汇编来查看插桩代码的实现：
1 2 3 4 5 6 7 8 9 10 11 12 | push rbp
mov rbp,rsp
mov eax,DWORD PTR [rdi]
mov ecx,eax
movzx eax,WORD PTR [rdi+0x4]
mov edx,eax
shl rdx,0x20
or rcx,rdx
mov QWORD PTR [rbp-0x8],rdi
mov rax,rcx
pop rbp
ret
|
可以看到，对于6字节的IntNTy，汇编中首先读取一个4字节的Dword，接着读取一个2字节的Word，然后通过“移位”与“或”操作组合成一个6字节的值。
显然，IntNty提供了更方便的方式，让我们可以在插桩时使用一个任意长度的整型值。但是，从汇编角度，当LLVM IR最终编译成汇编代码时，IntNTy仍然是基于Byte、Dword等类型实现，并且仍然需要引入额外的开销来进行组合。LLVM IR只不过是将基础类型“组合”的部分进行了封装，提供了便捷但并不会提升效率。
4. Predecessors与Successors
类似IDAPython，在基本块的级别获取其前继/后继。例如：
1 2 3 | for (llvm::BasicBlock* pred_bb : predecessors(cur_bb)) {
printf("prev_bb=%p\n", pred_bb); /* for debug */
}
|
4.1 问题：predecessors()可能返回重复的前驱基本块
这里需要注意，我们遇到过一个奇怪的情况(通常发生在switch结构中)，即predecessors()返回多个相同的基本块指针：
1 2 3 4 5 | prev_bb=0x56407eaee190
prev_bb=0x56407eaee190
prev_bb=0x56407eaee190
prev_bb=0x56407eaee190
prev_bb=0x56407eaee190
|
Github Issue中有人遇到了相同的情况：#76. 目前，我们只能在调用predecessors()后手动进行检查和去重。
4.2 unique predecessor/successors
查看LLVM BasicBlock类的文档时，发现了一些有意思的成员函数
1 2 3 4 5 | BasicBlock *getSingleSuccessor () const
Return the successor of this block if it has a single successor. More...
BasicBlock *getUniqueSuccessor () const
Return the successor of this block if it has a unique successor. More...
|
我们主要疑惑于其中"Unique"的含义。在查阅源码注释后，基本得到了解答：
1 2 3 | /// Note that unique predecessor doesn't mean single edge, there can be
/// multiple edges from the unique predecessor to this block (for example a
/// switch statement with multiple cases having the same destination).
|
最后，本篇只是做一个简单的分享，欢迎批评与指正。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
