This page looks best with JavaScript enabled

OLLVM 之控制流平坦化源码学习

 ·  ☕ 10 min read · 👀1 views

控制流平坦化 ,Control-Flow-Flattening（FLA）,的基本思想主要是通过一个主分发器来控制程序基本块的执行流程。该方法把函数内所有基本代码块放到控制流图的最底部，然后删除掉原来的基本块之间的跳转关系，添加混淆器的流程控制分发逻辑，通过新的复杂分发逻辑还原原来程序块之间的逻辑关系。即，通过一个主分发器，控制整个函数内代码块的运行流程。

FLA

-mllvm -fla : activates control flow flattening
-mllvm -split : activates basic block splitting. Improve the flattening when applied together.
-mllvm -split_num=3 : if the pass is activated, applies it 3 times on each basic block. Default:1

OLLVM控制流平坦化混淆源码位置：OLLVMCODE\lib\Transforms\Obfuscation\Flattening.cpp

0x00 getAnalysisUsage函数

这里我是用的LLVM12进行学习的。在新版LLVM中，若要调用其他Pass，不能够在Pass中直接Create了，必须override一个函数来描述Pass的依赖关系。比如在Flat的时候，OLLVM会将switch结构降级成if以扩大基本块的数量，以便于下一次再进行Flat的时候可以利用更多的基本块进行平坦化。 大家可能在网上其他博客中看到，在flatten函数开头有这一句，即create了一个LowerSwitchPass对象并用该对象对本函数进行处理

1
2
3

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

而在新版LLVM中，则是override了getAnalysisUsage函数，在函数中定义了依赖LowerSwitchPass，即要求在调用这个Pass之前要调用一次LowerSwitchPass进行预处理。可以说从结构上更加规范了。

1
2
3
4

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequiredID(LowerSwitchID);
  FunctionPass::getAnalysisUsage(AU);
}

0x01 runOnFunction函数 

 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")) {
    if (flatten(tmp)) {
      ++Flattened;
    }
  }
  return false;
}

在runOnFunction函数中，同Bogus和Substitution，调用toObfuscate函数判断是否要进行混淆，如果为真，则调用flatten对函数进行混淆。

0x01 flatten函数

不同与BCF和Sub，在Pass收集基本块之前，会设置一个名为scrambling_key的变量。会调用llvm::cryptoutils->get_bytes获取一个随机种子，这个种子用于后面产生switch-case的随机case值

1
2
3

// SCRAMBLER
char scrambling_key[16];
llvm::cryptoutils->get_bytes(scrambling_key, 16);

然后，同之前的混淆，会将所有的基本块存在一个vector里，然后会有一个判断，如果当前处理的函数中有一个基本块以 Invoke 指令结尾，那么该函数无法混淆；如果整个函数只有一个基本块，也无法混淆

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

// Save all original BB
for (Function::iterator i = f->begin(); i != f->end(); ++i) {
    BasicBlock *tmp = &*i;
    origBB.push_back(tmp);

    // 如果当前处理的函数中有一个基本块以 Invoke 指令结尾，那么该函数无法混淆
    BasicBlock *bb = &*i;
    if (isa<InvokeInst>(bb->getTerminator())) {
        return false;
    }
}
// Nothing to flatten
if (origBB.size() <= 1) {
  return false;
}

然后会从vector中删除第一个基本块，并做一些特殊判断处理。因为平坦化要求第一个基本块只能有一个后继基本块，如果第一个基本块末尾就是条件跳转（有两个或多个后继块）就无法进行后面的平坦化操作。因此，需先判断第一个基本块末尾是否是条件跳转，如果是，则要把这个条件跳转的语句切割出来，成为一个新的基本块，并插入到vector开头

 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

// 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();
--i;

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

  // 将条件跳转的语句切割出来，成为一个新的基本块，并插入到vector开头
  BasicBlock *tmpBB = insert->splitBasicBlock(i, "first");
  origBB.insert(origBB.begin(), tmpBB);
}

// 删除第一个基本块最后的末尾跳转
insert->getTerminator()->eraseFromParent();

下面就是要构建主分发器了。OLLVM-FLA利用While-Switch结构重新组合分发原始基本块从而实现平坦化。Switch分发结构就是主分发器。而switch需要switch var，在OLLVM中，switch var是基本块的随机数编号，OLLVM为每一个基本块用随机数编号，并通过switch进行分发。其基本模式类似如下

1
2
3
4
5
6
7
8
9

while(true) {
  switch(var) {
    case 0x5166726F:
      BB1; break;
    case 0x6F726651:
      BB2; break;
    .....
  }
}

这部分代码就是创建switch var。AllocaInst意为在栈上创建变量，ConstantInt::get 获取指定类型的常量数据，用于给分配的变量赋初值。

1
2
3
4
5
6
7
8
9

// Create switch variable and set as it
switchVar =
    new AllocaInst(Type::getInt32Ty(f->getContext()), 0, "switchVar", insert);

// StoreInst::StoreInst(Value *val, Value *addr, BasicBlock *InsertAtEnd)
new StoreInst(
    ConstantInt::get(Type::getInt32Ty(f->getContext()),
                      llvm::cryptoutils->scramble32(0, scrambling_key)),
    switchVar, insert);

然后后面要构建两个基本块分别作为主分发器和子分发器。注意这里的insert依旧是第一个基本块的对象指针。

1
2
3
4

  // Create main loop
  // static BasicBlock *Create(LLVMContext &Context, const Twine &Name="", Function *Parent = nullptr, BasicBlock *InsertBefore = nullptr)
  loopEntry = BasicBlock::Create(f->getContext(), "loopEntry", f, insert);
  loopEnd = BasicBlock::Create(f->getContext(), "loopEnd", f, insert);

然后这里有个问题就是这三个基本块的关系。BasicBlock::Create 创建的基本块，是在第四个参数 BasicBlock InsertBefore 之前插入基本块（如果不指定InsertBefore则会插入在函数末尾）。那么这样创建完后，三个基本块的关系是：loopEntry->loopEnd->insert

而我们知道，正确的调用关系应该是 insert-> loopEntry, loopEntry -> 基本块 -> loopEnd, loopEnd -> loopEntry 。因此，需要调整一下它们的位置，使loopEnd也指向loopEntry，第一个基本块到loopEntry的跳转在后面建立

1
2
3

// Move first BB on top
insert->moveBefore(loopEntry);
BranchInst::Create(loopEntry, loopEnd);

下面就是创建switch结构。这里有个点巨坑，就是对F.begin()删除末尾跳转。如果大家前面认真看的话，会发现前面对insert块做了删除末尾跳转的操作，然后又建立了第一个基本块到loopEntry的条件跳转，然后这里又对F.begin()做了删除末尾跳转的操作，最后在后面还会建立F.begin()到loopEntry的跳转。可能是因为我太菜了，没看懂这是什么魔幻操作，就把这部分代码删了，只留一句 *BranchInst::Create(loopEntry, &f->begin()); 即建立第一个基本块到loopEntry的条件跳转。

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

// load switchVar 变量
load = new LoadInst(switchVar->getType()->getElementType(), 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);

// 使函数第一个初始块指向loopEntry
BranchInst::Create(loopEntry, &*f->begin());

下面要将所有基本块装入switch，同时，为每个基本块生成一个唯一的随机数作为块编号，在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);   // 添加随机数编号和BB的关联
}

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

接下来要调整基本块之间的关系。我们知道。OLLVM-FLA的设计思路是在每个case执行完之后，在case的逻辑最后更新switch var的值。故，OLLVM-FLA会遍历每一个基本块，并依据基本块末尾跳转的类型做处理并设置switch var的值为下一个基本块的case值，这里有三种情况

无后继基本块

也就是该基本块没有末尾跳转。即，该块是以 ret 结尾的结束块。这种块因为不需要重新回到分发器，所以不用做任何处理

1
2
3
4
5

// Ret BB
if (i->getTerminator()->getNumSuccessors() == 0) {
  continue;
}
// LLVM可用 (BasicBlock *)->getTerminator()->getNumSuccessors() 获取后继块数量

无条件跳转结尾基本块

无条件跳转基本块，后面会有一个后继

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

// If it's a non-conditional jump
if (i->getTerminator()->getNumSuccessors() == 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 的值
  new StoreInst(numCase, load->getPointerOperand(), i);
  BranchInst::Create(loopEnd, i);      // 跳转到loopEnd
  continue;
}

这里有个坑点，就是这个DefaultCase。根据平坦化的设计思路，后继块应该都在基本块列表中并在前面添加好了case值，也就是说真实块一定都是有case值的，那default块有什么用呢。在建立switch结构的时候，本质上做的就是一次一次条件判断，即我们在CFG图中看到的子分发器，也就是说必然会有一个分支需要指向Default块（虽然这个Default永远不会被运行到），而这条分支就是没有后继case值的，因此需要进行判断。

条件跳转结尾基本块

如果当前是条件跳转基本块，那么应该会有两个分支，即有两个后继

 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

// 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));

  // 如果后继case值为空则设置为 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)));
  }

  // Create a SelectInst
  BranchInst *br = cast<BranchInst>(i->getTerminator());

  // static SelectInst *Create(Value *C, Value *S1, Value *S2, const Twine &NameStr = "", Instruction *InsertBefore = nullptr,Instruction *MDFrom = nullptr)
  SelectInst *sel =
      SelectInst::Create(br->getCondition(), numCaseTrue, numCaseFalse, "",
                          i->getTerminator());
  // 意为 根据br->getCondition()是否为True来决定*sel的值是numCaseTrue还是numCaseFalse，并把这条选择语句插入到i->getTerminator()之前

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

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

以上就是平坦化混淆实现的全部内容了，最后，函数内调用了一下fixStack函数修复栈

0x02 fixStack函数

OLLVM-FLA最后一步是 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());

0x03 魔改思路

标准OLLVM-FLA已经被玩烂了，基本都是通过loopEnd（预处理器）定位基本块，然后对所有基本块开始符号执行，并将各个基本块连接起来。当然，很多人会在使用OLLVM-FLA的同时搭配BCF和Sub，并开启编译器优化。编译器优化会破坏标准平坦化的五部分结构，故网络上的一键自动化脚本基本都会失效。 但是，编译器优化毕竟是不确定的，希望能通过魔改OLLVM算法，来实现加强混淆。

多个loopEnd

动态生成多个loopEnd，因为识别真实块是需要先识别出loopEnd然后找loopEnd的前继。生成多个loopEnd后分析者必须得找全所有loopEnd才可以适配到所有真实块。

loopEnd直接跳转基本块

因为标准OLLVM是在每个真实块结尾处设置switchVar，loopEnd仅作为跳转到loopEntry的跳板。所以只需要识别出loopEntry的前继就可以识别到所有loopEnd，进而识别出所有真实块，这也是我认为平坦化设计上的最大弱点。为了魔改的时候克服掉这个弱点，可以将修改loopEnd的作用。

大概思想就是主分发器只会进行第一次分发，并执行第一个基本块。第一个基本块执行完毕后进入loopEnd，至此，loopEnd（预处理器）接管主分发器的全部功能，在预处理器里也实现一个switch结构，并插入LoadInst加载switchVar，再用于SwitchInst跳转。即，原先loopEnd会跳转到loopEntry进行下一次分发，魔改后由loopEnd直接跳转到下一个基本块。

魔改FLA

基于多个loopEnd和loopEnd直接跳转基本块的思想，实现出了一个魔改平坦化Pass，以下是效果图：
魔改FLA

复杂分发过程

OLLVM的平坦化，仅仅是靠一个switch来实现分发，并在每个真实块的末尾修改switchVar的值来继续控制下一次的分发。可以自实现整个分发过程，比如 Pluto FlatteningEnhanced 构造了一颗随机二叉树并将所有真实块排列到树的叶子节点上，并为每个父节点设置分发块。通过树结构为每个 节点/块 设置权值与跳转，自实现整个平坦化的分发过程。 他的算法相较于原版OLLVM-FLA复杂很多，后面会给出分析文章。但是因为他这个套思想没有解决loopEnd的前继就是真实块这个弱点，所以对于符号执行去混淆来说，难度不会提升太多。

0x04 参考资料

  1. 基于LLVM Pass实现控制流平坦化
  2. 基于LLVM的控制流平坦化的魔改和混淆Pass实战
  3. 重写 OLLVM 之控制流平坦化
  4. Pandaos-控制流平坦化源码分析
  5. [原创]ollvm源码分析 - Pass之Flattening
  6. Pluto-Obfuscator
Share on
Qfrost
WRITTEN BY
Qfrost
CTFer, Anti-Cheater, LLVM Committer