Indirection-Bounded Call Graph Analysis

TY - GEN

T1 - Indirection-Bounded Call Graph Analysis

AU - Chakraborty, Madhurima

AU - Gnanakumar, Aakash

AU - Sridharan, Manu

AU - Møller, Anders

N1 - Publisher Copyright: © Madhurima Chakraborty, Aakash Gnanakumar, Manu Sridharan, and Anders Møller;

PY - 2024/9

Y1 - 2024/9

N2 - 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.jsbased 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.

AB - 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.jsbased 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.

KW - call graphs

KW - JavaScript

KW - points-to analysis

UR - http://www.scopus.com/inward/record.url?scp=85204982722&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ECOOP.2024.10

DO - 10.4230/LIPIcs.ECOOP.2024.10

M3 - Article in proceedings

AN - SCOPUS:85204982722

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 38th European Conference on Object-Oriented Programming, ECOOP 2024

A2 - Aldrich, Jonathan

A2 - Salvaneschi, Guido

PB - Dagstuhl Publishing

T2 - 38th European Conference on Object-Oriented Programming, ECOOP 2024

Y2 - 16 September 2024 through 20 September 2024

ER -