Indexing Context-Sensitive Reachability
This work addresses scalability issues for software analysis tools, enabling more efficient context-sensitive analyses on large-scale codebases, though it is incremental as it builds on existing reachability indexing schemes.
The paper tackles the high computational complexity of context-sensitive data flow analysis by reducing it to a graph reachability problem, achieving orders of magnitude speedup with moderate space overhead in experiments on C/C++ programs.
Many context-sensitive data flow analyses can be formulated as a variant of the all-pairs Dyck-CFL reachability problem, which, in general, is of sub-cubic time complexity and quadratic space complexity. Such high complexity significantly limits the scalability of context-sensitive data flow analysis and is not affordable for analyzing large-scale software. This paper presents \textsc{Flare}, a reduction from the CFL reachability problem to the conventional graph reachability problem for context-sensitive data flow analysis. This reduction allows us to benefit from recent advances in reachability indexing schemes, which often consume almost linear space for answering reachability queries in almost constant time. We have applied our reduction to a context-sensitive alias analysis and a context-sensitive information-flow analysis for C/C++ programs. Experimental results on standard benchmarks and open-source software demonstrate that we can achieve orders of magnitude speedup at the cost of only moderate space to store the indexes. The implementation of our approach is publicly available.