SPLASH 2014
Mon 20 - Fri 24 October 2014 Portland, Oregon, United States
Fri 24 Oct 2014 14:15 - 14:37 at Salon E - Static Analysis Chair(s): Anders Møller

Inclusion-based alias analysis for C can be formulated as a context-free language (CFL) reachability problem. It is well known that the traditional cubic CFL-reachability algorithm does not scale well in practice. We present a highly scalable and efficient CFL-reachability-based alias analysis for C. The key novelty of our algorithm is to propagate reachability information along only original graph edges and bypass a large portion of summary edges, while the traditional CFL-reachability algorithm propagates along all summary edges. We also utilize the Four Russians’ Trick - a key enabling technique in the subcubic CFL-reachability algorithm - in our alias analysis. We have implemented our subcubic alias analysis and conducted extensive experiments on widely-used C programs from the pointer analysis literature. The results demonstrate that our alias analysis scales extremely well in practice. In particular, it can analyze the recent Linux kernel (which consists of 10M SLOC) in about 30 seconds.

Fri 24 Oct

oopsla2014
13:30 - 15:00: OOPSLA - Static Analysis at Salon E
Chair(s): Anders MøllerAarhus University
oopsla2014141415020000013:30 - 13:52
Talk
Link to publication
oopsla2014141415155000013:52 - 14:15
Talk
Nimrod PartushTechnion, Eran YahavTechnion
Link to publication
oopsla2014141415290000014:15 - 14:37
Talk
Qirun ZhangThe Hong Kong University of Science and Technology, Xiao XiaoThe Hong Kong University of Science and Technology, Charles ZhangHong Kong University of Science and Technology, Hao YuanBOPU Technologies, Zhendong SuUniversity of California, Davis
Link to publication
oopsla2014141415425000014:37 - 15:00
Talk
Lucas BrutschyETH Zurich, Pietro FerraraIBM Thomas J. Watson Research Center, Peter MüllerETH Zurich
Link to publication