A Principled Approach to Selective Context Sensitivity for Pointer Analysis YUE LI,Nanjing University,China and Aarhus University,Denmark TIAN TAN",Nanjing University,China and Aarhus University,Denmark ANDERS MOLLER,Aarhus University,Denmark YANNIS SMARAGDAKIS,University of Athens,Greece Context sensitivity is an essential technique for ensuring high precision in static analyses.It has been observed that applying context sensitivity partially,only on a select subset of the methods,can improve the balance between analysis precision and speed.However,existing techniques are based on heuristics that do not provide much insight into what characterizes this method subset.In this work,we present a more principled approach for identifying precision-critical methods,based on general patterns of value flows that explain where most of the imprecision arises in context-insensitive pointer analysis.Using this theoretical foundation, we present an efficient algorithm,ZIPPER,to recognize these flow patterns in a given program and employ context sensitivity accordingly.We also present a variant,ZIPER,that additionally takes into account which methods are disproportionally costly to analyze with context sensitivity. Our experimental results on standard benchmark and real-world Java programs show that ZIPPER preserves effectively all of the precision(98.8%)of a highly-precise conventional context-sensitive pointer analysis (2-object-sensitive with a context-sensitive heap,2obj for short),with a substantial speedup(on average, 3.4x and up to 9.4x),and that ZIPPERe preserves 94.7%of the precision of 2obj,with an order-of-magnitude speedup (on average,25.5x and up to 88x).In addition,for 10 programs that cannot be analyzed by 2obj within a 3 hours time limit,on average ZIPPER can guide 2obj to finish analyzing them in less than 11 minutes with high precision compared to context-insensitive and introspective context-sensitive analyses. CCS Concepts:.Theory of computation-Program analysis. Additional Key Words and Phrases:static analysis,points-to analysis,Java ACM Reference Format: Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis.2020.A Principled Approach to Selective Context Sensitivity for Pointer Analysis.ACM Trans.Program.Lang.Syst.1,1,Article 1 (January 2020),40 pages. https:/doi.org/10.1145/3381915 1 INTRODUCTION Pointer analysis is a fundamental family of static analyses that compute abstractions of the possible values of pointer variables in a program.Such information is essential for reasoning about aliasing and inter-procedural control flow in object-oriented programs,and it is used in a wide range of software engineering tools,e.g.,for bug detection [Chandra et al.2009;Naik et al.2006,2009]. security analysis [Arzt et al.2014;Grech and Smaragdakis 2017;Livshits and Lam 2005],program "Corresponding author Authors'email addresses:yueli@nju.edu.cn,tiantan@nju.edu.cn,amoeller@cs.au.dk,smaragd@di.uoagr. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted.To copy otherwise,or republish,to post on servers or to redistribute to lists,requires prior specific permission and/or a fee.Request permissions from permissions@acm.org. 2020 Association for Computing Machinery. 0164-0925/2020/1-ART1$15.00 https:/doi.org/10.1145/3381915 ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.1 A Principled Approach to Selective Context Sensitivity for Pointer Analysis YUE LI, Nanjing University, China and Aarhus University, Denmark TIAN TAN∗ , Nanjing University, China and Aarhus University, Denmark ANDERS MØLLER, Aarhus University, Denmark YANNIS SMARAGDAKIS, University of Athens, Greece Context sensitivity is an essential technique for ensuring high precision in static analyses. It has been observed that applying context sensitivity partially, only on a select subset of the methods, can improve the balance between analysis precision and speed. However, existing techniques are based on heuristics that do not provide much insight into what characterizes this method subset. In this work, we present a more principled approach for identifying precision-critical methods, based on general patterns of value flows that explain where most of the imprecision arises in context-insensitive pointer analysis. Using this theoretical foundation, we present an efficient algorithm, Zipper, to recognize these flow patterns in a given program and employ context sensitivity accordingly. We also present a variant, Zipper𝑒 , that additionally takes into account which methods are disproportionally costly to analyze with context sensitivity. Our experimental results on standard benchmark and real-world Java programs show that Zipper preserves effectively all of the precision (98.8%) of a highly-precise conventional context-sensitive pointer analysis (2-object-sensitive with a context-sensitive heap, 2obj for short), with a substantial speedup (on average, 3.4× and up to 9.4×), and that Zipper𝑒 preserves 94.7% of the precision of 2obj, with an order-of-magnitude speedup (on average, 25.5× and up to 88×). In addition, for 10 programs that cannot be analyzed by 2obj within a 3 hours time limit, on average Zipper𝑒 can guide 2obj to finish analyzing them in less than 11 minutes with high precision compared to context-insensitive and introspective context-sensitive analyses. CCS Concepts: • Theory of computation → Program analysis. Additional Key Words and Phrases: static analysis, points-to analysis, Java ACM Reference Format: Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis. 2020. A Principled Approach to Selective Context Sensitivity for Pointer Analysis. ACM Trans. Program. Lang. Syst. 1, 1, Article 1 (January 2020), 40 pages. https://doi.org/10.1145/3381915 1 INTRODUCTION Pointer analysis is a fundamental family of static analyses that compute abstractions of the possible values of pointer variables in a program. Such information is essential for reasoning about aliasing and inter-procedural control flow in object-oriented programs, and it is used in a wide range of software engineering tools, e.g., for bug detection [Chandra et al. 2009; Naik et al. 2006, 2009], security analysis [Arzt et al. 2014; Grech and Smaragdakis 2017; Livshits and Lam 2005], program ∗Corresponding author Authors’ email addresses: yueli@nju.edu.cn, tiantan@nju.edu.cn, amoeller@cs.au.dk, smaragd@di.uoa.gr. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Association for Computing Machinery. 0164-0925/2020/1-ART1 $15.00 https://doi.org/10.1145/3381915 ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020