构建一个基于理论支撑且具有实用性的选择性对象敏感指针分析框架

《Proceedings of the ACM on Programming Languages》：Towards a Theoretically-Backed and Practical Framework for Selective Object-Sensitive Pointer Analysis

选择性上下文敏感性分析通过改进的指针流图和变量流图，系统识别上下文敏感对象，在30个Java程序中实现37.2倍和382倍速度提升且精度损失仅0.1%和0.2%。

　　

摘要

上下文敏感性是指针分析中的基础技术，对于提高分析精度至关重要，但往往会导致显著的效率损失。最近的进展集中在选择性上下文敏感性分析上，即仅对程序中的部分元素（如方法或堆对象）进行上下文敏感性分析，而对其他元素则采用上下文不敏感性分析，以此在精度和效率之间取得平衡。然而，尽管这类方法越来越多，现有的方法通常是基于特定的代码模式来设计的，因此缺乏系统识别可以从上下文敏感性中受益的代码场景的全面理论基础。

本文提出了一种新颖的基础理论，该理论能够准确估计出在上下文敏感性下真正能够提高精度的对象范围。所提出的理论将这种上限的识别问题重新表述为典型的指针流图（Pointer Flow Graph, PFG）上的图可达性问题，而这些问题在上下文不敏感性条件下都可以高效解决。基于这一理论基础，我们引入了选择性上下文敏感性分析方法Moon。Moon在变量流图（Variable Flow Graph, VFG）上进行双向遍历，VFG是PFG的一种优化版本，旨在提高遍历效率。这种遍历能够系统地识别出所有在上下文敏感性下能够提高精度的对象。我们的理论基础以及方法中精心设计的权衡机制，使得Moon能够限制被选对象的范围，从而在分析精度和效率之间实现有效平衡。通过对30个Java程序进行的广泛实验表明，Moon在处理2个对象敏感和3个对象敏感的分析时，分别实现了37.2倍和382.0倍的加速效果，同时精度损失仅为0.1%和0.2%。这些结果表明，Moon在效率和精度之间的平衡显著优于所有之前的方法。