Making Pointer Analysis More Precise by Unleashing the Power of Selective Context Sensitivity 147:17 Smaragdakis 2013;Li et al.2018a,b,2020;Lu and Xue 2019;Minseok Jeon and Oh 2020;Smaragdakis et al.2014].It consists of three general precision metrics,i.e.,the total size of points-to sets for all variables(VarPts),the average size of points-to set per variable(AvgPts),and the number of all may-alias variable pairs(Aliases);and four independently useful client analyses that are often adopted in the literature to measure precision.The clients include a cast-resolution analysis(with the metric being the number of cast operations that may fail,denoted FCasts),a devirtualization analysis(with the metric being the number of virtual call sites that may have multiple call targets, denoted PCalls),a method reachability analysis(with the metric being the number of reachable methods,denoted RMtds),and a call-graph construction analysis(with the metric being the number of call graph edges,denoted CEdges). State of the art.The nature of Unity-Relay enables BAToN to take advantage of the precision achieved by any selective approach(as input),thereby whatever the state-of-the-art is,BAroN can achieve practically better precision(Theorems 4.3 and 4.6).In this context,we compare against two state-of-the-art selective approaches,ZIPPER [Li et al.2020]and SCALER [Li et al.2018b] (also adopted by BATON as inputs in Section 5),to evaluate how much more precision BAToN can achieve.ZIPPER and SCALER are open-source tools that try to maximize the precision while not threatening scalability,and have been demonstrated to be significantly more precise than other selective approaches [Smaragdakis et al.2014].We do not consider ZIPPER [Li et al.2018a]as it fails to scale for all our benchmarks. 6.1 RQ1.Precision and Scalability of BATON(Unity). For ZIPPER and SCALER,we use their default configurations as in Li et al.[2018b,2020],which are well-tuned and achieve good precision and efficiency trade-offs.As part of BAToN,we also include CoLLECTION for comparison.To provide a sense of how precise the pointer analyses(guided by these selective approaches)are,we consider CI as a baseline. Figure 7 shows graphically the precision improvement for a single metric:Aliases(i.e.,may-alias variable pairs).Table 1 presents the results for all analyses,in full detail.For each program,there are five rows of data,corresponding to the five analyses evaluated.Columns 3-9 list the seven precision metrics explained above,and the rightmost column shows the analysis time in seconds. Note that ZIPPERe,SCALER and BATON(Unity)require a pre-analysis to select contexts,however, these computations are very fast(from seconds to minutes)and are negligible compared to pointer analysis time,thus the pre-analysis time is elided in our evaluation.Next,we examine the detailed results in Table 1.For all numbers in the table.lower is better. Precision.From Table 1,we can see that ZIPPERe,SCALER and CoLLECTION are much more precise than CI.For BATON(Unity),as expected,it achieves better precision than all these three analyses for all precision metrics for all programs in Table 1.This result also validates Theorem 4.3.The precision improvements are significant in general,and are striking for some programs such as hsqldb and heritrix.Considering that the compared analyses are already highly precise,such precision improvements made by BATON(Unity)are impressive.BATON(Unity)performs well especially for VarPts,AvgPts and Aliases,which are the most important outputs of pointer analysis,necessary for numerous clients.The precision improvements for PCalls and RMtds are not as remarkable as other metrics.Actually,existing work has shown that the precision improvement of a pointer analysis has less impact on these two clients compared to others [Kastrinis and Smaragdakis 2013]. This can also be observed in the experimental results from recent selective context-sensitive pointer analysis work [Jeon et al.2019;Jeong et al.2017;Li et al.2020].Finally,due to high precision,BAToN (Unity)can avoid spending time on propagating many spurious data flows.Thus,sometimes,it can run even faster than individual analyses (CoLLECTION,ZIPPER or SCALER)as discussed below. Proc.ACM Program.Lang.,Vol.5,No.OOPSLA,Article 147.Publication date:October 2021.Making Pointer Analysis More Precise by Unleashing the Power of Selective Context Sensitivity 147:17 Smaragdakis 2013; Li et al. 2018a,b, 2020; Lu and Xue 2019; Minseok Jeon and Oh 2020; Smaragdakis et al. 2014]. It consists of three general precision metrics, i.e., the total size of points-to sets for all variables (VarPts), the average size of points-to set per variable (AvgPts), and the number of all may-alias variable pairs (Aliases); and four independently useful client analyses that are often adopted in the literature to measure precision. The clients include a cast-resolution analysis (with the metric being the number of cast operations that may fail, denoted FCasts), a devirtualization analysis (with the metric being the number of virtual call sites that may have multiple call targets, denoted PCalls), a method reachability analysis (with the metric being the number of reachable methods, denoted RMtds), and a call-graph construction analysis (with the metric being the number of call graph edges, denoted CEdges). State of the art. The nature of Unity-Relay enables Baton to take advantage of the precision achieved by any selective approach (as input), thereby whatever the state-of-the-art is, Baton can achieve practically better precision (Theorems 4.3 and 4.6). In this context, we compare against two state-of-the-art selective approaches, Zipper𝑒 [Li et al. 2020] and Scaler [Li et al. 2018b] (also adopted by Baton as inputs in Section 5), to evaluate how much more precision Baton can achieve. Zipper𝑒 and Scaler are open-source tools that try to maximize the precision while not threatening scalability, and have been demonstrated to be significantly more precise than other selective approaches [Smaragdakis et al. 2014]. We do not consider Zipper [Li et al. 2018a] as it fails to scale for all our benchmarks. 6.1 RQ1. Precision and Scalability of Baton (Unity). For Zipper𝑒 and Scaler, we use their default configurations as in Li et al. [2018b, 2020], which are well-tuned and achieve good precision and efficiency trade-offs. As part of Baton, we also include Collection for comparison. To provide a sense of how precise the pointer analyses (guided by these selective approaches) are, we consider CI as a baseline. Figure 7 shows graphically the precision improvement for a single metric: Aliases (i.e., may-alias variable pairs). Table 1 presents the results for all analyses, in full detail. For each program, there are five rows of data, corresponding to the five analyses evaluated. Columns 3ś9 list the seven precision metrics explained above, and the rightmost column shows the analysis time in seconds. Note that Zipper𝑒 , Scaler and Baton (Unity) require a pre-analysis to select contexts, however, these computations are very fast (from seconds to minutes) and are negligible compared to pointer analysis time, thus the pre-analysis time is elided in our evaluation. Next, we examine the detailed results in Table 1. For all numbers in the table, lower is better. Precision. From Table 1, we can see that Zipper𝑒 , Scaler and Collection are much more precise than CI. For Baton (Unity), as expected, it achieves better precision than all these three analyses for all precision metrics for all programs in Table 1. This result also validates Theorem 4.3. The precision improvements are significant in general, and are striking for some programs such as hsqldb and heritrix. Considering that the compared analyses are already highly precise, such precision improvements made by Baton (Unity) are impressive. Baton (Unity) performs well especially for VarPts, AvgPts and Aliases, which are the most important outputs of pointer analysis, necessary for numerous clients. The precision improvements for PCalls and RMtds are not as remarkable as other metrics. Actually, existing work has shown that the precision improvement of a pointer analysis has less impact on these two clients compared to others [Kastrinis and Smaragdakis 2013]. This can also be observed in the experimental results from recent selective context-sensitive pointer analysis work [Jeon et al. 2019; Jeong et al. 2017; Li et al. 2020]. Finally, due to high precision, Baton (Unity) can avoid spending time on propagating many spurious data flows. Thus, sometimes, it can run even faster than individual analyses (Collection, Zipper𝑒 or Scaler) as discussed below. Proc. ACM Program. Lang., Vol. 5, No. OOPSLA, Article 147. Publication date: October 2021