标题： 无控制流图的流敏感性：一种高效的安德森风格流敏感指针分析 显示英文标题

标题： Flow Sensitivity without Control Flow Graph: An Efficient Andersen-Style Flow-Sensitive Pointer Analysis

摘要： 流敏感指针分析通过结合控制流来准确建模指针行为，是精确程序分析的重要组成部分。 流敏感指针分析广泛用于别名分析、污点分析、程序理解、编译器优化等。 现有的基于控制流图的流敏感指针分析方法，通过利用控制流信息的复杂技术，显著提高了指针分析的精度。 然而，由于控制流图固有的复杂结构，在解决指向信息时不可避免地会遇到计算效率低的问题。 我们提出了CG-FSPTA，一种基于流敏感约束图（FSConsG）的流敏感指针分析方法，以克服基于控制流图分析的效率问题。 CG-FSPTA使用一种流敏感变体，利用集合约束图（通常用于流不敏感指针分析）的结构优势，同时保持变量定义和使用的流敏感性，从而可以融入复杂的图优化和动态求解技术。 这样，CG-FSPTA在保持流敏感分析精度的同时实现了显著的效率提升。 在基准程序上的实验评估表明，CG-FSPTA在保持精度的同时显著减少了内存使用和执行时间。 特别是，通过在FSConsG中求解，CG-FSPTA相比最先进的方法平均内存减少33.05%，并将流敏感指针分析加速了7.27倍。 这些实验结果强调了CG-FSPTA作为分析大规模软件系统的可扩展解决方案的有效性，为高效程序分析框架的未来发展奠定了坚实的基础。 显示英文摘要

摘要： Flow-sensitive pointer analysis constitutes an essential component of precise program analysis for accurately modeling pointer behaviors by incorporating control flows. Flow-sensitive pointer analysis is extensively used in alias analysis, taint analysis, program understanding, compiler optimization, etc. Existing flow-sensitive pointer analysis approaches, which are conducted based on control flow graphs, have significantly advanced the precision of pointer analysis via sophisticated techniques to leverage control flow information. However, they inevitably suffer from computational inefficiencies when resolving points-to information due to the inherent complex structures of control flow graphs. We present CG-FSPTA, a Flow-Sensitive Constraint Graph (FSConsG) based flow-sensitive pointer analysis to overcome the inefficiency of control-flow-graph-based analysis. CG-FSPTA uses a flow-sensitive variant to leverage the structural advantages of set-constraint graphs (which are commonly used in flow-insensitive pointer analysis) while keeping the flow sensitivity of variable definitions and uses, allowing the incorporation of sophisticated graph optimization and dynamic solving techniques. In this way, CG-FSPTA achieves significant efficiency improvements while keeping the precision of flow-sensitive analysis. Experimental evaluations on benchmark programs demonstrate that CG-FSPTA, significantly reduces both memory usage and execution time while maintaining precision. In particular, by solving in the FSConsG, CG-FSPTA achieves an average memory reduction of 33.05\% and accelerates flow-sensitive pointer analysis by 7.27x compared to the state-of-art method. These experimental results underscore the efficacy of CG-FSPTA as a scalable solution to analyze large-scale software systems, establishing a robust foundation for future advancements in efficient program analysis frameworks.