LLVM代码及指令选择分析

概述

LLVM Obfuscator是一款工业级别的代码混淆器，在过去几年的CTF里我们经常会遇到经过代码经过它混淆的情况。这片博文记录了我们对混淆器原理的研究以及从中发现的有关混淆器的设计实现的脆弱之处。基于我们的研究结果，我们在Binary Ninja平台上写了一个插件，通过这个插件可以自动化的解决掉由于代码混淆带来的逆向分析困难。

LLVM Obfuscator简介

LLVM Obfuscator是一个基于LLVM框架实现的一个开源代码混淆器，整个项目包含了三个相对独立的LLVM pass, 每个pass实现了一种混淆方式，通过这些混淆手段，可以模糊原程序的流程或者某一部分的算法，给逆向分析带来一些困难。

由于上述的三个pass是基于LLVM IR实现的, 因此从理论上来说， 这种混淆器是支持世界上任何一种语言和机器架构的。

关于每种pass的详细文档，可以查看下面的这三个链接：

1. Instructions Substitution(指令变换)
2. Bogus Control Flow(流程伪造)
3. Control Flow Flattening(流程平坦化)

上面的这几个链接里面是各个pass的作者维护的一份简单文档，如果你觉得文档不够详尽，建议直接参考相应的源码即可，可能对你来说会又直观又准确。

 如果说看代码，其实是比较费劲的一个事情，主要是LLVM Obfuscator的工程代码结构的原因。现在github上，LLVM Obfuscator是按分支来维护的，每个版本一个分支，也就是说你Clone下来的代码都杂在一起，直接上来就看代码很容易迷失在代码的海洋中。不过我们可以有目的的挑着看，比如我们Clone一份4.0的代码，然后直接在 lib/Transforms目录下的代码， 这里都是自定义的LLVM pass。

在我们这篇博文里面，我们只关注流程平坦化这一个主题，这个特性在我看来是比较有趣，并且混淆效果也是比较理想的一个特性。

控制流程平坦化

总体来说，控制流程平坦化这个特性，抽象下来，主要是通过这几个步骤来实现的：

1. 在整个代码流程中，分析搜集出所有的基本代码块(Basic Block)（译者注：遇到条件分支就算是一个新的代码块了）
2. 把基本代码块放到控制流图的最底部，然后删除掉原来的基本块之间的跳转关系
3. 添加混淆器的流程控制分发逻辑，通过新的复杂分发逻辑还原原来程序块之间的逻辑关系

还是举个例子吧，为了形象一点，我这里给出两幅图来进行左右对比。

 左边的图是IDA7.0（Demo版就行）对未混淆程序生成的代码流程图，右图是同一个程序经过LLVM Obfuscator的流程平坦化处理之后IDA7.0分析出的代码流程图。

在这两幅图里面，绿色的块表示函数里面的代码基本块，图中的蓝色的块就是混淆器为了达到混淆效果和保持原程序逻辑而添加的粘合代码，这里我们给这些蓝色块的代码起个名字好了，叫它 backbone(混淆器运行框架)

对于右边这幅图，为了看起来更加的直观，我们可以使用IDA的node分组的功能把流程图的显示方式优化一下，这里我直接把backbone代码合并成一个node，这样看起来就清晰了，看图：

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

由此我们也可以这样想，整个逻辑流程变成了一个状态机架构，每次执行哪个代码块由状态机的值来决定，而每个代码块最后会更新状态机的值，然后backbone框架代码根据这个值，再来决定执行哪个基本代码块，所以一个代码块肯定要对应一个固定的状态机的值。

流程平坦化的弱点

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

1. Medium-level IL
2. SSA Form
3. Value-set analysis

确定Backbone块（确定骨架代码）

为了搞清楚流程平坦化的弱点，我们通过一个例子来详细的分析一下Backbone的代码，先看下我们的例子：

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

注意，这里我们就发现了一个关键的脆弱点：给定一个状态变量，记为state_var，我们发现每个Backbone代码块至少包含一次对这个变量的引用，如果遍历出所有引用到这个变量的代码块，那我们就可以得到所有的Backbone块，下面我们通过Binary Ninja的medium-level IL特性来搜集所有的块，这里我直接给出代码：

 这个算法可以找出所有对state_var进行过引用的Backbone块，包括程序的起始块（这个块是定义这个变量的块），起始块一般是这样的：

 从起始块我们很容易找到这个状态变量，然后通过def-use和use-def调用链，就能比较顺利的找到剩余的Backbone块了。

确定真实的程序逻辑块

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

 看代码可以知道，先是修改一下状态变量state_var的值，然后跳转到骨架代码。看上面的代码，我们基本可以确定，下次执行的真实代码块对应的case值是0xfcbce33c，对于那种有多个出口的真实块会被拆分成多个块，看起来会大致像下面这样：

 这里，原程序的一个条件语句其实被转换成了一个赋值语句，然后根据赋值的结果决定是不是要执行某个代码块，举个例子来说，比如原程序是这样的(^_^一起截图了，下面的是变化后的结果)：

 但是，我们的目标是找到所有的真实代码块，为了达到这个目标，我们需要利用LLVM Obfuscator的另一个关键弱点：所有逻辑基本块中，每个块至少包含一次state_var的定义动作（注意是定义不是引用），就跟起始块有点类似。

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

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

还原代码流程

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

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

目前我们还差一步，那就是我们目前还不知道对于一个给定的基本代码块，它的下一个执行节点是什么，也就是我们需要确定一个基本代码块执行完毕的时候，它把状态机的值改成了什么。为了完成这个目标，我们就要借助Binary Ninja的另一个很重要的特性，Value-Set分析，通过这个分析，可以知道某个寄存器或者内存位置里面的值是什么（译者注：相当于一个值跟踪系统，有点模拟执行的味道），有了这个，我们也可以确定出来最后状态机的值了。

前面提到过，一个基本代码块最后会把状态机state_var更新成一个固定值，现在我们就把这些值都找出来，这样整条链就串起来了：

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

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

 大致逻辑就是：

1. 先把%next_state设置成%false_branch
2. 如果%original_condition的结果为1， 在把%next_state设置成%true_branch
3. 最后再把state结果保存到%state变量

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

 现在版本的API还不太方便，但是结果还是准确的，把上面的东西综合起来，就形成了一个比较完整的脚本了：

 重构干净的二进制文件

目前来说，在Binary Ninja平台上patch程序还是比较麻烦的，但是好像也没有什么更好的替代品了。到现在为止，我们已经能够重构原始的控制流程了，剩下的工作就是根据掌握的信息来patch二进制代码了，让真实逻辑代码块之间直接相连，忽略掉Backbone代码。

构建代码原型

在我们目前获取的所有原始代码块里面，还包含了当时LLVM Obfuscator插入的一些框架代码，比如更新状态机的代码，这个代码现在对我们来说是垃圾代码了，因此需要清理掉这些代码了，正好用这些代码的空闲位置来插入一些我们的代码块连接指令，我整理了一下，下面这三种类型的指令都可以删掉了：

1. 跳转到Backbone分发器的代码(译者注：就是基本块最后的那种jump指令)
2. 更新state_var的指令
3. 用来计算state_var结果的相关指令

为了直观一点，继续给例子吧，下图中凡是标红的指令都是要删除掉的了，没用了：

 上面这些代码删除掉之后， 还能为我们后面修复流程的时候腾出来代码空间，一举两得。

修复控制流程

经过上面的步骤之后，在原始代码块里面腾出了一些空间，我们就利用这些空间来添加一些我们自己的修复指令，我们就用最简单的跳转指令来进行代码块之间的连接就好了，对于那种没有条件跳转的块，直接在最后接上 jmp next_block 就好了。

对于有条件分支的情况下，就需要确定是使用哪种jcc指令了，前面的小节里面我们知道，控制流平坦化pass会用true状态覆盖false状态，如果true分支成立。在实际的代码中，一般是使用cmovne这样的语句来操作的，于是这里取一个巧，我们就干脆不管这个时候的状态，而是依葫芦画瓢，复用它的状态结果，直接做一个简单的映射关系，cmovne直接就替换成 jne，这样既简单又准确，所以最后的结果大致就是这样的：

 有了上述的准备工作之后，下面的patch过程就简单了，对于每个基本代码块，按照下面的步骤来操作：

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

这里分别给出一个无条件跳转和条件跳转情况下的修复例子：

 到现在，整个控制流程就修复好了

最后清理

经过上述的修复之后，那些backbone代码和垃圾指令肯定是无法执行到了，但是在我们载入IDA分析的时候，还是会在视图中出现，还是在心理上造成干扰，所以这里为了看起来干净一些，把这些没用的指令全部都用nop给填充一下（前面我们已经得到了backbone代码块集合了）

成果展示

为了展示一下我们的成果，我们再把还原的结果在 Ninja中的结果贴一下，先看没有经过混淆的原始代码：

 下面是经过混淆过的代码：

 按照我们上述的修复流程修复一下，最终我们得到这样的结果：

 对比第一张图和第三张图，其实已经非常接近了，但是也有那么一点点不同（译者：但是都无伤大雅，HoHo~~）：

• 部分代码块被拆分开了
• 插入了一些连接代码块的jump指令

上面这两点算是一点小遗憾，而且不是那么好修复

插件出炉

上述的所有过程手工起来还是比较麻烦的，我们做成了插件，你可以在上找到源码，请注意这里Binary Ninja插件，直接clone下来就可以用了。

使用插件来还愿代码只需要2步：

1. 选择一条更新state_var的指令
2. 执行插件

LLVM代码混淆分析及逻辑还原

LLVM指令选择过程理解

指令选择(instruction selection)是将中间语言转换成汇编或机器代码的过程。在LLVM后端中具体表现为模式匹配，目标指令选择阶段会把后端td文件里面的DAG模式和selection DAG的节点相匹配，如果找到一个匹配，则匹配的节点会被有具体机器指令（或者伪指令）的节点代替。

1. LLVM IR基本概念

LLVM IR是一门中间语言，向上承接C、JAVA等高级语言，向下可以被翻译成面向具体目标的汇编语言，在编译器中的位置如下图所示。其一个主要优点是LLVM项目已经构建了多种针对LLVM IR的优化方法，因此很多高级语言在转换为LLVM IR后可以使用现有的基础设施进行优化。

 中间表示：LLVM IR可以以可读文本代码和二进制代码两种形式呈现。LLVM库中提供了对IR进行构造、组装和拆卸的接口。LLVM优化器也在IR上进行操作，并在IR上进行了大部分优化。

 后端：负责汇编码或机器码生成的步骤，将LLVM IR转换为特定机器架构的汇编代码或而二进制代码，包括寄存器分配、循环转换、窥视孔优化器、特定机器架构的优化和转换等步骤。

 编译器的三段式设计

根据上文所述，可以看出支持一种新的编程语言只需重新实现一个前端，支持一种新的目标架构只需重新实现一个后端，前端和后端连接枢纽就是LLVM IR。下面将主要介绍LLVM IR的基础表达指令：

从LLVM IR的指令可以看出，其表达抽象程度比汇编语言要高，例如add二元加法运算，所有的i8、i16、i32的加法都要用其进行表示，甚至vector的加法也要使用该运算符表示，因此具有一定抽象能力。但是要想运行到目标硬件需要将LLVM IR转换为基于目标的汇编指令，该过程主要有LLVM的后端完成，一个主要工作就是进行指令选择，为抽象的LLVM运算符、内存操作符等选择对应的目标硬件指令，其主要依赖于DAG图的模式匹配技术。

2. 指令选择的总体流程

指令选择的输入是LLVM IR，输出是使用无限寄存器组的指令序列，整个过程可以如下几个阶段：

本文将以一个简单的示例解释整个指令选择的过程，此函数的C程序如下，其实现了一个无符号的64-bit参数x和32-bit的参数y的乘积，返回值以32-bit无符号整形返回。

unsigned int MUL(unsigned long long int x, unsigned int y)

{

    return x * y;

}

2.1 创建DAG

指令选择的第一阶段是以LLVM IR作为输入创建DAG(有向无环图)，后序的每个阶段都是对这个DAG进行处理，指导发射称为指令序列。上述C程序对应的LLVM IR表示如下，可由Clang工具生成IR表示。

define dso_local i32 @MUL(i64 %x, i32 %y) local_unnamed_addr #0 {

entry:

  %0 = trunc i64 %x to i32

  %conv1 = mul i32 %0, %y

  ret i32 %conv1

}

一个Selection DAG表示一个basic block，每个basic block是一个没有分支的指令连续指令序列。上述MUl函数只有一个entry block,但是一般函数可能具有多个basic block，下面的hello函数则具有4个basic block：entry、if.then、if.else、return四个基本块，将每个基本块分别创建一个DAG。

define dso_local i32 @hello(i32 %x) local_unnamed_addr #0 {

entry:

  %cmp = icmp eq i32 %x, 100

  br i1 %cmp, label %if.then, label %if.else



if.then:                                          ; preds = %entry

  %call = tail call i32 bitcast (i32 (...)* @hello100 to i32 (i32)*)(i32 100) #2

  br label %return



if.else:                                          ; preds = %entry

  %call1 = tail call i32 bitcast (i32 (...)* @helloOther to i32 (i32)*)(i32 %x) #2

  br label %return



return:                                           ; preds = %if.else, %if.then

  %retval.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]

  ret i32 %retval.0

}

SelectionDAG 简单理解：

下面就是MUL函数的初始化SelectionDAG:

 初始化DAG

从上图中可以看出entry node在一个DAG的底部，蓝边代表chain操作数的传递过程，黑边代表数据的流动过程，上图的等效文本形式如下,可通过图的后序遍历得到：

t0: ch = EntryToken

        t2: i32,ch = CopyFromReg t0, Register:i32 %0

        t4: i32,ch = CopyFromReg t0, Register:i32 %1

      t7: i64 = build_pair t2, t4

    t8: i32 = truncate t7

    t6: i32,ch = CopyFromReg t0, Register:i32 %2

  t9: i32 = mul t8, t6

t11: ch,glue = CopyToReg t0, Register:i32 $x0, t9

t12: ch = RISCWISD::Ret t11, Register:i32 $x0, t11:1

2.2 优化

在指令选择过程中共有3次优化，第一次优化是在创建初始化DAG后，其余两次在合法化后，优化的目的主要是简化复杂的SelectionDAG。下图是第一次优化的结果，其变化是使用t13节点替代了t3和t4,优化器将64-bit数据的高32位删除，因为函数中乘法只要求返回32-bit整数，因此可以删除t3和t4。LLVM的第一次优化过程中只优化于目标独立的算子，例如add、sub、load等。LLVM后端开发者可以通过复写 PerformDAGCombine函数实现依赖于自定义目标的优化。

 第一阶段优化

2.3 合法化 Types 和 Operations

完成第一阶段优化后，可以看到t7节点产生64-bit的结果，但是后端RISCW目标硬件只支持32-bit数据，本阶段将解决这个问题。首先进行Types合法化，将所有的数据转化为目标机器支持的数据类型，一般需要进行数据的转换、提升、扩展，例如将i1->i32，i64->i32。下图中的DAG就是合法的，将t3和t7删除将保证DAG使用i32整数。

 合法化DAG

Operations合法化在第二次优化后，将DAG中的operations转换为目标支持的操作，例如DAG中有 rotl node 但是目标指令集中不支持，因此可以将其转换为bit shift 和 or两个操作进行。有3种方法进行是opertions合法化。第一种方法，complier将其展开为支持的操作。第二种可以将其数据类型进行提升。第三种通过手写C++编码定制器合法化过程。

2.5 指令选择

在指令选择前，大多数DAG的node是目标无关的operations，例如add、sub，同时也会有依赖于目标的操作节点例如RISCWISD::Ret，所以我们需要将这些抽象的节点映射到具体的依赖于目标机器的指令，LLVM中在指令选择阶段实现。其主要思想也比较简单，就是通过模式将node匹配到机器指令。指令的描述和模式由 LLVM 后端开发者进行编写，主要使用TableGen语法在td文件中进行描述。同时复杂的模式也可以通过直接C++编码实现。下图是指令选择完成后的DAG图，可以看出t9使用MUL代替了原来的mul,t12节点使用PseudoRET代替了RISCWISD::Ret。

 指令选择完DAG

指令选择过程就是DAG的模式匹配过程，模式的定义其主要在td文件中进行描述。当一个匹配找到后，将其DAG中的Node替换为具体的机器指令或伪指令。所以td文件中的Pattern的定义对于治病选择起到至关重要的作用。

每一个 Pattern 记录继承子 Pat class，其有两个参数，第一个参数DAG图中待匹配的模式，第二个参数是一个由机器指令组成DAG,当一个 Pattern 匹配后，将使用第二个参数替换第一个参数。示例如下：

class PatGprGpr<SDPatternOperator OpNode, RWInst Inst>

    : Pat<(OpNode GPR:$rs1, GPR:$rs2), (Inst GPR:$rs1, GPR:$rs2)>;

class PatGprSimm12<SDPatternOperator OpNode, RWInstI Inst>

    : Pat<(OpNode GPR:$rs1, simm12:$imm12), (Inst GPR:$rs1, simm12:$imm12)>;

PatGprGpr用于替换两个通用寄存器操作数的指令，Pattern定义方法如下,其中add为llvm ir中操作， ADD为依赖于机器的指令操作。

def : PatGprGpr<add, ADD>;

PatGprSimm12 替换一个操作数为通用寄存器,另一个操作数为立即数的指令。其中simm12是一个用于匹配12bit立即数的模式。

def : PatGprSimm12<add, ADDI>;

2.6 调度和格式化

在这个阶段是将指令选择完成的DAG转化为指令序列，该过程中可以设置符合目标硬件的调度策略。如下是MUL函数的指令序列，在此序列中仍然是使用虚拟寄存器表示，后续会有寄存器分配阶段来完成，下面序列中有部分寄存器活性信息。

bb.0.entry:

  liveins: $x0, $x2

  %2:gpr = COPY $x2

  %0:gpr = COPY $x0

  %3:gpr = MUL %0:gpr, %2:gpr

  $x0 = COPY %3:gpr

  PseudoRET implicit $x0

3 总结

上文主要讲述了LLVM IR的语法基础及将IR的抽象表达指令转换到底层的汇编指令。LLVM IR作为编译器的中间组件，起到了承上启下的作用，给上层开发新语言提供了接口，也给下层支持新硬件提供了开发框架,同时LLVM提供了多种优化模块及数据分析模块帮助编译器开发者实现优化，极大的降低了编译器开发的门槛。同时文中也详细阐述了LLVM指令的选择过程，展示如何将ISD的SDNode转换为汇编指令操作，帮助编译器开发者理解LLVM后端的工作机制，以方便开发者添加自己的芯片后端。

在AI芯片行业蓬勃发展的当下，不但要求有高水准的芯片设计能力和高水平的芯片制造能力，同时也需要更强的软件能力，拥有一个优化水平高的编译器是一款成功芯片的关键，它可以在相同成本的情况获得更快更好的AI服务，因此编译器的研究在当前的芯片行业变得尤为重要。

参考文献

参考文献链接

https://mp.weixin.qq.com/s/S-5jCiaG05dY8f5sK_kdcQ

https://mp.weixin.qq.com/s/TbnMt8etym0VTZLYIYylkw

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 用jacoco统计JAVA项目测试代码覆盖率
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• GDB调试之源代码查看与管理(六)
• 写代码时如何合理的画图表达逻辑结构
• 十行python代码实现文件去重，去除重复文件的脚本
• [代码随想录] 第四天
• idea 中java代码修改后运行代码不生效
• 一行代码创建网页（html）
• 如何在SAP GUI中快速执行新的事务代码

指令 代码 LLVM指令 代码llvm 指令llvm_ir llvm 04 代码生成codegen代码llvm 函数 代码llvm 02 概念 代码 基础llvm 代码生成 代码llvm tvm 编译器 示例 代码llvm 代码生成 杂谈 代码llvm 利器 指令 代码 代码生成 技术应用 指令 代码