详解 LLVM 混淆器

作者：Kareem El-Faramawi | Toshi Piazza

译：Skye

LLVM 混淆器是一个工业级的混淆器，在近几年的 CTF 比赛中频频出现。这篇博文主要包括了我们在理解混淆器本身的设计方面的工作，以及在模糊处理的实现中可能存在的弱点。我们使用 Binary Ninja 及其插件来使这方面的工作自动化。

引言

开源的 LLVM 混淆器显示为三个 3 个相对独立的 LLVM 分支，都是为了执行掩盖 CFG 的混淆模式，或是以某种方式计算原始程序的算术运算。通过这些混淆手段，可以模糊原程序的流程或者某一部分的算法，给逆向分析带来一些困难。

值得注意的是，由于这种方式在 LLVM IR 上运行，因此它支持目前的所有架构。

以下是三个 LLVM 混淆的方式：

• 指令替换
• 虚假控制流
• 控制流平坦化

以上均是作者维护的文档页面，然而，如果觉都文档存在不足，我们可以阅读源码来理解混淆器。

不幸的是，LLVM-obfuscator 这一项目有着众多分支，一个用于该分支所针对的每个 LLVM 版本，只要一个对整个 LLVM 项目的 clone 操作，读者也许会在繁杂的代码中迷失。4.0 版本的代码分支可以在这里看到，在 lib/Transforms 目录中，就是习惯上的 LLVM 混淆器。

这篇博文主要重点是 LLVM 混淆器的控制流平坦化的特性，该特性是在整个 LLVM 生态系统中最有效的，也是最有意思的混淆处理方式。

控制流平坦化

我们可以将控制流平坦化的效果可视化为下面的 CFG 转换，主要通过以下步骤实现：

1. 在源程序整个代码流程中，分析搜索出所有的基本代码块(Basic Block)
2. 把基本代码块(Basic Block)放置在控制流图的最底端，删除掉所有的基本块中的跳转关系（注：因此，源程序中的条件分支等不是一个基本代码块）
3. 添加混淆器的流程控制分发逻辑，通过新的复杂分发逻辑来还原源程序基本代码块之间的逻辑关系

我们以下图来说明，左侧是 IDA Pro 7.0（demo 版即可）对未混淆程序生成的 CFG，右侧是相同的程序，但是经过 LLVM 混淆的控制流平坦化后，使用 IDA Pro 7.0 生成的 CFG。

在这两幅图中，绿色的块表示函数里面的代码基本块，图中的蓝色的块就是混淆器为了达到混淆效果和保持原程序逻辑而添加的粘合代码，因为蓝色块在 IDA Pro 中的 CFG 大致为一个主干，因此我们叫它函数主干(backbone of the function)。

对于右侧这幅图，为了看起来更加的直观，我们可以使用 IDA 的 node 分组的功能把流程图的显示方式优化一下，将 backbone 代码合并为一个节点(node)，经过这样处理后的 CFG，更像在其他文献中见到的控制流平坦化后的 CFG 了。

虽然现在流程图简单了不少，但是通过和上面的左图进行对比， 整个程序流程还是发生了很大的变化，并且各个基本块之间的逻辑关系也很难判断了，整个代码流程看上去更像是一个 switch...case 结构，每个基本块是 case 分支逻辑。

因此，我们可以这样想：整个程序的控制流变成了一个状态机，每次执行哪个代码块由状态机的值来决定，而每个代码块最后会更新状态机的值，然后程序主干（backbone of the function）根据状态机的值来跳转，决定执行哪个代码块，因此，一个代码块对应一个固定的状态机的值。

控制流平坦化的不足

从现在开始，我们开始借助 Binary Ninja 这个平台来进行后续的分析，选择这个平台主要是基于这个平台里的几个 IDA 中没有的特性：

• Medium-level IL
• SSA Form
• Value-set analysis

确定函数主干

为了理解流程平坦化的弱点，我们通过一个例子来详细的分析一下：

这个例子就是我们上面的那个经过混淆处理的程序的一部分，其他部分的代码基本是相似的，因此这里我们就截取其中一部分代表就可以了。这段代码的作用是，读取状态变量，然后把变量和某个值进行比较，如果比较相等，就跳转到某个基本块执行，如果不等，就跳转到下一个函数主干中继续上述的过程。

我们这就发现了一个关键的脆弱点：给定一个状态变量，记为 state_var ，我们发现每个函数主干代码块至少包含一次对这个变量的引用，如果遍历出所有引用到这个变量的代码块，那我们就可以得到所有的函数主干块。下面我们通过 Binary Ninja 的 medium-level IL 特性来寻找所有的基本代码块，代码如下：

def compute_backbone_map(bv, mlil, state_var):
    backbone = {}

    # Collect all mlil instructions where the state variable is used
    # `state_var` is the variable loaded in each backbone block to check the state,
    # either the state variable itself, or a pointer to it
    uses = mlil.get_var_uses(state_var)

    # Gather the blocks where the state is used
    blks = (b for idx in uses for b in mlil.basic_blocks if b.start <= idx < b.end)

    # In each of these blocks, find the value of the state
    for bb in blks:
        # Find the comparison
        cond_var = bb[-1].condition.src
        cmp_il = mlil[mlil.get_var_definitions(cond_var)[0]]

        # Pull out the state value
        state = cmp_il.src.right.constant
        backbone[state] = bv.get_basic_blocks_at(bb[0].address)[0]

    return backbone

上面这个算法可以找到所有引用过 state_var 的函数主干块，包括程序的起始块。幸运的是，程序的起始块通常都会包含该状态变量，就在状态机跳转之前，如下图所示：

我们在自定义的起始块中很容易就能找到状态变量，接着通过 def-use 和 use-def 调用链，就能找到其他的主干块。

确定真实的程序逻辑块

通过类似的方式，我们看看能不能找到什么特征，通过这个特征来找到所有的逻辑块。在我们的这个例子里面，一个真实基本块会包含一个或者多个执行出口，而执行出口一般都是以一个无条件跳转实现的，一个比较典型的真实块看起来大致是这样的：

这段代码大致是，先修改状态变量的值，然后跳转至函数主干，那就亦为之，下次执行的真实的代码块对应的 case 值为 0xfcbce33c ，一个真实的代码块的子块会稍稍有趣一些，在 MLIL 视图中，CMOV 指令被扩展为多个基本块：

这里，源程序的一个条件语句其实被转换成了一个赋值语句，然后根据赋值的结果决定是不是要执行某个代码块，如果源程序如下：

if (var == 0xdeadbeef) {
  // ...
}

将被转换成：

state_var = var == 0xdeadbeef ?
  0xe38294d4 :
  0xfcbce33c;

尽管这个转换很有趣，但我们的目的是找到源程序中的所有基本块。为了实现目的，我们注意到 LLVM 混淆器中的一个弱点：所有的源程序基本块都包含对状态变量的至少一次定义。

乍一看，可能我们要基于深度优先来进行一次 def-use 调用的搜索，不过在 Binary Ninja 上，这个工作被简化了不少，前面一个小节里面，我们查找了所有使用到了状态变量 state_var 的代码块，但是在这里我们只查找定义了这个变量的代码块就好了，代码如下：

# this gets all definitions of state_var, and
# we treat all such instructions as being in
# a real basic block
real = mlil.get_var_definitions(state_var)
real = itemgetter(*real)(mlil)

上面的代码里面找到的每个包含了对状态变量定义的代码块都被认为是一个基本的逻辑代码块，包含起始块。后面的章节里面会发现，这种特征方式得到的结果还是很令人满意的。

还原 CFG

到现在为止，我们基本上已经有了重构代码流程的所有信息，再梳理一下的话，我们现在对于一个经过混淆过的程序，目前掌握了以下两点信息：

• 所有的代码基本块
• 状态机值和基本代码块的映射关系

我们不知道的是，不知道对一个给定的代码块，它的下一个执行代码块是说明。因此，我们要确定一个基本代码块执行完毕后，它的状态机的值改变成了何值。为了完成这个目标，我们需要用到 Binary Ninja 另一个特性，那就是 Value-Set 分析。通过该分析，我们可以知道某内存地址或某寄存器的值，因此，我们就可以确定状态机的值。

前文提到过，一个基本代码块会把状态机的变量值更新为一个固定值，考虑到对状态机变量的定义，这十分容易理解。代码如下：

def resolve_cfg_link(bv, mlil, il, backbone):
    # il refers to a definition of the state_var
    bb = bv.get_basic_blocks_at(il.address)[0]

    # Unconditional jumps will set the state to a constant
    if il.src.operation == MediumLevelILOperation.MLIL_CONST:
        return CFGLink(bb, backbone[il.src.constant], def_il=il)
    # ...

对于有条件跳转的情况，处理的方式有点 trick 的味道，由于我们的目标是要确定基本块执行完毕的时候，出口的状态机变量的值是什么，也就是要确定条件跳转的时候，哪个为真, 哪个为假, 为了方便，我们使用 Ninja 的 SSA 图形视图来观察一下，看下面这个例子：

在这个例子里面，函数执行完毕的时候，是有两种情况的状态机变量的，在上图里面，凡是会影响到状态机变量相关的语句全都高亮了。为了更加的直观，这里把上述的逻辑用 LLVM-IR 再描述一下：

%next_state = select i1 %original_condition, i32 %true_branch, i32 %false_branch
store i32 %next_state, i32* %state

因此，在编译时，大致逻辑为：

1. 先把 %next_state 置为 %false_branch
2. 如果 %original_condition 的结果为 1，将 %next_state 置为 %true_branch
3. 把 state 结果保存至 %state 变量

观察上图中的 SSA-MLIL, 我们观察高亮的语句部分，其实就是在两个不同版本的 %next_State 变量之间进行选择，而且每个不同版本的 %next_State 后面跟着一个数字作为版本号标志，再根据我们分析的逻辑，版本号小的那个就是 false，版本号大的是 true 。最后借助于 Ninja 的 Value-Set 分析，我们就可以得出最后的 %next_State 的最终值，所以就能确定下一个要执行的基本块是哪个了，代码如下：

    # ...
    # Conditional jumps choose between two values
    else:
        # Go into SSA to figure out which state is the false branch
        # Get the phi for the state variable at this point
        phi = get_ssa_def(mlil, il.ssa_form.src.src)
        assert phi.operation == MediumLevelILOperation.MLIL_VAR_PHI

        # The cmov (select) will only ever replace the default value (false)
        # with another if the condition passes (true)
        # So all we need to do is take the earliest version of the SSA var
        # as the false state
        f_def, t_def = sorted(phi.src, key=lambda var: var.version)

        # There will always be one possible value here
        false_state = get_ssa_def(mlil, f_def).src.possible_values.value
        true_state  = get_ssa_def(mlil, t_def).src.possible_values.value

        return CFGLink(bb, backbone[true_state], backbone[false_state], il)

现在版本 API 使用不便，但结果大致准确，综合上述分析，脚本如下：

def deflatten_cfg(func, mlil, addr):
    state_var = func.get_low_level_il_at(addr).medium_level_il.dest
    backbone = compute_backbone_map(bv, mlil, state_var)
    original = compute_original_blocks(bv, mlil, state_var)
    CFG = [resolve_cfg_link(bv, mlil, il, backbone) for il in original]
    print "[+] Computed original CFG"
    pprint(CFG)

"""
[+] Computed original CFG
[<C Link: <block: x86_64@0x4006e7-0x400700> => T: <block: x86_64@0x400700-0x400720>,
                                               F: <block: x86_64@0x400735-0x400741>>,
 <U Link: <block: x86_64@0x4006d4-0x4006e7> => <block: x86_64@0x4006e7-0x400700>>,
 <U Link: <block: x86_64@0x400700-0x400720> => <block: x86_64@0x400720-0x400735>>,
 <U Link: <block: x86_64@0x4006b4-0x4006d4> => <block: x86_64@0x400741-0x400749>>,
 <U Link: <block: x86_64@0x400735-0x400741> => <block: x86_64@0x400741-0x400749>>,
 <C Link: <block: x86_64@0x400699-0x4006b4> => T: <block: x86_64@0x4006b4-0x4006d4>,
                                               F: <block: x86_64@0x4006d4-0x4006e7>>,
 <U Link: <block: x86_64@0x400720-0x400735> => <block: x86_64@0x4006e7-0x400700>>]
"""

重构二进制文件

不幸的是，在 Binary Ninja 上 Patch 二进制程序十分不方便，但是没有更好的选择了。到现在为止，我们已经能够重构原始的控制流程了，剩下的工作就是根据掌握的信息来 Patch 程序，让真实逻辑代码块之间直接相连，忽略(nop)掉状态机的函数主干代码。

构建代码原型

我们目前获取的所有原始代码块里面，还包含了当时 LLVM 混淆器插入的一些框架代码，比如更新状态机的代码，这个代码现在对我们来说是垃圾代码了，因此需要清理掉这些代码，删掉以下三类代码不会影响基本代码块：

• 当前代码块的结束代码
• 更新状态机值的代码
• def-use 调用链中计算状态转移的代码

我们通过示例来说明。首先，我们在一个代码块中看到了无条件跳转的“死”指令，因为不存在 def-use 调用链，我们将红色高亮指令删除即可：

在这里红色高亮的所有指令都可以删掉，所以在下面这个有条件跳转指令的代码块中，可以删掉的指令将有更多：

将上述无用代码移除之后，还会给我们修复源程序的控制流腾出空间，在上面两种情况下，我们都注意到了可以删除的指令，并在下一个步骤继续执行。

修复控制流

现在，我们可以修复源程序的控制流了。仅用最简单的跳转指令来进行代码块之间的连接，对于没有条件跳转指令的代码块，使用如下指令即可：

jmp next_block

对于有条件分支的情况下，就需要确定是使用哪种 jcc 指令了。前面的小节里面我们知道，如果 true 分支成立，控制流平坦化会用 true 状态覆盖 false 状态。在实际的代码中，一般是使用 cmovne 这样的语句来操作的，于是这里取一个巧，我们就干脆不管这个时候的状态，我们使用 jne 替代，复用混淆的状态转移结果，最后的 Patch 就像这样：

; cc is the condition used in the CMOVcc
jcc true_branch
jmp false_branch

经过上述分析，我们的 Patch 过程步骤如下：

1. 把除了垃圾指令之外的指令拷贝一份形成一个新的代码块
2. 在代码块的最后追加 jump 跳转到下一个块
3. 最后为了跟原先的程序大小保持一致，把剩余的空间用 nop 指令填充

对于无条件跳转，我们这样处理（Patch 后在右侧）：

有条件跳转，我们这样处理：

现在，整个源程序的 CFG 就修复好了。

最后的清理

在 Patch 之后，函数主干代码和垃圾指令是在实际运行中无法执行到的，但使用 IDA Pro 打开还是在代码块视图中出现。为了看起来更整齐，我们可以将无用指令使用 nop 填充。（这一步并不是必要的，如 IDA 的线性分析器将修复函数主干，我们的目的是使 CFG 更可读）

结果

为了展示我们的解混淆，我们在 Binary Ninja 查看源程序的 main 函数：

源程序的控制流平坦化后：

上图右侧的代码块就是我们的函数主干，源程序的基本代码块都位于左侧。

最终，我们解混淆的结果如下：

对比一下，我们解混淆的结果已经接近源程序了。仅有这一点不同：

• 部分代码块被控制流平坦化拆开，解混淆后我们没有将这些代码块合并
• 为了连接代码块，我们插入了 jmp 指令，源程序中并没有

但是这些问题是我们目前比较难修复的，因为我们并没有手动处理函数中所有的块。目前函数的功能已经和源程序相差无几，我们的目的也差不多达到了。

使用插件

手动实现本文的分析还是十分麻烦的，我们将工作自动化，做成了插件，你可以在 Github 找到源码，clone 这个项目至 Binary Ninja 的插件目录就可以使用了。（注：Binary Ninja 收费，免费版本不支持插件扩展）

使用插件解混淆只需要两步：

1. 找到一条更新 state_var 的指令
2. 右键执行插件

以下为示例：

参考

• 原文：https://blog.rpis.ec/2017/12/dissection-llvm-obfuscator-p1.html
• 翻译了一半才想起来这篇在看雪上早有翻译了，有能力的还是阅读原文，翻译出来的，总觉得差点味道，各位将就看
• 越来越多的 CTF 的二进制题目中为了恶心选手，二进制程序用 LLVM 混淆的也越来越多，可能以后解 LLVM 混淆流程会自动化，但目前还是以手动分析为主。所以还是学习一个。