基于AHP的軟件演化分析模型

李俊普，王建新，莫翹楚

（北京林業(yè)大學(xué) 信息學(xué)院，北京100083）

0 引 言

由于軟件［1］的支持環(huán)境更新和升級(jí)較為頻繁，大量的優(yōu)秀軟件不能繼續(xù)使用，變成了遺產(chǎn)系統(tǒng) （legacy system）［2］，一般來說，要研究歷史版本的演化過程，需要利用開發(fā)過程中記錄的文檔［3］，但此類文檔相對軟件很不具體，在軟件工程控制不嚴(yán)格時(shí)并非必須包含，因此，依據(jù)文檔記錄分析軟件的演化信息將變得十分困難。相反，如果在源代碼級(jí)別上分析軟件，則能更好地直接理解軟件的演化過程［4］，但是人工分析源代碼的工作量十分龐大，甚至超過了開發(fā)源代碼本身，因此，近年來針對軟件演化的大多數(shù)研究都轉(zhuǎn)向了基于源代碼的自動(dòng)化的演化分析技術(shù)［5］。

當(dāng)前較為成熟的軟件源代碼演化分析方法分別基于抽象的語法功能模塊、語法基本元素 （語法節(jié)點(diǎn)）以及文本比對的分析算法。前兩者的分析基礎(chǔ)是抽象語法樹。

抽象語法樹 （abstract syntax tree，AST），或者簡稱語法樹 （syntax tree），是源代碼的抽象語法結(jié)構(gòu)的樹狀表現(xiàn)形式，樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)或元素。

基于軟件功能模塊的演化分析方法，其原理是先將軟件源代碼進(jìn)行詞法分析和語法分析［5］，從中提取出語法功能結(jié)構(gòu)模塊，例如類、函數(shù)、結(jié)構(gòu)體等，分別計(jì)算不同版本程序語法樹的Hash值和子節(jié)點(diǎn)，分析出功能模塊的改變，能夠較好體現(xiàn)出軟件中體系結(jié)構(gòu)變化所帶來的影響，甚至可以分析出安全缺陷的演化［6］，同時(shí)又可以忽略掉一些無關(guān)代碼本質(zhì)改變的文本調(diào)整帶來的誤差。

相對功能結(jié)構(gòu)的抽象，基于語法基本元素的改變進(jìn)行演化分析的方法在語法功能的體現(xiàn)上會(huì)稍顯不足，某些重構(gòu)方式無法檢測分析［7］，但該方法能較完整反映程序在最小語法單元上的變化，一定程度上減少Hash 沖突帶來的誤差［8］。

基于文本比對的演化分析方法在代碼行的粒度上進(jìn)行代碼比對和演化分析［9］。這種方法實(shí)現(xiàn)相對簡單，但需要高效的比對算法。其主要依據(jù)是不同版本之間源代碼在文本層面上的區(qū)別，采用的算法的基本功能是匹配不同版本間打亂順序的代碼行。源代碼在版本間改動(dòng)較少的情況下該方法比較精確，但不能分析出較高層的演化因素。

以上3種分析算法各有優(yōu)劣，各有比較適應(yīng)的代碼演化場景，但獨(dú)自均無法做到全面的演化分析，不能得到一個(gè)相對滿意的演化結(jié)果指標(biāo)。因此，本文提出了一種基于層次分析法 （analytic hierarchy process，AHP）的軟件演化分析模型，通過制定總目標(biāo) （演化率），并把它分解為3種演化分析方法對應(yīng)的子目標(biāo)，能夠根據(jù)子目標(biāo)對應(yīng)的演化率綜合出總目標(biāo)對應(yīng)的演化率，更加真實(shí)地反映軟件的整體演化率。

1 分析方法

層次分析法（AHP）是一種定性與定量相結(jié)合的層次化的系統(tǒng)結(jié)構(gòu)決策分析方法，通過建立多層次模型，將評價(jià)指標(biāo)進(jìn)行量化，最終得到各方案相對目標(biāo)的重要性權(quán)重排序［10］。AHP主要用于預(yù)測、評估和分析等，實(shí)用性很強(qiáng)。

1.1 確定評估指標(biāo)

軟件演化的程度通常由很多不同的因素決定，而各種演化分析方法又有著不同的優(yōu)劣程度，對各種演化方式的檢測分析程度也不同，其結(jié)果也必然存在誤差。綜合各個(gè)指標(biāo)的包含關(guān)系和相關(guān)性，我們將演化率的評價(jià)指標(biāo)歸結(jié)為以下4個(gè)：

（1）分析類型范圍。即各種演化分析方法對不同演化類型的支持程度。

（2）誤差大小。演化分析多少會(huì)存在誤差，需估算其大小。

（3）定位精度。不同的演化分析方式有著不同的分析粒度，從而有不同的定位精度，因此對最終結(jié)果必然存在影響。

（4）功能結(jié)構(gòu)分析能力。也就是在軟件功能結(jié)構(gòu)演化上的分析程度。

雖然有其它指標(biāo)能夠評價(jià)軟件演化程度，但上述4個(gè)指標(biāo)是起決定作用的主要指標(biāo)。

1.2 構(gòu)建AHP綜合層次模型

根據(jù)上一部分的分析，我們已經(jīng)確定了對于3種演化分析方式的衡量指標(biāo)。AHP層次分析模型評估指標(biāo)系統(tǒng)一般是分為目標(biāo)層、準(zhǔn)則層和方案層這3層。其中目標(biāo)層表示解決問題的目的，是我們最終要達(dá)到的目標(biāo)，在此對應(yīng)的是演化率。

準(zhǔn)則層表示的是針對各個(gè)評價(jià)方案所考慮的子目標(biāo)，本問題中就是上一部分分析的4 個(gè)因素：分析類型范圍、誤差大小、定位精度和功能結(jié)構(gòu)分析能力。

方案層即解決問題的方案，對應(yīng)的是基于功能模塊、語法基本元素和文本比對這3種演化分析方式。由此，我們建立如圖1所示的AHP演化分析綜合層次模型。由于模型中所有上下層元素之間均存在關(guān)聯(lián)，因此是完全相關(guān)結(jié)構(gòu)。

圖1 AHP演化分析綜合層次模型

1.3 相對貢獻(xiàn)分析

考慮到層次分析法在本文的應(yīng)用主題，即分析軟件在整體上、特別是功能架構(gòu)上的變化，功能結(jié)構(gòu)這個(gè)影響因素比其它因素要重要。而相比誤差大小和定位精度，分析類型范圍也更重要。結(jié)合專家意見，通過兩兩比較，我們將分析類型范圍、誤差大小、定位精度和功能結(jié)構(gòu)分析能力這4種指標(biāo)的重要性比值近似定為3∶2∶1∶4。

對于分析類型范圍，演化分析的算法應(yīng)該能夠盡可能多的覆蓋可能的程序演化種類，這樣才能更準(zhǔn)確地分析出程序的演化行為。表1列舉了一些常見的程序演化的種類以及各個(gè)演化分析方式對其支持的情況。

表1 不同演化分析方法的分析類型覆蓋情況

表1可用來為分析當(dāng)前指標(biāo)的貢獻(xiàn)提供參考。

由于各種演化分析方法都有自己的缺陷，所以在演化分析的過程中，必定存在誤差，將沒有發(fā)生演化的情況判定為已發(fā)生演化。下面對一些可能造成誤差的情況進(jìn)行列舉，以便輔助分析當(dāng)前指標(biāo)的貢獻(xiàn)，見表2。

表2 不同演化分析方法可能存在誤差的情況

對于定位精度，我們以行來進(jìn)行區(qū)分?；谖谋镜姆治龇绞剑軌蚨ㄎ坏矫恳恍袃?nèi)容的變化情況；基于語法基本元素的演化分析方式，由于是以較小語法結(jié)點(diǎn)作為分析基礎(chǔ)，因此能將結(jié)果定位到平均2行左右；而基于功能模塊的演化分析方式，由于其本身具有的宏觀特性，其精確程度在平均約為4行。

最后是功能結(jié)構(gòu)的分析能力，由于基于功能模塊的分析方式是從較高層次的角度來對演化規(guī)律進(jìn)行把握，顯然在此衡量指標(biāo)上具有較大貢獻(xiàn)，而基于文本的方式關(guān)注的是程序代碼在細(xì)節(jié)上的變動(dòng)情況，所以不太能夠反映演化的宏觀規(guī)律。

1.4 構(gòu)造判斷矩陣

在對各個(gè)層次的相關(guān)貢獻(xiàn)進(jìn)行分析之后，我們要通過構(gòu)建判斷矩陣來得到各個(gè)方案的最終權(quán)值分配情況。由于同時(shí)分析多個(gè)貢獻(xiàn)難于得到準(zhǔn)確的重要程度比值，且容易造成誤差，所以我們將對所有元素的相對貢獻(xiàn)進(jìn)行兩兩比較，得到其重要性權(quán)值。在此，我們將僅使用1～9標(biāo)度法來區(qū)分其重要性程度，如表3中所列重要性標(biāo)度。

表3 兩個(gè)元素對比的重要性標(biāo)度

對于n個(gè)事物，兩兩比較其重要性得的判斷矩陣，需滿足以下性質(zhì)［7］：

（1）aij＞0；

（2）當(dāng)i≠j時(shí)，aij＝1／aij；

（3）當(dāng)i＝j(luò)時(shí)，aij＝1。

其中，aij為i與j 兩元素相對重要性的比值。

根據(jù)上一部分內(nèi)容中對各個(gè)元素的貢獻(xiàn)分析，首先根據(jù)實(shí)際情況對兩兩貢獻(xiàn)比值調(diào)整確定，在此基礎(chǔ)上，結(jié)合重要性標(biāo)度方法，我們可以得到范圍和指標(biāo)等信息。

基于功能模塊、語法基本元素和文本比對3種演化分析方法 （P1、P2、P3）對分析類型范圍、誤差大小、定位精度以及功能結(jié)構(gòu)分析能力這4 種衡量指標(biāo) （G1、G2、G3、G4）的判斷矩陣，見表4。

分析類型范圍、誤差大小、定位精度以及功能結(jié)構(gòu)分析能力這4種衡量指標(biāo) （G1、G2、G3、G4）對綜合演化率（A）的判斷矩陣見表5。

1.5 一致性檢驗(yàn)

在判斷矩陣A 中，如果成立，則矩陣A 是一致性矩陣。要在準(zhǔn)則下對元素權(quán)重進(jìn)行重要性的排序，判斷矩陣A 的一致性的作用至關(guān)重要。但是在實(shí)際評價(jià)中，盡管判斷矩陣是通過兩兩比較貢獻(xiàn)后得到的成對比較陣，但其重要程度帶有主觀因素，這是事物的復(fù)雜性和人的認(rèn)識(shí)的主觀局限性造成的，所以矩陣有可能會(huì)存在不一致的邏輯錯(cuò)誤。因此我們需要對判斷矩陣進(jìn)行一致性檢驗(yàn)，確保最終結(jié)果的準(zhǔn)確性。

表4 P1、P2、P3對分析類型范圍（G1）、誤差大小（G2）、定位精度（G3）、功能結(jié)構(gòu)分析能力（G4）的貢獻(xiàn)判斷矩陣

表5 P1、P2、P3、P4對綜合演化率（A）的貢獻(xiàn)判斷矩陣

根據(jù)AHP原理，我們可以通過數(shù)學(xué)的方法來檢驗(yàn)判斷矩陣的一致性是否合理，過程如下：

（1）首先計(jì)算判斷矩陣的最大特征根，如式 （1）所示

（2）然后計(jì)算一致性指標(biāo)CI，如式 （2）所示

式中：λmax——比較判斷矩陣的最大特征根，n——比較判斷矩陣的階數(shù)。

在此基礎(chǔ)上，根據(jù)下式計(jì)算一致性比例CR

理想情況下，CR＝0。但是在實(shí)際評價(jià)中，主觀因素必然會(huì)導(dǎo)致誤差的存在。通常認(rèn)為0.1是一個(gè)臨界值。當(dāng)CR 小于這個(gè)值時(shí)，認(rèn)為判斷矩陣式可以接受的；當(dāng)CR 大于這個(gè)值時(shí)，需要重新修正相應(yīng)的判斷矩陣，以達(dá)到對CR的檢驗(yàn)標(biāo)準(zhǔn)要求。

經(jīng)檢驗(yàn)得知，上述5 個(gè)矩陣的一致性比例CR 分別為0.0521，0.0176，0.0089，0.0630，0.0474，均 滿 足 一 致性檢驗(yàn)條件。

1.6 層次排序權(quán)重

層次排序權(quán)重分為層次單排序權(quán)重和層次總排序權(quán)重。層次單排序權(quán)重指一層中每一個(gè)元素針對上層中單個(gè)元素的權(quán)重；而層次總排序權(quán)重的定義是：對于目標(biāo)層的總權(quán)重，方案層上的每一個(gè)元素對應(yīng)的權(quán)重大小。在求得層次總排序權(quán)重之前，需要先求得每個(gè)層次單排序的權(quán)重，然后，以此為基礎(chǔ)，求得層次總排序的權(quán)重。

層次單排序權(quán)重計(jì)算的步驟如下：

（1）將判斷矩陣的每一列向量歸一化

（2）對第一步中得到的按列歸一化后的判斷矩陣，再按行求和

經(jīng)計(jì)算，得到層次單排序權(quán)重，見表6和表7。

1)基于微課的自主學(xué)習(xí)：翻轉(zhuǎn)課堂順利實(shí)施的技術(shù)支持就是微課，特別是在實(shí)踐性較強(qiáng)的計(jì)算機(jī)公共類課程中，把微課作為輔助教學(xué)非常便利，學(xué)生可以不受時(shí)間、地點(diǎn)的限制，多次地通過觀看微課進(jìn)行知識(shí)的復(fù)習(xí)和強(qiáng)化。在具體實(shí)現(xiàn)時(shí)，根據(jù)不同的課程要求，教師構(gòu)建基于微課的課程自主學(xué)習(xí)平臺(tái)，平臺(tái)主要包括以下功能：

表6 方案層單排序權(quán)重

表7 準(zhǔn)則層單排序權(quán)重

總排序權(quán)重計(jì)算步驟如下：

（1）相對于總目標(biāo)，第k－1層的所有m 個(gè)元素的權(quán)重記作w（k－1）i。

（2）相對于上層 （第k－1層），第k 層的所有n 個(gè)元素的單排序權(quán)重是一個(gè)向量，而第j個(gè)元素對應(yīng)的向量是

（3）第k層的每一個(gè)元素的權(quán)重是一個(gè)標(biāo)量。它的第j個(gè)元素相對于總目標(biāo)而言的總排序權(quán)重是

層次總排序權(quán)重見表8。

表8 層次總排序權(quán)重

根據(jù)表8，綜合演化率 （E）和基于功能模塊 （Efun）、語法基本元素 （Emod）和文本比對 （Etxt）這3種演化分析方法的線性關(guān)系為

2 實(shí)驗(yàn)分析

基于AHP的綜合演化率計(jì)算模型，兼顧了基于功能模塊、語法基本元素和文本比對3種演化分析方法的優(yōu)點(diǎn)，同時(shí)也考慮到了它們各自的不足，在種類繁多的實(shí)際版本演化中，能夠更好的反映軟件的演化程度和演化規(guī)律。為了驗(yàn)證基于AHP算法的綜合演化率的準(zhǔn)確性，我們提出一個(gè)假設(shè)：

在外界條件不變的情況下，當(dāng)某種演化分析的算法對所有演化種類G1 的支持程度能夠達(dá)到100%，誤差大小G2為0，定位精度G3 為1，同時(shí)對功能結(jié)構(gòu)的分析程度G4能達(dá)到100%，則這種算法得到的演化率將無限接近理想演化率。

記計(jì)算演化率和理想演化率分別為Edet和Epref。那么，對于任意整數(shù)ε（無論它多么小），總存在著正數(shù)δ1，δ2，δ3，δ4，使得當(dāng)同時(shí)滿足以下4個(gè)不等式時(shí)，0＜｜G1－1｜＜δ1，0＜｜G2－0｜＜δ2，0＜｜G3－0｜＜δ3，0＜｜G4－1｜＜δ4，滿足

式 （10）說明，在自變量趨于以上極端值的情況下，Edet的極限值為Epref。

由于各種算法各有優(yōu)劣，所以導(dǎo)致結(jié)果會(huì)在一定程度上偏離理想的演化率。我們期望基于AHP的綜合演化分析方法能夠考慮各種分析方法的優(yōu)劣，更加接近真實(shí)結(jié)果的演化率。

為此，以Linux下著名圖像處理工具gimp為例，對它的兩個(gè)版 本 （v2.0.5 和v2.2.11）進(jìn) 行 人 為 的 演 化 分 析，盡可能全面的考慮各種演化情況，計(jì)算出實(shí)際演化率約為28.3%。而基于功能模塊、語法基本元素和文本比對的3種演化分析方法以及通過AHP層次分析法計(jì)算出的演化率分別為26.3%，24.8%，35.7%和27.5%。通過比較可以發(fā)現(xiàn)，通過AHP層次分析方法進(jìn)行綜合過后的結(jié)果更加接近實(shí)際真實(shí)結(jié)果。

下面以開源軟件gimp和7－zip為例進(jìn)行多版本演化分析比較。

2.1 gimp多版本演化分析

將gimp的5個(gè)版本 （v2.05－v2.6.11）用3種演化分析方法進(jìn)行演化分析，得到如表9所示的結(jié)果。

表9 gimp各版本的總體情況和演化情況

通過對gimp的演化分析，我們得到演化率的變化情況圖，如圖2所示。從圖中可以看出，對于gimp軟件的版本演化率，從功能模塊分析、語法元素分析、文本分析以及綜合分析的結(jié)果都具有大致的先上升、后下降的趨勢，但在細(xì)節(jié)上略有不同。綜合分析獲得的版本演化率在趨勢上表現(xiàn)得更折衷一些。

2.2 7－zip多版本演化分析

將開源壓縮工具7－zip的4個(gè)版本 （v4.23－v9.22）用3種演化分析方法進(jìn)行演化分析，得到如表10所示的結(jié)果。

通過對7－zip的演化分析，我們得到演化率的變化情況圖，如圖3所示。從圖中可以明顯地看出，4種分析手段所獲取的7－zip軟件的版本演化率具有類似的趨勢。這說明這4種方式具有內(nèi)在的正相關(guān)的聯(lián)系。但是，綜合分析計(jì)算所得的版本演化率在上升階段和下降階段都相對比較平穩(wěn)。

圖2 gimp各版本演化率變化情況

表10 7－zip各版本的總體情況和演化情況

圖3 7－zip各版本演化率變化情況

從圖2和圖3可以看出，gimp軟件和7－zip軟件的版本演化率遵循了類似的變化規(guī)律，都是在第2個(gè)版本中具有最大的版本演化率。

但是，截止到本文檢測時(shí)間為止，7－zip軟件具有4個(gè)不同的版本，而gimp軟件僅有3個(gè)不同版本。因此，可以認(rèn)為，7－zip軟件的最后兩個(gè)版本在軟件演化行為上起到了gimp軟件最后一個(gè)版本的演化作用。所以，我們可以根據(jù)演化率劃分演化階段，而不必僅僅局限于版本號(hào)。通過圖2 和圖3 等軟件演化圖可以直觀地查看軟件的演化情況。

2.3 實(shí)驗(yàn)結(jié)果分析

從以上的實(shí)驗(yàn)數(shù)據(jù)分析可以發(fā)現(xiàn)，軟件在初期版本的更新中總是存在較高的演化率，一定程度上可以反映軟件在開發(fā)前期的變動(dòng)較大［11］，特別是功能架構(gòu)上更是如此。在后期的版本演化中，演化率會(huì)逐漸減小，趨于穩(wěn)定。另外，在各種方式的演化率上，AHP 都比較接近真實(shí)演化率，符合實(shí)際演化情況。其中基于文本的分析方式顯得較不穩(wěn)定，說明其反映功能架構(gòu)變化的能力的欠缺，難以從整體上把握演化的實(shí)際規(guī)律。

3 結(jié)束語

我們結(jié)合層次分析的方法，提出了綜合演化率的計(jì)算模型。該模型融合了程序功能模塊、語法基本元素和文本分析的演化分析方法，以分析類型范圍、誤差大小、定位精度以及功能結(jié)構(gòu)分析能力作為衡量指標(biāo)，從而確定3種演化分析方式的綜合權(quán)重，最終得到更加真實(shí)、更能反映實(shí)際演化規(guī)律的演化率。

同時(shí)，我們對多種軟件的多個(gè)版本進(jìn)行演化分析，以驗(yàn)證基于AHP算法的準(zhǔn)確性，并發(fā)現(xiàn)軟件演化的規(guī)律。通過實(shí)驗(yàn)，我們發(fā)現(xiàn)在早期的開發(fā)過程中，軟件版本的波動(dòng)存在較大變化，當(dāng)程序變得相對成熟過后，版本也就趨于穩(wěn)定，演化率也相應(yīng)減小，這個(gè)軟件工程規(guī)律對軟件的研發(fā)具有借鑒意義。

通過軟件演化率計(jì)算模型，我們可以通過軟件本身量化地分析和查看軟件的演化情況，而不僅僅局限于版本號(hào)和軟件伴隨文檔。

［1］Canfora G，Cerulo L，Di P.Tracking your changes：A language－independent approach ［J］.IEEE Software，2009，26（1）：50－57.

［2］Laguna MA，Cespo Y.A systematic mapping study on software product line evolution：From legacy system reengineering to product line refactoring ［J］.Science of Computer Programming，2013，78 （2）：1010－1034.

［3］Carvalho NR，Simes A，Almeida JJ.Open source software documentation mining for quality assessment［J］.Advances in Information Systems and Technologies，2013，206 （AISC）：785－794.

［4］Gde N，Koschke R.Studying clone evolution using incremental clone detection ［J］.Journal of Software：Evolution and Process，2013，25 （2）：165－192.

［5］WU Shizhong，GUO Tao，DONG Guowei，et al.Software vulnerability analyses：A road map ［J］.Journal of Tsinghua University：Science and Technology，2012，52 （10）：1309－1319 （in Chinese）. ［吳世忠，郭濤，董國偉，等.軟件漏洞分析技術(shù)進(jìn)展 ［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，52（10）：1309－1319.］

［6］Li Y，Wang L.Specifying and detecting behavioral changes in source code using abstract syntax tree differencing ［M］.Trustworthy Computing and Services：Springer Berlin Heidelberg，2013：466－473.

［7］Yoshida N，Higo Y，Kusumoto S.An experience report on analyzing industrial software systems using code clone detection techniques［C］／／Proceedings of the 19th Asia－Pacific Software Engineering Conference，2012：310－313.

［8］Gu X，Bian Y，Wu L，et al.The study on the software feasibility assessment model based on component evolution and system behavior consistency ［J］.International Journal of Digital Content Technology and its Applications，2012，6 （22）：284－292.

［9］Rainer A，Lane PCR，Malcolm J，et al.Using n－grams to rapidly characterise the evolution of software code ［C］／／Proceedings of 1st International Workshop on Automated Engineering of Autonomous and Runtime Evolving Systems and the 23rd IEEE／ACM International Conference on Automated Software Engineering，2008：43－52.

［10］YAN Wei，CHEN Changhuai，CHEN Yan.The threshold value of consistency index for analytic hierarchy process ［J］.Journal of Applied Statistics and Management，2011，30（3）：414－423 （in Chinese）.［閆威，陳長懷，陳燕.層次分析法一致性指標(biāo)的臨界值研究 ［J］.數(shù)理統(tǒng)計(jì)與管理，2011，30 （3）：414－423.］

［11］ZHOU Yixun，CHEN Haibo.Analyzing Java program evolution using abstract syntax tree matching ［J］.Computer Applications and Software，2011，28 （8）：196－199 （in Chinese）.［周逸勛，陳海波.使用抽象語法樹匹配分析Java程序演化 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2011，28 （8）：196－199.］