Sandro Stucki

Lifting On-Demand Analysis to Higher-Order Languages

Daniel Schoepe, David Seekatz, Ilina Stoilkovska, Sandro Stucki, Daniel Tattersall, Pauline Bolignano, Franco Raimondi, and Bor-Yuh Evan Chang. In Proceedings of the 30th International Symposium on Static Analysis (SAS 2023), in LNCS, volume 14284, pp. 460–484, Springer, 2023.

Abstract

In this paper, we present an approach to lift on-demand analysis to higher-order languages. Specifically, our approach bootstraps an on-demand call graph construction by leveraging a pair of on-demand data flow analyses. Static analysis is increasingly applied to find subtle bugs or prove deep properties in large, industrial code bases. To effectively do this at scale, analyzers need to both resolve function calls in a precise manner (i.e., construct a precise call graph) and examine only the relevant portion of the program (i.e., be on-demand). A strawman strategy to this problem is to use fast, approximate, whole-program call graph construction algorithms. However, this strategy is generally not adequate for modern languages like JavaScript that rely heavily on higher-order features, such as callbacks and closures, where scalable approximations often introduce unacceptable imprecision. This strategy also limits increasingly sophisticated on-demand analyses, which scale by analyzing only parts of a program as needed: the scalability advantages of an ondemand analysis may be thwarted by the need to construct a wholeprogram call graph. The key insight of this paper is that existing ondemand data flow analyses can themselves be applied in a black-box manner to construct call graphs on demand. We propose a soundness condition for the existing on-demand analyses with respect to partial call graphs, formalize our algorithm as an abstract domain combinator, and prove it sound in Isabelle/HOL. Furthermore, we evaluate a prototype implementation of the resulting on-demand call graph construction algorithm for a subset of JavaScript (using the Synchronized Push-Down Systems framework as the underlying data flow analysis) on benchmarks making heavy use of higher-order functions.

Links