Problem
In Defense of Probabilistic Static Analysis Benjamin Livshits Microsoft Research livshits@microsoft.com Shuvendu K. Lahiri Microsoft Research shuvendu@microsoft.com 1. Introduction In designing a static analysis, one has to trade-off analysis scalabil- ity for analysis precision. While much has been said about clever and useful ways to create static approximations of dynamic pro- gram behavior, at the end of the day, static analysis precision is not elastic. In other words, the analysis designer either over-provisions, designing an algorithm that overly precise, suffering in terms of scalability, or what is often even worse, under-provisions, design- ing an algorithm that is insufficiently precise, often yielding an analysis that is too inaccurate to be deployed.
Approach
Moreover, much of the time, precision of a given static analysis is both over- and under-provisioned. This is because precision is highly dependent on the language features and how (frequently) they are used in the programs of interest. For instance, 1-level ob- ject sensitivity is overkill for most types of code, except it is needed for programs that use factories extensively. Moreover, often, 2- level object sensitivity would be required to handle object factories more accurately. The lack of elasticity in terms of static analysis precision has lead analysis designers to combine or stage their analysis together.
Results
For example, reflection analysis and string analysis are frequently combined with a points-to and analysis of JNI constructs. For C, a pre-processing step may be used to identify various allocation func- tions such as malloc, kalloc, etc. In JavaScript, aliases to eval may need to be identified ahead of other analysis steps. Widely us- able analyses are therefore constructed piecemeal, ultimately re- sulting in a patchwork of different analysis techniques connected together. 2. Elasticity In this paper we claim that we need a more elastic approach to anal- ysi