静态程序分析chapter2 IRJimple 和 CFG,阅读程序分析输出结果是

文章目录 一、IR（Intermediate Representation）编译器（Compiler）3AC（3-Address Code）Soot和它的IR：JimpleJVM中的方法调用与方法签名简介invokespecialinvokevirtualinvokeinterfaceinvokestaticinvokedynamicmethod signature CFG（Control Flow Graph）的建立建立节点Node建立边Edge 总结

---

一、 IR（Intermediate Representation） 编译器（Compiler）

      编译器编译一般要经过5个阶段：词法分析；语法分析；语义分析；优化；目标代码生成。下面通过自然语言处理来说明这些步骤（处理代码也是类似的）。

      词法分析（Lexical Analysis）通过正则表达式来判断每一个单词本身是否存在错误。如果每一个单词都是正确的，就会给它们做上标记（Token），交给下一个步骤。

      语法分析（Syntax Analysis）通过上下文无关语法来判断每一个语句是否符合英文语法（主谓宾…）。如果语句的语法没有问题，就会将其转化为抽象语法树（AST）。

      语义分析（Semantic Analysis）通过属性语法来判断每一个语句的语义上是否存在问题，比如语句 Apples eat you 从语义上来说是行不通的。当然编译器在这个步骤的工作是比较简单的，它只对语句做类型检查，比如不能将一个 float 类型变量赋值给 char 类型变量。如果语句的语义没有问题，就会生成修饰过后的抽象语法树。

      优化（optimization）步骤是通过转换器转换为一种中间表示形式（IR），优化的结果就是生成了IR。通常所说的IR就是三地址码（3AC）。

      最终的目标代码（.obj）通过IR来生成。

      而静态分析通常是在IR上进行的，虽然最早也可以在AST上进行，但是现在已经被淘汰了。IR的优点在于：它是语言无关的并且包含有控制流信息，通常认为IR是静态分析的基石。见下面图示：

3AC（3-Address Code）

      三地址码的格式：在一个语句的右侧只有一个操作符。比如语句 a = b + c + 2；它转换为三地址码的格式；t1 = b + c；a = t1 + 2；其中的 t1 是临时变量。

      其实三地址码就是包含有三个地址的语句。这里的地址指的是：常量（2）、变量名（b or c）以及临时变量（t1）。

      常见的三地址码格式：（x，y 和 z 都是地址）

            x = y bop z
            x = uop z
            x=y
            goto L
            if x goto L
            if x rop y goto L

      bop 指的是二元算术运算符（+ , - , * , / , …）；uop 指的是一元算术运算符（- ，casting …）；rop指的是二元关系判断运算符（> , < , == …）。

Soot和它的IR：Jimple

      Jimple是一种典型的三地址码。下面给出一些简单的Java代码和对应的Jimple代码作为示例：（关于Soot，后面会专门讲解）

一、
      Java Src（do-while 循环）:

public class DoWhileLoop3AC{public static void main(String[] args){int[] arr = new int[10];int i = 0;do {i = i + 1;}while(arr[i] < 10)}}

      其中main函数所对应的Jimple代码为：

public static void main(java.lang.String[]){java.lang.String[] r0;int[] r1;int $i0,i1;r0 := @parameter0: java.lang.String[];r1 = newarray (int)[10];i1 = 0;label1:i1 = i1 + 1;$i0 = r1[i1];if $i0 < 10 goto label1;return;}

二、
      Java Src（方法调用）:

public class MethodCall3AC{String foo(String para1,String para2){return para1 + " " + para2;}public static void main(String[] args){MehtodCall3AC mc = new MehtodCall3AC();String result = mc.foo("hello","world"); }}

      其中 foo 函数和 main 函数对应的Jimple代码为：

java.lang.String foo(java.lang.String,java.lang.String){MethodCall3AC r0;java.lang.String r1, r2, $r7;java.lang.StringBuilder $r3,$r4,$r5,$r6;r0 := @this: MethodCall3AC;r1 := @parameterr0: java.lang.String;r2 := @parameterr1: java.lang.String;$r3 = new java.lang.StringBulider;specialinvoke $r3.<java.lang.StringBulider: void<init>()>();$r4 = virtualinvoke $r3.<java.lang.StringBulider: java.lang.StringBulider append(java.lang.String)>(r1);$r5 = virtualinvoke $r4.<java.lang.StringBulider: java.lang.StringBulider append(java.lang.String)>(" ");$r6 = virtualinvoke $r5.<java.lang.StringBulider: java.lang.StringBulider append(java.lang.String)>(r2);$r7 = virtualinvoke $r6.<java.lang.StringBulider: java.lang.String toString()>();return $r7;}public static void main(java.lang.String[]){java.lang.String[] r0;MethodCall3AC $r1;r0:= @parameter0: java.lang.String[];$r1= new MethodCall3AC;specialinvoke $r1.<MethodCall3AC: void<init>()>();virtualinvoke $r1.<MethodCall3AC: java.lang.String foo(java.lang.Stirng,java.lang.String)>("hello","world");return;}

三、
      Java Src（类）:

package a.b.c;public class Class3AC{public static final double pi = 3.14;public static void main(String[] args){}}

      这个类对应的Jimple代码为：

public class a.b.c.Class3AC extends java.lang.Object{public static final double pi;public void <init>(){a.b.c.Class3AC r0;r0 := @this: a.b.c.Class3AC;specialinvoke r0.<java.lang.Object: void <init>()>();return;}public static void main(java.lang.String[]){java.lang.String[] r0;r0:= @parameter0: java.lang.String[];return;}public static void <clinit>(){<a.b.c.Class3AC: double pi> = 3.14;return;}} JVM中的方法调用与方法签名简介 invokespecial

      用来调用构造函数，父类方法和私有方法（constructor、superclass method、private method），构造函数的的方法名是 。

invokevirtual

      用来调用实例方法、基于类进行分派（instance method、virtual dispatch）

invokeinterface

      用来调用接口中的方法

invokestatic

      用来调用静态方法

invokedynamic

      Java7 添加，调用方法让其动态执行

method signature

      方法签名的格式为：<类名： 返回值 方法名（参数1的类型，参数2的类型…）>（传入的实参1，传入的实参2…）

CFG（Control Flow Graph）的建立

      下面讲述采用3AC-IR建立控制流程图的过程。控制流程图是静态分析的最基本的结构，控制流程图是由节点和边组成的，节点通常是一个独立的3AC语句，或者是一个基本块BB（Basic Block）；边用来表示控制流的方向。

建立节点Node

      BB是满足下面特点的最大的连续语句系列。第一，BB只能拥有一个入口。第二，BB只能拥有一个出口。根据这两个特点，对于连续的3AC语句，将它们转换为一系列BB的方法为：

      每一个入口语句只能为：在所有语句中的第一条语句；任何跳转语句的目的地址所在语句；任何跳转语句的下一条语句。

      当我们找到所有入口语句之后，就可以轻易地构建BB了。

      下图中左侧为输入语句，右侧是根据上面方法构建的BB：

      每一个BB中的第一条语句称为 leaders，先找到所有的 leaders：(1)是第一条语句；(3)(7)(12)是跳转语句的目标语句；(5)(11)(12)是跳转语句的下一条语句。

      最后，得到的BB如下图所示：

建立边Edge

      1，如果一个基本块 A 的最后一条语句为跳转语句，并且该跳转语句指向另一个基本块 B 的第一条语句，那么，存在一条边从基本块 A 指向基本块 B 。

      2，如果一个基本块 A 的最后一条语句不是无条件跳转语句，而 B 是紧接着 A 的下一个基本块，那么，存在一条边从基本块 A 指向基本块 B 。

      称 A 为 B 的前驱，B 为 A 的后继。

      通常，我们需要再添加两个节点，入口节点和出口节点。类似于数据结构链表的链表头，它们并不包含任何语句，仅用来标记CFG的入口和出口。入口节点指向的BB中包含有整个代码执行中的第一条IR语句；指向出口节点的BB中包含可能是整个代码执行的最后一条IR语句。

      在上面的BB中按照既有规则加上边之后，得到的 CFG 如下图：

总结

      静态分析的原材料是 3AC-IR ，文中列出了常用的六种 3AC-IR 的格式，为了更好的理解，我们介绍了 Soot 是如何将 Java 源代码转换为 IR Jimple 的，并且补充了JVM中的方法调用。最后一部分介绍了在 IR 的基础上建立 CFG ，包括边和节点的建造，后面会继续介绍如何在 CFG 上进行数据流分析和三个典型案例讲解。未完待续~