Indirection-Bounded Call Graph Analysis
This program is tentative and subject to change.
Call graphs play a crucial role in analyzing the structure and behavior of programs. For JavaScript and other dynamically typed programming languages, static call graph analysis relies on approximating the possible flow of functions and objects, and producing usable call graphs for large, real-world programs remains challenging.
In this paper, we propose a simple but effective technique that addresses performance issues encountered in call graph generation. We observe via a dynamic analysis that typical JavaScript program code exhibits small levels of indirection of object pointers and higher-order functions. We demonstrate that a widely used analysis algorithm, wave propagation, closely follows the levels of indirections, so that call edges discovered early are more likely to be true positives. By bounding the number of indirections covered by this analysis, in many cases it can find most true-positive call edges in less time. We also show that indirection-bounded analysis can similarly be incorporated into the field-based call graph analysis algorithm ACG.
We have experimentally evaluated the modified wave propagation algorithm on 25 large Node.js-based JavaScript programs. Indirection-bounded analysis on average yields close to a 2X speed-up with only 5% reduction in recall and almost identical precision relative to the baseline analysis, using dynamically generated call graphs for the recall and precision measurements. To demonstrate the robustness of the approach, we also evaluated the modified ACG algorithm on 10 web-based and 4 mobile-based medium sized benchmarks, with similar results.
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 |