Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE'18.November 4-9,2018,Lake Buena Vista.FL,USA Precision Time Precision Time 3400 Timeout 12000 2200 2188 12000 3300 2176 3300 10000 10000 3211 2150 3200 3170 8000 8000 3100 3071 6000 2100 2080 2080 6000 3000 2979 4000 2D50 4000 2050 2900 2000 2000 2800 2000 0 20M 30M 60M 80M 150M 20M 30M 60M 80M 150M ☐#may-fall casts-量-12GB★48GB ◆-368G8 ☐#may-fall casts量-12GB◆48GB ◆-368GB (a)eclipse (b)pmd Figure 8:SCALER-guided pointer analysis time (efficiency)and the corresponding number of may-fail casts(precision)with different TST values(20M,30M,60M,80M and 150M)on the machines under different memory sizes(12GB,48GB,and 368GB). sensitivity for it.Since java.lang.Object's constructor <init>is scalability vary as a function of TST values,for three different RAM an empty method,analyzing it with or without 2obj does not affect configurations.As the figure demonstrates,there is nothing special the precision of pointer analysis.Thus SCALER-guided pointer anal- about ScALER's default 30M TST:the system adapts appropriately ysis achieves exactly the same precision as the conventional 2obj for both larger and smaller values.Users can simply increase or analysis for luindex and lusearch(see Table 1).This again demon- decrease the TST value to achieve better precision(up to the level strates the self-tuning ability of ScALER which can automatically the analysis setup can support)or better efficiency,respectively. obtain maximal precision for simple programs. This simple design with TST being the only tuning knob is able to drive complicated pointer analyses to adapt to different programs Answer to RQ3:SCALER automatically selects appropriate STp to achieve their preferred scalability and precision. values and context-sensitivity to ensure the scalability of pointer analysis for programs of varying complexity.In addition,the cost of SCALER-Guided Pointer Analysis with Different Memory Sizes.As such good adaptivity is very low. shown in Figure 8,with the largest TST value of 150M,SCALER- guided pointer analysis is not scalable for pmd with 12GB or 48GB 6.4 SCALER-Guided Pointer Analysis with memory,but it is scalable if using 368GB memory.With the same Different TSTs and Memory Sizes TST,SCALER-guided pointer analysis running on a machine with a larger memory is more likely to be scalable.For example,with a TST As real-world analysis settings may differ widely,we conduct ex- of 150M,SCALER-guided pointer analysis is not scalable with 12GB periments by running SCALER with different TST and memory sizes, to further evaluate the adaptiveness and usability of SCALER in prac- memory for any of the 6 programs,it is scalable for 4 programs tice.We run SCALER for the top six costliest-to-analyze programs if using 48GB memory,and it is scalable for all 6 programs with 368GB memory.This result indirectly demonstrates that scalability in Table 1(jython,soot,pmd,briss,jedit,and eclipse),with (and,thus,the choice of TST)is tied to memory size. TST values(20M,30M.60M,80M,and 150M)on three machines with different memory sizes:12GB,48GB,and 368GB,representing Answer to RQ4:Better precision or better efficiency of SCALER- typical memory sizes of a personal laptop,a commodity server,and guided pointer analysis can be achieved by simply increasing or a large server,respectively. decreasing the TST value.The scalability is related to memory sizes. Conventional pointer analyses that are not scalable for these six with the same TST,SCALER-guided pointer analysis is more likely to programs in Table 1(with memory size 48GB)are also all unscal- scale under larger memory:thus a small(large)TST is recommended able on another machine with a much larger memory size,368GB. for a small(large)memory size for good scalability(precision). However,under SCALER's default TST of 30M(as used in previous experiments),SCALER-guided pointer analysis still scales for all six 7 RELATED WORK programs even on a machine with only 12GB memory.This result further demonstrates the effectiveness of SCALER in making pointer Context sensitivity,despite bringing great precision benefits,intro- analysis scalable in practice. duces many uncertainties to scalability,which may render a pointer Since the six programs under different TST and memory settings analysis useless in practice.We focus on related work that leverages exhibit similar trends,for space reasons we only show two rep- pre-analysis to achieve good efficiency and precision trade-offs for resentative programs,eclipse and pmd,in Figure 8.We illustrate context-sensitive pointer analysis. precision changes via the #may-fail casts metric,which is arguably Introspective analysis [33]attempts to achieve precision and the most common precision metric in Java pointer-analysis litera- scalability trade-offs by refining a context-sensitive analysis while ture[14,15,17,32-34,37,38]. avoiding its worst-case cost.Similar to ScALER,it first performs a pre-analysis(context-insensitive pointer analysis)to extract neces- SCALER-Guided Pointer Analysis under Different TSTs.Figure 8 sary information to guide later pointer analysis.Unlike SCALER,it encodes a lot of information:it shows how both precision and relies on a set of six manually-selected metrics (e.g.,the maximum 137Scalability-First Pointer Analysis with Self-Tuning Context-Sensitivity ESEC/FSE ’18, November 4–9, 2018, Lake Buena Vista, FL, USA 3 300 3 211 3 170 3 071 2 979 0 2 000 4 000 6 000 8 000 10 000 12 000 2 800 2 900 3 000 3 100 3 200 3 300 3 400 20M 30M 60M 80M 150M #may-fail casts 12GB 48GB 368GB Time Timeout Precision Timeout (a) eclipse 2 188 2 176 2 080 2 080 2 050 0 2 000 4 000 6 000 8 000 10 000 12 000 2 000 2 050 2 100 2 150 2 200 20M 30M 60M 80M 150M #may-fail casts 12GB 48GB 368GB Time Timeout Precision Timeout (b) pmd Figure 8: Scaler-guided pointer analysis time (efficiency) and the corresponding number of may-fail casts (precision) with different TST values (20M, 30M, 60M, 80M and 150M) on the machines under different memory sizes (12GB, 48GB, and 368GB). sensitivity for it. Since java.lang.Object’s constructor <init> is an empty method, analyzing it with or without 2obj does not affect the precision of pointer analysis. Thus Scaler-guided pointer anal￾ysis achieves exactly the same precision as the conventional 2obj analysis for luindex and lusearch (see Table 1). This again demon￾strates the self-tuning ability of Scaler which can automatically obtain maximal precision for simple programs. Answer to RQ3: Scaler automatically selects appropriate STp values and context-sensitivity to ensure the scalability of pointer analysis for programs of varying complexity. In addition, the cost of such good adaptivity is very low. 6.4 Scaler-Guided Pointer Analysis with Different TSTs and Memory Sizes As real-world analysis settings may differ widely, we conduct ex￾periments by running Scaler with different TST and memory sizes, to further evaluate the adaptiveness and usability of Scaler in prac￾tice. We run Scaler for the top six costliest-to-analyze programs in Table 1 (jython, soot, pmd, briss, jedit, and eclipse), with TST values (20M, 30M, 60M, 80M, and 150M) on three machines with different memory sizes: 12GB, 48GB, and 368GB, representing typical memory sizes of a personal laptop, a commodity server, and a large server, respectively. Conventional pointer analyses that are not scalable for these six programs in Table 1 (with memory size 48GB) are also all unscal￾able on another machine with a much larger memory size, 368GB. However, under Scaler’s default TST of 30M (as used in previous experiments), Scaler-guided pointer analysis still scales for all six programs even on a machine with only 12GB memory. This result further demonstrates the effectiveness of Scaler in making pointer analysis scalable in practice. Since the six programs under different TST and memory settings exhibit similar trends, for space reasons we only show two rep￾resentative programs, eclipse and pmd, in Figure 8. We illustrate precision changes via the #may-fail casts metric, which is arguably the most common precision metric in Java pointer-analysis litera￾ture [14, 15, 17, 32ś34, 37, 38]. Scaler-Guided Pointer Analysis under Different TSTs. Figure 8 encodes a lot of information: it shows how both precision and scalability vary as a function of TST values, for three different RAM configurations. As the figure demonstrates, there is nothing special about Scaler’s default 30M TST: the system adapts appropriately for both larger and smaller values. Users can simply increase or decrease the TST value to achieve better precision (up to the level the analysis setup can support) or better efficiency, respectively. This simple design with TST being the only tuning knob is able to drive complicated pointer analyses to adapt to different programs to achieve their preferred scalability and precision. Scaler-Guided Pointer Analysis with Different Memory Sizes. As shown in Figure 8, with the largest TST value of 150M, Scaler￾guided pointer analysis is not scalable for pmd with 12GB or 48GB memory, but it is scalable if using 368GB memory. With the same TST, Scaler-guided pointer analysis running on a machine with a larger memory is more likely to be scalable. For example, with a TST of 150M, Scaler-guided pointer analysis is not scalable with 12GB memory for any of the 6 programs, it is scalable for 4 programs if using 48GB memory, and it is scalable for all 6 programs with 368GB memory. This result indirectly demonstrates that scalability (and, thus, the choice of TST) is tied to memory size. Answer to RQ4: Better precision or better efficiency of Scaler￾guided pointer analysis can be achieved by simply increasing or decreasing the TST value. The scalability is related to memory sizes: with the same TST, Scaler-guided pointer analysis is more likely to scale under larger memory; thus a small (large) TST is recommended for a small (large) memory size for good scalability (precision). 7 RELATED WORK Context sensitivity, despite bringing great precision benefits, intro￾duces many uncertainties to scalability, which may render a pointer analysis useless in practice. We focus on related work that leverages pre-analysis to achieve good efficiency and precision trade-offs for context-sensitive pointer analysis. Introspective analysis [33] attempts to achieve precision and scalability trade-offs by refining a context-sensitive analysis while avoiding its worst-case cost. Similar to Scaler, it first performs a pre-analysis (context-insensitive pointer analysis) to extract neces￾sary information to guide later pointer analysis. Unlike Scaler, it relies on a set of six manually-selected metrics (e.g., the maximum 137