soot-And-jimple

参考

soot API：https://soot-oss.github.io/soot/docs/4.4.1/jdoc/index.html

官方文档：https://github.com/soot-oss/soot/wiki/Tutorials

PDF：sootsurvivorsguide.pdf

一篇很不错的入门文章：https://zhuanlan.zhihu.com/p/558087790

Soot

数据结构

Scene：表示进行分析一个类时产生的完整环境（上下文）。通过它，可以设置应用程序类（提供给 Soot 进行分析的类）、主类（包含主方法的类）和访问关于过程间分析的信息（例如，指针信息和调用图）。

SootClass：表示加载到 Soot 中或使用 Soot 创建的类。

SootMethod：表示类的方法。

SootFiled：表示类的成员字段。

Body：代表一个方法体，有不同的风格，对应于不同的 IR（例如 JimpleBody）。这些数据结构是使用面向对象技术实现的，并且尽可能地设计为易于使用和通用。

Unit： 表示 Soot 中的语句，jimple 使用 Stmt 表示。

Jimple 中间表示的处理方法集合在 soot.jimple、soot.jimple.internal 中，大量优化集合在 soot.jimple.toolkits.* 中，尤其是在 soot.jimple.toolkits.scalar 和 soot.jimple.toolkits.annotation.*

Values：一个数据被表示为一个 Value。包括：局部变量（Local）、常量（在 Jimple 中表示为 Constant）、表达式（在 Jimple 中表示为 Expr）等等。表达式有各种不同的实现，例如 BinopExpr 和 InvokeExpr ，但一般来说可以理解为对一个或多个值执行某些操作并返回另一个值。

Box：在 Soot 中的引用（类似于指针），一般用于修改代码，有以下两种类型。

• ValueBox：指 Values，每个 unit 中都有使用和定义的 Values 的概念，这对于替换 Units 中使用的或定义的 box 非常有用，例如在执行常量折叠时
• UnitBox：指 Units，当一个 unit 可以有多个后继时（例如分支语句），就会使用 UnitBox。

Soot 执行阶段

Soot 中每一个执行的部分被称为 pack，而 Soot 的执行一般分为几个 packs 的阶段。第一步是生成 Jimple 代码以供各种 packs 使用。这是通过解析类、jimple 或 java 文件并将其结果通过 Jimple Body（jb） pack 进行传递。

packs 的命名方案相当简单。第一个字母指定 pack 接受的 IR；s 表示 Shimple，j 表示 Jimple，b 表示 Baf，g 表示 Grimp。第二个字母指定 pack 的角色；b 表示方法主体，t 表示用户定义的转换，o 表示优化，a 表示属性生成(注解)。pack 名称末尾的 p 表示 pack。例如，jap（Jimple 注解包）包含所有程序内分析。

下图是 Inter-procedural analysis（程序间分析） 的执行流程，在 Soot 运行周期中包括三个额外的包：cg（调用图生成），wjtp（整个 Jimple 转换包）和 wjap（整个 Jimple 注解包）。这些包生成的信息可以通过 Scene 提供给 Soot 的其他部分使用。而之后的 jtp、jop、jap 则是给每个 body 使用的，最终的产生的 bb（Baf Body 是 Soot 基于栈的中间表示，用于创建字节码）和 tag

image-20230325211418466

我们可以扩展 Soot 的 Main 类以包括我们自己的分析，将一个中间步骤注入到 Soot 中，使得 Soot 可以运行我们自定义的分析并处理传递给它的所有其他选项。过程间（inter-procedural analysis）需要注入到 wjtp 阶段而过程内（intra-procedural analysis）则注入到 jtp 阶段。下图的代码示例展示了如何将一个类 MyAnalysisTagger（执行某些 intra-procedural analysis）的实例注入到 Soot 中。

image-20230325221540502

使用Soot创建一个类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

//加载java.lang.Object类并创建相应的SootClass对象及SootMethods、字段SootFields
//如果有使用其他的类文件，需要引入例如标准库的类Scene.v().loadClassAndSupport("java.lang.System");
Scene.v().loadClassAndSupport("MyClass");

//为HelloWorld类创建SootClass对象。
sClass = new SootClass("HelloWorld", Modifier.PUBLIC);

//设置父类为java.lang.Object的SootClass对象
sClass.setSuperclass(Scene.v().getSootClass("java.lang.Object"));

//把新建的SootClass添加到Scene
Scene.v().addClass(sClass);

//创建一个main方法
method = new SootMethod("main",                 
    Arrays.asList(new Type[] {ArrayType.v(RefType.v("java.lang.String"), 1)}),
    VoidType.v(), Modifier.PUBLIC | Modifier.STATIC);

//将method添加到SootClass中
sClass.addMethod(method);

//为main方法创建一个JimpleBody，并将其设为活跃
JimpleBody body = Jimple.v().newBody(method);
method.setActiveBody(body);

//创建locals，并将其放入JimpleBody
arg = Jimple.v().newLocal("l0", ArrayType.v(RefType.v("java.lang.String"), 1));
body.getLocals().add(arg);

//将第一个参数的值分配给arg
units.add(Jimple.v().newIdentityStmt(arg, 
      Jimple.v().newParameterRef(ArrayType.v
        (RefType.v("java.lang.String"), 1), 0)));

//
// insert "tmpRef.println("Hello world!")"
{
    SootMethod toCall = Scene.v().getMethod
      ("<java.io.PrintStream: void println(java.lang.String)>");
    units.add(Jimple.v().newInvokeStmt
        (Jimple.v().newVirtualInvokeExpr
           (tmpRef, toCall.makeRef(), StringConstant.v("Hello world!"))));
}

//输出为.class文件
int java_version = Options.v().java_version();
String fileName = SourceLocator.v().getFileNameFor(sClass, Options.output_format_class);
OutputStream streamOut = new FileOutputStream(fileName);
BafASMBackend backend = new BafASMBackend(sClass, java_version);
backend.generateClassFile(streamOut);
streamOut.close();
或者使用
String fileName = SourceLocator.v().getFileNameFor(sClass, Options.output_format_class);
OutputStream streamOut = new JasminOutputStream(new FileOutputStream(fileName));
PrintWriter writerOut = new PrintWriter(new OutputStreamWriter(streamOut));
JasminClass jasminClass = new soot.jimple.JasminClass(sClass);
jasminClass.print(writerOut);
writerOut.flush();
streamOut.close();

//输出为jimple文件
String fileName = SourceLocator.v().getFileNameFor(sClass, Options.output_format_jimple);
OutputStream streamOut = new FileOutputStream(fileName);
PrintWriter writerOut = new PrintWriter(new OutputStreamWriter(streamOut));
Printer.v().printTo(sClass, writerOut);
writerOut.flush();
streamOut.close();

• SootClass 对应着一个对象。
• SootMethod 只能有一个活动的 Body，可通过 SootMethod.getActiveBody() 获取。
• Body有三个重要的功能：Locals、Traps 和 Units。
  • Locals 是主体中的局部变量。
  • Traps 是哪些单元捕获的哪些异常。
  • Units 是语句本身。

Soot配置与使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

G.reset();//初始化soot
Options.v().set_src_prec(Options.src_prec_class);//设置处理文件的类型,默认的是class文件
Options.v().set_process_dir(Collections.singletonList(processDir))//处理路径
Options.v().set_whole_program(true);//开启全局模式
Options.v().set_allow_phantom_refs(true);//开启虚引用
Options.v().set_prepend_classpath(true);//允许soot使用JVM的classpath
Options.v().set_output_format(Options.output_format_jimple);//文件输出格式设置为jimple
Scene.v().loadNecessaryClasses();//加载所有需要的类
PackManager.v().runPacks();//运行soot中所有的分析包
PackManager.v().writeOutput();//输出结果

G.reset();
Options.v().set_src_prec(Options.src_prec_class);
Options.v().set_process_dir(Collections.singletonList(processDir))
Options.v().set_whole_program(true);
Options.v().set_allow_phantom_refs(true);
Options.v().set_prepend_classpath(true);
Options.v().set_output_format(Options.output_format_jimple);
Scene.v().loadNecessaryClasses();
PackManager.v().runPacks();
PackManager.v().writeOutput();

apk配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14

G.reset();
Options.v().set_prepend_classpath(true);
Options.v().set_allow_phantom_refs(true);
Options.v().set_src_prec(Options.src_prec_apk);
Options.v().set_process_dir(Collections.singletonList(apkPath));
Options.v().set_android_jars(androidJarPath);
Options.v().set_whole_program(true);
List<String> excludeList = new ArrayList<>();
excludeList.add("java.*");
excludeList.add("javax.*");
Options.v().set_exclude(excludeList);//排除不需要分析的类和方法
Options.v().set_output_format(Options.output_format_jimple);
Scene.v().loadNecessaryClasses();
//PackManager.v().runPacks();

设置全程序分析，默认情况下是不进行全程序分析的。

1
2
3
4
5
6
7
8
9
10

public static void main(String[] args) {
  PackManager.v().getPack("wjtp").add(
      new Transform("wjtp.myTransform", new SceneTransformer() {
        protected void internalTransform(String phaseName,
            Map options) {
          System.err.println(Scene.v().getApplicationClasses());
        }
      }));
  soot.Main.main(args);
} 

一般使用 jtp、jop、jap 三个 pack 针对每个 body 进行分析。

• jtp 默认使用，并且是空的，需要我们放入自己的 intra-procedural analyses。
• jop 中有 Jimple 优化功能，但在默认情况下是禁用的。
• jap 默认启用，但是其中的处理功能会被禁用，当我们把自己的分析放入到 jap 时，会自动开启。
• 想要往 jtp、jop、jap 中加入 Transform 必须要使用 BodyTransformer。

下面是一份 jap 的使用示例。注册了一个新的 BodyTransformer，为每个方法中的每个语句打印出标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public static void main(String[] args) {
  PackManager.v().getPack("jap").add(
      new Transform("jap.myTransform", new BodyTransformer() {

        protected void internalTransform(Body body, String phase, Map options) {
          for (Unit u : body.getUnits()) {
            System.out.println(u.getTags());
          }
        }
      }));
  Options.v().set_verbose(true);
  PhaseOptions.v().setPhaseOption("jap.npc", "on");
  soot.Main.main(args);
}

数据流分析

1. 确定分析的性质。是向前还是向后的流分析？是否需要特别考虑分支？
2. 确定预期的近似值。是 may(并集) 分析还是 must(交集) 分析？即确定合并的信息流在通过一个节点时，采取并集还是交集。
3. 执行实际的流分析。实质上为中间表示中的每种语句编写方程——例如，应如何处理赋值语句。
4. 决定入口节点（如果是向后流）和内部节点的初始状态或近似值——通常是空集或全集，具体取决于分析的保守程度。 执行数据流分析需要一些表示数据如何在程序中流动的结构，例如控制流图（cfg）。 Soot 数据流框架通过 soot.toolkits.graph.DirectedGraph 接口进行处理 cfg。

Soot 提供了三种数据流分析的实现：

• ForwardFlowAnalysis 前向分析，从 UnitGraph 的入口语句开始进行向前传播。
• BackwardFlowAnalysis 后向分析，从 UnitGraph 的出口节点开始向后传播。
• ForwardBranchedFlowAnalysis 前向分支分析，实质上是一种前向分析，但是允许将不同的流集传播到不同的分支中。例如：处理 if(p != null) ，则可以将 p != nll 传播到为 true 的分支中，p == null 传播到为 false 的分支中。

继承类

实现分析，需要继承 ForwardFlowAnalysis（BackwardFlowAnalysis、ForwardBranchedFlowAnalysis ），其有两个参数：

• N：节点类型。通常是 Unit，但也可以对保存其他类型节点的图进行流分析。
• A: 抽象类型。通常使用 sets 或 maps 作为抽象类型，但一般来说，可以使用任何你喜欢的东西。但要注意，抽象类型必须正确地实现 equals(…) 和 hashCode()，这样 Soot 才能确定什么时候达到了固定点。

构造函数——真正的实现

实现一个构造函数，需要以 DirectedGraph<N> 作为参数（其中N是节点类型），并将其传递给父类的构造函数。在构造函数的末尾需要调用 doAnalysis() 方法以执行数据流分析，在调用父类构造函数和 doAnalysis() 方法之间可以自定义数据分析结构。

一些需要用到的方法和类：

• newInitialFlow() 返回一个自定义的抽象类型 A 的对象。这个对象被分配为每个语句的初始入集和出集，除了第一个语句的入集（如果实现的是一个向后分析，则为一个退出语句，例如 return 或 throw）
• entryInitialFlow() 初始化第一个语句的入集。
• copy(A source, A dest) 方法接受两个自定义的抽象类型 A 的参数：源和目标。实现将源复制到目标中。
• merge(A in1, A in2, A out) 方法用于在控制流的合并点（例如 if/then/else 语句的末尾）合并流集。接受三个参数，一个来自左分支的出集，一个来自右分支的出集，这将成为合并点之后下一个语句的新合并入集。即将两个 in 集合并为一个 out 集。
• flowThrough(A in, N d, A out) 方法接受三个参数，类型为 A 的入集； 要处理的类型为 N 的节点，通常是一个 Unit；类型为 A的出集。第一个参数始终是流函数的参数（即在正向分析中它是入集，在反向分析中它是出集），第三个参数始终是流函数的结果（即在正向分析中它是出集，在反向分析中它是入集）。是数据流分析的核心处理方法。
• FlowSet 接口中有一些集合操作的方法以及具体实现的类
  • ArraySparseSet：使用稀疏数组实现集合，支持高效的添加、删除、查找和迭代操作。
  • ArrayPackedSet：使用紧凑数组实现集合，可以存储更多的元素，但是由于使用了位运算，因此在操作时需要进行一些额外的计算，因此操作复杂度略高于ArraySparseSet。
  • 一般来说，如果需要存储的元素数量较少，可以选择ArraySparseSet；如果需要存储更多的元素，可以选择ArrayPackedSet；如果需要表示不确定的分析结果，可以选择ToppedSet。
    • ToppedSet：是ArraySparseSet的子类，额外支持一个元素作为“top”元素，用于表示未知的分析结果。
    • a.intersection(b,c); 表示 c=a∩b
    • a.union(b,c); 表示 c=a∪b
    • c.complement(d); 返回 c 和 d 的对称差（即 c 中存在而 d 不存在的元素以及 d 中存在而 c 中不存在的元素）
    • d.add(v); 表示 d=d∪{v}

最后可以把分析的结果放在 tag 中。

活跃变量分析

下面是一个分析 class 中的活跃变量的简单示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

import soot.*;
import soot.options.Options;
import soot.toolkits.graph.CompleteUnitGraph;
import soot.toolkits.graph.UnitGraph;
import soot.toolkits.scalar.BackwardFlowAnalysis;

import java.util.*;

public class LiveAnalysis {

    public static void main(String[] args) {
        G.reset();
        Options.v().set_src_prec(Options.src_prec_class);
        Options.v().set_process_dir(Collections.singletonList("C:\\Users\\守城\\Desktop\\Step2\\Lab3"));
        Options.v().set_whole_program(true);
        Options.v().set_allow_phantom_refs(true);
        Options.v().set_prepend_classpath(true);
        Options.v().set_keep_line_number(true);
        Options.v().set_output_format(Options.output_format_jimple);
        Scene.v().loadNecessaryClasses();
        SootClass sootClass = Scene.v().getSootClass("lab3");
        System.out.println("Name：" + sootClass.getName());
        System.out.println("Number of methods in SootClass: " + sootClass.getMethods().size());
        for (SootMethod sootMethod : sootClass.getMethods()) {
            System.out.println("Analyzing method: " + sootMethod.getName());
            CompleteUnitGraph graph = new CompleteUnitGraph(sootMethod.retrieveActiveBody());
            MyBackwardAnalysis myBackwardAnalysis = new MyBackwardAnalysis(graph);
            for (Unit unit : graph) {
                Set<String> flowBefore = myBackwardAnalysis.getFlowBefore(unit);
                Set<String> flowAfter = myBackwardAnalysis.getFlowAfter(unit);
                System.out.println("Before: " + flowAfter + " | After: " + flowBefore + " | Statement: " + unit);
            }
        }
    }
    public static class MyBackwardAnalysis extends BackwardFlowAnalysis<Unit, Set<String>> {
        public MyBackwardAnalysis(UnitGraph graph) {
            super(graph);
            doAnalysis();
        }

        @Override
        protected Set<String> newInitialFlow() {
            return new HashSet<>();
        }

        @Override
        protected Set<String> entryInitialFlow() {
            return new HashSet<>();
        }

        @Override
        protected void merge(Set<String> in1, Set<String> in2, Set<String> out) {
            out.clear();
            out.addAll(in1);
            out.addAll(in2);
        }

        @Override
        protected void copy(Set<String> source, Set<String> dest) {
            dest.clear();
            dest.addAll(source);
        }

        @Override
        protected void flowThrough(Set<String> in, Unit unit, Set<String> out) {
            out.clear();
            out.addAll(in);
            for (ValueBox box : unit.getDefBoxes()) {
                Value value = box.getValue();
                if (value instanceof Local) {
                    out.remove(((Local) value).getName());
                }
            }
            for (ValueBox box : unit.getUseBoxes()){
                Value value = box.getValue();
                if (value instanceof Local){
                    out.add(((Local) value).getName());
                }
            }
        }
    }
}

常量传播

跟活跃变量分析不同，常量传播需要设置初始集，需要把方法的参数先判断是否为常量，再将其添加初始集合。同时，在进行merge合并时，大部分时取交集或者是其他更加复杂的算法，但是不会取并集。

因为如果是两条支路中，在一条支路中是常量，但是在另外一条支路中不是常量，所以此时取交集会更加准确一点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public static class ConstantPropagation extends ForwardFlowAnalysis<Unit, FlowSet<String>> {
    public ConstantPropagation(UnitGraph graph) {
        super(graph);
        doAnalysis();
    }

    @Override
    protected FlowSet<String> newInitialFlow() {
        return new ArraySparseSet<>();
    }

    @Override
    protected FlowSet<String> entryInitialFlow() {
        FlowSet<String> flowSet = new ArraySparseSet<>();
        List<Value> valueList = ((UnitGraph)graph).getBody().getParameterRefs();
        for (Value value : valueList){
            String className = ((RefType) value.getType()).getClassName();
            if (className.equals("java.lang.Integer") || className.equals("java.lang.String")
            || className.equals("java.lang.Boolean") || className.equals("java.lang.Byte")
            || className.equals("java.lang.Character") || className.equals("java.lang.Double")
            || className.equals("java.lang.Float") || className.equals("java.lang.Long")
            || className.equals("java.lang.Short")){
                flowSet.add(value.toString());
            }
        }
        return flowSet;
    }

    @Override
    protected void merge(FlowSet<String> in1, FlowSet<String> in2, FlowSet<String> out) {
        in1.intersection(in2, out);
    }

    @Override
    protected void copy(FlowSet<String> source, FlowSet<String> dest) {
        dest.clear();
        dest.union(source);
    }

    @Override
    protected void flowThrough(FlowSet<String> in, Unit unit, FlowSet<String> out) {
        out.clear();
        out.union(in);
        boolean isConstant = false;
        for (ValueBox box : unit.getUseBoxes()){
            Value value = box.getValue();
            // 判断 x = y - y 这种特殊情况
            if (unit instanceof SubExpr && ((JSubExpr) unit).getOp1Box().getValue() == ((JSubExpr) unit).getOp2Box().getValue()){
                isConstant = true;
                break;
            }
            if (value instanceof Constant || out.contains(value.toString())){
                isConstant = true;
                continue;
            }
            if (!out.contains(value.toString())){
                isConstant = false;
            }
        }
        if (isConstant){
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.add(value.toString());
            }
        }else {
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.remove(value.toString());
            }
        }
    }
}

更改之后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

public static class ConstantPropagation extends ForwardFlowAnalysis<Unit, Map<String, Object>> {
    public ConstantPropagation(UnitGraph graph) {
        super(graph);
        doAnalysis();
    }

    @Override
    protected Map<String, Object> newInitialFlow() {
        return new HashMap<>();
    }

    @Override
    protected Map<String, Object> entryInitialFlow() {
        Map<String, Object> map = new HashMap<>();
        List<Value> valueList = ((UnitGraph)graph).getBody().getParameterRefs();
        for (Value value : valueList){
            String className = ((RefType) value.getType()).getClassName();
            if (className.equals("java.lang.Integer") || className.equals("java.lang.String")
                    || className.equals("java.lang.Boolean") || className.equals("java.lang.Byte")
                    || className.equals("java.lang.Character") || className.equals("java.lang.Double")
                    || className.equals("java.lang.Float") || className.equals("java.lang.Long")
                    || className.equals("java.lang.Short")){
                map.put(value.toString(), value.toString().substring(0, 11));
            }
        }
        return map;
    }

    @Override
    protected void merge(Map<String, Object> in1, Map<String, Object> in2, Map<String, Object> out) {
        for (Map.Entry<String, Object> entry1 : in1.entrySet()){
            String parameter1 = entry1.getKey();
            for (Map.Entry<String, Object> entry2 : in2.entrySet()){
                String parameter2 = entry2.getKey();
                if (parameter1.equals(parameter2)){
                    out.put(parameter1, "Constant");
                }
            }
        }
    }

    @Override
    protected void copy(Map<String, Object> source, Map<String, Object> dest) {
        dest.clear();
        dest.putAll(source);
    }

    @Override
    protected void flowThrough(Map<String, Object> in, Unit unit, Map<String, Object> out) {
        out.clear();
        out.putAll(in);
        boolean isConstant = false;
        boolean isConstantValue = true;
        boolean isParameter = false;
        String para = null;
        for (ValueBox box : unit.getUseBoxes()){
            Value value = box.getValue();
            // 判断 x = y - y 这种特殊情况
            if (unit instanceof SubExpr && ((JSubExpr) unit).getOp1Box().getValue() == ((JSubExpr) unit).getOp2Box().getValue()){
                isConstant = true;
                break;
            }
            if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).equals("NAC")){
                isConstant = false;
                break;
            }
            if (value instanceof Constant || (out.containsKey(value.toString()) && ((String)out.get(value.toString())).startsWith("@parameter"))){
                isConstant = true;
                if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).equals("Constant")) isConstantValue = false;
                if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).startsWith("@parameter")){
                    isParameter = true;
                    para = ((String)out.get(value.toString())).substring(0, 11);
                }
            }
        }
        if (isConstant && isConstantValue && !isParameter){
            int constantValue = 0;
            // 单个赋值语句
            if (unit instanceof JAssignStmt){
                Value op = ((JAssignStmt)unit).getRightOp();
                if (out.containsKey(op.toString())){
                    constantValue = (Integer)(out.get(op.toString()));
                }else if (op instanceof Constant){
                    constantValue = ((IntConstant)op).value;
                }
            }
            // 判断加法
            if (unit instanceof AddExpr){
                Value op1 = ((AddExpr) unit).getOp1();
                Value op2 = ((AddExpr) unit).getOp2();
                constantValue = ((IntConstant)op1).value + ((IntConstant)op2).value;
            }
            // 判断减法
            if (unit instanceof SubExpr){
                Value op1 = ((JSubExpr) unit).getOp1();
                Value op2 = ((JSubExpr) unit).getOp2();
                constantValue = ((IntConstant)op1).value - ((IntConstant)op2).value;
            }
            // 判断乘法
            if (unit instanceof MulExpr){
                Value op1 = ((MulExpr) unit).getOp1();
                Value op2 = ((MulExpr) unit).getOp2();
                constantValue = ((IntConstant)op1).value * ((IntConstant)op2).value;
            }
            // 判断除法
            if (unit instanceof DivExpr){
                Value op1 = ((DivExpr) unit).getOp1();
                Value op2 = ((DivExpr) unit).getOp2();
                constantValue = ((IntConstant)op1).value / ((IntConstant)op2).value;
            }
            // 判断取余
            if (unit instanceof RemExpr){
                Value op1 = ((RemExpr) unit).getOp1();
                Value op2 = ((RemExpr) unit).getOp2();
                constantValue = ((IntConstant)op1).value % ((IntConstant)op2).value;
            }
            // 判断与运算
            if (unit instanceof AndExpr){
                IntConstant op1 = (IntConstant) ((AndExpr) unit).getOp1();
                IntConstant op2 = (IntConstant) ((AndExpr) unit).getOp2();
                constantValue = op1.value & op2.value;
            }
            // 判断或运算
            if (unit instanceof OrExpr){
                IntConstant op1 = (IntConstant) ((OrExpr) unit).getOp1();
                IntConstant op2 = (IntConstant) ((OrExpr) unit).getOp2();
                constantValue = op1.value | op2.value;
            }
            // 判断异或运算
            if (unit instanceof XorExpr){
                IntConstant op1 = (IntConstant) ((XorExpr) unit).getOp1();
                IntConstant op2 = (IntConstant) ((XorExpr) unit).getOp2();
                constantValue = op1.value ^ op2.value;
            }
            // 判断左移
            if (unit instanceof ShlExpr){
                IntConstant op1 = (IntConstant) ((ShlExpr) unit).getOp1();
                IntConstant op2 = (IntConstant) ((ShlExpr) unit).getOp2();
                constantValue = op1.value << op2.value;
            }
            // 判断右移
            if (unit instanceof ShrExpr){
                IntConstant op1 = (IntConstant) ((ShrExpr) unit).getOp1();
                IntConstant op2 = (IntConstant) ((ShrExpr) unit).getOp2();
                constantValue = op1.value >> op2.value;
            }
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.put(value.toString(), constantValue);
            }
        }else if (isConstant && !isConstantValue){
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.put(value.toString(), "Constant");
            }
        }else if (isConstant && isParameter){
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.put(value.toString(), para);
            }
        }
        else {
            for (ValueBox box : unit.getDefBoxes()){
                Value value = box.getValue();
                out.put(value.toString(), "NAC");
            }
        }
    }
}

死代码消除

• 控制流分析
  • 从方法入口开始，遍历 CFG 并标记可达语句。当遍历结束时，那些没有被标记的语句即控制流不可达。
• 活跃变量分析
  • 无用赋值：一个局部变量在一条语句中被赋值，但再也没有被该语句后面的语句读取，这样的变量和语句分别被称为无用变量和无用赋值。
  • 所以如果一个赋值语句中，等号左侧是一个无用变量，那么就可把该语句标记为无用赋值，然后去除。
• 常量传播
  • 分支不可达：预先对被检测代码应用常量传播分析，通过它来告诉我们条件值是否为常量，然后在遍历 CFG 时，我们不进入相应的不可达分支
  lab完成中的死代码消除部分，写的不咋地，将就一下。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426

  import soot.*; import soot.jimple.*; import soot.jimple.infoflow.InfoflowConfiguration; import soot.jimple.infoflow.android.InfoflowAndroidConfiguration; import soot.jimple.infoflow.android.SetupApplication; import soot.jimple.internal.*; import soot.jimple.toolkits.callgraph.Edge; import soot.options.Options; import soot.toolkits.graph.CompleteUnitGraph; import soot.toolkits.graph.UnitGraph; import soot.toolkits.scalar.BackwardFlowAnalysis; import soot.toolkits.scalar.ForwardFlowAnalysis; import java.util.*; public class DeadCodeEliminator { public static void main(String[] args) { initializeSoot(); initializeFlowDroid(); // 去除无需分析的androidx、R类 Collection<SootClass> toAnalysisClasses = Scene.v().getApplicationClasses(); toAnalysisClasses.removeIf(sootClass -> sootClass.getName().startsWith("androidx") || sootClass.getName().startsWith("com.example.lab_code.R") || sootClass.getName().startsWith("com.example.lab_code.BuildConfig")); //添加未被调用的方法 Map<SootClass, Set<SootMethod>> hashMap = new HashMap<>(); for (SootClass sootClass : toAnalysisClasses){ if (sootClass.getName().equals("dummyMainClass")) continue; Set<SootMethod> sootMethods = new HashSet<>(); for (SootMethod sootMethod : sootClass.getMethods()){ boolean isCalled = false; Iterator<Edge> iterator = Scene.v().getCallGraph().edgesInto(sootMethod); if (iterator.hasNext()){ isCalled = true; } if (!isCalled){ System.out.println("在类: " + sootClass.getName() + " 的方法: " + sootMethod.getName() + " 从未被调用"); sootMethods.add(sootMethod); } } hashMap.put(sootClass, sootMethods); } //删除未被调用的方法 for (Map.Entry<SootClass, Set<SootMethod>> entry : hashMap.entrySet()){ SootClass sootClass = entry.getKey(); Set<SootMethod> sootMethods = entry.getValue(); for (SootMethod sootMethod : sootMethods){ Scene.v().getSootClass(sootClass.getName()).removeMethod(sootMethod); System.out.println("删除类: " + sootClass.getName() + " 的方法: " + sootMethod.getName()); } } // 活跃变量分析去除无效赋值 for (SootClass sootClass : toAnalysisClasses){ if (sootClass.getName().equals("dummyMainClass")) continue; for (SootMethod sootMethod : sootClass.getMethods()) { CompleteUnitGraph graph = new CompleteUnitGraph(sootMethod.retrieveActiveBody()); LiveAnalysis liveAnalysis = new LiveAnalysis(graph); for (Unit unit : graph) { boolean toRemove = false; Set<String> flowAfter = liveAnalysis.getFlowAfter(unit); for (ValueBox box : unit.getDefBoxes()) { Value value = box.getValue(); for (String liveVariable : flowAfter){ if (liveVariable.equals(value.toString())){ toRemove = false; break; }else if (value instanceof InstanceFieldRef && liveVariable.equals(((InstanceFieldRef) value).getBase().toString())){ toRemove = false; break; } toRemove = true; } } if (toRemove){ System.out.println("在类: " + sootClass.getName() + " 的方法 " + sootMethod.getName() + " 中移除的语句为: " + unit); Scene.v().getCallGraph().removeAllEdgesOutOf(unit); } } } } //常量传播 List<Unit> toRemoveUnits = new ArrayList<>(); for (SootClass sootClass : toAnalysisClasses){ if (sootClass.getName().equals("dummyMainClass")) continue; for (SootMethod sootMethod : sootClass.getMethods()) { CompleteUnitGraph graph = new CompleteUnitGraph(sootMethod.retrieveActiveBody()); ConstantPropagation constantPropagation = new ConstantPropagation(graph); for (Unit unit : graph) { Map<String, Object> flowBefore = constantPropagation.getFlowBefore(unit); if (unit.branches()){ if (unit instanceof IfStmt){ Value condition = ((IfStmt)unit).getCondition(); Unit targetUnit = ((IfStmt)unit).getTarget(); if (condition instanceof EqExpr){ EqExpr eqExpr = (EqExpr) condition; }else if (condition instanceof GeExpr){ GeExpr geExpr = (GeExpr) condition; }else if (condition instanceof GtExpr){ GtExpr gtExpr = (GtExpr) condition; }else if (condition instanceof LeExpr){ LeExpr leExpr = (LeExpr) condition; Value op1 = leExpr.getOp1(); Value op2 = leExpr.getOp2(); if (flowBefore.containsKey(op1.toString()) && ((String)flowBefore.get(op1.toString())).equals("NAC")) continue; if (flowBefore.containsKey(op1.toString()) && ((String)flowBefore.get(op1.toString())).equals("Constant")){ System.out.println("该值来自上面的分支，无法直接判断！"); }else if(flowBefore.containsKey(op1.toString()) && ((String)flowBefore.get(op1.toString())).startsWith("@parameter")){ System.out.println("该变量为方法参数，无法在方法内部进行判断!"); Iterator<Edge> iterator = Scene.v().getCallGraph().edgesInto(sootMethod); while (iterator.hasNext()){ Edge edge = iterator.next(); int idx = (((String)flowBefore.get(op1.toString())).charAt(10)) - 48; Unit callEdge = edge.srcUnit(); InvokeExpr invokeExpr = ((InvokeStmt) callEdge).getInvokeExpr(); Value arg = invokeExpr.getArg(idx); if (((IntConstant)arg).value <= ((IntConstant)op2).value){ List<Unit> preds = graph.getPredsOf(targetUnit); for (Unit pred : preds){ System.out.println(pred); } } } }else if (flowBefore.containsKey(op1.toString()) && flowBefore.get(op1.toString()) instanceof IntConstant){ if (((IntConstant)flowBefore.get(op1.toString())).value <= ((IntConstant)op2).value){ RemoveUnit(toRemoveUnits, graph, unit); }else { toRemoveUnits.add(targetUnit); RemoveUnit(toRemoveUnits, graph, targetUnit); } } }else if (condition instanceof LtExpr){ LtExpr ltExpr = (LtExpr) condition; }else if (condition instanceof IntConstant){ if (((IntConstant)(condition)).value == 0) { toRemoveUnits.add(targetUnit); RemoveUnit(toRemoveUnits, graph, targetUnit); }else { RemoveUnit(toRemoveUnits, graph, unit); } } } if (unit instanceof SwitchStmt){ List<Unit> caseTargets = ((SwitchStmt) unit).getTargets(); Value key = ((SwitchStmt) unit).getKey(); if (flowBefore.containsKey(key.toString()) && ((String)flowBefore.get(key.toString())).equals("NAC")) continue; if (flowBefore.containsKey(key.toString()) && ((String)flowBefore.get(key.toString())).equals("Constant")){ System.out.println("该值来自上面的分支，无法直接判断！"); }else if(flowBefore.containsKey(key.toString()) && ((String)flowBefore.get(key.toString())).startsWith("@parameter")){ System.out.println("该变量为方法参数，无法在方法内部进行判断!"); }else if(key instanceof IntConstant){ Unit notRemove = ((SwitchStmt) unit).getTarget(((IntConstant)key).value); for (Unit caseTarget : caseTargets){ if (notRemove.toString().equals(caseTarget.toString())) continue; RemoveUnit(toRemoveUnits, graph, caseTarget); } } } } } } } } public static void RemoveUnit(List<Unit> toRemoveUnits, CompleteUnitGraph graph, Unit targetUnit) { Unit succ = graph.getSuccsOf(targetUnit).get(0); while (true){ toRemoveUnits.add(succ); if ((succ instanceof JGotoStmt) || (succ instanceof JReturnStmt) || (succ instanceof JReturnVoidStmt)) break; succ = graph.getSuccsOf(succ).get(0); } } public static void initializeFlowDroid(){ InfoflowAndroidConfiguration config = new InfoflowAndroidConfiguration(); config.setInspectSinks(false); config.setInspectSources(false); config.setCodeEliminationMode(InfoflowConfiguration.CodeEliminationMode.NoCodeElimination); config.getCallbackConfig().setCallbackAnalysisTimeout(120); config.getAnalysisFileConfig().setAndroidPlatformDir("D:\\Android SDK\\platforms"); config.getAnalysisFileConfig().setTargetAPKFile("C:\\Users\\守城\\Desktop\\Step2\\Lab_4.apk"); SetupApplication setupApplication = new SetupApplication(config); setupApplication.constructCallgraph(); } public static void initializeSoot(){ G.reset(); Options.v().set_prepend_classpath(true); Options.v().set_allow_phantom_refs(true); Options.v().set_src_prec(Options.src_prec_apk); Options.v().set_process_dir(Collections.singletonList("C:\\Users\\守城\\Desktop\\Step2\\Lab_4.apk")); Options.v().set_android_jars("D:\\Android SDK\\platforms"); Options.v().set_whole_program(true); List<String> excludeList = new ArrayList<>(); excludeList.add("java.*"); excludeList.add("javax.*"); excludeList.add("androidx.*"); Options.v().set_exclude(excludeList);//排除不需要分析的类和方法 Options.v().set_output_format(Options.output_format_jimple); Options.v().setPhaseOption("cg.spark", "on"); Scene.v().loadNecessaryClasses(); } public static class LiveAnalysis extends BackwardFlowAnalysis<Unit, Set<String>> { public LiveAnalysis(UnitGraph graph) { super(graph); doAnalysis(); } @Override protected Set<String> newInitialFlow() { return new HashSet<>(); } @Override protected Set<String> entryInitialFlow() { return new HashSet<>(); } @Override protected void merge(Set<String> in1, Set<String> in2, Set<String> out) { out.clear(); out.addAll(in1); out.addAll(in2); } @Override protected void copy(Set<String> source, Set<String> dest) { dest.clear(); dest.addAll(source); } @Override protected void flowThrough(Set<String> in, Unit unit, Set<String> out) { out.clear(); out.addAll(in); for (ValueBox box : unit.getDefBoxes()) { Value value = box.getValue(); if (value instanceof Local) { out.remove(((Local) value).getName()); } } for (ValueBox box : unit.getUseBoxes()){ Value value = box.getValue(); if (value instanceof Local){ out.add(((Local) value).getName()); } } } } public static class ConstantPropagation extends ForwardFlowAnalysis<Unit, Map<String, Object>> { public ConstantPropagation(UnitGraph graph) { super(graph); doAnalysis(); } @Override protected Map<String, Object> newInitialFlow() { return new HashMap<>(); } @Override protected Map<String, Object> entryInitialFlow() { Map<String, Object> map = new HashMap<>(); List<Value> valueList = ((UnitGraph)graph).getBody().getParameterRefs(); for (Value value : valueList){ String className = ((RefType) value.getType()).getClassName(); if (className.equals("java.lang.Integer") || className.equals("java.lang.String") || className.equals("java.lang.Boolean") || className.equals("java.lang.Byte") || className.equals("java.lang.Character") || className.equals("java.lang.Double") || className.equals("java.lang.Float") || className.equals("java.lang.Long") || className.equals("java.lang.Short")){ map.put(value.toString(), value.toString().substring(0, 11)); } } return map; } @Override protected void merge(Map<String, Object> in1, Map<String, Object> in2, Map<String, Object> out) { for (Map.Entry<String, Object> entry1 : in1.entrySet()){ String parameter1 = entry1.getKey(); for (Map.Entry<String, Object> entry2 : in2.entrySet()){ String parameter2 = entry2.getKey(); if (parameter1.equals(parameter2)){ out.put(parameter1, "Constant"); } } } } @Override protected void copy(Map<String, Object> source, Map<String, Object> dest) { dest.clear(); dest.putAll(source); } @Override protected void flowThrough(Map<String, Object> in, Unit unit, Map<String, Object> out) { out.clear(); out.putAll(in); boolean isConstant = false; boolean isConstantValue = true; boolean isParameter = false; String para = null; for (ValueBox box : unit.getUseBoxes()){ Value value = box.getValue(); // 判断 x = y - y 这种特殊情况 if (unit instanceof SubExpr && ((JSubExpr) unit).getOp1Box().getValue() == ((JSubExpr) unit).getOp2Box().getValue()){ isConstant = true; break; } if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).equals("NAC")){ isConstant = false; break; } if (value instanceof Constant || (out.containsKey(value.toString()) && ((String)out.get(value.toString())).startsWith("@parameter"))){ isConstant = true; if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).equals("Constant")) isConstantValue = false; if (out.containsKey(value.toString()) && ((String)out.get(value.toString())).startsWith("@parameter")){ isParameter = true; para = ((String)out.get(value.toString())).substring(0, 11); } } } if (isConstant && isConstantValue && !isParameter){ int constantValue = 0; // 单个赋值语句 if (unit instanceof JAssignStmt){ Value op = ((JAssignStmt)unit).getRightOp(); if (out.containsKey(op.toString())){ constantValue = (Integer)(out.get(op.toString())); }else if (op instanceof Constant){ constantValue = ((IntConstant)op).value; } } // 判断加法 if (unit instanceof AddExpr){ Value op1 = ((AddExpr) unit).getOp1(); Value op2 = ((AddExpr) unit).getOp2(); constantValue = ((IntConstant)op1).value + ((IntConstant)op2).value; } // 判断减法 if (unit instanceof SubExpr){ Value op1 = ((JSubExpr) unit).getOp1(); Value op2 = ((JSubExpr) unit).getOp2(); constantValue = ((IntConstant)op1).value - ((IntConstant)op2).value; } // 判断乘法 if (unit instanceof MulExpr){ Value op1 = ((MulExpr) unit).getOp1(); Value op2 = ((MulExpr) unit).getOp2(); constantValue = ((IntConstant)op1).value * ((IntConstant)op2).value; } // 判断除法 if (unit instanceof DivExpr){ Value op1 = ((DivExpr) unit).getOp1(); Value op2 = ((DivExpr) unit).getOp2(); constantValue = ((IntConstant)op1).value / ((IntConstant)op2).value; } // 判断取余 if (unit instanceof RemExpr){ Value op1 = ((RemExpr) unit).getOp1(); Value op2 = ((RemExpr) unit).getOp2(); constantValue = ((IntConstant)op1).value % ((IntConstant)op2).value; } // 判断与运算 if (unit instanceof AndExpr){ IntConstant op1 = (IntConstant) ((AndExpr) unit).getOp1(); IntConstant op2 = (IntConstant) ((AndExpr) unit).getOp2(); constantValue = op1.value & op2.value; } // 判断或运算 if (unit instanceof OrExpr){ IntConstant op1 = (IntConstant) ((OrExpr) unit).getOp1(); IntConstant op2 = (IntConstant) ((OrExpr) unit).getOp2(); constantValue = op1.value | op2.value; } // 判断异或运算 if (unit instanceof XorExpr){ IntConstant op1 = (IntConstant) ((XorExpr) unit).getOp1(); IntConstant op2 = (IntConstant) ((XorExpr) unit).getOp2(); constantValue = op1.value ^ op2.value; } // 判断左移 if (unit instanceof ShlExpr){ IntConstant op1 = (IntConstant) ((ShlExpr) unit).getOp1(); IntConstant op2 = (IntConstant) ((ShlExpr) unit).getOp2(); constantValue = op1.value << op2.value; } // 判断右移 if (unit instanceof ShrExpr){ IntConstant op1 = (IntConstant) ((ShrExpr) unit).getOp1(); IntConstant op2 = (IntConstant) ((ShrExpr) unit).getOp2(); constantValue = op1.value >> op2.value; } for (ValueBox box : unit.getDefBoxes()){ Value value = box.getValue(); out.put(value.toString(), constantValue); } }else if (isConstant && !isConstantValue){ for (ValueBox box : unit.getDefBoxes()){ Value value = box.getValue(); out.put(value.toString(), "Constant"); } }else if (isConstant && isParameter){ for (ValueBox box : unit.getDefBoxes()){ Value value = box.getValue(); out.put(value.toString(), para); } } else { for (ValueBox box : unit.getDefBoxes()){ Value value = box.getValue(); out.put(value.toString(), "NAC"); } } } } }

FlowDroid

参考

https://segmentfault.com/a/1190000019977434

介绍

FlowDroid(github链接)是目前对 Android app 进行污点分析效果最好的工具之一，数据流算法是基于IFDS算法实现的。 污点分析的目的其实很简单，就是为了检查应用中是否存在从污点源到泄漏点的数据流。 但是它的优点在于它构建的数据流精度很高，可以对上下文、流、对象和字段敏感，从而使得分析结果非常精确。

FlowDroid的常规配置如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

InfoflowAndroidConfiguration config = new InfoflowAndroidConfiguration();
//设置时限，避免陷入死循环
config.getCallbackConfig().setCallbackAnalysisTimeout(120);
//设置sdk中的platform路径
config.getAnalysisFileConfig().setAndroidPlatformDir(androidPlatformsPath);
//设置需要分析的apk的文件路径
config.getAnalysisFileConfig().setTargetAPKFile(apkFilePath)
SetupApplication setupApplication = new SetupApplication(config);
//构建CG
setupApplication.constructCallgraph();

InfoflowAndroidConfiguration config = new InfoflowAndroidConfiguration();
config.getCallbackConfig().setCallbackAnalysisTimeout(120);
config.getAnalysisFileConfig().setAndroidPlatformDir(androidPlatformsPath);
config.getAnalysisFileConfig().setTargetAPKFile(apkFilePath)
SetupApplication setupApplication = new SetupApplication(config);
setupApplication.constructCallgraph();

Soot中，CallGraph的算法选项主要包括：

1. CHA(Call Hierarchy Analysis)：默认的静态分析算法，基于类的继承关系分析方法调用；
2. RTA(Rapid Type Analysis)：基于CHA的分析算法，会预先分析虚函数表，提高精度；
3. VTA(Virtual Call Target Analysis)：基于RTA的分析算法，会分析方法内部的虚函数调用，进一步提高精度；
4. Spark：另一种基于CHA的算法，相对于CHA，Spark的性能更高，但精度可能会降低。

区别主要体现在精度和性能上，CHA是最基本的分析算法，精度较低，但相对而言，性能较高，适用于大型的代码库；而RTA和VTA在提高精度的同时，也增加了分析的时间成本，适用于小型的代码库或者需要更精确的分析场景；Spark在精度和性能上都相对于CHA有一定的提升，但精度仍然不及RTA和VTA。因此，在选择算法时需要根据具体的分析场景来决定使用哪种算法。

1
2
3
4
5
6
7
8
9
10
11
12

//Spark
Options.v().setPhaseOption("cg.spark", "on");
//CHA
Options.v().setPhaseOption("cg.cha", "on");
//RTA
Options.v().setPhaseOption("cg.spark", "on");
Options.v().setPhaseOption("cg.spark", "rta:true");
//On-fly-CG：在构建CG时，在遍历字节码的同时进行CG的构建，遇到一个方法调用时就添加一个对应的边。
Options.v().setPhaseOption("cg.spark", "on-fly-cg:false");
//VTA
Options.v().setPhaseOption("cg.spark", "on");
Options.v().setPhaseOption("cg.spark", "vta:true");

污点分析

做污点分析的配置如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

//sourceSinkFilePath是source点与sink点的声明文件
config.getAnalysisFileConfig().setSourceSinkFile(sourceSinkFilePath);
// apk中的dex文件有对方法数量的限制导致实际app中往往是多dex，不作设置将仅分析classes.dex
config.setMergeDexFiles(true);
//设置AccessPath的path长度限制，默认为5，设置-1表示不作限制
config.getAccessPathConfiguration().setAccessPathLength(-1);
//设置Abstractio的path长度限制，设置-1表示不作限制
config.getAccessPathConfiguration().setMaxAbstractionPathLength(-1);
SetupApplication setupApplication = new SetupApplication(config);
//设置Callback的声明文件
SetupApplication.setCallbackFile("AndroidCallbacks.txt");
setupApplication.calculateSourcesSinksEntrypoints("SourcesAndSinks.txt");
SetupApplication.runInfoflow();

• AccessPath 是程序中指向内存位置的一条路径。例如一个Java对象的字段可以被表示为对象的引用AccessPath的一部分。AccessPath的一些常见例子包括用于追踪对象属性的“this.field”、“array[index]”等等。
• Abstraction 是指在程序分析中，为了简化程序，将某些复杂的细节隐藏在某些更抽象的形式下。例如，可以将整个对象视为单个抽象值，而不考虑它的具体结构和属性。在这种情况下，抽象表示仅仅是一个值或一些值的集合，它们代表了一些具体的值的集合。这种简化可以加速程序分析的速度，但会牺牲一些准确性。

流程

• 进行FlowDroid的配置，需要加载SourcesAndSinks.txt、AndroidCallbacks.txt文件
• 对Soot进行配置初始化，需要加载CG配置
• 构建一个虚拟的main方法，添加到入口点（entrypoint）
• 遍历entrypoint收集回调函数
• 有可能还需要进入xml文件中做进一步的回调函数的分析
• 将SourceAndSink.txt文件中包含的source、sink点，封装到sourceSinkManager中
• 生成CG图，并以此生成ICFG图
• 接下来基于CG、ICFG，计算存在的source、sink
• 确认source到sink间是否存在连通的数据路径，如果存在则认为是一个风险点
• 最终输出结果

jimple

Jimple 是 soot 中最主要的中间表示，是一种三地址码（三地址码 Three-Address Code 也可简写为3AC，要求：指令右侧至多有一个操作符。）只需要大约15种不同的指令，例如：

1
2
3
4

t2 = a + b + 3
三地址码则表示为
t1 = a + b
t2 = t1 + 3

使用 r0，r1，r2….表示类型对象；i0，i1，i2…..表示基本数据类型变量；带有 $ 表示临时变量，如上面的 t2 的含义；@parameter 表示函数参数。

1
2
3
4

specialinvoke 	用于调用构造方法、父类方法、私有方法
virtualinvoke 	用于调用普通的成员方法
staticinvoke  	用于调用静态方法
interfaceinvoke 相对于virtualinvoke不做优化，需要额外检查接口的实现

其他部分与 smali 挺相像的，并且是很好理解的，直接看是十分容易明白的。直接看下面的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public class Loop {
    public static void main(String[] args) {
        int x = 0;
        for (int i=0;i<10;i++){
            x = x+1;
        }
    }
}


jimple：

public class Loop extends java.lang.Object
{

    public void <init>()
    {
        Loop r0;

        r0 := @this: Loop;

        specialinvoke r0.<java.lang.Object: void <init>()>();

        return;
    }

    public static void main(java.lang.String[])
    {
        java.lang.String[] r0;
        int i1;

        r0 := @parameter0: java.lang.String[];

        i1 = 0;

     label1:
        if i1 >= 10 goto label2;

        i1 = i1 + 1;

        goto label1;

     label2:
        return;
    }
}

在 jimple 代码中，开头是一个叫 Loop 的类继承了 java.lang.Object 类(默认的所有类的父类），然后是一个初始化的过程，生成默认的构造函数，默认会调用父类的构造函数(即 java.lang.Object )，接下来就是 main 函数，在源代码里 main 函数有一个 String[] args 的参数，这在 jimple 代码中就对应了一个声明的参数 r0，源代码中 for 循环里面的 i 在 jimple 代码中用 i1 指代，label1 里面的内容就是 for 循环的条件内容，只要不满足循环条件，用一个 goto 语句跳转到 label2。这里出现了一个有意思的现象，那就是源代码中 x 值的变化在 jimple 中被“优化”掉了，这是因为 x 是不活跃变量，所以会被优化。

do-while循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

jimple：

public class DoWhile extends java.lang.Object
{

    public void <init>()
    {
        DoWhile r0;

        r0 := @this: DoWhile;

        specialinvoke r0.<java.lang.Object: void <init>()>();

        return;
    }

    public static void main(java.lang.String[])
    {
        int[] r0;
        int $i0, i1;
        java.lang.String[] r1;

        r1 := @parameter0: java.lang.String[];

        r0 = newarray (int)[10];

        i1 = 0;

     label1:
        i1 = i1 + 1;

        $i0 = r0[i1];

        if $i0 < 10 goto label1;

        return;
    }
}

这里是给数据对象 arr 用 r0 来代替，并对它进行了初始化，接下来还是用 label 表示程序的位置，将每一次循环的条件都能表示出来。可以注意到：Do-While 循环是先进入循环执行对应的语句，再通过 if 语句进行循环的跳转。

Switch语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

public class SwitchExample {
    public static void main(String[] args) {
        int input = Integer.parseInt(args[0]);
        switch (input) {
            case 1:
                System.out.println("Case 1");
                break;
            case 2:
                System.out.println("Case 2");
                break;
            default:
                System.out.println("Default case");
                break;
        }
    }
}


Jimple:
public class SwitchExample extends java.lang.Object
{
    public void <init>() {
        SwitchExample r0;
        
        r0 := @this: SwitchExample;
        specialinvoke r0.<java.lang.Object: void <init>()>();
        return;
    }
    
    public static void main(java.lang.String[]) {
        java.lang.String[] r0;
        int i1, $i0;
        java.lang.String r2;
        java.io.PrintStream $r1;
        
        r0 := @parameter0: java.lang.String[];
        r2 = r0[0];
        staticinvoke <java.lang.Integer: int parseInt(java.lang.String)>(r2);
        i1 = $i0;
        
        lookupswitch(i1) {
            case 1: goto label1;
            case 2: goto label2;
            default: goto label3;
        }
        
    label1:
        $r1 = <java.lang.System: java.io.PrintStream out>;
        $r1.println("Case 1");
        goto label4;
        
    label2:
        $r1 = <java.lang.System: java.io.PrintStream out>;
        $r1.println("Case 2");
        goto label4;
        
    label3:
        $r1 = <java.lang.System: java.io.PrintStream out>;
        $r1.println("Default case");
        
    label4:
        return;
    }
}

在此Jimple代码示例中，switch 语句被转换为lookupswitch（或者tableswitch）指令，后面跟随着各个case标签的跳转指令。每个case标签下面的代码表示对应case的操作。在这个例子中，每个case都会调用System.out.println()来输出相应的字符串。

• lookupswitch是根据一个键值来匹配分支，这些键值是离散的，不一定是连续的整数。
• tableswitch则是基于一个偏移量来进行分支匹配，分支的键值必须是连续的整数。

方法调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public class MethodCall {
    public static void main(String[] args) {
        int a = 1;
        int b = 2;
        int c = foo(a,b);
    }

    static int foo(int x, int y){
        return x + y;
    }
}

jimple：

public class MethodCall extends java.lang.Object
{

    public void <init>()
    {
        MethodCall r0;

        r0 := @this: MethodCall;

        specialinvoke r0.<java.lang.Object: void <init>()>();

        return;
    }

    public static void main(java.lang.String[])
    {
        java.lang.String[] r0;

        r0 := @parameter0: java.lang.String[];

        staticinvoke <MethodCall: int foo(int,int)>(1, 2);

        return;
    }

    static int foo(int, int)
    {
        int i0, i1, $i2;

        i0 := @parameter0: int;

        i1 := @parameter1: int;

        $i2 = i0 + i1;

        return $i2;
    }
}

可以看到我们定义的方法 foo 在源代码和 jimple 源码中差不多，很好理解，就是用了一个中间变量来取得 i0 和 i1 的和，再将这个中间变量 $i2 返回。在 main 函数中使用 staticinvoke 表示静态方法的调用。