2019-05-13

Obfuscation-llvm混淆flatten源码分析

1. Control Flow Flattening算法

源码层面的control flow flattening

源码层面的控制流图

图(a)为原始代码，图(b)为经过control flow flattening的代码，图(c)为原始代码的控制流图，图(d)为经过control flow flattening的代码的控制流图。[1]

2. IR层Control Flow Flattening的源码分析

2.1 IR层简介

其中IR(intermediate representation)是前端语言生成的中间代码，也是Pass操作的对象，它主要包含四个部分：

Module：比如一个.c或.cpp文件
Function：代表文件中的一个函数
BasicBlock：每个函数会被划分为一些block，它的划分标准是：一个block只有一个入口和一个出口。
Instruction：具体的指令。
它们之间的关系可以用下图来表示：

2.2 源码分析

使用一个简单的例子来测试Control Flow Flattening的处理流程，测试代码如下：

int func1(int a,int b)
{
     int result;
     if(a>0){
            result=a+b;
     }
     else{
            result=a-b;
     }
     return result;
}

这段测试代码生成的IR代码如下图所示：

2.2.1 入口函数runOnFunction

Control Flow Flattening Pass处理的对象是函数，所以重载函数runOnFunction，如果Pass处理的的对象时Module，可以重载runOnModule。

bool runOnFunction(Function &F) override {
    Function* tmp = &F;
    // Do we obfuscate
    if (flatten(tmp)) {
        //++Flattened;
    }

    return false;
}

2.2.2 处理函数flatten

将函数中的所有BasicBlock保存到vector容器originBB中，当originBB的数量小于等于1时，返回false。

// f为flatten参数： Function *f
// vector<BasicBlock *> origBB;

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

// Nothing to flatten
if (origBB.size() <= 1) {
  return false;
}

将originBB中的第一个BasicBlock删除掉，并通过f->begin()获取函数的第一个BasicBlock；如果第一个BasicBlock的最后一条指令是否是跳转指令，如果是跳转指令的话转换为跳转类型指令。

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

如果是跳转指令是条件跳转，或者是第一个BasicBlock的后继BaseBlock大于1个(非条件跳转指令的后继BasicBlock为1个，条件跳转指令的后继BasicBlock为2个，return指令的后继BasicBlock为0个)。获取跳转指令的地址，然后通过splitBasicBlock将第一个BasicBlock一分为2，后边划分出来的BasicBlock起名叫”first”，然后将”first”插入到originBB的起始位置。
这样做是为了将变量声明部分与控制流部分分割开，因为first部分是要放进switch-case分支中的，防止变量作用域错误。

if ((br != NULL && br->isConditional()) ||
    insert->getTerminator()->getNumSuccessors() > 1) {

    BasicBlock::iterator i = insert->end();
    --i;

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

    BasicBlock* tmpBB = insert->splitBasicBlock(i, "first");
    origBB.insert(origBB.begin(), tmpBB);
}

此时的IR图如下所示：

接着将第一个BasicBlock(即entry BB)与其下一个BasicBlock(即first)的跳转关系解除：

// Remove jump
insert->getTerminator()->eraseFromParent();

解除之后的IR图如下所示：

然后在第一个BasicBlock创建switchVar变量，并赋一个随机的值。

// AllocaInst *switchVar;

// Create switch variable and set as it
switchVar =
new AllocaInst(Type::getInt32Ty(f->getContext()), 0, "switchVar", insert);
new StoreInst(
        ConstantInt::get(Type::getInt32Ty(f->getContext()),
                         llvm::cryptoutils->scramble32(0, scrambling_key)),
                         switchVar, insert);

接着创建while循环需要的”loopEntry”和”loopEnd”2个BasicBlock，在loopEntry中读取switchVar的值：

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

load = new LoadInst(switchVar, "switchVar", loopEntry);

将第一个BasicBlock(即entry，也就是insert)放在loopEntry之前，并设置第一个BasicBlock的最后一条指令跳转loopEntry。
设置loopEnd的最后一条指令跳转loopEntry。

// Move first BB on top    // insert现在是entry basicblock，将entry BB放在loopEntry BB之前。
insert->moveBefore(loopEntry);
BranchInst::Create(loopEntry, insert);   // entry bb的最后一个指令为br loopEntry

// loopEnd jump to loopEntry
BranchInst::Create(loopEntry, loopEnd);  // loopEnd bb的最后一个指令为br loopEntry

接着创建switch-case中的default跳转对应的BasicBlock swDefault，swDefault在loopEnd之前，并在swDefault中添加一条跳转loopEnd的指令。

// 创建switch-case的default分支BB，default分支的指令只有br loopEnd
BasicBlock *swDefault = BasicBlock::Create(f->getContext(), "switchDefault", f, loopEnd);
BranchInst::Create(loopEnd, swDefault);

然后在loopEntry中创建了switch-case的指令，指定default block为swDefault，并设置switch-case的变量switchVar。

// Create switch instruction itself and set condition
// 在loopEntry中创建switch-case，并设置条件值
switchI = SwitchInst::Create(&*f->begin(), swDefault, 0, loopEntry);
switchI->setCondition(load);

然后将第一个BasicBlock的最后跳转指令设置为跳转loopEntry：

// Remove branch jump from 1st BB and make a jump to the while
f->begin()->getTerminator()->eraseFromParent();
// 函数的第一个bb，也就是entry bb，的最后一条指令为br loopEntry
BranchInst::Create(loopEntry, &*f->begin());

上述流程创建了while循环相关的2个BasicBlock，switch-case指令，和其对应的switchDefault BasicBlock，并修改各个BasicBlock之间的跳转关系，如下图所示：

接下来需要将所有保存在容器originBB中的BasicBlock添加到switch-case中，每一个BasicBlock对应一个case，并且每个case的值都是一个随机值。代码如下：

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

此时的IR图如下所示：

添加了全部的BasicBlock之后，需要修改switch-case层级的BasicBlock之间的跳转关系，使得每个BasicBlock执行完毕之后，会重新设置switchVar值，然后通过while循环再次进入switch-case中的下一个case中，知道程序执行完毕。
如果BasicBlock的最后指令的后继BB数量为0(return语句的指令后继BB只有0个)，不需要处理；
如果BasicBlock的最后指令的后继BB数量为1，找到后继BB，从switch-case指令中找到该BB对应的case号码，将其赋值给switchVar，然后将最后的指令替换为跳转loopEnd。

// Recalculate switchVar
for (vector<BasicBlock*>::iterator b = origBB.begin(); b != origBB.end(); ++b) {
    BasicBlock *i = *b;
    ConstantInt* numCase = NULL;

    // getNumSuccessors是获取后续BB的个数，Ret BB后继BB为0个，...

    // Ret BB, Ret BB的最后不用加br loopEnd
    if (i->getTerminator()->getNumSuccessors() == 0) {
        continue;
    }

    // If it's a non-conditional jump
    if (i->getTerminator()->getNumSuccessors() == 1) {
        // Get successor and delete terminator
        BasicBlock* succ = i->getTerminator()->getSuccessor(0);
        i->getTerminator()->eraseFromParent();

        // Get next case
        numCase = switchI->findCaseDest(succ);

        // If next case == default case (switchDefault)
        if (numCase == NULL) {
            numCase = cast<ConstantInt>(
                ConstantInt::get(switchI->getCondition()->getType(),
                     llvm::cryptoutils->scramble32(
                           switchI->getNumCases() - 1, scrambling_key)));
        }

        // Update switchVar and jump to the end of loop，BB结尾跳转loopEnd
        new StoreInst(numCase, load->getPointerOperand(), i);
        BranchInst::Create(loopEnd, i);
        continue;
    }

    // If it's a conditional jump
    if (i->getTerminator()->getNumSuccessors() == 2) {
         ...
    }
}

设置完跳转关系的IR图如下所示：