一句话：提出 Pearl 多重推导方法，通过批量传播传递关系大幅减少 CFL 可达性分析冗余，加速值流与别名分析。
CFL 可达性是程序分析的基础框架，通常通过在带标签图上推导可达性关系实现。现有算法普遍采用单次推导（SRD），每次只处理一条关系，在求解频繁出现的传递关系时产生大量冗余，影响效率。本文提出 Pearl，一种多重推导方法：在传递性感知子图上批量传播可达性关系，同时推导多条涉及传递性的边，从而消除冗余。作者在 C/C++ 的上下文敏感值流分析和字段敏感别名分析上评估 Pearl。相比标准 CFL 算法，Pearl 分别平均加速 82.73 倍和 155.26 倍；相比当前最优求解器 Pocr，也平均快 10.1 倍（最高 29.2 倍）和 2.37 倍（最高 4.22 倍），且内存占用更低。
Context-free language (CFL) reachability is a fundamental framework for formulating program analyses. CFL-reachability analysis works on top of an edge-labeled graph by deriving reachability relations and adding them as labeled edges to the graph. Existing CFL-reachability algorithms typically adopt a single-reachability relation derivation (SRD) strategy, i.e., one reachability relation is derived at a time. Unfortunately, this strategy can lead to redundancy, hindering the efficiency of the analysis. To address this problem, this paper proposes Pearl, a multi-derivation approach that reduces derivation redundancy for transitive relations that frequently arise when solving reachability relations, significantly improving the efficiency of CFL-reachability analysis. Our key insight is that multiple edges involving transitivity can be simultaneously derived via batch propagation of reachability relations on the transitivity-aware subgraphs that are induced from the original edge-labeled graph. We evaluate the performance of Pearl on two clients, i.e., context-sensitive value-flow analysis and field-sensitive alias analysis for C/C++. By eliminating a large amount of redundancy, Pearl achieves average speedups of 82.73x for value-flow analysis and 155.26x for alias analysis over the standard CFL-reachability algorithm. The comparison with Pocr, a state-of-the-art CFL-reachability solver, shows that Pearl runs 10.1x (up to 29.2x) and 2.37x (up to 4.22x) faster on average respectively for value-flow analysis and alias analysis with less consumed memory.
@inproceedings{ShiLSLLX23,
title = {Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability Analysis},
author = {Chenghang Shi and Haofeng Li and Yulei Sui and Jie Lu and Lian Li and Jingling Xue},
booktitle = {ASE},
year = {2023},
doi = {10.1109/ase56229.2023.00118}
}