基于版本间克隆映射的演化模式识别及谱系构建

张久杰 翟晔 王春晖 张丽萍 刘东升

摘要：针对当前克隆谱系的构建方法较为复杂、演化模式亟需扩充等问题，提出了新的克隆代码演化模式，并根据软件版本间的克隆代码映射关系自动构建了克隆谱系。首先，针对软件每一版本进行克隆检测并利用潜在狄利克雷分配（LDA）抽取克隆代码的主题信息；然后，根据克隆代码主题的相似度确定版本间克隆代码的映射关系；进而，根据已有的映射关系为克隆代码添加演化模式并分析演化特征；最终，结合映射信息与演化模式信息完成克隆谱系的构建。针对4款开源软件进行了克隆谱系的构建实验，实验结果表明所提克隆谱系构建方法可行，证实了新提出的演化模式在克隆代码演化过程中确实存在。实验发现约90%的克隆代码在软件演化过程中比较稳定，约67%的克隆群经历的发布版本数不超过发布版本总数的一半。实验结论及理论分析将为克隆代码的后续研究及克隆代码的维护与管理提供有力支持。

关键词：

克隆代码；主题建模；软件演化；演化模式；克隆谱系；软件维护

中图分类号： TP311.5； TP18 文献标志码：A

0引言

克隆代码（Code Clone）是指软件系统中一些具有相同或者相似的语法或语义特征的代码片段。克隆代码在软件系统中普遍存在，并且与软件工程领域中的各类研究问题密切相关。软件单一版本中的基础性克隆代码数据已经难以呈现克隆代码在软件演化过程中的变化情况，因此，需要对软件中的克隆代码进行演化跟踪并分析演化情况，从而获得更全面的信息，为软件开发及维护提供更多帮助。

当前的克隆谱系构建方法存在一些不足之处，例如克隆演化模式单一、克隆谱系构建方法复杂、能够分析的克隆类型及编程语言不全面等。本文提出了新的克隆演化模式、克隆演化特征以及克隆谱系的自动化构建方法。以区分视角的方式更加全面地分析了克隆代码的演化模式，利用代码主题信息确立版本间克隆代码映射并最终构建克隆谱系。本文研究结果将为软件开发、软件维护、软件重构及克隆管理等工作提供参考。

1相关工作

1.1克隆代码简介

在软件开发及维护过程中，由于程序员经常使用“拷贝/粘贴/修改”的开发方式、使用相同或相似的应用程序接口（Application Program Interface， API）及算法等因素，导致软件系统中存在大量相同或相似度非常高的代码片段，称为克隆代码。在该研究领域，经过学者们多年研究，已经达成了克隆代码至少应该被检测的基本共识。

克隆代码的研究工作最早可追溯到20世纪90年代，随后，该研究领域受到越来越多国内外相关研究者的高度关注，并在克隆检测、克隆演化、克隆分析以及克隆重构等方面产生了大量研究成果[1]。

在该研究领域，克隆代码以Type1、Type2、Type3和Type4的方式分类最为流行[2]。Type1指除空白符与注释变化外完全相同的代码段；Type2指除空白符、注释、标识符、类型及常量的替换外句法结构完全相同的代码段；Type3是指除空白符、注释、标识符、类型替换外，句法结构基本相同，但含有少量语句增加、删除或修改的代码段；Type4克隆代码则为功能相似或相同但句法结构不同的代码段。根据克隆代码检测的反馈粒度，相关工作通常以克隆对或克隆群（也称克隆集合、克隆类）为基本单位进行克隆代码的研究。克隆对是指存在克隆关系的一对代码片段。克隆群代表一些克隆代码的集合，同一克隆群内的任意两个代码片段可以构成克隆对，不同克隆群之间的克隆代码通常不具有克隆关系。

图1呈现了来自同一个克隆群的三段克隆代码CF1、CF2和CF3。由克隆代码类型的定义可知，CF1与CF2为Type2克隆关系、CF2与CF3为Type2克隆关系、CF1与CF3也构成了Type2克隆关系。在这三段代码中，只有函数名以及一处标识符不同，所以三者之间均可构成Type2类型克隆对。

1.2克隆演化与克隆谱系

随着软件需求的不断增加，软件需要不断升级，软件中的克隆代码也可能随着软件演化而发生改变。在分析克隆代码为软件带来的影响时，不但要研究软件单一版本中的克隆，还要研究克隆代码以时间为序的演化问题[3-4]。基于此，一些研究者从宏观上分析了克隆代码的数量或密度随着多版本演化的变化情况[5-6]，从微观上利用演化模式来研究克隆代码的演化过程也受到研究者的广泛关注[7]。

Kim等[8]在2005年最早提出了克隆谱系的概念，并用克隆谱系抽取工具对克隆代码的演化进行分析[9]。随后，借助于克隆谱系研究克隆代码便在该领域成为了一种基本研究方法。例如，Zibran等[10]借助克隆谱系对软件演化过程中克隆代码的去除活动进行了研究。Saha等针对17款C、C++、Java及C#语言的开源软件进行了关于克隆谱系的实证研究[11]，并发现大部分克隆群在演化中要么不发生句法上的不一致改变，要么会发生一致性的改变。虽然克隆谱系已经被广泛用于克隆代码演化研究，然而针对克隆谱系构建方法本身的研究却相对较少。目前构建克隆谱系的方法主要可以分为4种，分别为基于版本控制系统（Control Version System， CVS）或SVN（Subversion）、基于增量克隆检测、基于克隆区域描述符（Clone Region Descriptor， CRD）以及基于相似度距离函数。

基于版本控制系统的方法通常借助SVN或CVS中的修改日志来计算相邻版本间克隆代码的变化情况实现对克隆代码进行演化跟踪，进而按照时序关系合并修改信息，得到克隆谱系。由于该方法以某一选定版本中的克隆代码作为起源并进行跟踪，很难处理软件后续版本中新增的克隆代码。

Gde等[12]使用增量克隆检测技术构建了克隆谱系，然而该方法只适合处理给定版本的软件，当有新的版本加入后，整个方法需要重新执行，时空消耗均非常高，所以该方法难以灵活应对具有新增版本的克隆谱系构建工作。

基于相似度距离函数的方法通常要结合抽象语法树（Abstract Syntax Tree， AST）、Token等代码中间表示形式，该类方法的核心算法时空复杂度相对偏高。Bakota[13]提出了一种的基于相似度距离函数并结合抽象语法树的克隆谱系构建方法，并针对软件的多个版本进行了克隆代码的演化研究。Ying等[14]提出了基于Token与源码相结合的克隆谱系构建方法，但该方法只能在Linux系统下处理C语言的Type1和Type2类型的克隆代码，对其他程序设计语言或其他克隆类型的演化研究存在着很大的局限性。Saha等[15]提出了基于文本并结合代码位置信息的方法构建了克隆谱系。该方法首次对Type3克隆代码进行了克隆谱系的构建研究，然而由于该方法需要处理文件位置变化、方法重命名等问题导致了构建方法较为复杂。

基于CRD的方法在构建克隆谱系时也存在一定的局限性，如果代码某些部分（如循环终止条件、代码的嵌套结构、条件语句的分支谓词等）发生变化，则可能会导致CRD的失效，这将严重影响克隆谱系构建的全面性和准确性。Meng等[16]基于CRD确立了相邻版本间克隆群映射关系，然后基于二元关系合成方法研究了克隆谱系的构建。

1.3克隆演化模式与演化特征

克隆演化模式从微观上体现了克隆代码随着软件不同版本的演化而发生的变化情况。虽然不同研究问题针对克隆演化模式的分类有所不同，但对相同或相似的克隆演化行为的分类大致相同。根据匹配粒度及版本长度，可以将克隆演化模式大体上分为3类。

第1类是克隆群在两个版本间的演化模式。Kim等[8]最早开展了相关研究，将演化模式分为无变化、增加、去除、一致变化、不一致变化和位移6种模式。Ying等[14]以Kim等[8]的演化模式概念集为出发点，识别了除位移模式以外的其他5种模式。

第2类是克隆片段在两个版本间的演化模式。Bakota等[17]介绍了4种不同的克隆片段演化方式，包括消失克隆实例、发生克隆实例、移动克隆实例以及迁移克隆实例。

第3类是研究克隆群在多个版本中的长期演化模式，包括延迟传播（Late Propagation， LP）模式以及独立演化模式等[18-19]。

克隆代码演化特征可以从生命周期以及谱系结构等视角对克隆代码的演化过程进行分析。各类演化模式出现的时间及位置信息可以反映克隆代码的变化方式。克隆代码的演化特征将为克隆演化分析提供最基本的参考信息。长期性的克隆演化模式与演化特征将为软件后期开发及维护活动提供更多具有决策性的意见。

1.4基于主题建模技术研究软件演化

近年来，主题建模技术已不断地应用于软件工程领域。Kuhn等[20]将主题建模技术应用于代码分析，并尝试从中挖掘出代码的功能性主题；Thomas等[21]验证了利用主题建模技术进行软件演化分析是具有可行性的，并利用主题建模技术研究了软件的演化情况[22]；Asuncion等[23]将主题建模技术用于软件的可追踪性研究；金靖等[24]运用潜在狄利克雷分配（Latent Dirichlet Allocation， LDA）模型识别代码功能以支持软件开发人员对代码进行良好的理解与复用；张瑞霞等[25]通过LDA主题模型针对软件相邻版本中的克隆群进行了映射研究，但并未构建克隆谱系也未深入分析克隆代码的演化模式和演化特征；Phan等[26]分析比较了LDA、概率隐语义分析（Probability Latent Semantic Analysis，PLSA）、潜在语义分析（Probability Semantic Analysis，LSA）等主题模型，并证明了LDA在挖掘文档潜在语义时比其他模型表现更佳。

1.5小结

通过分析、总结上述相关研究现状可知，现有克隆谱系构建方法主要存在以下不足：

1）依赖代码位置信息且构建流程相对繁琐。

2）无法处理软件在演化过程中新增的克隆代码。

3）代码语句格式对克隆谱系的构建存在影响。

4）不能处理Type3及Type4克隆代码。

5）可移植性较差、编程语言不可扩展。

6）严重依赖特定的克隆代码检测工具。

本文提出了一种基于主题建模技术的克隆谱系构建方法，通过映射克隆代码的主题信息进行克隆谱系的构建。与基于相似度距离函数的方法相比，本文方法不需要代码的中间表示形式（如Token、AST），流程相对简单；与基于增量克隆检测的方法相比，本文针对新增版本的克隆谱系构建而言具有良好的可扩展性。因为本文方法只需根据增版本中克隆代码的主题信息即可扩展原有克隆谱系，而基于增量克隆检测的方法则需要重新执行整个构建过程；与基于CRD的方法相比，本文方法直接利用主题信息构建谱系，避免了由于循环终止及条件语句的变化等情况造成的相邻版本间克隆代码映射失败或错误的问题。此外，由于本文借助于代码的主题信息，所以能支持多种程序设计语言及多种代码粒度的克隆谱系构建研究，而且能够有效处理Type3甚至Type4克隆代码，而不仅局限于Type1和Type2克隆。本文方法不依赖任何特定的克隆代码检测工具，只需运用主题模型从克隆检测结果中抽取主题即可。本文将在原型系统的实现中将克隆代码检测工具视为插件，以支持多种克隆检测工具。

自Kim等[8]提出克隆谱系概念以及克隆演化研究中所使用的6种模式后，该领域研究者大多以其作为基准框架进行克隆代码的演化研究，即便有新的模式提出也只是针对部分或个别演化现象而言，例如LP模式[18-19]。

通过分析现有研究中的克隆演化模式可以发现，前期研究者们不区分视角地分析各种演化模式，例如Kim等[8]提出的6种模式中，无变化、一致变化和不一致变化是针对克隆代码的数量和文本内容而言的，而位移则是针对代码位置的变化而言，增加和去除模式则是针对克隆群内代码片段数量而言的。这些演化模式属于不同的视角，但某些视角中显然缺少一些演化模式来解释不同的演化现象，例如Kim等[8]的模式中虽然包含了克隆群内代码片段数量的增加与去除，但并未包含片段数量不变这一模式，这个模式与其提出的无变化模式是不冲突的，因为一个克隆群内的克隆片段数量不变的情况下，克隆代码的文本内容是完全可以发生改变的。

本文区分视角地重新定义了传统意义上的克隆演化模式，并提出了新的演化模式，将从克隆群生存情况、克隆群内片段数量与克隆代码片段内容这三个视角来分析克隆代码的演化模式，这使得不同演化模式之间的区别更加清晰，模式识别的方法也将会变得简单。

通过分析1.4节的相关研究可知，基于主题建模技术的软件演化分析已经取得了很大的成功，并且这些研究问题充分证明了主题建模技术是可以用于软件工程领域中的众多问题，包括软件的理解与演化分析等。LDA已经被广泛并成熟地运用在人工智能及自然语言处理等领域，而且文献[20-26]可以充分说明利用LDA进行软件演化分析是可行的。本文将使用LDA对克隆代码进行主题建模分析，从而根据克隆代码的主题信息进行克隆群映射、演化模式识别及克隆谱系构建等工作。

2演化模式识别及克隆谱系构建方法

本文的克隆谱系构建方法主要分为5个核心步骤：

第1步针对软件多版本分别进行克隆代码检测并获取克隆检测结果；

第2步以克隆群为基本单位进行克隆代码的主题信息抽取；

第3步进行克隆群以及克隆片段的映射；

第4步识别各类克隆演化模式、分析克隆演化特征；

第5步合并映射结果与克隆演化模式，完成克隆谱系的构建工作。

主要流程如图2所示。

2.1克隆检测及代码主题抽取

克隆检测是克隆代码研究领域中的基础性、必要性工作，克隆检测的反馈结果能为克隆代码分布分析、演化分析、重构分析等研究提供最基本的数据支持。本文借助现有克隆代码检测工具对软件的多个版本进行克隆代码检测。选取了CloneDetective[27]以及本文的前期研究开发的克隆代码检测工具FClones[28]作为本文实验时所使用的克隆代码检测工具。CloneDetective能有效检测Java语言的Type1、Type2和Type3克隆代码，FClones能有效检测C语言的Type1、Type2和Type3克隆代码。这两款工具的克隆代码检测结果将为本文的克隆谱系构建研究提供基础性数据。

当软件多个版本的克隆检测完成后，每个版本中都会含有一定数量的克隆群，而相邻版本间的克隆群映射是构建整个克隆谱系工作中不可缺少的部分。在软件的每个版本中，由于同一克隆群内的克隆代码有较高的语法及语义的相似性，而不同克隆群之间克隆代码的相似程度却较低。所以，相邻版本中对应的克隆群之间的主题信息具有较高的相似性，而非对应的克隆群之间的主题信息差异较大。基于此，本文以克隆群为基本单位进行克隆代码的主题信息抽取，并基于主题的相似性进行版本之间的克隆群映射。

本文将使用LDA主题模型对克隆代码进行主题信息抽取。抽取主题之前需对代码进行预处理，方法参考了文献[24]中使用的静态分析以及切词方法。经过切词后还需针对部分单词进行过滤处理，因为初步切词的结果中会包含大量的编程语言关键字、Java开发工具包（Java Developers Kit， JDK）中的类名和接口名及英文中常见的停用词。过滤之后的结果作为主题模型的输入数据，然后利用LDA对克隆群抽取主题。抽取结果中包含了不同克隆群主题对应的主题词，本文以克隆群主题词集合的相似性作为克隆群映射的基本依据。

2.2克隆群映射

针对版本间克隆群主题词集合的相似性计算问题，本文使用Jaccard相似度计算模型，之所以采用此计算模型是考虑了每个克隆群的主题词集可视为一个集合，因此可以利用该模型计算两个克隆群主题词集之间的相似程度。Jaccard相似度模型计算两个集合A与B的相似度如式（1）所示：

JaccardSim（A，B）=A∩B/A∪B（1）

针对多版本克隆群映射问题，本文设计了映射算法，如算法1所示。算法思想为：按照版本时序关系，每个克隆群在后一版本中先寻找一个最相似的克隆群作为后继进行映射，此为第一轮映射。之后，对于任意一个没有前驱的克隆群，在其前一版本中寻找前驱，如果找到满足条件的克隆群则进行映射；对于任意一个没有后继的克隆群，在其后一版本中再次寻找后继，如果找到满足条件的克隆群则进行映射，此为第二轮映射。第二轮映射完成后，对于任意一个无后继的克隆群，从其下下版本开始，找一个与其最相似的而且无前驱的克隆群，如果找到满足条件的克隆群则进行映射并结束寻找，此为第三轮映射。至此所有克隆群映射工作完成。

算法1Clone Group Mapping。

有序号的程序——————————Shift+Alt+Y

程序前

1）

for each version∈versions do

2）

for each cg∈version do

3）

cg.pre=[]，cg.next=[]

4）

end for

5）

end for

6）

for each version∈versions do

7）

for each cg∈version do

8）

cg.next.append（cg.findNext（version.next））

9）

end for

10）

end for

11）

for each version∈versions do

12）

for each cg∈version do

13）

if cg.pre==[] then

14）

cg.pre.append（cg.findPre（version.pre））

15）

end if

16）

end for

17）

end for

18）

for each version∈versions do

19）

for each cg∈version do

20）

if cg.next==[] then

21）

cg.next.append（cg.findNext（version.next））

22）

end if

23）

end for

24）

end for

25）

for each version∈versions do

26）

for each cg∈version do

27）

nextVersion=（version.next）.next

28）

while cg.next==[] and nextVersion do

29）

if cg.findNext（nextVersion） then

30）

break

31）

nextVersion=nextVersion.next

32）

end if

33）

end while

34）

end for

35）

end for

程序后

在算法1中，Vi和Vi+1分别代表软件中的两个相邻版本，CGi， j代表版本Vi中编号为j的克隆群，CGi， j.pre记录CGi， j映射到了前一版本（或更前版本）中对应的克隆群编号信息。CGi， j.next记CGi， j映射到了后一版本（或更后版本）中对应的克隆群编号信息。在映射算法中，首先将当前版本Vi中的所有克隆群CGi， j的后继初始化为空，将后一版本Vi+1中所有克隆群的前驱初始化为空，然后再进行三轮映射。findNext和findPre函数分别代表在某一版本中为当前克隆群寻找后继克隆群、前驱克隆群并返回相应的克隆群的编号信息。version.pre和version.next分别代表当前版本的前一版本及后一版本。

在算法1中，相邻版本间克隆群映射的条件相对严格，对于当前版本Vi中的任一克隆群CGi， j而言，在后一版本Vi+1中映射到的克隆群CGi+1，k是所有Vi+1的克隆群中与CGi， j的主题相似度最高的，而不是仅仅在满足相似度阈值的情况下即可进行映射。这样的映射规则保证了每一对映射包含的两个克隆群都有非常高的主题相似度。克隆群映射过程中，主题相似度阈值直接影响映射结果，参照了前期研究[25]中采用的克隆群映射相似度阈值，本文将主题相似度阈值暂设为0.8，但该值并非固定，本文将在原型工具的实现以及后续研究中对该阈值的设定问题进行更详细的研究。

克隆群映射完成后，除起始本中的克隆群没有前驱、最终版本中的克隆群没有后继以外，如果某一克隆群未能找到其前驱，则说明该克隆群是新增克隆群，如果某一克隆群未能找到其后继，则说明该克隆群在软件演化的过程中可能被移除。克隆群的前驱与后继信息将有助于判断克隆代码的演化模式类型。

图3呈现了某款软件多版本中的部分克隆群映射效果。图中每一竖排圆点代表一个版本中的不同克隆群，每条线段代表映射关系，不同灰度和大小的圆形及线段代表了不同的映射关系与演化模式。

2.3克隆片段映射

由于单纯的克隆群映射还不能够呈现更多的克隆代码演化信息，例如不一致变化等。所以，在相邻版本间的克隆群映射完成后，还需要针对两个对应克隆群内的克隆代码片段进行映射，以便识别出更多的克隆代码演化模式与演化特征。由于存在映射关系的两个克隆群内的克隆代码片段之间的相似程度相对较高，导致代码主题信息区分度不大，所以片段映射时不能再次利用代码的主题信息进行匹配。

在Ying等[14]及Saha等[15]的克隆谱系构建研究中，克隆片段的映射主要参考了位置信息，例如Saha等[15]在映射克隆代码片段时，如果其所在的文件名、函数名及起止行号不变，在不匹配克隆代码内容的情况下就直接进行映射。该类方法虽然能够较快地进行片段映射，但针对函数重命名以及代码位置变化时，容易造成映射错误。如果文件名、函数名等属性不一致时，则还需要根据代码文本内容或中间形式进行克隆片段的映射。如果不考虑文件的位置属性而仅仅通过代码相似性来映射克隆片段，则可能由于克隆代码的位置改变而造成映射的偏差，所以为了综合考虑克隆代码片段的位置信息以及克隆代码本身的相似性，本文针对克隆代码片段映射任务定义了4种距离。

1）目录距离。两段克隆代码所在目录的相似程度。本文考虑了软件演化过程中某些路径名可能出现较小的修改，例如将某一目录名“temp”改为“tmp”等，所以计算目录相似度时不宜采用严格的字符串匹配。本文采用编辑距离来衡量两个目录的距离，这样避免了由于个别目录名修改而造成映射错位等问题。与Ying等[14]的克隆片段映射方法相比，本文考虑了目录名可能修改的情况，所以对位置属性的处理更为合理。

2）文件名距离。与目录距离的定义类似，文件名距离是指文件名之间的编辑距离。之所以将目录距离与文件名距离分开考虑是因为很大一部分克隆代码会来自于同一源代码文件，所以利用文件名距离辅助判断克隆代码片段映射关系可以大大减少其他距离的计算量。

3）签名距离。在本文中，签名是指能够代表一段代码的一个字符串，例如函数的签名可以为函数名和参数列表。签名距离为两个代码段对应的签名之间的编辑距离，签名距离可以在路径距离及文件名距离都相同时进一步来判断克隆代码之间的相似度，因此可以用于克隆片段映射。

4）文本距离。文本距离的计算首先将源代码视为字符串，进而通过计算字符串的编辑距离得出克隆代码的文本距离。当待映射的克隆片段之间具有相同的目录距离、文件名距离、签名距离时，利用文本距离可以最终判断克隆片段的映射关系。本文不仅仅使用文本距离进行作为克隆片段的映射依据是考虑了片段映射的效率问题，前3种距离的计算量相对较少，可以大大节省克隆片段映射的时间。

为了综合利用上述4种距离属性进行映射，制订了以下具有优先级的映射规则进行克隆代码片段映射，假设相邻版本中已经映射的两个克隆群分别为CG与CG′。它们所包含的克隆片段的映射步骤为：

步骤1对于克隆群CG中的任一克隆片段CF与CG′中的所有克隆片段计算目录距离，CF选择与其目录距离最小的克隆片段进行映射，已经映射的克隆片段不能再次参与映射。

步骤2如果目录距离相等，CF选择与其文件名距离最小的克隆片段映射，已经映射的克隆片段不能再次参与映射。

步骤3如果文件名距离相等，CF选择与其签名距离最小的克隆片段映射，已经映射的克隆片段不能再次参与映射。

步骤4如果签名距离相等时，CF选择与任意一个文本距离最小的克隆片段映射，已经映射的克隆片段不能再次参与映射。

克隆片段的映射方法之所以不再使用类似克隆群的映射方法是考虑了克隆片段可能存在新增、去除等情况，所以可能存在克隆片段映射不完全的情况，即部分克隆片段未能与相邻版本间的其他克隆片段建立映射关系，但这类信息将有助于克隆群容量演化模式及克隆代码片段内容层面演化模式的分析。

2.4克隆演化模式及其识别

当相邻版本间克隆群映射完成后，即可识别克隆群层面的演化模式。针对克隆群层面演化模式主要涉及到克隆群本身的生存情况以及群内包含克隆代码片段的数量的变化情况。

与其他研究方法相比，本文将克隆群与克隆片段的演化模式分开研究使得各种模式具有更加清晰的视角。Kim等[8]将演化模式分成6种，与本文所用模式不同的是，Kim等[8]的方法考虑了位移模式，即克隆代码的位置发生了改变。本文方法更关注克隆群及克隆代码内容上的改变，所以不考虑位移模式，取而代之，本文将简单模式、复活模式与合并模式引入到演化模式概念集中。复活模式的产生意味着克隆代码存在延迟传播现象的可能。延迟传播是指一些克隆代码在演化过程中出现过内容的不一致改变而分离，而在后续版本中又重新变为克隆关系。克隆代码的延迟传播研究将有助于分析克隆代码与Bugs的关系[18-19]，所以复活模式值得深入研究。

本文针对克隆群演化而言主要研究两种视角下的九种演化模式，分别为克隆群生存视角下的6种模式包括：新生模式、消失模式、分支模式、合并模式、复活模式、简单模式；以及克隆群内片段数量视角下的3种模式，包括：增加模式、去除模式和保持模式。每种模式的基本定义如下：

新生模式当前版本中的某一克隆群与前续版本中的任何克隆群未能建立映射关系，即该克隆群无前驱。

消失模式当前版本中的某一克隆群与后续版本中的任何克隆群未能建立映射关系，即该克隆群无后继。

分支模式当前版本中的某一克隆群在后一版本中与多个克隆群具有映射关系，即该克隆群具有多个后继。

合并模式当前版本中的某一克隆群在前一版本中与多个克隆群具有映射关系，即该克隆群具有多个前驱。

复活模式某一克隆群在演化过程中先经历消失模式，而后又经历新生模式，即该克隆群“死而复活”，为复活模式。

增加模式当前版本中的某一克隆群与前一版本中对应克隆群相比，包含克隆代码片段的数量有所增加。

去除模式当前版本中的某一克隆群与前一版本中对应的克隆群相比，包含克隆代码片段的数量有所减少。

保持模式当前版本中的某一克隆群与前一版本中对应的克隆群相比，包含克隆片段的数量保持不变。

简单模式当前版本中某一克隆群有唯一的前驱克隆群和唯一的后继克隆群，而且前驱和后继克隆群都存在于相邻版本中，演化过程相对简单，没有发生过新生、消失、合并、分支以及复活演化模式。

克隆群映射完成后，克隆群层面的演化模式识别即可进行。由各类模式的定义可知，如果克隆群无前驱则发生了新生模式；如果克隆群无后继则发生了消失模式；如果克隆群有多个前驱则发生了合并模式；如果克隆群有多个后继则发生了分支模式；如果克隆群先发生了消失模式而后又出现新生模式则产生了复活模式；其余模式均为简单模式。

图4呈现了某软件系统6个连续版本中的部分克隆群的演化情况。其中：矩形代表软件系统的版本，圆形代表克隆群，箭头代表映射关系。由映射信息可知，B1和C3克隆群均发生了分支模式（例如B1分化为C1和C2），B2克隆群发生了消失模式，C4克隆群发生了复活模式，E1克隆群发生了合并模式，其余均为简单模式。

图5呈现了某克隆群CG在4个版本中的演化过程；同时呈现了克隆群内克隆片段数量的变化情况，其中圆形代表克隆群CG，正方形代表克隆代码片段。显然，CG在V1到V2的演化过程中增加了克隆片段，即发生了增加模式；在V2到V3的演化过程中去除了克隆片段，即发生了去除模式；在V3到V4的演化过程中，群内片段数量保持不变，即属于保持模式。

此外，本文还研究了3种克隆代码片段内容层面的演化模式，包括：无变化模式、一致变化模式和不一致变化模式。每种模式的基本定义如下：

无变化模式在相邻版本间对应的克隆群内，所有参与了片段映射的克隆代码片段的内容都未发生改变。

一致变化模式在相邻版本间对应的克隆群内，所有参与了片段映射的克隆片段的内容作了一致改变。

不一致变化模式在相邻版本间对应的克隆群内，所有参与了片段映射的部分或全部的克隆代码片段内容做了不一致改变。

克隆片段演化模式与克隆群演化模式不同，克隆片段模式仅仅针对克隆片段内容层面在相邻版本间的演化而言。本文将克隆片段演化模式分为3种，但这3种模式与Kim等[8]提出的相关演化模式存在差异。在本文中，这3种模并不涉及克隆群层面的演化，而在Kim等[8]的研究中，这3种模式既涉及到克隆群层面的演化同时又涉及到克隆代码内容层面的演化，视角混淆。本文将这3种模式重新定义，视角明确，有较好的层次感，更加清晰，易于理解。

图6呈现了某克隆群CG内的克隆代码片段在4个相邻版本间的演化过程，其中圆形代表克隆群，正方形代表克隆代码片段，不同填充颜色及边框代表克隆代码片段内容发生了不同的改变。在V1到V2的演化过程中，群内所有克隆代码片段发生了内容上的一致变化；在V2到V3的演化过程中，克隆代码片段发生了内容上的不一致变化；在V3到V4的演化过程中，也发生了内容上不一致变化，而且还增加了克隆代码片段。由此可见，不同视角的克隆演化模式可能会同时发生，所以区分视角的克隆演化模式分析是十分必要的，这将为克隆演化的后期研究提供更加清晰和明确的思路。

针对上述3种克隆片段演化模式，本文先识别无变化模式，即对应克隆群内的所有参与映射的克隆代码片段内容不变。这种模式识别较为简单，可以将代码元素的变化情况作为参考，求出对应克隆片段源代码的差异，从而确定是否改变。如果在对应克隆群内所有参与映射的克隆代码内容不变，则为无变化模式。识别无变化模式完成后，可识别一致变化和不一致变化模式。如果参与映射的部分或全部克隆代码内容发生了改变，先求出所有对应克隆代码片段的差异，然后计算这些差异的相似情况。如果所有差异相同，则为一致变化模式，否则为不一致变化模式。本文将借助Diff工具对克隆代码片段内容层面的演化情况进行分析，从而给出克隆代码片段的演化模式。

2.5克隆演化特征

克隆代码映射关系中包含了大量的克隆代码演化信息。基于已构建的克隆代码映射关系，本文从克隆演化模式、克隆生命周期以及克隆代码数量增长率等方面选取克隆演化特征进行分析。克隆演化模式提供了丰富的演化信息，便于研究和理解克隆演化现象。克隆生命周期能够反映克隆群在演化过程中所经历的版本数量。此外，克隆演化特征还可用于克隆代码相关问题的预测研究，例如可用代码的有害性及稳定性预测等问题。

2.5.1演化模式的数量特征

通过对各类克隆演化模式进行统计，可以发现克隆群在软件的演化过程中主要进行了哪种改变方式。统计某一克隆群经历各种演化模式的数量可以宏观地了解克隆群的演化情况。演化模式的数量特征可以从侧面反映一款软件中大部分克隆代码是否稳定，如果简单模式与无变化模式数量较多，则说明大部分克隆代码的演化相对稳定。而其他模式的数量较多，则可以反映某些克隆群在演化过程中比较多变，稳定性较差。在研究克隆代码的稳定性或有害性时，克隆代码所经历的某些演化模式可能作为判断其性质的决定性因素。例如，如果某个克隆群在演化过程中频繁发生一致或者不一致变化模式，则该克隆群必然占据了过多的维护成本，可以认为其有害性较强，建议优先去除或者重构，因此，克隆演化模式的数量特征可以为克隆代码的其他相关研究工作提供良好的数据支持。

2.5.2克隆代码的生命周期

对于一个克隆群而言，其所经历的版本数量就是其生命周期。克隆群的生命周期可以明确反映克隆群在演化过程中存在时间的长短。对于生命周期较长而且演化相对稳定的克隆群，可以建议开发或维护人员进行简单的跟踪。对于生命周期比较短暂的克隆，通过分析其引入因素及去除因素，可以总结一些有意义的开发及维护策略作为经验，从而为后期的开发及维护提供参考，避免再次引入该类克隆代码，从而降低开发及维护的成本。

2.5.3克隆代码数量结构特征

在软件的演化过程中，克隆代码片段可能被增加或去除，因此，克隆群以及克隆代码片段数量的增长比可以直接反映克隆代码整体数量结构的变化情况。克隆群与克隆代码片段的数量比则可以直接反映克隆代码在演化过程中整体的繁殖量。克隆代码的数量结构特征可以在宏观上反映软件系统中克隆代码所占比重的变化情况。在实际的软件开发或维护环境中，如果发现克隆代码的整体繁殖能力越来越强，则可以考虑重构或去除某些克隆代码，从而为后续的开发及维护工作减轻压力。

2.6克隆谱系构建

克隆谱系是指克隆代码在软件多个版本演化过程中变化情况的记录信息。将克隆谱系作为克隆代码分析的基本数据，可以进行更多克隆代码相关问题的研究。当相邻版本间的克隆群映射、对应克隆群之间的克隆代码片段映射、克隆演化模式识别及克隆演化特征分析完成后，按照版本的时序，将所有演化信息合并得到克隆谱系。从宏观结构层面来看，克隆谱系主要是根据克隆群映射关系连接而成的拓扑结构。克隆谱系反映了克隆代码在软件的演化过程中是如何产生、繁殖和去除的。克隆谱系中的每个克隆群都记录了对应的演化模式信息，其内部包含的克隆代码片段也各自记录了微观层面的片段映射关系以及片段演化模式。

本文克隆谱系结构与前期相关研究中的克隆谱系结构明显不同。在前期相关研究中，其克隆谱系结构主要为克隆群粒度层面的树形结构，而本文构建的克隆谱系不再为树形结构，而是拓扑结构。在前期相关研究中，克隆演化模式的概念几乎全部来自于Kim等的研究[8]，仅限于大约6种模式，而且各个模式之间不分视角，结构不清晰。此外，前期相关工作也并为分开视角地考虑到克隆群的合并模式与复活模式，所以其克隆谱系的构建工作中还关注了克隆直系与克隆家系的概念。克隆直系描述了某一克隆群的单支演化过程，克隆家系描述了起源于同一个克隆群的所有克隆直系的演化过程。虽然本文研究方法拓展了传统意义上的克隆谱系结构，但是克隆直系与克隆家系的子结构仍然可以在本文方法构建的克隆谱系中找到，因为并非所有克隆群都经历合并或者复活模式。除了克隆直系与克隆家系以外，本文将引入克隆族系的概念，克隆族系描述了起源于或合并于不同克隆群的所有直系克隆及家系克隆。由于合并及复活演化模式的存在，某一些克隆群的起源并非前续版本中的单一克隆群，而可能是经由多个克隆群合并之后演化而来，克隆族系将更加有助于分析克隆群的合并或重构问题。

图7展示了克隆谱系的基本结构，其中圆形代表克隆群，正方形代表克隆代码片段，箭头代表映射关系，不同的灰度及字母分别代表了克隆代码的模式及编号。

3实验与分析

3.1数据来源

本文分别针对4款开源软件的多个发布版本进行了克隆谱系的构建研究。使用了CloneDetective[27]和FClones[28]克隆代码检测工具以函数粒度进行克隆检测。4款开源软件的基本信息如表1所示。本文所选取的开源软件常被软件工程领域研究者作为基础的实验数据使用，具有一定代表性。例如Lin等[29]在研究克隆代码模式时使用了jedit以及jhotdraw等开源软件作为研究对象。针对这些开源软件的实验数据能为本文的后续对比研究作一定的铺垫。选取这些开源软件还考虑了不同程序设计语言及不同功能的软件，而且这些开源软件一直被良好地开发与维护，拥有较多的发布版本，含有丰富的克隆代码。能为克隆演化研究提供基础性数据。

3.2实验结果及分析

实验中，在相邻版本间克隆群映射时，主题相似度阈值设定参照了前期相关研究[25]，将阈值暂设为0.8，但是该阈值并非固定不变，本文将在后续研究中对此值的选取问题进行更为细致深入的研究。通过对4款软件系统构建克隆谱系，得出了每款软件中的克隆群在演化过程中表现在生存层面的演化模式数量，各类演化模式数量统计如表2所示。

由表2可知，本文新提出的克隆演化模式在克隆代码演化过程中确实存在，而且占有一定数量。例如，在jhotdraw的16个发布版本的演化过程中，出现了3次合并模式；在ffmpeg的29个发布版本中，出现了8次合并模式以及20次复活模式。复活模式将为克隆代码与Bugs的研究提供更多参考信息，因此本文所提出的新的演化模式具有更深层次的研究意义。

此外，实验还统计了克隆群在容量层面的演化模式，包括克隆群内片段数量的增加、去除以及保持3种模式，如表3所示。由表3可知，克隆群在容量层面发生克隆代码片段增加及去除模式也出现了多次，这说明了克隆代码在演化过程中是非常可能再次被复制重用或删除。在jhotdraw及ffmpeg中，克隆群容量发生多次增加及去除模式，而在jedit及bluefish中该类演化模式数量则相对较少。由此可知，各类演化模式在不同功能、不同程序设计语言、不同开发团队、不同规模的软件系统中均有可能发生。

除了分析粗粒度的克隆演化模式以外，本文还针对细粒度的克隆代码演化情况进行了分析。从克隆代码片段的内容层面，分析了同一克隆群内的克隆代码片段在版本之间的变化情况。包括无变化模式、一致变化模式和不一致变化模式。此层面的各类演化模式数量如表4所示。由表4可知，绝大多数（平均约90%）克隆克隆代码在演化过程中基本不变；平均约10%的克隆代码发生了改变，而发生一致改变的克隆代码较多，平均约为6.5%，发生不一致改变的克隆群最少，平均约为4.4%。这也说明了绝大多数克隆代码在演化过程中不会被修改，而被修改的克隆代码超过一半被一致性地修改了，仅有一少部分被不一致地修改。本文将在后续研究中继续关注引起克隆代码不一致性修改的原因及其为软件开发及软件维护带来的利弊。

本文除了关注克隆代码演化模式之外，还统计了克隆群的生命周期，如表5所示。由表5可知，大部分克隆代码在软件演化过程中并未生存较长时间，而仅有一小部分克隆代码在演化过程中一直稳定地生存下来。生存时间不超过软件整体生命周期40%的克隆群数大约为总数的67%。生存时间超过软件整体生命周期80%的克隆群数大约为总数的6%。剩余部分克隆群的生命周期约占软件整体生命周期的27%。

克隆代码在演化过程中会伴随着克隆群的消失与新生模式，但克隆群及克隆代码片段的数量会随着软件演化的推进而增多，表6给出了克隆群数量及克隆代码数量在软件版本演化过程中的数量增长比率。

由表6可知，这4款开源软件中的克隆代码几乎全部以增加克隆代码数量的方式演化。克隆群数量平均增长率约为24.1%，克隆代码片段数的平均增长率约为17.4%。也有个别相邻版本间存在着克隆群及克隆片段减少的情况，但这种情况比较少见。出现克隆代码数目减少的原因可能包括克隆检测工具阈值的固定性、克隆代码修改量较大、克隆代码被重构等。

克隆代码的数量结构说明克隆代码在软件开发、维护、升级及重构等活动中都扮演着不可或缺的角色，占据了软件整体代码的一定比例。克隆代码的跟踪、维护及管理将对软件开发活动和软件质量产生积极性的影响。

4结语

本文基于软件多版本演化，根据克隆代码主题信息构建版本间克隆代码的映射关系，为演化过程中的克隆代码添加演化模式，分析演化特征并构建克隆谱系。

本文传承了利用克隆代码主题信息进行克隆群映射的工作，并继续开展了克隆演化模式识别、演化特征分析以及克隆谱系构建的工作。发现了大部分克隆代码（约90%）在演化过程中表现得相对稳定，但仍然有部分克隆代码在演化过程中比较多变，稳定性较差。另外，本文还通过实验验证了新提出的克隆演化模式在克隆代码演化过程中确有发生。还发现了大部分克隆代码的生命周期并未超过软件演化整体周期的50%。本文研究结论将为克隆代码演化分析、克隆代码的维护管理及重构任务提供更多参考信息。

本文的研究内容与实验依然存在一些不足之处，包括：Type3克隆代码内容层面的演化模式还需要进一步深入研究；一致变化模式及不一致变化模式的判断需要更加详细合理的标准；克隆群映射准确性与全面性的评价需要研究；克隆谱系结果未进行良好的可视化等。

本文将在后续研究中陆续改进、完善不足之处，包括：选取更加适合分析克隆代码的主题模型；为克隆群和克隆代码片段映射工作构建测试集和自动化的评价框架；将克隆谱系的结果进行良好的可视化；研究各种演化模式与Bugs的关系；为克隆代码构建本体模型以及检索系统；为克隆代码的维护与管理提供更多帮助。此外，将在下一步研究工作中，进一步考虑将所提方法与已有的一些经典的研究工作进行深入的对比分析；同时，分析不同方法中某些阶段不同算法的选择或不同参数的取值对最终结果的影响。

参考文献：

[1]

ROY C K， ZIBRAN M F， KOSCHKE R. The vision of software clone management： past， present， and future （Keynote paper） [C]// Proceedings of the 2014 IEEE Conference on Software Maintenance， Reengineering and Reverse Engineering. Piscataway， NJ： IEEE， 2014： 18-33.

[2]

BELLON S， KOSCHKE R， ANTONIOL G， et al. Comparison and evaluation of clone detection tools [J]. IEEE Transactions on Software Engineering， 2007， 33（9）： 577-591.

[3]

PATE J R， TAIRAS R， KRAFT N A. Clone evolution： a systematic review [J]. Journal of Software： Evolution and Process， 2013， 25（3）： 261-283.

[4]

BARBOUR L， KHOMH F， ZOU Y. An empirical study of faults in late propagation clone genealogies [J]. Journal of Software： Evolution and Process， 2013， 25（11）： 1139-1165.

[5]

LAGUE B， PROULX D， MAYRAND J， et al. Assessing the benefits of incorporating function clone detection in a development process [C]// Proceedings of the 1997 IEEE International Conference on Software Maintenance. Piscataway， NJ： IEEE， 1997： 314-321.

[6]

ANTONIOL G， VILLANO U， MERLO E， et al. Analyzing cloning evolution in the Linux kernel [J]. Information and Software Technology， 2002， 44（13）： 755-765.

[7]

GDE N. Clone Evolution [M]. Berlin： Springer， 2011： 3-4.

[8]

KIM M， SAZAWAL V， NOTKIN D， et al. An empirical study of code clone genealogies [J]. ACM SIGSOFT Software Engineering Notes， 2005， 30（5）： 187-196.

[9]

KIM M， NOTKIN D. Using a clone genealogy extractor for understanding and supporting evolution of code clones [J]. ACM SIGSOFT Software Engineering Notes， 2005， 30（4）： 1-5.

[10]

ZIBRAN M F， SAHA R K， ROY C K， et al. Evaluating the conventional wisdom in clone removal： a genealogybased empirical study [C]// Proceedings of the 28th Annual ACM Symposium on Applied Computing. New York： ACM， 2013： 1123-1130.

[11]

SAHA R K， ASADUZZAMAN M， ZIBRAN M F， et al. Evaluating code clone genealogies at release level： an empirical study [C]// Proceedings of the 10th IEEE Working Conference on Source Code Analysis and Manipulation. Piscataway， NJ： IEEE， 2010： 87-96.

[12]

GDE N， KOSCHKE R. Studying clone evolution using incremental clone detection [J]. Journal of Software： Evolution and Process， 2013， 25（2）： 165-192.

[13]

BAKOTA T. Tracking the Evolution of Code Clones [M]. Berlin： Springer， 2011： 86-98.

[14]

YING T， LI P Z， CHUN H W， et al. Extract function clone genealogies across multiple versions [J]. International Journal of Security and Its Applications， 2015， 9（6）： 167-182.

[15]

SAHA R K， ROY C K， SCHNEIDER K. gCad： a nearmiss clone genealogy extractor to support clone evolution analysis [C]// Proceedings of the 2013 IEEE International Conference on Software Maintenance. Piscataway， NJ： IEEE， 2013： 488-491.

[16]

MENG C， XIAO H， TIAN T， et al. A new clone group mapping algorithm for extracting clone genealogy on multiversion software [C]// Proceedings of the 2013 Third International Conference on Instrumentation， Measurement， Computer， Communication and Control. Piscataway， NJ： IEEE， 2013： 848-853.

[17]

BAKOTA T， FERENC R， GYIMOTHY T. Clone smells in software evolution [C]// Proceedings of the 23rd International Conference on Software Maintenance. Piscataway， NJ： IEEE， 2007： 24-33.

[18]

AVERSANO L， CERULO L， PENTA M D. How clones are maintained： an empirical study [C]// Proceedings of the 11st European Conference on Software Maintenance and Reengineering. Piscataway， NJ： IEEE， 2007： 81-90.

[19]

THUMMALAPENTA S， CERULO L， AVERSANO L， et al. An empirical study on the maintenance of source code clones [J]. Empirical Software Engineering， 2009， 15（1）： 1-34.

[20]

KUHN A， DUCASSE S， GíRBA T. Semantic clustering： identifying topics in source code [J]. Information and Software Technology， 2007， 49（3）： 230-243.

[21]

THOMAS S W， ADAMS B， HASSAN A E， et al. Validating the use of topic models for software evolution [C]// Proceedings of the 2010 IEEE Conference on Source Code Analysis and Manipulation. Piscataway， NJ： IEEE， 2010： 55-64.

[22]

THOMAS S W， ADAMS B， HASSAN A E， et al. Studying software evolution using topic models [J]. Science of Computer Programming， 2014， 80： 457-479.（无期）

[23]

ASUNCION H U， ASUNCION A U， TAYLOR R N. Software traceability with topic modeling [C]// Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. New York： ACM， 2010： 95-104.

[24]

金靖，李萌，华哲邦，等.一种基于LDA和静态分析的代码功能识别方法[J].计算机工程与应用，2013，49（15）：27-31.（JIN J， LI M， HUA Z B， et al. Code function recognition approach based on LDA and static analysis [J]. Computer Engineering and Applications， 2013， 49（15）： 27-31.）

[25]

张瑞霞，张丽萍，王春晖，等.基于主题建模技术的克隆群映射方法[J].计算机工程与设计，2015，36（6）：1524-1529.（ZHANG R X， ZHANG L P， WANG C H， et al. Clone group mapping method based on topic modeling [J]. Computer Engineering and Design， 2015， 36（6）： 1524-1529.）

[26]

PHAN X H， NGUYEN L M， HORIGUCHI S. Learning to classify short and sparse text & Web with hidden topics from largescale data collections [C]// Proceedings of the 17th International Conference on World Wide Web. New York： ACM， 2008： 91-100.

[27]

JUERGENS E， DEISSENBOECK F， HUMMEL B. Clonedetectivea workbench for clone detection research [C]// Proceedings of the 31st International Conference on Software Engineering. Piscataway， NJ： IEEE， 2009： 603-606.

[28]

张久杰，王春辉，张丽萍，等.基于Token编辑距离检测克隆代码[J].计算机应用，2015，35（12）：3536-3543.（ZHANG J J， WANG C H， ZHANG L P， et al. Clone code detection based on Levenshtein distance of token [J]. Journal of Computer Applications， 2015， 35（12）： 3536-3543.）

[29]

LIN Y， XING Z， PENG X， et al. Clonepedia： summarizing code clones by common syntactic context for software maintenance [C]// Proceedings of the 2014 IEEE International Conference on Software Maintenance and Evolution. Piscataway， NJ： IEEE， 2014： 341-350.