Towards a Theoretically-Backed and Practical Framework for Selective Object-Sensitive Pointer Analysis

doi:10.1145/3763111

2025-10-01

PRE

DOI：10.1145/3763111

原文求助

摘要

En 中文

上下文敏感性是指针分析中的基础技术，对于提高精度至关重要且必不可少，但通常会带来显著的效率成本。近期进展聚焦于选择性上下文敏感分析，即仅对部分程序元素（如方法或堆对象）进行上下文敏感分析，其余元素则进行上下文不敏感分析，旨在平衡精度与效率。然而，尽管此类方法层出不穷，现有方法通常依赖特定的代码模式，因此缺乏系统识别可受益于上下文敏感性的代码场景的全面理论依据。本文提出了一种新颖且基础性的理论，建立了对真实情况的正确向上近似，即真正在上下文敏感性下能提高精度的对象。所提出的理论将这一上界的识别重新表述为在典型的指针流图（PFG）上的图可达性问题，每个问题均可分别在上下文不敏感条件下高效求解。基于此理论基础，我们介绍了我们的选择性上下文敏感分析框架MOON。MOON对变量流图（VFG，一种为促进高效遍历而优化的PFG变体）执行双向遍历。此遍历系统地识别所有在上下文敏感性下能提高精度的对象。我们的理论基础，结合框架内精心设计的权衡，使MOON能够限制被选对象的范围，从而在分析精度与效率之间实现有效平衡。在30个Java程序上的广泛实验表明，MOON分别为2对象敏感和3对象敏感分析带来了37.2倍和382.0倍的速度提升，同时仅造成0.1%和0.2%的精度损失。这些结果凸显了MOON在效率与精度之间取得的平衡显著优于所有先前方法。

Keyword:

Pointer Analysis

Selective Object-Sensitivity