Interprocedural Analysis - 过程间分析
2026-02-01 10:00:39

Interprocedural Analysis - 过程间分析

Call Graph Construction

What is Call Graph

调用图Call Graph指从调用点连接到调用的目标方法target Method​

image

‍

Method Calls in Java

​Method Call in Java可以分为三类，其中Virtual Call是构建Call Graph的关键所在

image

‍

Method Dispatch of Virtual Call

如何去解构resolve一个Virtual Call​

image

(1) 首先确定返回值的类型receiver object​

(2) 其次是确定方法签名signature​

如上图所示，方法签名Signature = Class Type(方法所在类名) + method name(方法名) + descriptor(方法描述)

其中descriptor = return type(返回值类型) + parameter types(参数类型) 组成

‍

确定了Virtual Call的组成，就可以进行dispatch了

image

我们可以定义一个函数Dispatch(c,m)，其中c为返回值类型，m为要调用的方法的签名signature，如果类class c中有这样一个非抽象non-abstract方法m'，它的方法名name和方法描述descriptor与m相同，则m'即为函数结果

若在类class c未找到这样一个方法，就将c替换为c'，这里c'为类class c的父类，继续调用Dispatch(c',m)来求解

‍

下面是一个利用Dispatch函数的样例

image

‍

Class Hierarchy Analysis - CHA

中文翻译-“类层次分析”

​CHA也是用来解Call Graph的一个方法

使用这个分析方法需要知道类的层次信息，比如一个类的父类有哪些、子类有哪些

以下面这个例子解释

1
2
A a = ...
a.foo();

​CHA的思想是假设，假设a可能指向A类的对象/A的所有子类的对象

然后CHA通过查询A整个类的继承结构去找目标方法是谁

‍

可以通过定义一个函数 Resolve(cs) - cs指call site调用点，来表示使用CHA去寻找目标方法

image

​T={}中T指Target Method目标方法

​m=method signature ai CS指的是目标方法的签名

分为三种情况：static call, special call, virtual call​

‍

(1) ​Static Call​​

1
2
3
4
5
Class C {
	static T foo(P p, Q q) {......}
}

C.foo(x, y);  // Call Site

这个示例中，cs为C.foo(x, y)，签名m为<C: T foo(P, Q)>​

显而易见，T为C.foo​

这是最简单的一种情况

‍

(2) ​Special Call​​

在学习Method Calls in Java时已知，Special Call调用的是构造函数、私有方法以及父类的方法，这里以调用父类方法为例进行解释分析

1
2
3
4
5
6
Class C extends B {
	T foo(P p, Q q) {
		...
		super.foo(p, q);  // Call Site
	}
}

这里super.foo(p, q)为Call Site​

签名m为<B: T foo(P, Q)>​

​c^m=class type of m 为B​

然后利用Dispatch(c^m,m)，也就是Dispatch(B, m)进行求解

那么不禁会有这样一个疑问，为什么结果不直接使用B.foo(P p, Q q)，而还要Dispatch去解呢

因为类B的构造可能如下所示

1
2
3
4
5
Class B extendes A {....}

Class A {
	T foo(P p, Q q) {...}
}

类B中并没有foo方法，而是B的父类A中有foo方法，所以Dispatch就可以避免这样的问题，通过层层结构得到最后的目标方法

‍

(3) ​Virtual Call​​

以下面代码为例解释分析

1
2
3
4
5
6
class C {
	T foo(P p, Q q) {...}
}

C c = ...
c.foo(x, y);  // Call Site

​cs为c.foo(x, y)​

​m为<C: T foo(P, Q)>​

根据图中算法所示

首先取出调用点cs返回值的声明类型并将其赋值给c，这里cs返回值的声明类型为C​

然后利用for循环去不断地调用Dispatch(c', m)，这里c'指的是c自身以及其子类以及其子类的子类

‍

一个简单使用CHA进行分析的案例如下所示

image

这里在Resolve(b.foo())中可以看出CHA算法的一个不足

那就是程序运行时不会调用C.foo(), D.foo()，属于假结果，结果不准确

‍

​IDEA中就使用了CHA​

image

‍

综上所述

​CHA的优点-快，缺点-结果不够准确

‍

Construct Call Graph by CHA

image

‍

BuildCallGraph Algorithm

image

‍

​WL - Work List - 待处理的初始方法，最开始通常只有一个Main方法

​CG - Call Graph - 算法返回的结果

​RM - Reachable Methods - 记录已经到达，即已经处理过的方法，不做重复处理

‍

利用上面的算法可以构造一个完整的Call Graph，如下图所示

image

‍

Interprocedural Control Flow Graph - ICFG

What is ICFG

image

紧跟着Call Site的语句被叫作Return Site​

1
2
3
4
void foo() {
	bar(...);  // Call Site
	int n = 10;  // Return Site
}

​Return edges就会从bar方法的Return语句连回到n = 10​

简而言之，ICFG = CFS(s) + Call & Return edges​

示例如下所示

image

‍

Interprocedural Data Flow Analysis

image

上一页
2026-02-01 10:00:39