An Incremental Algorithm for Algebraic Program Analysis

作     者：Zhou, Chenyu Fang, Yuzhou Wang, Jingbo Wang, Chao 

作者机构：Univ Southern Calif Los Angeles CA 90007 USA Purdue Univ W Lafayette IN USA 

出 版 物：《PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL》 (Proc. ACM Program. Lang.)

年 卷 期：2025年第9卷第POPL期

页      面：1934-1961页

核心收录：

基　　金：U.S. National Science Foundation (NSF) [CCF-2220345] 

主　　题：Algebraic Program Analysis Data-flow Analysis Side-channel Analysis Incremental Algorithm 

摘      要：We propose a method for conducting algebraic program analysis (APA) incrementally in response to changes of the program under analysis. APA is a program analysis paradigm that consists of two distinct steps: computing a path expression that succinctly summarizes the set of program paths of interest, and interpreting the path expression using a properly-defined semantic algebra to obtain program properties of interest. In this context, the goal of an incremental algorithm is to reduce the analysis time by leveraging the intermediate results computed before the program changes. We have made two main contributions. First, we propose a data structure for efficiently representing path expression as a tree together with a tree-based interpreting method. Second, we propose techniques for efficiently updating the program properties in response to changes of the path expression. We have implemented our method and evaluated it on thirteen Java applications from the DaCapo benchmark suite. The experimental results show that both our method for incrementally computing path expression and our method for incrementally interpreting path expression are effective in speeding up the analysis. Compared to the baseline APA and two state-of-the-art APA methods, the speedup of our method ranges from 160x to 4761x depending on the types of program analyses performed.