面向對象軟件系統演化模型

馬 健,樊建平,劉 峰,李紅輝

(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.