ESEC/FSE'18.November 4-9,2018,Lake Buena Vista,FL,USA Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis TST:( SCALER Selected Program P Optional context TST-Based STp. ST-Based sensitivity Scalable Precise Points-to Pre-Analysis ST Selection Context Sensitivity for every Pointer Analysis information method of p Figure 5:Overview of the SCALER framework. 1 class A{ 14c1a55B{ costs thousands or hundreds of seconds;2 programs (luindex and void foo(){ 15 void bar(){ B b1 new B()j//B1 1 cc new c();//C1 lusearch)represent simple programs for which 2obj costs only b1.bar(); 17 c.m(); dozens of seconds.These programs are all analyzed with a large 18 Java library:Open JDK 1.6.0_24. 6 void goo(){ 19J 7 B b2 new B();//B2 SCALER uses a default TST value of 30M(million)which exhibits 8 b2.bar(); uniform scalability on all machines in our experimental setup.To 9 18 answer RQ1-RQ3(Section 6.1-6.3),we run the experiments on our 11c1a55C{ default machine with a Xeon E5-2697A 2.6GHz CPU and 48GB of 12 void m(){...} RAM,with the default TST(30M).To answer RQ4,different TST 13 values are considered,and the experiments are also run on machines with smaller and larger memory sizes(Section 6.4). Figure 6:An example illustrating #ctx computation. collection methods,thus their #ptsm values are large.This would 6.1 Scalability and Precision of SCALER-Guided affect STp-based context sensitivity,which may make SCALER pick Pointer Analysis less precise context sensitivity for these methods.However,collec- In this section,we examine the scalability and precision of SCALER- tion methods are important to the precision of pointer analysis,thus guided pointer analysis(SCALER for short)by comparing it with should be analyzed as precisely as possible by ScALER.To address conventional context-sensitive pointer analyses for Java:object- this problem,SCALER treats methods under package java.util. sensitivity [25]and type-sensitivity [32],which are the mainstream specially,explicitly assigning them to be analyzed by the most variants adopted in recent analysis clients.For example,object- precise context sensitivity(i.e.,2obj in our settings). sensitivity is widely adopted in recent Android static analysis frame works [1,9]and type-sensitivity is used in recent reflection analy- 6 EVALUATION sis [20]and security analysis [10]tools. In the evaluation,we investigate the following research questions: Table I shows the results for all analyses.Each program has five rows of data,respectively representing context-insensitive RQ1.Does SCALER consistently achieve scalability,while matching (CI),conventional context-sensitive,SCALER,and two introspective or exceeding the precision of the most precise conventional (IntroA and IntroB)pointer analyses.(The last two analyses will be pointer analyses [25,32]that use the same variant of context- discussed in Section 6.2.)For conventional context-sensitive pointer sensitivity for the entire program? analyses,we consider 2obj,2type,and 1type.Call-site-sensitivity RQ2.How does SCALER fare against introspective analysis [33]that and lobj are not considered as the former is not effective for Java also applies context-sensitivity selectively for the different programs [15,17,37]and the latter is usually both less efficient methods of the program? and less precise than 2type [15,32].As it is virtually impossible to RQ3.What is the overhead of running SCALER?What are the com- predict the scalability of a precise context-sensitive pointer analysis puted values of STp and what are the resulting distributions in advance,to get the most precise conventional analysis results we of SelectCtx in practice? run 2obj,2type,and 1type in the given order(from the most to RQ4.How does SCALER perform with different TST values and the least precise one)until one of them terminates within 3 hours. different memory sizes? So in Table 1,the second row for each program shows the results Experimental Setup.All pointer analyses were performed using of the most precise conventional pointer analysis that is scalable. Doop [29](with the version published in the artifact of [33],which 6.1.1 Scalability of SCALER-Guided Pointer Analysis.In Table 1,the contains the exact setup for different analyses).The time budget third column for each program demonstrates ScALER's extremely for all analyses is 3 hours(10 800 seconds).To demonstrate the good scalability.2obj is not scalable for the first six programs,and generality of SCALER's scalability and precision,we consider 10 even the fast 2type also fails to scale for jython and soot.How- real-world Java programs that cover different levels of program ever,SCALER scales for all of them,with its one-shot principle.In complexity.Five of these programs come from the DaCapo 2006 addition,for the first seven complex and large programs,SCALER benchmark suite and include the toughest-to-analyze programs runs (sometimes significantly)faster than the most precise con- (jython,eclipse).The rest are well-known open-source applica- ventional pointer analysis that is scalable,even if we add SCALER's tions.Concretely,as shown in Table 1,6 programs(jython,soot. pre-analysis time(CI). pmd,briss,jedit and eclipse)represent complex applications for For example,according to past literature and extensive experi- which 2obj is not scalable within 3 hours;2 programs (findbugs ence [15,32,37,38],jython is considered the most troublesome and chart)represent medium-complexity programs for which 2obj program in terms of scalability,among the DaCapo benchmarks [3]. 134ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis TST-Based ST Selection ST-Based Context Sensitivity STp Selected context sensitivity for every method of P Scalable & Precise Pre-Analysis Pointer Analysis Points-to information SCALER TST Optional Program P Figure 5: Overview of the Scaler framework. 1 class A { 2 void foo() { 3 B b1 = new B();//B1 4 b1.bar(); 5 } 6 void goo() { 7 B b2 = new B();//B2 8 b2.bar(); 9 } 10 } 11 class C { 12 void m() {...} 13 } 14 class B { 15 void bar() { 16 C c = new C();//C1 17 c.m(); 18 } 19 } B1 B2 C1 Figure 6: An example illustrating #ctxc m computation. collection methods, thus their #ptsm values are large. This would affect STp -based context sensitivity, which may make Scaler pick less precise context sensitivity for these methods. However, collec￾tion methods are important to the precision of pointer analysis, thus should be analyzed as precisely as possible by Scaler. To address this problem, Scaler treats methods under package java.util.* specially, explicitly assigning them to be analyzed by the most precise context sensitivity (i.e., 2obj in our settings). 6 EVALUATION In the evaluation, we investigate the following research questions: RQ1. Does Scaler consistently achieve scalability, while matching or exceeding the precision of the most precise conventional pointer analyses [25, 32] that use the same variant of context￾sensitivity for the entire program? RQ2. How does Scaler fare against introspective analysis [33] that also applies context-sensitivity selectively for the different methods of the program? RQ3. What is the overhead of running Scaler? What are the com￾puted values of STp and what are the resulting distributions of SelectCtx in practice? RQ4. How does Scaler perform with different TST values and different memory sizes? Experimental Setup. All pointer analyses were performed using Doop [29] (with the version published in the artifact of [33], which contains the exact setup for different analyses). The time budget for all analyses is 3 hours (10 800 seconds). To demonstrate the generality of Scaler’s scalability and precision, we consider 10 real-world Java programs that cover different levels of program complexity. Five of these programs come from the DaCapo 2006 benchmark suite and include the toughest-to-analyze programs (jython, eclipse). The rest are well-known open-source applica￾tions. Concretely, as shown in Table 1, 6 programs (jython, soot, pmd, briss, jedit and eclipse) represent complex applications for which 2obj is not scalable within 3 hours; 2 programs (findbugs and chart) represent medium-complexity programs for which 2obj costs thousands or hundreds of seconds; 2 programs (luindex and lusearch) represent simple programs for which 2obj costs only dozens of seconds. These programs are all analyzed with a large Java library: Open JDK 1.6.0_24. Scaler uses a default TST value of 30M (million) which exhibits uniform scalability on all machines in our experimental setup. To answer RQ1śRQ3 (Section 6.1ś6.3), we run the experiments on our default machine with a Xeon E5-2697A 2.6GHz CPU and 48GB of RAM, with the default TST (30M). To answer RQ4, different TST values are considered, and the experiments are also run on machines with smaller and larger memory sizes (Section 6.4). 6.1 Scalability and Precision of Scaler-Guided Pointer Analysis In this section, we examine the scalability and precision of Scaler￾guided pointer analysis (Scaler for short) by comparing it with conventional context-sensitive pointer analyses for Java: object￾sensitivity [25] and type-sensitivity [32], which are the mainstream variants adopted in recent analysis clients. For example, object￾sensitivity is widely adopted in recent Android static analysis frame￾works [1, 9] and type-sensitivity is used in recent reflection analy￾sis [20] and security analysis [10] tools. Table 1 shows the results for all analyses. Each program has five rows of data, respectively representing context-insensitive (CI), conventional context-sensitive, Scaler, and two introspective (IntroA and IntroB) pointer analyses. (The last two analyses will be discussed in Section 6.2.) For conventional context-sensitive pointer analyses, we consider 2obj, 2type, and 1type. Call-site-sensitivity and 1obj are not considered as the former is not effective for Java programs [15, 17, 37] and the latter is usually both less efficient and less precise than 2type [15, 32]. As it is virtually impossible to predict the scalability of a precise context-sensitive pointer analysis in advance, to get the most precise conventional analysis results we run 2obj, 2type, and 1type in the given order (from the most to the least precise one) until one of them terminates within 3 hours. So in Table 1, the second row for each program shows the results of the most precise conventional pointer analysis that is scalable. 6.1.1 Scalability of Scaler-Guided Pointer Analysis. In Table 1, the third column for each program demonstrates Scaler’s extremely good scalability. 2obj is not scalable for the first six programs, and even the fast 2type also fails to scale for jython and soot. How￾ever, Scaler scales for all of them, with its one-shot principle. In addition, for the first seven complex and large programs, Scaler runs (sometimes significantly) faster than the most precise con￾ventional pointer analysis that is scalable, even if we add Scaler’s pre-analysis time (CI). For example, according to past literature and extensive experi￾ence [15, 32, 37, 38], jython is considered the most troublesome program in terms of scalability, among the DaCapo benchmarks [3]. 134