Indexing the Extended Dyck-CFL Reachability for Context-Sensitive Program Analysis
Many context-sensitive dataflow analyses can be formulated as
an extended Dyck-CFL reachability problem,
where function calls and returns are modeled as partially matched parentheses.
despite many works on the standard Dyck-CFL reachability problem,
solving the extended version is still of quadratic space complexity and nearly cubic time complexity,
significantly limiting the scalability of program analyses.
This paper, for the first time to the best of our knowledge, presents a cheap approach to transforming the extended Dyck-CFL reachability problem to conventional graph reachability, a much easier and well-studied problem.
allows us to benefit from recent advances in reachability indexing schemes, making it possible
to answer any reachability query in a context-sensitive dataflow analysis within almost constant time plus only a few extra spaces.
We have implemented our approach in two common context-sensitive dataflow analyses,
one determines pointer alias relations and the other tracks information flows.
demonstrate that, compared to their original analyses, we can achieve orders of
magnitude ($10^2\times$ to $10^5\times$) speedup at the cost of only a moderate space overhead.
Our implementation is publicly available.
Sat 10 DecDisplayed time zone: Auckland, Wellington change
16:00 - 17:00
|Indexing the Extended Dyck-CFL Reachability for Context-Sensitive Program AnalysisVirtual|
Qingkai Shi Ant Group, Yongchao WANG Hong Kong University of Science and Technology, Peisen Yao Hong Kong University of Science and Technology, Charles Zhang Hong Kong University of Science and TechnologyDOI
|The Essence of Online Data Processing|