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

沈天琪 等: DDoop: 基于差分式 Datalog 求解的增量指针分析框架 2609

specific algorithms, the supported pointer analysis options are limited and their usability is significantly restricted. To this end, this study
designs and implements Differential Doop (DDoop), an incremental pointer analysis framework based on Differential Datalog evaluation.
DDoop implements incremental input fact generation and automatic rewriting for incremental analysis rules, expressing incremental
analysis problems of multi-version programs as Differential Datalog evaluation problems. Finally, a mature Differential Datalog solution
engine like DDlog can be fully utilized to achieve end-to-end incremental pointer analysis, maximizing compatibility and reuse of existing
pointer analysis implementations in Doop and providing transparent support for incrementalization. Additionally, experimental evaluation of
DDoop is conducted on widely adopted real-world programs. The results show that compared to the non-incremental Doop framework,
DDoop has a significant performance advantage while highly compatible with a variety of pointer analysis rules existing in Doop.
Key words: pointer analysis; incremental analysis; Datalog engine; incremental computation; Differential Datalog

随着信息技术的发展, 我们已经处于一个软件定义一切的时代. 大到航空、电力、铁路系统, 小到智能家居、
移动支付, 软件在生活中已经几乎是无处不在. 而随着软件的普及, 软件故障可能会严重影响人们的财产或生命安
全, 甚至带来灾难性的后果, 因此人们对软件质量的要求越来越高, 而对软件质量的保障就显得愈发重要. 静态程
序分析是一类重要的软件质量保障技术, 其能够对程序代码进行自动化扫描, 而无需实际运行程序.
指针分析是公认最基础的静态程序分析技术之一, 其用于在编译期静态计算程序中的指针变量在运行时可能
等人提出的
指向的内存位置 (或对象). 指针分析的结果通常可表示为待分析程序中每个指针的指向集 (points-to set). 这些信
息对于推理面向对象程序中的别名关系和过程间控制流至关重要, 被广泛地应用于错误检测 [1] 、安全分析 [2] 、程
序验证 [3] 、编译优化 [4] 等一系列技术中. 这些技术可以视为指针分析的客户端分析, 也即它们需要将指针分析产
生的结果作为输入, 因而指针分析的效率和精度直接影响了后续的客户端分析. 也正因如此, 虽然已经有超过 40
年的研究历史, 指针分析至今仍是静态程序分析学术研究中的重点领域 [5] .
然而, 指针分析目前的实用性仍有所不足. 一方面, 尽管研究人员已经在指针分析的算法和实现上投入了大量
人力, 但是即使是目前最先进的全量指针分析算法或框架, 其可扩展性仍然有所欠缺 [6] : 将高精度的指针分析应用
到数百万行的大型程序上可能需要花费超过数小时 [7] . 对于大多数生产应用来说, 这样的时间消耗通常是不可接
受的. 此问题严重削弱了高精度指针分析在现实世界大规模程序中的应用能力.
另一方面, 在如今提倡的 DevOps 实践 [8] 中, 代码的变更和发布与以往相比更加频繁. CI/CD 是 DevOps 实践
中的重要流程, 静态代码扫描是 CI/CD 中的一个关键环节, 指针分析又是静态代码扫描的基础. 频繁的变更意味
着更频繁地对代码进行扫描, 这对指针分析的可扩展性提出了更高要求. 另外, 频繁的变更也意味着连续两个版本
的代码差异往往很小: 通常仅限于程序的某个模块. 换言之, 对于整个程序而言, 在一次变更后, 程序的变化主要是
局部的, 相应地, 指针分析结果的变化通常也仅占很小比例.
在处理代码变更频繁且单次变更变化相对局部的场景时, 传统的全程序程序分析方法效率较低: 如果我们每
次都对整个程序进行完整的全程序指针分析, 会发现在绝大多数情况下, 可推断的指针指向关系实际上在新旧两
次分析中是完全不变的, 尤其是对于程序中未发生代码变更或不受代码变更影响的部分 [9] . 这意味着我们在这些
部分进行了完全重复的冗余计算, 这无疑是对计算资源的巨大浪费, 同时也会导致开发者等待 CI/CD 流程的时间
过长, 严重影响开发者的工作效率.
有鉴于此, 已经有研究人员提出了增量指针分析技术 [9,10] . 增量指针分析是一种能够有效利用先前分析结果的
方法, 它通过保留分析中的中间结果, 仅针对两次输入程序中不同的部分计算指针指向集的变化, 从而达到减少重
复计算, 节省运行时间的效果. 近年来 Liu IPA 和 SHARP [10] 分别是上下文不敏感指针分析和上下文
[9]
敏感指针分析的最新增量化工作. 它们通过在 Andersen 风格的指针分析算法中识别指向集传播的特殊性质, 从而
减少增量分析过程中的冗余计算. 然而, 这两个工作对增量指针分析的支持仅限于少数几种指针分析, 并且都是基
于命令式语言 (Java) 开发的, 这在一定程度上限制了它们的可选择性和易用性, 特别是在需要进行面向特定场景
定制的开发时.
另一方面, Doop [11] 是一个基于 Datalog 的声明式指针分析框架, 其被认为是在过去 10 年内最主流的指针分析框
架, 被用于实现和比较新提出的指针分析算法 [12,13] . Doop 会先将待分析程序转换为输入事实, 然后将这些输入事实和
相应的分析规则传递给 Datalog 引擎进行计算, 最后将 Datalog 引擎的输出作为分析结果. Doop 提供了一组优雅的规