Lifting On-Demand Analysis to Higher-Order Languages

Artifact for paper "Lifting On-Demand Analysis to Higher-Order Languages". Paper 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. While static analysis is increasingly applied to find subtle bugs or prove deep properties in large, industrial code bases, to effectively find bugs or prove properties at scale, analyzers both need to resolve function calls in a precise manner (i.e., construct a precise call graph) and to 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 on-demand analysis may be thwarted by the need to construct a whole-program call graph. The key insight of this paper is that existing on-demand 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 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