所有文章 标签 分类

Class Hierarchy Analysis 算法: 快速生成调用图

MartinLwx  收录于  类别 Program-Analysis
     约 2328 字  预计阅读 5 分钟 

对于 OOP 语言来说，搭建调用图的核心问题是有多态的场景下如何确定到底是哪一个方法被调用了，下面是 Java 的一些可能的函数调用 1

Static Call Special Call Virtual Call
Instruction invokestatic invokespecial invokeinterface, invokevirtual
Receiver Objects ❌ ✅ ✅
Target Methods Static Method Constructor, Private Instance Method, Superclass Instance Method Other Instance Method
Count of Possible Target Methods 1 1 $\ge 1$ (polymorphism)
Determinancy Compile-time Compile-time Run-time

其中 Virtual Call 因为包含了多态，方法调用存在多个可能的目标方法

以 Java 语言为例，可能存在如下的方法调用

java

A a = ...
a.foo()

上面的方法调用是 a.foo()，调用者是 a，a 的声明类型是 A

对于方法，我们最关心的是它的方法签名，即方法的唯一 ID，它包含如下的要素 2

  • Class Type: 调用者的声明类型
  • " 子签名 "
    • Method Name: 方法的名字，在这个例子中就是 foo
    • Return Type: 方法的返回类型
    • Parameter Types: 方法每个入参的类型

这里的“子签名”不包含 Class Type，后面在 CHA 算法里面会看到它的用处

为了方便，这里为方法签名引入记号 2：

java

<Class Type>: <Return Type> <Method Name>(<Parameter Types>)

那么上面的 a.foo() 的记号就是 A: foo()

类层次结构分析（Class Hierarchy Analysis，CHA）算法的核心思想是根据方法调用里面的调用者（Receive Variable）的声明类型（Declarative Type）推导到底调用了哪个（些）方法，后面会展开来说是什么意思

顾名思义，CHA 是基于类层次结构的分析，那么使用 CHA 的前提是类的层次结构是已知的，另外 CHA 假设：调用者可能指向它的声明类型，也可能是声明类型的子类

Tip

有时候，调用者的声明类型可能是一个接口，那么此时 CHA 假设调用者可能指向所有实现了这个接口的类

CHA 算法只要记住 2 个函数即可，$\texttt{Dispatch}$ 和 $\texttt{Resolve}$

输入

  • 当前考虑的类 $c$
  • 方法签名 $m$

输出：实际上被调用的方法

算法：对于 $\texttt{Dispatch}(c,m)$

  • 如果类 $c$ 里面有非抽象方法 符合方法签名 $m$（这里不需要考虑方法签名 $m$ 的 Class Type，这也是前面为啥单独把“子类型“单独列出来），那么就找到了实际上被调用的方法，直接返回该方法
  • 否则，调用 $\texttt{Dispatch}(c’,m)$，这里的 $c’$ 是 $c$ 的父类

总结：$\texttt{Dispatch}$ 很好理解，其实它和我们自己肉眼确定 OOP 语言的某个方法调用实际上被调用的方法是一致的

Tip

简单来说，call site 就是方法调用所在的语句

输入：call site

输出：所有这个 call site 可能调用的方法集合

算法：

  • 初始化集合 $T$ 为空
  • 定义 $m$ 为 call site 的方法签名
  • 分情况
    • 如果 $m$ 是静态方法调用，直接返回 ${ m }$
    • 如果 $m$ 是普通实例方法调用（非 Virtual Call），拿出 $m$ 的声明类型 $c^m$ ，那么 $T= {\texttt{Dispatch}(c^m, m)}$
    • 如果 $m$ 是 Virtual Call，那么取出 call site 调用者的声明类型（记为 $c$），对于 $c$ 以及的每一个子类 $c’$，调用 $\texttt{Dispatch}(c’, m)$ 并把结果加到 $T$ 里面。

总结：CHA 算法对待 Virtual Call 的方法很粗暴也很直接，直接枚举所有可能的情况，它认为实际的调用者可能是声明类型的实例，也可能是声明类型的子类（直接或间接）的实例

输入：Entry Method，Java 的话就是 main 方法

输出：调用图

算法：

  • 初始化
    • $\texttt{WorkList} = {Entry\ Method}$，存储着要处理的方法
    • $\texttt{CG} = \emptyset$，表示调用图，可以用边的集合表示调用图
    • $\texttt{RM} = \emptyset$，表示可达的方法，同时也起到了哈希表的作用，只要方法进入到 $\texttt{RM}$ 那就表示处理过了
  • 只要 $\texttt{WorkList}$ 非空
    • 取出 1 个方法，记为 $m$
    • 如果 $m$ 不在 $\texttt{RM}$ 里面，也就是还没有访问过
      • 把 $m$ 加到 $\texttt{RM}$ 里面
      • 对于方法 $m$ 的每一个 call site $cs$
        • $T=\texttt{Resolve}(cs)$
        • 对于集合 $T$ 里面的每一个方法 $m'$
          • 把调用边 $cs\rightarrow m’$ 添加到 $\texttt{CG}$ 里面
          • 把方法 $m’$ 添加到 $\texttt{WorkList}$ 里面
  • 返回 $\texttt{CG}$

最近因为工作需要在看 ArkAnalyzer 的源码 3，里面刚好有 CHA 算法的例子，下面来看看到底是如何实现的，源码仓挂在了 Gitee 上，链接在 这里

Tip

下面的代码经过省略，只显示跟 CHA 算法有关的部分

先看方法签名的类 MethodSignature

ts

export class MethodSignature {
    private declaringClassSignature: ClassSignature;
    private methodSubSignature: MethodSubSignature;
    ...
}

它的 2 个成员分别是 ClassSignature 和 MethodSubSignature

ts

export class ClassSignature {
    private declaringFileSignature: FileSignature;
    private className: string;
    ...
}

export class MethodSubSignature {
    private methodName: string;
    private parameters: MethodParameter[];
    private returnType: Type;
    private staticFlag: boolean;
}

ClassSignature + MethodSubSignature 的 methodName, parameters, returnType 刚好就是我们前面提到的方法签名的构成

入口函数是 makeCallGraphCHA 函数，入参是一堆 Entry Points，用方法签名表示

ts

public makeCallGraphCHA(entryPoints: MethodSignature[]): CallGraph {
    let callGraph = new CallGraph(this);
    let callGraphBuilder = new CallGraphBuilder(callGraph, this);
    callGraphBuilder.buildClassHierarchyCallGraph(entryPoints);
    return callGraph;
}

public buildClassHierarchyCallGraph(entries: Method[], displayGeneratedMethod: boolean = false): void {
    ...
    let classHierarchyAnalysis: ClassHierarchyAnalysis = 
        new ClassHierarchyAnalysis(this.scene, this.cg);
    classHierarchyAnalysis.start(displayGeneratedMethod);
}

可以看到 classHierarchyAnalysis.start 启动了 CHA 算法，下面是这个方法的内容

ts

protected init(): void {
    this.processedMethod = new Set();
    this.cg.getEntries().forEach((entryFunc) => {
        this.workList.push(entryFunc);
    })
}

public start(displayGeneratedMethod: boolean): void {
    this.init();
    while (this.workList.length !== 0) {
        const method = this.workList.shift() as FuncID;
        const cgNode = this.cg.getNode(method) as CallGraphNode;

        if (this.processedMethod.has(method) || cgNode.isSdkMethod()) {
            continue;
        }

        ...
        
        this.processMethod(method).forEach((cs: CallSite) => {
            let me = this.cg.getArkMethodByFuncID(cs.calleeFuncID);

            this.addCallGraphEdge(method, me, cs, displayGeneratedMethod);

            if (!this.processedMethod.has(cs.calleeFuncID)) {
                this.workList.push(cs.calleeFuncID);
                this.processedMethod.add(cs.callerFuncID);
            }
        })
    }
}

可以看到，算法流程基本上和前面描述的 CHA 算法逻辑差不多，关键几个点解释如下

  • this.processedMethod 看名字也知道，表示处理过的方法，避免重复处理同一个方法
  • this.processMethod(method) 调用的 processMethod 方法后面会讲

Dispatch + Resolve

在 ArkAnalyzer 里面，$\texttt{Dispatch}$ 函数和 $\texttt{Resolve}$ 函数都放在了 resolvecall 里面，resolveCall 则是通过 processMethod 唤起

ts

protected processMethod(methodID: FuncID): CallSite[] {
    ...
    cfg.getStmts().forEach((stmt) => {
        if (stmt.containsInvokeExpr()) {
            this.resolveCall(cgNode.getID(), stmt).forEach(stmt => calleeMethods.push(stmt));
        }
    })

    return calleeMethods;
}

resolveCall 的代码为

ts

public resolveCall(callerMethod: NodeID, invokeStmt: Stmt): CallSite[] {
    let invokeExpr = invokeStmt.getInvokeExpr();
    let resolveResult: CallSite[] = [];

    if (!invokeExpr) {
        return [];
    }

    // process anonymous method call
    this.getParamAnonymousMethod(invokeExpr).forEach(method => {
        resolveResult.push(
            new CallSite(
                invokeStmt,
                undefined,
                this.cg.getCallGraphNodeByMethod(method).getID(),
                callerMethod,
            )
        );
    });

    // 返回方法
    let calleeMethod = this.resolveInvokeExpr(invokeExpr);
    if (!calleeMethod) {
        return resolveResult;
    }

    if (invokeExpr instanceof ArkStaticInvokeExpr) {
        // NOTE: Case 1. Static Method Call
        resolveResult.push(
            new CallSite(
                invokeStmt,
                undefined,
                this.cg.getCallGraphNodeByMethod(calleeMethod!.getSignature()).getID(),
                callerMethod!
            )
        );
    } else {
        let declareClass = calleeMethod.getDeclaringArkClass();
        // NOTE: Case 2. Virtual Call
        this.getClassHierarchy(declareClass).forEach((arkClass: ArkClass) => {
            if (arkClass.isAbstract()) {
                return;
            }

            let possibleCalleeMethod = arkClass.getMethodWithName(calleeMethod!.getName());

            if (possibleCalleeMethod && possibleCalleeMethod.isGenerated() &&
                arkClass.getSignature().toString() !== declareClass.getSignature().toString()) {
                // remove the generated method in extended classes
                return;
            }

            if (possibleCalleeMethod && !possibleCalleeMethod.isAbstract()) {
                resolveResult.push(
                    new CallSite(
                        invokeStmt,
                        undefined,
                        this.cg.getCallGraphNodeByMethod(possibleCalleeMethod.getSignature()).getID(),
                        callerMethod
                    )
                );
            }
        });
    }

    return resolveResult;
}

和前面介绍的 $\texttt{Dispatch}, \texttt{Resolve}$ 相比，ArkAnalyzer 似乎直接将非静态方法调用都当成 Virtual Call 处理

以上就是 CHA 算法的全部内容，它的优点是简单，计算很快，但缺点是不够精确，可能存在误报。比如，假设 A 和 B 这两个类里面都有 foo 方法，对于下面这样一段 Java 代码

java

A a = new B();
a.foo();

CHA 算法会认为 A 和 B 的 foo 方法都是目标方法，因为它没有考虑到 new B() 这一部分。这些可以通过指针分析进一步精确化，这一块就放在未来的文章中再讨论了 :0

  1. 南京大学.软件分析2020.07.Interprocedural Analysis Page 20 ↩︎

  2. 南京大学.软件分析2020.07.Interprocedural Analysis Page 23 ↩︎ ↩︎

  3. ArkAnalyzer: The Static Analysis Framework for OpenHarmony ↩︎

更新于 2025-03-19
 Program-Analysis, Compiler, Internal
 | 主页