基于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.］