CFL-based methods for approximating interleaved Dyck reachability
Open Access
- 15 April 2025
- journal article
- general
- Published by Springer Nature in International Journal on Software Tools for Technology Transfer
- Vol. 27 (2) , 255-266
Abstract
Interleaved Dyck Reachability is a standard, graph-based formulation of a plethora of static analyses that seek to be context- and field-sensitive, where each type of sensitivity is expressed via a CFL/Dyck language. Unfortunately, the problem is well known to be undecidable in general, and thus existing approaches resort to clever overapproximations. Recently, a mutual-refinement algorithm, that iteratively considers each of the two sensitivities in isolation until a fixpoint is reached, was shown to achieve high precision. In this work we present a more precise approximation of Interleaved Dyck Reachability, by extending the mutual-refinement algorithm in three general directions. First, we develop refined CFLs to express each type of sensitivity precisely, while simultaneously also lightly overapproximating the opposite type. Second, we modify the graph information in a way to highlight unreachable paths not previously captured by the algorithm. Third, we apply the resulting algorithm on an on-demand basis, which effectively masks out imprecision incurred by parts of the graph that are irrelevant for the query at hand. Our experiments show that the new approach offers significantly higher precision than the vanilla mutual-refinement algorithm and other common baselines; for a particularly challenging benchmark, we report, on average, $51\%$ of the reachable pairs compared to the most recent alternative.
Keywords
Funding Information
- Hong Kong University of Science and Technology
This publication has 29 references indexed in Scilit:
- Mutual Refinements of Context-Free Language Reachability2023
- Tight bounds for reachability problems on one-counter and pushdown systemsInformation Processing Letters, 2021
- Conditional Dyck-CFL Reachability Analysis for Complete and Efficient Library Summarization2017
- Demand-driven context-sensitive alias analysis for Java2011
- Subcubic algorithms for recursive state machinesACM SIGPLAN Notices, 2008
- Refinement-based context-sensitive points-to analysis for JavaACM SIGPLAN Notices, 2006
- Context-Sensitive Points-to Analysis: Is It Worth It?2006
- Demand-driven points-to analysis for Java2005
- Analysis of recursive state machinesACM Transactions on Programming Languages and Systems, 2005
- Program analysis via graph reachabilityInformation and Software Technology, 1998