Better Not Together: Staged Solving for Context-Free Language Reachability
This program is tentative and subject to change.
Context-free language reachability (CFL-reachability) is a fundamental formulation for program analysis with many applications. CFL-reachability analysis is computationally expensive, with a slightly subcubic time complexity concerning the number of nodes in the input graph.
This paper proposes staged solving: a new perspective on solving CFL-reachability. Our key observation is that the context-free grammar (CFG) of a CFL-based program analysis can be decomposed into (1) a smaller context-free grammar, $L$, for matching parentheses, such as procedure calls/returns, field stores/loads, and (2) a regular grammar, $R$, capturing control/data flows. Instead of solving these two parts monolithically (as in standard algorithms), staged solving solves $L$-reachability and $R$-reachability in two distinct stages. In practice, $L$-reachability, though still context-free, involves only a small subset of edges, while $R$-reachability can be computed efficiently with close to quadratic complexity relative to the node size of the input graph. We implement our staged CFL-reachability solver, STG, and evaluate it using two clients: context-sensitive value-flow analysis and field-sensitive alias analysis. The empirical results demonstrate that STG achieves speedups of 861.59x and 4.1x for value-flow analysis and alias analysis on average, respectively, over the standard subcubic algorithm. Moreover, we also showcase that staged solving can help to significantly improve the performance of two state-of-the-art solvers, POCR and PEARL, by 74.82x (1.78x) and 37.66x (1.7x) for value-flow (alias) analysis, respectively.
This program is tentative and subject to change.
Fri 20 SepDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
10:30 - 11:50 | |||
10:30 20mTalk | Total Recall? How Good Are Static Call Graphs Really? Technical Papers Dominik Helm TU Darmstadt | ATHENE - National Research Center for Applied Cybersecurity, Darmstadt, Sven Keidel TU Darmstadt, Germany, Anemone Kampkötter TU Dortmund, Johannes Düsing TU Dortmund University, Tobias Roth Technische Universität Darmstadt, Ben Hermann TU Dortmund, Mira Mezini TU Darmstadt DOI Pre-print | ||
10:50 20mTalk | Unimocg: Modular Call-Graph Algorithms for Consistent Handling of Language Features Technical Papers Dominik Helm TU Darmstadt | ATHENE - National Research Center for Applied Cybersecurity, Darmstadt, Tobias Roth Technische Universität Darmstadt, Sven Keidel TU Darmstadt, Germany, Michael Reif CQSE, Mira Mezini TU Darmstadt DOI | ||
11:10 20mTalk | Better Not Together: Staged Solving for Context-Free Language Reachability Technical Papers Chenghang Shi SKLP, Institute of Computing Technology, CAS, Haofeng Li Institute of Computing Technology,Chinese Academy of Sciences, Jie Lu SKLP, Institute of Computing Technology, CAS, Lian Li Institute of Computing Technology at Chinese Academy of Sciences; University of Chinese Academy of Sciences; Zhongguancun Laboratory | ||
11:30 20mTalk | Call Graph Soundness in Android Static Analysis Technical Papers Jordan Samhi CISPA Helmholtz Center for Information Security, René Just University of Washington, Tegawendé F. Bissyandé University of Luxembourg, Michael D. Ernst University of Washington, Jacques Klein University of Luxembourg |