Intermediate Representation

编译器和静态分析器

• Compiler

  编译器将高级编程语言代码（Source Code）转换为机器码（Machine Code），不仅仅是转换，在转换过程中还要报错。主体框架如下图：

  首先通过Scanner做词法分析（使用形式化方法，例如使用正则表达式），没有通过词法分析会报错，如果通过了词法分析，每个单词会生成tokens,转下一步。

  之后，Parser使用Tokens做语法分析（使用上下文无关文法），如果通过了语法分析则生成AST（抽象语法树）。

  然后用Type Checker做语义分析（主要用Attribute Grammer），对于编译器来讲，只能做类型检查（例如一个float number不能赋给一个int类型的值）,如果通过了语义分析会生成Decorated AST。

  词法，语法，语义都通过后，如果编译器还需要做后续的优化，那么需要通过转换器Translator转换成一种中间表示形式（IR，通常指3AC），对3AC做完优化后生成机器码（Machine Code）交由机器执行。如果想用静态分析器查错或者查漏洞，一般是在3AC的基础上。

  IR之前的部分可以统称为前端，IR之后的部分可以称为后端。

AST和IR

• 为什么程序分析主要使用IR而不使用AST（也可做简单的静态分析）

  如下图：

  左为AST，右为3AC，从这个例子可以比较出AST和3AC的几点不同：

  AST：

  1. 高级别的，能够体现（接近）语法结构
  2. 依赖于不同的语言
  3. 适合于做类型检查
  4. 缺乏控制流信息

  IR：

  1. 低级别的，比较接近机器码
  2. 不依赖于具体语言
  3. 统一且简洁（没有冗余信息）
  4. 包含控制流信息
  5. 通常被作为静态分析的基础

IR: Three Address Code（3AC）

• 3-Address Code(3AC)

  3AC并没有一个标准的形式化的定义。通常，3AC的右侧至多有一个运算符，3AC的转换需要引入临时变量，如下图：

• 为什么叫3-address？

  地址并不是正常的编程语言的地址，只是一种概念上的，地址主要有3种形式，分别为： Name(变量名)：如上图中的a,b；Constant(常量)：如上图中的3；Compiler-generated temporary(编译器生成的临时变量)：如上图中的t1,t2。（注：每个3AC至多包含3个地址，每种指令都有对应的3AC）

• 一些常见的3AC形式

  1. x = y bop z
  2. x = uop y
  3. x = y
  4. goto L
  5. if x goto L
  6. if x rop y goto L 具体解释如下图：

真实静态分析器中的3AC

• Soot and its IR：Jimple

  Soot：Most popular static analysis framework for Java

  Soot的github

  Soot的tutorials

  Soot’s IR is Jimple：typed 3-address code

• Jimple的例子

  Do-While Loop:

  Method Call:

  拓展：JVM里主要的四种方法调用

  invokespecial：call constructor，call superclass methods, call private methods

  invokevirtual：instance methods call (virtual dispatch)

  invorkeinterface：cannot optimization，checking interface implementation

  invokestatic：call static methods

  其他概念 Java 7：invokedynamic -> Java static typing，dynamic language runs on JVM

  method signature：class name：return type method name(parameter1 type，parameter2 type, …)

  Class：

Static Single Assignment(SSA)

• SSA中所有变量都要赋予不同的名称 （All assignments in SSA are to variables with distinct names）

  1. 为每个定义重新命名（Give each definition a fresh name）
  2. 将新名称传播给后续操作使用（Propagate fresh name to subsequent uses）
  3. 每个变量只有一个定义（Every variable has exactly one definition）

  例：

• 控制流合并时的情况

  需确保每个变量只有一个定义，如图：

  这时候会定义一个phi-function

• SSA的好处和坏处

  好处：

  1. 程序流信息可以间接地体现在唯一的变量名中（唯一的变量名带了一些流信息）

  2. 定义和使用对是显式的

  坏处：

  1. SSA可能会引入太多的变量和phi-function
  2. 转换为机器码时可能会导致效率低下的问题

  源ppt：

控制流分析

• 3AC通常被使用来建立控制流图（CFG）
• CFG是静态程序分析的基本结构
• CFG中的节点可以是单个3地址指令或者是一个Basic Block(BB)

图例：

Basic Blocks(BB)

• Basic Blocks（BB）是连续3-Address指令的最大序列，拥有以下属性：
  1. BB的入口只能是块中的第一个指令
  2. BB的出口只能是块中的最后一个指令

• 构建BB的算法

  输入：

  3-Address指令序列p

  输出：

  p的BB列表

  方法：

  1. 决定P中每个BB的第一个3-Address指令（leader）

     • p中第一个指令是leader
     • 任何有条件或无条件跳转的目标指令都是leader
     • 有条件或无条件跳转指令后的第一条指令是leader

  2. 构建p的BBs

     • BB由一个leader及其所有后续指令组成，直到下一个leader为止

Control Flow Graphs(CFG)

• 构建CFG
  1. CFG的节点是BBs
  2. 添边
• 添边
  1. 有(BB)A到（BB)B的有条件或无条件跳转，AB间添一条边
  2. (BB)B紧接着(BB)A,并且(BBA)不以无条件跳转指令(goto L)结尾

注：通常使用跳转到的基本块代替跳转到的指令标签，如图：

• Entry和Exit
  1. 是最后添加的两个结点
  2. 并不对应着任何可执行IR
  3. 从Entry到BB的边指向第一条指令（多线程的时候可能包含多条Entry）
  4. 从BB到Exit的边可能包含IR的最后一条指令(可能有多条出边，例如多个if…return..的情况)