中间表示

中间表示IR

讲讲IR（Intermediate Representation），中间表示

编译器与静态分析器

编译器Compilers负责将源代码（Source code） 转换为机器代码（Machine Code），大致流程框架如下：

• 词法分析器（Scanner），结合正则表达式，通过词法分析（Lexical Analysis）将 source code 翻译为 token。
• 语法分析器（Parser），结合上下文无关文法（Context-Free Grammar），通过语法分析（Syntax Analysis），将 token 解析为抽象语法树（Abstract Syntax Tree, AST）
• 语义分析器（Type Checker），结合属性文法（Attribute Grammar），通过语义分析（Semantic Analysis），将 AST 解析为 decorated AST
• Translator，将 decorated AST 翻译为生成三地址码这样的中间表示形式（Intermediate Representation, IR），并基于 IR 做静态分析（例如代码优化这样的工作）。
• Code Generator，将 IR 转换为机器代码。

流程图如下：

静态分析得先确保这是一份合格的代码，然后再进行分析

分析代码合不合格，这是 trivial 的事情，由前面的各种分析器去做就行了，我们要做的是 non-trivial 的事情，所以是基于IR来分析

AST与IR

为什么在静态分析的时候，使用 IR 而非 AST ？

我们可以对比一下：

我们可以知道：

• AST 是 high-level 且接近语法结构的，而 IR 是 low-level 且接近机器代码的
• AST 是依赖于编程语言的，IR 通常是独立于编程语言的：三地址码会被分析器重点关注，因为可以将各种前端语言统一翻译成同一种 IR 再加以优化
• AST 适合快速类型检查，IR 的结构更加紧凑和统一：在 AST 中包含了很多非终结符所占用的结点（body, assign 等），而 IR 中不会需要到这些信息
• AST 缺少控制流信息，IR 包含了控制流信息：AST 中只是有结点表明了这是一个 do-while 结构，但是无法看出控制流信息；而 IR 中的 goto 等信息可以轻易看出控制流

综上所述，不难看出 IR 更适合作为静态分析的基础

三地址码3AC

三地址码（3-Address Code）通常没有统一的格式。在每个指令的右边至多有一个操作符，例如如下式子：

a + b + 3

转化为三地址码，这一步一般会引入临时变量：

t1 = a + b
t2 = t1 + 3

三地址码为什么叫做三地址码，因为每条 3AC 至多有三个地址。而一个「地址」可以是：

• 名称 Name: a, b
• 常量 Constant: 3
• 编译器生成的临时变量 Compiler-generated Temporary: t1, t2

下面是一些常见的 3AC ：

• x = y bop z：双目运算并赋值，bop = binary operator
• x = uop z：单目运算并赋值，uop = unary operator
• x = y：直接赋值
• goto L：无条件跳转，L = label
• if x goto L：条件跳转
• if x rop y goto L：包含了关系运算的条件跳转，rop = relational operator

其实到这里会发现和汇编语言还是有些相似之处😆

Soot

Soot 是 Java 的静态分析框架，其中的 IR 叫做 Jimple，这个jimple就是基于三地址码的形式

比如有如下java代码：

public class LoopDemo {
    public int testLoop() {
        int sum = 0;
        // 标准的 for 循环：初始化; 条件; 更新
        for (int i = 0; i < 10; i++) {
            sum = sum + i;
        }
        return sum;
    }
}

那么转化为Jimple后（伪代码）

public int testLoop()
{
    LoopDemo r0;      // 'this' 指针
    int sum, i;       // 局部变量声明

    r0 := @this: LoopDemo;  // 获取 this 引用

    sum = 0;          // [初始化 sum]
    i = 0;            // [for 初始化]: i = 0

 label1:             
    if i >= 10 goto label2;  
  
    sum = sum + i;    
    i = i + 1;        
    goto label1;      

 label2:              
    return sum;       
}

这里只举了一个for循环的例子，还有很多的场景，可以自行去了解

Static Single Assignment

静态单赋值（SSA），就是让每次对变量x赋值都重新使用一个新的变量xi，并在后续使用中选择最新的变量

3AC        | SSA
p = a + b    p1 = a + b
q = p - c    q1 = p1 - c
p = q * d    p2 = q1 * d
q = p + q    q2 = p2 + q1

但是在这个情况下，会因为不同控制流汇入到一个块，导致多个变量备选的问题：

这里解决的办法就是使用一个合并操作符$\phi$（phi-function），根据控制流的信息确定使用哪个变量

为什么要用 SSA :

• 控制流信息间接地集成到了独特变量名中
  • 如果有些对控制流不敏感的简化分析，就可以借助于 SSA
• 定义与使用是显式的
  • 更有效率的数据存取与传播，有些优化在基于 SSA 时效果更好（例如条件常量传播，全局变量编号等）

为什么不用 SSA :

• SSA 会引入过多的变量和 phi 函数
• 在转换成机器代码时会引入低效率的问题

CodeQL

上面提到：

”如果有些对控制流不敏感的简化分析，就可以借助于 SSA“

正因为CodeQL需要污点追踪这个重要的功能，所以它选择使用SSA来简化分析流程

CodeQL和soot的逻辑很不一样，它将代码解析为一个存储AST结构的数据库，我们通过编写查询语句，在这个数据库中查询来进行代码审计，而当我们在 CodeQL 中使用 DataFlow 或 TaintTracking 库时，CodeQL 会在内存中通过逻辑推导构建出 SSA 形式的数据流图

所以我们可以理解CodeQL的IR就是它的database以及SSA图

控制流分析

控制流分析（Control Flow Analysis）通常指的是构建控制流图（Control Flow Graph, CFG），并以 CFG 作为基础结构进行静态分析的过程

CFG 的一个结点可以是一条单独的 3AC，但是更常见的是一个基本块（Basic Block）

Basic Blocks

基本块就是一段连续 3AC，满足两个特征：

• 只能从块的第一条指令进入
• 只能从块的最后一条指令离开

如何构建一个基本块:

• 输入：程序 P 的一系列 3AC
• 输出：程序 P 的基本块
• 方法
  1. 决定 P 的 leaders
     • P 的第一条指令就是一个 leader
     • 跳转的目标指令是一个 leader
     • 跳转指令的后一条指令，也是一个 leader
  2. 构建 P 的基本块
     • 一个基本块就是一个 leader 及其后续直到下一个 leader 前的所有指令

利用上面的规则，我们可以很快的构建出基本块，比如这个例子：

Control Flow Graph

上面讲了控制流图构建的第一步，构建基本块

而除了基本块，CFG 中还会有块到块的边。块 A 和块 B 之间有一条边，只有这两种情况：

• A 的末尾有一条指向了 B 开头的跳转指令。
• A 的末尾紧接着 B 的开头，且 A 的末尾不是一条无条件跳转指令

注意到每个基本块和开头指令的标号唯一对应，因此很自然地，我们可以将跳转指令的目标改为基本块的标号而非指令标号

此时我们就可以了解一些概念：

• 若 A -> B，则我们说 A 是 B 的前驱（predecessor），B 是 A 的后继（successor）
• 除了构建好的基本块，我们还会额外添加两个结点，「入口（Entry）」和「出口（Exit）」
  • 这两个结点不对应任何 IR
  • 入口有一条边指向 IR 中的第一条指令
  • 如果一个基本块的最后一条指令会让程序离开这段 IR，那么这个基本块就会有一条边指向出口。

这样，我们就完成了一个控制流图的构建：

总结

至此，我们了解了：

• 编译器与静态分析器的关系
• 了解 3AC 和其通常形式
• 如何基于 IR 构建基本块
• 如何基于基本块构建控制流图