面向程序理解的系统依赖图构建算法

王克朝，王甜甜，苏小红，马培军，童志祥

(1.哈尔滨工业大学 计算机科学与技术学院，150001 哈尔滨;2.哈尔滨学院 软件学院，150086 哈尔滨)

程序理解［1］是通过对程序的分析、抽象及推 理获取知识的一个演绎过程，需要解决数据收集、知识组织及信息浏览3个方面的问题.解决这些问题的一个关键是程序的中间表示.

K.J.Ottenstein 等［2］提出了程序依赖图的概念.S.Horwitz等［3］将程序依赖图扩展为系统依赖图，捕获过程间的调用关系.系统依赖图是程序基于图形的中间表示，能清晰地表示出程序中的各种控制依赖和数据依赖关系及程序的语法与语义信息，因此在编译器优化［4-5］、程序切片［6］、软件审查［7］、软件测试［8］、编程题自动评分［9-11］、克隆代码检测［12-13］以及软件缺陷检测［14-15］等领域得到了广泛的应用.系统依赖图的构建方法也得到了广泛的研究，近年来提出了面向对象［16］、面向方面［17］以及函数式程序［18］的系统依赖图的创建方法.

然而，程序理解过程中，常常需要按需的程序分析，如果程序规模较大，则很难一次理解、分析所有的系统依赖图节点及边;此外，由于编程语言的语法多样性，同一个编程任务可由多种语法结构实现，这种现象称为代码多样化，增加了程序理解的难度.因此，本文采取控制依赖和数据依赖分别求解，在控制依赖子图的基础上，按需进行数据流分析，降低了算法复杂度，使之适合于分析大规模代码;将选择语句和循环语句统一表示，将表达式表示为抽象语法树，为实现程序标准化时进行语义等价的程序转换和程序匹配提供了方便.

1 系统依赖图的概念

定义1 程序依赖图(Program Dependence Graph，PDG)单过程程序P的PDGG=(V，E)是一个有向图.其中:V为节点集合，表示程序中的语句和谓词;E⊂V×V为边集合，表示节点间的数据依赖或控制依赖关系.

定义2 系统依赖图(System Dependence Graph，SDG)多过程程序 P的SDGG={GPDGs，EInterpro}是一个有向图.其中:GPDGs为PDG集合，每个过程(函数)表示为一个PDG;EInterpro为过程间调用边与依赖边的集合，过程间的调用边将函数调用位置与被调函数的entry相连，过程间的数据依赖边表示实参和形参间的数据流.

系统依赖图包含控制依赖子图和数据依赖子图.

定义3 控制依赖子图(Control Dependence Sub-graph，CDS)由节点和控制依赖边构成，表示程序的控制流信息.

定义4 数据依赖子图(Data Dependence Sub-graph，DDS)由节点和数据依赖边构成，表示程序的数据流信息.

依赖图中的边主要有4种依赖关系:控制依赖、流依赖、声明依赖和过程调用依赖.令v1，v2分别为依赖图中的两个节点，分别定义如下:

定义5(控制依赖) 如果v2的执行是由v1表示的谓词在执行时确定的，那么v2控制依赖于v1.不从属于任何控制谓词的节点控制依赖于entry节点.

定义6(流依赖) 如果有一条从v1到v2的路径，且存在一个在v2中定义并在v1中使用的变量，且该变量在从v1到v2的路径上的其他任何地方没有被重新定义，则称v2流依赖于v1.

定义7(声明依赖) 从声明某变量的节点v1到后面的各个定义该变量的节点v2间的特殊的数据依赖.

定义8(过程调用依赖) 从函数调用节点v1到被调函数入口节点v2的边.

2 面向程序理解的SDG自动生成模型

2.1 对传统SDG的改进

1)传统SDG数据流分析的复杂度高，不适合于大规模软件分析，因此本文将SDG分解为CDS和DDS，基本操作基于CDS，只在需要数据流信息时，在CDS的基础上计算数据流信息，这样既可利用SDG能够表示程序语法与语义信息及便于程序匹配的优点，又可降低数据流分析的复杂度，节省空间和时间，使之适合于分析大规模代码.

2)传统SDG以不同的形式表示各种选择结构语句和循环语句，不利于代码标准化操作，因此本文在SDG中新增加了选择结构节点和循环结构节点类型.选择结构节点包括selection节点和selector节点，统一了所有选择结构语句if、if-else、switch和选择运算符(?:)的表示形式，其中:selection节点为选择结构;selector节点及其子节点为选择分支.循环结构节点包括iteration节点和init-sub节点，统一了 for、while和 do-while的表示形式.其中iteration节点表示选择结构，其子节点表示循环体中的语句，init-sub节点用于dowhile语句中.统一了选择语句和循环语句表示，便于消除选择结构和循环结构的语法表示的多样化.

3)传统的SDG将表达式表示为节点中的token串，这种表示方式不能充分表示表达式的语法结构，本文将表达式表示为抽象语法树，连接到语句节点上.这样，使得控制依赖树不但可以表示控制流，还可以充分表示语法信息，便于执行指针分析和程序转换.

2.2 自动生成模型

根据源程序SDG的特点，本文基于程序理解的基本原理将整个SDG自动生成过程划分为:程序信息的提取、CDS的构造和DDS的构造.图1给出了面向程序理解的SDG自动生成的模型.

图1 面向程序理解的SDG自动生成模型

CDS是根据程序信息提取阶段创建的token串、符号表和函数列表来构建的，在创建系统CDS的同时处理程序的某些语法错误.

DDS的构造本质上是建立流依赖边和声明依赖边，可归结到程序中到达-定值信息的求解.由于CDS包含控制流信息，可通过CDS获得节点之间的控制依赖关系，从而获得各个节点的到达-定值信息，因此可在创建完CDS后对其执行数据流分析，构建DDS.

3 CDS的构建

进一步分析程序信息提取阶段创建的token串、符号表和函数列表来构建CDS，算法如图2所示.其中:GS为语法栈，用来保存分析过程中需要记录的语法信息;hQ为控制依赖节点队列，用以记录节点间的控制依赖关系.该算法识别程序的语法元素，并建立各个语句节点间的控制依赖关系，从而生成CDS.

图2 系统CDS构建算法

4 按需DDS构建

数据依赖是节点表示的语句之间数据的定义和使用关系.数据依赖可分为不同的类型，如流依赖、声明依赖等.

本文自底向上按需分析给定程序模块的函数调用关系:对给定程序模块的函数调用图，首先计算其终端节点函数的数据依赖，然后自底向上分析该函数的主调函数的数据依赖，当终端节点存在多个主调函数时，只需分析终端节点一次，无需重复分析终端节点，也无需多个过程依赖图拷贝.可以对给定程序模块执行局部数据依赖分析，因此适用于分析大规模程序.

基于编译器代码优化领域中经典的迭代数据流分析算法，在CDS的基础上计算数据依赖信息，建立DDS，其构建模型如图3所示.

图3 系统DDS构建模型

4.1 求到达－定值信息

要建立各种数据依赖边应首先求节点间的到达-定值信息.到达-定值的相关概念如表1所示.

表1 数据流方程的定义

其中:

所有患者均顺利完成手术。2组患者术前腰椎侧凸Cobb角及腰椎前凸角差异无统计学意义（P ＞0.05，表1）；2组术后2周及1年腰椎侧凸Cobb角及腰椎前凸角均较术前显著改善，差异有统计学意义（P ＜ 0.05，表1）；A组术后1年腰椎侧凸矫正率为79.2%，B组为81.4%，差异无统计学意义（P ＞ 0.05）。2组患者术前顶椎旋转程度差异无统计学意义（P ＞ 0.05）；术后2周及1年顶椎去旋转程度B组优于A组，差异有统计学意义（P ＜ 0.05，表2）。

1)变量x的定值是一个语句，它赋值或可能赋值给x.最普通的定值是对x的赋值或读值到x中的语句.

2)如果有路径从紧跟d的点到达p，并且在这条路径上d没有被注销，则定值d到达p.

3)如果某个变量a的定值d到达点p，那么p引用a的最新定值可能在d点.如果沿着这条路径的某两点间是读a或对a的赋值，那么注销变量a的定值d.

为了计算到达程序中每个语句的定值的集合，首先计算局部的定值信息，然后通过控制依赖边进行传播.数据流信息可以由建立和解方程来收集，这些方程联系程序不同点的信息.

当控制流通过一个语句时，语句末尾的信息是在这个语句中产生的信息或是进入语句开始点并且没有被这个语句注销的信息.由数据流方程可看出，算法的关键在于各个控制流节点的GEN和KILL集合的计算，而生成GEN和KILL集合则需要知道各个节点定值和使用了那些变量，用DEF与REF集合来表示.

4.1.1 计算REF与DEF集合

CDS中节点的 GEN、KILL、IN、OUT集合的计算都是基于各节点的REF与DEF信息的，所以从CDS的节点中收集REF与DEF信息对于到达-定值的计算是十分关键的.

CDS中每个节点都有一个REF和DEF集合.一个节点的REF集合包含了该节点进行计算时引用的所有变量，DEF集合包含了该节点计算的变量.如表2所示.

表2 基本表达式的REF集合定义

在建立好CDS后，便可以后根序遍历CDS，根据节点的不同类型，采用表3中相应的表达式求其REF和DEF集合.

表3 各种不同类型的语句的REF和DEF集合定义

4.1.2 计算GEN和KILL集合

在获得CDS中各个节点的REF和DEF集合信息后，GEN集合的生成将十分直接:在遍历CDS时，如果当前节点是赋值语句节点或scanf语句节点，则根据它的DEF集合，由当前的节点号和DEF中的变量名组成GEN集合中一个元素，从而建立GEN集合.

KILL集合的生成需要对整个CDS中的节点进行多次遍历.算法描述如图4所示.

图4 KILL集合求解算法

4.1.3 计算IN和OUT集合

为了传播数据流信息，在计算到达-定值信息时需要使用IN和OUT集合.一个节点的IN集合由到达该节点的前一点的定值组成，OUT集合由到达该节点下一点的定值组成.由于一个语句节点的IN和OUT集合可能不同，本文为CDS中的每个语句节点都计算这两个集合.

采用迭代法求各个节点的IN和OUT集合.在每次迭代时对CDS中每个节点N，使用KILL和GEN集合计算IN与OUT集合.IN［N］等于节点N在CDS中前驱节点的OUT集合，OUT［N］是用IN［N］、GEN［N］、KILL［N］生成的.算法描述如图5所示.

图5 到达－定值信息的求解算法

到此为止，CDS中每个节点的到达-定值信息就计算完毕了.

4.2 建立数据依赖边

在获得了各个节点的IN和OUT集合后，后根序遍历CDS，利用各节点的IN集合和REF集合即可获得节点间的数据依赖关系.具体的规则是如果当前节点的REF集合中某个变量名和IN集合中某个二元组中的变量名相同，则认为当前节点和IN集合同一个二元组中给出的节点之间存在流依赖关系，并将生成的流依赖关系放入表中存储.建立流依赖边和声明依赖边的算法如图6所示.

图6 程序系统DDS建立算法

5 系统依赖图的生成实例

如图7，8中所示的两个示例程序，均实现相同的功能，但循环结构和选择结构采用了不同的语法表示形式，Horwitz方法采用不同的形式表示这两个程序，而本文创建的SDG可将这两个语义等价程序表示成相同的形式，如图9所示，从而可以统一分析、理解这两个程序，降低了程序理解的复杂度.在此基础上，可以进一步执行程序标准化转换，消除代码多样化.

图7 示例程序1

图9 系统依赖图实例

此外，与Horwitz方法相比，本文方法直接基于控制依赖子图分析数据流信息，并且可实现按需的数据流分析，降低了数据流分析的复杂度，节省空间和时间，使之适合于分析大规模代码.

图8 与示例程序1语义等价的示例程序2

6 SDG在程序理解中的应用

本文提出的系统依赖图生成算法已在“基于程序理解的C语言编程题自动评分系统”中得到了应用，整个评分过程划分为3个阶段:将程序代码转换成SDG;根据控制流和数据流对SDG进行标准化转换;最后匹配标准化后的学生程序与模板程序控制依赖子图，并根据匹配结果给出评分.由此可看到，编程题自动评分系统的基础和关键是SDG.

本文算法还被应用于“语义相似的程序识别”中，识别大规模程序中语义相似的程序代码［19］.其基本思想是:分别将待检测的两段源代码解析为两棵系统依赖图的控制依赖树，并分别执行基本代码标准化;利用度量值方法提取两棵基本代码标准化后的控制依赖树的候选相似代码控制依赖树;对提取的候选相似代码，进行数据流分析，执行高级代码标准化操作;计算语义相似度，获得相似度结果，从而识别语义相似的程序代码.

应用结果表明:本文构建的SDG能够充分表示程序的语法和语义，既可应用于分析小规模程序代码，也可应用于分析大规模程序代码，对可执行按需数据流分析，具有较低的复杂度和较高的准确性，并为程序标准化与语义分析提供了方便.

7 结论

1)提出了一种面向程序理解的SDG构建算法，包含程序信息的提取、CDS的构建和DDS的构建3个阶段.

2)改进了传统的SDG，直接基于CDS分析数据流信息，统一表示选择语句和循环语句，将表达式表示为抽象语法树.

3)提出的SDG构建算法已被应用于基于程序理解的编程题自动评分系统和大规模程序的语义相似程序代码识别中，结果表明该SDG能够充分表示程序的语法和语义，且按需进行数据流分析的方法降低了程序理解和分析的复杂度.

［1］ EXTON C.Constructivism and program comprehension strategies［C］//Proceedings of the 10th International WorkshoponProgram Comprehension(IWPC'02).Washington，DC:IEEE Computer Society，2002:282-283.

［2］ OTTENSTEIN K J，LOTTENSTEIN M.The program dependence graph in a software development environment［C］//Proceedings of the First ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments.New York:ACM，1984:177-184.

［3］HORWITZ S，REPS T，BINKLEY D.Interprocedural slicing using dependence graphs［J］.ACM Transactions on Programming Languages and Systems，1990，12(1):26-60.

［4］ MATSUMOTO T，SAITO P，FUJITA P.Equivalence checking of C programs by locally performing symbolic simulation on dependence graphs［C］//Proceedings of the 7th International Symposium on Quality Electronic Design(ISQED'06). Washington， DC:IEEE Computer Society，2006:370-375.

［5］逄龙，王甜甜，苏小红，等.支持多程序语言的静态信息提取方法［J］.哈尔滨工业大学学报，2011，43(3):62-66.

［6］SRIDHARAN M，FINK P J，BODIK R.Thin slicing［C］//Proceedingsofthe2007 ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM，2007:112-122.

［7］ANDERSON P，ZARINS M.The codesurfer software understanding platform［C］//Proceedings of the 13th International Workshop on Program Comprehension.Washington，DC:IEEE Computer Society，2005:147-148.

［8］MILLER J，REFORMAT M，ZHANG H.Automatic test data generation using genetic algorithm and program dependence graphs［J］.Information and Software Technology，2006，48(7):586-605.

［9］ WANG Tiantian，SU Xiaohong，MA Peijun，et al.Ability-training-oriented automated assessment in introductory programming course［J］.Computers ＆Education，2011，56(1):220-226.

［10］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.

［11］马培军，王甜甜，苏小红.基于程序理解的编程题自动评分方法［J］.计算机研究与发展，2009，46(7):1136-1142.

［12］杨轶，苏璞睿，应凌云，等.基于行为依赖特征的恶意代码相似性比较方法［J］.软件学报，2011，22(10):2438-2453.

［13］WANG Tiantian，SU Xiaohong，MA Peijun.Program normalization for removing code variations［C］//International Conference on Computer Science and Software Engineering. Washington， DC:IEEE Computer Society，2008:306-309.

［14］SNELTING G，ROBSCHINK T，KRINKE J.Efficient path conditions in dependence graphs for software safety analysis［J］.ACM Transactions on Software Engineering and Methodology，2006，15(4):410-457.

［15］王甜甜，苏小红，马培军.程序标准化转换中的指针分析算法研究 ［J］.电子学报，2009.37(5):1104-1108.

［16］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.

［17］ZHAO Jianjun，RINARD M.System Dependence Graph Construction for Aspect-Oriented Programs［R］.MIT-LCSTR-891，MIT:Laboratory for Computer Science，2003.

［18］SILVA J TAMARIT S，TOMÁS C.System dependence graphs in sequential erlang［C］//Proceedings of the 15th International Conference on Fundamental Approaches to Software Engineering.Washington，DC:IEEE Computer Society，2012:486-500.

［19］王甜甜，马培军，苏小红，等.一种基于程序源代码语义分析的代码相似度检测方法:中国，200910073094.4［P］.2009.