SPLASH 2023
Sun 22 - Fri 27 October 2023 Cascais, Portugal
Thu 26 Oct 2023 14:54 - 15:12 at Room II - program analysis 1 Chair(s): Manu Sridharan

In this paper, we introduce DebloaterX, a new approach for automatically identifying context-independent objects to debloat contexts in object-sensitive pointer analysis (kobj). Object sensitivity achieves high precision, but its context construction mechanism combines objects with their contexts indiscriminately. This leads to a combinatorial explosion of contexts in large programs, resulting in inefficiency. Previous research has proposed a context-debloating approach that inhibits a pre-selected set of context-independent objects from forming new contexts, improving the efficiency of kobj. However, this earlier context-debloating approach under-approximates the set of context-independent objects identified, limiting performance speedups.

We introduce a novel context-debloating pre-analysis approach that identifies objects as context-dependent only when they are potentially precision-critical to kobj based on three general container-usage patterns. Our research finds that objects containing no fields of "abstract" (i.e., open) types can be analyzed context-insensitively with negligible precision loss in real-world applications. We provide clear rules and efficient algorithms to recognize these patterns, selecting more context-independent objects for better debloating. We have implemented DebloaterX in the Qilin framework and will release it as an open-source tool. Our experimental results on 12 standard Java benchmarks and real-world programs show that DebloaterX selects 92.4% of objects to be context-independent on average, enabling kobj to run significantly faster (an average of 19.3x when k = 2 and 150.2x when k = 3) and scale up to 8 more programs when k = 3, with only a negligible loss of precision (less than 0.2%). Compared to state-of-the-art alternative pre-analyses in accelerating kobj, DebloaterX outperforms Zipper significantly in both precision and efficiency and outperforms Conch (the earlier context-debloating approach) in efficiency substantially while achieving nearly the same precision.

Thu 26 Oct

Displayed time zone: Lisbon change

14:00 - 15:30
program analysis 1OOPSLA at Room II
Chair(s): Manu Sridharan University of California at Riverside
14:00
18m
Talk
The Bounded Pathwidth of Control-Flow Graphs
OOPSLA
Giovanna Kobus Conrado Hong Kong University of Science and Technology, Amir Kafshdar Goharshady Hong Kong University of Science and Technology, Chun Kit Lam Hong Kong University of Science and Technology
DOI
14:18
18m
Talk
How Profilers Can Help Navigate Type Migration
OOPSLA
Ben Greenman University of Utah, Matthias Felleisen Northeastern University, Christos Dimoulas Northwestern University
DOI
14:36
18m
Talk
Synthesizing Precise Static Analyzers for Automatic Differentiation
OOPSLA
Jacob Laurel University of Illinois at Urbana-Champaign, Siyuan Brant Qian University of Illinois at Urbana-Champaign; Zhejiang University, Gagandeep Singh University of Illinois at Urbana-Champaign; VMware Research, Sasa Misailovic University of Illinois at Urbana-Champaign
DOI
14:54
18m
Talk
A Container-Usage-Pattern-Based Context Debloating Approach for Object-Sensitive Pointer Analysis
OOPSLA
DOI Pre-print
15:12
18m
Talk
Static Analysis of Memory Models for SMT Encodings
OOPSLA
Thomas Haas TU Braunschweig, René Maseli TU Braunschweig, Roland Meyer TU Braunschweig, Hernán Ponce de León Huawei
DOI