一種圖編輯距離的軟件體系結構變化性度量方法及應用研究

鐘林輝，夏 鯨，彭 云，謝 冰

1(江西師范大學 計算機信息工程學院，南昌 330022) 2(北京大學 軟件工程研究所，北京 100008)

1 引 言

軟件體系結構作為一類重要的軟件制品，其變化會對軟件的開發(fā)和維護產生較大的影響[1].通過比較不同版本軟件體系結構的差異性，不僅可以判斷軟件體系結構變化是否與軟件需求一致，而且可以度量、分析和預測軟件演化的趨勢.然而，目前已有的軟件體系結構變化性度量方法(例如MoJoFM[2]和a2a[3])只考慮經過劃分得到的“簇”中軟件實體的變化，未考慮“簇”之間關系的變化；而有的方法(例如基于圖核(Graph Kernel)理論的方法[4]，基于圖編輯或者樹編輯距離的軟件差異性比較方法[5，6])雖然考慮了軟件實體之間的結構特征，但實際上針對的是面向對象模型或軟件體系結構的實現(xiàn)，而非軟件體系結構的設計.

因此，為了克服目前軟件體系結構變化性度量方法的不足，本文在軟件體系結構設計層次，既考慮構件本身的變化，也考慮軟件體系結構在結構上的變化，提出了以軟件體系結構為中心的軟件演化分析框架，以及針對軟件體系結構規(guī)約、基于圖編輯距離的變化性度量方法，并基于上述方法對若干開源軟件體系結構的演化歷史進行了度量分析.本文組織安排如下：首先是相關研究的介紹，隨后是以軟件體系結構為中心的構件化軟件演化分析框架，在第4及第5節(jié)分別介紹了軟件體系結構變化性度量具體方案，以及在開源軟件體系結構演化分析上的應用；第6節(jié)是工具支持，最后是結束語.

2 相關研究

本文相關研究涉及到跨版本的軟件變化性研究，主要包括變化性建模以及變化性度量.

2.1 變化性建模

變化性建模是采用靜態(tài)或者動態(tài)的方法將不同軟件版本的差異性用邏輯、規(guī)則和契約等形式加以描述.

①采用靜態(tài)方法：文獻[7]提出了用謂詞邏輯和本體表示程序不同版本抽象語法樹的變化.文獻[8]采用符號執(zhí)行和代碼總結的策略，能自動生成程序的差異性描述文檔.文獻[9]提出了用變化規(guī)則表示不同版本之間結構變化的策略.

②采用動態(tài)方法：文獻[10]提出了變化契約的概念以及推理框架，通過捕獲程序在運行時刻方法調用時進入、退出和異常等情況下的數(shù)據，進而歸納出變化契約.另外，國內研究者對軟件的變化也進行了研究，比較典型的是文獻[29]中提出了一種結合關鍵字檢索和啟發(fā)式規(guī)則，實現(xiàn)多層次演化信息之間追蹤關系逆向的方法；以及文獻[11]通過對代碼變化進行分組和聚類以發(fā)現(xiàn)變化的軌跡模式.

2.2 變化性度量

本文的變化性度量包括面向對象的程序或模型的變化性度量和軟件體系結構的變化性度量：

①面向對象的程序或模型的變化性度量：例如，JDiff工具將程序抽象為擴展的控制流圖，通過提出的差異性算法比較不同版本在方法上的差異性[6]，UMLDiff工具通過計算不同UML圖之間的編輯距離代價判斷面向對象模型的差異性[5].文獻[12]通過計算不同軟件版本所包含的類在大小、內聚和耦合等屬性上數(shù)值大小變化，判斷面向對象軟件的演化穩(wěn)定性.不同于計算語法樹或者模型之間的變換來度量變化，在文獻[13，14]中提出的語義差異性操作能識別不同類圖、活動圖等在語義上的差別.在文獻[15-17]中則利用Kolmogorov復雜性的信息度量概念，計算不同軟件版本的差異性.文獻[30]提出采用層次分析法，試圖構建功能模塊、語法和文本等變化同演化率之間的函數(shù)關系.文獻[18]通過度量面向對象程序在包、結構簇、語義簇三個視圖上的差異性，判斷軟件設計質量是否存在偏差.文獻[4]將面向對象風格的軟件體系結構表示為標簽圖，基于隨機行走算法獲得的路徑作為軟件體系結構的特征向量并利用圖核理論度量軟件的差異性.

②軟件體系結構的變化性度量：例如文獻[19]基于軟件體系結構視圖復雜性度量和耦合性度量，分析了軟件變化對軟件體系結構的影響.文獻[31]為了研究構件變化所引發(fā)的波動效應，提出了利用構件組合運算度量軟件體系結構可演化性的方法.MoJoFM[2]將軟件劃分為若干簇，通過計算簇內節(jié)點的移動和簇的合并操作判斷兩個不同劃分的變化程度.文獻[20]將軟件體系結構演化過程分解為若干原子操作，通過計算原子操作在多個視圖上的質量屬性的變化達到分析軟件演化趨勢的目的.文獻[21]提出了體系結構債務(architectural debts)的概念，用以定量分析體系結構層次的文件變化同軟件維護代價之間的關系.文獻[22]則研究了跨體系結構模塊和體系結構模塊內部的協(xié)同變化，對軟件質量的不同影響.有的研究采用多種視圖相結合的方法研究軟件體系結構的變化性度量，例如文獻[3，23]提出了一種多層次軟件體系結構度量方案，其中度量公式cvg反應軟件體系結構在構件實現(xiàn)層次的變化，度量公式a2a反應軟件體系結構在系統(tǒng)層次的變化.但是，這些方法建立在MoJoFM度量的基礎上，沒有考慮到節(jié)點之間關系，而僅僅考慮簇的換名和增加，節(jié)點的換名、增加和移動等5個操作，導致計算結果不夠準確.

3 以軟件體系結構為中心的軟件演化分析框架

為了有效地支持構件化軟件的開發(fā)和演化，在我們的早期研究中提出了擴充構件描述語言(xCDL)支持基于構件的系統(tǒng)組裝與演化的策略[32]，不僅可以有效的支持基于構件的系統(tǒng)構造定義，而且可以支持系統(tǒng)的演化以及系統(tǒng)的部署.其中的關鍵技術包括擴充了CDL以支持對構件及軟件體系結構本身的演化的表示和跟蹤，通過基于構件的軟件配置管理模型CBSCM[33]，實現(xiàn)對構件化軟件演化數(shù)據的存儲.基于上述思想和關鍵技術，本文進一步提出了以軟件體系結構為中心的構件化軟件演化分析框架，如圖1所示.

圖1 以SA為中心的軟件演化分析框架Fig.1 Framework of architecture-centric software evolution analysis

整個框架分為3個部分，包括以軟件體系結構為中心的正向工程、以軟件體系結構為中心的逆向工程、以及軟件演化分析過程.其中，以軟件體系結構為中心的正向工程所產生的軟件制品例如每個版本的軟件體系結構描述、軟件體系結構的實現(xiàn)等均存儲在基于構件的軟件配置管理系統(tǒng)中；而以軟件體系結構為中心的逆向工程通過現(xiàn)有的逆向工程工具，對遺留系統(tǒng)的演化歷史進行軟件體系結構層次的重建，構造出帶版本信息的軟件體系結構描述，并將其存儲在基于構件的軟件配置管理系統(tǒng)中.軟件演化分析則通過提取基于構件的軟件配置管理系統(tǒng)中存儲的帶版本信息的軟件體系結構描述，度量相鄰版本之間的變化性，并實現(xiàn)對不同軟件系統(tǒng)的演化變化性進行度量.

4 軟件體系結構變化性度量

4.1 軟件體系結構的屬性圖

軟件體系結構可以用多種方法加以描述，例如軟件體系結構描述語言或者圖.為了實現(xiàn)基于圖的軟件體系結構變化性的度量，本文通過對軟件體系結構描述語言進行解析，構造出其對應的屬性圖，屬性圖中刻畫了軟件體系結構元素之間的關系，相關定義如下：

定義1.軟件體系結構屬性圖：G=是一個4元組，其中，V表示節(jié)點集合，E表示邊集合，LV表示節(jié)點的標簽映射函數(shù)，LE表示邊的標簽映射函數(shù).在軟件體系結構的語境下，節(jié)點集合、邊的集合、節(jié)點的標簽函數(shù)及邊的標簽函數(shù)定義如下.

定義2.節(jié)點集合V：表示軟件體系結構中的構件(包括復合構件與原子構件)、構件實例、每個構件對外提供的方法及實例、對外所需的方法及實例，以及版本信息例如版本號；其中，方法的實例是為了區(qū)分具有相同類型的不同構件實例中的方法，例如圖2(b)中的節(jié)點S2是方法Semantize的實例.

定義3.邊的集合E：表示節(jié)點之間的關系，根據構件、方法、版本之間的關系，可以區(qū)分為以下幾種關系：方法之間的連接關系、方法之間的映射關系、復合構件和原子構件之間的組成關系，構件與版本之間的版本關系，以及構件與其實例之間的實例關系，構件和方法之間的對外所需的功能和對外提供的功能.

定義4.節(jié)點的標簽函數(shù)LV：LV定義為LV：V→String，即節(jié)點到字符串的映射.字符串可以表示構件名稱、方法名稱、版本號等.

定義5.邊的標簽函數(shù)LE：將上述邊的類型通過函數(shù)映射到具體的字符串，即：LE：E→{"connectTo"，"mapTo"，"composeOf"，"versionOf"，"instanceOf"，"requires"，"provides"}其中connectTo表示構件實例之間方法的連接關系，mapTo表示復合構件與成員構件之間方法的映射關系，composeOf表示復合構件與成員構件的包含關系，versionOf表示構件與版本的版本關系，instanceOf表示構件與構件實例的實例關系，requires和provides表示構件與方法需要和提供的關系.

例如，考慮一個編譯系統(tǒng)的概念結構如圖2(a)所示，相應的用xCDL描述的軟件體系結構如下：

component Parser < Version = 1.0 > is

provides：

function Initialize()；

function FileName() return String；

requires：

function Semantize(Tree)；

function Generate(Tree)；

end Parser；

component Semanticizer < Version = 1.2 > is

provides：

function Semantize(Tree)；

function Incremental_Semantize(Context：Tree；

Addition：Tree)；

requires：

function FileName() return String；

end Semanticizer；

component Code_Generator < Version = 1.2 > is

provides：

function Generate(Tree)；

requires：

function Initialize_Parser()；

function Semantize(Context：Tree；Addition：Tree)；

end Code_Generator；

component Complier < Version=2.1>

PreLink：Complier < Version=1.8 >

Reference：

Parser，Semanticizer，Code_Generator；

Instance：

P：Parser < Version = 1.0 >；

S：Semanticizer < Version = 1.2 >；

G：Code_Generator < Version = 1.2 >

Connection：

P.Semantize to S.Semantize；

P.Generate to G.Generate；

S.FileName to P.FileName；

G.Initialize_Parser to P.Initialize；

G.Semantize to S.Incremental_Semantize；

End Complier

其經過解析后得到的軟件體系結構屬性圖，如圖2(b)所示.

圖2 例子：編譯系統(tǒng)概念圖及其體系結構的屬性圖表示Fig.2 An example：compiler and its attribute-graph presentation

4.2 基于圖編輯距離的變化性度量

基于上述軟件體系結構屬性圖，本文采用圖編輯距離的方法度量軟件體系結構的變化性.圖的編輯距離指的是使用節(jié)點的替換、增加和剔除操作，以及邊的替換、增加和剔除操作，將圖g1轉換為圖g2所需要的最小代價[24,25].存在多種計算圖編輯距離的算法，其中二分圖的編輯距離算法將圖的編輯距離看作是二次分配問題，能有效計算圖的編輯距離[26].

為了使用二分圖編輯距離算法，需要定義節(jié)點和邊關于插入、刪除及替換操作的編輯代價，同時需要滿足圖編輯距離的三角不等式關系.在本文軟件體系結構屬性圖中，節(jié)點的標簽對應的是軟件體系結構描述語言中元素的標識符，例如構件的名稱、接口的名稱、版本號(以字符串形式表示，例如"2.31")等；邊的標簽對應的是枚舉類型.因此，節(jié)點之間和邊之間的編輯代價定義如下：

定義6.節(jié)點之間的編輯代價Cij：Cij區(qū)分為替換代價、刪除代價以及插入代價3種.即c(Vi→Vj)=stringEditDistance(LV(Vi)，LV(Vj))；c(Vi→ε)=c(ε→Vi)=strlen(Vi)，其中，LV(Vi)，LV(Vj)分別表示節(jié)點Vi和Vj的標簽，即節(jié)點的替換操作代價c(Vi→Vj)為字符串LV(Vi)和LV(Vj)之間的編輯距離.插入操作代價c(ε→Vi)和刪除編輯代價c(Vi→ε)為字符串LV(Vi)的長度.一般，取c(Vi→Vj) =min{(c(Vi→ε) +c(ε→Vj)，c(Vi→Vj)}可以滿足圖編輯距離所需的三角不等式關系.顯然，在以字符串的編輯距離作為編輯代價的前提下，可以證明c(Vi→Vj) =min{c(Vi→ε))+c(ε→Vj)，c(Vi→Vj)}=c(Vj→Vi).

定義7.邊之間的編輯代價：c(Ei→Ej) =if(LE(Ei)=LE(Ej))：0：1；c(Ei→ε)=c(ε→Ei)=1，即若Ei的標簽LE(Ei)與Ej的標簽LE(Ej)相同，則替換代價為0，否則為1.邊的插入和刪除操作代價定義為1.顯然邊的編輯代價亦滿足三角不等式關系.

(1)

圖3 兩個版本的編譯器體系結構(用屬性圖表示)Fig.3 Two compiler versions represented by attribute-graph

k1≤|V(gi-1)|，0

(2)

例如，考慮如下編譯系統(tǒng)的演化歷史如圖3所示.

節(jié)點和邊的編輯代價矩陣分別如下：

考慮邊的關系，則新的代價矩陣如下，計算可得編輯路徑為：p(1，2，3，7，8，9)={(Complier→Complier)，(C1→C2)，(1.0→1.2)，(ε→2.1) ，(ε→Parser)，(ε→P2) }，對應的編輯代價為C*(p(1，2，3，7，8，9))=0+2+1+4+7+5=19.

此時，因此該編譯器變化性度量值為編輯代價19.

5 應用：開源軟件體系結構演化分析

5.1 演化度量

為了對開源軟件體系結構進行演化分析，本文在軟件體系結構變化性度量EP(S，i)的基礎上定義了2個度量指標LEP和EEP，其中：

①LEP衡量軟件系統(tǒng)的近期變化，反映的是系統(tǒng)總的變化.該度量從系統(tǒng)全局的角度來分析，重點關注最新版本的變化，對每個版本的EP增加權重函數(shù)2i-maxRank(其中maxRank為參與度量最新版本對應的序列號)，統(tǒng)計系統(tǒng)從初始版本生成最新版本所有的版本屬性變化的加權總和，即系統(tǒng)S從第i個版本到第j個版本的EP加權求和，定義如公式(3)：

(3)

②EEP主要衡量軟件系統(tǒng)的早期變化，同樣反映的是系統(tǒng)總的變化.該度量從系統(tǒng)全局的角度分析，重點關注較早版本的變化，對每個版本的EP增加權重函數(shù)2minRank-i(其中minRank為參與度量早期版本對應的序列號)，統(tǒng)計系統(tǒng)從初始版本到最新版本所有的版本屬性變化的加權總和，即系統(tǒng)S從第i個版本到第j個版本的EP的加權求和，定義如公式(4)：

(4)

實驗過程下載了4個開源軟件系統(tǒng)的源代碼以及第三方提供的實驗數(shù)據[3]作為本文的實驗基礎，這四個系統(tǒng)分別為cassandra，hbase，hive，openjpa，其中cassandra和hive這兩個系統(tǒng)各使用了8個版本，hbase和openjpa這兩個系統(tǒng)各使用了12個版本，其中版本標簽是github中設定的版本號，編制的版本號是按照提取的開源系統(tǒng)版本重新按序編排(從1開始).實驗中首先計算系統(tǒng)每個版本的EP值，系統(tǒng)的總LEP值/EEP值；同時，為了度量每個系統(tǒng)內部的變化過程，分別計算每個系統(tǒng)的前i個版本的LEP值/EEP值，即LEP(1，i)和EEP(1，i).具體計算結果見表1-表4.

5.2 系統(tǒng)間演化度量分析

表1 cassandra變化數(shù)據Table 1 cassandra′s change data

表2 hbase變化數(shù)據Table 2 hbase′s change data

表3 hive變化數(shù)據Table 3 hive′s change data

表4 openjpa變化數(shù)據Table 4 openjpa′s change data

根據表1到表4中的EP值分別畫出了各個系統(tǒng)演化的EP值的折線圖(如圖4)，根據總LEP/EEP值畫出了各個系統(tǒng)整體LEP/EEP值柱狀圖(如圖5).

圖4 四個開源系統(tǒng)的EP比較Fig.4 Comparison of EP among four open source systems

通過對圖4和圖5的分析，即對4個軟件系統(tǒng)之間的變化進行分析，可以得出以下結論：

圖4中每條折線的第一個點值的大小反應了該軟件系統(tǒng)初始版本的體系結構的大小，從圖4可以看出，casscandra，hbase，hive這三個系統(tǒng)的初始版本的體系結構相對來說比較小，其體系結構演化EP值都在10000以內，而openjpa的初始版本的體系結構相對來說要大得多，其體系結構演化EP值超過了35000.此外，cassandra中EP值大于第一個版本的EP值的一半的版本有2個，占版本總個數(shù)的25%；對應于hbase中有8個，占總個數(shù)的75%；hive中有3個，占總個數(shù)的37.5%；openjpa中有0個，占總個數(shù)的0%.從這個數(shù)據可以看出，這四個系統(tǒng)中，hbase變化最大，openjpa變化最小，cassandra和hive變化程度比較接近.

按照LEP和 EEP的定義，值越大表示軟件變化越大.從圖5中可以看出，hbase的LEP值最大，表示該系統(tǒng)的近期變化在這四個系統(tǒng)中是最大的；openjpa系統(tǒng)的LEP值最小，EEP值最大，表示該系統(tǒng)的近期變化在這四個系統(tǒng)中是最小的，早期變化是最大的.別外，cassandra和hive這兩個系統(tǒng)的LEP值和EEP值都比較接近，說明這兩個系統(tǒng)的近期和早期變化程度較為接近.

圖5 四個開源系統(tǒng)的LEP/EEP比較Fig.5 Comparison of LEP/EEP among four open source systems

根據表1到表4中的每個系統(tǒng)的EP值畫出對應的EP值折線和趨勢線圖(見圖6).

按照LEP和 EEP的定義，值越大表示軟件變化越大.從圖5中可以看出，hbase的LEP值最大，表示該系統(tǒng)的近期變化在這四個系統(tǒng)中是最大的；openjpa系統(tǒng)的LEP值最小，EEP值最大，表示該系統(tǒng)的近期變化在這四個系統(tǒng)中是最小的，早期變化是最大的.別外，cassandra和hive這兩個系統(tǒng)的LEP值和EEP值都比較接近，說明這兩個系統(tǒng)的近期和早期變化程度較為接近.

根據表1到表4中的每個系統(tǒng)的EP值畫出對應的EP值折線和趨勢線圖(見圖6).

圖6 四個開源軟件的EP折線及趨勢線圖Fig 6 Line and trend chart of four open source system′s EP

對比分析這四個系統(tǒng)的EP值折線和趨勢線，可以得出以下結論：cassandra，hive，openjpa這三個系統(tǒng)的趨勢線呈下降的趨勢，這說明這三個系統(tǒng)在演化過程中的變化越來越小，從趨勢線下降的程度分析，這三個系統(tǒng)的趨勢線下降的程度依次變大，這說明openjpa的變化最為穩(wěn)定；而hbase這個系統(tǒng)的演化趨勢線呈上升的趨勢，說明該系統(tǒng)在演化的過程中變化程度越來越大.

小結：通過從EP、LEP及EEP三個方面對以上四個系統(tǒng)之間的演化分析可知，這四個系統(tǒng)中，hbase不僅變化程度是最大的，而且變化在持續(xù)增大；openjpa變化程度是最小的，且是穩(wěn)定變化；cassandra和hive這兩個系統(tǒng)相對于hbase和openjpa，變化程度較為不穩(wěn)定.

5.3 系統(tǒng)內部演化度量分析

根據表1到表4中的前i個版本的LEP值/EEP值，畫出系統(tǒng)各自對應的LEP/EEP折線圖(見圖7).

圖7 四個開源軟件前i個版本LEP/EEP折線圖Fig.7 Line chart of the first i versions of four open source system′s LEP/EEP

通過對前i個版本的軟件系統(tǒng)LEP/EEP值的計算，可以分析版本增加對系統(tǒng)早期和近期變化程度的影響.LEP值變大說明近期版本的變化較大，反之；EEP變大說明該系統(tǒng)早期版本變化較大，反之.通過對圖7的分析，可以得出以下結論：

從圖7(a)可知，cassandra系統(tǒng)的LEP值呈上下波動趨勢，說明該系統(tǒng)的演化處于不穩(wěn)定趨勢，但是LEP(1，4)值和LEP(1，6)的值突然增大，說明系統(tǒng)第4個版本和第6個版本變化較大.cassandra的EEP(1，1)到EEP(1，6)明顯變大，隨后變化不明顯，說明該系統(tǒng)演化到第6個版本的時候早期變化較大，此后早期變化比較穩(wěn)定.

從圖7(b)可知，hbase系統(tǒng)的LEP值呈增長趨勢，說明該系統(tǒng)的變化處于增長的趨勢，但是LEP(1，3)，LEP(1，6)，LEP(1，8)，LEP(1，9)和LEP(1，11)的值突然增大，說明這個系統(tǒng)的第3、6、8、9、11個版本變化較大；hbase的EEP(1，1)到EEP(1，7)值變化明顯變大，特別是EEP(1，3)突然增大，隨后的EEP值變化不明顯，說明該系統(tǒng)演化到第3個版本的時候早期變化很大，從第4個版本到第7個版本的早期變化較大，此后早期變化比較穩(wěn)定.

從圖7(c)可知，hive系統(tǒng)的LEP值呈上下波動趨勢，說明該系統(tǒng)的演化處于不穩(wěn)定狀態(tài).但是LEP(1，2)，LEP(1，5)和LEP(1，7)突然增大，說明該系統(tǒng)的第2、5、7個版本的變化較大；hive的EEP(1，2)突然增大，隨后EEP(1，3)到EEP(1，5)值明顯變大，然后變化不明顯，說明該系統(tǒng)演化到第2個版本的時候早期變化很大，從第3個版本到第5個版本的演化過程中，早期變化較大，隨后早期變化比較穩(wěn)定.

從圖7(d)可知，openjpa系統(tǒng)的LEP值呈下降的趨勢，說明該系統(tǒng)的變化逐漸減少，只是第7個版本上出現(xiàn)較大變化.openjpa的EEP(1，1)到EEP(1，3)變化較為明顯，隨后變化不明顯，說明該系統(tǒng)發(fā)展到第3個版本的時候早期變化較為明顯，隨后早期變化比較穩(wěn)定.

根據對表1到表4中每個系統(tǒng)EP值的分析，可以得出如下結論：cassandra的這8個版本一共經歷了3個變化減小和2個變化增大的過程；hbase的這12個版本一共經歷了5個變化減小和4個變化增大的過程；hive的這8個版本一共經歷了3個變化減小和3個變化增大的過程；openjpa的這12個版本一共經歷了4個變化減小和4個變化增大的過程.

小結：通過從EP、LEP和EEP對以上四個開源系統(tǒng)進行演化度量可知，這四個系統(tǒng)中，cassandra的演化過程是不穩(wěn)定變化的，在第4和第6個版本時變化大幅度增大；hbase的演化過程是變化持續(xù)增大的，其中在第3和第11個版本時變化大幅度增大；hive的演化過程是不穩(wěn)定變化的，在第2和第7個版本時變化大幅度變大；openjpa的演化過程是穩(wěn)定變化的，除了在第7個版本處有個小幅度的變化增大之外，其他版本的變化程度逐漸變小.

6 工具支持

為了支持構件化軟件的演化分析，本文開發(fā)了相應的支持工具，包括軟件體系結構規(guī)約重建、xCDL圖的屬性圖表示、編輯距離的計算、變化性度量等主要功能.其中，

①軟件體系結構重建功能主要負責從源代碼恢復用xCDL表示的軟件體系結構.這部分功能主要借助現(xiàn)有的軟件體系結構逆向工具例如ACDC[28]方法，或者借助已有的基于ACDC恢復的數(shù)據.在恢復時不僅是產生簇(構件)，而且借助源程序構造體系結構中構件之間連接關系，以及版本信息.

圖8 系統(tǒng)結構圖Fig.8 System structure

②xCDL的屬性圖表示：通過解析xCDL或者在逆向生成xCDL時，構造軟件體系結構的圖結構.

③編輯距離的計算：通過分析屬性圖中的節(jié)點和邊關系，構造節(jié)點的編輯代價矩陣和邊的編輯代價矩陣，利用二分圖匹配算法計算圖之間的編輯距離.

④變化性度量：給定不同系統(tǒng)在軟件演化過程中的一組軟件體系結構規(guī)約，分別計算其相鄰版本的軟件體系結構編輯距離；并基于度量指標LEP和EEP比較軟件內部或者不同系統(tǒng)之間的變化性.

7 結束語

對軟件體系結構變化性進行度量，能夠幫助軟件開發(fā)人員在較高層次理解軟件不同版本之間的差異性和理解系統(tǒng)內部或者系統(tǒng)之間的變化程度.為了克服傳統(tǒng)軟件體系結構變化性度量方法只考慮軟件實體元素變化的不足，本文將軟件體系結構映射為屬性圖，通過度量不同圖之間結構上的差異性，達到實現(xiàn)軟件體系結構差異性比較的目的.同時，基于上述方法，以4個開源軟件作為實驗對象，從軟件版本變化、軟件最新變化和軟件早期變化等角度分別對4個系統(tǒng)內部變化程度，以及系統(tǒng)之間變化的程度進行了分析.實驗效果表明，通過以上方法，可以分析開源軟件在軟件體系結構層次上的變化程度及其穩(wěn)定性.

[1] Medvidovic N，Taylor R N.Software architecture：foundations，theory，and practice[C].In：Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering，ACM，2010：471-472.

[2] Wen Z，Tzerpos V.An effectiveness measure for software clustering algorithms[C].In：Proceedings of the 12th IEEE International Workshop on Program Comprehension，IEEE，2004：194-203.

[3] Le D M，Behnamghader P，Garcia J，et al.An empirical study of architectural change in open-source software systems[C].In：Proceedings of the 12th Working Conference on Mining Software Repositories，IEEE Press，2015：235-245.

[4] Nakamura T，Basili V R.Metrics of software architecture changes based on structural distance[C].In：The 11th IEEE International Symposium on Software Metrics，IEEE，2005：8-17.

[5] Xing Z，Stroulia E.UMLDiff：an algorithm for object-oriented design differencing[C].In：Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering，ACM，2005：54-65.

[6] Apiwattanapong T，Orso A，Harrold M J.JDiff：A differencing technique and tool for object-oriented programs [J].Automated Software Engineering，2007，14(1)：3-36.

[7] Hashimoto M，Mori A，Izumida T.A comprehensive and scalable method for analyzing fine-grained source code change patterns[C].In：The 22nd International Conference on Software Analysis，Evolution and Reengineering (SANER)，IEEE，2015：351-360.

[8] Buse R P L，Weimer W R.Automatically documenting program changes[C].In：Proceedings of the IEEE/ACM International Conference on Automated Software Engineering，ACM，2010：33-42.

[9] Kim M，Notkin D，Grossman D.Automatic inference of structural changes for matching across program versions[C].In：Proceedings of the 29th International Conference on Software Engineering，2007：333-343.

[10] Le T D B，Yi J，Lo D，et al.Dynamic inference of change contracts[C].In：The International Conference on Software Maintenance and Evolution (ICSME)，IEEE，2014：451-455.

[11] Jiang Q，Peng X，Wang H，et al.Summarizing evolutionary trajectory by grouping and aggregating relevant code changes[C].In：The 22nd International Conference on Software Analysis，Evolution，and Reengineering (SANER)，IEEE，2015：361-370.

[12] Almousa H，Alenezi M.Measuring software architecture stability evolution in object-oriented open source systems [J].Journal of Engineering and Applied Sciences，2017，12(2)：353-362.

[13] Maoz，Shahar，Jan Oliver Ringert，et al.CDDiff：semantic differencing for class diagrams[C].In：The European Conference on Object-Oriented Programming,Springer Berlin Heidelberg，2011：230-254.

[14] Maoz S，Ringert J O，Rumpe B.ADDiff：semantic differencing for activity diagrams[C].In：Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering，ACM，2011：179-189.

[15] Arbuckle T.Studying software evolution using artefacts′shared information content [J].Science of Computer Programming，2011，76(12)：1078-1097.

[16] Hayase Y，Kanda T，Ishio T.Estimating product evolution graph using Kolmogorov complexity[C].In：Proceedings of the 14th International Workshop on Principles of Software Evolution，ACM，2015：66-72.

[17] Threm D，Yu L，Ramaswamy S，et al.Using normalized compression distance to measure the evolutionary stability of software systems[C].In：The 26th International Symposium on Software Reliability Engineering (ISSRE)，IEEE，2015：112-120.

[18] Zhu T，Wu Y，Peng X，et al.Monitoring software quality evolution by analyzing deviation trends of modularity views[C].In：The 18th Working Conference on Reverse Engineering，IEEE，2011：229-238.

[19] Durisic D，Nilsson M，Staron M，et al.Measuring the impact of changes to the complexity and coupling properties of automotive software systems[J].Journal of Systems and Software，2013，86(5)：1275-1293.

[20] Li B，Liao L，Si J.A technique to evaluate software evolution based on architecture metric[C].In：The 14th International Conference on Software Engineering Research，Management and Applications (SERA)，IEEE，2016：1-8.

[21] Xiao L，Cai Y，Kazman R，et al.Identifying and quantifying architectural debt[C].In：Proceedings of the 38th International Conference on Software Engineering，ACM，2016：488-498.

[22] Kouroshfar E，Mirakhorli M，Bagheri H，et al.A study on the role of software architecture in the evolution and quality of software[C].In：Proceedings of the 12th Working Conference on Mining Software Repositories，IEEE Press，2015：246-257.

[23] Behnamghader P，Le D M，Garcia J，et al.A large-scale study of architectural evolution in open-source software systems [J].Empirical Software Engineering，2017，22(3)：1146-1193.

[24] Bunke H，Allermann G.Inexact graph matching for structural pattern recognition [J].Pattern Recognition Letters，1983，1(4)：245-253.

[25] Sanfeliu A，F(xiàn)u K S.A distance measure between attributed relational graphs for pattern recognition [J].IEEE Transactions on Systems，Man，and Cybernetics，1983，13(3)：353-362.

[26] Riesen K，Neuhaus M，Bunke H.Bipartite graph matching for computing the edit distance of graphs [J].Graph-Based Representations in Pattern Recognition，2007，(4538)：1-12.

[27] Riesen K，Bunke H.Approximate graph edit distance computation by means of bipartite graph matching [J].Image and Vision Computing，2009，27(7)：950-959.

[28] Tzerpos V，Holt R C.ACDC：an algorithm for comprehension-driven clustering[C].In：The 7th Working Conference on Reverse Engineering，IEEE，2000：258-267.

[29]Wang Jin-shui,Ai Wei, Peng Xin, et al.Recovering traceability links among multi-level software evolution information[J].Computer Science, 2012,39(7):135-139.

[30]Li Jun-pu,Wang Jian-xin, Mo Qiao-chu.Software-evolution analysis model based on AHP[J].Computer Engineering and Design,2015,36(9):2416-2421.

[31]Huang Wan-gen, Chen Song-qiao.Measuring software architecture evolution based on component combination operations[J].Computer Science,2007,34(9):245-261.

[32]Zhong Lin-hui,Xie Bing,Shao Wei-zhong.Supporting component-based software development by extending the CDL with software configuration information[J].Journal of Computer Research and Development,2002,39(10):1361-1365.

[33] Zhang Lu,Xie Bing, Mei Hong,et al.Study of component-based software configuration management technologies[J].Acta Electronica Sinica,2001,29(2):266-268.

附中文參考文獻：

[29] 王金水，艾 偉，彭 鑫，等.多層次的軟件演化追蹤關系逆向恢復[J].計算機科學，2012，39(7)：135-139.

[30] 李俊普，王建新，莫翹楚.基于AHP的軟件演化分析模型[J].計算機工程與設計，2015，36(9)：2416-2421.

[31] 黃萬艮，陳松喬.基于構件組合運算的SA可演化性度量[J].計算機科學，2007，34(9)：245-261.

[32] 鐘林輝，謝 冰，邵維忠.擴充CDL支持基于構件的系統(tǒng)組裝與演化[J].計算機研究與發(fā)展，2002，39(10)：1361-1365.

[33] 張 路，謝 冰，梅 宏，等.基于構件的軟件配置管理技術研究[J].電子學報，2001，29(2)：266-268.