利用符号执行去除控制流平坦化

# 1. 背景

## 1.1 控制流平坦化

控制流平坦化(control flow flattening)的基本思想主要是通过一个主分发器来控制程序基本块的执行流程，例如下图是正常的执行流程

![image_1b6tbj30u6pc1c361ftd13ca1vfjn.png-9.7kB][1]

经过控制流平坦化后的执行流程就如下图

![image_1b6td3nbf8hl185kf8f7ugn2d14.png-13.7kB][2]

这样可以模糊基本块之间的前后关系，增加程序分析的难度，同时这个流程也很像VM的执行流程。更多控制流平坦化的细节可以看[Obfuscating C++ programs via control flow flattening][3]，本文以[Obfuscator-LLVM][4]的控制流平坦化为例。

[1]: http://static.zybuluo.com/birdg0/8opczl4idqc0zsw7mkkfaghv/image_1b6tbj30u6pc1c361ftd13ca1vfjn.png
  [2]: http://static.zybuluo.com/birdg0/x8mc397bj2al3pivppeep3z2/image_1b6td3nbf8hl185kf8f7ugn2d14.png
  [3]: http://ac.inf.elte.hu/Vol_030_2009/003.pdf
  [4]: https://github.com/obfuscator-llvm/obfuscator/tree/llvm-3.6.1
  [5]: https://pdfs.semanticscholar.org/a29f/c90b207befb42f67a040c6a07ea6699f6bad.pdf
  [6]: http://dslab.epfl.ch/pubs/selsymbex.pdf
  [7]: http://mir.cs.illinois.edu/marinov/publications/SenETAL05CUTE.pdf
  [8]: https://github.com/JonathanSalwan/Triton
  [9]: https://github.com/angr/angr
  [10]: http://static.zybuluo.com/birdg0/wxx18tv5ric5wknyj4l6im5k/image_1b708vp9hi4k31r1fq4ei01l1c9.png
  [11]: http://static.zybuluo.com/birdg0/bujceez9oc7smst2f44cchz2/image_1b70ac22pbru153717be17ttcr3m.png
  [12]: http://blog.quarkslab.com/deobfuscation-recovering-an-ollvm-protected-program.html
  [13]: https://github.com/programa-stic/barf-project
  [14]: https://github.com/angr/angr-management/blob/master/angrmanagement/utils/graph.py
  [15]: http://static.zybuluo.com/birdg0/6bavjjtzbizgk20ywnjrk90y/image_1b72oboes1nujq144nspep120o1t.png
  [16]: http://static.zybuluo.com/birdg0/en19d7sqsly89wfj1bwhtbft/image_1b72muut91qdb15ms1knnish1tom.png
  [17]: http://static.zybuluo.com/birdg0/qgdi8y6gljpymbpqj9tienck/image_1b72nf28b1ovl1v571i3a1q9g1l9t13.png
  [18]: https://security.tencent.com/index.php/opensource/detail/18
  [19]: https://security.tencent.com/index.php/opensource/detail/18
  [20]: http://ac.inf.elte.hu/Vol_030_2009/003.pdf
  [21]: https://github.com/obfuscator-llvm/obfuscator/tree/llvm-3.6.1
  [22]: https://pdfs.semanticscholar.org/a29f/c90b207befb42f67a040c6a07ea6699f6bad.pdf
  [23]: http://dslab.epfl.ch/pubs/selsymbex.pdf
  [24]: http://mir.cs.illinois.edu/marinov/publications/SenETAL05CUTE.pdf
  [25]: https://github.com/JonathanSalwan/Triton
  [26]: https://github.com/angr/angr
  [27]: http://blog.quarkslab.com/deobfuscation-recovering-an-ollvm-protected-program.html
  [28]: https://github.com/programa-stic/barf-project
  [29]: https://github.com/angr/angr-management

## 1.2 符号执行

[符号执行][5]是一种重要的形式化方法和软件分析技术，通过使用符号执行技术，将程序中变量的值表示为符号值和常量组成的计算表达式，符号是指取值集合的记号，程序计算的输出被表示为输入符号值的函数，其在软件测试和程序验证中发挥着重要作用，并可以应用于程序漏洞的检测。

符号执行的发展是从静态符号执行到动态符号执行到[选择性符号执行][6]，动态符号执行会以具体数值作为输入来模拟执行程序，是[混合执行][7](concolic execution)的典型代表，有很高的精确度，目前较新的符号执行工具有[Triton][8]和[angr][9]，本文是以angr为例。

# 2. 分析

首先写一个简单的示例程序

```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int check_password(char *passwd)
{
    int i, sum = 0;
    for (i = 0; ; i++)
    {
        if (!passwd[i])
        {
            break;
        }
        sum += passwd[i];
    }
    if (i == 4)
    {
        if (sum == 0x1a1 && passwd[3] > 'c' && passwd[3] < 'e' && passwd[0] == 'b')
        {
            if ((passwd[3] ^ 0xd) == passwd[1])
            {
                return 1;
            }   
            puts("Orz...");
        }
    }
    else
    {
        puts("len error");
    }
    return 0;
}

int main(int argc, char **argv)
{
    if (argc != 2)
    {
        puts("error");
        return 1;
    }
    if (check_password(argv[1]))
    {
        puts("Congratulation!");
    }
    else
    {
        puts("error");
    }
    return 0;
}
```

编译
```
gcc check_passwd.c -o check_passwd
```

用IDA查看未经过控制流平坦化的控制流程图(CFG)

![image_1b708vp9hi4k31r1fq4ei01l1c9.png-174.7kB][10]

添加控制流平坦化
```
build/bin/clang check_passwd.c -o check_passwd_flat -mllvm -fla
```

可以看到控制流平坦化后的CFG非常漂亮

![image_1b70ac22pbru153717be17ttcr3m.png-77kB][11]

通过分析可以发现原始的执行逻辑只在真实块(自己想的名称...)以及序言和retn块中，其中会产生分支的真实块中主要是通过**CMOV**指令来控制跳转到哪一个分支，因此只要确定这些块的前后关系就可以恢复出原始的CFG，这个思路主要是参考[Deobfuscation: recovering an OLLVM-protected program][12]。

# 3. 实现

## 3.1 获取真实块、序言、retn块和无用块

由于angr的CFG跟IDA的有点不同，因此本文使用[BARF][13]来获取，后来问了Fish Wang可以用[angr-management][14]下的to_supergraph来获取。主要思路：

1. 函数的开始地址为序言的地址
2. 序言的后继为主分发器
3. 后继为主分发器的块为预处理器
4. 后继为预处理器的块为真实块
5. 无后继的块为retn块
6. 剩下的为无用块

主要代码：
```python
def get_retn_predispatcher(cfg):
    for block in cfg.basic_blocks:
        if len(block.branches) == 0 and block.direct_branch == None:
            retn = block.start_address
        elif block.direct_branch == main_dispatcher:
            pre_dispatcher = block.start_address
    return retn, pre_dispatcher
    
def get_relevant_nop_blocks(cfg):
    relevant_blocks = []
    nop_blocks = []
    for block in cfg.basic_blocks:
        if block.direct_branch == pre_dispatcher and len(block.instrs) != 1:
            relevant_blocks.append(block.start_address)
        elif block.start_address != prologue and block.start_address != retn:
            nop_blocks.append(block)
    return relevant_blocks, nop_blocks
```

## 3.2 确定真实块、序言和retn块的前后关系

这个步骤主要是使用符号执行，为了方便，这里把真实块、序言和retn块统称为真实块，符号执行从每个真实块的起始地址开始，直到执行到下一个真实块。如果遇到分支，就改变判断值执行两次来获取分支的地址，这里用angr的inspect在遇到类型为ITE的IR表达式时，改变临时变量的值来实现，例如下面这个块

![image_1b72oboes1nujq144nspep120o1t.png-13kB][15]

使用**statement before**类型的inspect
```python
def statement_inspect(inspect):
    global modify_value
    expressions = state.scratch.irsb.statements[state.inspect.statement].expressions
    if len(expressions) != 0 and isinstance(expressions[0], pyvex.expr.ITE):
        state.scratch.temps[expressions[0].cond.tmp] = modify_value
        state.inspect._breakpoints['statement'] = []

state.inspect.b('statement', when=simuvex.BP_BEFORE, action=statement_inspect)
```

修改临时变量28为false或true再执行就可以得到分支的地址
```
t48 = ITE(t28,0xca2df6de,0xaf59b039)
```

如果遇到call指令，使用hook的方式直接返回
```python
def retn_procedure(state):
    global b
    ip = state.se.any_int(state.regs.ip)
    b.unhook(ip)
    return
    
b.hook(hook_addr, retn_procedure, length=5)
```

主要代码：
```python
for relevant in relevants_without_retn:
    block = cfg.find_basic_block(relevant)
    has_branches = False
    hook_addr = None
    for ins in block.instrs:
        if ins.asm_instr.mnemonic.startswith('cmov'):
            patch_instrs[relevant] = ins.asm_instr
            has_branches = True
        elif ins.asm_instr.mnemonic.startswith('call'):
            hook_addr = ins.address
    if has_branches:
        flow[relevant].append(symbolic_execution(relevant, hook_addr, claripy.BVV(1, 1), True))
        flow[relevant].append(symbolic_execution(relevant, hook_addr, claripy.BVV(0, 1), True))
    else:
        flow[relevant].append(symbolic_execution(relevant))
```

## 3.3 Patch二进制程序

首先把无用块都改成nop指令
```python
for nop_block in nop_blocks:
    fill_nop(origin_data, nop_block.start_address - base_addr, nop_block.end_address - base_addr + 1)
```

然后针对没有产生分支的真实块把最后一条指令改成jmp指令跳转到下一真实块
```python
last_instr = cfg.find_basic_block(parent).instrs[-1].asm_instr
file_offset = last_instr.address - base_addr
origin_data[file_offset] = opcode['jmp']
file_offset += 1
fill_nop(origin_data, file_offset, file_offset + last_instr.size - 1)
fill_jmp_offset(origin_data, file_offset, childs[0] - last_instr.address - 5)
```

针对产生分支的真实块把**CMOV**指令改成相应的条件跳转指令跳向符合条件的分支，例如`CMOVZ`改成`JZ`，再在这条之后添加`JMP`指令跳向另一分支
```python
instr = patch_instrs[parent]
file_offset = instr.address - base_addr
fill_nop(origin_data, file_offset, cfg.find_basic_block(parent).end_address - base_addr + 1)
origin_data[file_offset] = opcode['j']
origin_data[file_offset + 1] = opcode[instr.mnemonic[4:]]
fill_jmp_offset(origin_data, file_offset + 2, childs[0] - instr.address - 6)
file_offset += 6
origin_data[file_offset] = opcode['jmp']
fill_jmp_offset(origin_data, file_offset + 1, childs[1] - (instr.address + 6) - 5)
```

上述就是去除控制流平坦化的总体实现思路。

# 4. 演示

去除指定函数的控制流平坦化
````
python deflat.py check_passwd_flat 0x400530
```

用IDA查看恢复后的CFG

![image_1b72muut91qdb15ms1knnish1tom.png-172.4kB][16]

可以看到CFG跟原来的大致一样，然后反编译恢复出原始代码

![image_1b72nf28b1ovl1v571i3a1q9g1l9t13.png-12.4kB][17]

# 5. 总结

本文主要针对x86架构下Obfuscator-LLVM的控制流平坦化，但最重要的是去除控制流平坦化过程中的思路，同时当函数比较复杂时可能速度会有点慢。有时间会以此为基础尝试分析伪造控制流、指令替换和VM等软件保护手段，另外符号执行也可以应用于漏洞挖掘领域，例如借助符号执行生成覆盖率更高的Fuzzing测试集以及求解达到漏洞点的路径等。本文相关的脚本[deflat][18]请移步到[TSRC][19]实验室下载。

由于小弟刚学习符号执行，可能有理解错误的地方，欢迎研究符号执行或者认为有更好思路的师傅们批评指正。最后，感谢angr主要开发者Fish Wang在这期间的耐心帮助。

# 6. 参考

1. [Obfuscating C++ programs via control flow flattening][20]
2. [https://github.com/obfuscator-llvm/obfuscator/tree/llvm-3.6.1][21]
3. [Symbolic Execution and Program Testing][22]
4. [Selective Symbolic Execution][23]
5. [CUTE: A Concolic Unit Testing Engine for C][24]
6. [https://github.com/JonathanSalwan/Triton][25]
7. [https://github.com/angr/angr][26]
8. [http://blog.quarkslab.com/deobfuscation-recovering-an-ollvm-protected-program.html][27]
9. [https://github.com/programa-stic/barf-project][28]
10. [https://github.com/angr/angr-management][29]