Two Sparsification Strategies for Accelerating Demand-Driven Pointer Analysis

To resolve aliasing, precise program analyses rely on pointer analyses. Demand-driven pointer analysis seeks to be efficient 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 in terms of 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, typeaware 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.