CG

PreviousDFA NextTabby 🔦

Last updated 7 months ago

Was this helpful?

CG

Call Graph

进行过程间分析（Interprocedural Analysis，跨函数分析）前需要有函数调用图。

调用图是程序中调用关系的一种表示方式

JVM中的几种调用指令👇

Static Call

Special Call

Virtual Call

instruction

invokestatic

invokespecial

invokeinterface、invokevirtual

receiver objects

√

description

static methods

constructors、private instance methods、superclass instance methods

other instance methods

target methods

≥1(polymorphism)

determinacy

Compile-time

Run-time

由于Java语言的多态特性，虚方法的调用是在动态执行时分派的，子类可能重写了父类的方法，我们无法通过静态分析确定实际调用的方法，因此只能做May Analysis。

SootUp目前提供了两种构建调用图的方法，分别是CHA和RTA

CHA

Class Hierarchy Analysis（CHA）是根据receiver variable的声明类型来解析virtual call的，需要有类继承树的信息。

A a = ...
a.foo()

这里变量a的声明类型是A，但实际上a可能new的是A类本身或者A的子类。

因此这里找的调用方法是A类的foo方法，以及所有能够继承到A类foo方法的子类重写的foo方法。

在SootUp中也提供了CHA的相关接口。

Best Practice

以下面程序为例

package org.demo;

class A {
    public void foo(){}
}

class B extends A {
}

class G extends A {
    public void foo() {}
}

class C extends B {
    public void foo() {}
}

class D extends B {
    public void foo() {}
}


public class test {
    public static void main(String[] args) {
        B b = new B();
        b.foo();
    }
}

继承关系如下：

IDEA -> navigate -> call hierarchy得到的结果如下：

下面用SootUp进行分析

ClassHierarchyAnalysisAlgorithm这个类实现了CHA算法

In this algorithm, every virtual call is resolved to the all implemented overwritten methods of subclasses in the entire class path

调用图的构建需要有一个入口方法，由入口方法逐步扩大 “reachable world”

ClassHierarchyAnalysisAlgorithm#initialize可以传入一个入口方法签名的列表，不传默认会寻找main方法

JavaClassPathAnalysisInputLocation inputLocation
    = new JavaClassPathAnalysisInputLocation("target/classes");
JavaView view = new JavaView(inputLocation);

JavaClassType classType = view.getIdentifierFactory().getClassType("org.demo.A");
TypeHierarchy typeHierarchy = view.getTypeHierarchy();
System.out.println("Subclasses of A: " + Arrays.toString(typeHierarchy.subclassesOf(classType).toArray()));

MethodSignature methodSignature = view.getIdentifierFactory().getMethodSignature(
    view.getIdentifierFactory().getClassType("org.demo.test"),
    "main",
    "void",
    Collections.singletonList("java.lang.String[]"));

ClassHierarchyAnalysisAlgorithm cha = new ClassHierarchyAnalysisAlgorithm(view);
CallGraph cg = cha.initialize(Collections.singletonList(methodSignature));
String cgStr = cg.exportAsDot();
Files.write(Paths.get("src/main/resources/CG.dot"), cgStr.getBytes());

// Subclasses of A: [org.demo.G, org.demo.B, org.demo.D, org.demo.C]

得到的调用图

显然比IDEA的准确一点。。。

Implementation

下面看一下SootUp中的实现

find entrypoints

创建一个ClassHierarchyAnalysisAlgorithm需要传入JavaView，其含有所有类和方法的数据。initialize不传参则会寻找main方法，具体就是遍历当前view中所有的类（除掉library class），找到方法签名符合main方法签名的方法。

public MethodSignature findMainMethod() {
    Set<SootClass> classes = new HashSet<>();
    for (SootClass aClass : view.getClasses()) {
        if (!aClass.isLibraryClass()) {
            classes.add(aClass);
        }
    }

    Collection<SootMethod> mainMethods = new HashSet<>();
    for (SootClass aClass : classes) {
        for (SootMethod method : aClass.getMethods()) {
            if (method.isStatic()&& method.getSignature().equals(
                JavaIdentifierFactory.getInstance()
                .getMethodSignature(
                    aClass.getType(), "main", "void",
 			Collections.singletonList("java.lang.String[]")))) 				{mainMethods.add(method);}
        }
    }

    return mainMethods.stream().findFirst().get().getSignature();
}

initialize

找到main方法后会将其作为entry point

initialize开始构造CG

final CallGraph constructCompleteCallGraph(View view, List<MethodSignature> entryPoints) {
    MutableCallGraph cg = initializeCallGraph();

    Deque<MethodSignature> workList = new ArrayDeque<>(entryPoints);
    Set<MethodSignature> processed = new HashSet<>();

    // implicit edge from entry point to static initializer
    addImplicitEdgesOfEntryPoints(entryPoints, cg, workList);

    processWorkList(view, workList, processed, cg);
    return cg;
}

worklist是Queue的一个具体实现Deque（Double Ended Queue，双端队列）

注意这里worklist中的元素是方法签名而非方法语句。

将entryPoints添加到worklist中。

这里就有一点比较tricky的，构造调用图的时候还是考虑到了Java语言的特性

addImplicitEdgesOfEntryPoints首先会找entry point方法所在类是否有静态初始化方法，即<clinit>方法，接着把entry point方法和<clinit>方法都加入CG，再加个entry point到<clinit>的调用边，并把<clinit>方法加入到worklist

worklist process

接下来就是worklist算法启动，processed集合用于记录已经reach到的方法

从worklist里pop出一个方法签名，如果已经在processed集合里，就不进行处理。

找出当前方法签名所在类，对方法进行预处理（preProcessingMethod，这是一个抽象方法，由AbstractCallGraphAlgorithm子类实现），将当前方法签名加入CG。

找出当前方法中所有调用语句指向的callee（resolveAllCallsFromSourceMethod）

sourceMethod.getBody().getStmts().stream()
    .filter(Stmt::containsInvokeExpr)
    .flatMap(s -> resolveCall(sourceMethod, s.getInvokeExpr()));

解析这些方法调用（resolveCall由子类实现）

resolveCall

下面便是CHA的核心算法👇

MethodSignature targetMethodSignature = invokeExpr.getMethodSignature();
if ((invokeExpr instanceof JDynamicInvokeExpr)) {
    return Stream.empty();
}

SootMethod targetMethod = findConcreteMethod(view, targetMethodSignature).orElse(null);

if (targetMethod == null
    || MethodModifier.isStatic(targetMethod.getModifiers())
    || (invokeExpr instanceof JSpecialInvokeExpr)) {
    return Stream.of(targetMethodSignature);
} else {
    ArrayList<ClassType> noImplementedMethod = new ArrayList<>();
    List<MethodSignature> targets =
        resolveAllCallTargets(targetMethodSignature, noImplementedMethod);
    if (!targetMethod.isAbstract()) {
        targets.add(targetMethod.getSignature());
    }
    if (invokeExpr instanceof JInterfaceInvokeExpr) {
        IdentifierFactory factory = view.getIdentifierFactory();
        noImplementedMethod.stream()
            .map(
            classType ->
            resolveConcreteDispatch(
                view,
                factory.getMethodSignature(
                    classType, targetMethodSignature.getSubSignature())))
            .filter(Optional::isPresent)
            .map(Optional::get)
            .forEach(targets::add);
    }
    return targets.stream();
}

CHA中，通过receiver object的声明类的类结构来获取所有可能的调用目标，声明类的每个子类，只要有调用方法的实现（不管是继承得到的还是重写的），都会被考虑为调用目标。

dispatch

findConcreteMethod会对方法进行dispatch，即从自身往父类上找，直到找到方法被实现的地方。

superClassesOf并不能得到接口的父接口。

这里还考虑了一个Java语言的另一个feature

Java中接口是可以多继承的（类就不可以）
而且接口声明的方法不一定要被实现（默认方法default和静态方法static可以不被实现）
注意，default方法虽然被default修饰，但访问级别是public的

package org.demo;

public interface inter1 {
    default void hack(){
        System.out.println("hack inter1");
    }
}

public interface inter2 {}

public interface inter3 extends inter1, inter2 {
    default void hack(){
        System.out.println("hack inter3");
    }
}

class A implements inter3

implementedInterfacesOf会找到当前类实现的所有接口，包括父类所实现的接口，以及接口所继承的父接口。（如果传入的classType是接口，也能找到其继承的接口）

在这些接口中寻找子签名对应的方法，并获取最小的那个接口中的方法（最小即继承结构最底端，因为对于default方法，子接口是可以重写的）

B b = new B(); b.hack()

这里得到的是<org.demo.inter3: void hack()>

能走到这一步要么是receiver object的声明类是接口，调用的是接口的普通方法
要么调用的是接口的默认方法或静态方法

inter3 b = new B(); b.hack();

改成inter1中声明普通方法，A类实现hack接口

这里得到的便是<org.demo.inter1: void hack()>

specialinvoke&staticinvoke

dispatch之后便对调用类型进行判断

SootMethod targetMethod = findConcreteMethod(...);

if (targetMethod == null
    || MethodModifier.isStatic(targetMethod.getModifiers())
    || (invokeExpr instanceof JSpecialInvokeExpr)) {
    return Stream.of(targetMethodSignature);

感觉这里的逻辑有问题，invoke static/invoke special的一些特殊情况需要dispatch

super和静态方法的调用可能是目标继承得到的方法，通过原方法签名不能直接获取到，不能直接返回targetMethodSignature，而应该返回findConcreteMethod的得到的targetMethod的签名。

virtualinvoke

我们主要关注虚方法的调用

subtypesOf遍历子类（适用于接口）找非抽象的实现方法

如果子类中没找到这个方法，即子类没有实现它并且子类不是接口，就将子类加入noImplementedMethod

接着看子类实现的接口中，如果有子签名对应的默认方法，也加入targets

这里getInterfaces得到的是类声明时明确写的implements后面跟的接口，是直接实现的接口，而非继承得到的。

这么操作的意图不是很懂。。。感觉会引入假的调用边。个人觉得这里的顺序应该这样，先在当前子类拿到method，拿不到再尝试接口的default方法，再拿不到才加入noImplementedMethod

interfaceinvoke

接着判断若是invoke interface，则将上面noImplementedMethod再进行dispatch

resolveConcreteDispatch还是调的findConcreteMethod