Page 34 - 《软件学报》2024年第6期
P. 34

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


                 则来处理不同的分析设置, 如上下文敏感性、反射处理等, 目前在                   Doop  中已经实现了约    50  种不同的指针分析算法.
                 然而, 目前的   Doop  框架中仅提供了全程序指针分析算法, 并不支持增量指针分析算法. 此外, 从分析算法的角度来提
                 供增量支持的方式需要对现有的指针分析算法及实现进行大规模重构, 增加了分析算法的开发和维护成本.
                    本文设计并实现了一种新的增量指针分析框架                 DDoop (Differential Doop), 旨在为  CI/CD  流程提供高效的增
                 量指针分析, 并充分兼容和复用          Doop  中提供的大量指针分析实现. 我们的核心洞察是将增量指针分析委托给支
                 持增量评估机制的       Datalog  引擎, 而无需修改现有的指针分析算法和实现. 在            Datalog  中, 增量评估是一种优化技
                 术, 用于在现有计算结果的基础上, 仅对新添加或修改的数据进行重新计算, 以减少重复计算和提高查询效率. 我
                 们观察到, 代码的变更在       Doop  中实际上可以映射到输入事实的变更, 其可作为增量                Datalog  引擎的输入, 经增量
                 评估后即可得到增量输出结果           (即增量分析结果), 而无需对分析规则进行任何修改.
                    我们的   DDoop  框架采用了基于差分数据流         (differential dataflow, DDF) 的  DDlog  引擎  [14] , 这是一种能够支持
                 高效的增量评估的       Datalog  引擎. Doop  框架目前所使用的   Datalog  引擎  Soufflé  [15] 并不支持增量评估机制. Zhao  等
                 人  [16] 尝试为  Soufflé 提供增量评估的支持, 但由于   Soufflé 设计与实现机制的限制, 他们的工作只能为            Soufflé 中的
                 部分语法结构提供增量特性, 这种弱增量能力不足以支持                   Doop  框架中的复杂指针分析规则. Ritsogianni    [17] 曾试图
                                                       2
                 在  Doop  框架中整合  DDlog  引擎以提供增量分析的能力, 然而其方法设计与实现过于粗糙, 仅能支持                      Doop  中最
                 简单的分析. 此外, 根据其实验评估, 它只是在每一轮分析的时候将                   Soufflé 引擎换成  DDlog  引擎, 实际运行的还
                 是完整评估, 并未有效的利用         DDlog  引擎的增量能力.
                    因此, 在我们的     DDoop  增量指针分析框架中, 主要需要解决以下两个挑战: 1) 如何高效地将代码变更转换为
                 输入事实的变更; 2) 如何将      Doop  中基于  Soufflé 的指针分析实现移植到支持增量评估机制的             DDlog  引擎. 为了解
                 决这些问题, 本文将      DDoop  增量指针分析框架设计为前后端分离的架构: 前端实现增量输入事实生成, 以获取对
                 应代码变更的输入事实变更; 后端通过自动化规则重写器, 将                  Doop  中现有的   Soufflé 版本规则重写转换为     DDlog
                 版本规则. 通过这种方式, 我们的框架能够透明地兼容复用                  Doop  框架中现有的指针分析规则, 而无需在算法实现
                 层面进行修改即可实现增量效果. 具体而言, DDoop             框架做到了如下两点: 1) 兼容       Doop  框架本身已经拥有的丰富
                 的、各种精度的指针分析规则; 2) 利用增量特性, 尽量减少重复计算, 以在连续的分析场景下比非增量框架的批量
                 模式更快地得到运行结果. 实验评估结果显示, DDoop              增量框架在我们的实验基准集上相比原始               Doop  框架可实
                 现平均约   5×, 最高约  36×的加速.
                    总而言之, 本文作出了以下主要贡献.
                    (1) 设计并实现了一种基于差分式          Datalog  的增量指针分析框架     DDoop, DDoop  框架主要面向代码变更频繁
                 的  CI/CD  场景设计. 值得注意的是, 尽管我们并未引入新的增量指针分析算法, 但我们成功地在                       DDoop  框架中实
                 现了对   Doop 中现有的大量指针分析算法的透明增量化支持.
                    (2) 详细阐述了    DDoop  框架的前端和后端设计, 包括如何有效地识别和处理代码变更, 以及如何将这些变更
                 映射到指针集的变化, 从而减少不必要的重复计算.
                    (3) 通过实验评估验证了       DDoop  框架的分析效率和兼容性. 实验评估结果表明             DDoop  框架对  Doop  框架中现
                 有指针分析规则实现了兼容性和可复用性的最大化, 且在处理各种大小和复杂度的代码变更时, 都能实现显著的
                 分析加速.
                    本文第   1  节介绍本工作的相关背景知识. 第           节介绍所提出的增量指针分析框架             DDoop  的整体架构设计与
                 实现. 第  3  节通过实验展示     DDoop  框架的性能和兼容性. 第      4  节讨论  DDoop  框架设计与实现中的一些局限性.
                 第     5  节回顾相关工作. 第  6  节对本工作进行总结, 并提出未来工作展望.
                 1   背景知识


                 1.1   指针分析
                    在目前的大多数主流编程语言中            (如  C、C++、Java 等), 都存在指针或引用类型, 指针或引用类型变量的值
   29   30   31   32   33   34   35   36   37   38   39