Heap Abstraction via Early-Confluent Object Merging for Pointer Analysis
This program is tentative and subject to change.
Heap abstraction critically affects both the efficiency and precision of pointer analysis for Java programs. By merging heap objects allocated at different program points, heap abstractions can significantly improve analysis efficiency, but often at the cost of precision. Mahjong, a state-of-the-art heap abstraction based on object merging, demonstrates that object merging can substantially improve the efficiency of pointer analysis while preserving precision for type-dependent clients; however, this client-specific guarantee limits its general applicability. In this work, we investigate how to improve the efficiency of pointer analysis through object merging, while preserving precision in a manner independent of any particular client. Our key insight is that, from the perspective of pointer analysis, many heap objects exhibit early flow confluence: they are allocated at different program points and then quickly propagate to the same pointers (variables or fields), after which they continue to flow together through the program. Merging such early-confluent objects has negligible impact on overall analysis precision. In contrast, merging objects that do not flow to the same pointers, or that converge only much later, can introduce substantial precision loss.
Guided by this insight, we propose Valve, a new heap abstraction approach that efficiently identifies and merges early-confluent objects. Valve encodes the flow information needed for early-confluence detection as nondeterministic finite automata (NFAs) and reduces mergeability checking to an NFA-equivalence test, enabling efficient object merging while retaining high precision. We evaluate Valve on the largest benchmarks used in recent literature as well as modern large-scale Java applications, by integrating it with multiple state-of-the-art pointer-analysis techniques and directly comparing it with Mahjong. The results show that Valve achieves substantially higher precision than Mahjong for non-type-dependent clients, while maintaining comparable precision for type-dependent clients. At the same time, Valve delivers comparable or often better analysis efficiency across all evaluated cases. Overall, Valve, as a heap abstraction approach, significantly improves the efficiency of pointer analysis across several state-of-the-art techniques while maintaining high precision (99.61% on average).
This program is tentative and subject to change.
Tue 6 OctDisplayed time zone: Pacific Time (US & Canada) change
10:30 - 12:00 | |||
10:30 18mTalk | Hermes: Making Path-Sensitive Pointer Analysis Scalable for Sparse Value-Flow Analysis OOPSLA Yuxuan He School of Informatics, Xiamen University, Ruilin Jiang School of Informatics, Xiamen University, He Zhang School of Informatics, Xiamen University, Qingkai Shi Nanjing University, Huaxun Huang School of Informatics, Xiamen University, Rongxin Wu Xiamen University | ||
10:48 18mTalk | Heap Abstraction via Early-Confluent Object Merging for Pointer Analysis OOPSLA Jinpeng Wang Nanjing University, Yufei Liang Nanjing University, Zhongsheng Zhan Nanjing University, Tian Tan Nanjing University, Yue Li Nanjing University Pre-print | ||
11:06 18mTalk | Mechanically Translating Iterative Dataflow Analysis to Algebraic Program Analysis OOPSLA Chenyu Zhou University of Southern California, Jingbo Wang Purdue University, Chao Wang University of Southern California | ||
11:24 18mTalk | When FPGA Meets Dataflow Analysis: An Explorative Step OOPSLA Fang Wei Nanjing University, Qinlin Chen Nanjing University, Nairen Zhang Nanjing University, Jiacai Cui Nanjing University, Tian Tan Nanjing University, Zhiqiang Zuo Nanjing University, Yue Li Nanjing University | ||
11:42 18mTalk | Beyond Nominality: Faster Rapid Type Analysis in the Presence of Structural Subtyping OOPSLA | ||