代码混淆——复杂度进化

上一篇中我们对Armariris进行了一定的改进，主要在对体量较大的BasicBlock进行了切割，增加了一条从当前BasciBlock到它前驱的控制流，并且恒为假。

有两个比较明显的问题：

（1）分支判断过于简单；

（2）增加的只是一条控制流线，并没有增加程序块，所以程序复杂度上升的有限。

为了让程序的复杂度得以进化，本次就对上述两个问题进行修改。在OLLVM中（开源的混淆工具，Armariris就是它的魔改）采用了更复杂（或者叫完整）的虚假控制流。对于第一个问题我们采用之前介绍过的不透明谓词解决。而第二个问题需要完善虚假控制流，从原始的程序块中衍生出符合语法的程序块，并融入到整个程序的控制流中。

首先，在FunctionPass的入口函数中，加入虚假控制流的启动入口。

bool Flattening::runOnFunction(Function &F) {
    Function *tmp = &F;
    // Do we obfuscate
    if (toObfuscate(flag, tmp, "fla") && ((int) llvm::cryptoutils->get_range(100) <= Percentage)) {
        errs() << "fla " + F.getName() +"\n";
        addBougusControlFlow(F);	//从这里给函数增加虚假控制流
        if (flatten(tmp)) {
            ++Flattened;
        }
    }

    return false;
}

首先要解决的问题是，可以以哪些块作为原始块用于衍生虚假块。

还是和上次一样的，对于长度大于平均值的BasicBlock。我们将其切割，切割为上半部分和下半部分。以下半部分为基础，克隆出一个虚假的BasicBlock。然后在上半部分的最后加入流程控制语句，在下半部分的两个块中进行选择跳转。

bool Flattening::addBougusControlFlow(Function &func) {
    unsigned average = 0;
    int sumLength = 0;
    std::list<BasicBlock *> basicBlocks;
    for ( Function::iterator I = func.begin(); I != func.end(); I++ ) {
        if ( I == func.begin() ) {
            continue;
        }
        sumLength += I->size();
        basicBlocks.push_back(&*I);
    }
    average = sumLength / func.size();
    BasicBlock::iterator begin = func.begin()->begin();
    AllocaInst *randNum = new AllocaInst(Type::getInt32Ty(func.getContext()), 0, "", &*begin);
    while (strcmp(begin->getOpcodeName(), "store")) {
        begin++;
    }
    new StoreInst(ConstantInt::get(Type::getInt32Ty(func.getContext()), llvm::cryptoutils->get_range(100) + 1),
                  randNum, &*begin);
    for ( std::list<BasicBlock *>::iterator I = basicBlocks.begin(); I != basicBlocks.end(); I++ ) {
        if ( (*I)->size() > average ) {
            addBogusFlow(*I, func, randNum);
        }
    }
    return true;
}

所以在addBougusControlFlow中先做长度统计。这里函数的第一个BasicBlock不计入，因为这个部分往往是大量的alloca和store语句，用于对函数内部变量的初始化，虽然很长，内容很多，但是对于增加复杂度没有意义。对于符合要求的BasicBlock，调用addBogusFlow，进入下一步。randNum是在函数中由分配的一个新的变量。在高级语言中，我们声明并初始化一个变量只需要如下:

int a = 0;

但是在IR中，这个行为被分成两部分:

%1 = alloca i32, align 4
store i32 0, i32* %1, align 4

第一条alloca指令，在函数栈帧上分配出一个32位int型的变量空间，align表示对齐。

第二条store表示将32位int型的立即数0，填入刚才分配的空间中，也就是初始化。

randNum的声明和初始化就需要一个AllocaInst和一个StoreInst。这个变量的作用是作为后面不透明谓词的操作数。

下面进入addBogusFlow函数

第一步是从BasicBlock的中间切割开

BasicBlock::iterator middle = basicBlock->end();
int pos = basicBlock->size() / 2;
while (pos--) {
    middle--;
}
BasicBlock *realBlock = basicBlock->splitBasicBlock(middle, "RealBlock");

返回的后半部分作为realBlock存在，clone出一个alteredBlock

BasicBlock *alteredBlock = llvm::CloneBasicBlock(realBlock, VMap, "AlteredBlock", &func);

然后需要修改原来的basicBlock的TerminatorInst，替换成一个选择跳转语句

TerminatorInst *end = basicBlock->getTerminator();
LoadInst *loadInst = new LoadInst(randNum, "", end);	//取出randNum
BinaryOperator *sub = BinaryOperator::Create(Instruction::Sub, (Value *)loadInst,
                            ConstantInt::get(Type::getInt32Ty(func.getContext()), 1, false),
                            "", end);	//randNum - 1
BinaryOperator *mul = BinaryOperator::Create(Instruction::Mul, (Value *)loadInst, sub, "", end);	// randNum * (randNum - 1)
BinaryOperator *rem = BinaryOperator::Create(Instruction::URem, mul,
                            ConstantInt::get(Type::getInt32Ty(func.getContext()), 2,
                                             false), "", end);	//randNum * (randNum - 1) % 2
ICmpInst *condition = new ICmpInst(end, ICmpInst::ICMP_EQ, rem,
                         ConstantInt::get(Type::getInt32Ty(func.getContext()), 0,
                                          false));
BranchInst::Create(realBlock, alteredBlock, (Value *)condition, basicBlock);
end->eraseFromParent();

如果要使用randNum，不能直接使用，要通过一条load指令从栈上取出。取出后构造一个简单的公式

x * (x-1) % 2

判断结果与0是否相等（当然相等），相等跳入realBlock，否则进入alteredBlock。

到这里跳转的问题就解决了，那么之后就是将alteredBlock进行改造，使他与realBlock不同，如果是两个相同的BasicBlock，那么上面增加的跳转就没有意义。

对于alteredBlock的修改我们可以在原有指令的基础上增加它的变形，要比凭空构造简单许多，也不容易出错。这里只针对BinaryOperator，也就是二元操作符进行修改.

Instruction::BinaryOps firstArray[13] = {Instruction::Xor, Instruction::Or, Instruction::And,
                                       Instruction::Add, Instruction::Sub, Instruction::Mul, Instruction::UDiv,
                                       Instruction::SDiv, Instruction::URem, Instruction::SRem, Instruction::Shl,
                                       Instruction::LShr, Instruction::AShr};
if ( opcode == Instruction::Add || opcode == Instruction::Sub ||
         opcode == Instruction::Mul || opcode == Instruction::UDiv ||
         opcode == Instruction::SDiv || opcode == Instruction::URem ||
         opcode == Instruction::SRem || opcode == Instruction::Shl ||
         opcode == Instruction::LShr || opcode == Instruction::AShr ||
         opcode == Instruction::And || opcode == Instruction::Or ||
         opcode == Instruction::Xor ) {
        for ( int random = (int)llvm::cryptoutils->get_range(2); random < 3; random++ ) {
            unsigned randOp = llvm::cryptoutils->get_range(13);
            switch ( llvm::cryptoutils->get_range(4) ) {
                case 0:
                    BinaryOperator::Create(firstArray[randOp], I->getOperand(0),
                                           I->getOperand(1), I->getName(), &*I);
                    if ( willDelete.find(&*I) == willDelete.end() ) {
                        willDelete.insert(&*I);
                    }
                    break;
                case 1:
                    BinaryOperator::Create(firstArray[randOp], I->getOperand(0),
                                           I->getOperand(1), I->getName(), &*I);
                    break;
                case 2:
                    op = BinaryOperator::Create(firstArray[randOp], I->getOperand(0), I->getOperand(1), "", &*I);
                    BinaryOperator::Create(firstArray[randOp], op, I->getOperand(1), "", &*I);
                    break;
                case 3:
                    if ( op != nullptr )
                        BinaryOperator::Create(firstArray[randOp], op, I->getOperand(1), "", &*I);
                    else
                        BinaryOperator::Create(firstArray[randOp], I->getOperand(0), I->getOperand(1), "", &*I);
                    break;
                default:
                    break;
            }
        }
    }

首先是针对整数的计算，当确定操作符为整数计算符时，我们根据该指令，随机构造新的指令加入进来。除了整数计算还有浮点数计算，与之类似。

ICmpInst::Predicate ICmpPreArray[] = {ICmpInst::ICMP_EQ, ICmpInst::ICMP_NE, ICmpInst::ICMP_UGT,
                                      ICmpInst::ICMP_UGE, ICmpInst::ICMP_ULE, ICmpInst::ICMP_ULT,
                                      ICmpInst::ICMP_SGE, ICmpInst::ICMP_SGT, ICmpInst::ICMP_SLE,
                                      ICmpInst::ICMP_SLT};
if ( opcode == Instruction::ICmp ) {
    ICmpInst *currentI = (ICmpInst *) (&I);
    switch (llvm::cryptoutils->get_range(3)) { // must be improved
        case 0: //do nothing
            break;
        case 1:
            currentI->swapOperands();
            break;
        case 2: // randomly change the predicate
            currentI->setPredicate(ICmpPreArray[llvm::cryptoutils->get_range(10)]);
            break;
    }
}
FCmpInst::Predicate FCmpPreArray[] = {FCmpInst::FCMP_OEQ, FCmpInst::FCMP_ONE, FCmpInst::FCMP_UGE,
                                      FCmpInst::FCMP_UGT, FCmpInst::FCMP_ULE, FCmpInst::FCMP_ULT,
                                      FCmpInst::FCMP_OGE, FCmpInst::FCMP_OGT, FCmpInst::FCMP_OLT,
                                      FCmpInst::FCMP_OLE};
if ( opcode == Instruction::FCmp ) {
    FCmpInst *currentI = (FCmpInst *) (&I);
    switch (llvm::cryptoutils->get_range(3)) { // must be improved
        case 0: //do nothing
            break;
        case 1:
            currentI->swapOperands();
            break;
        case 2: // randomly change the predicate
            currentI->setPredicate(FCmpPreArray[llvm::cryptoutils->get_range(10)]);
            break;
    }
}

对于条件判断语句，修改条件判断的谓词。

当然对于其他操作符也可以进行修改，偷个懒先不搞了。要做也很容易，调用LLVM的接口即可。

针对alteredBlock的修改，先看看效果

RealBlock2:                                       ; preds = %36
  %41 = load i32, i32* %8, align 4
  %42 = add nsw i32 %41, %40
  store i32 %42, i32* %8, align 4
  br label %43

这是realBlock,只有简单的四条语句

RealBlock2AlteredBlock:                           ; No predecessors!
  %66 = load i32, i32* %8, align 4
  %67 = urem i32 %66, %40
  %68 = ashr i32 %66, %40
  %69 = add i32 %66, %40
  %70 = add i32 %69, %40
  %71 = add nsw i32 %66, %40
  store i32 %71, i32* %8, align 4
  br label %43

这是衍生的alteredBlock，可以看到增加了多条指令。

然后对文件进行测试。

原始的IR函数

define i32 @main() #0 {
  ...

; <label>:13:                                     ; preds = %0
  %14 = load i32, i32* %4, align 4
  %15 = add nsw i32 %14, 1
  store i32 %15, i32* %6, align 4
  %16 = load i32, i32* %2, align 4
  store i32 %16, i32* %5, align 4
  br label %21

; <label>:17:                                     ; preds = %0
  %18 = load i32, i32* %4, align 4
  store i32 %18, i32* %6, align 4
  %19 = load i32, i32* %2, align 4
  %20 = add nsw i32 %19, 1
  store i32 %20, i32* %5, align 4
  br label %21

; <label>:21:                                     ; preds = %17, %13
  store i32 0, i32* %8, align 4
  br label %22

; <label>:22:                                     ; preds = %32, %21
  %23 = load i32, i32* %8, align 4
  %24 = icmp slt i32 %23, 3
  br i1 %24, label %25, label %35

; <label>:25:                                     ; preds = %22
  %26 = load i32, i32* %6, align 4
  %27 = load i32, i32* %5, align 4
  %28 = sub nsw i32 %26, %27
  store i32 %28, i32* %9, align 4
  %29 = load i32, i32* %9, align 4
  %30 = load i32, i32* %7, align 4
  %31 = add nsw i32 %30, %29
  store i32 %31, i32* %7, align 4
  br label %32

; <label>:32:                                     ; preds = %25
  %33 = load i32, i32* %8, align 4
  %34 = add nsw i32 %33, 1
  store i32 %34, i32* %8, align 4
  br label %22

; <label>:35:                                     ; preds = %22
  %36 = load i32, i32* %7, align 4
  switch i32 %36, label %40 [
    i32 0, label %37
    i32 3, label %38
  ]

; <label>:37:                                     ; preds = %35
  store i32 1, i32* %7, align 4
  br label %41

; <label>:38:                                     ; preds = %35
  %39 = load i32, i32* %3, align 4
  store i32 %39, i32* %7, align 4
  br label %41

; <label>:40:                                     ; preds = %35
  store i32 0, i32* %7, align 4
  br label %41

; <label>:41:                                     ; preds = %40, %38, %37
  %42 = load i32, i32* %7, align 4
  %43 = icmp ne i32 %42, 0
  br i1 %43, label %49, label %44

; <label>:44:                                     ; preds = %41
  %45 = load i32, i32* %5, align 4
  %46 = add nsw i32 %45, 1
  store i32 %46, i32* %5, align 4
  %47 = load i32, i32* %6, align 4
  %48 = add nsw i32 %47, 1
  store i32 %48, i32* %6, align 4
  br label %49

; <label>:49:                                     ; preds = %44, %41
  ret i32 0
}

正好100行

加固后的IR函数

define i32 @main() #0 {
  ...

switchDefault:                                    ; preds = %loopEntry
  br label %loopEnd

first:                                            ; preds = %loopEntry
  %.reload = load volatile i32, i32* %.reg2mem
  %.reload9 = load volatile i32, i32* %.reg2mem8
  %13 = icmp sgt i32 %.reload, %.reload9
  %14 = select i1 %13, i32 420575174, i32 997972431
  store i32 %14, i32* %switchVar
  br label %loopEnd

; <label>:15:                                     ; preds = %loopEntry
  %16 = load i32, i32* %5, align 4
  %17 = add nsw i32 %16, 1
  store i32 %17, i32* %7, align 4
  %18 = load i32, i32* %1
  %19 = sub i32 %18, 1
  %20 = mul i32 %18, %19
  %21 = urem i32 %20, 2
  %22 = icmp eq i32 %21, 0
  %23 = select i1 %22, i32 -439097710, i32 -1781361060
  store i32 %23, i32* %switchVar
  br label %loopEnd

RealBlock:                                        ; preds = %loopEntry
  %24 = load i32, i32* %3, align 4
  store i32 %24, i32* %6, align 4
  store i32 -379256416, i32* %switchVar
  br label %loopEnd

; <label>:25:                                     ; preds = %loopEntry
  %26 = load i32, i32* %5, align 4
  store i32 %26, i32* %7, align 4
  %27 = load i32, i32* %3, align 4
  store i32 %27, i32* %.reg2mem10
  %28 = load i32, i32* %1
  %29 = sub i32 %28, 1
  %30 = mul i32 %28, %29
  %31 = urem i32 %30, 2
  %32 = icmp eq i32 %31, 0
  %33 = select i1 %32, i32 1829204214, i32 -1524008387
  store i32 %33, i32* %switchVar
  br label %loopEnd

RealBlock1:                                       ; preds = %loopEntry
  %.reload15 = load volatile i32, i32* %.reg2mem10
  %34 = add nsw i32 %.reload15, 1
  store i32 %34, i32* %6, align 4
  store i32 -379256416, i32* %switchVar
  br label %loopEnd

; <label>:35:                                     ; preds = %loopEntry
  store i32 0, i32* %9, align 4
  store i32 -1775434091, i32* %switchVar
  br label %loopEnd

; <label>:36:                                     ; preds = %loopEntry
  %37 = load i32, i32* %9, align 4
  %38 = icmp slt i32 %37, 3
  %39 = select i1 %38, i32 577122341, i32 -754147452
  store i32 %39, i32* %switchVar
  br label %loopEnd

; <label>:40:                                     ; preds = %loopEntry
  %41 = load i32, i32* %7, align 4
  %42 = load i32, i32* %6, align 4
  %43 = sub nsw i32 %41, %42
  store i32 %43, i32* %10, align 4
  %44 = load i32, i32* %10, align 4
  store i32 %44, i32* %.reg2mem16
  %45 = load i32, i32* %1
  %46 = sub i32 %45, 1
  %47 = mul i32 %45, %46
  %48 = urem i32 %47, 2
  %49 = icmp eq i32 %48, 0
  %50 = select i1 %49, i32 -392282435, i32 -1911983968
  store i32 %50, i32* %switchVar
  br label %loopEnd

RealBlock2:                                       ; preds = %loopEntry
  %51 = load i32, i32* %8, align 4
  %.reload21 = load volatile i32, i32* %.reg2mem16
  %52 = add nsw i32 %51, %.reload21
  store i32 %52, i32* %8, align 4
  store i32 -1465792220, i32* %switchVar
  br label %loopEnd

; <label>:53:                                     ; preds = %loopEntry
  %54 = load i32, i32* %9, align 4
  %55 = add nsw i32 %54, 1
  store i32 %55, i32* %.reg2mem22
  %56 = load i32, i32* %1
  %57 = sub i32 %56, 1
  %58 = mul i32 %56, %57
  %59 = urem i32 %58, 2
  %60 = icmp eq i32 %59, 0
  %61 = select i1 %60, i32 -1156815832, i32 1175436138
  store i32 %61, i32* %switchVar
  br label %loopEnd

RealBlock3:                                       ; preds = %loopEntry
  %.reload24 = load volatile i32, i32* %.reg2mem22
  store i32 %.reload24, i32* %9, align 4
  store i32 -1775434091, i32* %switchVar
  br label %loopEnd

; <label>:62:                                     ; preds = %loopEntry
  %63 = load i32, i32* %8, align 4
  store i32 %63, i32* %.reg2mem25
  store i32 -778348989, i32* %switchVar
  br label %loopEnd

NodeBlock:                                        ; preds = %loopEntry
  %.reload28 = load volatile i32, i32* %.reg2mem25
  %Pivot = icmp slt i32 %.reload28, 3
  %64 = select i1 %Pivot, i32 -1489924166, i32 1283611807
  store i32 %64, i32* %switchVar
  br label %loopEnd

LeafBlock5:                                       ; preds = %loopEntry
  %.reload26 = load volatile i32, i32* %.reg2mem25
  %SwitchLeaf6 = icmp eq i32 %.reload26, 3
  %65 = select i1 %SwitchLeaf6, i32 313440066, i32 297950529
  store i32 %65, i32* %switchVar
  br label %loopEnd

LeafBlock:                                        ; preds = %loopEntry
  %.reload27 = load volatile i32, i32* %.reg2mem25
  %SwitchLeaf = icmp eq i32 %.reload27, 0
  %66 = select i1 %SwitchLeaf, i32 1875124790, i32 297950529
  store i32 %66, i32* %switchVar
  br label %loopEnd

; <label>:67:                                     ; preds = %loopEntry
  store i32 1, i32* %8, align 4
  store i32 -2121542355, i32* %switchVar
  br label %loopEnd

; <label>:68:                                     ; preds = %loopEntry
  %69 = load i32, i32* %4, align 4
  store i32 %69, i32* %8, align 4
  store i32 -2121542355, i32* %switchVar
  br label %loopEnd

NewDefault:                                       ; preds = %loopEntry
  store i32 1890410157, i32* %switchVar
  br label %loopEnd

; <label>:70:                                     ; preds = %loopEntry
  store i32 0, i32* %8, align 4
  store i32 -2121542355, i32* %switchVar
  br label %loopEnd

; <label>:71:                                     ; preds = %loopEntry
  %72 = load i32, i32* %8, align 4
  %73 = icmp ne i32 %72, 0
  %74 = select i1 %73, i32 -1711396090, i32 2070871614
  store i32 %74, i32* %switchVar
  br label %loopEnd

; <label>:75:                                     ; preds = %loopEntry
  %76 = load i32, i32* %6, align 4
  %77 = add nsw i32 %76, 1
  store i32 %77, i32* %6, align 4
  %78 = load i32, i32* %7, align 4
  store i32 %78, i32* %.reg2mem29
  %79 = load i32, i32* %1
  %80 = sub i32 %79, 1
  %81 = mul i32 %79, %80
  %82 = urem i32 %81, 2
  %83 = icmp eq i32 %82, 0
  %84 = select i1 %83, i32 -2103269463, i32 2005576382
  store i32 %84, i32* %switchVar
  br label %loopEnd

RealBlock4:                                       ; preds = %loopEntry
  %.reload34 = load volatile i32, i32* %.reg2mem29
  %85 = add nsw i32 %.reload34, 1
  store i32 %85, i32* %7, align 4
  store i32 -1711396090, i32* %switchVar
  br label %loopEnd

; <label>:86:                                     ; preds = %loopEntry
  ret i32 0

RealBlockAlteredBlock:                            ; preds = %loopEntry
  %87 = load i32, i32* %3, align 4
  store i32 %87, i32* %6, align 4
  store i32 -379256416, i32* %switchVar
  br label %loopEnd

RealBlock1AlteredBlock:                           ; preds = %loopEntry
  %.reload13 = load volatile i32, i32* %.reg2mem10
  %88 = sdiv i32 %.reload13, 1
  %.reload12 = load volatile i32, i32* %.reg2mem10
  %89 = and i32 %.reload12, 1
  %.reload11 = load volatile i32, i32* %.reg2mem10
  %90 = and i32 %.reload11, 1
  %91 = and i32 %90, 1
  %.reload14 = load volatile i32, i32* %.reg2mem10
  %92 = add nsw i32 %.reload14, 1
  store i32 %92, i32* %6, align 4
  store i32 -379256416, i32* %switchVar
  br label %loopEnd

RealBlock2AlteredBlock:                           ; preds = %loopEntry
  %93 = load i32, i32* %8, align 4
  %.reload19 = load volatile i32, i32* %.reg2mem16
  %94 = ashr i32 %93, %.reload19
  %.reload18 = load volatile i32, i32* %.reg2mem16
  %95 = or i32 %93, %.reload18
  %.reload17 = load volatile i32, i32* %.reg2mem16
  %96 = or i32 %95, %.reload17
  %.reload20 = load volatile i32, i32* %.reg2mem16
  %97 = add nsw i32 %93, %.reload20
  store i32 %97, i32* %8, align 4
  store i32 -1465792220, i32* %switchVar
  br label %loopEnd

RealBlock3AlteredBlock:                           ; preds = %loopEntry
  %.reload23 = load volatile i32, i32* %.reg2mem22
  store i32 %.reload23, i32* %9, align 4
  store i32 -1775434091, i32* %switchVar
  br label %loopEnd

RealBlock4AlteredBlock:                           ; preds = %loopEntry
  %.reload32 = load volatile i32, i32* %.reg2mem29
  %98 = xor i32 %.reload32, 1
  %.reload31 = load volatile i32, i32* %.reg2mem29
  %99 = sub i32 %.reload31, 1
  %.reload30 = load volatile i32, i32* %.reg2mem29
  %100 = udiv i32 %.reload30, 1
  %.reload33 = load volatile i32, i32* %.reg2mem29
  %101 = add nsw i32 %.reload33, 1
  store i32 %101, i32* %7, align 4
  store i32 -1711396090, i32* %switchVar
  br label %loopEnd

loopEnd:                                          ; preds = %RealBlock4AlteredBlock, %RealBlock3AlteredBlock, %RealBlock2AlteredBlock, %RealBlock1AlteredBlock, %RealBlockAlteredBlock, %RealBlock4, %75, %71, %70, %NewDefault, %68, %67, %LeafBlock, %LeafBlock5, %NodeBlock, %62, %RealBlock3, %53, %RealBlock2, %40, %36, %35, %RealBlock1, %25, %RealBlock, %15, %first, %switchDefault
  br label %loopEntry
}

我没有截全，很长，一共307行。也就是说函数规模变成原来的3倍。

编译一下丢IDA看看。

混淆前，程序主要流程是这样的

混淆后，由于我屏幕太小，只能截Graph overview

最后，代码已经同步到github

https://github.com/penguin-wwy/Armariris

有兴趣的小伙伴可以玩一玩

over