静态程序分析，就是在不执行代码的情况下，对程序进行分析。在程序分析中，根据分析的输入可以分为两种：基于源码的程序分析和基于二进制的程序分析。但是不管是基于源码还是基于二进制程序，我们都没有办法直接对他们进行分析：源码是一种文本文件，是非结构化的数据，不方便分析，而二进制则是0和1组成的数据，也不方便直接分析，因此，需要将源码和二进制程序转换成某种表示形式，方便进行分析。

我们在执行静态程序分析时，有很多要求，例如在 静态代码分析工具评估指标及方法 这篇博客中，介绍了静态程序分析的部分评估内容，涉及到 性能、检查规模、误报和漏报 等评估指标，都跟我们分析的输入有关。本文对我们执行静态程序分析的中间表示进行简单的介绍。

因为我们更侧重工程实现，所以本文主要从目前的一些典型的中间表示入手开始，强化实现，相关的理论上面的概念会顺便提一下，以加深理解（本文主要基于 C/C++ 进行介绍）。

1. 业界典型工具的中间表示介绍

首先，我们介绍几种典型的中间表示，以引出我们的分析。前面介绍到：静态程序分析有基于源码的程序分析和基于二进制的程序分析。相应的生成中间表示的方法不同：

• 基于源码的程序分析，主要应用到了编译原理相关的技术，是正向的 IR 的生成，因此离不开编译器相关的技术介绍。我们以 llvm 和 gcc 中的中间表示引入这部分的介绍。
• 基于二进制的程序分析，主要需要对二进制程序进行反汇编，这部分不是我们这篇文章的重点，但是会进行简单介绍。

1.1 llvm编译器及中间表示介绍

事实上，llvm 是目前应用最火的一款编译器，我曾经跟同事调侃：llvm 编译器养活了中国大部分研究编译器和程序分析的人，包括学术界和产业界。基于 clang + llvm 的工具链，可以比较快速地实现静态代码分析工具。clang + llvm 工具链最主要的优点：license 协议友好、API 设计良好，方便集成、模块化好。clang + llvm 主要形成的中间表示如下：

图1.1 clang + llvm 主要的文件

应用最多的就是上面的 clang AST 和 llvm ir。在博客 Clang编译步骤及命令梳理 中，已经详细介绍了 clang 的编译步骤相关的内容，这里就不再详细介绍两种中间表示的生成方式了，这里结合实际的中间表示，进行一下介绍。

在这部分的介绍中，我们采用如下的源码为例进行介绍：

#include <stdio.h>

int main() {
    int x = 4;
    printf("hello %d\n", x);
    return 0;
}

(1) 抽象语法树

抽象语法树（AST），是以树状结构表示的一种形式，因此结构化程度比较高，表达的信息比较丰富，可以比较完整地表达程序的结构，因此，有些资料将 AST称为 结构化中间表示（structural IR）；这种形式尽可能地保留源码的信息，因此在部分的文章中，将该形式的中间表示称为 High Level IR，如前面博客中打印出来的 clang AST 如下：

图1.2 clang AST举例

如上面的表示，我们可以看到 AST 中至少包含如下的信息：

• 节点的类型信息
• 节点之间的父子关系
• 节点的引用信息（如 DeclRefExpr，会和 Decl 变量声明建立关联）
• 节点在源码中的位置信息

我们从 AST 可以非常方便地知道源码是什么样子，这也就是 AST 被称为 High Level IR 的原因。

(2) 三地址码

下面贴一个 llvm ir（保留了变量名等信息，但是没有执行 mem2reg）:

@.str = private unnamed_addr constant [10 x i8] c"hello %d\0A\00", align 1

; Function Attrs: noinline nounwind uwtable
define dso_local i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  %x = alloca i32, align 4
  store i32 0, i32* %retval, align 4
  store i32 4, i32* %x, align 4
  %0 = load i32, i32* %x, align 4
  %call = call i32 (i8*, ...) @printf(i8* noundef getelementptr inbounds ([10 x i8], [10 x i8]* @.str, i64 0, i64 0), i32 noundef %0)
  ret i32 0
}

上面贴出来了一个全局变量，外加一个函数的实现。我们可以看到：对于每个函数，都是由不同的 block 组合而成的，每个 block 都有一个名字（如上面的 entry）和一系列的指令组成，每个 block 中的指令都是线性的关系，这种中间表示也叫做 线性中间表示（Linear IR）。

如果想了解更多的关于 AST 和 三地址码的介绍（包括 SSA 形式），可以参考博客：静态代码分析中间表示基本概念

1.2 gcc编译器及Gimple介绍

还是如上面的例子，生成 gcc 的 gimple 形式，执行命令如下：

gcc -fdump-tree-gimple -c test.c

生成的 gimple 形式如下：

int main ()
{
  int D.2348;

  {
    int x;

    x = 4;
    printf ("hello %d\n", x);
    D.2348 = 0;
    return D.2348;
  }
  D.2348 = 0;
  return D.2348;
}

gcc 的 gimple 是 SSA 形式的，如果理解了 三地址码 和 SSA 的概念，理解 gimple 并不复杂。 

1.3 llvm 和 gcc 三种中间表示对比

下面我们对比一下这三种中间表示：

• Clang AST：是一种比较 High Level 的 IR 的一种典型的表示形式，可以比较完备地体现源码格式，可以针对源码的代码风格进行检查，同时，也可以基于该表示形式生成 CFG 后，做更深的数据流分析（比如 Clang Static Analyzer），我们通常讲的 AST，都是类似于 Clang AST，或者功能上接近的树状表达形式。一般在使用时，结合 Token 和 符号表 完成更进一步的分析。
• GCC Gimple：这一层次的中间表示，是我认为做静态程序分析比较恰当的一个层次，因为生成了三地址码形式，但是没有形成过多的表示，和源码相对来说还比较接近。
• LLVM BitCode：这个层次的中间表示，已经和汇编比较接近，比如里面的 Load 和 Store 等操作，都是汇编里面才有的，更适合做编译器优化的研究、或者本身开发的编程语言采用 LLVM 作为后端时使用。虽然可以在这个层次做静态程序分析，但是如果开发专门的用于漏洞检查的静态程序分析工具，可能不如 GCC Gimple 这一层类似的中间表示合适。

2. 数据流分析到底适合在哪种中间表示上进行分析？

从静态代码分析工具的实现目标来看：主要有代码风格检查和信息安全检查等。从检查的方法上，主要有面向程序结构的检查和基于数据流的检查两大类。不同的检查适合不同的中间表示。一般我们认为：

• 面向程序结构的检查，一定是基于 AST 进行的检查，有时候需要结合 Token 和 符号表 一起检查；
• 基于数据流的检查，一般都是在三地址码（或SSA）形式的中间表示上面分析，也可以在 AST 上面进行分析。

那么，数据流分析，到底适合在哪种中间表示上进行分析呢？

强调：下面的针对这个问题的回答，主要是个人看法，目前还在进行探索，大家可以参考，不必多认可！

针对这个问题，我介绍下面的几点：

• 面向学术界，如果有新的或者好的数据流分析相关的算法和探索，适合三地址码，并且可以基于算法类型，选择普通三地址码或者SSA形式；
• AST可以完整表达源码信息，包含的信息非常丰富，因此某种语言的不同版本之间，AST差距比较大，例如 java7 和 java8，因此，如果要在 AST 上面实现数据流分析，会需要兼容非常多的语法特性，并且会导致升级困难；
• 三地址码可以对不同的语法进行兼容，因此有一定的稳定性，从而使数据流分析算法比较稳定，在语言版本升级时，不需要做特别大的适配工作；
• SSA形式的中间表示，可以执行稀疏的数据流分析，相比于普通三地址码，具有一定的优势；很多在 llvm bc 上执行的分析，都充分利用了该特性；
• llvm bc 相对于普通的三地址码，我感觉更接近底层，比如 汇编。我们对于 gcc 的 gimple 和 llvm 的 bc，可以看到这一点。事实上，llvm bc 相对于普通的三地址码（或者 SSA 形式），例如 gcc 的 gimple，完整的生成的中间表示，最终变量的数量是几十倍的增加。
• llvm bc 并不适合商用级别的静态代码分析工具的开发，我们都清楚：数据流分析的性能（包括时间和内存消耗），和变量的数量有直接关系，在 IFDS 算法中，和变量的三次方成正比，因此个人认为 llvm bc 更适合学术圈来验证算法；
• 从已有的商用工具来看，coverity 是基于 AST 进行分析的（Scalable and Incremental Software Bug Detection），fortify 是针对不同的语言，生成一种统一的AST（不是三地址码形式，但是对部分 AST 节点进行了合并，例如只保留了 while 循环，for 循环也转换成了 while 循环，可以从 nst 文件确认）；
• coverity 和 fortify 这样的头部静态程序分析工具，都是在 AST 上面执行的数据流分析；
  
• 个人认可的观点：① 面向工业应用，或者期望商用的产品，可以自己生成统一的 AST 来进行数据流分析，或生成类似于 gcc gimple 形式及更高层次的三地址码进行分析，不适合使用类似于 llvm bc 这样的偏底层的中间表示；② 面向学术界，可以考虑 llvm bc 这样的中间表示，已经做了极大的简化，可以比较快出结果。

3. 对中间表示的进一步抽象

事实上，输入的是中间表示，但是正常在执行分析时，不会直接在中间表示上面进行分析的，而是在中间表示上进行各种抽象，从而简化我们的分析。下面介绍几种典型的抽象数据结构，如下图所示：

图3.1 部分中间表示扩展

如上图：

• 最底层是输入的中间表示，通常如果有需要，可以进行序列化处理，然后直接读入，例如 clang 可以 dump AST，llvm 的 bc 文件就是一种 SSA 形式的中间表示；
• 中间的一层是在中间表示上生成的数据表示，一般基于中间表示执行数据流分析时，都需要生成这部分结构；
• 最上面的一层，是当前比较典型的两种比较高级的抽象形式。对 CPG 相关的概念，最初是在 joern 工具中引入的，综合了各种代码表示，并放到图数据库中，对 SVFG 相关概念，在 SVF 中引入的，并且，基于该框架，实现了一种基于 SVFG 的 MemoryLeak 的检查工具。

实际上，上面的各种图的构建，也需要大量的数据结构和相关的算法实现，并且有可能还需要执行复杂的静态代码分析。例如 SVFG 的构造，需要执行全程序的指针分析。但是如果构造出来这些抽象表示之后，可以更加方便我们进行后续的分析，这个转换就是有价值的。

4. 二进制中间表示

在第1节中，我们就提到了二进制的中间表示，并且在那一节我们重点介绍了由源码来正向生成的中间表示。这一部分，我们介绍二进制的中间表示。

我们从编译器执行的后端顺序是：中间表示 -> 汇编 -> 二进制程序。这里，我们提一点就是一般汇编结束后（以linux上的编译为例），会生成 .o 文件，.o 链接生成 .out 可执行文件，虽然这两个是不同的阶段产物，但是都是 ELF 文件，可以通过相同的工具进行解析。

那么我们在分析二进制文件时，也需要找到合适的一种表示来分析二进制文件。我们使用工具可以非常方便地从二进制的 ELF 文件，生成 汇编代码，或者直接查看原始的机器代码，但是 汇编代码 和 机器代码 并不方便分析，比如 机器代码，都是 0 和 1 组成的数据，都没办法分析，汇编代码 形式非常多，如果针对每一种 汇编代码 都实现一套分析算法，那么会非常多，所以将二进制文件生成某种中间表示，就是一种很好的选择。

下面介绍几种典型的在二进制分析中会使用的中间表示：

• VEX IR：在二进制程序分析中应用广泛，比如 angr 就是选用 VEX IR 作为中间表示的；
• REIL（Reverse Engineering Intermediate Language）：可以参考：https://github.com/Cr4sh/openreil
• LLVM IR：这种 IR 是目前应用非常广泛的一种中间表示形式，可以直接利用 LLVM IR 自身提供的一些静态代码分析能力，微软开源了一个工具 llvm-mctoll  可以用来将二进制文件转成 LLVM IR。

5. 总结

本文介绍了静态程序分析中的中间表示，重点放在了基于源码分析使用的中间表示部分。也对基于不同的中间表示的基础上做的抽象进行介绍。