一句话：提出 Falcon，将路径敏感内存模型下的析取推理分解为半路径敏感摘要与按需解析，实现可扩展的上下文敏感数据依赖分析。
本文针对路径敏感与上下文敏感的数据依赖分析中，强制采用路径敏感内存模型所带来的别名路径爆炸问题，提出融合式分析框架 Falcon。其核心思想是把析取推理的计算代价一分为二：第一阶段做上下文敏感、半路径敏感的稀疏分析，将数据依赖简洁地摘要为符号化的、无存储（storeless）的值流图；第二阶段为按需驱动，在值流图上解析传递性数据依赖，并在求解所需依赖的同时顺带计算完全路径敏感的指针信息。作者将该方法应用于薄切片（thin slicing）与值流缺陷检测两个客户端，在 16 个规模从 13 KLoC 到 8 MLoC 的 C/C++ 程序上，与多种当前最先进的分析方法进行比较，结果表明该方法在精度与可扩展性上均有显著优势。
This paper presents a scalable path- and context-sensitive data dependence analysis. The key is to address the aliasing-path-explosion problem when enforcing a path-sensitive memory model. Specifically, our approach decomposes the computational efforts of disjunctive reasoning into 1) a context- and semi-path-sensitive analysis that concisely summarizes data dependence as the symbolic and storeless value-flow graphs, and 2) a demand-driven phase that resolves transitive data dependence over the graphs, piggybacking the computation of fully path-sensitive pointer information with the resolution of data dependence of interest. We have applied the approach to two clients, namely thin slicing and value-flow bug finding. Using a suite of 16 C / C + + programs ranging from 13 KLoC to 8 MLoC, we compare our techniques against a diverse group of state-of-the-art analyses, illustrating the significant precision and scalability advantages of our approach.
@article{YaoZXSWZ24,
title = {Falcon: A Fused Approach to Path-Sensitive Sparse Data Dependence Analysis},
author = {Peisen Yao and Jinguo Zhou and Xiao Xiao and Qingkai Shi and Rongxin Wu and Charles Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656400}
}