面向对象软件系统演化模型

马 健,樊建平,刘 峰,李红辉

(1.北京交通大学 计算机与信息技术学院,北京100044;2.中国科学院 深圳先进技术研究院,广东 深圳518055)

0 引 言

自然界和人类社会中的大量系统都可以通过复杂网络加以描述[1]。面向对象软件系统也可以转化为人工复杂网络。这方面的研究有:Bhattacharya等[2]分析了软件源代码,将函数抽象为节点,调用关系抽象为有向边构造图形,生成软件拓扑结构。Chong等[3]不仅构造了软件图形,还为边分配权重进行了扩展。Chaikalis等[4]将类抽象为节点,将类之间的(调用、关联、依赖)关系抽象为有向边。Turnu等[5]分析了Java、Eclipse和Netbeans大型面向对象软件系统的源代码,研究了源代码中的类和它们之间的依赖关系和整个发行版及其子项目的复杂性,结果表明,这样的系统可以被看作是复杂软件网络。

网络演化是网络的结构发生变化,网络演化的模型有:Barabási等[6]提出了BA无标度网络模型,模型基于增量增长和线性优先关系两种机制;Valverde等[7]提出了基于节点复制和边重新连接的模型;Myers[8]提出了基于重构过程的模型。Dorogovtsev等[9]提出了依赖现有节点的度数和年龄的模型;Zheng等[10]也提出了一个基于节点的度数和年龄的模型(Degree and age dependent adjustable evolution,DAAE);Li等[11]提出了一种模拟软件网络演化的模块连接机制,使用模块化连接代替在前面的模型中采用的单节点连接,因为将面向对象系统模块化与现实世界软件本质上更加相似。张锡哲等[12]提出一种新颖的基于复杂网络的服务软件行为演化模型,在大量真实服务数据的基础上,考察了面向服务的软件系统的演化仿真并分析其拓扑特征,与传统软件所构成的软件网络进行了对比,指出面向服务的软件系统特有的特征规律。还有一些模型也从不同的角度模拟了软件网络演化这一过程[13]。

本文提出了一种基于局域事件(Local events)的软件网络演化模型,模型以面向对象软件系统为研究对象,分析软件系统网络的度分布,模拟软件网络的演化过程。

1 基本概念

1.1 软件网络

本文中从软件的源代码中提取组成系统的类抽象为节点,它们之间的关系抽象为边,例如:源类引用目标类对象,将目标类对象作为局部变量或者源类方法的参数或返回类型是目标类。软件系统转化为由许多相互连接的类组成的类图。这样,复杂的软件系统就用软件类图表示,研究结论表明像大量人工网络那样,软件类图也具有“小世界”和“无标度”的特性[14]。我们将类图看作软件网络,也就是将面向对象软件系统也可以转化为人工网络。

图1为Junit软件类图。将类抽象为节点,类之间的关系抽象为边,Junit软件类图可以看作是错综复杂的软件网络。

图1 Junit软件类图Fig.1 Junit class diagrams

度分布是网络统计性质中最重要的性质,也称为网络节点的度分布,分布情况可用分布函数P(k)表示,P(k)表示一个随机选定的节点的度恰好为k的概率。网络中一个节点直接连接的邻接点的多少通常反映了它在网络中的重要程度。例如万维网、电影演员网、论文引用关系网等,新演员总是愿意与有影响力的演员合作,网页链接总是更多地指向那些有很多连接指向它的网页,一篇论文被引用的次数越多,被新论文引用的概率就越大。

1.2 BA无标度网络模型(Scale-free networks)

1999年,Barabási等[15]提出了无标度网络(Scale-free networks)模型,具有幂律分布的网络被称为无标度网络,其度分布具有胖尾现象,实验结果表明许多现实的大规模网络的度分布服从幂律分布。

BA网络包括两个特性:

(1)增长。初始时具有少量m0个节点,每个时间步增加一个新节点,连接到m m≤m0()个已存在于系统中的旧节点上。

(2)优先连接。新节点连接到旧节点的概率与旧节点的度成正比,N表示网络节点总数。

经过t时间间隔后,网络演化为一个有N＝m0＋mt个节点、mt条边的网络,达到稳定的状态。

无标度网络模型是节点的度连接没有明显的特征长度,因此也称为无标度网络。该模型描述了网络具有演化生长和节点依附偏好的特性,即精确或近似地遵循幂函数的度分布。

2 基于局域事件网络演化模型

软件最初的版本一般都相对简单,软件内部的复杂程度也相对一般,但随着时间的推移,为满足新的需求或加入新的功能会对程序进行修改,软件的复杂程度也会不断地增加。在真实的软件系统中,新增类加入到软件中与软件中已存在的类发生关系,已存在的类之间也会改变现有的各种关系或删除已存在的类及其关系。局域事件演化网络模型模拟了上述情形,例如:带有新边的新节点与现有节点之间的连接,在网络中现有节点间添加新边,现有边的删除和重新连接。在BA模型的基础上,本文提出了基于局域事件网络演化模型模拟真实软件网络的演化过程。

(1)初始网络:具有少量m0个节点。

(2)网络演化:

①以概率p1增加一个新节点,新节点连接m条新边,新节点按择优概率式(1)选取节点i与新增节点产生一条边,这个过程重复m次。

②以概率p2在网络已有节点之间增添m条边,新增的边一端按择优概率公式(1)∏(k i)选取节点i,另一个节点也按择优概率公式(1)∏(k j)选取节点j。

③以概率p3在网络已有节点之间删除m条边。

综合上述3种情况,将式(3)(4)(5)相加可得:

式中:N＝m0＋mt;∑jk j＝2mt－m;对于较大的t、m0和m可以忽略,初始条件t i时刻增加的连接数为m,k i(t i)＝m。

对上述微分方程(6)求解得:

网络中所有的节点都以同样的幂律增长,γ称为动力学指数。p1＋p2＋p3＝1。

随机变量t i服从(0,t)区间上的均匀分布,有:;

由式(7)可以看出,基于局域事件网络演化模型也是无标度模型。

3 实验分析

3.1 实验数据

Dependency Finder分析工具可以实现从Java字节码文件中抽取面向对象软件类关系和度量。在本实验中使用Dependency Finder抽取所选实验对象类的之间关系进行分析。

为验证本文提出的基于局域事件的无标度网络模型,选取了6款Java面向对象开源软件,表1为Azureus5.7.1.0,structs1.3.10,tomcat9.0.0,ant1.9.7,itext5.5.9,jedit4.3的参数,使用Mablab对生成的幂律函数曲线进行分析拟合。

表1 软件相关参数Table 1 Software related parameters

3.2 实验结果分析

图2为在双对数坐标中的参数分析,是提出的模型式(7)的度分布曲线。对变量分别取对数可以得到度分布曲线是一条负斜率的直线,所以,得到模型为无标度网络模型。

图2 模型不同参数度分布图Fig.2 Different parameter of model degree distribution

本文分析了6个面向对象软件系统,以Azureus5.7.1.0为例,图3(a)中的‘∗’为Azureus真实网络的度分布,‘＋’为BA无标度网络模型的度分布曲线,‘·’为基于局域事件(LE)的无标度网络的度分布曲线。可以看出,在图3(a)的双对数坐标中,Azureus真实网络度分布具有胖尾现象。说明度数大的节点占少数,大部分的节点的度数较小,度数较大的少数节点对应于软件系统中的通用类,这些类被程序员经常使用。上述结果表明,面向对象软件系统的度分布遵循幂律分布。

这种基于局域网络演化机制的模型适合描述面向对象软件系统,软件网络经过长时间演化后,导致网络中大多数节点拥有少数连接的边,而极少数节点,拥有大量连接。结果导致“富者越富”和中枢点现象。这些软件网络的度分布都服从幂律分布。

图3 软件系统演化模型的仿真结果Fig.3 Simulation results of software systems

采用目前通用的验证度指数的方法,根据初步统计,对软件系统进行度指数分析。所有软件网络拟合后曲线的斜率均在(2,3)区间,结论与建模分析得到的结论一致。显然,本文提出的模型更能较好地模拟真实网络的度分布情况,模拟Azureus仿真网络的参数为m＝10,p1＝0.8,p2＝0.1;模拟structs仿真网络的参数为m＝10,p1＝0.8,p2＝0.06;其他模拟仿真网络的参数如表2所示,与实际系统的演化度分布情况基本一致。

表2 模拟参数Table 2 Simulation parameters

综上所述,软件系统经过长时间演化后,导致网络中大多数节点拥有少数连接的边,而极少数节点,拥有大量连接。即软件大多数节点较少与其他节点产生依赖(调用、继承、消息等)关系,极少节点与大量其他节点具有依赖关系。例如:有的工具类被许多其他类调用,面向对象软件网络具有复杂网络特性,即度分布服从幂律分布。

4 结束语

本文选取了6款开源面向对象软件系统为研究对象,对BA无标度网络模型进行改进,增加了添加节点、添加边、删除边和边的重连等局域事件,模拟软件网络的演化过程。实验结果表明,软件系统的度分布服从衰减幂律分布和无标度分布。标度指数在2和3之间,也就是说,大规模软件系统的度分布服从衰减幂律分布的无标度分布,这种现象说明通用类在软件系统的成长过程中发挥着重要作用,其中代码重用引起了“富者越富”现象的产生。软件演化的过程中还伴随着节点和边的添加、移除和边的重连现象,为了描述软件系统的演化过程,构建了一个软件系统演化模型,模拟软件网络演化增长,就是文中提出的基于局域事件的网络演化模型。实验结果表明,该模型的度分布与实际软件网络基本相符,提出的模型能较好地描述真实软件的演化增长情况,计算得到的幂律指数与真实软件的度分布基本一致。数据仿真验证了该模型的有效性。

[1]郭玉泉,李雄飞.复杂网络社区的分形聚类检测方法[J].吉林大学学报:工学版,2016,46(5):1633-1638.Guo Yu-quan,Li Xiong-fei.Fractal clustering method for uncovering community of complex network[J].Journal of Jinlin University(Engineering and Technology Edition),2016,46(5):1633-1638.

[2]Bhattacharya P,Iliofotou M,Neamtiu I,et al.Graph-based analysis and prediction for software evolution[C]∥Proceedings of the 34th International Conference on Software Engineering(ICSE).Zuricah:ACM,2012:419-429.

[3]Chong C Y,Lee S P.Analyzing maintainability and reliability of object-oriented software using weighted complex network[J].Journal of Systems and Software,2015,110:28-53.

[4]Chaikalis T,Chatzigeorgiou A.Forecasting java software evolution trends employing network mod-els[J].IEEE Transactions on Software Engineering,2015,41(6):582-602.

[5]Turnu I,Concas G,Marchesi M,et al.The fractal dimension of software networks as a global quality metric[J].Information Sciences,2013,245(10):290-303.

[6]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[7]alverde S,SoléR V.Network motifs in computational graphs:a case study in software architecture[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2005,72(2):026107.

[8]Myers C R.Software systems as complex networks:structure,function,and evolvability of software collaboration graphs[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2003,68(2):046116.

[9]Dorogovtsev S N,Mendes J F F.Evolution of reference networks with aging[J].Physical Review E Statistical Physics,Plasmas,Fluids,and Related Interdisciplinary Topics,2000,62(2):1842-1845.

[10]Zheng X L,Zeng D,Li H,et al.Analyzing opensource software systems as complex networks[J].Physica A Statistical Mechanics and Its Applications,2008,387(24):6190-6200.

[11]Li H,Zhao H,Cai W,et al.A modular attachment mechanism for software network evolution[J].Physica A Statistical Mechanics and Its Applications,2013,392(9):2025-2037.

[12]张锡哲,吕天阳,张斌.基于服务交互行为的复杂服务协同网络建模[J].软件学报,2016,27(2):231-246.Zhang Xi-zhe,LüTian-yang,Zhang Bin.Modeling complex collaboration network for service-oriented software based on execution behaviors[J].Journal of Software,2016,27(2):231-246.

[13]Dabrowski R,Stencel K,Timoszuk G.Software is a directed multigraph[C]∥Proceedings of the 5th European conference on Software architecture.Essen:Spring,2011:360-369.

[14]Valverde S,Cancho R F I,Sole R V.Scale-free networks from optimal design[J].Europhysics Letters,2002,60(4):512-517.

[15]Barabási A L,Alert R,Jeong H.Mean-field theory for scale-free random networks[J].Physica A Statistical Mechanics and Its Applications,1999,272(1):173-187.