支持局部调用图生成的指针分析

万志远，周 波

（浙江大学 计算机科学与技术学院，浙江 杭州310027）

调用图（call graph）是一种描述软件程序中方法间调用关系的有向图［1］，通常表示为G＝（V，E）.其中，顶点集V 表示程序中的程序单元（如方法、过程）集合，有向边集合E 表示程序中程序单元的调用关系集合.调用图用途广泛，是编译器、软件验证工具和程序理解工具进行过程间分析（interprocedural analysis）的先决条件［2］.

现代面向对象编程语言大量使用动态分配（dynamic dispatch），程序中调用点的目标方法由调用点接收对象（receiver）的运行时类型（runtime type）决定.由于程序的任意部分可构造接收对象，大部分静态程序分析工具和框架均采用基于全程序分析［3-8］（whole-program analysis）的 调 用 图 生 成 方法.在文献［9］的实验中，基于全程序分析生成的调用图中，平均有超过50%的顶点为Java标准库中的方法，对于实验中大部分的被分析程序，这一数字甚至超过80%.事实上，许多软件工程应用并不关注调用图中库方法间的调用关系.对于现代面向对象程序语言，全程序分析的可扩展性问题严重阻碍了其在实际中的应用，库和框架规模的日益增长加剧了这一问题.这些库包括程序语言标准库（如：Java程序语言的J2SE、C＋＋语言的STL）、领域相关的方法库（如：图像处理和线性代数）以及可扩展的框架和中间件.本研究统一使用“库”一词来表示程序所依赖的所有库方法.

分析实际应用程序可以发现，与程序中库的代码量相比，应用部分的代码量规模较小.对于许多Web应用程序而言，库代码在静态分析时甚至不可用，因为应用部分依赖的库在实际部署时才能确定（如：Servlet容器）.因此，本研究不分析库部分代码，以提升调用图生成方法的性能.

本研究提出一种指针分析方法，用于生成完整且精确的应用部分局部调用图.该指针分析方法仅分析应用部分代码以及应用部分所引用的库部分代码中的方法签名、类的域和类层次结构（class hierarchy）.该方法对标准指针分析进行扩展，构建混合堆模型（heap model），以区分应用部分及库部分的抽象内存位置.方法为程序中的每一变量维护一个混合指针指向集合（points-to set）.此外，该方法构建一系列规则对应用部分和库部分的交互行为进行建模，并利用这些规则推导库部分的指针信息.该方法使用库的混合指针指向集合解析调用图中的库回调边，并限制回流进入应用部分指针指向集合的抽象对象.本研究在Soot程序分析框架上实现该方法，并在14个Java基准程序上对该方法的性能及生成调用图的完整性和精确性进行评估.

1 研究背景

1.1 调用图生成技术

对于面向对象编程语言，程序中调用点的目标方法由动态分配决定.对于调用点v.m（…），目标方法由调用的接收对象v 的运行时类型决定.运行时类型可通过指针分析获取，通常存储于指针指向集合中.文献中［3］、［4］中的调用图生成技术通常采用On-the-fly方法构建程序的调用图.一方面，On-thefly方法对于被分析程序中的调用点v.m（…），使用变量v的指针指向集合确定调用点的目标方法，逐步构建调用图.另一方面，逐步构建的调用图为指针分析提供过程间指针信息，进一步构造指针指向集合.在On-the-fly调用图生成方法中，指针指向集合的构造和调用图的生成同时进行，直至指针指向集合或调用图中没有变化产生.

1.2 局部调用图生成技术

大部分静态程序分析工具和框架均采用基于全程序分析的调用图生成方法.然而，基于全程序分析的调用图生成方法无法满足应用领域的实际需求.首先，基于全程序分析的调用图生成方法资源消耗大.由于程序应用部分大量使用库代码，即使在分析规模相对较小的程序时，基于全程序分析的调用图生成方法运行也会消耗大量硬件资源.如图1所示，Spark 框 架（运 行 环 境：Intel Core 2 2.33 GHz E6550CPU，2GB RAM）在对该程序进行全程序分析生成调用图时，运行时间超过40s，内存消耗超过250 M.其次，全程序分析生成的调用图中大多数调用边为库方法的调用关系.以图1为例，经Spark产生的调用图中，共有101 229条调用边，其中应用部分内部的调用边仅25条.然而，许多应用领域并不关注全局调用图中库方法间的调用关系，因此，应用部分的局部调用图比全局调用图更具实际意义.

一种构建局部调用图的解决方案是提升方法的可扩展性，只分析应用部分代码，完全排除库中代码产生的影响.这种方法被用于静态分析框架WALA中［3］.该方法在分析中完全排除库代码产生的影响，导致生成的调用图不完整.具体原因在于：1）调用图缺少从库到应用部分的回调边，因而缺失对回调边目标方法的分析；2）该方法忽略库与应用部分的交互，包括方法调用语句和STORE／LOAD语句，因而缺失库与应用部分之间的抽象对象交换信息.

另一种构建局部调用图的解决方案既考虑方法本身的可扩展性，也兼顾构建的调用图的精确性和完整性.该方案通过对库代码进行预分析，计算库方法的方法摘要（procedure summary），摘要描述库方法的指针信息.当应用部分调用库中的某方法时，该方案直接使用被调用方法的方法摘要，从而避免对该库方法的重复分析.这一方案也存在问题：在生成和使用方法摘要时，需要面临抽象表达及算法设计等诸多技术挑战，无缝使用方法摘要需额外的基础结构支持［9］.

图1 局部调用图的Java示例程序说明Fig.1 Sample Java program for illustration of partial call graphs

以上2种解决方案各有利弊，本文选取第3种解决方案，不分析库的具体行为从而保证调用图生成方法的可扩展性，并对库的指针信息进行假设，从而保证调用图的完整性及精确性.该解决方案将被分析程序的库部分视为黑盒，不分析库中方法的调用关系.

1.3 全局调用图和局部调用图

如图2所示分别为由Spark和本研究方法构建的调用图分支.图1中示例程序的全局调用图2（a）和局部调用图2（b）的2个分支.局部调用图中包含3种类型的调用边.

1）应用调用边（application call graph edge）的源方法与目标方法均为应用部分的方法，如图2（b）中的指示线①所示.

2）库调用边（library call graph edge）的源方法属于应用部分，目标方法属于库部分，如图2（b）中的指示线②和③所示.在进行实验数据统计时，当应用部分的某方法一次或多次调用库部分方法时，仅向局部调用图中添加一条库调用边.

3）库回调边（library call back edge）的源方法属于库部分，目标方法属于应用部分，如图2（b）中的指示线④所示.

图2 由Spark和本文方法生成的调用图分支Fig.2 Two branches of call graphs generated by Spark and proposed approach

2 指针分析方法

2.1 方法特征

本研究提出的指针分析方法为流不敏感、上下文不敏感、域敏感的Andersen风格［10］指针分析方法，采用On-the-fly调用图生成方法.输入为Java类集合，该集合称为应用类.应用类依赖于其他Java类，被依赖的Java类集合称为库类.该指针分析方法分析完整的应用部分代码，但不分析库代码的方法体（method body），仅分析库代码中方法的签名、类的域以及类的层次结构.

堆模型（heap model）是指针分析中重要的设计要素.最常见堆模型将任一个静态内存分配点（allocation site）视为单一的抽象内存位置.该方法不分析库代码的方法体，库中的内存分配点不可知.因此，该方法使用混合堆模型以区分应用部分和库部分的内存位置：使用内存分配点表示应用代码所生成的抽象对象，使用类名表示库代码所生成的抽象对象.

通常，利用指针分析计算程序中的指针指向关系，即将每一个指针变量映射到运行时可能指向的对象的超集.典型的指针指向关系通过变量的指针指向集合表示.对任一变量v，其对应的指针指向集合中的每一个抽象对象o 均满足（v，o）这一指针指向关系.

混合堆模型将单一指针指向集合扩展为混合指针指向集合.混合指针指向集合包含2部分：应用指针指向集合和库指针指向集合.

定义1 （应用指针指向集合）对于被分析程序中的变量v，定义应用指针指向集合为PtA（v），该集合包含应用部分代码创建的抽象对象，由内存分配点表示.

定义2 （库指针指向集合）对于被分析程序中的变量v，定义库指针指向集合为PtL（v），该集合包含库部分代码创建的抽象对象，由类名表示.

2.2 集合及概念

被分析程序的类集合为Cls，应用部分代码所声明的类集合为ClsA，库部分代码所声明的类集合表示为ClsL.Cls定义的方法集合为Method.类cls∈ClsA，声明的域由集合fields（cls）＝｛f0，f1，…，fq-1｝表示.域包含非静态域集合F 以及静态域集合SF.本研究将静态域视为特殊形式的全局变量，通过引入一个人工构造域［］表示数组中的元素.

通常，方法m∈M 具有参数列表、本地变量及由语句序列组成的方法体.应用部分的变量集合由V 表示.本地变量vi∈V.任一方法m 具有k 个参数，参数依次表示为p0，p1，…，pk-1.对于非静态方法，p0表示参数this.Java编程语言中参数可被视为一种特殊形式的本地变量，即pi∈V.方法m 的方法体由语句序列组成，不同类型语句组成语句集合Statement.如表1所示，本研究关注指针操作相关的基本语句，并假设所有复杂的语句及表达式均可拆分为基本语句.表1中的基本语句类型可表达Java编程语言中的大部分语义.本指针分析方法为流不敏感，因此不考虑分支语句和循环语句.CALL语句和RETURN 语句处理过程间控制流，每个CALL语句对应于一个调用点（call site），应用代码中的调用点由集合C 表示.

集合O 表示程序代码创建的抽象对象集合.其中应用代码创建的对象集合为OA，库代码创建的对象集合为OL，OA∪OL＝O.

表1 基本语句及其对应的指针赋值图实体Tab.1 Elementary statements and corresponding pointer assignment graph entities

2.3 程序表示

本指针分析构造指针赋值图（pointer assignment graph，PAG）［11］用于表示被分析程序的指针信息.PAG 由3类节点组成，分别是内存分配节点（allocation node）、变量节点（variable node）和域解引用节点（field dereference node）.内存分配节点表示抽象对象，是对应用代码的内存位置建模，集合为OA.变量节点表示程序中的本地变量、方法参数、返回值及静态域.域解引用节点表示域访问的表达式，通过对变量节点的参数化，表示解引用操作.PAG 的节点由4类边相连，包含new／newarray、assign、store和load，反映了抽象对象的流动方向.

本方法遍历被分析程序的语句序列，根据基本语句与PAG 实体的对应关系创建PAG 实体，逐步构造PAG.表1 显示了不同类型的基本语句与PAG 实体的对应规则，其中v、vi、vR、cls.f 和this为变量节点，o为内存分配节点，vi.f 为域解引用节点.在处理过程间数据流时，每一个方法m 的形式参数都在PAG 中存在相应节点，此外，还存在一个特殊节点retm，表示m 的返回值.对于方法m 中的每一个调用点c，在实际参数和形式参数对应的节点间添加assign边，并在调用m 的方法中被赋值的变量对应的节点和retm间添加assign 边.PAG 中每一个节点n都拥有一个指针指向集合，集合中包含所有可能被该节点引用的抽象对象，这些抽象对象沿PAG 边传播.

2.4 库模型

2.4.1 定义 本研究不分析库代码的方法体，提出以下模型表示程序的库部分信息.

变量 定义Library为库代码中的任意变量.

方法 定义mL为库代码中的任意方法.

指针指向集合 库部分存在唯一指针指向集合Pt（Library），该指针指向集合包含2 部分.其一为PtL（Library），包含抽象对象o∈OL，这些对象被库代码引用.假设库部分代码能创建及引用任意库类的对象，因此，PtL（Library）隐式地包含库部分所有类的对象，这些对象由对应的类名表示.其二为PtA（Library），包含抽象对象o∈OA，这些对象在应用部分创建，并被库代码引用.

调用点 cL为库部分代码中的任意调用点，可调用库类中的任意可见方法和非静态应用类cls中的方法m，该方法重写库方法.此外，存在抽象对象o∈PtA（Library），StaticType（o）为cls的本身或者cls的子类.StaticType（o）表示对象o的静态类型.

2.4.2 抽象对象推测 由于应用部分和库部分交互，部分抽象对象从应用部分逃逸至库部分，反之亦然.通过分析应用部分和库部分的交互行为，可推测出创建于库部分的抽象对象集合OL，更新应用部分代码中变量的库指针指向集合.

针对不同类型的基本语句定义如下规则，以推测库部分创建的抽象对象集合及变量的库指针指向集合.

1）实例载入

规则1 对于语句v2＝v1.f，非静态域f在cls∈ClsL中声明：

StaticType（f）∈OL；

StaticType（f）∈PtL（v2）.

其中，StaticType（v）表示变量v的静态类型.

2）静态载入

规则2 对于语句v＝cls.f，cls∈ClsL：

StaticType（f）∈OL；

StaticType（f）∈PtL（v）.

3）静态方法调用

考虑应用部分代码中的静态方法调用，假设目标方法为静态方法m，该方法在某库类中声明.

规则3 对 于 语 句vR＝cls.m（v1，…，vj），X∈ClsL：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

其中，vi表示实际参数，retm表示方法cls.m 的返回值.

4）实例方法调用

考虑某一个应用部分的方法存在一个实例方法调用，该方法调用的目标方法为实例方法m，该方法在某库类中声明.

规则4 对 于 语 句vR＝v0.m（v1，…，vj），v0∈V：

StaticType（retm）∈OL；

StaticType（retm）∈PtL（vR）.

考虑库方法中一个实例方法调用，假设目标方法为实例方法m，该方法在某库类中声明并被某应用类的方法重写，它也是某条库回调边的目标方法.

规则5 对于语句Library.m（v1，…，vk）：

StaticType（this）∈OL；

StaticType（this）∈PtL（this）；

StaticType（vi）∈OL；

StaticType（vi）∈PtL（vi）∧1≤i≤k.

2.5 虚函数调用的处理

定义3 CallGraph为程序应用部分的局部调用图，CallGraph是由调用边组成的有限集合.调用边定义为三元组（m1，m2，c），其中m1，m2∈｛mL｝∪Method，且c∈｛cL｝∪C，调用边连接调用点和调用点对应的目标方法.

对于应用部分的方法M 中的虚拟函数调用点v.m（…），依照以下2条规则，使用PtA（v）和PtL（v）解析调用点c∈C 的目标方法，并构建调用边.

规则6 对于抽象对象o∈PtA（v），存在StaticLookup（StaticType（o），m）＝m′：

（M，m′，c）∈CallGraph.

规则7 对于抽象对象cls∈PtL（v），存在StaticLookup（cls，m）＝m′：（M，m′，c）∈CallGraph.

以上规则中，StaticType（o）表示对象o的静态类型，StaticLookup（cls，m）表示通过静态查询获得声明于类cls中签名为m 的方法.

对于库部分代码中的虚拟函数调用点，定义如下规则，利用PtA（Library）解析调用点cL的目标方法，构建库回调边.

规则8 对于每一抽象对象o∈PtA（Library），方法m 声明于cls∈ClsA，并且满足cls∈｛Static-Type（o）｝∪SuperTypes（StaticType（o）），方法m重写库类方法：（mL，m，cL）∈CallGraph.Super-Types（cls）表示类cls超类型的集合.

3 实 验

实验旨在验证本研究提出方法的可扩展性、生成调用图的完整性及精确性.实验中将本文提出的方 法 与Spark［11］和Averroes［12］方 法 进 行 对 比.Spark指针分析框架构建在Soot分析框架之上，采用全程序分析方法生成调用图.Averroes为当前最新的局部调用图生成方法，分析程序的库方法以生成字节码级别的占位库（placeholder library），通过Spark及其他全程序分析框架分析应用部分代码和占位库，构建局部调用图.实验结果表明：

2）性能方面，本文方法平均分析时间为32s，比Averroes的平均分析速度快4.9倍，比Spark的平均分析速度快13.7倍.

2）调用图完整性方面，除缺失2条库调用边，本文提出方法生成的调用图覆盖基准程序动态调用图中所有调用边，该结果与Averroes相同.

3）调用图精确性方面，与全程序分析调用图生成方法Spark相比，本文方法额外产生中位值22条应用调用边、中位值2 条库调用边以及中位值23条库回调边.相较于Spark 产生的调用图中调用边的总量，本文方法生成的调用图中额外调用边数量可忽略不计.

3.1 实验准备

实验 的 运 行 环 境 为Intel Core 2 2.13 GHz p7450CPU 及2 GB RAM.实验使用DaCapo v.2006-10-MR2基准程 序［13］和SPEC jvm 98 基 准 程序［14］，采用与文献［12，15］相同的配置.实验中分析JDK 1.4Java标准库（jre 1.4.2＿11）.实验中选取的基准程序具体信息如表2所示.

3.2 方法实现

在Soot［4］框架2.5.0 版本上实现所提出的指针分析方法（PtaPCG），通过Spark［11］指针分析框架驱动方法的执行.实验中对Soot进行配置，将分析的范围限定在程序的应用部分，实现基于PAG 节点工作队列，该队列中PAG 节点PtA／L存在更新.对于每队列中的每一个个PAG 节点，将PtA／L中的抽象对象传播至相邻节点的指针指向集合中.抽象对象的传播同时会引起：1）应用部分新的可达方法被发现；2）新发现的可达方法引起实际参数和形式参数、返回值以及本地变量间的PAG 边的创建；3）应用部分和库部分的指针指向集合间抽象对象的流动.

当不存在未处理的可达方法并且PAG 节点的工作队列为空时，算法将终止.实现扩展Spark标准指针分析，包括创建库指针指向集合、传递库指针指向集合中的抽象对象以及使用库指针指向集合解析调用点.此外，还对以下方面进行了优化.

1）数组.由于Soot程序分析框架将所有的数组元素建模成数组引用域［］，代码实现中将数组中每个元素的指针指向集合进行合并，从而形成该数组引用的指针指向集合.

2）反射和动态类加载机制.反射和动态类加载机制在Java程序中广泛使用.然而，由反射机制引起的类和方法的访问无法通过静态分析确定.实现中利用TamiFlex［16］收集的动态运行信息，确定由反射产生的程序行为.

3）标准库.通过分析发现，许多传入标准库代码的抽象对象并未被其他库方法引用，如传入类java.lang.Object构造器的对象.代码实现中对这些标准库方法进行特殊处理，当这些方法被调用时，不将抽象对象传入库部分的指针指向集合中.

3.3 性 能

如图3 所 示 为PtaPCG、Averroes和Spark 的运行时间.PtaPCG 的运行性能良好，平均运行时间为32s.与Averroes相比，PtaPCG 平均分析时间快4.9倍（最小为1.9倍，最大为33.9倍，几何平均为4.9倍），与Spark 相 比，PtaPCG 平 均 分 析 时 间 快13.7倍（最小为3.3倍，最大为131.2倍，几何平均为13.7倍）.

实验结果表明，PtaPCG 显著提升了Spark 的性能.性能提升的原因在于生成调用图时PtaPCG未对库部分的方法体进行分析，Averroes的运行时间分为2个部分：1）预分析时间：Averroes生成占位库所使用的时间，图3中显示为AverroesPlaceholder；2）分析时间，Spark使用Averroes占位库进行全程序分析生成调用图的运行时间，图3 中显示为AverroesAnalysis.分析发现，Averroes的运行时间大部分为预分析时间.

表2 本实验使用的基准程序信息Tab.2 Information of benchmarks used in proposed experiment

图3 PtaPCG、Averroes和Spark分析基准程序的运行时间对比Fig.3 Comparison of time taken by PtaPCG，Averroes and Spark for each benchmark program

3.4 调用图完整性

实验中通过对存在于由＊J［17］工具记录的动态调用图、缺失于由静态工具生成的静态调用图的调用边数量进行统计，评估PtaPCG、Averroes 和Spark产生的调用图的完整性.动态调用图是＊J工具通过观察和记录基准程序的动态运行得到的.实验结果如表3 所示，“Dynamic”行显示了基准程序的动态调用图中应用部分调用边的数量，“Dynamic＼PtaPCG”行、“Dynamic＼Averroes”行和“Dynamic＼Spark”行分别显示了PtaPCG、Averroes和Spark生成的静态调用图中缺失的动态调用边数量.实验结果表明，PtaPCG 和Averroes生成的调用图中缺少lusearch和xalan基准程序中的2条库调用边.分析发现，lusearch基准程序在动态运行时抛出一个NullPointerException 异常，动态调用图中包含对该异常类构造器的调用，而xalan基准程序在动态运行时调用了java.lang.ref.Finalizer.register方法.调用边的缺失是由于PtaPCG 和Averroes均未对Java虚拟机的行为进行完整的建模.

此外，“Dynamic＼Spark”行显示Spark 生成的调用图中缺失相当数量的调用边，这是由于这些基准程序大量使用反射机制，而Spark未对反射机制进行完整的处理.PtaPCG 和Averroes 则利用TamiFlex收集的动态信息对反射进行处理.

3.5 调用图精确性

实验中通过比较PtaPCG、Averroes和Spark生成调用图中3种类型调用边的数量，来评估方法所生成调用图的精确性.Spark 通过全程序分析生成调用图，而PtaPCG 和Averroes均不分析库类中的方法体而生成局部调用图.因此，PtaPCG 和Averroes生成的调用图与Spark 生成的调用图相似度越高，表明其生成的调用图精确性越高.

对调用图完整性进行评估，发现PtaPCG、Averroes和Spark生成的静态调用图都存在一定程度的不完整性，为防止完整性与精确性的评估结果产生混淆，在进行调用图精确性评估前，先将这些缺失的调用边加入到静态调用图中.表4～6 中的“PtaPCG＼Spark”行和“Averroes＼Spark”行分别表示与Spark相比PtaPCG 和Averroes生成的3 种类型额外的调用边数量.

3.5.1 应用调用边 如表4 所示，对于基准程序luindex、compress、db、jess和raytrace，PtaPCG 能够精确地产生调用图中的应用调用边.对于所有基准程序而言，与Spark相比，PtaPCG 产生中位值22条额外的应用调用边（最小为0，最大为1 821，中位值为22）.该中位值为Spark产生调用图中应用调用边中位值的0.49%.这些额外的调用边主要存在于基准程序bloat、hsqldb和xalan的调用图中.通过分析可知，这些基准程序中存在实现库接口的大规模子系统，这些接口分别是java.util.＊、JDBC和XML.与Averroes相比，PtaPCG 产生的额外应用调用边中位值比Averroes的中位值23略小.实验结果表明，对于应用调用边而言，PtaPCG 比Averroes生成更加精确的调用图.

表3 PtaPCG、Averroes和Spark生成调用图的完整性对比Tab.3 Comparison of completeness of call graphs generated by PtaPCG，Averroes and Spark

3.5.2 库调用边 如表5所示，对于基准程序antlr、luindex、compress和raytrace，PtaPCG 能够产生精确的库调用边.对于所有基准程序而言，与Spark相比，PtaPCG 产生中位值为2的额外库调用边（最小为0，最大为112，中位值为2）.该中位值仅为Spark生成库调用边中位值的0.55%.与Averroes相比，PtaPCG 额外库调用边中位值比Averroes的中位值3略小.实验结果表明，对于库调用边而言，PtaPCG 比Averroes生成更加精确的调用图.

3.5.3 库回调边 如表6所示为库回调边精确性的评估结果.对于所有基准程序而言，与Spark 相比，PtaPCG 产生额外库回调边的中位值为23（最小为1，最大为645，中位值为22.5），该中位值占Spark生成库回调边中位值的31.69%.与Averroes相比，PtaPCG 产生额外库回调边的中位值比Averroes的中位值5大.引起库回调边不精确的原因包含以下2个方面.

1）PtaPCG对＜clinit＞的处理方法.PtaPCG 在3种情况下把对＜clinit＞的隐式调用构建为库回调边：当某静态方法被调用时、当某静态域被访问时以及当某个对象或某个对象数组初始化时.然而，Spark则把对＜clinit＞的隐式调用构建为应用调用边.实验结果中，由PtaPCG产生的调用图中大部分额外的库回调边的目标方法均为静态初始化块＜clinit＞.

2）PtaPCG 对库部分代码引用的对象进行保守假设，即认为调用库方法传入库中的对象会被库中其他的方法引用.实际上，其中的一些库方法并不会将对象泄露给其他库代码.正是由于这一假设，扩大了库指针指向集合的规模，从而引入额外的库回调边.此外，由于应用部分与库部分的交互，这些对象会污染应用部分变量的指针指向集合，进一步影响其他类型调用边的精确性.

表4 比较PtaPCG、Averroes和Spark生成的调用图中应用调用边的精确性对比Tab.4 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to application call graph edges

表5 PtaPCG、Averroes和Spark生成的调用图中库调用边的精确性对比Tab.5 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to library call graph edges

表6 PtaPCG、Averroes和Spark生成的调用图中库回调边的精确性对比Tab.6 Comparison of precision of call graphs generated by PtaPCG，Averroes and Spark with respect to library call back edges

4 相关工作

4.1 全程序分析调用图生成方法

Dean等［5］提出了类层次结构分析法（class hierarchy analysis，CHA），方法中假设接收对象的运行时类型可以是其声明类型的任意子类型.Bacon等［6］提出 了 快 速 类 型 分 析 法（rapid type analysis，RTA），方法将运行时类型限制在程序可达部分已经创建实例的类中.Diwan等［7］提出了Modula-3的调用图生成算法，为每一个本地变量维护一个不同的运行时类型集合.Sundaresan等［8］提出了变量类型分析法（variable type analysis，VTA），通过创建类型传播图来表示由赋值引起的类型传播，并通过传播类型计算变量的指针指向集合.Tip等［18］设计了一个基于集合的统一框架，描述不同类型的指针分析方法，并在此框架上提出了一系列指针分析算法（CTA、MTA、FTA 和XTA），这些算法的不同之处在于使用了不同粒度的指针指向集合.

4.2 局部调用图生成方法

局部调用图生成方法面临的主要挑战在于对未分析部分代码做出精确且完整的假设.Tip等［18］将所有传入库代码中的对象集结成一个特殊的指针指向集合SE，并利用该指针指向集合确定库代码的目标方 法.Grothoff等［19］提 出 名 为Kacheck／J 的 工具，用以推测Java程序中的局限属性（confinement properties）.局限属性定义如下：若某个类及其子类的实例均封装在同一个包（package）内，那么就称这个类及其子类是被局限的.该方法用于识别库部分与应用部分之间的逃逸对象，从而对库部分指针指向集合中的对象进行精确的假设.Andersen［10］提出一种名为CGC的调用图生成方法，依赖分离编译假设，创建应用部分的局部调用图.该方法使用一个指针指向集合摘要，表示库中所有变量的指针指向信息，在不分析库部分代码的前提下，对应用部分可能的行为进行推导.Rountev等［20］提出创建一个占位方法main，通过分析所有实现库接口或扩展库抽象类的应用类生成代表未知代码的占位方法.该占位方法包含各种类型语句，以模拟未知代码的潜在行为.然而，占位方法改变了应用部分代码原本的逻辑，致使精确性降低.Ali等［12］提出了Averroes工具，基于分离编译假设［15］生成占位库，占位库中包含了对库代码行为的估计，包括Spark在内的全程序分析框架能够通过直接分析占位库来生成局部调用图.

本研究和Zhang 等［21］的工作存在关联，文献［21］的研究目标在于创建精确的应用部分调用图，通过对库部分代码进行深入分析，达到对库回调边的目标方法进行精确解析的目的，这与本研究的初衷不同.

5 结 语

本文提出了一种指针分析方法，在不分析库部分语句的前提下，创建Java程序应用部分的局部调用图.该方法使用混合堆模型，区分应用部分及库部分的抽象内存位置.为应用部分和库部分的交互构建形式化模型，推测库中创建的抽象对象.本研究在Soot程序分析框架上实现了该方法，通过与Spark 及Averroes进行比较，评估该方法的性能及生成调用图的完整性和精确性.实验结果表明：本文方法能高效地创建精确且完整的局部调用图.今后的工作包括为库中不同代码部分定义多个不同的指针指向集合，对反射机制、静态初始化和异常处理机制进行更加完整和精确地建模，以提高构建调用图的精确性.

（

）：

［1］GROVE D，CHAMBERS C.A framework for call graph construction algorithms［J］.ACM Transactions on Programming Languages and Systems，2001，23（6）：685-746.

［2］LHOTÁK O.Comparing call graphs［C］∥Proceedings of the 7th ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering.San Diego：ACM，2007：37-42.

［3］T.J.Watson libraries for analysis（WALA）［EB／OL］.［2014-03-21］.http：∥wala.sourceforge.net.

［4］VALLÉE-RAI R，GAGNON E，HENDREN L J，et al.Optimizing Java bytecode using the soot framework：is it feasible？［C］∥Proceedings of the 9th International Conference on Compiler Construction.Berlin：Springer，2000：18-34.

［5］DEAN J，GROVE D，CHAMBERS C.Optimization of object-oriented programs using static class hierarchy analysis［C］∥Proceedings of the 9th European Conference on Object-Oriented Programming.London：Springer，1995：77-101.

［6］BACON D F，SWEENEY P F.Fast static analysis of C＋＋virtual function calls［C］∥Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.San José：ACM，1996：324-341.

［7］DIWAN A，MOSS J，MCKINLEY K S.Simple and effective analysis of statically-typed object-oriented programs［C］∥Proceedings of the 11th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.San José：ACM，1996：292-305.

［8］SUNDARESAN V，HENDREN L，RAZAFIMAHEFA C，et al.Practical virtual method call resolution for Java［C］∥Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming，Systems，Languages and Applications.Minneapolis：ACM，2000：264-280.

［9］YAN D，XU G，ROUNTEV A.Rethinking Soot for summary-based whole-program analysis［C］∥Proceedings of ACM SIGPLAN International Workshop on State of the Art in Java Program Analysis.Beijing：ACM，2012：9-14.

［10］ANDERSEN L O.Program analysis and specialization for the C programming language［D］.Denmark：University of Copenhagen，1994：6-35.

［11］LHOTÁK O，HENDREN L.Scaling Java points-to analysis using SPARK ［C］∥Proceedings of the 12th International Conference on Compiler Construction.Warsaw：Springer，2003：153-169.

［12］ALI K，LHOTÁK O.Averroes：whole-program analysis without the whole program ［C］∥Proceedings of the 27th European Conference on Object-Oriented Programming.Montpellier：Springer，2013：378-400.

［13］BLACKBURN S M，GARNER R，HOFFMAN C，et al.The DaCapo benchmarks：Java benchmarking development and analysis［C］∥Proceedings of the 21st Annual ACM SIGPLAN International Conference on Object-Oriented Programing，Systems，Languages and Applications.Portland：ACM，2006：169-190.

［14］Standard Performance Evaluation Corporation：SPEC JVM98benchmarks［EB／OL］.［2014-03-21］.http：∥www.spec.org／jvm98.

［15］ALI K，LHOTÁK O.Application-only call graph construction［C］∥Proceedings of the 26th European Conference on Object-Oriented Programming. Beijing：Springer，2012：688-712.

［16］BODDEN E，SEWE A，SINSCHEK J，et al.Taming reflection：aiding static analysis in the presence of reflection and custom class loaders［C］∥Proceedings of the 33rd International Conference on Software Engineering.Honolulu：ACM，2011：241-250.

［17］DUFOUR B，HENDREN L，VERBRUGGE C.＊J：a tool for dynamic analysis of Java programs［C］∥Proceedings of Companion of the 18th Annual ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages，and Applications.Anaheim：ACM，2003：306-307.

［18］TIP F，PALSBERG J.Scalable propagation-based call graph construction algorithms［C］∥Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.Minneapolis：ACM，2000：281-293.

［19］GROTHOFF C，PALSBERG J，VITEK J.Encapsulating objects with confined types［C］∥Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programming，Systems，Languages and Applications.Tampa Bay：ACM，2001：241-255.

［20］ROUNTEV A，MILANOVA A，RYDER B G.Fragment class analysis for testing of polymorphism in Java software［J］.IEEE Transactions on Software Engineering，2004，30（6）：372-387.

［21］ZHANG W，RYDER B G.Automatic construction of accurate application call graph with library call abstraction for Java［J］.Journal of Software Maintenance and Evolution：Research and Practice，2007，19（4）：231-252.