Fixpoint Reuse for Incremental JavaScript Analysis

Report ID: 
2019-02
Authors: 
Lawton Nichols, Mehmet Emre, Ben Hardekopf
Date: 
2019-03-01 00:00:00

Abstract

When programs are frequently updated, the cost of statically analyzing those programs is multiplied by the number of program versions that must be analyzed. In cases such as analyzing JavaScript programs, the baseline analysis is costly, exacerbating this cost. One example of this is JavaScript-based browser addons which are continually updated and the addons must be repeatedly vetted for each update because of known instances of malicious code injection during updates. Incremental analysis reduces this cumulative cost by using a previous version's solution to accelerate analysis of the current version. Modern incremental analyses are not applicable to dynamic programming languages because they assume an a priori control flow graph, which is not available. In this paper, we propose the first incremental static analysis for JavaScript. We do not require perfect precision, but we show empirically that there is a negligible precision loss in practice. A large part of our technique is a method for matching code between JavaScript program versions, a non-trivial problem for which existing techniques for non-JavaScript languages do not apply. For our benchmarks, drawn from real browser addons and node.js programs, our incremental analysis performance is on average within a factor of two of an optimal incremental analysis.

Document

PDF icon worklist-reuse.pdf