Taking out the Toxic Trash: Recovering Precision in Mixed Flow-Sensitive Static Analyses
Journal:
arXiv
Published Date:
Apr 8, 2025
Abstract
Static analysis of real-world programs combines flow- and context-sensitive
analyses of local program states with computation of flow- and
context-insensitive invariants at globals, that, e.g., abstract data shared by
multiple threads. The values of locals and globals may mutually depend on each
other, with the analysis of local program states both making contributions to
globals and querying their values. Usually, all contributions to globals are
accumulated during fixpoint iteration, with widening applied to enforce
termination. Such flow-insensitive information often becomes unnecessarily
imprecise and can include superfluous contributions -- trash -- which, in turn,
may be toxic to the precision of the overall analysis. To recover precision of
globals, we propose techniques complementing each other: Narrowing on globals
differentiates contributions by origin; reluctant widening limits the amount of
widening applied at globals; and finally, abstract garbage collection undoes
contributions to globals and propagates their withdrawal. The experimental
evaluation shows that these techniques increase the precision of mixed
flow-sensitive analyses at a reasonable cost.
