Mon 5 - Sat 10 December 2022 Auckland, New Zealand
Sat 10 Dec 2022 16:00 - 16:30 at AMRF Auditorium - Data Chair(s): Amal Ahmed

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.
This transformation
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.
Experimental results
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 Dec

Displayed time zone: Auckland, Wellington change

16:00 - 17:00
DataOOPSLA at AMRF Auditorium
Chair(s): Amal Ahmed Northeastern University, USA
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 Technology
The Essence of Online Data Processing
Philip Dexter SUNY Binghamton, Yu David Liu SUNY Binghamton, Kenneth Chiu SUNY Binghamton