Wed 19 Jan 2022 15:05 - 15:30 at Salon I - Algorithmic Verification 1 Chair(s): Qirun Zhang

Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on \emph{bidirected graphs} where each edge $u\xrightarrow{\llparenthesis_i}v$ labeled by an open parenthesis “$\llparenthesis_i$” is accompanied with an inverse edge $v\xrightarrow{\rrparenthesis_i}u$ labeled by the corresponding close parenthesis “$\rrparenthesis_i$”, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with $n$ nodes and $m$ edges, the optimal bidirected Dyck-reachability algorithm computes \emph{all-pairs} reachability information in $O(m)$ time.

This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires $O(n^2)$ update time to achieve $O(1)$ query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees.

Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update (\emph{i.e.}, edge insertion and deletion) in $O(n\cdot\alpha(n))$ time and support any all-pairs reachability query in $O(1)$ time, where $\alpha(n)$ is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the $O(m)$-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches.

Wed 19 Jan

Displayed time zone: Eastern Time (US & Canada) change

15:05 - 16:20
Algorithmic Verification 1POPL at Salon I
Chair(s): Qirun Zhang Georgia Institute of Technology
15:05
25m
Research paper
Efficient Algorithms for Dynamic Bidirected Dyck-ReachabilityRemote
POPL
Yuanbo Li Georgia Institute of Technology, Kris Satya Georgia Institute of Technology, Qirun Zhang Georgia Institute of Technology
DOI Media Attached
15:30
25m
Research paper
The Decidability and Complexity of Interleaved Bidirected Dyck ReachabilityRemote
POPL
Adam Husted Kjelstrøm Aarhus University, Andreas Pavlogiannis Aarhus University
DOI Media Attached
15:55
25m
Research paper
Subcubic Certificates for CFL ReachabilityRemote
POPL
Dmitry Chistikov University of Warwick, Rupak Majumdar MPI-SWS, Philipp Schepper CISPA
DOI Media Attached