A Dependence Clusters Detection Method Based on Higher-Order Function Summary

YANG Jia-yi; ZHANG Ying-zhou; LI Jun-feng; MA Rui; WANG Quan-sheng; XUE Yu-chuan

doi:10.12263/DZXB.20230862

您当前的位置：

首页 >

文章列表页 >

A Dependence Clusters Detection Method Based on Higher-Order Function Summary

PAPERS | 更新时间：2025-12-08

- A Dependence Clusters Detection Method Based on Higher-Order Function Summary
- ACTA ELECTRONICA SINICA Vol. 52, Issue 4, Pages: 1337-1348(2024)
- 作者机构：
  
  南京邮电大学计算机学院、软件学院、网络空间安全学院，江苏南京 210023
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62272214)
- DOI：10.12263/DZXB.20230862
  CLC： TP311
- Received：13 September 2023，
  
  Revised：2023-12-08，
  
  Published：25 April 2024
- 稿件说明：
移动端阅览
杨嘉毅,张迎周,李俊锋,等.一种基于高阶函数摘要的依赖簇检测方法[J].电子学报,2024,52(04):1337-1348.

YANG Jia-yi, ZHANG Ying-zhou, LI Jun-feng, et al.A Dependence Clusters Detection Method Based on Higher-Order Function Summary[J].Acta Electronica Sinica, 2024, 52(04): 1337-1348.
杨嘉毅,张迎周,李俊锋,等.一种基于高阶函数摘要的依赖簇检测方法[J].电子学报,2024,52(04):1337-1348. DOI：10.12263/DZXB.20230862

YANG Jia-yi, ZHANG Ying-zhou, LI Jun-feng, et al.A Dependence Clusters Detection Method Based on Higher-Order Function Summary[J].Acta Electronica Sinica, 2024, 52(04): 1337-1348. DOI：10.12263/DZXB.20230862

摘要

依赖簇是相互依赖的程序组件的最大集合，依赖簇中任意一点产生变动都会引起其他组件的连锁反应.在实际生产环境中，依赖簇检测对于软件理解、测试、维护具有非常重要的意义.传统的依赖簇检测方法基于系统依赖图（System Dependence Graph，SDG）实现过程间依赖关系的计算.但是SDG的构建过程比较复杂，时间空间的占用比较大.为提高依赖簇检测的效率并减少空间占用，本文提出了一种有效的轻量级依赖簇检测方法.该方法通过构建每个过程高阶函数形式的函数摘要，将形参和全局变量的数据依赖作为摘要参数，并用函数摘要的参数初始化过程内依赖信息.通过在调用点处对高阶函数形式的摘要进行实例化，即可将调用过程的依赖关系通过摘要参数进行传递，从而获取过程间的依赖信息.为了进一步提升检测效率，我们还提出了基于自适应计算的依赖簇检测优化策略，该策略可以减少因函数的递归调用产生的相关冗余计算.本文选取了不同规模不同领域的工程项目和基准测试集进行相关对比实验，结果表明：基于高阶函数的依赖簇检测方法相比系统依赖图的检测方法，能够提升2.689倍的分析效率并减少35.7%的空间占用；基于自适应计算的依赖簇检测优化策略在高阶函数方法的基础上能够减少56.7%的冗余计算，提升23.9%的分析效率.

Abstract

Dependence clusters are the largest sets of interdependent program components

where any change in one point of the cluster can trigger a chain reaction in other components. In practical production environments

detecting dependence clusters is of great importance for software understanding

testing

and maintenance. Traditional dependence cluster detection methods rely on the system dependence graph (SDG) to calculate dependencies

However

constructing an SDG is a complex process that incurs significant time and space costs when analyzing large programs. In order to improve the efficiency of cluster detection

this paper proposes a light-weight and efficient dependence cluster detection method based on higher-order functions

which can avoid constructing SDG in the analysis. This method constructs a function summary in the form of a higher-order function for each procedure

where the data dependencies of formal parameters and global variables are used to initialize the dependence inside the procedure. The dependence cluster information between procedures can be obtained by instantiating the function summary and passing the dependence through summary parameters at the call site

which avoids the construction of an SDG. To further improve the analysis efficiency of the higher-order function-based detection method

we propose an optimization strategy based on adaptive computing

which significantly reduces the redundant calculations caused by the mutual recursive calls between functions. In the end

we select benchmark test sets with different scales and fields and conduct relevant experiments

which demonstrate that the proposed program dependence cluster detection method based on higher-order functions can improve analysis efficiency by 268.9% and reduce space usage by 35.7% compared with the detection method based on SDG. The optimization strategy based on adaptive computing can reduce redundant calculations by 56.7% and improve analysis efficiency by 23.9% compared with the method based on higher-order functions.

关键词

Keywords

references

BINKLEY D . Dependence cluster causes [C ] // Scalable Program Analysis . Dagstuhl : Schloss Dagstuhl-Leibniz-Zentrum für Informatik , 2008 : 1 - 13 .

HARMAN M , BINKLEY D , GALLAGHER K , et al . Dependence clusters in source code [J ] . ACM Transactions on Programming Languages and Systems , 2009 , 32 ( 1 ): 1 - 33 .

ISLAM S S , KRINKE J , BINKLEY D , et al . Coherent dependence clusters [C ] // Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering . New York : ACM , 2010 : 53 - 60 .

程克 . 基于形式概念分析的依赖簇检测方法研究 [D ] . 北京 : 北京化工大学 , 2015 .

CHENG K . Research on Formal Concept Analysis Based Dependence Cluster Detection [D ] . Beijing : Beijing University of Chemical Technology , 2015 . (in Chinese)

ACAR U A , BLELLOCH G E , HARPER R . Adaptive functional programming [J ] . ACM Transactions on Programming Languages and Systems , 2006 , 28 ( 6 ): 990 - 1034 .

陈洪龙 , 李仁发 . 自适应演化软件研究进展 [J ] . 计算机应用研究 , 2010 , 27 ( 10 ): 3612 - 3616, 3621 .

CHEN H L , LI R F . Survey on self-adaptive evolution software [J ] . Application Research of Computers , 2010 , 27 ( 10 ): 3612 - 3616, 3621 . (in Chinese)

连瑞琦 , 张兆庆 , 乔如良 . 一种增量式数据流分析方法 [J ] . 计算机研究与发展 , 2002 , 39 ( 2 ): 136 - 141 .

LIAN R Q , ZHANG Z Q , QIAO R L . An incremental method of data-flow analysis [J ] . Journal of Computer Research and Development , 2002 , 39 ( 2 ): 136 - 141 . (in Chinese)

王留帅 . 基于函数摘要的C++过程间静态分析研究 [D ] . 成都 : 电子科技大学 , 2017 .

WANG L S . Summary-Based Interprocedure Analysis for C++ [D ] . Chengdu : University of Electronic Science and Technology of China , 2017 . (in Chinese)

KIM S K , VENET A J , THAKUR A V . Deterministic parallel fixpoint computation [J ] . Proceedings of the ACM on Programming Languages , 2019 , 4(POPL): 1- 33 .

BINKLEY D , HARMAN M . Locating dependence clusters and dependence pollution [C ] // 21st IEEE International Conference on Software Maintenance (ICSM'05) . Piscataway : IEEE , 2005 : 177 - 186 .

GALINDO C , KRINKE J , PÉREZ S , et al . Field-sensitive program slicing [M ] // Software Engineering and Formal Methods . Cham : Springer International Publishing , 2022 : 74 - 90 .

LERCH J , SPÄTH J , BODDEN E , et al . Access-path abstraction: scaling field-sensitive data-flow analysis with unbounded access paths (t) [C ] // 2015 30th IEEE/ACM International Conference on Automated Software Engineering . Piscataway : IEEE , 2015 : 619 - 629 .

姜淑娟 , 徐宝文 , 史亮 , 等 . 一种基于异常传播分析的依赖性分析方法 [J ] . 软件学报 , 2007 , 18 ( 4 ): 832 - 841 .

JIANG S J , XU B W , SHI L , et al . An approach to analyzing dependence based on exception propagation analysis [J ] . Journal of Software , 2007 , 18 ( 4 ): 832 - 841 . (in Chinese)

张健 , 张超 , 玄跻峰 , 等 . 程序分析研究进展 [J ] . 软件学报 , 2019 , 30 ( 1 ): 80 - 109 .

ZHANG J , ZHANG C , XUAN J F , et al . Recent progress in program analysis [J ] . Journal of Software , 2019 , 30 ( 1 ): 80 - 109 . (in Chinese)

MARLOW S , NEWTON R , PEYTON JONES S . A monad for deterministic parallelism [J ] . ACM SIGPLAN Notices , 2011 , 46 ( 12 ): 71 - 82 .

张迎周 , 徐晨晨 , 竺殊荣 . 一种参数化的改进SDG程序切片方法 [J ] . 南京邮电大学学报(自然科学版) , 2017 , 37 ( 6 ): 75 - 80, 89 .

ZHANG Y Z , XU C C , ZHU S R . Parametric method for improving SDG-based program slicing [J ] . Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition) , 2017 , 37 ( 6 ): 75 - 80, 89 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Conceptual Knowledge Discovery and Evolution in Formal Context with Object Structure Information

Generating All Pseudo-Intents with Minimal Generators of Formal Concept

The Visualizing Calculation of Formal Concept That Based on the Attribute Topologies

Extended Model of Formal Concept Analysis Oriented for Heterogeneous Data Analysis

Related Author

LI Jin-hai

LIU Wen-qi

ZHANG Wen-xiu

YAN Meng-yu

XU Lei

XU Bao-wen

YANG Bin

ZHANG Tao

Related Institution

Data Science Research Center, Kunming University of Science and Technology

Faculty of Science, Kunming University of Science and Technology

School of Mathematics and Statistics, Xi’an Jiaotong University

School of Computer Science and Technology,Southeast University

School of Information Science and Engineering, Yanshan University

⁰