Tai-e 分析之IR

两位老师在介绍Tai-e的时候，都会提到Tai-e的IR设计，会比Soot的更直观，这里具体看看Tai-e的IR设计及实现。

还是先给个老师演示Tai-e的IR例子。

0x01 Tai-e IR

1.1 Soot VS Tai-e

upload successful

1.2 重点结构

  • JClass（在pascal.taie.language.classes）表示程序中的类。每个实例包含类的各种信息，如类名、修饰符、声明的方法和字段等。
  • JMethod 和 JField：（在pascal.taie.language.classes）：表示程序中的类成员，即方法和字段。每个 JMethod/JField 实例都包含方法/字段的各种信息，如声明类、名称等。
  • ClassHierarchy（在pascal.taie.language.classes）：管理程序中的所有类。它提供了查询类层次信息的API，如方法分派、子类检查等。
  • Type（在pascal.taie.language.type）：表示程序中的类型。它有几个子类，如 PrimitiveType、ClassTyp 和 ArrayType，代表不同类型的 Java 类型。
  • TypeSystem（在pascal.taie.language.type）：提供用于检索特定类型和子类检查的API。
  • World（在pascal.taie）：管理整个程序的信息。通过使用它的获取器，你可以访问这些信息，例如ClassHierarchy 和TypeSystem。World 本质上是一个单例类，可以通过调用 World.get() 获得实例。

这几个都很重要，是阅读Tai-e代码，了解Tai-e实现的基础。

1.3 Tai-e IR

Tai-e 的IR 基于类型、3地址码、Java方法的语句（statement）和表达式（expression）。

重要的三个核心类：

  • IR 是 Tai-e 中间表示的核心数据结构，每个 IR 实例都可以看作是特定方法主体信息（如变量、参数、语句等）的容器。您可以通过 JMethod.getIR()（只要方法不是抽象的）轻松获取方法的 IR 实例。
  • Stmt 表示程序中的所有语句。该接口有十几个子类，分别对应不同的语句。Stmt 保存在IR 中，可以通过 IR.getStmts() 获取。
  • Exp 表示程序中的所有表达式。该接口有几十个子类，分别对应各种表达式。Exp 与Stmts 关联，可以通过Stmt 的特定API 获取。

详细的Expr和Stmt子类就不贴在这里了，可以直接看参考【1】中的原文

1.4 Demo

看个例子，InvokeDemo.java

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
import java.lang.reflect.Method;

public class InvokeDemo {
    private String name;

    InvokeDemo(String name){
        this.name = name;
    }

    public void echoName(){
        System.out.println("echo by echoName: " + this.name);
    }

    public void echo(String content){
        System.out.println("echo by echo: " + content);
    }

    public static void main(String[] args) throws Exception {
        String content = args[0];
        String methodNmae = args[1];
        InvokeDemo tt = new InvokeDemo(content);
        // 1. 测试污点为参数
        Method method = tt.getClass().getMethod("echo", String.class);
        method.invoke(tt, content);

        // 2. 测试污点为method
        Method method2 = tt.getClass().getMethod(methodNmae);
        method2.invoke(tt);

        // 3. 测试类型
        Object tt3 = new InvokeDemo(content);
        Method method3 = tt3.getClass().getMethod("echo", String.class);
        method3.invoke(tt3, content);
    }
}

指定-a ir-dumper

1
java -jar tai-e-all.jar -cp ./InvokeDemoPath -pp --main-class InvokeDemo -ap -a ir-dumper

Tai-e IR 如下：

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
public class InvokeDemo extends java.lang.Object {

    private java.lang.String name;

    void <init>(java.lang.String r1) {
        [0@L7] invokespecial %this.<java.lang.Object: void <init>()>();
        [1@L8] %this.<InvokeDemo: java.lang.String name> = r1;
        [2@L9] return;
    }

    public void echoName() {
        java.io.PrintStream $r2;
        java.lang.String $r1, $r3;
        [0@L12] $r2 = <java.lang.System: java.io.PrintStream out>;
        [1@L12] $r1 = %this.<InvokeDemo: java.lang.String name>;
        [2@L12] $r3 = invokedynamic <java.lang.invoke.StringConcatFactory: java.lang.invoke.CallSite makeConcatWithConstants(java.lang.invoke.MethodHandles$Lookup,java.lang.String,java.lang.invoke.MethodType,java.lang.String,java.lang.Object[])> "makeConcatWithConstants" <MethodType: java.lang.String (java.lang.String)>["echo by echoName: "]($r1);
        [3@L12] invokevirtual $r2.<java.io.PrintStream: void println(java.lang.String)>($r3);
        [4@L13] return;
    }

    public void echo(java.lang.String r0) {
        java.io.PrintStream $r1;
        java.lang.String $r2;
        [0@L16] $r1 = <java.lang.System: java.io.PrintStream out>;
        [1@L16] $r2 = invokedynamic <java.lang.invoke.StringConcatFactory: java.lang.invoke.CallSite makeConcatWithConstants(java.lang.invoke.MethodHandles$Lookup,java.lang.String,java.lang.invoke.MethodType,java.lang.String,java.lang.Object[])> "makeConcatWithConstants" <MethodType: java.lang.String (java.lang.String)>["echo by echo: "](r0);
        [2@L16] invokevirtual $r1.<java.io.PrintStream: void println(java.lang.String)>($r2);
        [3@L17] return;
    }

    public static void main(java.lang.String[] r0) {
        java.lang.String r1, r2, %stringconst3;
        int %intconst0, %intconst1;
        InvokeDemo $r3;
        java.lang.Class $r4, %classconst2, $r8;
        java.lang.Class[] $r5, $r9;
        java.lang.reflect.Method $r6, $r10;
        java.lang.Object[] $r7, $r11;
        [0@L20] %intconst0 = 0;
        [1@L20] r1 = r0[%intconst0];
        [2@L21] %intconst1 = 1;
        [3@L21] r2 = r0[%intconst1];
        [4@L22] $r3 = new InvokeDemo;
        [5@L22] invokespecial $r3.<InvokeDemo: void <init>(java.lang.String)>(r1);
        [6@L24] $r4 = invokevirtual $r3.<java.lang.Object: java.lang.Class getClass()>();
        [7@L24] $r5 = newarray java.lang.Class[%intconst1];
        [8@L24] %classconst2 = java.lang.String.class;
        [9@L24] $r5[%intconst0] = %classconst2;
        [10@L24] %stringconst3 = "echo";
        [11@L24] $r6 = invokevirtual $r4.<java.lang.Class: java.lang.reflect.Method getMethod(java.lang.String,java.lang.Class[])>(%stringconst3, $r5);
        [12@L25] $r7 = newarray java.lang.Object[%intconst1];
        [13@L25] $r7[%intconst0] = r1;
        [14@L25] invokevirtual $r6.<java.lang.reflect.Method: java.lang.Object invoke(java.lang.Object,java.lang.Object[])>($r3, $r7);
        [15@L28] $r8 = invokevirtual $r3.<java.lang.Object: java.lang.Class getClass()>();
        [16@L28] $r9 = newarray java.lang.Class[%intconst0];
        [17@L28] $r10 = invokevirtual $r8.<java.lang.Class: java.lang.reflect.Method getMethod(java.lang.String,java.lang.Class[])>(r2, $r9);
        [18@L29] $r11 = newarray java.lang.Object[%intconst0];
        [19@L29] invokevirtual $r10.<java.lang.reflect.Method: java.lang.Object invoke(java.lang.Object,java.lang.Object[])>($r3, $r11);
        [20@L36] return;
    }
}

0x02 IR的实现

虽然Tai-e 拿Soot 做对比，但是实际上Tai-e 也是在Soot 基础之上，通过Transfromer接口实现Soot IR 到Tai-e IR 转化。

2.1 World

World 是个很重要的Tai-e 实现类，它存着整个分析程序的IR信息，它是一个final class，里面有很多结构，这里一一简单介绍下：

  • World: static，通过getWorld() 获取
  • options: 配置
  • typeSystem: 类型关系
  • classHierarchy: 类层次结构
  • irBuilder: 生成IR，重点
  • nativeModel:
  • mainMethod: 指定的main方法
  • implicitEntries: 隐式入口，比如Thread.run(这个在CodeQL是没有的)

2.2 buildWorld

问题：World 是如何生成的呢？

先看下调用栈，如下：

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
build:197, SootWorldBuilder (pascal.taie.frontend.soot)
internalTransform:130, SootWorldBuilder$1 (pascal.taie.frontend.soot)
transform:36, SceneTransformer (soot)
apply:105, Transform (soot)
internalApply:37, ScenePack (soot)
apply:118, Pack (soot)
runWholeProgramPacks:620, PackManager (soot)
runPacksNormally:500, PackManager (soot)
runPacks:425, PackManager (soot)
run:266, Main (soot)
runSoot:256, SootWorldBuilder (pascal.taie.frontend.soot)
build:84, SootWorldBuilder (pascal.taie.frontend.soot)
lambda$buildWorld$3:132, Main (pascal.taie)
run:-1, Main$$Lambda$139/0x0000000800dc8000 (pascal.taie)
lambda$runAndCount$0:112, Timer (pascal.taie.util)
get:-1, Timer$$Lambda$110/0x0000000800d2b680 (pascal.taie.util)
runAndCount:93, Timer (pascal.taie.util)
runAndCount:111, Timer (pascal.taie.util)
runAndCount:107, Timer (pascal.taie.util)
buildWorld:124, Main (pascal.taie)
lambda$main$0:60, Main (pascal.taie)
run:-1, Main$$Lambda$109/0x0000000800d2b228 (pascal.taie)
lambda$runAndCount$0:112, Timer (pascal.taie.util)
get:-1, Timer$$Lambda$110/0x0000000800d2b680 (pascal.taie.util)
runAndCount:93, Timer (pascal.taie.util)
runAndCount:111, Timer (pascal.taie.util)
runAndCount:107, Timer (pascal.taie.util)
main:52, Main (pascal.taie)

2.2.1 SootWorldBuilder#build1

具体逻辑在SootWorldBuilder中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void build(Options options, List<AnalysisConfig> analyses) {
        initSoot(options, analyses, this);
        // set arguments and run soot
        List<String> args = new ArrayList<>();
        // set class path
        Collections.addAll(args, "-cp", getClassPath(options));
        // set main class
        String mainClass = options.getMainClass();
        if (mainClass != null) {
            Collections.addAll(args, "-main-class", mainClass, mainClass);
        }
        // add input classes
        args.addAll(getInputClasses(options));
        runSoot(args.toArray(new String[0]));
    }

这里首先可以看看runSoot的实现，其实就是调用Soot进行分析

1
2
3
4
5
private static void runSoot(String[] args) {
    try {
        soot.Main.v().run(args);
    } catch (SootResolver.SootClassNotFoundException e) {
    ...

整个build逻辑可以分为三部分

  1. 初始化soot参数，initSoot
  2. 获取待分析的类，并组合成soot.Main 的参数
  3. 执行soot分析

2.2.2 initSoot

那么具体的逻辑就是Soot的执行了，返回去看看Soot是怎么配置的，具体在initSoot方法中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void initSoot(Options options, List<AnalysisConfig> analyses,
                             SootWorldBuilder builder) {
    // reset Soot
    G.reset();
    soot.options.Options.v().set_output_dir...
    ...
    Transform transform = new Transform(
            "wjtp.tai-e", new SceneTransformer() {
        @Override
        protected void internalTransform(String phaseName, Map<String, String> opts) {
            builder.build(options, Scene.v());
        }
    });
    PackManager.v()
            .getPack("wjtp")
            .add(transform);

重点逻辑是Soot 的Transform 接口。

在soot.Main.v().run(args) 过程中，会执行PackManager.v().runPacks()，其会调用所有的transfrom接口。

Transform中的builder 还是SootWorldBuilder，通过transfrom 接口执行build，不过这个build方法不是上面的那个了，参数不同。

2.2.3 SootWorldBuilder#build2

注意和上面的那个build不同。

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
private void build(Options options, Scene scene) {
	// 初始化
    World.reset();
    World world = new World();
    World.set(world);

    // options will be used during World building, thus it should be
    // set at first.
    world.setOptions(options);
    // initialize class hierarchy
    ClassHierarchy hierarchy = new ClassHierarchyImpl();
    SootClassLoader loader = new SootClassLoader(
            scene, hierarchy, options.isAllowPhantom());
    hierarchy.setDefaultClassLoader(loader);
    hierarchy.setBootstrapClassLoader(loader);
    world.setClassHierarchy(hierarchy);
    // initialize type manager
    TypeSystem typeSystem = new TypeSystemImpl(hierarchy);
    world.setTypeSystem(typeSystem);
    // initialize converter
    Converter converter = new Converter(loader, typeSystem);
    loader.setConverter(converter);
    // build classes in hierarchy
    // 注意这里，对class关系进行构建，保存在ClassHierarchy中
    buildClasses(hierarchy, scene);
    // set main method
    if (options.getMainClass() != null) {
        if (scene.hasMainClass()) {
            world.setMainMethod(
                    converter.convertMethod(scene.getMainMethod()));
        } else {
            logger.warn("Warning: main class '{}'" +
                            " does not have main(String[]) method!",
                    options.getMainClass());
        }
    } else {
        logger.warn("Warning: main class was not given!");
    }
    // set implicit entries
    world.setImplicitEntries(implicitEntries.stream()
            .map(hierarchy::getJREMethod)
            // some implicit entries may not exist in certain JDK version,
            // thus we filter out null
            .filter(Objects::nonNull)
            .toList());
    // initialize IR builder
    world.setNativeModel(getNativeModel(typeSystem, hierarchy, options));
    IRBuilder irBuilder = new IRBuilder(converter);
    world.setIRBuilder(irBuilder);
    if (options.isPreBuildIR()) {
        irBuilder.buildAll(hierarchy);
    }
}

可以看到，这里对World进行初始化。

赋值呢？

1. World.ClassHierarchy

1
2
3
4
5
protected static void buildClasses(ClassHierarchy hierarchy, Scene scene) {
    // TODO: parallelize?
    new ArrayList<>(scene.getClasses()).forEach(c ->
            hierarchy.getDefaultClassLoader().loadClass(c.getName()));
}

2. World.irBuilder

在最后，如果prebuildIR为true，通过irBuilder = new IRBuilder(converter); & irBuilder.buildAll(hierarchy); 进行了tai-e IR构建。

如果prebuildIR false呢，只是不在这里构建IR，而是在后续以需要的时候构建，在pta指针分析中，其调用栈如下：

1
2
3
4
5
6
7
8
build:209, MethodIRBuilder (pascal.taie.frontend.soot)
buildIR:53, IRBuilder (pascal.taie.frontend.soot)
getIR:192, JMethod (pascal.taie.language.classes)
setSolver:91, ThreadHandler (pascal.taie.analysis.pta.plugin)
lambda$setSolver$0:94, CompositePlugin (pascal.taie.analysis.pta.plugin)
accept:-1, CompositePlugin$$Lambda$239/0x0000000800eb1288 (pascal.taie.analysis.pta.plugin)
forEach:1511, ArrayList (java.util)
setSolver:94, CompositePlugin

一直要在当需要获取当前节点的IR时，进行build。

2.2.4 Converter逻辑

Tai-e的IR和Soot的IR是不一样的，但是一开始Tai-e又用到soot去获取待分析jar的类、IR等信息，具体在哪里作的转换呢？

pascal.taie.frontend.soot目录

1
2
3
4
5
6
7
8
9
├── Converter.java
├── IRBuilder.java
├── MethodIRBuilder.java
├── Modifiers.java
├── SootClassBuilder.java
├── SootClassLoader.java
├── SootFrontendException.java
├── SootWorldBuilder.java
└── VarManager.java

在上面的World.irBuilder 例子中，就是将SootMethod转化为Tai-e IR。

MethodIRBuilder#build

MethodIRBuilder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
IR build() {
    SootMethod m = (SootMethod) method.getMethodSource();
    Body body = m.retrieveActiveBody();
    m.releaseActiveBody(); // release body to save memory
    varManager = new VarManager(method, converter);
    if (method.getReturnType().equals(VOID)) {
        returnVars = Set.of();
    } else {
        returnVars = Sets.newLinkedSet();
    }
    stmts = new ArrayList<>();
    if (!method.isStatic()) {
        buildThis(body.getThisLocal());
    }
    buildParams(body.getParameterLocals());
    preprocessTemps(body,
            tempToDef = Maps.newHybridMap(),
            unusedInvokeTempRets = Sets.newHybridSet());
    buildStmts(body);
    buildExceptionEntries(body);
    return new DefaultIR(method,
            varManager.getThis(), varManager.getParams(), returnVars,
            varManager.getVars(), stmts, exceptionEntries);
}

其他的Soot IR也类似，不赘述。

0x03 拓展

3.1 World应用

World 在哪些地方用到呢？

3.2 Main 限制

Y4er师傅的文章中也提到了Tai-e 在PTA 分析中的Main 函数限制怎么突破，其实我们从以上的逻辑中，不难发现Main函数的限制是怎么产生的：

  1. upload successful
  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public void onStart() {
        // process program main method
        JMethod mainMethod = World.get().getMainMethod();
        if (mainMethod != null) {
            solver.addEntryPoint(new EntryPoint(mainMethod,
                    new MainEntryPointParamProvider(mainMethod, solver)));
        }
        // process implicit entries
        if (solver.getOptions().getBoolean("implicit-entries")) {
            for (JMethod entry : World.get().getImplicitEntries()) {
                solver.addEntryPoint(new EntryPoint(entry, EmptyParamProvider.get()));
            }
        }
    }

疑问？soot只有一个MainMethod吗？多个怎么办？

如何突破Main限制，可以看Y4er师傅提到的参考【3】

TODO: 如何解决Y4er师傅提到的Main Entry问题？

3.3 implicit Entries 隐式入口

upload successful

AbstractWorldBuilder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public abstract class AbstractWorldBuilder implements WorldBuilder {
    protected static final List<String> implicitEntries = List.of(
            "<java.lang.System: void initializeSystemClass()>",
            "<java.lang.Thread: void <init>(java.lang.ThreadGroup,java.lang.Runnable)>",
            "<java.lang.Thread: void <init>(java.lang.ThreadGroup,java.lang.String)>",
            "<java.lang.Thread: void exit()>",
            "<java.lang.ThreadGroup: void <init>()>",
            "<java.lang.ThreadGroup: void <init>(java.lang.ThreadGroup,java.lang.String)>",
            "<java.lang.ThreadGroup: void uncaughtException(java.lang.Thread,java.lang.Throwable)>",
            "<java.lang.ClassLoader: void <init>()>",
            "<java.lang.ClassLoader: java.lang.Class loadClassInternal(java.lang.String)>",
            "<java.lang.ClassLoader: void checkPackageAccess(java.lang.Class,java.security.ProtectionDomain)>",
            "<java.lang.ClassLoader: void addClass(java.lang.Class)>",
            "<java.lang.ClassLoader: long findNative(java.lang.ClassLoader,java.lang.String)>",
            "<java.security.PrivilegedActionException: void <init>(java.lang.Exception)>"
    );

实际jdk17下
upload successful

分析完毕，输出统计信息
upload successful

0x04 参考

  1. Program Abstraction in Tai-e (core classes and IR)
  2. Tai-e:基于程序分析的安全漏洞检测框架
  3. How to analyze java web or spring project(by:Y4er)
  4. 静态程序分析框架“太阿”的设计之道

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true