o-llvm: Control Flow Flattening

o-llvm 分析： 控制流平坦化源码分析

这是本人关于 o-llvm 分析系列文章的第一篇文章，网上已经有很多关于 o-llvm 相关的分析文章了，我写这一系列的文章只是为了督促我仔细分析 o-llvm 的每一个角落，并加深记忆。

o-llvm 与 llvm 什么关系？ 这个可能是很多菜鸡搞不清楚的问题，我曾经也搞不清楚，一直以为“混淆” 是 llvm 自带的功能，殊不知，ollvm 只是一个基于 llvm 框架实现的插件，llvm 是一套前后端完善的编译框架。

本篇文章分析的代码相对路径为

1
lib/Transforms/Obfuscation/Flattening.cpp

FunctionPass

o-llvm 基于 llvm pass 模块实现，llvm pass 可以理解成 llvm 的插件，o-llvm 的控制流平坦化实现是基于 FunctionPass ，llvm 会对目标程序中的每一个函数调用 FunctionPass。为什么基于 FunctionPass 来实现控制流平坦化呢？因为 o-llvm 控制流平坦化最小粒度是函数，即以函数为单位展开混淆。FunctionPass 有机会处理目标代码的每一个函数。

关于 pass 的编写，我会另外开一篇文章来记录，这篇文章就简单的提一下 FunctionPass 的编写。

编写 FunctionPass 需要继承 FunctionPass类并实现 runOnFunction 函数，如下代码

1
2
3
4
5
6
7
8
9
10
11
12
namespace {
    struct DummyPass : public FunctionPass {
        public:
            static char ID;
            DummyPass() : FunctionPass(ID) {}
            virtual bool runOnFunction(Function &F) override;
    };
}

bool DummyPass::runOnFunction(Function &F) {
    return false; // We did not alter the IR
}

注册 FunctionPass

1
2
3
// Register the pass with llvm, so that we can call it with dummypass
char DummyPass::ID = 0;
static RegisterPass<DummyPass> X("dummypass", "Example LLVM pass printing each function it visits");

Flattening::runOnFunction

Function pass 注册后，llvm 会对每一个函数调用 runOnFunction, llvm 中用 llvm::Function 类代表函数，函数单位内的所有信息都可以通过该类的实例来获取，例如基本块。

1
2
3
4
5
6
7
8
9
10
bool Flattening::runOnFunction(Function &F) {
  Function *tmp = &F;
  // Do we obfuscate
  if (toObfuscate(flag, tmp, "fla")) { // toObfuscate 判断该函数是否要fla
    if (flatten(tmp)) {
      ++Flattened;
    }
  }
  return false;
}

上面这段代码主要调用了 toObfuscate 和 flatten，前者用于判断是否需要对当前处理的函数混淆，后者是控制流平坦化的主要逻辑。

toObfuscate 判断是否混淆

toObfuscate 判断当前操作的函数是否要进行某种混淆（fla, sub, bcf）

o-llvm 开启混淆有两种方法：

1. 命令行参数指定全局混淆
2. Functions-annotations 指定局部混淆

局部混淆 annotations 修饰方法例子如下：

1
int func() __attribute((__annotate__(("fla"))));

llvm 中用 readAnnotate(f) 来获取函数的 annotations

toObfuscate 先判断 annotations 标志，再判断全局标记。

flatten 函数

flatten 函数的代码量比较大，因此我按照逻辑顺序拆开代码分析。

1: 将原函数的 SwitchInst 语句转换成 If

1
2
3
// Lower switch
FunctionPass *lower = createLowerSwitchPass();
lower->runOnFunction(*f);

createLowerSwitchPass 也是一个 FunctionPass，它的功能是将指定 function 中的 SwitchInst 转换成 if 。

为什么要把原始代码中的 switch 转换成 if 呢？ 这是为了实现多次混淆，每次混淆都能增加大量的基本块。

2: 保存原始函数的基本块列表

1
2
3
4
5
6
7
8
9
10
// Save all original BB
for (Function::iterator i = f->begin(); i != f->end(); ++i) {
  BasicBlock *tmp = &*i;
  origBB.push_back(tmp);

  BasicBlock *bb = &*i; 
  if (isa<InvokeInst>(bb->getTerminator())) {
    return false;
  }
}

这段代码中我比较疑惑的是如果当前处理的函数中有一个基本块以 Invoke 指令结尾，那么该函数无法混淆。

3: 处理函数入口基本块

函数入口基本块，即函数的第一个基本块，这个基本块比较特殊。控制流平坦化，需要添加一个类似 while - switch 的结构，入口基本块需要特殊处理，使控制流进入 while 循环体。

入口基本块的结尾指令不能是条件跳转，如果是条件跳转指令，需要拆分将其拆分成两个基本块。

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
// Remove first BB
origBB.erase(origBB.begin());

// Get a pointer on the first BB
Function::iterator tmp = f->begin();  //++tmp;

BasicBlock *insert = &*tmp;

// If main begin with an if
BranchInst *br = NULL;
if (isa<BranchInst>(insert->getTerminator())) {
  br = cast<BranchInst>(insert->getTerminator());
}

if ((br != NULL && br->isConditional()) ||
    insert->getTerminator()->getNumSuccessors() > 1) {
  BasicBlock::iterator i = insert->end(); // BasicBlock::iterator 遍历指令的
 --i;

  if (insert->size() > 1) {
    --i;
  }

  BasicBlock *tmpBB = insert->splitBasicBlock(i, "first"); // 拆分成两个基本块，方便后面处理
  origBB.insert(origBB.begin(), tmpBB); 
} 

// Remove jump
insert->getTerminator()->eraseFromParent();// 删除最后一条指令

4: 创建 switch 变量

o-llvm 利用 while - switch 重新组合原始基本块，switch 需要 switch var，o-llvm 中的 switch var 是基本块的随机数编号，o-llvm 为每一个基本块用随机数编号。重新组合基本块和类似模式如下:

1
2
3
4
5
6
7
8
9
10
while(true) {
	switch(var)
	case 0x8123123:
		BB1;
		break;
	case 0x8799882:
		BB2;
		break;
	.......
}

创建 switchVar 变量

1
2
3
4
5
6
7
// Create switch variable and set as it
switchVar =
    new AllocaInst(Type::getInt32Ty(f->getContext()), 0, "switchVar", insert); // 在first BB插入switchVar
new StoreInst(
    ConstantInt::get(Type::getInt32Ty(f->getContext()),
                     llvm::cryptoutils->scramble32(0, scrambling_key)),
    switchVar, insert);

AllocaInst 在栈中分配变量， ConstantInt::get 获取指定类型的常量数据，用于给分配的变量赋初值。

insert 是插入目标函数第一个基本块，下同。

5: 创建主循环

1
2
3
// Create main loop
loopEntry = BasicBlock::Create(f->getContext(), "loopEntry", f, insert);
loopEnd = BasicBlock::Create(f->getContext(), "loopEnd", f, insert);

BasicBlock::Create 会在 insert 之前插入基本块，若不指定 insert，则默认插入到函数的尾部，我们想要的实际效果是：

insert -> loopEntry，然而当前基本块的关系是 loopEntry -> insert, 因此要调整两者的位置。

1
2
3
4
// 调整 insert 与 loopEntry 之间的关系
insert->moveBefore(loopEntry);
BranchInst::Create(loopEntry, insert); // insert -> loopEntry
BranchInst::Create(loopEntry, loopEnd); // loopEnd -> loopEntry

6: 创建 switch

1
2
3
4
5
6
7
8
9
10
11
12
13
// load switchVar 变量
load = new LoadInst(switchVar, "switchVar", loopEntry);

// 创建 switch default 基本块， default -> loopEnd 
BasicBlock *swDefault =
    BasicBlock::Create(f->getContext(), "switchDefault", f, loopEnd);
BranchInst::Create(loopEnd, swDefault);

// 创建 SwitchInst 指令
switchI = SwitchInst::Create(&*f->begin(), swDefault, 0, loopEntry);

// 设置 SwitchVar 变量
switchI->setCondition(load);

7: 将原始基本块放入 switch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Put all BB in the switch
for (vector<BasicBlock *>::iterator b = origBB.begin(); b != origBB.end();
     ++b) {
  BasicBlock *i = *b;
  ConstantInt *numCase = NULL;

  // Move the BB inside the switch (only visual, no code logic)
  i->moveBefore(loopEnd);

  // Add case to switch
  numCase = cast<ConstantInt>(ConstantInt::get(
      switchI->getCondition()->getType(),
      llvm::cryptoutils->scramble32(switchI->getNumCases(), scrambling_key)));
  switchI->addCase(numCase, i);
}

到目前为止，基本块只是放入到了 switch 里面，还需要进一步处理。

这段代码可以理解成获取随机数，不会重复

1
llvm::cryptoutils->scramble32(switchI->getNumCases(), scrambling_key)

从这段代码来看，switch var 是在添加 case 的时候生成的，整个代码中都没有维护 switch var 与 基本块关系的变量，这是因为 o-llvm 利用 llvm 本身来维护switch var 值与基本块的对应关系。SwitchInst.findCaseDest 函数可以获取 Switch 中指定基本块的 case 常量。

8: 重新修正基本块之间的关系

上一步，o-llvm 将 oriBB里面的所有基本块都添加到 switch 中，并为每一个基本块生成 case 对应的值，接下来就是调整基本块之间的关系。

主要有3类基本块:

  1. 无条件跳转结尾
  2. 有条件跳转结尾
  3. RET 指令结尾

我们分别来看这 3 类处理的过程，这段代码是循环中抽离出来的，i 代表当前修正的基本块。

1. 无条件跳转结尾的基本块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// If it's a non-conditional jump
if (i->getTerminator()->getNumSuccessors() == 1) { // 后继基本块数量为 1
  // 获取后继基本块，并删除跳转跳转指令
  BasicBlock *succ = i->getTerminator()->getSuccessor(0);
  i->getTerminator()->eraseFromParent(); // 删除结尾跳转指令

  // 获取后继基本块对应的 case 值
  numCase = switchI->findCaseDest(succ);

  // 如果没有找到后继基本块对应的 case 值，default 
  if (numCase == NULL) {
    numCase = cast<ConstantInt>(
        ConstantInt::get(switchI->getCondition()->getType(),
                         llvm::cryptoutils->scramble32(
                             switchI->getNumCases() - 1, scrambling_key)));// 获取 default 的 case 值
  }
  // 更新 switchVar 的值，变跳转到 loopEnd
  new StoreInst(numCase, load->getPointerOperand(), i);
  BranchInst::Create(loopEnd, i); // 跳转到loopEnd
  continue;
}

2. 有条件跳转结尾

对于一个条件跳转的基本块，一般两个后继。

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
// If it's a conditional jump
if (i->getTerminator()->getNumSuccessors() == 2) {
    // 分别获取两个后继的 case 值
    ConstantInt *numCaseTrue =
        switchI->findCaseDest(i->getTerminator()->getSuccessor(0));
    ConstantInt *numCaseFalse =
        switchI->findCaseDest(i->getTerminator()->getSuccessor(1));

    // 后继是否为 default case
    if (numCaseTrue == NULL) {
        numCaseTrue = cast<ConstantInt>(
            ConstantInt::get(switchI->getCondition()->getType(),
                             llvm::cryptoutils->scramble32(
                                 switchI->getNumCases() - 1, scrambling_key)));
    }

    if (numCaseFalse == NULL) {
        numCaseFalse = cast<ConstantInt>(
            ConstantInt::get(switchI->getCondition()->getType(),
                             llvm::cryptoutils->scramble32(
                                 switchI->getNumCases() - 1, scrambling_key)));
    }

    // 创建 SelectInst
    BranchInst *br = cast<BranchInst>(i->getTerminator());
    SelectInst *sel =
        SelectInst::Create(br->getCondition(), numCaseTrue, numCaseFalse, "",
                           i->getTerminator());

    // 删除 terminator （结尾跳转指令）
    i->getTerminator()->eraseFromParent();

    // 更新 switchVar 的值，变跳转到 loopEnd
    new StoreInst(sel, load->getPointerOperand(), i);
    BranchInst::Create(loopEnd, i);
    continue;
}

3. RET 指令结尾

这个就比较简单了，RET 指令不需要重新回到 loop，所以不用做任何处理

1
2
3
4
// Ret BB
if (i->getTerminator()->getNumSuccessors() == 0) {
continue;
}

9: 修复 stack

o-llvm 控制流平坦化的最后一步是 fixStack(Function *f) 这一步是处理局部变量分配问题。

主要处理两类变量:

1. PHI Node
2. 非入口基本块中分配的局部变量

对于 PHI Node，fixStack 直接简单的粗暴的调用 DemotePHIToStack 将 PHI Node 变量 Entry 中分配

1
DemotePHIToStack(tmpPhi.at(i), f->begin()->getTerminator());

对于非 Entry 基本块中申请的局部变量，若该变量在其它基本块中还有使用的话，需要将该变量提到 Entry 中分配

1
DemoteRegToStack(*tmpReg.at(i), f->begin()->getTerminator());

总结

o-llvm 控制流平坦化的原理非常简单，只是简单的将原始基本块插入到 switch 结构中，并删除原始基本块之间的跳转指令。然而实际案例中，为何还原 o-llvm 控制流平坦化如此困难？

要回答这个问题，我们首先来回到 flatten 的第一步，将 switch 转换成二分if。该过程主要是通过调用 llvm 里面的一个 FunctionPass 来实现。

1
2
3
// Lower switch
FunctionPass *lower = createLowerSwitchPass();
lower->runOnFunction(*f);

LowerSwitchPass 将 switch 指令转换成等价的 if 实现，这极大的增加基本块的数量，当下一次对这个函数混淆的时候，将产生更多的 case。

重复对某个函数执行 flatten ，基本块的数量将越来越多，其中大量的基本块都是为实现二分 if 而存在，这使得识别原始基本块十分困难。

最后，flatten 执行完后，可能还有其它的优化 pass 对混淆过的函数进行处理，进一步打乱一些固定的特征模式。

参考

https://llvm.org/docs/WritingAnLLVMPass.html#writing-an-llvm-pass-basiccode

https://osterlund.xyz/posts/2017-11-28-LLVM-pass.html

https://www.zhihu.com/question/49642237

obfuscator
obfuscator llvm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！