Flow sensitivity without control flow graph: An efficient Andersen-style flow-sensitive pointer analysis☆

Jiahao Zhang

doi:10.1016/j.jss.2026.113027

Flow sensitivity without control flow graph: An efficient Andersen-style flow-sensitive pointer analysis☆

2026-07-01

0

PRE

AI

DOI：10.1016/j.jss.2026.113027

原文链接

原文求助

摘要

En 中文

基于流敏感约束图的指针分析构成精确程序分析的关键组成部分，通过整合控制流以准确建模指针行为。流敏感指针分析广泛应用于别名分析、污点分析、程序理解、编译器优化等领域。现有基于控制流图的流敏感指针分析方法虽通过复杂技术利用控制流信息显著提升了指针分析的精度，但受控流图固有复杂结构影响，在解析指向信息时不可避免地存在计算低效问题。本文提出Cc-FSPTA，一种基于流敏感约束图（FSConsG）的流敏感指针分析方法，旨在克服基于控流图分析的效率瓶颈。Cc-FSPTA采用流敏感变体，既利用了集合约束图（常用于流不敏感指针分析）的结构优势，又保留了变量定义与使用的流敏感性，从而能够融入高级图优化和动态求解技术。通过这种方式，Cc-FSPTA在保持流敏感分析精度的同时实现了显著效率提升。在基准程序上的实验评估表明，Cc-FSPTA通过FSConsG简化图结构，在维持精度的前提下显著降低了内存使用和执行时间。特别是通过在FSConsG中求解，Cc-FSPTA相较于当前最先进的流敏感指针分析方法，平均内存减少33.05%，加速比达7.27倍。这些实验结果充分验证了Cc-FSPTA作为可扩展解决方案分析大规模软件系统的有效性，为未来高效程序分析框架的进一步发展奠定了坚实基础。

Keyword:

Program analysis

Static analysis

Pointer analysis

Flow-sensitivity

Constraint graph

Performance

Flow sensitivity without control flow graph: An efficient Andersen-style flow-sensitive pointer analysis☆

摘要

期刊

机构

引用论文