Two Sparsification Strategies for Accelerating Demand-Driven Pointer Analysis

This work has been published as a full paper at ICST’23 [KB23]. In the context of real-world static program analysis, precise data-flow analyses rely on pointer analysis to resolve aliasing. Demand-driven pointer analysis aims to improve the scalability, by computing information only for variables on which a demand is raised, through a points-to or alias query. Yet, research has shown that when applied to large-scale programs even demand-driven analyses can become expensive regarding memory and runtime. This paper thus investigates to what extent demand-driven pointer analysis can be accelerated further if being executed over a sparse control-flow graph (CFG), specialized to those queries. We investigate two designs: First, type-aware sparsification, in which the resulting CFG only consists of statements containing variables that are type-compatible with the query variable. Second, alias-aware sparsification, where the resulting CFG consists of the def-use chains of the query variable and all its intra-procedural aliases. We implement both designs in SparseBoomerang by extending Boomerang, a pointer analysis framework based on push-down systems. We evaluate SparseBoomerang by comparing it to Boomerang in terms of precision and performance. On the PointerBench micro-benchmark suite for alias analysis, SparseBoomerang maintains the precision of Boomerang, in both designs. We evaluate the runtime and memory performance of SparseBoomerang by using FlowDroid as a taint analysis client on real-world apps. Compared to the baseline Boomerang, on average SparseBoomerang solves alias queries 2.4x faster when using the type-aware sparsification strategy, and 2.8x faster when using the alias-aware variant with negligible memory overhead.