Page 50 - 《软件学报》2024年第6期

2626 软件学报 2024 年第 35 卷第 6 期

相关的工程实现细节和编程语言相关. 因此, DDoop 框架拥有对如 C++, Rust, Python 等其他语言的指针分析能力
的潜在适应性. 这为 DDoop 框架的未来发展提供了广阔的可能性. 此外, 我们的增量框架技术本身是框架无关的,
可以应用于其他基于 Datalog 的分析框架. 因此我们的技术具有更广阔的潜在适用性.

5 相关工作

在本节中, 我们主要通过以下 3 个方面来介绍和讨论我们的增量指针分析框架的相关工作: (1) 指针分析框架;
(2) 增量分析算法; (3) 增量计算.

5.1 指针分析框架
鉴于指针分析的基础分析地位及其重要性, 指针分析研究人员已经开发了一系列指针分析框架, 包含已有指
针分析算法的实现以及支持新的指针分析算法的开发.
Soot [22] 中提供了两个指针分析框架 SPARK [23] 和 Paddle [24] , 其中 SPARK 是上下文不敏感的, 而 Paddle 支持多
种基于标签的上下文敏感指针分析. WALA [25] 提供了一个 Andersen 风格的流不敏感指针分析框架. 目前已在其基
大多数现有的增量分析算法都源自
础上开发了一些新的指针分析工作, 例如 IPA 和 [9] SHARP [10] . Doop [11] 是一个基于 Datalog 的声明式指针分析框架,
其支持现有大多数指针分析算法, 被认为是当前最主流的指针分析框架. Qilin [26] 是一个在 Soot 基础上开发的指针
分析框架, 其支持各种细粒度的 Java 上下文敏感指针分析. Tai-e [27] 是最新提出的一个 Java 程序分析框架, 其精心
设计了一个易学、易用、高效的指针分析框架和基于指针分析的分析插件系统. CodeQL [28] 是一个语义代码分析
引擎, CodeQL 支持对包括 Java 在内 11 种语言进行静态分析, 提供了基于 Steensgaard 算法的指针分析功能, 其底
层分析同样依赖于 Datalog 实现. 此外, 与本工作的思路类似, CodeQL 近期通过更换后端 Datalog 引擎, 实现了一
个支持增量分析的增量 CodeQL 原型框架 [29] .
目前的这些主流的指针分析框架主要面向的是全程序指针分析, 对增量指针分析的支持较弱. 据我们所知, 其
中仅有在 Soot [22] 之上基于 CFL 可达性的增量指针分析 [30] , 以及在 WALA [25] 之上的 IPA 和 [9] SHARP [10] 等少数工作
提出了增量指针分析算法, 而且它们面向的是特定指针分析算法的增量化, 并未从指针分析框架的层面上提供增
量分析的能力. 而 CodeQL 的原型增量框架虽然从框架层面支持了增量能力, 然而由于其算法层面仅提供了基础
的指针分析能力, 无法兼容和复用 Doop 中现有的大量指针分析算法实现, 特别是上下文敏感对指针分析精度至
关重要的部分. 本文提出的增量指针分析框架 DDoop 则是不仅从分析框架的层面解决了指针分析的增量化问题,
并且能够完全兼容 Doop 框架中现有已实现的各种上下文敏感性的大量指针分析算法.

5.2 增量分析算法

由于能够响应代码变更快速提供最新分析结果的优势, 近年来增量分析在静态分析领域受到了极大的关注.
针对各种静态分析技术, 研究人员分别提出了相应的增量化方案.
Reviser [31] 是一种针对基于 IDE/IFDS 的数据流分析框架的增量分析技术, 能够快速响应程序的增量变更.
Pacak 等人 [32] 和 Zwaan 等人 [33] 各自分别提出了自动推导增量类型检查器的工作, 能够在 IDE 等实时场景下对代
码变更立即产生反馈. Lu 等人 [30] 基于 CFL 可达性提出了一种增量指针分析算法. Liu 等人 [9,10] 针对上下文不敏感
指针分析和上下文敏感指针分析分别提出了相应的增量化方案. Zhao 等人 [34] 在 CHA 调用图构建算法的基础上提
供了一种增量构建算法.
DRed (deletion-rederivation) 算法 [35] . 然而, 不同的分析算法中需要进行增
量处理的部分以及增量化的细节不尽相同, 这就导致需要为每一种静态分析算法单独设计相应的增量算法, 这个
过程非常冗长且极易出错. 此外, 基于 DRed 的增量分析算法通常会存在过度删除 (over-deletion) 的问题 [36] , 即大
量数据可能先被删除, 但随后又被重新派生, 这可能会带来比较大的性能问题.
与这些传统的在分析算法层面进行增量化的工作相比, 我们的增量指针分析框架没有牺牲分析算法的透明
度, 可以兼容并复用现有的分析算法. 因此, 这种方式可以解决一大类 (可以用 Datalog 表述的) 程序分析算法的增
量化问题, 而无需为每个具体的分析问题实现特定的增量化方案. 此外, 在我们基于 DDlog 的增量分析框架中, 也