基于静态类型分析的Java程序函数调用图构建方法研究

摘要

函数调用图是编译期对程序中函数调用关系的一种静态描述，在函数调用图中，节点表示函数，边表示函数之间的调用关系。函数调用图在软件工程领域有广泛的应用，例如编译优化，过程间数据流分析，回归测试，程序理解等。Java语言的多态机制及子类对父类函数的覆写，使得无法在编译期静态确定虚函数调用点中接受对象的实际类型，从而无法实现接受对象和目标函数之间的静态绑定，因此Java程序的函数调用图只是对实际运行时函数调用关系的一种约近。如何提高虚函数调用的解决效率，减少函数调用图中结点和边的数量，从而使构建的函数调用图能够更准确的反应程序执行时函数之间的实际调用关系，一直是程序分析领域的热点和难点问题。 本文首先结合实例对类层次分析，快速类型分析，和XTA三种基于静态类型分析的虚函数调用解决策略进行了详细说明，并在我们实现的构建函数调用图的原型系统上通过实验比较了上述三种解决方法的分析精度和分析效率。实验证明了XTA方法能够提高快速类型分析的分析精度，并且证明了快速类型分析能够实现分析精度和分析效率的最好均衡。 本文在原XTA方法的基础上，根据类型传播和类型可达思想提出了一种改进的XTA方法。改进方法用增量式的方式来考虑程序中函数的可达性，并在过程内类型传播的基础上，对每个可达函数中的实例化对象类型给定一个可达变量的集合，从而进一步约减虚函数调用点中接受对象的可能类型。通过实例，说明了改进方法对原有XTA方法分析精度的提高。 本文进一步发展和完善了F．Tip提出的基于集合的算法描述框架，并给出了在此框架下类层次分析，快速类型分析，XTA和本文提出的改进XTA的算法描述，从集合论的角度证明了改进方法相对原方法在分析精度上的提高。 本文设计并实现了一个构建函数调用图的原型系统，该原型系统基于对Java程序的字节码分析，目前能够实现程序的类层次图和基于类层次分析，快速类型分析和XTA方法的函数调用图的构建。

目录

文摘

英文文摘

论文说明：插图索引、附表索引

湖南大学学位论文原创性声明及学位论文版权使用授权书

第1章绪论

1.1研究背景及意义

1.1.1虚函数调用的实质—多态

1.1.2 Java虚拟机

1.1.3动态绑定机制

1.1.4函数调用图及应用

1.2研究现状

1.2.1静态类型分析

1.2.2动态编译优化

1.3本文工作及结构

第2章基于静态类型分析的虚函数解决策略

2.1类层次分析(CHA)

2.2快速类型分析(RTA)

2.3 XTA

2.4实验与性能评测

2.4.1评测标准与测试环境

2.4.2性能比较

2.5小结

第3章基于类型传播和类型可达改进XTA

3.1类型传播

3.1.1过程内的类型传播

3.1.2过程间的类型传播

3.1.3类型传播图

3.2基于类型传播与类型可达改进XTA

3.3基于集合的算法描述框架

3.3.1类层次分析(CHA)

3.3.2快速类型分析(RTA)

3.3.3 XTA

3.3.4改进XTA

3.4小结

第4章构建函数调用图的原型系统的设计与实现

4.1字节码分析

4.2系统设计

4.3系统实现

4.3.1分析对象生成模块

4.3.2分析引擎模块

4.3.3统计与显示模块

4.4小结

结论

参考文献

附录

致谢