Soot生成控制流图

Soot是McGill大学的Sable研究小组自1996年开始开发的Java字节码分析工具，它提供了多种字节码分析和变换功能，通过它可以进行过程内和过程间的分析优化，以及程序流图的生成，还能通过图形化的方式输出，让用户对程序有个直观的了解。尤其是做单元测试的时候，可以很方便的通过这个生成控制流图然后进行测试用例的覆盖，显著提高效率。

如果是将Soot当作简单工具来分析的人，可以直接使用Soot自带的工具soot.tools.CFGViewer分析类中的每个方法的控制流并生成DOT语言描述的控制流图，然后用graphviz中的dot命令来转换成可视化图形格式如.PNG

使用soot.tools.CFGViewer来生成Triangle.class的控制流图

进入项目bin目录下，拷贝soot.trunk.jar

1 java -cp soot-trunk.jar soot.tools.CFGViewer --soot-classpath .;"%JAVA_HOME%"jrelib
t.jar TriangleClass.Triangle

为什么这里是TriangleClass.Triangle,是因为Triangle类是在TriangleClass包下的，所以类名需要加上完整包名

Triangle.java源代码如下：

 1 package TriangleClass;
 2 
 3 public class Triangle {
 4     
 5     
 6     public String triangle(int a, int b, int c){
 7         
 8         if(a > 0 && b > 0 && c >0){
 9             if(a + b >c)
10             {
11                 if(a == b || b ==c || a ==c)
12                 {
13                     if(a == b && b == c)
14                     {
15                         return "equilateral";
16                     }
17                     return "isosceles";
18                 }
19                 else{
20                     return "scalene";
21                 }
22             }
23             else{
24                 return "Not Triangle";
25             }
26         }
27         else{
28             return "Not Triangle";
29         }
30         
31         
32         
33     }
34     
35     public int a;
36     public int b;
37     public int c;
38 
39 }

其中一个文件已经生成

重命名后（文件名太长了。。），使用graphviz dot转换为图片PNG格式

1 dot -Tpng -o Triangle.png Triangle.dot

再生成Test.class的控制流图：

Test.java

 1 package Soot;
 2 
 3 public class Test {
 4     
 5     private double num = 5.0;
 6     
 7     public double cal(int num, String type){
 8         double temp=0;
 9         if(type == "sum")
10         {
11             for(int i = 0; i <= num; i++){
12                 temp =temp + i;
13             }
14         }
15         else if(type == "average")
16         {
17             for(int i = 0; i <= num; i++){
18                 temp = temp + i;
19             }
20             temp = temp / (num -1);
21         }else{
22             System.out.println("Please enter the right type(sum or average)");
23         }
24         return temp;
25     }
26 }

但是作为程序员，怎么能满足于简单的使用！

那么如何使用代码来在程序内部实现这个从分析代码到输出的过程呢？以下为Soot的深入理解内部代码实现生成控制流图：

Soot的输入时多源的，可以是java的字节码。Soot提供了四个中间表示法，通过将源文件转换为中间表示，基于这些中间表示传入不同的变换类来进行分析，优化或者再变换，另外还直接提供一组直接用于优化Java字节码的API。Soot的扩展机制以Pack为中心，一个Pack包括若干个变换用户可以自行设计新的变换，将其加入到soot的调度执行过程中以实现特定的功能，如输出为dot文件格式。

四种中间表示法是：Baf，Grimp，Jimple和Shimple

Baf - 基于栈的bytecode

传统的JVM bytebode是基于栈操作的指令集（Dalvik 基于寄存器操作），与之对应的Baf同样如此。那Baf抽象了什么呢？两个，忽略了constant pool(常量池)和bytecode指令中的type依赖。在bytecode中对不同保留类型，如int和float，的同一操作（如add），有不同的指令。这是因为在计算机中整形和浮点型的表达方式是不一样的，在底层实现时无法让两个操作符分属于这两种不同类型，也就是需要不同的指令对应不同的数据类型的操作。我们做分析时不用在意它到底调用的什么类型的指令，不对int还是float做细致区分，只要知道它是个数且知道是对这数的什么样的操作就行了。Baf因此用于在bytecode层面上的分析。

：：使用这种基于栈的中间表示法为的是简化一定要在栈代码上执行的分析和变换的开发。

Jimple - 紧凑、无栈、类型化的三地址代码中间表示法

Jimple是Soot的核心，是四种IR中最重要的。Soot能直接创建Jimple码，也可由Java sourcecode或者bytecode转化翻译而来。bytecode会被翻译成untyped Jimple，再通过type inference 方法对局部变量加上类型。翻译的重要一步是对表达式作线性化使得每个statement只能最多refernce 3个局部变量或者常量（没懂。。）。相对于bytecode的200多种指令，Jimple只有15条，分别对应着核心指令的 NopStmt, IdentityStmt, AssignStmt；函数内控制流指令的IfStmt, GotoStt, TableSwitchStmt和LookUpSwitchStmt，函数间控制流的InvoeStmt, ReturnStmt, ReturnVoidStmt, 监视器指令EnterMonitorStmt和ExitMonitorStmt，最后处理异常ThrowStmt和退出的RetStmt。

：：结构清晰，更适用于程序分析和代码优化

Grimp -- Jimple聚合版

可以构造树形结构，更接近于java源代码，适用于反汇编并便于阅读

Shimple -- Static Single Assignment 版的Jimple

给出java源代码，和不同表示形式的比较：

java源码：

1 public class Foo {
2 public static void main(String[] args) { Foo f = new Foo();
3 int a = 7;
4 int b = 14;
5 int x = (f.bar(21) + a) * b; }
6 public int bar(int n) { return n + 42; } }

Jimple中间表示：

public static void main(java.lang.String[]) { java.lang.String[] r0;
Foo $r1, r2;
int i0, i1, i2, $i3, $i4;
r0 := @parameter0: java.lang.String[]; $r1 = new Foo;
specialinvoke $r1.<Foo: void <init>()>(); r2 = $r1;
i0 = 7;
i1 = 14;
// InvokeStmt
$i3 = virtualinvoke r2.<Foo: int bar()>(21);&nbsp;
$i4 = $i3 + i0;
i2 = $i4 * i1;
return;
}
public int bar() { Foo r0;
int i0, $i1;
r0 := @this: Foo; // IdentityStmt
i0 := @parameter0: int; // IdentityStmt $i1 = i0 + 21; // AssignStmt
return $i1; // ReturnStmt
}

Grimp中间表示：

1 public static void main(java.lang.String[]) { java.lang.String[] r0;
2 Foo r2;
3 int i0, i1, i2;
4 r0 := @parameter0: java.lang.String[]; r2 = new Foo();
5 i0 = 7;
6 i1 = 14;
7 i2 = (r2.<Foo: int bar(int)>(21) + i0) * i1;
8 return; }

Soot读入Java字节码，然后通过Baf将字节码转换为可分析的Jimple，然后再进入分析变换过程，接着可以再转换为Grimp形式或者Baf形式来输出或者再转换为java字节码输出优化的Java字节码，这就是Soot在数据层面抽象的处理过程。

Soot的执行过程被分成了好几大步，每一大步被称为一个pack。第一步是把输入的bytecode (.class)或者.java 文件或者.jimple 翻译成Jimple code。再把生成的Jimple作为剩下packs的输入。"函数中分析(intra-procedure analysis)"执行流程示意如下

如图所示，在soot里每一个圆圈算一个阶段，每个阶段都有对应的Pack（p）实现，Pack是一组变换器，当Pack被调用时，它按照顺序执行每一个变换器。提供拓展机制的是那些允许用户做自定义变换（Transformation）的Pack：jtp（Jimple Transformation Pack），stp(Shimple Transformation Pack),在不改变soot自身的情况下，用户可以满足自身需求的类（变换器），然后将其注入到这些Pack中，之后调用soot.Main，使其进入soot的调度过程中。

Soot变换器通常是继承了BodyTransformer或SceneTransformer的类的实例。BodyTransformer针对单个方法体进行变换，SceneTransformer针对整个应用进行变换。在这两种情况下，变换器类都必须重构internalTransform方法，对要分析的代码执行某种变换。

如下是简单的格式：

 1 import java.util.Iterator;
 2 import java.util.Map;
 3 import soot.*;
 4 
 5 class Example {
 6 
 7   public void run(String dir){
 8     
 9     Printer printer = new Printer();
10     //生成变换器
11     Transform t1 = new Transform("jtp.Printer", printer);
12     //加入到Pack中
13     PackManager.v().getPack("jtp").add(t1);
14     
15     int size;
16     String[] soot_args = new String[size];
17     /*指定参数选项调用main*/
18     soot.Main.main(soot_args);
19   }
20 
21   public static void main(String[] args){
22     Example example = new Example();
23     example.run("要处理的类路径");
24   }
25 
26   class Printer extends BodyTransformer {
27 
28     @Override
29     protected void internalTransform(Body body, String string, Map map) {
30       /*添加自己的变换*/
31       }
32     }
33   }
34 }

　这里interTransform是最重要的处理类，通过流程我们会知道在这个阶段会传过来JimpleBody或ShimpleBody，即internalTransform的参数Body body， String string是阶段名称，map是调用soot传递的参数选项。

　在Soot中一个Body隶属于一个SootMethod, 即soot用一个Body为一个方法存储代码。我们输出上面Triangle.class的body

 1 public java.lang.String triangle(int, int, int)
 2     {
 3         TriangleClass.Triangle r0;
 4         int i0, i1, i2, $i3;
 5 
 6         r0 := @this: TriangleClass.Triangle;
 7 
 8         i0 := @parameter0: int;
 9 
10         i1 := @parameter1: int;
11 
12         i2 := @parameter2: int;
13 
14         if i0 <= 0 goto label5;
15 
16         if i1 <= 0 goto label5;
17 
18         if i2 <= 0 goto label5;
19 
20         $i3 = i0 + i1;
21 
22         if $i3 <= i2 goto label4;
23 
24         if i0 == i1 goto label1;
25 
26         if i1 == i2 goto label1;
27 
28         if i0 != i2 goto label3;
29 
30      label1:
31         if i0 != i1 goto label2;
32 
33         if i1 != i2 goto label2;
34 
35         return "equilateral";
36 
37      label2:
38         return "isosceles";
39 
40      label3:
41         return "scalene";
42 
43      label4:
44         return "Not Triangle";
45 
46      label5:
47         return "Not Triangle";
48     }

　　有了Body的信息，我们需要进行控制流分析，将Body转换为控制流图。控制流图除了表示这个节点（每一个节点表示一个基本块）之外，还会存储这个节点的前驱和后继，形式上可以表示为：

　　前驱

　　后继

　　Soot提供两种控制流图UnitGraph和BlockGraph，都实现DirectedGraph接口，这两个都是抽象类，soot提供了若干实例化的类：CompleteUnitGraph，BriefUnitGraph,都在soot.toolkits.graph中使用这些就可以将Body转换为控制流图CFG。

　　通过阅读源代码可知，CFGGraphType可以通过字符串生成相应类型的控制流图，这样有利于参数化程序。

　　CFGGraphType.java相应代码

　　这里通过CFGGraphType类来读取参数信息，生成相应的控制流图类型，

protected void internalTransform(Body b, String phaseName, Map<String, String> options) {
         initialize(options);
         CFGGraphType graphtype;
         graphtype = CFGGraphType.getGraphType(“BriefUnitGraph”);
         DirectedGraph<Unit> graph = graphtype.buildGraph(body);
                 /*后续操作*/
         
     }

　　我们可以看看Triangle.class生成的BriefUnitGraph类型控制流图：可看出每个statement有preds前驱集合和succs后继集合

// preds: []
r0 := @this: TriangleClass.Triangle
// succs [i0 := @parameter0: int]
// preds: [r0 := @this: TriangleClass.Triangle]
i0 := @parameter0: int
// succs [i1 := @parameter1: int]
// preds: [i0 := @parameter0: int]
i1 := @parameter1: int
// succs [i2 := @parameter2: int]
// preds: [i1 := @parameter1: int]
i2 := @parameter2: int
// succs [if i0 <= 0 goto return "Not Triangle"]
// preds: [i2 := @parameter2: int]
if i0 <= 0 goto return "Not Triangle"
// succs [if i1 <= 0 goto return "Not Triangle", return "Not Triangle"]
// preds: [if i0 <= 0 goto return "Not Triangle"]
if i1 <= 0 goto return "Not Triangle"
// succs [if i2 <= 0 goto return "Not Triangle", return "Not Triangle"]
// preds: [if i1 <= 0 goto return "Not Triangle"]
if i2 <= 0 goto return "Not Triangle"
// succs [$i3 = i0 + i1, return "Not Triangle"]
// preds: [if i2 <= 0 goto return "Not Triangle"]
$i3 = i0 + i1
// succs [if $i3 <= i2 goto return "Not Triangle"]
// preds: [$i3 = i0 + i1]
if $i3 <= i2 goto return "Not Triangle"
// succs [if i0 == i1 goto (branch), return "Not Triangle"]
// preds: [if $i3 <= i2 goto return "Not Triangle"]
if i0 == i1 goto (branch)
// succs [if i1 == i2 goto (branch), if i0 != i1 goto return "isosceles"]
// preds: [if i0 == i1 goto (branch)]
if i1 == i2 goto (branch)
// succs [if i0 != i2 goto return "scalene", if i0 != i1 goto return "isosceles"]
// preds: [if i1 == i2 goto (branch)]
if i0 != i2 goto return "scalene"
// succs [if i0 != i1 goto return "isosceles", return "scalene"]
// preds: [if i0 == i1 goto (branch), if i1 == i2 goto (branch), if i0 != i2 goto return "scalene"]
if i0 != i1 goto return "isosceles"
// succs [if i1 != i2 goto return "isosceles", return "isosceles"]
// preds: [if i0 != i1 goto return "isosceles"]
if i1 != i2 goto return "isosceles"
// succs [return "equilateral", return "isosceles"]
// preds: [if i1 != i2 goto return "isosceles"]
return "equilateral"
// succs []
// preds: [if i0 != i1 goto return "isosceles", if i1 != i2 goto return "isosceles"]
return "isosceles"
// succs []
// preds: [if i0 != i2 goto return "scalene"]
return "scalene"
// succs []
// preds: [if $i3 <= i2 goto return "Not Triangle"]
return "Not Triangle"
// succs []
// preds: [if i0 <= 0 goto return "Not Triangle", if i1 <= 0 goto return "Not Triangle", if i2 <= 0 goto return "Not Triangle"]
return "Not Triangle"
// succs []

　　生成了控制流还没有结束，我们需要将它输出为图形，如dot类型文件，所幸soot带了将CFG转化成dot的类：CFGToDotGraph和DotGraph,所以我们可以将之前的结果作为输入，生成dot文件，代码为：

protected void internalTransform(Body b, String phaseName, Map<String, String> options) {
   
         CFGGraphType graphtype;
         graphtype = CFGGraphType.getGraphType(“BriefUnitGraph”);
         DirectedGraph<Unit> graph = graphtype.buildGraph(b);
         /*后续操作*/
         CFGToDotGraph drawer= new CFGToDotGraph();
         /*设定参数*/
         drawer.setBriefLabels(PhaseOptions.getBoolean(options, briefLabelOptionName));
            drawer.setOnePage(!PhaseOptions.getBoolean(options, multipageOptionName));
    drawer.setUnexceptionalControlFlowAttr("color", "black");
    drawer.setExceptionalControlFlowAttr("color", "red");
    drawer.setExceptionEdgeAttr("color", "lightgray");
    drawer.setShowExceptions(Options.v().show_exception_dests());
        /*生成dotGraph*/
        DotGraph canvas = graphtype.drawGraph(drawer, graph, b);
        /*输出*/
        String methodname = body.getMethod().getSubSignature();
    String classname = body.getMethod().getDeclaringClass().getName().replaceAll("\$", "\.");
    String filename = soot.SourceLocator.v().getOutputDir();
        if (filename.length() > 0) {
            filename = filename + java.io.File.separator;
        }
        filename = filename + classname + " " + methodname.replace(java.io.File.separatorChar, '.') + DotGraph.DOT_EXTENSION;

    G.v().out.println("Generate dot file in " + filename);
    canvas.plot(filename);
         
     }

　　之后只用设定好soot_args就可

　　完整代码见Github:

https://github.com/clownice/GenerateControlFlow