ESEC/FSE'18.November 4-9,2018,Lake Buena Vista,FL,USA Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis context insensitivity exhibits very good and stable scalability We propose the SCALER pointer analysis framework that,given for all programs (but it is much less precise). a total scalability threshold,automatically selects an appropriate Scalability of context-sensitivity is not only unpredictable,but also variant of context sensitivity for each method in the program tends to be bimodal [32]:when analyzing a given program with being analyzed(Section 3).The approach relies on the concept of scalability-critical methods that helps explain why context- existing context-sensitivity techniques,usually the analysis either sensitive pointer analysis is sometimes unscalable. terminates relatively quickly(we say that the analysis is scalable in this case),or it blows up and does not terminate even with very We present a novel technique to efficiently estimate the amount high time limits of points-to information that would be needed to analyze each Consider a scenario where the task is to analyze a set of pro- method with different variants of context sensitivity,using ob- grams within a given time budget,for example as part of a large- ject allocation graphs(Section 4). scale security analysis.Should one pick a precise context-sensitive We describe our open-source implementation(Section 5). pointer analysis and take the risk that it may not scale for sev- We conduct extensive experiments by comparing SCALER with eral programs,or pick a scalable,context-insensitive,analysis that state-of-the-art pointer analyses (Section 6).The evaluation sacrifices precision for all programs?One answer is introspective demonstrates that SCALER achieves predictable scalability for all analysis [33],which tunes context sensitivity according to the re- the evaluated programs in one shot,while providing a precision sults of a first-pass,context-insensitive analysis.However,that that matches or even exceeds that of the best alternatives.As approach is,as the authors put it,an "if all else fails"analysis that an example,the jython benchmark from DaCapo is known to should only be used if traditional context-sensitive algorithms fail. cause problems for context-sensitive pointer analysis [15,38]: Thus,computing resources are wasted,because one has to wait 1type is the most precise conventional pointer analysis that is until the context-sensitive analysis reaches a timeout,before the scalable for jython,taking around 33 minutes on an ordinary introspective analysis is run as a fallback. PC,while 2obj and 2type do not complete within 3 hours.In In this paper,we present a pointer analysis framework named comparison,SCALER achieves significantly better precision than SCALER that has the following desirable properties. both 1type and the state-of-the-art introspective analysis [33] (i)Users only have to apply SCALER once for each program,without and takes under 8 minutes. a need to experiment with different variants of context sensitiv- 2 BACKGROUND ity. (ii)SCALER prioritizes scalability.Given a reasonable time budget, Pointer analysis typically consists of computing the points-to sets SCALER can be expected to finish analyzing any given program of variables in the program text.2 Points-to sets form a relation P within the budget.More specifically,if a context-insensitive between variables and abstract objects,i.e.,a subset of pointer analysis is scalable for P,users can confidently expect Var x Obi that SCALER will also scale for P. with Var being the set of program variables and Obj the set of (iii)SCALER is able to achieve precision comparable to,or better abstract objects.Abstract objects are typically represented as al- than that of the most precise context-sensitivity variant that is location sites,i.e.,instructions that allocate objects (e.g.,new in scalable for P.That is,the user does not need to manually pick a Java)[6].An allocation site stands for all the run-time objects it can context-sensitivity variant a priori,but can expect to effectively possibly allocate.This representation by nature loses significant match the best option that one could have picked,on a single precision.A program variable corresponds to many run-time incar- analysis run.Experimentally,this precision is much greater than nations during program execution-not just for executions under prior introspective analyses [33]. different inputs but also for different instances of local variables The key insight of SCALER is that the size of context-sensitive during distinct activations of the same method. points-to information (or,equivalently,the total memory consumed) To combat the loss of precision,context-sensitive pointer anal- is the critical factor that determines whether analysis of a given pro- ysis enhances the computed relations to maintain a more precise gram using a particular context-sensitivity variant is scalable or not, abstraction of variables and objects [30,35].Variables get quali- and that it is possible to estimate the size of context-sensitive points- fied with contexts,to distinguish their different incarnations.The to information produced by different kinds of context sensitivity analysis effectively computes a subset of without conducting the context-sensitive analysis.This estimate Ctx x Var x Obj can be computed using a cheap,context-insensitive pre-analysis, where Ctx is a set of contexts for variables.3 This precision is valu- by leveraging the notion of object allocation graphs [37]. able for intermediate analysis computations,even though the final SCALER is parameterized by a number called the total scalability analysis results get collapsed in the easily-understandable Var x Obj threshold (TST),which can be selected based on the available mem- relation:distinguishing the behavior of a much-used variable or ory.For a given TST,SCALER automatically adapts different kinds of context sensitivity (e.g.,object-sensitivity,type-sensitivity)and con- 2A second formuation is that of alias analysis which computes the pairs of variables text insensitivity,at the level of individual methods in the program, or expressions that can be aliased.For most published algorithms,computing points-to sets and computing alias sets are equivalent problems:one can be mapped to the other to stay within the desired bound and thereby retain scalability. without affecting the algorithm's fundamental precision or scalability. while utilizing the available space to maximize precision. For simplicity of exposition we ignore context sensitivity for abstract objects(aka heap cloning)which also qualifies Obj with a set of heap contexts,HCtr,in much the In summary,this paper makes the following contributions: same way as qualifying variables. 130ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis • context insensitivity exhibits very good and stable scalability for all programs (but it is much less precise). Scalability of context-sensitivity is not only unpredictable, but also tends to be bimodal [32]: when analyzing a given program with existing context-sensitivity techniques, usually the analysis either terminates relatively quickly (we say that the analysis is scalable in this case), or it blows up and does not terminate even with very high time limits. Consider a scenario where the task is to analyze a set of pro￾grams within a given time budget, for example as part of a large￾scale security analysis. Should one pick a precise context-sensitive pointer analysis and take the risk that it may not scale for sev￾eral programs, or pick a scalable, context-insensitive, analysis that sacrifices precision for all programs? One answer is introspective analysis [33], which tunes context sensitivity according to the re￾sults of a first-pass, context-insensitive analysis. However, that approach is, as the authors put it, an łif all else failsž analysis that should only be used if traditional context-sensitive algorithms fail. Thus, computing resources are wasted, because one has to wait until the context-sensitive analysis reaches a timeout, before the introspective analysis is run as a fallback. In this paper, we present a pointer analysis framework named Scaler that has the following desirable properties. (i) Users only have to apply Scaler once for each program, without a need to experiment with different variants of context sensitiv￾ity. (ii) Scaler prioritizes scalability. Given a reasonable time budget, Scaler can be expected to finish analyzing any given program P within the budget. More specifically, if a context-insensitive pointer analysis is scalable for P, users can confidently expect that Scaler will also scale for P. (iii) Scaler is able to achieve precision comparable to, or better than that of the most precise context-sensitivity variant that is scalable for P. That is, the user does not need to manually pick a context-sensitivity variant a priori, but can expect to effectively match the best option that one could have picked, on a single analysis run. Experimentally, this precision is much greater than prior introspective analyses [33]. The key insight of Scaler is that the size of context-sensitive points-to information (or, equivalently, the total memory consumed) is the critical factor that determines whether analysis of a given pro￾gram using a particular context-sensitivity variant is scalable or not, and that it is possible to estimate the size of context-sensitive points￾to information produced by different kinds of context sensitivity without conducting the context-sensitive analysis. This estimate can be computed using a cheap, context-insensitive pre-analysis, by leveraging the notion of object allocation graphs [37]. Scaler is parameterized by a number called the total scalability threshold (TST), which can be selected based on the available mem￾ory. For a given TST, Scaler automatically adapts different kinds of context sensitivity (e.g., object-sensitivity, type-sensitivity) and con￾text insensitivity, at the level of individual methods in the program, to stay within the desired bound and thereby retain scalability, while utilizing the available space to maximize precision. In summary, this paper makes the following contributions: • We propose the Scaler pointer analysis framework that, given a total scalability threshold, automatically selects an appropriate variant of context sensitivity for each method in the program being analyzed (Section 3). The approach relies on the concept of scalability-critical methods that helps explain why context￾sensitive pointer analysis is sometimes unscalable. • We present a novel technique to efficiently estimate the amount of points-to information that would be needed to analyze each method with different variants of context sensitivity, using ob￾ject allocation graphs (Section 4). • We describe our open-source implementation (Section 5). • We conduct extensive experiments by comparing Scaler with state-of-the-art pointer analyses (Section 6). The evaluation demonstrates that Scaler achieves predictable scalability for all the evaluated programs in one shot, while providing a precision that matches or even exceeds that of the best alternatives. As an example, the jython benchmark from DaCapo is known to cause problems for context-sensitive pointer analysis [15, 38]: 1type is the most precise conventional pointer analysis that is scalable for jython, taking around 33 minutes on an ordinary PC, while 2obj and 2type do not complete within 3 hours. In comparison, Scaler achieves significantly better precision than both 1type and the state-of-the-art introspective analysis [33] and takes under 8 minutes. 2 BACKGROUND Pointer analysis typically consists of computing the points-to sets of variables in the program text.2 Points-to sets form a relation between variables and abstract objects, i.e., a subset of Var × Obj with Var being the set of program variables and Obj the set of abstract objects. Abstract objects are typically represented as al￾location sites, i.e., instructions that allocate objects (e.g., new in Java) [6]. An allocation site stands for all the run-time objects it can possibly allocate. This representation by nature loses significant precision. A program variable corresponds to many run-time incar￾nations during program executionÐnot just for executions under different inputs but also for different instances of local variables during distinct activations of the same method. To combat the loss of precision, context-sensitive pointer anal￾ysis enhances the computed relations to maintain a more precise abstraction of variables and objects [30, 35]. Variables get quali￾fied with contexts, to distinguish their different incarnations. The analysis effectively computes a subset of Ctx × Var × Obj where Ctx is a set of contexts for variables.3 This precision is valu￾able for intermediate analysis computations, even though the final analysis results get collapsed in the easily-understandable Var ×Obj relation: distinguishing the behavior of a much-used variable or 2A second formulation is that of alias analysis, which computes the pairs of variables or expressions that can be aliased. For most published algorithms, computing points-to sets and computing alias sets are equivalent problems: one can be mapped to the other without affecting the algorithm’s fundamental precision or scalability. 3 For simplicity of exposition, we ignore context sensitivity for abstract objects (a.k.a., heap cloning) which also qualifies Obj with a set of heap contexts, HCtx, in much the same way as qualifying variables. 130