Static analysis指在不对program进行运行的情况下，对其行为进行分析。搞compiler的人用之于优化，搞安全的用于做taint analysis。对于Java有两大开源的static analysis 框架，Soot和WALA，前者由McGill大学维护，后者是IBM。最新的Soot开始支持对Andoird 代码分析，包括static taint analysis。
从这篇开始，我们将由浅入深的对Soot进行了解，使用，甚至扩展。在这里默认读者对static analysis理论（lattice, 不动点, may & must等），Java source code和bytecode语法有基本了解。将主要依据Soot 官网提供的资料作为依据，特别是那本『生存手册』（点击打开链接）。
好了，现在我们开始。
Soot包括四种IR（中间码-表示形式），分别代表了四种对Java Sourcode或者bytecode的不同程度的抽象。
Baf – 基于栈的bytecode
传统的JVM bytebode是基于栈操作的指令集（Dalvik 基于寄存器操作），与之对应的Baf同样如此。那Baf抽象了什么呢？两个，忽略了constant pool(常量池)和bytecode指令中的type依赖。在bytecode中对不同保留类型，如int和float，的同一操作（如add），有不同的指令。这是因为在计算机中整形和浮点型的表达方式是不一样的，在底层实现时无法让两个操作符分属于这两种不同类型，也就是需要不同的指令对应不同的数据类型的操作。我们做分析时不用在意它到底调用的什么类型的指令，不对int还是float做细致区分，只要知道它是个数且知道是对这数的什么样的操作就行了。Baf因此用于在bytecode层面上的分析。
Jimple – typed, 3-addresses, statement based。
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。
看段书中的例子。用
java -cp soot-trunk.jar soot.Main -f J Foo
读入sootOutput文件夹中的Foo.Jimple。其所对应的Java 源码为，
public class Foo {public static void main(String[] args) { Foo f = new Foo();int a = 7;int b = 14;int x = (f.bar(21) + a) * b; }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); $i4 = $i3 + i0;i2 = $i4 * i1;return;}public int bar() { Foo r0;int i0, $i1;r0 := @this: Foo; // IdentityStmti0 := @parameter0: int; // IdentityStmt $i1 = i0 + 21; // AssignStmtreturn \$i1; // ReturnStmt}可以看出Jimple是一种Java sourcecode和 bytecode的混合体。对于局部变量的声明和赋值statement用的是Java，而控制流和函数调用采用的是bytecode。和反编译Dalvik bytecode所得的smali类似，Jimple在每个method body前会把所有用到的局部变量和stack位置做出声明（即Var -> Loc, 把变量映射到栈中的地址并在body中用地址替代变量名）。带"$"的局部变量表示是stack中的位置而不是原java code中真正声明过的局部变量，表示在java中不出现而bytecode中少不了的隐含变量如this, 储存中间结果的变量等。反之不带的即与原java code中局部变量相对应。
线性化过程把int x = (f.bar(21)) + a) * b拆成了三条statement：函数调用一条， $i4 = $i3 + i0和i2 = $i4 * i1；因此保证了每条stament至多只带3条地址。
i0 := @parameter0和r0 := @this作为IdentityStmt分别代表对形参和this的复制。所有的局部变量都是带类型的。
Jimple适用于绝大多数的不需要精确control flow或者SSA的静态分析。
Shimple — Static Single Assignment 版的Jimple
和Jimple基本一样，只有两点不同: SSA 和phi-node。SSA保证了每个局部变量都有一个静态定义。
目前还没有看到用SSA的可能，先暂时略过。
Grimp — 更适合人读的
和Jimple类似，多了允许树形表达和new指令。相比于Jimple，更贴近Java code，所以更适合人来读。
public static void main(java.lang.String[]) { java.lang.String[] r0;Foo r2;int i0, i1, i2;r0 := @parameter0: java.lang.String[]; r2 = new Foo();i0 = 7;i1 = 14;i2 = (r2.<Foo: int bar(int)>(21) + i0) * i1;return; }可以看到树形表达式没有被linerazation, 对象的初始化浓缩到new中，一些临时局部变量被省去了。Grimp更适用于做available expr（表达expr简洁）和反编译（适合人读）。
介绍完Soot的基本IR们，我们来说说Soot的基本使用。command为
java -cp soot-2.5.0.jar soot.Main -cp . -pp A B 输入的class有两种 1. application class 即要被分析和翻译的（在Soot里叫transformation）class 2. Library class. 为application class所引用，有助于分析但不会直接被分析的class。
关于具体的命令就不再这里敷述了。
Soot的执行过程被分成了好几大步，每一大步被称为一个pack。第一步是把输入的bytecode (.class)或者.java 文件或者.jimple 翻译成Jimple code。再把生成的Jimple作为剩下packs的输入。"函数中分析(intra-procedure analysis)"执行流程示意如下：
转动心中的期待，血在澎湃，吃苦流汗算什么。
