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

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


                                            表 3    剪枝选项对指针分析精度的影响         (续)

                                                Precision metrics (unpruned)     Precision metrics (pruned)
                    Project     Analysis
                                              #vpt      #fpt     #call-edge  #vpt      #fpt     #call-edge
                                  CI        4 093 997  316 226    84 567    4 093 997  316 226   84 567
                                  lobj      2 339 198  115 218    77 897    2 339 198  115 218   77 897
                                 2objH       713 208   55 539     68 782    713 208    55 539    68 782
                   CheckStyle   1callsite   2 721 068  170 652    79 733    2 721 068  170 652   79 733
                                 1type      2 531 744  135 910    78 952    2 531 744  135 910   78 952
                                 2typeH      717 783   55 624     68 887    717 783    55 624    68 887
                              selective2objH  1 066 552  75 882   71 261    1 066 552  75 882    71 261

                    实验评估结果表明, 虽然在增量输入事实生成阶段引入剪枝策略可能会最终的指针分析结果带来轻微的精度
                 损失, 但影响极小, 我们设计的剪枝策略在现有的增量指针分析场景中仍可以保持相当高的精度.

                 4   讨 论
                                             Java 指针分析框架

                 4.1   内存占用
                    静态程序分析没有银弹, 一种好的静态分析技术必然要在多个相互制衡的方面之间做出权衡取舍. 增量分析
                 虽然在分析效率上具有显著优势, 但这意味着其必然需要在其他方面付出一些代价——对于非增量的静态分析技
                 术而言, 在分析过程中, 它们往往可以通过删除在后续分析中不再需要的中间结果来节省内存使用; 而增量分析在
                 分析的全流程中必须维护所有与最终结果相关的中间结果, 以用于下一轮的增量分析, 这会导致增量分析的内存
                 使用量大幅增加. 目前, 我们的        DDoop  增量框架也存在内存占用相对较高的问题. 虽然实验已经证明其在流行的
                 Java 项目  (如  Jedis) 上能支持  Doop  中的许多指针分析精度, 但与原始的       Doop  相比, DDoop  的内存使用量仍然是
                 其数倍. 在这种情况下, 尽管我们在分析耗时上将可扩展性向前推进了一步, 但当前的内存问题成为了阻止我们
                 的  DDoop  框架进一步分析更大规模       (数百万行) 程序的主要障碍.

                 4.2   精度影响
                    在我们的框架前端中, 为了提高增量输入事实生成的效率, 引入了剪枝优化技术. 然而, 在提升输入事实生成
                 速度的同时, 剪枝优化技术也给指针分析的精度带来了挑战. 尽管我们的框架在第                          1  轮全量生成中处理所有可能
                 引用的类库, 确保了初始的精度, 但具体到后续的增量事实生成前端中的剪枝操作, 精度的问题开始浮现. 具体而
                 言, 我们的剪枝操作会将基于类依赖关系加载类的过程“截断”到类依赖库类中的第                          1  层, 这样, 如果程序的改变并
                 未导致引用类库的变化, 或者只是停止引用某些类库, 那么这种剪枝操作不会对精度产生负面影响. 这种情况下,
                 剪枝可以看作是一种优化策略, 既提高了分析效率, 又保持了精度. 然而, 当程序的变更引发新的依赖库类引用时,
                 剪枝操作可能会对精度产生负面影响. 因为这些新引用的依赖库类在静态分析层面对指针流数据流的完整建模可
                 能需要额外载入更多的依赖库类, 而剪枝操作已经将其截断, 于是我们的静态分析算法就无法通过获取经过库函
                 数相关的数据流建模, 从而影响精度. 在实验评估中, 我们也确实观察到了剪枝操作对精度的影响, 但总体上精度
                 损失非常细微, 处于可控范围之内. 此外, 在静态代码扫描的设置下, 更注重于尽早发现问题, 并快速地提供结果,
                 可以接受一定程度的误报或漏报, 对分析精度的要求并不如程序验证那么苛刻.

                 4.3   潜在适用性
                    我们的   DDoop  增量框架是针对                     Doop  设计的, 因此, 目前的   DDoop  增量框架实现无法针

                 对其他更加广泛的编程语言编写的程序运行增量分析. 但是, DDoop                  框架在理论上具有对于这些使用非             Java 语言
                 编写的程序的潜在分析能力. 具体而言, DDoop (Doop) 框架的指针分析在原理上就是将                       Andersen  指针分析在
                 PAG  上计算不动点的问题转换为了在           Datalog  程序中不断迭代生成新的      facts 以达到不动点的问题. 显然, 从方法
                 的角度上来说, Andersen   算法部分是平台无关的, 只是在实现框架的过程中, 不同的语言对应的具体的和语言特性
   44   45   46   47   48   49   50   51   52   53   54