基于SOOT框架的JAVA指针分析

概述

code
研一在国科大暑假小学期，选修了北大熊英飞和张路老师的《程序分析》，上课期间，很多时候都是云里雾里。课程结束后，留有一个大作业「实现一个JAVA上的指针分析系统」。花了几天时间，终于将其搞定，于是决定当一个“事后诸葛亮”，整理下大作业实现的思路，简单系统的讲述下如何完成这个系统。

需求

利用开源框架，如SOOT程序分析框架，对JAVA程序进行指针分析。

输入：

public static void main(String[] args) {
Benchmark.alloc(1); //标记分配点
A a = new A();
Benchmark.alloc(2);
A b = new A();
Benchmark.alloc(3);
A c = new A();
if (args.length>1) a=b;
Benchmark.test(1, a); //标记测试点编号和被测变量
Benchmark.test(2, c);
}

输出：

1: 1 2
2: 3

上述需求是这样理解的，alloc(1)表示一开始new A()得到的地址标号为1，同理得到b、c的地址标号。最后输入测试变量，得到a可能在的地址标号。以a分析举例，一开始，A a = new A()，可以确定a变量对应有地址1，然后在if (args.length>1) a=b;语句之后，a还可能有地址2，然后，合并分支，可以得到a可能在的地址为1和2。

分析

刚开始接触到这个大作业，应该先根据理论知识，确定相应的几个核心问题，然后根据问题，我们逐步提出软件框架，最后设计出整个系统。首先，是核心问题的提出，我们需要思考的问题包括：

1 指针分析中，半格应该是什么？程序怎样来表示半格？
2 JAVA程序中，存在哪几种操作，该操作会影响指针的指向？这些操作，对应的半格操作是什么？
3 对于域敏感的指针分析，如何处理域敏感？假设存在类A，其表示为：

class A {
   	B f;
   }
class B {
}

那么对于两个A变量a和b，赋值操作a=b，那么对于a.f以及b.f。它们是否是相同的。
4 程序中，存在条件选择函数，按照程序分析的假设，要认为每条支路都当做一条支路，如何实现分支，半格在其中如何变化，最后如何实现合并？
5 程序中，存在函数调用，也就是程序间程序分析，假设存在这样的调用：

fun1 () {
  	int a, b;
  	fun2(a, b);
}
fun2 (int c, int d) {
  	d = c;
}

如何使得fun1中的a和b参数与fun2中的d和c对应起来。同时，每个函数域中存在很多的同名函数，则如何让他们不会相互影响？

程序实现

根据上述问题的分析，我们可以可以慢慢整理出一个框架，具体过程就不再赘叙，我就直接用另一个大佬实现的，我稍微修改的程序框架来进行说明。

Variable类

Variable类用于表示半格变量，它需要实现下述功能：

1. 对于程序中出现的每个变量，都应该有一个对应的Variable对象。
2. Variable中需要一个对象，用于存储半格变量，也就是地址标号。以及相应对地址标号的操作，如添加获取等。
3. 在程序分析时，遇到分支，半格在不同分支会有不同的变化值，然后在分支汇合处进行合并操作。因此，需要为Variable类实现复制操作，在不同分支，都具备单独的半格变量。（因为如果只是=只是引用，并不是复制），注意Member变量的复制，浅复制只是引用！！
4. 由于我们需要进行域敏感分析，因此需要保存每个对象相应的成员函数。因此，在每个Variable中，还应该具备成员变量，成员变量中包含了成员对应的Variable对象。
5. 在JAVA中与指针相关的操作，实际上就是赋值操作，我们需要模拟该操作。

因此，我们可以确定Variable类的简单框架：

class Variable {
  Local local; //程序中对应的变量
  Member member;
  Set<Integer> sourceId;

  Variable copy(boolean depp); // deep则对Member变量也进行复制，否则只是复制Member的引用
  void assign(Variable var);
  void addId(int id);
  Set<Integer> getSourceId();
}

Member类

Member类主要用于表示成员变量，用于存储成员变量与Variable对象的映射关系。因此它需要实现下面功能：

1. 具有一个映射表，能够根据成员变量描述，得到相应的Variable对象。
2. 由于类包含有映射表，Variable需要实现复制，因此其也要实现复制操作。
3. 添加映射关系等。

因此，我们可以确定Member类的简单框架。

class Member {
  Value value;
  Map<SootFieldRef, Variable> fieldMap;

  Member copy();
  Variable getVariable(SootFieldRef sfr);
  void addField(SootFieldRef sfr, Variable var);
}

Analyzer类

Analyzer类主要实现指针分析的整体的半格操作。它需要实现下面功能：

1. Analyzer系统中只能存在一个。
2. 需要设置内存位置标号。
3. 存在一个映射表，通过该表，我们可以找到所有变量对应的半格，也就是Variable对象，然后又因为存在不同分支，因此对于一些变量，其对应有多个半格。同时，需要对这个映射表进行简单的添、查操作。
4. 需要记录查询的标号以及变量对应关系。
5. 根据查询的标号以及变量对应关系，将对应变量的所有半格进行合并，得到最终结果。

因此，我们可以确定Analyzer类的基本框架。

class Analyzer {
  int allocId;
  Map<Local, Set<Variable>> localMap;
  Map<Integer, Local> queries;

  void setId();
  int getId();
  void addVar(Local local, Variable var);
  Set<Variable> getVars(Local local);
  void addQuery(int id, Local local);
  String run();
}

Contex类

在程序运行中，对于选择函数，则会产生分支，对于函数调用，则会进入一个新的运行区域，对于该区域，半格以及变量都会有所不同，因此，我们需要对该种行为进行一个抽象，因此我们抽象一个Contex对象，该对象模拟该种情况。因此该类需要实现下面功能：

1. 对于每个函数体内，具有独立的变量映射表。
2. 对于函数调用，需要将调用函数体内的变量与当前函数的参数进行联系。注意，函数调用后，只会影响对象的内部对象的指针指向！！
3. 对于程序中的分支（If等），其与主分支变量相同，但是需要复制一份，因为在不同分支中具备不同的半格变化表示。
4. 需要判断是否进入递归函数或者分支循环。
5. 注意点，创建分支区域与创建函数子区域是不同的。创建一个分支域!!!!需要复制半格，并且是deep复制，因为在分支内，对象及其内部成员都会受到影响。而创建函数子区域，则无需复制操作。在进行函数调用后，需要将参数与上层函数域内变量对应，简单的想，只要将上层对应变量的Variable与该层的Local对应就行了，这样在该域内，对该域的Local操作，然后相应进行半格操作。但是由于函数调用，不会改变对象本身的指针！！！！只能改变对象成员的指针，因此，我们此时与该域对应的参数的Local对应的应该是上层相应变量的Variable的浅复制，这样该域内可以改变对象的成员指针，但是不能改变对象本身指针，举例说明：

class A {
  B o;
  public A() {
    o = new B();
  }
}

class B {
  public B() {
    
  }
}

public class MyPointerAnalysis {
  
  static void swap(A a, A b) {
    a.o = b.o;
  }
  public static void main(String[] args) {    
    A a = new A();
    A b = new A();
    System.out.println("a: " + a.hashCode() + " b: " + b.hashCode());
    System.out.println("a.o: " + a.o.hashCode() + " b.o: " + b.o.hashCode());
    swap(a, b);
    System.out.println("a: " + a.hashCode() + " b: " + b.hashCode());
    System.out.println("a.o: " + a.o.hashCode() + " b.o: " + b.o.hashCode());
  }

}

上述程序的输出结果是：

a: 2018699554 b: 1311053135
a.o: 118352462 b.o: 1550089733
a: 2018699554 b: 1311053135
a.o: 1550089733 b.o: 1550089733

由此可见！
因此，我们可以确定Contex类的基本框架：：

class Contex {
  Analyzer analyzer;  // 存在不同的半格分支，需要analyzer保存某个变量的所有半格
  String methodSignature; // 所在的函数体
  Contex invokeMethod; //保存该函数被调用所在的函数体的指正，从而能够将函数参数与上一个函数域对应
  List<Value> args,
  Contex preBranch; // 用于保留分支前的支流指针，比如 存在分支 A-> B, A -> C，那么B,C对应的Contex保留的为A
  Map<Local, Variable> localMap; //在该域内，变量及其对饮的半格

  //创建一个函数调用的新域，
  Contex createInvokeContex(String methodSignature, List<Value> args, Variable thisVar)；
  //创建一个分支域!!!!需要复制半格，并且是deep复制，因为在分支内，对象及其内部成员都会受到影响
  Contex createBranchScope(String branchSignature)；
  // 将变量与半格对应
  void bindLocalAndVariable(Local local, Variable var);
  // 简单来说就是将上层函数域中对应的变量的半格，浅复制一下，与当前域的local进行对应。
  void bindArg(Local local, int paramIndex);
  // 对于函数域内，变量的声明对应的Local，建立Variable与其对应
  void bindThis(Local local);
  // 判断是否递归
  boolean isInRecursion(String invokeSignature);
  // 判断分支是否递归
  boolean isInBranchChain(String branchSignature);
}

MyTransformer类

该类主要就是调用SOOT框架，SOOT框架将java文件以及class文件转化为相应的jimple文件，通过调用框架，针对各种情况进行分析，具体要看代码。因此可以得到该类的基本框架为：

class MyTransformer extends SceneTransformer {
  @Override
  protected void internalTransform(String arg0, Map<String, String> arg1);

  void solveMethod(SootMethod method, Contex contex);
  void solveBlock(Unit u, Contex contex, UnitGraph graph);
  void solveUnit(Unit u, Contex contex);

关于SOOT一些简单使用

如何调用soot框架

需要导入的包:

import soot.PackManager;
import soot.Transform;

启动使用soot进行程序分析

1. 首先，你要创建一个继承SceneTransformer的类，并重写函数protected void internalTransform(String s, Map<String, String> map)来实现你自己在程序分析中的一些处理。

2. 注册重写的Transformer类：

   PackManager.v().getPack("wjtp").add(new Transform("wjtp.myapp", new MyTransformer()));

3. 在主函数中，启动soot函数：

   soot.Main.main(new String[]{
                   "-w",
                   "-f", "J",
                   "-p", "cg.spark", "enabled:true",
                   "-p", "wjtp.myapp", "enabled:true",
                   "-soot-class-path", <包含运行时包含soot的jar包路径>,
                   <分析的代码的入口类，比如 App.Main>
           });

** 通过分析图函数，来逐步分析每个节点

1. 导入包

   import soot.*;
   import soot.jimple.*;
   import soot.toolkits.graph.BriefUnitGraph;
   import soot.toolkits.graph.UnitGraph;

2. 开始依次执行

   // 获取main函数
   SootMethod mainMethod = Scene.v().getMainMethod();
   // 获取main函数的函数体
   Body body = mainMethod.getActiveBody();
   // 基于函数体，创建程序分析图
   UnitGraph graph = new BriefUnitGraph(body);
   // 获取其头节点
   Unit head = graph.getHeads().iterator().next();
   // 获取每个节点的后续节点
   List<Unit> succs = graph.getSuccsOf(head);
   List<Unit> succs = graph.getSuccsOf(u);

3. 一些语句实体的类型及相关操作

   IdentityStmt is //定义语句 exp: r0 := @this: test.FieldSensitivity
   // 获取语句的两侧操作数或定义字符
   Value lop = is.getLeftOp()
   Value rop = is.getRightOp()
   
   ParameterRef pr // 参数定义语句 如： benchmark.objects.A
   pr.getIndex()   // 参数在函数调用中的位置
   
   ThisRef tr // this定义 如： @this: benchmark.objects.B
   
   AssignStmt as // 赋值语句，如： r4 = $r9
   
   AnyNewExpr ae // new 语句，如： new benchmark.objects.B
   NewArrayExpr // new 数组
   
   Local // 局部变量，比如： $r3

4. 如果要对某个对象的内部值进行赋值或者操作，比如A.name = B.name，相关操作。

   // 首先获取FieldRef
   FieldRef fr// 该类型用于表示表达式是否是存在域内部操作的，如： r3.<benchmark.objects.A: benchmark.objects.B f>
   // 获取纯内部对象类型
   SootFieldRef sr = fr.getFieldRef() 如： <benchmark.objects.A: benchmark.objects.B f>
   // 获取实际操作的操作
   Local rbase = (Local) fr.getBase(); 如 r3
   
   InstanceFieldRef // 就是实例赋值 r3.<benchmark.objects.A: benchmark.objects.B f>

5. 函数调用类的。

   InvokeStmt // 函数调用的表达式，如： specialinvoke $r9.<benchmark.objects.B: void <init>()>()
   InvokeExpr ie // 与上上式类似 如： specialinvoke $r9.<benchmark.objects.B: void <init>()>()
   
   SootMethod invokeMethod = ie.getMethod(); // 获取调用的函数
   String methodSignature = invokeMethod.getSignature(); //获取函数标签
   List<Value> invokeArgs = ie.getArgs(); //获取参数
   
   InstanceInvokeExpr // 实例初始化调用函数，如： specialinvoke r0.<test.FieldSensitivity: void assign(benchmark.objects.A,benchmark.objects.A)>(r2, r3)