基于抽象语法树的修改影响分析方法

高 灿， 侯秀萍， 孙士明

（长春工业大学 计算机科学与工程学院，吉林 长春 130012）

0 引 言

在软件测试和维护过程中，一旦发现软件系统中存在错误，则应立即排除它们，为了保证程序的修改没有引入新的错误，则必须对其进行回归测试。为了节省测试成本、提高测试效率，回归测试只需要测试那些由于修改而受到影响的部分[1]。

面向对象程序中，多态允许对同样的请求可以有不同的响应，动态绑定允许在程序运行时才决定它的执行体，类的继承和使用过程使得面向对象程序具有模块化、层次化和有利于代码重用等优点，但同时又使得程序修改的扩散效应更加明显[2]。例如，继承使得一个类的成员变量和成员函数能够被一些子类所重用[3]，所以，当修改父类的时候就会导致与它相关的类也要在回归测试的过程中重新进行测试。

在回归测试中，重新测试所有的类从测试代价和成本上讲是完全没有必要的，仅测试那些修改的内容和修改影响到的内容就能够达到和全部重测同样的效果。杨芙清[4]等通过分析面向对象软件系统的特性，定义了对象之间的依赖关系，通过依赖关系导出测试对象的方法序列。Rothermel[5]等提出通过构建程序依赖图（Program Dependence Graph）来表示数据依赖和控制依赖，并找出关于继承、封装和多态等构造关系的子类和其它类[6]。

文中针对面向对象程序具有继承、封装、多态等特点，深入研究了程序修改的影响范围，提出了基于抽象语法树的修改影响分析方法，为测试人员提供合理的测试范围，期望能够达到减少回归测试花销，提高测试效率的目的。

1 程序依赖关系研究

1.1 依赖关系定义（Dependence Relationship，DR）

面向对象程序的封装性要求把属性和方法封装在一起形成类，不同的类通过方法的调用实现交互。

定义1 类C定义为属性集V和方法集M的并集，记为：

定义2 类C与C′之间的依赖关系D定义为在集合C和C′上的二元关系，记为：

其中，序偶〈x，y〉表示元素x依赖于元素y，即元素y的变化会影响到元素x。

定义3 数据依赖（Data Dependence，DD）。设类C中存在属性v∈V，若属性集V发生属性类型和值的调整及属性数量的增减等变化，导致类C′中引用属性v的方法发生变化，则称类C′数据依赖于类C，记为：C′DDC。

定义4 控制依赖（Control Dependence，CD）。设类C中存在方法m∈M，若方法集M发生访问类型、参数和语句的变化及方法数量的增减等情况，导致类C′中调用方法m的方法发生变化，则称类C′控制依赖于类C，记为：C′DCC。

1.2 依赖关系存储结构设计

根据程序依赖关系的定义，可以解析源文件语法树，抽取其数据依赖和控制依赖关系，将其存于相应的存储结构中，为修改影响分析提供依据。其主要结构设计如下：

1）数据依赖关系表（Date Dependence Relationship Table，DDRT）。

DDRT：：＝ （Class，Field，Method），其中：

Class：类名；

Field：属性名；

Method：使用该变量的方法名。

2）控制依赖关系表（Control Dependence Relationship Table，CDRT）。

CDRT ：：＝（Class，Method，Method＿call，Class＿call），其中：

Class：类名；

Method：方法名；

Method＿call：被调用的方法名；

Class＿call：被调用方法所在的类名。

2 基于抽象语法树的修改影响分析

在软件测试过程中要对程序源代码的语法结构进行合理存储，以利于确定修改信息，因此需要找到一种源代码语法层次信息的载体，也就是从程序源代码文件生成的抽象语法树（Abstract Syntax Tree，AST）[8]，并通过遍历Java源程序的抽象语法树获取源程序中的类名、方法名、属性名和调用信息等内容存储在二维表中。Eclipse开发平台中的JDT（Java Development Tooling）工具通过对源程序进行语法分析和词法分析可以将源代码解析成抽象语法树，用户只需要指明源文件的存储位置并调用ASTParser类中的creatAST（）方法就可以得到源程序中的类名、方法名、属性名和调用信息等内容并进行存储，以便后续使用。

对于一个面向对象程序P，通过遍历抽象语法树建立其DDRT表和CDRT表分别为T1，T2；设修改后的程序为P′，其DDRT表和CDRT表分别为T′1，T′2。

针对面向对象程序的特点，将程序的修改定义为6种原子修改，分别为：

1）增加方法；

2）删除方法；

3）修改方法；

4）增加属性；

5）删除属性；

6）修改属性。

所有的修改都可以视为这几种操作的组合。

2.1 增加方法（Added Method）

当增加一个方法时，还要同时增加对这个方法的调用，受到影响的部分为修改后的程序中直接和间接调用它的那些方法。因此，设新增加的方法为（C，m），按下述递归规则定义受其影响的方法集合AAM（C，m）定义为 ：

从AMi（C，m）构成 AMi＋1（C，m），如果不增加任何新的元素，有

2.2 删除方法（Deleted Method）

当删除一个方法时，对于这个方法的调用也同时被删除，因此，受到影响的部分为修改前的程序中调用它的那些方法。设删除的方法为（C，m），则受到影响的方法集合DM（C，m）定义为：

从DMi（C，m）构成 DMi＋1（C，m），如果不增加任何新的元素，有

2.3 修改方法（Changed Method）

对方法的修改包括以下几种情况：

1）修改方法的访问类型（public，protected和private）。

若将访问类型由public或者protected类型变为private类型，则方法不能被其它方法调用，因此，修改后的程序中不会出现对它的调用关系，受到影响的部分为修改前的程序中直接和间接调用该方法的其它方法，也就是相当于删除一个方法，对于此类情况的处理方法同式（4）；反之，若将访问类型由private类型变为public或者protected类型，则方法能被其它方法调用，因此，修改后的程序中调用该方法的其它方法受到影响，也就是相当于增加一个方法，处理方法同式（3）。

2）修改方法的参数（包括参数类型、参数个数和参数值）和方法体中的语句时，修改前和修改后的程序中直接和间接调用该方法的其它方法都会受到影响，因此处理按照方法式（3）和式（4），并取两种方法计算出的结果的并集。

2.4 增加属性（Added Property）

当增加一个属性时，受到影响的部分为修改后的程序中使用它的那些方法以及调用那些方法的其它方法。因此，设新增加的属性为（C，v），则受影响的方法集合AP（C，v）定义为：

从APi（C，v）构成APi＋1（C，v），如果不增加任何新的元素，有

2.5 删除属性（Deleted Field）

当删除一个属性时，受到影响的部分为修改前的程序中使用它的那些方法以及调用那些方法的其它方法。因此，设删除的属性为（C，v），则受影响的方法集合DP（C，v）定义为：

从DPi（C，v）构成DPi＋1（C，v），如果不增加任何新的元素，有

2.6 修改属性（Changed Property）

当修改一个属性时，受到影响的部分为修改后的程序中使用它的那些方法以及调用那些方法的其它方法。因此，设修改的属性为（C，v），则受影响的方法集合CP（C，v）定义为：

从CPi（C，v）构成CPi＋1（C，v），如果不增加任何新的元素，有

2.7 其它修改

除了以上提到的6种原子修改外，还有基于类粒度的修改，如增加类（Added Class）、删除类（Deleted Class）和修改类（Changed Class）。

增加类表示在一个空类中增加新的方法和属性。因此，可以使用式（3）和式（5）中提供的方法来确定受到修改影响的方法集。

删除类相当于对一个类删除它的所有属性和方法。因此，可以使用式（4）和式（6）中提供的方法鉴别修改影响范围。

修改类相当于对一个类中的属性和方法的修改，因此，可以使用式（3）、式（4）和式（7）中提供的方法确定修改影响范围。

3 实验结果

通过以上提到的集中方法，对一个Java测试程序进行了修改影响分析实验。该程序中包含6个类和20个方法，实验结果见表1。

表1 实验结果

从表中可以看出，与全部重测所有类中的所有方法相比，基于抽象语法树的修改影响分析方法能够减少回归测试中重新测试的方法数量，从而有效提高回归测试的效率，但是这种方法仅适合少量修改的情况。

4 结 语

介绍了一种针对面向对象程序的基于抽象语法树的修改影响分析方法，建议在回归测试中对修改的方法本身及受到属性和方法修改所影响的方法进行测试。虽然没有实现全面的自动化测试，但也在一定程度上提高了测试的效率，减少了测试的代价，在后续的研究过程中将继续关注修改范围的自动化确定和回归测试用例的选择等问题。

[1]White L J，Leung H K N.A firewall concept for both control－flow and date－flow in regression integration testing[C]／／Proceedings of the Conference on Software Maintenance，1992：262－270.

[2]雷海虹，缪力，张大方.面向对象程序的两种修改影响分析方法[J].计算机工程与科学，27（5）：101－103.

[3]陈跃峰，李中彬，谷骁勇.Java编程那些事儿[M].北京：清华大学出版社，2010：150－152.

[4]方菲，孙家骕，杨芙清.面向对象软件回归测试技术研究[J].软件学报，2001，12（3）：372－376.

[5]Rothermel G，Harrold M J.Selecting Regression Tests for Object－Oriented Sofware Proc.[C]／／IEEE International Conference on Softuare Maintenance，1994：14－25.

[6]马玉州.面向对象软件的回归测试方法研究[D]：[硕士学位论文].长春：吉林大学，2009.