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

李俊普，王建新，莫翹楚

（北京林業大學 信息學院，北京100083）

0 引 言

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

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

抽象語法樹 （abstract syntax tree，AST），或者簡稱語法樹 （syntax tree），是源代碼的抽象語法結構的樹狀表現形式，樹上的每個節點都表示源代碼中的一種結構或元素。

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

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

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

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

1 分析方法

層次分析法（AHP）是一種定性與定量相結合的層次化的系統結構決策分析方法，通過建立多層次模型，將評價指標進行量化，最終得到各方案相對目標的重要性權重排序［10］。AHP主要用于預測、評估和分析等，實用性很強。

1.1 確定評估指標

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

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

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

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

（4）功能結構分析能力。也就是在軟件功能結構演化上的分析程度。

雖然有其它指標能夠評價軟件演化程度，但上述4個指標是起決定作用的主要指標。

1.2 構建AHP綜合層次模型

根據上一部分的分析，我們已經確定了對于3種演化分析方式的衡量指標。AHP層次分析模型評估指標系統一般是分為目標層、準則層和方案層這3層。其中目標層表示解決問題的目的，是我們最終要達到的目標，在此對應的是演化率。

準則層表示的是針對各個評價方案所考慮的子目標，本問題中就是上一部分分析的4 個因素：分析類型范圍、誤差大小、定位精度和功能結構分析能力。

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

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

1.3 相對貢獻分析

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

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

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

表1可用來為分析當前指標的貢獻提供參考。

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

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

對于定位精度，我們以行來進行區分。基于文本的分析方式，能夠定位到每一行內容的變化情況；基于語法基本元素的演化分析方式，由于是以較小語法結點作為分析基礎，因此能將結果定位到平均2行左右；而基于功能模塊的演化分析方式，由于其本身具有的宏觀特性，其精確程度在平均約為4行。

最后是功能結構的分析能力，由于基于功能模塊的分析方式是從較高層次的角度來對演化規律進行把握，顯然在此衡量指標上具有較大貢獻，而基于文本的方式關注的是程序代碼在細節上的變動情況，所以不太能夠反映演化的宏觀規律。

1.4 構造判斷矩陣

在對各個層次的相關貢獻進行分析之后，我們要通過構建判斷矩陣來得到各個方案的最終權值分配情況。由于同時分析多個貢獻難于得到準確的重要程度比值，且容易造成誤差，所以我們將對所有元素的相對貢獻進行兩兩比較，得到其重要性權值。在此，我們將僅使用1～9標度法來區分其重要性程度，如表3中所列重要性標度。

表3 兩個元素對比的重要性標度

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

（1）aij＞0；

（2）當i≠j時，aij＝1／aij；

（3）當i＝j時，aij＝1。

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

根據上一部分內容中對各個元素的貢獻分析，首先根據實際情況對兩兩貢獻比值調整確定，在此基礎上，結合重要性標度方法，我們可以得到范圍和指標等信息。

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

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

1.5 一致性檢驗

在判斷矩陣A 中，如果成立，則矩陣A 是一致性矩陣。要在準則下對元素權重進行重要性的排序，判斷矩陣A 的一致性的作用至關重要。但是在實際評價中，盡管判斷矩陣是通過兩兩比較貢獻后得到的成對比較陣，但其重要程度帶有主觀因素，這是事物的復雜性和人的認識的主觀局限性造成的，所以矩陣有可能會存在不一致的邏輯錯誤。因此我們需要對判斷矩陣進行一致性檢驗，確保最終結果的準確性。

表4 P1、P2、P3對分析類型范圍（G1）、誤差大小（G2）、定位精度（G3）、功能結構分析能力（G4）的貢獻判斷矩陣

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

根據AHP原理，我們可以通過數學的方法來檢驗判斷矩陣的一致性是否合理，過程如下：

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

（2）然后計算一致性指標CI，如式 （2）所示

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

在此基礎上，根據下式計算一致性比例CR

理想情況下，CR＝0。但是在實際評價中，主觀因素必然會導致誤差的存在。通常認為0.1是一個臨界值。當CR 小于這個值時，認為判斷矩陣式可以接受的；當CR 大于這個值時，需要重新修正相應的判斷矩陣，以達到對CR的檢驗標準要求。

經檢驗得知，上述5 個矩陣的一致性比例CR 分別為0.0521，0.0176，0.0089，0.0630，0.0474，均 滿 足 一 致性檢驗條件。

1.6 層次排序權重

層次排序權重分為層次單排序權重和層次總排序權重。層次單排序權重指一層中每一個元素針對上層中單個元素的權重；而層次總排序權重的定義是：對于目標層的總權重，方案層上的每一個元素對應的權重大小。在求得層次總排序權重之前，需要先求得每個層次單排序的權重，然后，以此為基礎，求得層次總排序的權重。

層次單排序權重計算的步驟如下：

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

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

經計算，得到層次單排序權重，見表6和表7。

1)基于微課的自主學習：翻轉課堂順利實施的技術支持就是微課，特別是在實踐性較強的計算機公共類課程中，把微課作為輔助教學非常便利，學生可以不受時間、地點的限制，多次地通過觀看微課進行知識的復習和強化。在具體實現時，根據不同的課程要求，教師構建基于微課的課程自主學習平臺，平臺主要包括以下功能：

表6 方案層單排序權重

表7 準則層單排序權重

總排序權重計算步驟如下：

（1）相對于總目標，第k－1層的所有m 個元素的權重記作w（k－1）i。

（2）相對于上層 （第k－1層），第k 層的所有n 個元素的單排序權重是一個向量，而第j個元素對應的向量是

（3）第k層的每一個元素的權重是一個標量。它的第j個元素相對于總目標而言的總排序權重是

層次總排序權重見表8。

表8 層次總排序權重

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

2 實驗分析

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

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

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

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

由于各種算法各有優劣，所以導致結果會在一定程度上偏離理想的演化率。我們期望基于AHP的綜合演化分析方法能夠考慮各種分析方法的優劣，更加接近真實結果的演化率。

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

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

2.1 gimp多版本演化分析

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

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

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

2.2 7－zip多版本演化分析

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

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

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

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

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

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

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

2.3 實驗結果分析

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

3 結束語

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

同時，我們對多種軟件的多個版本進行演化分析，以驗證基于AHP算法的準確性，并發現軟件演化的規律。通過實驗，我們發現在早期的開發過程中，軟件版本的波動存在較大變化，當程序變得相對成熟過后，版本也就趨于穩定，演化率也相應減小，這個軟件工程規律對軟件的研發具有借鑒意義。

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

［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）. ［吳世忠，郭濤，董國偉，等.軟件漏洞分析技術進展 ［J］.清華大學學報：自然科學版，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）.［閆威，陳長懷，陳燕.層次分析法一致性指標的臨界值研究 ［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］.計算機應用與軟件，2011，28 （8）：196－199.］