基于依赖图等价代换的SSDG构建算法

徐 东，狄效国，孟宇龙，冯晓宁

（哈尔滨工程大学计算机科学与技术学院，哈尔滨150001）

1 概述

系统依赖图（System Dependence Graph，SDG）和程序切片技术作为软件语义分析的重要分析技术，被应用到软件语义分析的各个阶段。系统依赖图是在Ottenstein等人提出的程序依赖图（Program Dependence Graph，PDG）［1］的基础上，进行扩展后得到的可以表示程序内过程间依赖关系的图形化的表示结构。由于它能够清晰地表示程序之间各种数据依赖或控制依赖关系，易于软件开发测试人员对软件的理解，因此被广泛应用到软件的语义分析中。文献［2］通过对软件的系统依赖图进行分析查找相似性程序的恶意代码。传统的系统依赖图不能表示面向对象语言的封装、抽象、继承和多态等特性，因此，对原有系统依赖图进行面向对象扩充形成了面向对象系统依赖图［3］。近几年，又提出了面向方面系统依赖图和函数式程序的系统依赖图［4］。本文对程序的控制依赖图和控制流图（Control Flow Graph，CFG）［5］构建算法进行了深入研究，提出一种基于依赖图等价代换的系统依赖图优化算法，将程序的系统依赖图用程序依赖图进行替代。

2 基于控制依赖子图生成控制依赖图

根据文献［6］的介绍可知，控制依赖图（Control Dependence Graph，CDG）是一种可以确定2条语句关系的有效手段，通过控制依赖分析，可以方便地判断一条语句的执行是否会影响到另一条语句的执行，这是程序进行并发执行的基础。通过对程序内控制依赖关系分析研究可以将其定义为：

定义1 假设U1，U2为源程序的……