| 摘要: |
| 传统程序分析方法在处理大规模软件时, 常需显式构建依赖图(如系统依赖图、程序依赖图), 因程序实体与依赖关系数量随规模呈指数级增长而面临“构图困难”与冗余计算的性能瓶颈. 为应对此挑战, 提出一种基于按需切片计算的并行化程序分析框架. 该框架融合了符号化切片与高阶函数摘要技术, 其核心思想是: (1) 通过将函数调用的影响抽象为可复用的高阶函数式摘要, 通过动态函数求值替代显式依赖图存储与遍历, 从根本上规避了构图瓶颈; (2) 设计了一种针对高阶函数摘要的按需实例化机制, 基于用户指定的切片准则(如关键变量), 动态地、惰性地实例化摘要, 仅计算与分析目标直接相关的依赖, 从而大幅削减了计算冗余. 该框架通过子分析摘要的独立性和惰性实例化特性, 实现了任务的细粒度划分, 展现出良好的并行潜力. 实验结果表明, 该框架下的按需切片计算较符号化切片工具(SymPas)在分析时间上减少了65.3%, 内存峰值下降了68.2%; 其并行化版本(6线程)时间进一步减少93.8%, 并行效率接近90%. 为验证该框架在大型程序分析中的实用性与有效性, 将该框架应用于访问越界缺陷检测, 成功识别了132个真阳性实例, 为解决大规模软件分析的性能瓶颈提供了新的形式化解决思路. |
| 关键词: 程序分析 程序切片 程序分析框架 |
| DOI：10.13328/j.cnki.jos.007602 |
| 分类号:TP311 |
| 基金项目: |
|
| Parallel Program Analysis Framework Based on On-demand Slicing Calculation |
|
LI Jun-Feng, YUAN Xu-Dong, WEI Chen-Yu, LI Jian-Hao, ZHANG Ying-Zhou
|
|
School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
|
| Abstract: |
| Traditional program analysis methods, when dealing with large-scale software, often require explicit construction of dependency graphs (such as system dependency graphs and program dependency graphs). However, as the number of program entities and dependency relationships grows exponentially with the scale of software, these methods face performance bottlenecks of “graph construction difficulty” and redundant computation. To address this challenge, this study proposes a parallel program analysis framework based on on-demand slicing computation. The framework integrates symbolic slicing and higher-order function summary techniques, and its core ideas are as follows. (1) By abstracting the impact of function calls into reusable higher-order function summaries and replacing explicit dependency graph storage and traversal with dynamic function evaluation, the graph construction bottleneck is fundamentally avoided. (2) An on-demand instantiation mechanism for higher-order function summaries is designed, which dynamically and lazily instantiates summaries based on user-specified slicing criteria (e.g., key variables), computing only dependencies directly relevant to the analysis target, thereby significantly reducing computational redundancy. Through the independence of sub-analysis summaries and the lazy instantiation feature, this framework enables fine-grained task partitioning, demonstrating good parallelization potential. Experimental results show that the on-demand slicing computation under this framework reduces analysis time by 65.3% and peak memory usage by 68.2% compared to the symbolic slicing tool SymPas. Its parallel version (6 threads) further reduces analysis time by 93.8%, with parallel efficiency approaching 90%. To verify the practicality and effectiveness of the framework in large-scale program analysis, it is applied to out-of-bounds access defect detection, successfully identifying 132 true positive instances, providing a new formal solution for addressing performance bottlenecks in large-scale software analysis. |
| Key words: program analysis program slicing program analysis framework |
