SPLASH 2021
Sun 17 - Fri 22 October 2021 Chicago, Illinois, United States
Wed 20 Oct 2021 07:55 - 08:10 at Zurich C - Analysis - mirror Chair(s): Constantin Enea
Wed 20 Oct 2021 15:55 - 16:10 at Zurich C - Analysis Chair(s): Julian Dolby

Inclusion-based set constraint solving is the most popular technique for whole-program points-to analysis whereby an analysis is typically formulated as repeatedly resolving constraints between points-to sets of program variables. The set union operation is central to this process. The number of points-to sets can grow as analyses become more precise and input programs become larger, resulting in more time spent performing unions and more space used storing these points-to sets. Most existing approaches focus on improving scalability of precise points-to analyses from an algorithmic perspective and there has been less research into improving the data structures behind the analyses.

Bit-vectors as one of the more popular data structures have been used in several mainstream analysis frameworks to represent points-to sets. To store memory objects in bit-vectors, objects need to mapped to integral identifiers. We observe that this object-to-identifier mapping is critical for a compact points-to set representation and the set union operation. If objects in the same points-to sets (co-pointees) are not given numerically close identifiers, points-to resolution can cost significantly more space and time. Without data on the unpredictable points-to relations which would be discovered by the analysis, an ideal mapping is extremely challenging.

In this paper, we present a new approach to inclusion-based analysis by compacting points-to sets through object clustering. Inspired by recent staged analysis where an auxiliary analysis produces results approximating a more precise main analysis, we formulate points-to set compaction as an optimisation problem solved by integer programming using constraints generated from the auxiliary analysis’s results in order to produce an effective mapping. We then develop a more approximate mapping, yet much more efficiently, using hierarchical clustering to compact bit-vectors. We also develop an improved representation of bit-vectors (called core bit-vectors) to fully take advantage of the newly produced mapping. Our approach requires no algorithmic change to the points-to analysis. We evaluate our object clustering on flow sensitive points-to analysis using 8 open-source programs (>3.1 million lines of LLVM instructions) and our results show that our approach can successfully improve the analysis with an up to 1.83× speed up and an up to 4.05× reduction in memory usage.

Wed 20 Oct

Displayed time zone: Central Time (US & Canada) change

07:40 - 09:00
Analysis - mirrorOOPSLA at Zurich C
Chair(s): Constantin Enea University of Paris / IRIF / CNRS
07:40
15m
Talk
Making Pointer Analysis More Precise by Unleashing the Power of Selective Context SensitivityVirtual
OOPSLA
Tian Tan Nanjing University, Yue Li Nanjing University, Xiaoxing Ma Nanjing University, Chang Xu Nanjing University, Yannis Smaragdakis University of Athens
DOI
07:55
15m
Talk
Compacting Points-To Sets through Object ClusteringVirtual
OOPSLA
Mohamad Barbar University of Technology Sydney; CSIRO’s Data61, Yulei Sui University of New South Wales, Sydney
DOI
08:10
15m
Talk
Program Analysis via Efficient Symbolic AbstractionVirtual
OOPSLA
Peisen Yao Hong Kong University of Science and Technology; Ant Group, Qingkai Shi Ant Group, Heqing Huang Hong Kong University of Science and Technology, Charles Zhang Hong Kong University of Science and Technology
DOI
08:25
15m
Talk
JavaDL: Automatically Incrementalizing Java Bug Pattern DetectionVirtual
OOPSLA
Alexandru Dura Lund University, Christoph Reichenbach Lund University, Emma Söderberg Lund University
DOI
08:40
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA

15:40 - 17:00
AnalysisOOPSLA at Zurich C -8h
Chair(s): Julian Dolby IBM Research, USA
15:40
15m
Talk
Making Pointer Analysis More Precise by Unleashing the Power of Selective Context SensitivityVirtual
OOPSLA
Tian Tan Nanjing University, Yue Li Nanjing University, Xiaoxing Ma Nanjing University, Chang Xu Nanjing University, Yannis Smaragdakis University of Athens
DOI
15:55
15m
Talk
Compacting Points-To Sets through Object ClusteringVirtual
OOPSLA
Mohamad Barbar University of Technology Sydney; CSIRO’s Data61, Yulei Sui University of New South Wales, Sydney
DOI
16:10
15m
Talk
Program Analysis via Efficient Symbolic AbstractionVirtual
OOPSLA
Peisen Yao Hong Kong University of Science and Technology; Ant Group, Qingkai Shi Ant Group, Heqing Huang Hong Kong University of Science and Technology, Charles Zhang Hong Kong University of Science and Technology
DOI
16:25
15m
Talk
JavaDL: Automatically Incrementalizing Java Bug Pattern DetectionVirtual
OOPSLA
Alexandru Dura Lund University, Christoph Reichenbach Lund University, Emma Söderberg Lund University
DOI
16:40
20m
Live Q&A
Discussion, Questions and Answers
OOPSLA