A Principled Approach to Selective Context Sensitivity for Pointer Analysis 13 ZIPPER can guide context-sensitive pointer analysis to run faster while keeping most of its precision. We propose the ZIPPER express(ZIPPER)approach,which is developed on the basis of ZIPPER but additionally considers analysis cost when selecting the methods to be analyzed with context sensitivity(Section 5).Generally,ZIPPERe can guide context-sensitive pointer analysis to run extremely fast while being reasonably precise. In contrast to other techniques that apply context sensitivity selectively,the ZIPPER and ZIPPERe approaches are based on a tangible understanding of imprecision and not on heuristics that require non-transparent machine learning or other tuning of multiple and complex analysis parameters. We provide an extensive experimental evaluation to evaluate the effectiveness of ZIPPER and ZIPPER(Section 6). On average,ZIPPER reports that only 38%of the methods are precision-critical,which preserves 98.8%of the precision(measured as average across a range of popular analysis clients)for a 2-object-sensitive pointer analysis with a context-sensitive heap(2obj),for a speedup of 3.4x and up to 9.2x.These results demonstrate that the three general patterns of value flows indeed capture the vast majority of methods that benefit from context sensitivity. On average,ZIPPERe reports that only 14%of the methods are precision-critical but not efficiency-critical,which preserves 94.7%of the precision for 2obj for a speedup of 25.5x and up to 88x.In addition,for 10 programs that 2obj is unable to analyze within 3 hours,on average,ZIPPER can guide 2obj to finish analyzing them under 11 minutes with still good precision.Moreover,for some programs,ZIPPERe-guided pointer analysis can even run faster while being more precise than context-insensitive analysis.These results establish ZIPPERe as a new sweet spot in state-of-the-art pointer analyses,for making highly practical trade-offs between efficiency and precision. The present article extends and supersedes the paper by Li et al.[2018a]presented at the ACM Conference on Object-Oriented Programming,Languages,Systems,and Applications 2018(OOPSLA 2018).In comparison,this article contains the following major extensions(and reflects an updated, more complete understanding throughout the rest of the text): We add a brief literature review of the history and current trends in context-sensitive pointer analysis for Java(Section 2). We present the new pointer analysis variant,ZIPPERe(ZIPPER express),which is extremely fast with also good precision(Section 5). We investigate whether the precision-loss patterns of ZIPPER,as its theoretical foundation, are general enough to effectively identify the precision-critical methods and thus preserve the precision for other mainstream context-sensitivity variants,including call-site sensitivity, type sensitivity and hybrid context sensitivity(Section 6.5). We conduct new experiments and extensively evaluate ZIPPERe in terms of efficiency and precision in practice(Section 6.6). 2 CONTEXT SENSITIVITY:A BRIEF REVIEW In this section,we describe how context-sensitivity has evolved for Java pointer analysis from purely improving precision to making good precision and efficiency trade-offs.In addition to giving a brief review to discuss this important and intricate research topic,we also provide some necessary background for our work.We focus on whole-program analysis,which is the main application setting of this research topic [Smaragdakis and Balatsouras 2015;Sridharan et al.2013]. 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:3 Zipper can guide context-sensitive pointer analysis to run faster while keeping most of its precision. • We propose the Zipper express (Zipper𝑒 ) approach, which is developed on the basis of Zipper but additionally considers analysis cost when selecting the methods to be analyzed with context sensitivity (Section 5). Generally, Zipper𝑒 can guide context-sensitive pointer analysis to run extremely fast while being reasonably precise. In contrast to other techniques that apply context sensitivity selectively, the Zipper and Zipper𝑒 approaches are based on a tangible understanding of imprecision and not on heuristics that require non-transparent machine learning or other tuning of multiple and complex analysis parameters. • We provide an extensive experimental evaluation to evaluate the effectiveness of Zipper and Zipper𝑒 (Section 6). – On average, Zipper reports that only 38% of the methods are precision-critical, which preserves 98.8% of the precision (measured as average across a range of popular analysis clients) for a 2-object-sensitive pointer analysis with a context-sensitive heap (2obj), for a speedup of 3.4× and up to 9.2×. These results demonstrate that the three general patterns of value flows indeed capture the vast majority of methods that benefit from context sensitivity. – On average, Zipper𝑒 reports that only 14% of the methods are precision-critical but not efficiency-critical, which preserves 94.7% of the precision for 2obj for a speedup of 25.5× and up to 88×. In addition, for 10 programs that 2obj is unable to analyze within 3 hours, on average, Zipper𝑒 can guide 2obj to finish analyzing them under 11 minutes with still good precision. Moreover, for some programs, Zipper𝑒 -guided pointer analysis can even run faster while being more precise than context-insensitive analysis. These results establish Zipper𝑒 as a new sweet spot in state-of-the-art pointer analyses, for making highly practical trade-offs between efficiency and precision. The present article extends and supersedes the paper by Li et al. [2018a] presented at the ACM Conference on Object-Oriented Programming, Languages, Systems, and Applications 2018 (OOPSLA 2018). In comparison, this article contains the following major extensions (and reflects an updated, more complete understanding throughout the rest of the text): • We add a brief literature review of the history and current trends in context-sensitive pointer analysis for Java (Section 2). • We present the new pointer analysis variant, Zipper𝑒 (Zipper express), which is extremely fast with also good precision (Section 5). • We investigate whether the precision-loss patterns of Zipper, as its theoretical foundation, are general enough to effectively identify the precision-critical methods and thus preserve the precision for other mainstream context-sensitivity variants, including call-site sensitivity, type sensitivity and hybrid context sensitivity (Section 6.5). • We conduct new experiments and extensively evaluate Zipper𝑒 in terms of efficiency and precision in practice (Section 6.6). 2 CONTEXT SENSITIVITY: A BRIEF REVIEW In this section, we describe how context-sensitivity has evolved for Java pointer analysis from purely improving precision to making good precision and efficiency trade-offs. In addition to giving a brief review to discuss this important and intricate research topic, we also provide some necessary background for our work. We focus on whole-program analysis, which is the main application setting of this research topic [Smaragdakis and Balatsouras 2015; Sridharan et al. 2013]. ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020