软件演化环境下基于节点介数的构件重要性度量方法

成 蕾 林 英,2 李 彤

1(云南大学软件学院 云南 昆明 650091)

王晓芳1 郑交交1 李 响1

2(云南省软件工程重点实验室 云南 昆明 650091)

软件演化环境下基于节点介数的构件重要性度量方法

成 蕾1林 英1,2李 彤2*

1(云南大学软件学院 云南 昆明 650091)

王晓芳1郑交交1李 响1

2(云南省软件工程重点实验室 云南 昆明 650091)

在软件演化中，构件的重要性度量可以为软件演化的控制和监测提供依据。以软件体系结构为蓝图和支撑，提出软件体系结构有向图模型，引入节点介数对构件的重要性进行度量。并对构件的请求依赖、服务依赖进行分析和研究，通过使用Pearson相关系数进行分析，找出与节点介数最相关的因素。对大量开源软件源代码进行实验，实验结果表明，用节点介数度量构件的重要性是有效的，并且构件的请求依赖和服务依赖的总和与构件的节点介数最为相关。这也为下一步利用依赖关系衡量构件重要性指明了另一个研究方向。

软件体系结构 软件演化 构件 有向图 节点介数

0 引 言

软件系统逐渐发展为服务和构件的组合交付，并在社会的发展中出于需要被不断地调整和扩展，使得软件系统的规模增大，结构出现了多种层次、不同粒度、多种集成的方式。人们用术语“演化”来描述这种不断的改变[1,10,13]。这种普遍存在于软件系统中，软件系统逐渐变化直至达到理想形态的一系列的复杂变化活动就是软件演化。

软件具有构造和演化两个基本特性[1]。软件体系结构SA(software architecture)的发展已经趋于成熟，作为蓝图支撑人们从宏观层面对整体软件结构进行把握。然而，随着软件系统功能和规模的发展，对软件演化的掌握和控制变得越发复杂，难度也日益增加。传统的度量方法在软件演化中有着重要的贡献，展现了软件演化的某些特性[2-3,14]。然则，这些传统度量方法都共性地提早陷入软件结构中复杂的细节，对于宏观方面关注不够，难以整体且全面地把握软件结构。

20世纪90年代，Bohner[8,11]在提出软件变化分析过程框架的基础上使用可达矩阵的概念阐述了软件变化，但没有给出组成要素对软件贡献大小的概念。Valverde等[13]首先对面向对象的软件系统进行了研究，他们把系统的类图抽象为有向网络图。Myers[15]和Moura等[16]运用有向网络来表示软件系统的结构，在此基础上提出了基于重构的软件模型。随后，国内一批研究人员如汪北阳等[19]使用加权网络研究复杂软件系统的软件网络，王映辉等[17]、张朝昆等[18]开展软件结构的研究，获得了一系列研究成果。

本文的工作主要分为两个部分，一是基于构件之间的关联和有向图的概念，提出SA模型，并引入节点介数作为衡量构件在SA中的重要性指标，通过计算每个构件的节点介数，作为衡量构件重要性的参考；其次为了进一步研究与分析构件之间请求依赖、服务依赖对构件重要性的影响，使用Pearson相关系数分别计算这些依赖关系与节点介数的相关性。通过大量的实验分析，表明节点介数与构件的总依赖基本一致，依赖关系越强的构件，其节点介数越高，因此节点介数这一指标能够为软件演化过程中监控和掌握重要构件提供参考。

1 软件体系结构的模型

鉴于SA没有公认的定义，本文采用比较流行的简单定义[6,9]：SA是组成系统的构件与连接件的高层抽象，构件之间的交互作用关系视为连接件。

构件实现系统中需要的特定功能，符合一套接口标准并实现一组接口。在系统中表现为承担一定功能的数据或计算单元，也表现为面向软件体系架构的可复用软件模块，是系统中实际存在的可更换部分。

本文不考虑其内部结构，看做一个不透明的整体。把一个软件系统实例视作一个SA时，SA中构件之间的交互和依赖是有方向性的，构件之间的交互是无权有向的，则可以将SA的模型定义如下：

定义1SA的模型。将一个软件系统实例的SA的模型G描述为一个无权有向图三元组：

(1)NG是软件系统实例的SA模型的名称；

(2)V(G)是构成软件系统的构件所代表的节点的集合；

(3)E(G)是构成软件系统的构件间关系代表的无权有向边的集合。

定义2构件。一个节点所代表的构件V的描述是一个二元组：

(1)NC是构件的名称；

(2)FC是构件的功能描述。

定义3构件间关联。将构件间的交互关系作为无权有向边E描述为一个三元组：

(1)En是有向边的唯一标识；

(2)Vi是发起依赖的构件，即起始节点；

(3)Vj是接受依赖的构件，即终止节点；

(4) 即表示节点Vi指向节点Vj。

定义4构件的请求依赖。在SA的模型G=中，构件vi∈V(G)，以构件vi作为起始节点的边的总数称作构件vi的请求依赖，记为dreq(vi)。

构件的请求依赖描述了构件依赖其他模块的程度和关系。构件的请求依赖越高，则表示该构件直接依赖的构件数量越多，该构件的行为也就越复杂，所在的构件层次也就越高。

定义5构件的服务依赖。在SA的模型G=中，构件vi∈V(G)，以构件vi作为终止节点的边的总数称作构件vi的服务依赖，记为dser(vi)。

构件的服务依赖刻画了构件在SA中被其他模块直接依赖的程度。构件的服务依赖越高，构件的直接被依赖性越强，在SA中的复用率也就越高，说明该构件的行为功能越固定。

构件的请求依赖与构件的服务依赖的总和，称为构件的总依赖，记作dsum(vi)。

定义6节点介数。给定图G=，节点vi∈V(G)，在图G中经过节点vi的最短路径总数目与图G中所有的最短路径之比称为vi的节点介数，记为C(vi)。则：

(1)

其中：δst是节点s到节点t的所有最短路径的总数目，δst(v)是节点s到节点t的最短路径数中经过节点v的最短路径数目。

节点介数是一个重要的全局几何量，反应了节点在整个图中的作用和影响力。将SA的模型抽象为有向图模型后，在SA演化中引入节点介数，可以直观地观察到构件对应的节点在整个SA中的地位和影响力。节点介数是衡量构件在SA演化时的关键程度和地位的重要指标，对掌握和控制构件演化前后的影响范围和强度有着直观的指导作用和很强的现实意义。

在本文的实验中，将类拟为构件，类关系拟为SA的模型中的无权有向边，其对应关系如表1。

表1 SA的模型关系

2 演化环境下的构件重要性度量

演化是所有软件系统都必经的活动，系统的整体结构趋于复杂、构件数量庞大，寻找出结构中的重要构件。为软件演化的检测和可控提供依据的同时，也是掌握和评价演化的一个重要方面，对软件的演化工作显得尤为重要。

2.1 构件重要性度量方法

对构件的重要性进行度量，主要有5个步骤，包括：

(1) 获取构件和构件间关联。将源代码中的类作为一个构件，通过扫描源代码，得到构件名称标识和构件之间的关系。

(2) 将构件和构件之间的关系数据进行处理，并映射为邻接矩阵。若构件的个数为n，将构件之间的关系映射为n维的邻接矩阵M，并默认M11，M22，…，Mnn的值为0，有特殊自调用的构件除外；例如，若构件1对构件2有依赖关系，构件2对构件1没有依赖关系，则M12的值为1，M21的值为0。

(3) 以邻接矩阵M为基础，计算出每个节点的构件请求依赖、构件服务依赖和构件的总依赖。

(4) 计算每个节点的节点介数。计算全图的最短路径，得到全图的最短路径总数目以及各个节点的经过该节点的最短路径数目后，根据式(1)计算每个构件的节点介数。根据节点介数的大小度量出在SA中的重要构件。

(5) 分别计算构件的请求依赖、构件的服务依赖、构件的总依赖与节点介数的Pearson相关系数。根据式(2)分别进行计算，并研究与分析和节点介数最相关的因素。

在本文中使用的Pearson相关系数的计算公式为：

(2)

在Pearson相关系数的定义中：相关系数绝对值在[0.8,1.0]，是极强相关；相关系数绝对值在[0.6,0.8]，是强相关；相关系数绝对值在[0.4,0.6]，是中等程度相关；相关系数绝对值在[0.2,0.4]，是弱相关；绝对值在[0,0.2]，是极弱相关或无相关。

使用Pearson相关系数来计算节点构件的请求依赖、构件的服务依赖、构件的总依赖和节点介数的相关性。在实验中，节点介数、构件的请求依赖、构件的服务依赖、构件的总依赖之间，两个变量的观测值是成对的，每对观测值之间相互独立，且他们的标准差均不为0，那么Pearson相关系数就是有定义的。

2.2 算 法

算法1获取SA模型的邻接矩阵算法。

输入：构件名称标识链表Name和构件间交互关系链表Connection。

输出：SA的模型的邻接矩阵Matrix。

初始化：二维数组Matrix用于存储SA模型的邻接矩阵，Matrix的行列长度均等同于链表Name的长度。

Begin

For i ← 0 to length[Connection] do

row ← get index of component name 1 from Connection[i] in Name

column ← get index of component name 2 from Connection[i] in Name

Matirx[row][column] = 1

EndFor

End

例如在实验一中用Eclipse 3.0获得的部分矩阵如下：

得到SA模型的邻接矩阵之后便可以计算出每个构件的请求依赖和服务依赖。在计算构件的请求依赖时，Matrix[i][]这一列中有多少个1，最后累积相加所得的结果便是节点vi所对应的构件的请求依赖；同样地，在计算构件的服务依赖时，Matrix[][j]这一行中有多少个1，最后累积相加所得的结果便是节点vj所对应的构件的服务依赖。每个构件的请求依赖和服务依赖相加就得到节点的总依赖。

算法2SA有向图模型的全图最短路径算法。

输入：SA模型的邻接矩阵Matrix。

输出：SA模型的全图最短路径Pathes。

初始化：链表Pathes用于存储图中所有的最短路径。

Begin

For i ← 1 to length[Matrix] do

For j ← 1 to length[Matrix[i]] do

shortest(i,j) = minWeight(i,j)

EndFor

EndFor

For k ← 1 to length[Matrix] do

For i ← 1 to length[Matrix] do

For j ← 1 to length[Matrix] do

If (shortest(i,k)+shortest(k,j) < shortest(i,j)) Then

shortest(i,j) = shortest(i,k)+shortest(k,j)

EndIf

EndFor

EndFor

EndFor

End

算法3SA模型的节点介数计算算法。

输入：SA模型的全图最短路径Pathes，构件名称标识链表Name。

输出：SA模型的各个构件的节点介数。

初始化：链表Betweenness用于存储SA模型的节点介数，链表Betweenness的长度等同于构件名称标识链表Name的长度。

Begin

For i ← 0 to length[Name] do

k = 0

For j ← 0 to length[Pathes] do

If Name[i] exists in Pathes[j]

k ← k + 1

Else continue

EndIf

EndFor

Betweenness[i] = k/length[Pathes]

EndFor

End

3 实验分析

本文选取的开源软件近一百种，包括各种功能，例如软件开发平台、编程语言源代码包、开源专业性软件等，可按照节点的数量分为三类：节点数小于50的小规模软件，节点数在50至200的中规模软件，节点数大于200的大规模软件。

结果发现，本文的方法是切实有效的，且与软件的规模和功能种类无关，其构件的总依赖和节点介数的走向趋势总是相符的。但是节点介数的体现与软件的结构设计有关，在那些拥有良好设计、体系结构的软件中，所得实验结果最为理想，不仅其构件的总依赖和节点介数的变化总是趋于同步，而且构件之间的节点介数的区别更加明显；反之，没有良好的体系结构支撑的软件系统中，构件之间的节点介数几近一致，导致构件之间的度量困难。

由于篇幅的限制，最后选取属于大规模软件的Eclipse 3.0和属于中规模的Jabref的源码作为典型的两个实验示例进行分析。

3.1 实验一

使用Eclipse 3.0的源代码作为实验数据。

图1为Eclipse 3.0的构件的请求依赖、构件的服务依赖的分布曲线和构件的总依赖、节点介数的百分比折线图。由于节点介数的取值在[-1,1]之间，范围变化小，而总依赖的值远大于节点介数的值，为了更清楚地看到总依赖和节点介数的关系和走向趋势，采用百分比折线图进行分析。在图中Y轴表示了构件的请求依赖、构件的服务依赖的大小，X轴代表节点。

图1 Eclipse 3.0的分布折线图

通过观察折线图的走向，不难发现构件的请求依赖和构件的服务依赖之间是没有明显的相关关系，即构件的请求依赖和构件的服务依赖之间没有呈现规律的对应关系，请求依赖高的构件可能服务依赖高也可能服务依赖低。而构件的总依赖和节点介数的起伏走向基本是一致的，意味着总依赖高的构件节点介数也高。构件的节点介数越高，构件在软件体系结构中的功能、位置也就越重要。

采用式(2)计算度和节点介数的相关性，用Pearson相关系数来判断度和节点介数之间是否存在如折线图所呈现出的相关关系。表2为Eclipse 3.0相关性分析。

表2 Eclipse3.0相关性分析

由Pearson相关系数值的计算结果可以看出，折线图所展示出的趋势是正确的。构件的总依赖与节点介数为强正相关，构件的总依赖越大节点介数也越大，构件的服务依赖和请求依赖分别与节点介数为中等程度正相关，而请求依赖与服务依赖之间是极弱负相关或无相关。

3.2 实验二

使用Jabref的源代码作为实验数据。

图2为Jabref的构件的请求依赖、构件的服务依赖的分布曲线和构件的总依赖、节点介数的百分比折线图。Y轴表示了构件的请求依赖和构件的服务依赖的大小，X轴代表节点。

图2 Jabref的分布折线图

在Jabref的折线图中，构件的请求依赖和服务依赖没有呈现规律的相关趋势，而构件的总依赖和节点介数的起伏几乎重叠，这表明，在Jabref中，总依赖高的构件其节点介数也高。

表3 Jabref相关性分析

Jabref的相关性分析再次证明折线图展示的相关趋势是正确的。构件的请求依赖和服务依赖之间是极弱正相关或不相关，构件的请求依赖、服务依赖分别与节点介数强正相关，总依赖与节点介数极强正相关，节点介数随总依赖的增大而增大。

通过计算Eclipse 3.0和Jabref的构件的服务依赖和请求依赖的Pearson相关系数，可见构件的服务依赖和请求依赖的分布是没有规律的，它们之间不存在相关性。

根据Pearson相关系数分析可知，在软件体系结构中，构件的总依赖和节点介数均呈现极强正相关，而构件的服务依赖与节点介数的Pearson相关系数和构件的请求依赖与节点介数的Pearson相关系数的趋势变化并不稳定。由节点介数的定义可知，一个构件的节点介数与该构件的服务依赖、请求依赖和总依赖有着直接的关系，当一个构件的总依赖越大，那么这个构件在整个软件体系结构中的地位和重要程度也就越高，相应的节点介数越高；反之，若一个构件的总依赖越低，甚至没有，那么这个构件在整个软件体系结构中的地位和重要程度越低，节点介数也就越低。

构件的总依赖与其变化最密切相关，通过节点介数来判断构件在整个软件体系结构中的地位和重要程度的时候，构件的总依赖也是一个关键的判断因素。

4 结 语

实验证明使用节点介数度量软件演化环境下的构件的重要性，是有效的，补充了传统的度量方法在掌握软件体系结构宏观特性方面的不足。

在整个软件体系结构中，构件的请求依赖高的节点往往独立性较差，对底层构件或其他基础构件的依赖较强，耦合度高，功能比较复杂；构件的服务依赖高的节点通常内聚度高，结构稳定并且功能单一。

通过对构件的总依赖和节点介数的计算，可以清晰地度量构件在整个软件体系结构中的重要性。在软件体系结构演化的时候，可以更好地把握这些重要的节点的演化过程，降低演化风险，有助于监控管理那些在演化活动中比较难控制的活动和构件。软件体系结构中构件的请求依赖和服务依赖没有规律的相关关系，而构件的总依赖和节点介数之间通常表现为强正相关或极强正相关，即总依赖高的构件节点介数也高。

总依赖与节点介数极强正相关，为构件的重要性度量指明了另一个研究方向，尤其是在一个庞大的软件体系结构中时，如何在计算时对源代码中数量众多的节点进行降维，从而更加快速地计算构件的总依赖是下一步的研究重点。

[1] Bianchi A,Caivano D,Marengo V,et al.Iterative reengineering of legacy systems[J].IEEE Transactions on Software Engineering,2003,29(3):225-241.

[2] Zeng J,Sun H L,Liu X D,et al.Dynamic Evolution Mechanism for Trustworthy Software Based on Service Composition[J].Journal of Software,2010,21(2):261-276.

[3] Song W,Ma X X,Lu J.Instance migration in dynamic evolution of web service compositions[J].Chinese Journal of Computers,2009,32(9):1816-1831.

[4] Huang G,Mei H,Yang F Q.Runtime recovery and manipulation of software architecture of component-based systems[J].Automated Software Engineering,2006,13(2):257-281.

[5] Wilfredo T.Software Fault Tolerance:A Tutorial[J].Pomales,2000,1(2):220-232.

[6] Liu Y,Zhang S K,Wang L F,et al.Component-Based Software Frameworks and Role Extension Form[J].Journal of Software,2003,14(8).

[7] Brunet J,Murphy G C,Serey D,et al.Five Years of Software Architecture Checking:A Case Study of Eclipse[J].IEEE Software,2015,32(5):1-1.

[8] Bohner S A.Impact analysis in the software change process:a year 2000 perspective[C]//International Conference on Software Maintenance.IEEE Computer Society,1996:42-51.

[9] Shaw M,Garlan D.Software architecture:perspectives on an emerging discipline[J].Prentice Hall,2010,24(1):129-132.

[10] Ambriola V,Tortora G.Advances in Software Engineering and Knowledge Engineering[M].World Scientific,1993.

[11] Bohner S A.Software change impacts-an evolving perspective[C]//International Conference on Software Maintenance.IEEE Computer Society,2002:263.

[12] Drange P G,Dregi M,Hof P V.On the Computational Complexity of Vertex Integrity and Component Order Connectivity[J].Algorithmica,2014,8889:285-297.

[13] Valverde S,Cancho R F I,Sole R V.Scale-free Networks from Optimal Design[J].Europhysics Letters,2002,60(4):512-517.

[14] Eiben A E,Smith J.From evolutionary computation to the evolution of things[J].Nature,2015,521(7553):476-482.

[15] Myers C R.Software systems as complex networks:structure,function,and evolvability of software collaboration graphs[J].Physical Review E,2003,68(4 Pt 2):352-375.

[16] de Moura A P,Lai Y C,Motter A E.Signatures of small-world and scale-free properties in large computer programs[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(2):017102.

[17] 王映辉,王立福.软件体系结构演化模型[J].电子学报,2005,33(8):1381-1386.

[18] 张朝昆,崔勇,唐翯祎,等.软件定义网络(SDN)研究进展[J].软件学报,2015,26(1):62-81.

[19] 汪北阳,吕金虎.复杂软件系统的软件网络结点影响分析[J].软件学报,2013,24(12):2814-2829.

AMETHODOFCOMPONENTIMPORTANCEMEASUREMENTBASEDONNODEBETWEENNESSINSOFTWAREEVOLUTIONENVIRONMENT

Cheng Lei1Lin Ying1,2Li Tong2*Wang Xiaofang1Zheng Jiaojiao1Li Xiang1

1(CollegeofSoftware,YunnanUniversity,Kunming650091,Yunnan,China)2(KeyLaboratoryforSoftwareEngineeringofYunnanProvince,Kunming650091,Yunnan,China)

In software evolution, the importance measure of components can provide the basis for the control and monitoring of software evolution. With software architecture as blueprint and support, this paper proposes a software architecture directed graph model, and introduces node betweenness to measure the importance of components. And the component request dependence and service dependence are analyzed and studied. By using the Pearson correlation coefficient analysis, the factors which are most related to the node betweenness are found out. Through the experiment of a large number of open source software source code, the experimental results show that it is effective to use node betweenness to measure the importance of component, and the sum of component request dependence and the component service dependence is the most correlative factor to betweenness. This also points to another research direction for measuring the importance of components by using dependencies.

Software architecture Software evolution Component Directed graph Node betweenness

TP311

A

10.3969/j.issn.1000-386x.2017.10.005

2016-12-12。国家自然科学基金项目(61379032)。成蕾，硕士，主研领域：软件工程理论与方法。林英，副教授。李彤，教授。王晓芳，硕士。郑交交，硕士。李响，硕士。