程序分析之中间表示（Intermediate Representation）

静态分析

程序静态分析（Program Static Analysis）是指在不运行代码的方式下，通过词法分析、语法分析、控制流、数据流分析等技术对程序代码进行扫描，验证代码是否满足规范性、安全性、可靠性、可维护性等指标的一种代码分析技术。静态分析技术向模拟执行的技术发展以能够发现更多传统意义上动态测试才能发现的缺陷，从而提高开发效率和软件质量。本文介绍部分在静态代码分析中使用的中间表示的概念，主要包括抽象语法树、三地址码、SSA形式，及CFG和RTL等概念

---

中间表示（Intermediate Representation）

抽象语法树（Abstract Syntax Tree，AST）

在介绍AST时，我们用一个简单的例子：x = 3 + 4 * y 这个表达式作为例子来进行介绍：

• AST：
  • 是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，之所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节
  • 抽象语法树，其实就是用树状结构表示语法结构，也没有说必须是什么形式，只要能忠实地反映出源码的格式即可

当然，一般资料中在进行介绍时，都是以操作符作为根节点，画个树状的结构来表示，这里咱们也简单画一个意思一下，如下图：

三地址码（Three Address Code，TAC/3AC）

三地址码是一种有意思的中间表示，当前也是编译原理中用得最火的。这里我给大家梳理一种我的理解上的概念，那就是，刨掉赋值操作，最多只有一个操作符，先看下面的几个例子

• x = y bop z
• x = uop y
• x = y
• goto L

如上，第一个，除了赋值之外，只有 bop 一个操作符，第二个，只有 uop 一个操作符，第三个没有操作符，同时，操作符的概念可以进一步扩展到函数调用等，例如 call fun(a, b, c, d)，虽然有四个操作数，但是我们认为 call fun只是一个操作符。

如上面 x = 3 + 4 * y 转换为三地址码如下：

t1 = 4
t2 = y
t3 = t1 * t2
t4 = 3
t5 = t4 + t3
x = t5

当然，有些形式下会减少临时变量的使用，尽量复用原来的变量或者常量，形成的三地址码如下：

t1 = 4 * y
x = 3 + t1

三地址码最初只是处理类似于 x = y bop z 这种形式的语句，而提出来的“三个操作数”的意思，随着语法的扩充，也并不是完全就是“三地址”。

AST和三地址码对比

以下介绍几点AST和三地址码的对比特点：

• 源码相关性

  AST中的节点与输入源代码中的各个语法元素一一对应，忠实地体现了源码的内容和语法特性，因此AST与源码强相关；三地址码就是从AST进一步抽象的一种中间表示，更接近机器语言，可以认为和语言无关，是连接前后端的一种中间表示

• 变化频繁程度

  因为AST需要忠实地体现出源代码的语法元素，因此在对应的编程语言升级时，对应的AST必然会跟着发生变化，比如Java，从Java7变成Java8，增加了大量的Lambda表达式、函数引用等特性，所以AST节点也需要增加这些语法节点，所以AST的版本需要随着语言发布而不断变化。

  但是三地址码是一种经过处理的语言无关的中间表示，即使源代码结构变化，AST结构变化，但是转换后的三地址码是稳定的，不会经常发生变化，构造在三地址码上面的分析算法就相对比较稳定

• 结构

  AST体现源码的结构，需要匹配源码的语法，因此一般结构比较复杂，而三地址经过处理，一般比较紧凑，简单。例如，Java中，对 for，while，do while 有多种不同的循环方式，但是，其实内容大同小异，但是在AST层面，就是不一样的，但是转换为三地址码后，所表达的控制语义是完全一样的

• 表达信息

  AST表达了源码的信息，因此可以在AST上做程序结构的检查，但是三地址码中，可以更好地包含了程序控制流和数据流信息，能进行更深层次的流敏感分析，过程间分析，上下文敏感分析和对象敏感分析等等，从而实现各种更高难度的程序漏洞检查。

  同时，三地址码因为是语言无关的， 所以在部分静态代码分析工具实现时，会对不同的三地址码，实现一个分析引擎，只是通过开发不同语言的规则，实现对不同语言的能力的覆盖，而AST是无法做到这一点的。因此，三地址码也被认为是静态代码分析的基础

**静态单赋值形式**（Static Single Assignment Form，SSA）

文件地址

SSA概念及分类

• SSA概念

  在编译器的设计中，静态单赋值形式通常简写为SSA form或是SSA，是中介码的特性，每个变数仅被赋值一次。在原始的IR中，已存在的变数可被分割成许多不同的版本，在许多教科书当中通常会将旧的变数名称加上一个下标而成为新的变数名称，以至于标明每个变数及其不同版本。在SSA中，UD链（use-define chain，赋值代表define，使用变数代表use）是非常明确，而且每个仅包含单一元素

  以下面的代码为例：

  public void test(int x) {
      int y = 0;
      if (x > 3) {
          y = x + 4;
      } else {
          y = 10;
      }
      int z = y + 3;
      System.out.println(z);
  }

  以下图为例，左图是原始代码，里面有分支， y 变量在不同路径中有不同赋值，最后打印 z的值。右图是等价的 SSA 形式，y 变量在两个分支中被改写为 y2, y3，在控制流交汇处插入φ函数，合并了来自不同边的 y2, y3值, 赋给 y4 最后z由y4生成

  

  其实要讲SSA形式，就不能离开对DU Chain（Define-Use Chain）和UD Chain（Use-Define Chain）的介绍，因为很多地方对SSA的概念的介绍，都是从DU Chain和UD Chain引起的。Use-Define Chain 是一个数据结构，包含一个Define变量，以及它的全部Use的集合。相对的，Define-Use Chain 包含一个Use变量，以及它的全部 Define的集合。

  另外一种SSA的描述，就是在 Define-Use Chain中，每一个Use变量，只会有一个Define，例如，在前面例子中，z = y + 3 中，因为此时 y可能在两个分支中赋值，因此，对于变量 z = y + 3 中，y 的Use来说，有两个 Define，但是，通过更改为 SSA形式，z = y + 3 中，y只有一个 Define，那就是 y4。因此，通过将三地址码转为SSA形式，可以很大程度上，简化Use-Define Chain和Define-Use Chain。

• SSA分类

  SSA 有几种不同分类（主要是最小SSA、剪枝SSA、半剪枝SSA，另外两种严格SSA和最大SSA，大部分资料上都没有看到，只是在少部分资料中有见到，所以简单提一下）

  • 最小SSA

    最小SSA有以下特点：同一原始名字的两个不同定义的路径汇合处都插入一个φ函数。这样得到符合两大特征的且拥有最少φ函数数量的 SSA 形式。但是这里的最小不包含优化效果，比如死代码消除。如上面图2.1节，就是一个最小SSA形式

  • 剪枝SSA

    如果变量在基本块的入口处不是活跃 (live) 的，就不必插入φ函数。一种方法是在插入 φ函数的时候计算活跃变量分析。另一种剪枝方式是在最小SSA上做死代码消除，删掉多余的φ函数。如下面的例子，y在分支执行完后，在最后的BB块中不再使用，y已经不再活跃，此时没必要在这个节点添加φ函数，如下面右图红色标出来的位置（说明：虽然不是剪枝SSA，但是仍然是最小SSA）

    

  • 半剪枝SSA

    鉴于剪枝 SSA 的成本，可以稍微折衷一点。插入φ函数前先去掉非跨越基本块的变量名。这样既减少了名字空间也没有计算活跃变量集的开销。如下图所示，y变量除了Define，并没有Use，所以，变量y其实可以去掉，如下右图

    

  • 严格SSA

    如果一个 SSA中，每个Use被其Define支配（如果从程序入口到一个结点 A 的所有路径，都先经过结点B，则称A被B支配），那么称为严格 SSA（实际上，在强类型语言中，这种情况比较少，因为没有定义，就不允许使用，在少数动态类型语言中，允许没有定义就可以使用的才有这类问题）

  • 最大SSA

    最大SSA是相对最小SSA而言的，就是在每个汇合点处为每个变量放置一个φ函数。很显然，这种方法会导致SSA的使用效率最差，用户体验也很差，我估计谁生成的SSA是这样的形式，会被使用的人打死的

SSA形式和普通三地址码对比

其实对比SSA形式和普通的三地址码形式，只有一个区别，那就是，SSA形式，对于每个Use，只会有一个Define。两者在一定程度上，还是非常类似的。那么主要对比在于两种形式的各自的优缺点：

• SSA形式相对于三地址码，会引入大量的额外的临时变量，同时需要插入φ函数，还需要维护这些临时变量到原始变量的映射关系（当然，仁者见仁，智者见智，也有资料觉得这些额外的临时变量可以忽略，驳斥这个观点为谬论，不过的确还是有其不舒服的地方的）
• SSA形式的优势在于，SSA形式简化了DU Chain和UD chain，构建了一种稀疏结构，可以简化数据流分析（一般基于三地址码，需要基于传统的数据流分析来进行分析，称为dense分析，基于SSA形式，可以构造值依赖关系，基于值流分析，也称为sparse分析，同时，SSA形式也隐含了一定的程序流信息）
• SSA形式相比于普通三地址码，可以优化常量传播、值依赖分析、死代码、重复代码删除等

控制流图（Control Flow Graph，CFG）

也叫控制流程图，是一个过程或程序的抽象表现，是用在编译器中的一个抽象数据结构，由编译器在内部维护，代表了一个程序执行过程中会遍历到的所有路径。它用图的形式表示一个过程内所有基本块执行的可能流向, 也能反映一个过程的实时执行过程

1. 基本块（Basic Block）

   • 特点：
     • 单入口、单出口、每个块内的语句都是按顺序执行的，不能有分支和跳转
     • 只能从第一条语句进入该基本块，不能够以某种方式跳入该基本块的中间
     • 基本块内的语句在执行时必须从最后一条语句离开，不能够执行到一半跳转到其它的基本块

2. CFG

   CFG是一个由基本块组成的有向图，每个节点都是一个基本块。如果程序的执行路径可能从一个基本块$B_1$进入另一个基本块**$B_2$，$B_1$有一条指向$ B_2 $**的边

   其中：

   $N:$表示所有基本块节点的集合

   $E:$表示所有边的集合

   $n_0:$表示首节点

   CFG具有如下的两条性质：

   • CFG 必然有唯一的一个入口点
   • 首节点必然支配CFG中其他的所有节点（即从首节点到CFG上其他任何一个节点都有一条路可以连通）

寄存器传输语言（Register Transfer Language，RFL）

又译为暂存器转换语言、寄存器转换语言，一种中间语言，使用于编译器中。与汇编语言很接近。寄存器传递语言被用于描述一个架构中寄存器传输级上的数据流。 在学术论文和教科书中，寄存器传递语言被认为是一种与架构无关的汇编语言。GCC的中间语言，也被称为寄存器传递语言，风格类似于LISP。GCC的前端（front-end）会先将编程语言转译成RTL，之后再利用后端（back-end）转化成机器代码

以下一些文章用到相关技术：

• Vandal
• Securify2
• MadMax
• Gigahorse
• Ethainter

原文链接