DDoop: 基于差分式Datalog求解的增量指针分析框架

指针分析是对软件进行编译优化、错误检测的核心基础技术之一.现有经典指针分析框架,如Doop,会将待分析程序和分析算法转化成Datalog评估问题并进行求解,如程序规模较大,单次求解分析时间开销较大.在程序频繁变更发布的情况下,相关程序分析的开销更是难以负担.近年来,增量分析作为一种在代码频繁变更场景下有效复用已有分析结果提升分析效率的技术受到了越来越多的关注.然而,目前的增量指针分析技术通常针对特定算法设计,支持的指针分析选项有限,其可用性也受到较大限制.针对上述问题,本文设计并实现了一种基于差分式Datalog求解的增量指针分析框架DDoop(Differential Doop). DDoop实现了增量输入事实生成技术与增量分析规则自动化重写技术,将多版本程序增量分析问题表达为差分Datalog评估问题,从而可以充分利用成熟的差分式Datalog求解引擎,如DDlog,来实现端到端的增量指针分析,并最大化兼容复用Doop中已有的指针分析实现,提供透明的增量化支持.我们在广泛应用的真实世界程序上对DDoop进行了实验评估,实验结果显示DDoop相较于非增量的Doop框架具有显著的性能优势,同时高度兼容Doop中已有的各种指针分析规则.

DDoop: An Incremental Pointer Analysis Framework Based on Differential Datalog Evaluation

Pointer analysis is one of the core and fundamental technologies for software compiler optimization and bug detection. Existing classic pointer analysis frameworks, such as Doop, build on the idea of specify analysis algorithms declaratively using Datalog. If the size of the program-to-be-analyzed is too large, the analysis time overhead of a single evaluation can be high. The overhead of program analysis can hardly be afforded, especially in situations where programs are frequently changed and released. In recent years, incremental analysis, as a technology that effectively reuses existing analysis results and improves analysis efficiency in the face of frequent code changes, has received increasing attention. However, current incremental pointer analysis techniques are often designed for specific algorithms, so the pointer analysis options supported are limited, and their usability is significantly restricted. To address the above issues, we designed and implemented DDoop (Differential Doop), an incremental pointer analysis framework based on differential Datalog evaluation. DDoop implements incremental input fact generation and automatic rewriting for incremental analysis rules, expressing multi-version program incremental analysis problems as differential Datalog evaluation problems. Therefore, a mature differential Datalog 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. We experimentally evaluated DDoop on widely-used real-world programs. The results showed 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.