对象依赖关系在变更影响分析中的应用

杨鹤标 陈小强

摘 要：面向对象软件系统中对象间的依赖关系会因为部分对象的变更而波及到系统其它组成部分，对此，给出了一种对象依赖关系构造方法。该方法从粒度上将面向对象系统中对象间的依赖关系简化为接口依赖和方法依赖，通过搜索系统的层次结构，将构造出的依赖图中复杂的多对多依赖关系转化为依赖关系树中较为简洁的一对多依赖关系。当具体对象发生变更时，从变更节点处搜索多叉树获得变更影响的波及范围，根据变更度量方法得到变更产生的额外工作量，确定变更影响程度，为变更可能产生的风险评估和控制提供量化依据。通过一个实际案例展示了变更影响评估方法的可行性。

关键词：面向对象；对象依赖关系树；变更影响分析；波动效应

DOIDOI：10.11907/rjdk.181130

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2018）010-0153-04

英文摘要Abstract：The dependency between objects in OOS impacts other components while some objects take changes，this paper proposes an object dependency constructing method，which simplifies the dependency between objects into interface and function dependency，searches the hierarchical structure of system，and converts the complex many-to-many dependency in dependency graph to concise one-to-many dependency of dependency trees.When concrete object changes，this paper determines the scope of change impact by searching the changed node，calculates the extra workload，confirming the degree of change impact and providing quantitative base for risk assessment and control that change causes. Last the feasibility of change impact evaluation method is proved by an example.

英文关键词Key Words：object oriented； object dependency trees； change impact analysis； ripple effect

0 引言

面向对象系统中对象之间存在着错综复杂的依赖关系[1-2]，在软件开发过程中，客户需求的变更又是客观存在、不可避免的[3]，虽然面向对象开发技术提高了软件开发效率，但变更影响通过对象间依赖关系的传递又影响到开发效率，且带来的风险难以预测。传统的依赖分析法大多基于控制依赖和数据依赖的依赖图模型进行程序分析[4-5]。该方法从语句粒度进行分析研究，会得到大量冗余的依赖信息。当软件规模到达一定量级时，就无法直观确定变更影响的范围。面向对象的软件系统是以对象为基础的程序逻辑，当遇到面向对象中因多态技术而产生间接依赖关系时，传统的程序依赖图显得力不从心[6]。分析面向对象系统中对象之间的依赖关系，确定需求变更波及效应的涉及范围，在变更之前就清晰认识到变更造成的各种潜在影响，更易于对软件项目的开发过程进行控制以及降低项目开发风险。

本文根据面向对象的特性，从对象这一粒度层面对面向对象系统中的依赖关系进行分析，提出了一种对象层依赖关系构造方法。该方法在提出的依赖和节点表示法基础上，通过剖析面向对象系统的结构关系构造对象依赖图，再对依赖图进行遍历得到各组成部分之间的依赖关系树，将依赖图中多对多的辐射状依赖关系转化为依赖关系树中较为简洁的一对多树形依赖关系，可以方便快捷地确定对象之间的依赖关系；当发生对象变更时，以变更对象节点为初始点搜索依赖关系树，获取依赖于变更节点的其它对象节点，从而确定变更产生的影响范围。根据对象之间的依赖因子计算出变更产生的额外工作量，为项目过程控制及风险分析提供定量依据。

1 建模

依赖关系指系统组成部分之间存在的一种语义连接。当一个对象发生变更时，与之有依赖关系的另一个对象也发生相应变更，从而保证系统语义上的完整性和一致性[7]。通常將前者称为源对象节点，后者称为目标对象节点。如果源对象节点不依赖于其它对象节点，称这样的对象节点为底层节点。

1.1 对象依赖关系定义

定义1：对象依赖关系表示为一个三元组Dependence={（OS，OT，depType）| OS∈O，OT ∈O，Reachability（OT，OS）=1}，其中O是面向对象系统中对象节点的集合，OS表示源对象节点，OT表示目标对象节点，depType表示依赖类型，Reachability表示对象之间的可达性。

定义2 ：对象可达性。Reachability（Om，On）：Om，On是程序中的对象节点，存在着一条成功执行轨迹[8]Path，Ni是Path中的程序节点。Om通过节点Ni调用On，称Om与On的可达性为1，即Reachability（Om，On）=1；反之Reachability（Om，On）=0，记作：

Reachability（Om，On）=1，OminvokeOn0，else

1.2 依赖性质

当依赖源对象节点OS发生变更时，依赖目标对象节点OT也会发生相应变化。分析对象依赖关系可得出如下几种性质：

性质1： 自反性。软件系统中的任一对象都是依赖于自身的，即N，（N，N）∈Dependence。

性质2： 传递性。如果对象节点N1依赖于对象节点N2，对象节点N2依赖于对象节点N3，则对象节点N1也依赖于对象节点N3，即N1，N2，N3，（N1，N2）∈Dependence Λ （N2，N3）∈Dependence→（N1，N3）∈Dependence。

性质3 ：时序性。对象节点之间的依赖在时间上存在顺序性，即N1，N2，N3，在同一时间点，（N1，N2）∈Dependence Λ （N1，N3）∈Dependence是不成立的。

性质4 ：方向性。对象节点之间的依赖具有方向性，即依赖的方向是由依赖目标对象节点指向依赖源目标节点，记为ST→SS。

性质5 ：多样性。系统自身的性质决定了对象节点之间的依赖关系多种多样。一个系统由对象节点之间通过各种类型的依赖联系在一起。

根据依赖关系性质可有以下两种推论：

推论1 ：非循环依赖性。根据传递性和方向性可以推导出对象节点之间不存在循环依赖，即N1，N2，N3，（N1，N2）∈Dependence Λ （N2，N3）∈Dependence Λ（N3，N1）∈Dependence是不成立的。

推论2 ：直接依赖性与间接依赖性。两个对象节点之间的依赖路径上不包含其它对象节点，则将其称为直接依赖，反之称其为间接依赖。

1.3 对象依赖关系分类

面向对象软件中对象间多层抽象特性[9]使不同的依赖关系对接口、类或方法的依赖程度有所不同，依赖程度的差异性增加了变更影响分析中变更度量的难度，导致变更影响分析不准确。确定对象节点间的依赖类型可得到对象之间的依赖程度，从而提高变更影响的准确性。

本文将对象之间的依赖关系总结为接口依赖和方法依赖两大类。接口依赖指对象之间通过接口进行交互，从而产生依赖关系，主要包括包级别的依赖和类级别的依赖；方法依赖又称函数依赖，指对象通过方法的调用产生依赖关系[10]，主要包含函数级别的依赖。各个级别的依赖关系又可进一步细分，具体的依赖类型划分如表1所示。

2 对象依赖关系提取

在构建面向对象依赖图的基础上，对依赖图进行搜索，得到底层节点集合；再以底层节点中的元素为起始点深度优先搜索面向对象的依赖关系图，将依赖于底层节点的对象节点作为子节点，构造出以底层节点为根节点的对象依赖关系树，通过该方法可将依赖图中复杂的多对多依赖关系转化为关系树中较为简洁的一对多依赖关系，降低确定依赖关系的复杂度。

2.1 依赖图表示

本文在文献[11]提出的面向对象依赖图表示方法基础上，对依赖图中的对象节点和依赖关系设定相应的图形表示法，依赖关系图中使用到的依赖边和程序节点及其表示法如表2、表3所示。

对于依赖图中的每一个对象节点N，入度indegree（N） 表示依赖于节点N的节点数，出度outdegree（N）表示节点N依赖的节点数。由此可知，底层节点的出度为0，通过引入出度与入度的概念可有效解决依赖关系有向图中可能存在的循环依赖问题。

2.2 底层节点确定

根据底层节点解释可知，通过遍历依赖图中对象节点，找出所有出度为0的节点，就可得到底层节点的集合，算法1说明了底层节点确定过程。

算法1：

findRootNode

输入：源程序的依赖图

输出：RootNode

RootNode=，RootClass=，RootMethod=

//calculate the RootClass

for i=1 to n

if outdegree（class（i））=0 then

RootClass= RootClass ∪ class（i）

//calculate the RootMethod

for i=1 to m

if outdegree（method（i））=0 then

RootMethod= RootMethod ∪ method（i）

//calculate the RootNode

RootNode= RootClass ∪ RootMethod

2.3 依赖关系树构造

依赖关系多叉树的构造步骤：将依赖图中出度为0的节点集合RootNode作为初始队列，对队列中的元素执行出队操作，并以出队元素作为起始节点对依赖图进行深度優先搜寻，搜索到的关联节点执行入队操作。重复上述操作，直至队列为空时终止。算法2和算法3说明了将依赖关系图转化为依赖关系树的实现过程。

算法2：

DFS（G）

while indegree（RootNode）！=0

for each RootNode∈G.V

DFS-VISIT（G，RootNode）

// output the dependency set and dependency path

indegree（RootNode）--

connect（）；//connect the childtree

算法3：

DFS-VISIT（G，u）

for each v∈G.Adj（u） //v is the childnode of u

if indegree（v）！=0

DFS-VISIT（G，v）

indegree（v）--

// connect childnode to v by dependency path

//Construct the dependenceTree

为迅速找到变更节点影响到的程序节点，在得到依赖关系树后对其进行分割处理，将父节点和子节点组成的子树作为一棵深度为2的依赖关系树，建立直接依赖关系树。通过分析变更节点子节点子树，可方便地找到变更所影响到的节点结合。但此种方法缺点是会生成数量众多的依赖关系树，空间复杂度较高。

3 变更影响评估

在面向对象软件的维护过程中，软件变更是无法避免的，且变更会对系统其它部分产生难以预料的波动效应[12]，软件变更影响分析可确定潜在影响。变更影响分析包含一个变更元素的集合changeSet，以及变更影响到需要维护的元素集合impactSet。在遍历对象依赖关系树的基础上得到变更影响集合，再根据对象间的依赖因子计算变更带来的额外工作量。

3.1 变更影响集合确定

变更提议是软件开发人员在现有软件上提出的变更[13]，其组成的集合changeSet可根据实际变更要求准确定位到对象依赖关系树中的若干个节点；以changeSet中的每个元素为根节点依次递归遍历其对应的依赖关系树，得到每个元素的影响集合[14]impactSet，算法4描述了确定影响集合的过程。

算法4：

travel（node）

impactSet=，child_node=

for each node in changeSet do

for i=1 to node.child_list do

impactSet= impactSet∪child_node（i）

travel（childnode（i））

return impactSet

得到每个变更元素的影响集合后，可进一步求出影响集合之间的交集。该交集表示众多变更所共同影响到的元素，通过这一步骤可降低影响集合的冗余度，提高变更影响分析的准确度。

3.2 变更影响度量

变更影响程度在软件工程中体现为变更所产生的实际工作量，本文对文献[15]和文献[16]中的评估公式加以修改，根据变更集合元素和变更影响集合中每个元素的依赖因子以及依赖关系所属级别的工作负载，得到实施变更所产生的实际工作量大小。变更的工作量计算见公式（1）。

changeDegree=∑WLi*depFactor（OS，OT）（1）

式（1）中，WLi表示变更每个级别所需的工作负载，本文将包、类和方法级别的工作负载分别设为8、4和2；depFactor（OS，OT）表示两者之间的依赖因子。图1表示对象节点之间的依赖关系范例。

假设此依赖关系的工作负载为4，节点之间的依赖因子为depFactor（N1，N2）=0.8，depFactor（N2，N3）=0.4，depFactor（N3，N4）=0.6。通过上述条件可得到节点N1变更产生的额外工作量changeDegree=4*0.8+4*0.4+4*0.6=7.2。

4 案例分析

选取雇员管理系统中的部分程序源码，采用本文方法构建对象间的依赖关系。根据本文提出的图形表示法得到示例程序的依赖图如图2所示，经依赖树构造算法产生的依赖关系树如图3所示。关系树中的子节点直接依赖于父节点，通过观察依赖关系树，可以清晰得到两个节点之间是否存在依赖关系。

假设软件系统开发完成后，因为客户需求发生变化，需要对employeeService和EmployeeDAO进行修改，遍历这两个节点对应的依赖关系树可得到依赖于变更节点的依赖集合分别为{employeeServiceImpl，XXXEmployeeAction}和{EmployeeDAOImpl，employeeServiceImpl}，对影响集合中相同节点处理后得到影响的对象为{employeeServiceImpl，XXXEmployeeAction，EmployeeDAOImpl}。

通过底层节点提取算法对源程序的依赖关系分析可得到底层节点集合RootNode={Employee}。

变更集合元素和变更影响集合元素之间的工作负载都为4，对象间依赖关系和依赖因子如表4所示。结合分析得到的工作负载和依赖因子，可计算出此次变更所产生的额外工作总量changeDegree=4*0.6+4*0.2+4*0.6+4*0.2=6.4。

5 结语

软件项目开发過程中变更是不可避免的，在变更实施之前，准确预测变更对系统产生的影响范围及程度，对降低开发风险尤为重要。本文在分析面向对象系统组成部分的依赖关系基础上，提出一种对象依赖关系构造方法。该方法将依赖图中的多对多依赖关系转化为一对多的依赖关系树，通过遍历以变更节点为起始点的依赖关系树，得到变更影响波及的范围。根据对象间依赖因子计算变更产生的额外工作量，为项目开发过程分析提供定量依据。案例分析表明，该方法具有较高的准确度。为提高变更影响分析精度，今后可进一步研究接口和方法中属性的类型信息。

参考文献：

[1] ZHAO J.Applying program dependence analysis to Java software[C].Workship on Software Engineering and Database Systems，Taiwan，1998：162-169.

[2] MIKHAILOV A，HMELNOV A，CHERKASHIN E，et al.Control flow graph visualization in compiled software engineering[C].International Convention on Information and Communication Technology，Electronics and Microelectronics.2016：1313-1317.

[3] 刘华虓，金英，马鹏飞.一种需求变更影响分析方法[J].计算机研究与发展，2013，50（8）：1769-1777.

[4] DENARO G，MARGARA A，PEZZE M，et al.Dynamic data flow testing of object oriented systems[C].IEEE International Conference on Software Engineering.ACM，2015：947-958.

[5] NAJUMUDHEEN E S F，MALL R，SAMANTA D.A dependence graph-based test coverage analysis technique for object-oriented programs[C].Sixth International Conference on Information Technology：New Generations.IEEE Computer Society，2009：763-768.

[6] COOPER D，CHAN M W，MEHRA G，et al.Using dependence graphs to assist manual and automated object oriented software inspections[C].Australian Software Engineering Conference.IEEE Computer Society，2006：262-269.

[7] 杨鹤标，陈震.面向对象代码变更影响分析模型的研究[J].计算机工程与设计，2010，31（19）：4232-4234.

[8] 曹鹤玲，姜淑娟，鞠小林，等.基于动态切片和关联分析的错误定位方法[J].计算机学报，2015（11）：2188-2202.

[9] 李轩，郝克刚，葛玮.面向对象软件度量的分析和研究[J].计算机技术与发展，2006，16（11）：38-41.

[10] 欧阳，胡顺仁，汪治华.面向对象系统的类之间依赖关系度量研究[J].计算机科学，2004，31（2）：181-183.

[11] CHEN J L，WANG F J，CHEN Y L.An object-oriented dependency graph for program slicing[C].Technology of Object-Oriented Languages，1997.TOOLS 24.Proceedings.IEEE，1997：121-130.

[12] SUN X，LI B，LEUNG H，et al.Static change impact analysis techniques：a comparative study [J].Journal of Systems & Software，2015，109（C）：137-149.

[13] LEE M，OFFUTT A J，ALEXANDER R T，et al.Algorithmic analysis of the impacts of changes to object-oriented software[EB/OL].https：//ieeexplore.ieee.org/document/868959/arnumber=868959.

[14] NEJATI S，SABETZADEH M，ARORA C，et al.Automated change impact analysis between SysML models of requirements and design[C].ACM Sigsoft International Symposium on Foundations of Software Engineering.ACM，2016：242-253.

[15] YANG H B，LIU Z H，MA Z H.An algorithm for evaluating impact of requirement change[EB/OL].http：//www.doc88.com/p-6931564788263.html

[16] 楊鹤标，张继敏，朱玉全.一种需求变更影响的评估算法[J].计算机工程，2006，32（23）：82-84.

（责任编辑：杜能钢）