Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity Yue Li Tian Tan Anders Moller Yannis Smaragdakis Aarhus University Aarhus University Aarhus University University of Athens yueli@cs.au.dk tiantan@cs.au.dk amoeller@cs.au.dk smaragd@di.uoa.gr ABSTRACT timeout(>10800) ▣2obj▣2type▣Cl Context-sensitivity is important in pointer analysis to ensure high precision,but existing techniques suffer from unpredictable scala- bility.Many variants of context-sensitivity exist,and it is difficult to choose one that leads to reasonable analysis time and obtains 5000 high precision,without running the analysis multiple times. 4000 We present the SCALER framework that addresses this problem SCALER efficiently estimates the amount of points-to information 3000 that would be needed to analyze each method with different variants of context-sensitivity.It then selects an appropriate variant for 2000 each method so that the total amount of points-to information is bounded,while utilizing the available space to maximize precision. Our experimental results demonstrate that SCALER achieves pre- 份导时8济付 dictable scalability for all the evaluated programs(e.g.,speedups can reach 10x for 2-object-sensitivity),while providing a precision dbugs pmd soot that matches or even exceeds that of the best alternative techniques. Figure 1:Comparison of running time(seconds)of 2-object sensitivity,2-type sensitivity,and context-insensitive analy- CCS CONCEPTS ses.The y-axis is truncated to 7000 seconds for readability Theory of computation-Program analysis; and all truncated cases reach the time budget,10800 seconds. KEYWORDS challenging to produce precise analysis results without sacrificing scalability [12.30.35].Thus,for decades,researchers have contin- static analysis,points-to analysis,Java ued to develop sophisticated pointer analysis techniques [2,14- ACM Reference Format: 16,18,22,24,25,32,33,37,38]. Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis.2018.Scalability- One of the key mechanisms for achieving high analysis precision First Pointer Analysis with Self-Tuning Context-Sensitivity.In Proceedings is context sensitivity,which allows each program method to be of the 26th ACM Joint European Software Engineering Conference and Sympo- analyzed differently according to the context it is used in [17]. sium on the Foundations of Software Engineering (ESEC/FSE'18),November Context sensitivity has different variants,depending on the kind of 4-9.2018,Lake Buena Vista,FL,USA.ACM,New York,NY,USA,12 pages. context information used.For Java programs,object-sensitivity [25] https:/doi.org/10.1145/3236024.3236041 and type-sensitivity [32]have proven to be quite effective.The 1 INTRODUCTION former is strictly more precise but less efficient than the latter [15, 37].However,with any available variant,although the analysis can Pointer analysis is a family of static analysis techniques that provide gain in precision,scalability is known to be unpredictable [33,38]. a foundation for many other analyses and software engineering in the sense that programs very similar in size and other complexity tasks,such as program slicing [36,39].reflection analysis [19,31], metrics may have completely different scalability profiles. bug detection[13,26],security analysis [1,23],program verifica- Figure 1 shows time spent analyzing 10 real-world Java pro- tion [8,27],and program debugging and comprehension [5,21]. grams'under 2-object-sensitivity (2obj)[25],which is among The goal of pointer analysis is to statically compute a set of objects the most precise variants of context sensitivity,2-type-sensitivity (abstracted as their allocation sites)that a program variable may (2type)[32],and context-insensitivity(CI).We observe that point to during run time.Although stating this goal is simple,it is 2obj is not scalable for 6 out of 10 programs within 3 hours Permission to make digital or hard copies of all or part of this work for personal or while it can finish running for 3 programs within 5 minutes; classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation program size is far from a reliable predictor-for example,jython on the first page.Copyrights for components of this work owned by others than the (12 718 methods)is smaller than briss(26 582 methods),how author(s)must be honored.Abstracting with credit is permitted To copy otherwise.or republish,to post on servers or to redistribute to lists,requires prior specific permission ever,2type is not scalable for the former but scalable for the and/or a fee.Request permissions from permissions@acm.org. latter; ESEC/FSE '18.November 4-9,2018,Lake Buena Vista,FL.USA 2018 Copyright held by the owner/author(s).Publication rights licensed to ACM ACM1SBN978-1-4503-5573-5/18/11..$15.00 IThese are all popular open-source applications,including the heaviest(jython and ttps:/doi.org/10.1145/3236024.3236041 eclipse)of the DaCapo benchmarks [3]. 129

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity Yue Li Aarhus University yueli@cs.au.dk Tian Tan Aarhus University tiantan@cs.au.dk Anders Mùller Aarhus University amoeller@cs.au.dk Yannis Smaragdakis University of Athens smaragd@di.uoa.gr ABSTRACT Context-sensitivity is important in pointer analysis to ensure high precision, but existing techniques suffer from unpredictable scala￾bility. Many variants of context-sensitivity exist, and it is difficult to choose one that leads to reasonable analysis time and obtains high precision, without running the analysis multiple times. We present the Scaler framework that addresses this problem. Scaler efficiently estimates the amount of points-to information that would be needed to analyze each method with different variants of context-sensitivity. It then selects an appropriate variant for each method so that the total amount of points-to information is bounded, while utilizing the available space to maximize precision. Our experimental results demonstrate that Scaler achieves pre￾dictable scalability for all the evaluated programs (e.g., speedups can reach 10x for 2-object-sensitivity), while providing a precision that matches or even exceeds that of the best alternative techniques. CCS CONCEPTS · Theory of computation → Program analysis; KEYWORDS static analysis, points-to analysis, Java ACM Reference Format: Yue Li, Tian Tan, Anders Mùller, and Yannis Smaragdakis. 2018. Scalability￾First Pointer Analysis with Self-Tuning Context-Sensitivity. In Proceedings of the 26th ACM Joint European Software Engineering Conference and Sympo￾sium on the Foundations of Software Engineering (ESEC/FSE ’18), November 4ś9, 2018, Lake Buena Vista, FL, USA. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3236024.3236041 1 INTRODUCTION Pointer analysis is a family of static analysis techniques that provide a foundation for many other analyses and software engineering tasks, such as program slicing [36, 39], reflection analysis [19, 31], bug detection [13, 26], security analysis [1, 23], program verifica￾tion [8, 27], and program debugging and comprehension [5, 21]. The goal of pointer analysis is to statically compute a set of objects (abstracted as their allocation sites) that a program variable may point to during run time. Although stating this goal is simple, it is Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. ESEC/FSE ’18, November 4ś9, 2018, Lake Buena Vista, FL, USA © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-5573-5/18/11. . . $15.00 https://doi.org/10.1145/3236024.3236041 285 2458 53 93 5374 95 960 289 2950 45 54 1203 228 48 135 49 117 112 22 22 67 994 0 1000 2000 3000 4000 5000 6000 2obj 2type CI timeout (>10800) Figure 1: Comparison of running time (seconds) of 2-object sensitivity, 2-type sensitivity, and context-insensitive analy￾ses. The y-axis is truncated to 7000 seconds for readability, and all truncated cases reach the time budget, 10800 seconds. challenging to produce precise analysis results without sacrificing scalability [12, 30, 35]. Thus, for decades, researchers have contin￾ued to develop sophisticated pointer analysis techniques [2, 14ś 16, 18, 22, 24, 25, 32, 33, 37, 38]. One of the key mechanisms for achieving high analysis precision is context sensitivity, which allows each program method to be analyzed differently according to the context it is used in [17]. Context sensitivity has different variants, depending on the kind of context information used. For Java programs, object-sensitivity [25] and type-sensitivity [32] have proven to be quite effective. The former is strictly more precise but less efficient than the latter [15, 37]. However, with any available variant, although the analysis can gain in precision, scalability is known to be unpredictable [33, 38], in the sense that programs very similar in size and other complexity metrics may have completely different scalability profiles. Figure 1 shows time spent analyzing 10 real-world Java pro￾grams1 under 2-object-sensitivity (2obj) [25], which is among the most precise variants of context sensitivity, 2-type-sensitivity (2type) [32], and context-insensitivity (CI). We observe that • 2obj is not scalable for 6 out of 10 programs within 3 hours, while it can finish running for 3 programs within 5 minutes; • program size is far from a reliable predictorÐfor example, jython (12 718 methods) is smaller than briss (26 582 methods), how￾ever, 2type is not scalable for the former but scalable for the latter; 1These are all popular open-source applications, including the heaviest (jython and eclipse) of the DaCapo benchmarks [3]. 129

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. 130

ESEC/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

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE'18.November 4-9,2018,Lake Buena Vista.FL,USA object (e.g.,in a library method)according to the context in which 3.1.1 Scalability-Critical Methods.The scalability of a context- it is used helps the precision at all use sites of the common code. sensitive pointer analysis is closely linked to the amount of points-to Two observations on context sensitivity will be important in information it produces,i.e.,the size ofrelation pt'Ctxx VarxObj. our subsequent discussion.First,contexts qualify variables but are The challenge that ScALER addresses is to closely upper bound the generally chosen per method.The main use of context sensitivity size of pt'without performing a context-sensitive analysis,given is to distinguish different activations of the same method(e.g. only the result,pt Var x Obj,of a context-insensitive analysis. "stack frames"for the same procedure,in traditional stack-based Prior approaches have made similar attempts to obtain scalability, languages),which create fresh instances of all local variables at run but without a concrete model to predict scalability effectively,as time.Therefore.all local variables of the same method have the explained in Section 7. same set of contexts By then distinguishing which parts of the program can contribute Second,the worst-case complexity of a context-sensitive pointer disproportionately to the total size of pt',SCALER can adjust its analysis is much higher than that of a context-insensitive one:the context sensitivity at different methods,to yield higher precision number of computed points-to facts,and hence the complexity of only when this does not endanger scalability. the analysis,increases in the worst case multiplicatively by the To achieve this,we introduce the concept of scalability-critical size of the set Ctx.However,in the common case,the precision of methods.These are methods that are likely to yield very large context sensitivity often compensates,reducing the analysis com- amounts of context-sensitive points-to information.Whether a plexity:different contexts divide the points-to sets of variables into method is scalability-critical depends on the context sensitivity in non-overlapping subsets.In the ideal case,if a context-insensitive question.For example,a method may be scalability-critical under analysis computes a points-to relation pt Var x Obj,a context- 2obj(a 2-object-sensitive analysis)but not under 2type(a 2-type- sensitive analysis would compute a relation pt'Ctxx Varx Obj sensitive analysis). that is not greater in cardinality than Var x Obj.The extra precision Definition 3.1 (Scalability-Critical Methods).A method m is of the Ctx information would be enough to split the original points- scalability-critical (or,for brevity,just critical)under context sensi- to sets into disjoint subsets.This observation also hints at why tivity c,if the value of the product #ctx#ptsm exceeds a given context sensitivity has unpredictable scalability:When it works scalability threshold STp,where well to maintain precision,its cost is modest to none.When it fails to do so,however,the cost is orders-of-magnitude higher. .#ctx is an estimate of the number of contexts for m if using The actual definitions of the set Ctx can vary widely.Three context-sensitivity variant c,computed using a fast context- main categories are call-site sensitivity,object sensitivity,and type insensitive analysis, sensitivity: #ptsm is the sum of the sizes of the points-to sets for all local variables in m,computed using the same context-insensitive Call-site sensitivity has Ctx be a sequence of call sites,i.e., analysis,and instructions that call the method in which the qualified variable STp is a value that can be given by users(Section 3.1.2)or has been declared. computed automatically(Section 3.2)for program p. .Object sensitivity has Ctx be a sequence of abstract objects:they are the receiver object of the method containing the qualified That is,we upper-bound the potential contribution of a method variable,the receiver object of the method that allocated the to the context-sensitive points-to set(pt'Ctxx Varx Obj)by com previous receiver object,etc. puting the number of potential combinations of possible abstract Type sensitivity keeps the same information as object sensitiv- objects(i.e.,a subset of Obj)and contexts (i.e.,a subset of Ctx)that ity,but objects used as contexts are collapsed not per allocation may pertain to the method.The individual numbers are guaranteed instruction but per class that contains it. to be upper bounds,since they are computed by a less precise(and, We refer the reader to surveys that discuss the options in full de- thus,conservatively over-approximate)context-insensitive analy- tail [30,351. sis.Accordingly,their product is guaranteed to be an upper bound of the number of potential combinations. 3 THE SCALER FRAMEWORK The intuition behind Definition 3.1 is that a method m may cause scalability problems for different reasons:(1)m is being analyzed in In this section,we present an overview of the SCALER approach. too many contexts,(2)too much points-to information is computed We first describe the idea of scalability thresholds,which is the within m,or(3)although the individual numbers of contexts and key to predictable scalability (Section 3.1).Next,we explain how points-to facts for m are not very large,their product is.For this SCALER automatically chooses a suitable scalability threshold for reason,the product of the estimates #ctx and #ptsm gives an each program,based on a single parameter called the total scalability indication of potential scalability problems. threshold that depends only on the available space for storing points- It makes sense to perform this reasoning at the method level, to information(Section 3.2).These ideas are then collected in the since(as discussed in Section 2)decisions on context sensitivity are overall SCALER framework(Section 3.3). made per-method,i.e.,for all local variables of a method together. The number #ptsm can be obtained directly from the context- 3.1 Scalability Thresholds insensitive points-to relation:#ptsm=vemIpt(v,).Comput- We begin by introducing the concept of scalability-critical meth- ing #ctx is less straightforward.This is one of the technical ods(Section 3.1.1),and we then leverage this concept to address novelties of the approach,and we postpone its discussion until unscalability (Section 3.1.2). Section 4. 131

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA object (e.g., in a library method) according to the context in which it is used helps the precision at all use sites of the common code. Two observations on context sensitivity will be important in our subsequent discussion. First, contexts qualify variables but are generally chosen per method. The main use of context sensitivity is to distinguish different activations of the same method (e.g., łstack framesž for the same procedure, in traditional stack-based languages), which create fresh instances of all local variables at run time. Therefore, all local variables of the same method have the same set of contexts. Second, the worst-case complexity of a context-sensitive pointer analysis is much higher than that of a context-insensitive one: the number of computed points-to facts, and hence the complexity of the analysis, increases in the worst case multiplicatively by the size of the set Ctx. However, in the common case, the precision of context sensitivity often compensates, reducing the analysis com￾plexity: different contexts divide the points-to sets of variables into non-overlapping subsets. In the ideal case, if a context-insensitive analysis computes a points-to relation pt ⊆ Var × Obj, a context￾sensitive analysis would compute a relation pt′ ⊆ Ctx × Var × Obj that is not greater in cardinality than Var ×Obj. The extra precision of the Ctx information would be enough to split the original points￾to sets into disjoint subsets. This observation also hints at why context sensitivity has unpredictable scalability: When it works well to maintain precision, its cost is modest to none. When it fails to do so, however, the cost is orders-of-magnitude higher. The actual definitions of the set Ctx can vary widely. Three main categories are call-site sensitivity, object sensitivity, and type sensitivity: • Call-site sensitivity has Ctx be a sequence of call sites, i.e., instructions that call the method in which the qualified variable has been declared. • Object sensitivity has Ctx be a sequence of abstract objects: they are the receiver object of the method containing the qualified variable, the receiver object of the method that allocated the previous receiver object, etc. • Type sensitivity keeps the same information as object sensitiv￾ity, but objects used as contexts are collapsed not per allocation instruction but per class that contains it. We refer the reader to surveys that discuss the options in full de￾tail [30, 35]. 3 THE SCALER FRAMEWORK In this section, we present an overview of the Scaler approach. We first describe the idea of scalability thresholds, which is the key to predictable scalability (Section 3.1). Next, we explain how Scaler automatically chooses a suitable scalability threshold for each program, based on a single parameter called the total scalability threshold that depends only on the available space for storing points￾to information (Section 3.2). These ideas are then collected in the overall Scaler framework (Section 3.3). 3.1 Scalability Thresholds We begin by introducing the concept of scalability-critical meth￾ods (Section 3.1.1), and we then leverage this concept to address unscalability (Section 3.1.2). 3.1.1 Scalability-Critical Methods. The scalability of a context￾sensitive pointer analysis is closely linked to the amount of points-to information it produces, i.e., the size of relation pt′ ⊆ Ctx×Var×Obj. The challenge that Scaler addresses is to closely upper bound the size of pt′ without performing a context-sensitive analysis, given only the result, pt ⊆ Var × Obj, of a context-insensitive analysis. Prior approaches have made similar attempts to obtain scalability, but without a concrete model to predict scalability effectively, as explained in Section 7. By then distinguishing which parts of the program can contribute disproportionately to the total size of pt′ , Scaler can adjust its context sensitivity at different methods, to yield higher precision only when this does not endanger scalability. To achieve this, we introduce the concept of scalability-critical methods. These are methods that are likely to yield very large amounts of context-sensitive points-to information. Whether a method is scalability-critical depends on the context sensitivity in question. For example, a method may be scalability-critical under 2obj (a 2-object-sensitive analysis) but not under 2type (a 2-type￾sensitive analysis). Definition 3.1 (Scalability-Critical Methods). A method m is scalability-critical (or, for brevity, just critical) under context sensi￾tivity c, if the value of the product #ctxc m·#ptsm exceeds a given scalability threshold STp , where • #ctxc m is an estimate of the number of contexts for m if using context-sensitivity variant c, computed using a fast context￾insensitive analysis, • #ptsm is the sum of the sizes of the points-to sets for all local variables in m, computed using the same context-insensitive analysis, and • STp is a value that can be given by users (Section 3.1.2) or computed automatically (Section 3.2) for program p. That is, we upper-bound the potential contribution of a method to the context-sensitive points-to set (pt′ ⊆ Ctx×Var×Obj) by com￾puting the number of potential combinations of possible abstract objects (i.e., a subset of Obj) and contexts (i.e., a subset of Ctx) that may pertain to the method. The individual numbers are guaranteed to be upper bounds, since they are computed by a less precise (and, thus, conservatively over-approximate) context-insensitive analy￾sis. Accordingly, their product is guaranteed to be an upper bound of the number of potential combinations. The intuition behind Definition 3.1 is that a methodm may cause scalability problems for different reasons: (1) m is being analyzed in too many contexts, (2) too much points-to information is computed within m, or (3) although the individual numbers of contexts and points-to facts for m are not very large, their product is. For this reason, the product of the estimates #ctxc m and #ptsm gives an indication of potential scalability problems. It makes sense to perform this reasoning at the method level, since (as discussed in Section 2) decisions on context sensitivity are made per-method, i.e., for all local variables of a method together. The number #ptsm can be obtained directly from the context￾insensitive points-to relation: #ptsm = Í v ∈m |pt(v, _)|. Comput￾ing #ctxc m is less straightforward. This is one of the technical novelties of the approach, and we postpone its discussion until Section 4. 131

ESEC/FSE'18,November 4-9,2018,Lake Buena Vista,FL,USA Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis #ctx#ptsm c=2obj ∑m#ctx号，#ptsn 1000000 -c=2type ctx1,p1→obj1 c=1type ct2,p2→obj4 cbx3,p3-→obj9 Program 2 100000 #ct乐·#pts STp ctxk,Pm→ob TST is Memor 10000 Related Figure 3:Context-sensitive points-to information and TST. 0 points-to relation exhausts the available RAM.The scalability of method methodaooo methodaooo 卡1type2hype中 2obj meth pointer analysis is therefore related to the features of the analysis environment,most importantly the memory size. Figure 2:Choosing a context-sensitivity strategy c for the We now show how SCALER determines a scalability threshold for methods of program p based on a scalability threshold,STp. a given program,based on the concept of a total scalability threshold that represents the analysis capacity and can be selected based on, 3.1.2 Choosing Context Sensitivity Strategies.Given a scalability for example,the available memory,independently of the program threshold STp,ScALER classifies each method m as scalability-critical being analyzed. or not,relative to a context sensitivity variant.It then ensures scal- ability for critical methods by selecting a cheaper (less precise) Definition 3.2 (Total Scalability Threshold).A total scalability context sensitivity variant for them.As a result,different methods threshold(TST)is a number that satisfies the inequality E(STp)< will be analyzed with different context sensitivity variants. TST where E(STp)is the estimated cost for the given value of STp. Assume there is a set of context sensitivity variants computed as the sum of the sizes of the points-to relations(cf.Defi- nition 3.1)for all the methods in the program: C={c1,c2,,cn} where ci is typically more precise(but less efficient)than ci-1.For 8(STp)=∑m#ctxm leeC(,sTp）.ptSm example,this set could be C={1type,2type,2obj). Figure 2 illustrates(imaginary)distributions of #ctx#ptsm Figure 3 illustrates the concept.The complexity of a pointer values (log-scale y-axis)for a 10 000-method program,with each analysis(running on a given program)is closely related to the size method m(x-axis)ranked by decreasing value of #ctxm#ptsm of the points-to information,which is upper-bounded by E(STp). under different context sensitivity variants c e C.Assume a suitable The TST of the environment can be seen as analogous to the volume STp value has been chosen(we explain in Section 3.2 how this can of a container.The volume of the points-to information computed be done).According to Definition 3.1,the first 4000 methods are by the analysis has to fit in the TST volume for the analysis to scalability-critical under 2obj,and the first 2 000 are scalability- scale,i.e.,E(STp)<TST.This effectively normalizes the analysis critical also under 2type.All 10 000 methods are non-scalability- capacity for all programs,regardless of the number of methods they critical under 1 type. contain,or the variants of context sensitivity employed.We discuss For each method m,SCALER selects the most precise context- in Section 6 the actual TST values used in our experiments. sensitivity variant ci E C for which m is not scalability-critical, Importantly the TSTinequality,depends and context-insensitivity(Cl)if none exists.That is,method m is on the choice of context sensitivity,which can vary based on the analyzed with context-sensitivity SelectCtx(m,STp): approach described in Section 3.1.The self tuning approach of Cn if m is non-critical under cn for STp ScALER consists of computing.given the TST,an appropriate value of STp for a program p that will be used to assign appropriate SelectCtx(m,STp)= Ck if 3ck:m is non-critical under ck A m is critical under ck+for STp context-sensitivity variants to p's methods. CI otherwise To maximize precision while ensuring scalability,SCALER needs to pick the largest STp that satisfies the TST inequality.In this way. For example,in Figure 2,methods 1 to 1 999 will be analyzed as many methods as possible are analyzed with the most precise using 1type,methods 2000 to 3 999 using 2type,and methods 4000 context sensitivity that the total analysis capacity can afford.That to 10000 using 2obj. is,SCALER needs to pick max{STp E(STp)s TST}. The remaining issue,which we address in the following section, Figure 4 illustrates the mechanism using the distribution of Fig- is how to choose an appropriate scalability threshold for a given ure 2.This time,STp is not given by the user in advance.Instead, program to be analyzed. its value is computed to satisfy the inequality shown in Figure 4. For a candidate STp value,each method is classified as detailed in 3.2 Total Scalability Thresholds Section 3.1.2:it is assigned the most precise context sensitivity that As discussed earlier,the overall cost of a context-sensitive pointer keeps it from being scalability-critical. analysis is closely linked to the size of the points-to relation being In the case of Figure 4,the value of E(STp)for this program computed.An analysis that fails to terminate within realistic time corresponds to the sum of the areas of A1,A2,and A3.If A1 +A2 limits often does so because the space needed to represent the +A3 under the candidate STp is below TST,then STp is viable,but 132

ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis 2type 2obj 0 10 000 ST method 1 method 2000 method 4000 method 10 000 1type 2type 1type 1 000 000 2obj 100 000 p #ctx c m·#pts m c = c = c = Figure 2: Choosing a context-sensitivity strategy c for the methods of program p based on a scalability threshold, STp . 3.1.2 Choosing Context Sensitivity Strategies. Given a scalability threshold STp , Scaler classifies each methodm as scalability-critical or not, relative to a context sensitivity variant. It then ensures scal￾ability for critical methods by selecting a cheaper (less precise) context sensitivity variant for them. As a result, different methods will be analyzed with different context sensitivity variants. Assume there is a set of context sensitivity variants C = { c1, c2, ..., cn } where ci is typically more precise (but less efficient) than ci−1. For example, this set could be C = {1type, 2type, 2obj}. Figure 2 illustrates (imaginary) distributions of #ctxc m·#ptsm values (log-scale y-axis) for a 10 000-method program, with each method m (x-axis) ranked by decreasing value of #ctxc m·#ptsm, under different context sensitivity variantsc ∈ C. Assume a suitable STp value has been chosen (we explain in Section 3.2 how this can be done). According to Definition 3.1, the first 4 000 methods are scalability-critical under 2obj, and the first 2 000 are scalability￾critical also under 2type. All 10 000 methods are non-scalability￾critical under 1type. For each method m, Scaler selects the most precise context￾sensitivity variant ci ∈ C for which m is not scalability-critical, and context-insensitivity (CI) if none exists. That is, method m is analyzed with context-sensitivity SelectCtx(m, STp ): SelectCtx(m, STp ) =    cn if m is non-critical under cn for STp ck if ∃ck : m is non-critical under ck ∧ m is critical under ck+1 for STp CI otherwise For example, in Figure 2, methods 1 to 1 999 will be analyzed using 1type, methods 2 000 to 3 999 using 2type, and methods 4 000 to 10 000 using 2obj. The remaining issue, which we address in the following section, is how to choose an appropriate scalability threshold for a given program to be analyzed. 3.2 Total Scalability Thresholds As discussed earlier, the overall cost of a context-sensitive pointer analysis is closely linked to the size of the points-to relation being computed. An analysis that fails to terminate within realistic time limits often does so because the space needed to represent the TST is Memory- TST Related ctx1, p1 obj1 ctx2, p2 obj4 ctx3, p3 obj9 ctx , p obj k m n … … … … … … … … Program 1 Program 2 #ctx c Σm m·#pts m #ctx c Σm m·#pts m #ctx c Σm m·#pts m Figure 3: Context-sensitive points-to information and TST. points-to relation exhausts the available RAM. The scalability of pointer analysis is therefore related to the features of the analysis environment, most importantly the memory size. We now show how Scaler determines a scalability threshold for a given program, based on the concept of a total scalability threshold that represents the analysis capacity and can be selected based on, for example, the available memory, independently of the program being analyzed. Definition 3.2 (Total Scalability Threshold). A total scalability threshold (TST) is a number that satisfies the inequality E(STp ) ≤ TST where E(STp ) is the estimated cost for the given value of STp , computed as the sum of the sizes of the points-to relations (cf. Defi￾nition 3.1) for all the methods in the program: E(STp ) = Í m #ctx SelectCtx(m,STp ) m · #ptsm Figure 3 illustrates the concept. The complexity of a pointer analysis (running on a given program) is closely related to the size of the points-to information, which is upper-bounded by E(STp ). The TST of the environment can be seen as analogous to the volume of a container. The volume of the points-to information computed by the analysis has to fit in the TST volume for the analysis to scale, i.e., E(STp ) ≤ TST. This effectively normalizes the analysis capacity for all programs, regardless of the number of methods they contain, or the variants of context sensitivity employed. We discuss in Section 6 the actual TST values used in our experiments. Importantly, in the TST inequality, #ctx SelectCtx(m,STp ) m depends on the choice of context sensitivity, which can vary based on the approach described in Section 3.1. The self tuning approach of Scaler consists of computing, given the TST, an appropriate value of STp for a program p that will be used to assign appropriate context-sensitivity variants to p’s methods. To maximize precision while ensuring scalability, Scaler needs to pick the largest STp that satisfies the TST inequality. In this way, as many methods as possible are analyzed with the most precise context sensitivity that the total analysis capacity can afford. That is, Scaler needs to pick max{STp | E(STp ) ≤ TST}. Figure 4 illustrates the mechanism using the distribution of Fig￾ure 2. This time, STp is not given by the user in advance. Instead, its value is computed to satisfy the inequality shown in Figure 4. For a candidate STp value, each method is classified as detailed in Section 3.1.2: it is assigned the most precise context sensitivity that keeps it from being scalability-critical. In the case of Figure 4, the value of E(STp ) for this program corresponds to the sum of the areas of A1, A2, and A3. If A1 + A2 + A3 under the candidate STp is below TST, then STp is viable, but 132

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE'18.November 4-9,2018,Lake Buena Vista.FL,USA #ctxC#ptsm 1000000 -c=2obj SCALER performs this computation by leveraging the object al- c=2type location graph (OAG)structure proposed by Tan et al.[37].With c=1type the OAG,the context computation problem can be formulated as a graph traversal problem.For any program,based on an OAG 100000 derived from pre-analysis(context-insensitive pointer analysis), E(STp)=A1 +A2+A3s TST SCALER computes the number of contexts(#ctx)of every method for each kind of context sensitivity c used(2obj,2type and 1type STp STp is automatically computed in our setup)by enumerating all contexts of the method. 10000 based on the above inequality The OAG of a program is a directed graph.A node of the OAG represents an abstract object,which is identified by its allocation A1 A2 A3 site in the program.An edge of the OAG,say o-02,represents 0 method,methodaooo methodaooo methodsoooo an object-allocation relation between o1 and 02,i.e.,o1 is a receiver object of the method that contains the allocation site of o2.SCALER Figure 4:Selecting the scalability threshold(STp)based on leverages the pre-analysis to build the OAG for the given program the total scalability threshold (TST). The OAG provides a graphical perspective of object-(and type-) sensitivity,i.e.,a k-depth context in object-sensitivity corresponds to higher STp values may also be viable.The maximum such STp a k-node path in the OAG [37].Thus,to compute k-object-sensitive is computed using binary search in a range between 0 and the contexts of a method m,SCALER simply enumerates k-node paths maximum value of #ctxm selectCx(m.ST)sm for all m. in the OAG,leading to the receiver objects of m. Figure 6 illustrates the mechanism with a simple example.The allocation sites are labeled B1.B2,and C1,respectively.Suppose we 3.3 Overall Approach compute 2obj contexts for method m()(line 12)and its receiver Figure 5 shows the overall structure of the ScALER framework. object is C1(allocated at line 16).Further,B1 and B2 are two allocator SCALER is a stand-alone system that automatically selects a per- objects of C1 according to k-object-sensitivity [25,32].The possible method context-sensitivity variant that can subsequently be used (2obj)contexts of m()are [B1,C1]and [B2,C1].The corresponding to configure an existing pointer analysis tool like DooP,WALA,or OAG is given in Figure 6,which shows two 2-node paths that CHORD. are exactly the 2obj contexts for m().Since a context-insensitive Given a program p,a fast (but imprecise)context-insensitive analysis over-approximates the fully precise OAG,some edges may pointer analysis is run first to produce some basic points-to infor- be spurious.However,this is fine,since we only need an upper mation that is used for estimating #ptsm(Section 3.1.1)and #cx bound of the number of possible contexts,to establish scalability. (Section 4).The core of SCALER consists of one component that Type sensitivity is an isomorphic approximation of object sensi- decides the scalability threshold based on a given total scalability tivity [30],thus we can easily derive the contexts for type sensitivity threshold(Section 3.2)and another component that chooses context with the OAG.Following the definition [32],SCALER computes the sensitivity strategies for all methods in the program (Section 3.1.2). contexts for type sensitivity by merely replacing objects in contexts The framework relies on the collection C of context-sensitivity (as computed from the OAG)by the types that contain the alloca- variants.All that is needed for each variant is a mechanism for tion sites of the objects.For example,to compute the contexts for estimating the number of contexts,as presented in Section 4 for method m()(Figure 6)under 2type,SCALER first obtains the 2obj object-sensitivity and type-sensitivity. contexts,i.e.,[B1,C1]and [B2,C1],then replaces B1 and B2 by type A,and C1 by type B.As a result,there is only one context of m() 4 ESTIMATING THE NUMBER OF CONTEXTS under 2type,i.e.,[A,B]. In Section 3.1 we postponed the discussion of how to compute an 5 IMPLEMENTATION upper bound on the number of contexts(#ctx),for a given variant We have implemented SCALER as a stand-alone open-source tool in of context sensitivity c,using only context-insensitive analysis results.This computation is one of the key elements of SCALER and Java,available at http://www.brics.dk/scaler/.SCALER is designed to distinguishes it from prior approaches that have also tried to adapt work with various pointer analysis frameworks such as Doop [4], context sensitivity on a per-method basis [14,33,41]. WALA [7],CHORD [26],and SooT [40].To demonstrate its effective- The computation of the possible contexts for the context-sensitive ness,we have integrated ScALER with Doop [4],a state-of-the-art pointer analysis framework for Java analysis of a method,from only context-insensitive analysis results. is relatively easy for simple variants of context sensitivity,such as In practice,we found that the #ctxfn#ptsm values of some Java call-site sensitivity [28]:the possible contexts are call sites,readily collection methods under package java.util.are very large,be- identifiable in the program code.This computation is nontrivial cause(1)the collection methods are frequently called,thus their for object-and type-sensitivity[24,32],however:the contexts of a #ctx values are large,and (2)many objects are passed to the method are abstract objects,determined by the analysis mechanism. AWe do not consider call-site sensitive analyses(1call,2call)or 1-object sensitivity We are not aware of any prior work that performs a similar com- (1obj)nour evaluation.as these analysis variants are typically both less precise and putation of possible contexts for object-sensitive or type-sensitive less scalable than at least one of the analyses in our setup.The SCALER approach can be analyses,without running the analyses themselves. adapted to any collection of context sensitivity variants,as long as a relative ordering in both increasing precision and cost is possible. 133

Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA method A1 A2 A3 A1 + A2 + A3 ≤ TST is automatically computed based on the above inequality 1 method 2000 method 4000 method 10 000 0 10 000 1 000 000 100 000 STp #ctx c m·#pts m STp 2type 1type c 2obj = c = c = E(STp) = Figure 4: Selecting the scalability threshold (STp ) based on the total scalability threshold (TST). higher STp values may also be viable. The maximum such STp is computed using binary search in a range between 0 and the maximum value of #ctx SelectCtx(m,STp ) m · #ptsm for all m. 3.3 Overall Approach Figure 5 shows the overall structure of the Scaler framework. Scaler is a stand-alone system that automatically selects a per￾method context-sensitivity variant that can subsequently be used to configure an existing pointer analysis tool like Doop, Wala, or Chord. Given a program p, a fast (but imprecise) context-insensitive pointer analysis is run first to produce some basic points-to infor￾mation that is used for estimating #ptsm (Section 3.1.1) and #ctxc m (Section 4). The core of Scaler consists of one component that decides the scalability threshold based on a given total scalability threshold (Section 3.2) and another component that chooses context sensitivity strategies for all methods in the program (Section 3.1.2). The framework relies on the collection C of context-sensitivity variants. All that is needed for each variant is a mechanism for estimating the number of contexts, as presented in Section 4 for object-sensitivity and type-sensitivity. 4 ESTIMATING THE NUMBER OF CONTEXTS In Section 3.1 we postponed the discussion of how to compute an upper bound on the number of contexts (#ctxc m), for a given variant of context sensitivity c, using only context-insensitive analysis results. This computation is one of the key elements of Scaler and distinguishes it from prior approaches that have also tried to adapt context sensitivity on a per-method basis [14, 33, 41]. The computation of the possible contexts for the context-sensitive analysis of a method, from only context-insensitive analysis results, is relatively easy for simple variants of context sensitivity, such as call-site sensitivity [28]: the possible contexts are call sites, readily identifiable in the program code. This computation is nontrivial for object- and type-sensitivity[24, 32], however: the contexts of a method are abstract objects, determined by the analysis mechanism. We are not aware of any prior work that performs a similar com￾putation of possible contexts for object-sensitive or type-sensitive analyses, without running the analyses themselves. Scaler performs this computation by leveraging the object al￾location graph (OAG) structure proposed by Tan et al. [37]. With the OAG, the context computation problem can be formulated as a graph traversal problem. For any program, based on an OAG derived from pre-analysis (context-insensitive pointer analysis), Scaler computes the number of contexts (#ctxc m) of every method for each kind of context sensitivity c used (2obj, 2type and 1type in our setup) by enumerating all contexts of the method.4 The OAG of a program is a directed graph. A node of the OAG represents an abstract object, which is identified by its allocation site in the program. An edge of the OAG, say o1 → o2, represents an object-allocation relation between o1 and o2, i.e., o1 is a receiver object of the method that contains the allocation site of o2. Scaler leverages the pre-analysis to build the OAG for the given program. The OAG provides a graphical perspective of object- (and type-) sensitivity, i.e., a k-depth context in object-sensitivity corresponds to a k-node path in the OAG [37]. Thus, to compute k-object-sensitive contexts of a method m, Scaler simply enumerates k-node paths in the OAG, leading to the receiver objects of m. Figure 6 illustrates the mechanism with a simple example. The allocation sites are labeled B1, B2, and C1, respectively. Suppose we compute 2obj contexts for method m() (line 12) and its receiver object is C1 (allocated at line 16). Further, B1 and B2 are two allocator objects of C1 according to k-object-sensitivity [25, 32]. The possible (2obj) contexts of m() are [B1,C1] and [B2,C1]. The corresponding OAG is given in Figure 6, which shows two 2-node paths that are exactly the 2obj contexts for m(). Since a context-insensitive analysis over-approximates the fully precise OAG, some edges may be spurious. However, this is fine, since we only need an upper bound of the number of possible contexts, to establish scalability. Type sensitivity is an isomorphic approximation of object sensi￾tivity [30], thus we can easily derive the contexts for type sensitivity with the OAG. Following the definition [32], Scaler computes the contexts for type sensitivity by merely replacing objects in contexts (as computed from the OAG) by the types that contain the alloca￾tion sites of the objects. For example, to compute the contexts for method m() (Figure 6) under 2type, Scaler first obtains the 2obj contexts, i.e., [B1,C1] and [B2,C1], then replaces B1 and B2 by type A, and C1 by type B. As a result, there is only one context of m() under 2type, i.e., [A,B]. 5 IMPLEMENTATION We have implemented Scaler as a stand-alone open-source tool in Java, available at http://www.brics.dk/scaler/. Scaler is designed to work with various pointer analysis frameworks such as Doop [4], Wala [7], Chord [26], and Soot [40]. To demonstrate its effective￾ness, we have integrated Scaler with Doop [4], a state-of-the-art pointer analysis framework for Java. In practice, we found that the #ctxc m·#ptsm values of some Java collection methods under package java.util.* are very large, be￾cause (1) the collection methods are frequently called, thus their #ctxc m values are large, and (2) many objects are passed to the 4We do not consider call-site sensitive analyses (1call, 2call) or 1-object sensitivity (1obj) in our evaluation, as these analysis variants are typically both less precise and less scalable than at least one of the analyses in our setup. The Scaler approach can be adapted to any collection of context sensitivity variants, as long as a relative ordering in both increasing precision and cost is possible. 133