Scaling Interprocedural Static Data-Flow Analysis to Large C/C++ Applications
This program is tentative and subject to change.
Interprocedural data-flow analysis is important for computing precise information on whole programs. In theory, the popular algorithmic framework \emph{interprocedural distributive environments} (IDE) provides a tool to solve distributive interprocedural data-flow problems efficiently. Yet, unfortunately, available state-of-the-art implementations of the IDE framework start to run into scalability issues for programs with several thousands of lines of code, depending on the static analysis domain. Since the IDE framework is a basic building block for many static program analyses, this presents a serious limitation. In this paper, we report on our experience with making the IDE algorithm scale to C/C++ applications with up to $500,000$ lines of code. We analyze the IDE algorithm and its state-of-the-art implementations to identify their weaknesses related to scalability at both a conceptual and implementation level. Based on this analysis, we propose several optimizations to overcome these weaknesses, aiming at a sweet spot between reducing running time and memory consumption. As a result, we provide an improved IDE solver that implements our optimizations within the PhASAR static analysis framework. Our evaluation on real-world C/C++ applications shows that applying the optimizations speeds up the analysis on average by $7\times$, while also reducing memory consumption by $7\times$ on average as well. For the first time, these optimizations allow us to analyze programs with several hundreds of thousands of lines of LLVM-IR code in reasonable time and space.
This program is tentative and subject to change.
Mon 16 SepDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
15:30 - 17:00 | |||
15:30 15mTalk | Partial Redundancy Elimination in Two Iterative Data Flow Analyses Technical Papers Reshma Roy National Institute of Technology, Calicut, Sreekala S National Institute of Technology, Calicut, Vineeth Paleri National Institute of Technology, Calicut | ||
15:45 15mTalk | Indirection-Bounded Call Graph Analysis Technical Papers Madhurima Chakraborty University of California, Riverside, Aakash Gnanakumar University of California, Riverside, Manu Sridharan University of California at Riverside, Anders Møller Aarhus University | ||
16:00 15mTalk | Dynamically Generating Callback Summaries for Enhancing Static Analysis Technical Papers Steven Arzt Fraunhofer SIT; ATHENE, Marc Miltenberger Fraunhofer SIT | ATHENE - National Research Center for Applied Cybersecurity, Darmstadt, Julius Näumann TU Darmstadt | ATHENE - National Research Center for Applied Cybersecurity, Darmstadt | ||
16:15 15mTalk | A CFL-Reachability Formulation of Callsite-Sensitive Pointer Analysis with Built-in On-the-Fly Call Graph Construction Technical Papers Dongjie He Chongqing University, China, Jingbo Lu University of New South Wales, Jingling Xue UNSW Sydney | ||
16:30 15mTalk | Scaling Interprocedural Static Data-Flow Analysis to Large C/C++ Applications Technical Papers Fabian Schiebel Fraunhofer IEM, Florian Sattler Saarland Informatics Campus, Saarland University, Philipp Dominik Schubert Heinz Nixdorf Institut, Paderborn University, Sven Apel Saarland University, Eric Bodden | ||
16:45 15mTalk | CtChecker: a Precise, Sound and Efficient Static Analysis for Constant-Time Programming Technical Papers |