Taking out the Toxic Trash: Recovering Precision in Mixed Flow-Sensitive Static Analyses
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.