A Principled Approach to Selective Context Sensitivity for Pointer Analysis

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Documents

DOI

  • Yue Li, Nanjing University
  • ,
  • Tian Tan, Nanjing University
  • ,
  • Anders Møller
  • Yannis Smaragdakis, University of Athens

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, ZIPPERe, 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 ZIPPERe 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 three-hour time limit, on average ZIPPERe can guide 2obj to finish analyzing them in less than 11 minutes with high precision compared to context-insensitive and introspective context-sensitive analyses.

Original languageEnglish
Article number10
JournalACM Transactions on Programming Languages and Systems
Volume42
Issue2
ISSN0164-0925
DOIs
Publication statusPublished - May 2020

    Research areas

  • Java, points-to analysis, Static analysis

See relations at Aarhus University Citationformats

ID: 194695844