基于依赖图等价代换的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为源程序的2条语句，若U1与U2存在一条边即U1→U2，存在一条从U1到EXIT的路径，并且该路径中不包括U2即：

U2∉｛U1，U2，…，EXIT｜U1→U2→…→EXIT｝则认为U2控制依赖于

控制依赖子图（Control Dependence Subgraph，CDS）［7］生成算法基本思想是：建立一条从函数的分支节点指向该函数的边。具体操作是采用双向链表的双亲表示法，即在每个节点中开辟一个新的域用来存储其双亲节点，则该节点就有一条到父节点的反向依赖边。

整个源程序的控制依赖图创建是通过在控制依赖子图中添加一系列节点以及若干组边实现的。首先，为程序中所有函数创建函数列表，使用原函数的节点作为控制依赖子图的入口节点。若函数中存在参数，则需要为函数中的每个参数建立f＿para＿node节点即函数参数信息结点，该节点包括了参数的类型和参数名等基本信息。为该节点生成指向函数的反向控制依赖边。其次为源程序建立函数调用关系列表，该表主要存储源程序中函数之间存在各种调用关系F1→F2构建程序控制依赖图时需要在程序中添加代表函数调用的依赖边。主要思想是首先对函数列表进行检查，如果函数调用列表中存在的调用关系并且该调用是用户自定义的函数调用，则为其建立call＿node节点即控制依赖边信息节点，并在F1和F2之间添加控制依赖边和反向控制依赖边。其具体算法如下：

整个过程是在控制依赖子图的基础上通过Step1向其中添加一系列的函数参数信息节点，并为之添加指向该函数的反向控制依赖边，之后通过Step2向控制依赖子图中添加控制依赖边信息节点和其他依赖边信息，进而生成控制依赖图。

3 控制流图和程序依赖图

3．1 控制流图的生成算法

控制流图是对一个程序或者程序内过程的抽象，是编译器内部维护的抽象的数据结构。控制流图在软件的语义分析中起着十分重要的作用，通过将程序的源代码用图的形式表示出来，可以方便地获取程序中语句的前后继关系和程序的执行路径。控制流图相关定义如下：

定义2 假设存在（n1，n2）∈E，其中，E代表控制流图中边的集合，则称n1是n2的直接前驱，n2为n1的直接后继。nall－pre＝｛b∈N｜（b，n）∈E｝，nall－pre表示节点n所有的直接前驱的集合。nall－next＝｛b∈N｜（n，b）∈E｝，nall－next表示节点n的所有后继。需要注意的是在控制流图中，一个节点最多存在2个直接后继［7］。

定义3 如果存在一个语句序列：

path＝（n1，n2，…，nk），∀i，0＜i＜k，ni∈nall－pre则认为path为一条可执行路径［7］。

CFG是G＝（N，E）的有向图，为了方便操作在控制流图中添加Entry和Exit节点，其中，Entry代表控制流图的入口节点，是CFG中每个节点的前驱，Entry本身没有前驱节点；Exit代表控制流图的出口节点，它是CFG中每个循环或者过程中结束语句节点的后继。并且为了能够方便得到控制依赖边将在Entry与Exit之间也加入一条边。

CFG节点中包含了该节点相应的控制依赖信息和数据依赖信息的存储域，因此，可以将CFG看作是一种载体，它承载着程序依赖图中存在的各种控制依赖关系和数据依赖关系。控制流图不仅可以清晰地表示程序间各种依赖关系，它在安全漏洞分析中也起着重要的作用。例如，如果在控制流图中，没有能够正确到达代表着内存空间释放的节点的路径，则会造成内存泄露等问题［7］。

综合国内外早期对依赖图的研究就会发现，传统的做法是首先对控制流图进行分析，然后构建程序的控制依赖图和数据依赖图（Data Dependence Graph，DDG）［7］，在这里采用先建立系统的控制依赖图，然后在此基础建立程序的控制流图的算法。

3．2 数据依赖图

数据依赖图是对程序中2个或者2个以上语句节点之间存在的数据定义和使用关系的图形化表示形式。本文可以对其进行如下定义：

定义4 假设语句节点V2对语句节点V1存在数据依赖，则V1与V2满足以下关系［8］：

即在某一存储空间MS内节点V1与节点V2之间存在一条执行路径，则V1数据依赖于V2。根据数据依赖依赖关系的不同将其分为以下3种类型：

（1）流依赖

（2）输出依赖

（3）反依赖

其中，V（W）表示在节点V处对数据空间进行写操作；V（R）在节点V处进行读操作。

在建立程序控制流图后，就可以根据对控制流图的数据依赖图分析构建程序的数据依赖图［9］。变量i的定义集合为DEF（i）和引用集合为REF（i），若节点P和节点Q满足：

（1）P∈DEF（i）；

（2）Q∈REF（i）；

（3）在节点P和节点Q中存在一条路径，该路径没有出现对变量i的重新定义，则称节点Q数据依赖于P。

3．3 程序依赖图

程序依赖图是由程序的控制依赖图、控制流图和数据依赖图组成，其中，控制依赖图表示程序中各语句以及各代码块之间的控制依赖关系，控制流图描述了程序间的控制流，数据依赖图负责描述程序间数据依赖关系［10］。程序依赖图中存在的主要依赖关系有：

（1）控制依赖

如果在程序中语句节点V1控制决定语句节点V2的执行，则称V2控制依赖于节点V1，记为：

程序的每一部分不是从属于任何控制谓词，而是依赖于入口节点的控制。控制依赖关系反应的是程序中的各种嵌套结构。

（2）数据依赖

V2使用了在V1中定义的变量i，存在一条V1～V2的路径，在该路径中i变量没有被重新定义，就称V2数据依赖于节点V1。其依赖关系表示为：

但是仅仅是程序依赖还不足以完成对软件的分析，因为程序依赖图是通常只能表示只有一个过程的程序，需要分析的程序通常都是由若干过程组成的，所以提出一种能够分析由多个过程相互作用构成的程序的中间表示形式——系统依赖图。

4 基于依赖图等价代换的SSDG生成

基于程序依赖图只能计算程序的过程内切片，为了适应目前程序复杂多变性的特点，引入了程序的系统依赖图，通过将程序依赖图扩展成为SDG，可以很好地解决程序间过程调用的问题。因为SDG能够表示程序间的调用关系，所以它也能够表示过程间的参数传递。根据系统依赖图的特点可以给出以下论断：如果2个程序具有相同的系统依赖图，则认为这2个程序是语义相同的。但2个语义等价的程序却不一定具有相同的系统依赖图。SDG结合了程序间的数据依赖和控制依赖，并将其转换成为了一种单一结构的依赖关系，它很好地弥补了程序依赖图，只能表示过程间依赖关系的不足，为软件语义分析过程间的程序切片奠定了基础［11］。

4．1 系统依赖图的构造及存在的问题

系统依赖图是对程序依赖图的扩充［12］，程序中存在的过程间的相互调用关系都能够在系统依赖图中得到展示。需要在程序依赖图的基础上做以下工作：

（1）为每个程序中被调用的过程，增加一个entry节点。

（2）为程序中调用语句的每个实参增加Actualin和Actual－out节点，该语句节点与其实参的关系为控制依赖。

（3）为被调用过程内的每个形参添加Formal－in节点，如果该形参在调用中发生状态转变，则为其添加Formal－out节点。新添加的节点与节点entry存在控制依赖。

（4）为entry节点与调用语句节点添加一条调用边。

（5）为存在依赖关系的实参和形参添加依赖边，添加Actual－in与Actual－out之间依赖边。

程序的系统依赖图相对于程序依赖图来说，具有更加复杂的构造过程，即使是一个简单的程序，其产生的系统依赖图规模也相当庞大，这给基于系统依赖图计算程序切片的算法带来严重影响，稍微一点疏忽就可能会造成计算的程序切片结果不精确。针对这种情况，本文提出一种优化程序的系统依赖图的算法。首先对程序进行等价变换，然后再进行构造系统依赖图。该算法的使用对降低系统依赖图的时间复杂度，具有不可忽视的作用，有效地提高了计算程序切片的效率和准确率。

4．2 依赖图等价代换算法

该算法的基本思想是采用程序依赖图代替程序的系统依赖图描述经过变换后的过程间调用关系。

只有满足了以下2个条件，程序P的程序依赖图才能够正确表示它的系统依赖图：

（1）同步性

对于特定输入，SDG发生中断时，PDG也发生中断。

（2）等值性

任何时候，PDG中和SDG中与兴趣点相关的变量的值相等vp＝vs。其中，vs∈VS，vp∈VP，VS为SDG中与兴趣点N相关的变量集合；VP为PDG中与兴趣点N相关的变量集合。

用PDG等价代换SDG主要分为2个阶段（等价转换都是在子程序的副本中进行的，不会影响源代码）：

（1）程序的变换

由于源程序代码之间存在大量的依赖性，影响了程序切片的精度。为了更好地对算法进行描述，首先进行如下定义：

1）简单变量：不依赖其他任何变量的变量。

2）复杂变量：依赖于其他复杂变量、常量或者简单变量。

对以上2种变量进行简单定义以后，介绍程序的变换规则：

1）对于包含多个的赋值语句的表达式，如m＝＋＋n，将其变为n＝n＋1；m＝n。

2）将源程序中的常量符号用具体的值进行替换。

3）使用常量或者简单变量等价代换复杂变量。

（2）用过程内的调用关系替换过程间的调用关系

建立程序P的子过程参数关系映射表RMT，建立程序P调用关系表，通过该表记录父过程调用子过程时形参与实参的对应映射关系。具体的转换规则如下：

1）改变程序的形参表示形式，在符号表示上使其与实参保持一致。将映射关系保存到RMT表中，计算切片时统一使用实参表示。

2）如果存在actual＝C，则会有formal＝C，在RMT表中添加该映射关系。计算切片时使用C替代formal。

3）如果函数的返回值return不在实参与形参的并集中，则令return为实参，保存到映射关系表RMT中。

5 实验结果与分析

根据控制依赖子图和控制依赖图的生成算法，建立程序的控制依赖图。算法的基本流程：首先建立程序的函数列表和函数调用列表，为函数中的参数建立指向函数F的反响控制依赖边，为用户自定义的函数调用添加由被调用函数到调用函数的反响依赖边。然后模拟3．1节提到控制流图生成算法建立程序的控制流图，在控制流图的基础上进行数据依赖分析建立数据依赖图。图1为一个采用传统算法构造的关于程序mathCal的系统依赖图。

图1 传统系统依赖图

虽然mathCal程序代码规模较小，但是其产生的系统依赖图结构却十分复杂。很小的疏忽就会使构建的系统依赖图结果不准确，从而影响程序切片的计算，严重影响了软件语义分析的结果。根据4．2节提到的依赖图等价代换算法对程序mathCal进行变换后生成新的程序mathCal＿mod，代码如下：

在这之后建立mathCal＿mod的系统依赖图，如图2所示。

图2 简化的系统依赖图

对比图2与图3可以看出，通过系统依赖图优化算法得出系统依赖图的节点数以及边数明显小于传统算法得出的系统依赖图中的节点个数和依赖边边数。

在此基础上，本文对多个不同程序进行了一系列的实验以作对比，其中，优化前使用的是一般的系统依赖图生成算法［13］，优化后使用的是本文提出的系统依赖图生成算法，实验过程中分别选取不同规模的软件程序进行实验，优化前与优化后程序的节点个数的实验结果如图3所示。

图3 优化前后的节点个数

程序优化前后依赖边的边数变化的实验结果如图4所示。

图4 优化前后依赖边边数

可以看出，使用系统依赖图优化算法得出的系统依赖图的节点数和边数明显少于未使用系统依赖图优化算法时的数量，并且优化的比例相当可观，这可以很大程度上降低系统依赖图的规模，并对以后的程序切片的速率也有一定的提升。依赖图规模的降低使得依赖图更加简洁，从而可以提高程序切片的准确度。

6 结束语

本文介绍程序的各种图形化表示形式，包括控制流图、数据流图、控制依赖图、数据依赖图、程序依赖图以及系统依赖图。在打破传统的系统依赖图构建流程的基础上，提出一种先建立控制依赖图，然后建立程序控制流图的算法，并给出基于依赖图等价代换的系统依赖图优化算法。实验结果表明其有效性。在接下来的工作中，会将该算法进一步用在SSDG可达性动态切片生成中［14］，进而达到避免数据流程算法中因反复迭代造成复杂度高的缺陷，从而提高软件系统的可信性和可靠性。

［1］Ottenstein K J，Lottenstein M．The Program Dependence Graph in a Software Development Environment［C］／／Proceedings of the 1st ACM SIGSOFT／SIGPLAM Software Engineering Symposium on Practical Software Development Environments．New York，USA：ACM Press，1984：177－184．

［2］杨 轶，苏璞睿，应凌云，等．基于行为依赖特征的恶意代码相似性比较方法［J］．软件学报，2011，22（10）：2438－2453．

［3］Du Lin，Xiao Guorong，Li Daming．A Novel Approach to Construct Object－oriented System Dependence Graph and Algorithm Design［J］．Journal of Software，2012，7（1）：133－170．

［4］Tamarit S J S，Tom S C．System Dependence Graphs in Sequential Erlang［C］／／Proceedings of the 15th Inter－national Conference on Fundamental Approaches to Software Engineering．Washington D．C．，USA：IEEE Computer Society，2012：486－500．

［5］石 峰．C＋＋语言的程序依赖图的构造和应用研究［D］．西安：西安电子科技大学，2004．

［6］Baah G K，Podgurski A， Harrold M J． The Probabilistic Program Dependence Graph and Its Application to Fault Diagnosis［J］．IEEE Transactions on Software Engineering，2010，36（4）：528－545．

［7］王雅文．基于缺陷模式的软件测试技术研究［D］．北京：北京邮电大学，2009．

［8］Antoniol G．XML－oriented GCC AST Analysis and Transformations［C］／／Proceedings of the 3rd IEEE International Workshop on Source Code Analysis and Manipulation．Washington D．C．，USA：IEEE Press，2005：869－901．

［9］Yuan Dong，Yang Yun，Liu Xiao，et al．A Data Dependency Based Strategy for Intermediate Data Storage in Scientific Cloud Workflow Systems［J］．Concurrency and Computation：Practice and Experience，2012，24（9）：956－976．

［10］王雪莲．程序切片技术研究及其在软件测试数据生成中的应用［D］．北京：北京化工大学，2005．

［11］Wang Tiantian，Su Xiaohong，Wang Yuying，et al．Semantic Similarity－based Grading of Student Programs［J］．Information and Software Technology，2007，49（2）：99－107．

［12］Horwitz S，Liblit B，Polishchuk M．Better Debugging via Output Tracing and Callstack－sensitive Slicing［J］．IEEE Transactions on Software Engineering，2010，36（1）：7－19．

［13］李 鑫．GCC抽象语法树的解析及控制依赖子图的建立方法研究［D］．哈尔滨：哈尔滨工业大学，2008．

［14］马 亮．面向对象程序动态切片系统的研究与实现［D］．南京：南京航空航天大学，2007．