无需控制流图的流程敏感性分析：一种高效的安德森式流程敏感指针分析方法

《Journal of Systems and Software》：Flow sensitivity without control flow graph: An efficient Andersen-style flow-sensitive pointer analysis

　　摘要
流敏感指针分析是精确程序分析的重要组成部分，它通过整合控制流来准确建模指针行为。该技术被广泛应用于别名分析、污染分析、程序理解以及编译器优化等领域。现有的基于控制流图的流敏感指针分析方法通过运用复杂的控制流信息处理技术，显著提升了指针分析的精度。然而，由于控制流图本身结构复杂，在处理指针指向关系时往往存在计算效率低的问题。为此，我们提出了Cg-FsPta——一种基于流敏感约束图（FSConsG）的流敏感指针分析方法，旨在克服基于控制流图的分析效率缺陷。Cg-FsPta采用流敏感变体，充分利用集合约束图在结构上的优势（这类图表通常用于非流敏感指针分析），同时保留变量定义和使用的流敏感性，从而能够应用先进的图优化和动态求解技术。这样一来，Cg-FsPta在保持流敏感分析精度的同时实现了显著的效率提升。在基准程序上的实验结果表明，Cg-FsPta通过FSConsG简化图结构，有效降低了内存占用和执行时间，同时仍能维持分析精度。尤其是通过在FSConsG中求解，Cg-FsPta的平均内存使用量减少了33.05%，其流敏感指针分析速度相比现有最先进方法快7.27倍。这些实验结果充分证明了Cg-FsPta作为分析大规模软件系统的可扩展解决方案的有效性，为未来高效程序分析框架的发展奠定了坚实基础。

引言
指针分析用于确定指针在运行时可能引用的内存位置，是静态程序分析的核心组成部分。这一分析技术在软件安全（Sui等人，2014；Fink等人，2008；Yan等人，2018；Shi等人，2021；Sui等人，2012；Machiry等人，2017；Li等人，2022；Guo等人，2024）、程序验证（Lee等人，2005；Das等人，2002；Cheng等人，2024）以及编译器优化（Rountev和Chandra，2000；Hardekopf和Lin，2007b）等诸多领域都有广泛应用。提升指针分析的效率和精度（Andersen，1994；Hardekopf和Lin，2007a；Pearce等人，2007b；Sui等人，2014；Tan等人，2021；Zuo等人，2021）一直是长期的研究课题，因为其效果直接影响后续静态分析任务的准确性。指针分析的性能在很大程度上取决于分析方法以及所采用的图表示方式。非流敏感指针分析不考虑控制流和执行顺序，由于其简单性及较低的计算需求，因而具有出色的性能（Hardekopf和Lin，2007a；Pereira和Berlin，2009）。这类分析通常在约束图（ConsG）上开展，其中每个节点代表一个变量，每条边则表示两个变量之间的约束关系。这类表示方式可通过Andersen风格算法高效求解（Andersen，1994；Hardekopf和Lin，2007a），而且几十年来人们一直在对这类算法进行优化研究（Pereira和Berlin，2009；Lei和Sui，2019a；Liu等人，2022）。然而，这种计算效率是以精度为代价的，因为非流敏感分析会忽略执行顺序，将所有可能的程序状态汇总起来，从而导致过于保守的指针指向集合，常常出现错误的指针关系（Yu等人，2010；Sui等人，2014）。由于缺乏流敏感性，这类分析在需要详细建模程序执行序列的应用场景中显得力不从心。相反，流敏感指针分析通过考虑程序语句的顺序执行，能够提供更高的精度。通过追踪特定程序点的值变化，流敏感指针分析可以精确更新指针指向信息。正是这种更高的精度，使得流敏感分析在现代程序分析任务中尤为重要，尤其是在那些对正确性和详细行为建模有严格要求的情况下（Sui等人，2016；Hardekopf和Lin，2011）。通常，流敏感指针分析是基于控制流图（CFG）来进行的，相关技术包括半稀疏方法（Hardekopf和Lin，2009）、逐层分析（Yu等人，2010）以及稀疏值流图（SVFG）（Sui等人，2016）。这些方法通过选择性地传播指针指向信息或将程序划分为不同段，提升了指针分析的精度。尽管半稀疏技术（Hardekopf和Lin，2009）通过数据依赖管理和选择性更新减少了冗余计算，但它们往往存在可扩展性方面的问题。同样，SVFG也是通过整合CFG与简化后的控制流图——即由非流敏感指针分析得到的结果——来保持流敏感性的，因此它在处理节点中的语句以及沿边传播值时都需要进行操作。相邻节点中重复出现的变量会导致重复计算，进而降低效率。此外，由于现有的流敏感指针分析技术会将程序语句封装在节点中，所以现有的先进图简化技术（Hardekopf和Lin，2007a；Rountev和Chandra，2000；Lei等人，2023）以及动态求解技术（Pereira和Berlin，2009；Liu等人，2022）都无法应用。这一现象引发了一个重要的研究问题：能否将流敏感指针分析的精度与Andersen风格非流敏感分析的计算效率结合起来？为了解决这一难题，我们提出了Cg-FsPta——一种基于流敏感约束图（FSConsG）的新型流敏感指针分析方法，它有效地弥合了高效Andersen风格基于约束的分析与精确流敏感指针分析之间的差距。与现有的基于CFG的技术如SVFG（Sui等人，2016）不同，后者将可能包含多个变量的语句封装在节点中，从而无法应用为Andersen风格指针分析开发的强大优化技术，而我们的FSConsG则保持了ConsG结构的简洁性：每个节点仅代表一个变量，不包含任何控制流信息。将变量表示与控制流分离这一重要思路，使得我们的图表示方式比传统的流敏感分析方法更为简洁且计算效率更高。我们的FSConsG与现有的先进图优化技术天然兼容，包括变量替换（Rountev和Chandra，2000）和环消除（Tarjan，1972），以及高效的约束求解器，如Wave（Pereira和Berlin，2009）和Sfr（Lei和Sui，2019b）。因此，Cg-FsPta在保持流敏感分析精度特性的同时，大幅降低了计算开销，展现出作为当前程序分析挑战的可行且高效解决方案的潜力。构建FSConsG需要借助CFG的信息以及非流敏感指针分析的结果，这与现有技术VSFS中所使用的SVFG类似（Barbar等人，2021；Hardekopf和Lin，2009；Sui和Xue，2017）。其主要区别在于，我们使用的图是以ConsG的形式构建的，即每个变量都作为一个节点，每条边则代表一条指令。在FSConsG中，我们会根据执行点（CFG节点）将地址取用变量（抽象内存对象）分为不同的版本，并利用由Hardekopf和Lin（2009）提出的方法计算出的定义-使用关系，为这些地址取用变量构建一系列定义-使用链，从而保持其流敏感性。通过这种方式，我们可以为每个节点维护一个指针指向集合，并且只需处理边即可求解指针关系。由于我们的指针分析是在LLVM的中间表示形式（LLVM-IR）上进行的，而其中的顶层变量（指针）已经是字段敏感的（处于SSA形式），因此我们的FSConsG就已经足以用于流敏感指针分析。基于FSConsG，我们还提出了一种流敏感约束求解器。该求解器通过针对地址取用变量设计的特殊机制，确保其输出的指针指向集合结果与现有技术，如SFS和半稀疏方法（Hardekopf和Lin，2009）的结果一致。我们的Cg-FsPta将非流敏感指针分析和流敏感指针分析整合到了同一个抽象程序模型中，简化了流敏感指针分析的图表示方式，同时通过最小化计算开销并运用强大的图简化与动态求解技术，显著提升了流敏感指针分析的速度。我们实现了Cg-FsPta，并通过与现有的最先进方法VSFS进行比较，评估了它的可扩展性和效率。将该方法集成到LLVM-16编译器架构中，并使用SPEC CPU 2017基准测试套件进行测试后，结果显示Cg-FsPta在图中的约束数量、内存占用以及执行时间等方面均优于VSFS。这些改进得益于在不对分析精度造成影响的前提下，有效减少了FSConsG中的节点和边数量。此外，约束求解算法还优化了内存使用并提升了执行速度，使得Cg-FsPta的平均执行速度远远快于VSFS。我们的主要贡献如下：•我们通过流敏感约束图（FSConsG）将非流敏感指针分析和流敏感指针分析整合到同一个程序模型中，降低了流敏感指针分析的图复杂性，使其能够更好地与现有的图简化及约束求解技术相融合。•基于FSConsG，我们提出了一种具备特殊机制的约束求解算法，用于处理地址取用变量。通过结合现有的先进技术，该求解器显著提升了流敏感指针分析的效率。•我们将Cg-FsPta——包括FSConsG的构建方法和约束求解器——集成到了LLVM-16架构中，并通过基准程序进行了全面评估。实验结果表明，与VSFS相比，Cg-FsPta通过降低内存消耗，实现了平均33.05%的内存使用量减少，同时平均执行速度快7.27倍。这些结果充分体现了其在分析现代C/C++程序方面的有效性及可扩展性。本文的其余部分结构如下：第2节介绍了指针分析的相关背景知识，详细阐述了基于集合约束的分析、非流敏感分析以及流敏感分析的方法。第3节阐述了开发Cg-FsPta的动机，指出了现有方法的局限性。第4节介绍流敏感约束图（FSConsG），第5节介绍基于FSConsG的求解器，这两节详细描述了FSConsG的构建方式、Cg-FsPta的求解器实现，以及图折叠等图优化技术的应用。第6节通过实验对比Cg-FsPta与现有的最先进方法，在图结构、内存占用和执行时间等方面对其性能进行了评估。第7节探讨了相关研究工作，将我们的贡献置于现有研究的背景下进行分析。最后，第8节对研究结果进行总结，并指出未来工作的方向。Cg-FsPta将不依赖于流量和依赖流量的指针分析整合到同一模型中，通过降低图结构复杂性、内存占用以及执行时间来简化分析流程。这些创新显著提升了计算效率。CRediT作者贡献声明：张嘉豪：撰写——初稿、软件、方法论、形式化分析、数据整理、概念设计。程晓：撰写——审阅与编辑、撰写——初稿、验证、形式化分析。雷宇翔：撰写——审阅与编辑、验证、监督、形式化分析、概念设计。利益冲突声明：作者们声明存在以下可能被视为潜在利益冲突的财务利益/个人关系：张嘉豪表示获得了新南威尔士大学的资金支持；程晓也表示获得了新南威尔士大学的资金支持；雷宇翔同样表示获得了新南威尔士大学的资金支持。如有其他作者，则声明他们没有已知的财务利益或个人利益冲突。张嘉豪|程晓|雷宇翔，澳大利亚悉尼，新南威尔士大学计算机科学与工程学院。