改进的基于逆向流分析的C程序切片算法

吉林大学学报(信息科学版) ›› 2014, Vol. 32 ›› Issue (1): 47-55.

改进的基于逆向流分析的C程序切片算法

李冰雨^1a,2, 吕帅^1a,1b,1c, 何丽莉^1a

1. 吉林大学 a. 计算机科学与技术学院; b. 符号计算与知识工程教育部重点实验室; c. 数学学院, 长春 130012；2. 中国科学院信息工程研究所, 北京 100093

收稿日期:2013-08-16 出版日期:2014-01-24 发布日期:2014-04-03
作者简介:李冰雨(1990—), 男, 河南安阳人, 中国科学院硕士研究生, 主要从事程序分析与验证研究, (Tel)86-18511589916(E-mail)libingyu09@163.com; 通讯作者：吕帅(1981—), 男, 吉林公主岭人, 吉林大学讲师, 博士, 主要从事智能规划与自动推理研究,(Tel) 86-431-85159375(E-mail)lus@jlu.edu.cn。
基金资助:
教育部高等学校博士学科点专项科研基金资助项目(20120061120059); 中国博士后科学基金资助项目（2011M500612）; 国家自然科学基金资助项目（61070084; 61100090）

Improved C Program Slicing Algorithm Based on Reverse Flow Analysis

LI Bing-yu^1a,2, LvShuai^1a,1b,1c, HE Li-li^1a

1a. College of Computer Science and Technology; 1b. Key Laboratory of Symbolic Computation and Knowledge Engineering,Ministry of Education; 1c. College of Mathematics, Jilin University, Changchun 130012, China;2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China

Received:2013-08-16 Online:2014-01-24 Published:2014-04-03

摘要/Abstract

摘要：

为解决切片算法时空开销太大的问题, 提出一种改进的基于逆向流的静态切片算法。只需通过分析控制依赖, 获得程序整体框架, 再从切片点开始基于逆向控制流从里向外扩张式扫描, 在扫描中不断获得只与切片相关的数据依赖, 以此得到程序切片。该算法减少了计算控制流的工作量, 避免计算谓词依赖集的过程, 减少了存储资源开销, 提高了切片的效率。

关键词: 程序切片, 静态切片, 控制依赖, 数据依赖, 逆向流

Abstract:

An improved static slicing algorithm based on reverse flow has been put porward, to solve the disadvantage of traditional slicing algorithm that spends too much time and space. The improved algorithm only by analyzing the control dependence, to obtain the overall framework of the program, then scanning from inside to outside in the way of expanding based on reverse flow of control starting from the slicing point, continually gaining data dependence associated only with the slices, followed by analysis of the program slicing. This makes the algorithm not only solve the shortcomings of the traditional slicing algorithms, but also reduce the workload of the calculation control flow, eliminating the need to calculate the predicate dependency set, to further improve the efficiency of the slices, to reduce the w
aste of resources.

Key words: program slicing, static slicing, control dependence, data dependence, reverse flow

中图分类号:

TP31

李冰雨, 吕帅, 何丽莉. 改进的基于逆向流分析的C程序切片算法[J]. 吉林大学学报(信息科学版), 2014, 32(1): 47-55.

LI Bing-yu, Lv Shuai, HE Li-li. Improved C Program Slicing Algorithm Based on Reverse Flow Analysis[J]. Journal of Jilin University(Information Science Ed, 2014, 32(1): 47-55.