A Principled Approach to Selective Context Sensitivity for Pointer Analysis 1:5 1 object m(object o){ 2 return o: 3} 4 x1 new A() 5x2=m(x1): 6 y1 new B(); 7y2=m(y1): Fig.1.Example of precision loss in context-insensitive analysis context-sensitive pointer analysis is guaranteed to be at least as precise as(practically,more precise than)the conventional context sensitivity for the same choice of k.Similarly,Jeon et al.[2018] developed a machine-learning approach to select context elements,leading to a context-sensitive pointer analysis that is both reasonably efficient and precise. Selective Use of Context Sensitivity.The conventional approach to context sensitive analysis is to uniformly apply context sensitivity to every method in the given program.However,in recent years,researchers have become aware that for some methods,context sensitivity does not help improve the analysis precision but only introduces extra analysis cost.As a result,many selective context-sensitive pointer analyses have been proposed and contribute to a promising research direction for making practical trade-offs between precision and efficiency [Hassanshahi et al.2017;Jeon et al.2019;Jeong et al.2017;Li et al.2018b;Smaragdakis et al.2014].In these analyses,context sensitivity is applied only for the methods where it is deemed beneficial to the overall analysis precision.However,finding such precision-critical methods is challenging.The existing approaches to selective context-sensitive pointer analyses rely on heuristics [Hassanshahi et al.2017;Smaragdakis et al.2014]or machine learning [Jeon et al.2019;Jeong et al.2017].The heuristic approaches require manual tuning of multiple complicated parameters.The machine learning approaches are able to reveal some program features that may correlate with the analysis effectiveness;however,the weaknesses of machine learning approaches are also well known:they requires training and manual oversight during the tuning phase,they can behave unpredictably for new inputs,and they offer few insights on why they work. In this article,we present a more principled approach that explains when using context sensitivity for a method is beneficial for precision,or conversely,when omitting context sensitivity introduces imprecision. 3 CAUSES OF IMPRECISION IN CONTEXT-INSENSITIVE POINTER ANALYSIS To address the challenge of how to predict which methods are precision-critical in a given program, in this section,we introduce a general model to show that most of the precision loss in context- insensitive pointer analysis for Java can be expressed in terms of three patterns of value flows,or as combinations of these.Precision-loss patterns are independent of the chosen variant of context sensitivity,such as call-site sensitivity [Sharir and Pnueli 1981;Shivers 1991],object sensitivity [Mi- lanova et al.2005],and type sensitivity [Smaragdakis et al.2011].We first introduce the three precision loss patterns and then describe three corresponding concrete examples(Sections 3.1-3.3). This characterization of precision loss provides the conceptual foundation for ZIPPER and ZIPPER to identify the methods that will be analyzed with context sensitivity,as explained in Sections 4 and 5,respectively. A context-insensitive analysis does not distinguish between different calls to a method but merges the incoming abstract values(or points-to sets,in the case of pointer analysis)[Sharir and Pnueli 1981].Figure 1 shows a simple example.If method m is analyzed context-insensitively,then ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.A Principled Approach to Selective Context Sensitivity for Pointer Analysis 1:5 1 2 3 4 5 6 7 Object m(Object o){ return o; } x1 = new A(); x2 = m(x1); y1 = new B(); y2 = m(y1); Fig. 1. Example of precision loss in context-insensitive analysis. context-sensitive pointer analysis is guaranteed to be at least as precise as (practically, more precise than) the conventional context sensitivity for the same choice of 𝑘. Similarly, Jeon et al. [2018] developed a machine-learning approach to select context elements, leading to a context-sensitive pointer analysis that is both reasonably efficient and precise. Selective Use of Context Sensitivity. The conventional approach to context sensitive analysis is to uniformly apply context sensitivity to every method in the given program. However, in recent years, researchers have become aware that for some methods, context sensitivity does not help improve the analysis precision but only introduces extra analysis cost. As a result, many selective context-sensitive pointer analyses have been proposed and contribute to a promising research direction for making practical trade-offs between precision and efficiency [Hassanshahi et al. 2017; Jeon et al. 2019; Jeong et al. 2017; Li et al. 2018b; Smaragdakis et al. 2014]. In these analyses, context sensitivity is applied only for the methods where it is deemed beneficial to the overall analysis precision. However, finding such precision-critical methods is challenging. The existing approaches to selective context-sensitive pointer analyses rely on heuristics [Hassanshahi et al. 2017; Smaragdakis et al. 2014] or machine learning [Jeon et al. 2019; Jeong et al. 2017]. The heuristic approaches require manual tuning of multiple complicated parameters. The machine learning approaches are able to reveal some program features that may correlate with the analysis effectiveness; however, the weaknesses of machine learning approaches are also well known: they requires training and manual oversight during the tuning phase, they can behave unpredictably for new inputs, and they offer few insights on why they work. In this article, we present a more principled approach that explains when using context sensitivity for a method is beneficial for precision, or conversely, when omitting context sensitivity introduces imprecision. 3 CAUSES OF IMPRECISION IN CONTEXT-INSENSITIVE POINTER ANALYSIS To address the challenge of how to predict which methods are precision-critical in a given program, in this section, we introduce a general model to show that most of the precision loss in context￾insensitive pointer analysis for Java can be expressed in terms of three patterns of value flows, or as combinations of these. Precision-loss patterns are independent of the chosen variant of context sensitivity, such as call-site sensitivity [Sharir and Pnueli 1981; Shivers 1991], object sensitivity [Mi￾lanova et al. 2005], and type sensitivity [Smaragdakis et al. 2011]. We first introduce the three precision loss patterns and then describe three corresponding concrete examples (Sections 3.1–3.3). This characterization of precision loss provides the conceptual foundation for Zipper and Zipper𝑒 to identify the methods that will be analyzed with context sensitivity, as explained in Sections 4 and 5, respectively. A context-insensitive analysis does not distinguish between different calls to a method but merges the incoming abstract values (or points-to sets, in the case of pointer analysis) [Sharir and Pnueli 1981]. Figure 1 shows a simple example. If method m is analyzed context-insensitively, then ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020