一句话：将扩展 Dyck-CFL 可达性转化为普通图可达性，并借索引实现上下文敏感数据流分析的近常数时间查询。
上下文敏感数据流分析常可归结为扩展 Dyck-CFL 可达性问题，其中函数调用与返回被建模为部分匹配的括号。然而标准 Dyck-CFL 可达性已有较多工作，扩展版本仍面临二次空间与近三次时间开销，严重限制可扩展性。本文首次提出一种低成本转换，将扩展 Dyck-CFL 可达性归约为传统图可达性，从而复用成熟的可达性索引方案，使上下文敏感数据流分析中的可达性查询可在几乎常数时间内完成，且仅需少量额外空间。作者在指针别名分析与信息流追踪两类分析中实现该方法。实验表明，相比原始分析，可获 10^2 倍至 10^5 倍加速，空间开销适中，实现已公开。
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. Unfortunately, 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 × to 10 5 ×) speedup at the cost of only a moderate space overhead. Our implementation is publicly available.
@article{paperbot1409,
title = {Indexing the extended Dyck-CFL reachability for context-sensitive program analysis},
author = {Qingkai Shi and Yongchao Wang and Peisen Yao and Charles Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {6},
number = {OOPSLA2},
year = {2022},
doi = {10.1145/3563339}
}