一句话：提出关系链接视角与 Squid 算法，消除 CFL 可达性求解中的冗余链接操作，显著提升可扩展性。
上下文无关语言（CFL）可达性是程序分析的基础框架，但因（亚）立方时间复杂度而效率低下。本文提出“关系链接”新视角，将 CFL 可达性求解视为对表示二元关系的带标签边进行链接，揭示现有求解策略中频繁重复链接导致的推导冗余。基于增强图表示，作者设计 Squid 算法，引入自适应链接与差分链接两种技术以减少冗余操作。Squid 实现为独立工具，在 C/C++ 域敏感别名分析、上下文敏感值流分析及 Java 域敏感指向分析三类任务上，与两个先进 CFL 求解器和一个主流 Datalog 求解器对比。实验表明其大幅减少冗余链接，显著提升求解可扩展性。
Context-free language (CFL) reachability is a fundamental framework widely used to model a variety of program analysis tasks, though it often suffers from inherent inefficiency due to its (sub)cubic time complexity. In this paper, we propose a novel perspective, relation chaining, which interprets CFL-reachability solving as the process of chaining labeled edges representing binary relations. This formulation exposes substantial derivation redundancy (in terms of frequent and repetitive chaining operations) arising from inefficient chaining strategies employed by existing approaches. To address this, we introduce Squid , a new algorithm that incorporates two simple yet effective chaining techniques—adaptive chaining and differential chaining—built upon an enhanced graph representation. We have implemented Squid as a standalone tool and evaluated it against two state-of-the-art CFL-reachability solvers and a leading Datalog solver across three key program analyses: field-sensitive alias analysis and context-sensitive value-flow analysis for C/C++, and field-sensitive points-to analysis for Java. Experimental results show that Squid substantially improves the scalability of CFL-reachability solving by effectively reducing a large portion of redundant chaining operations.
@article{paperbot3800,
title = {Context-Free Language Reachability via Efficient Relation Chaining},
author = {Chenghang Shi and Haofeng Li and Jie Lu and Lian Li},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798270}
}