0 引言

在软件系统开发过程中，开发人员经常拷贝粘贴代码导致出现较多的重复或相似的代码，这种被重复使用的代码称为克隆代码(Code Clone)^[1]。现有研究^[2]已经表明，一个软件系统存在着较多的克隆代码，据统计，软件系统中存在9%~17%的克隆代码，工业软件中的克隆代码比例更高，克隆代码也被视为软件维护和发展中的潜在威胁。早期研究认为克隆代码是有害的，从而选择对克隆代码进行重构。此后，研究者们发现应对克隆代码进行分析和评估，而不是一味地重构克隆。在分析克隆代码的过程中，克隆演化(Clone Evolution)和克隆谱系(Clone Genealogy)是两个核心问题。因此，了解克隆代码的演化历史对管理系统中的克隆代码至关重要。

克隆代码演化的研究已经有很多，对Type-1、Type-2克隆代码演化的研究较为成熟，然而能够高效识别Type-3克隆演化模式的方法较少，且存在克隆谱系提取工具较少、准确率低等问题，因此能够精确提取Type-1、Type-2以及Type-3类型克隆谱系并理解其演化模式变得尤为重要。

本文采用基于词频向量计算和克隆特征相结合的分层克隆映射方法，并联系克隆实际变化分析克隆演化，提出新的克隆演化模式，并最终实现一款自动构建克隆谱系提取器 —— ECG(Extract Clone Genealogy)，此工具能够从多个软件版本中自动构建克隆谱系，为后期的应用研究提供基础数据。

1 相关工作 1.1 克隆相关概念

现有研究已经建立了克隆相关概念的术语^[3]，克隆片段(Clone Fragment)是指相互之间相似的代码片段；克隆群(Clone Group)是指一组相互之间具有克隆关系的代码片段的集合，也称为克隆类(Clone Class)。现有研究将克隆代码分为了四类^[4](见图 1)：Type-1克隆代码是指未发生修改的代码片段(除了空白符和注释)；Type-2克隆代码允许有更多的变化，但语法完全相同，仅仅是变量、类型和功能标识符发生改变。Type-1和Type-2也被称为精确克隆代码。Type-3相对于Type-2克隆代码而言有更多的修改，代码语句发生了增加、去除等变化；Type-4克隆代码是功能相同，但代码的实现方法不同的克隆。因此Type-3和Type-4也被称为近似克隆代码。

1.2 克隆映射

提取克隆谱系的必要条件是能够建立克隆映射，而克隆映射是对软件版本间的两个克隆建立映射关系，其映射条件是具有映射关系的两个克隆具有同源性。映射准确性直接影响到整个研究结果，因此克隆映射在克隆演化研究中是至关重要的。

Higo等^[5]提出了一种在演化系统中追踪克隆的方法，根据克隆区域描述(Clone Region Description,CRD)的概念，从提取的克隆区域文本和文件中的位置关系两方面描述克隆映射关系。此方法可以映射位置发生变化的克隆，但映射误报率较高。

Göde等^[6]提出了一种在连续版本的克隆检测过程中映射克隆的方法，根据软件系统版本间的源文件的变化映射克隆。该方法虽耗时较少，但仅能够映射给定的版本，若有新增版本时需要重新映射。

Bakoka等^[7]提出了一种基于机器学习的抽象语法树(Abstract Syntax Tree,AST)映射方法，使用文件名、位置和克隆距离进行。该方法虽能映射多版本的克隆，但大量的相似特征增加了其时间消耗。

Thummalapenta等^[8]提出了一种根据修改日志追溯克隆关系的方法，从代码版本控制软件(Concurrent Version System,CVS)代码库中获取系统修改日志，以第一个版本为起源，计算后续版本中的修改变化，从而得到映射关系。但由于以起源版本为标准，因此在后续版本中的增加的克隆无法被研究。

Saha 等^[9]先根据函数名和文件路径进行版本间的函数映射，再从检测结果中进行克隆映射。该方法缩短了运行时间，但易受重载函数与覆盖的函数影响。

Ci等^[10]改进了克隆区域描述(CRD)模型，基于CRD逐层匹配算法、文本相似度和文本位置重叠率对克隆群和片段进行映射，以二元关系连接克隆映射。该方法虽降低了时间复杂度，但映射准确率易受嵌套代码的格式变化的影响。

内蒙古师范大学软件分析实验室也在克隆映射方面开展了大量的研究，其中，张瑞霞等^[11]提出一种基于主题模型的克隆群映射算法，计算代码中每个词的概率从而提取出克隆群的主题词，通过计算主题词之间的相似度确立映射关系。此方法虽能映射，但未和克隆特征相结合，误报率较高。涂颖等^[12]将代码转换为一种中间表示形式——Token串，利用最长公共子序列计算Token串之间的相似度，从而得出克隆之间的映射关系。但由于无法关注代码实际变化，因此无法映射Type-3克隆代码。

1.3 克隆演化及克隆谱系

软件的单一版本未包含克隆代码以时间为序的演变关系，而在克隆管理和维护中，需要更全面了解克隆代码在各版本中的变化情况，即克隆演化。

Kim等^[13]提出的克隆谱系框架最具代表性，通过克隆谱系可以描述克隆群在软件的多个演化版本中的变化情况。直系克隆(Lineage Clone)是一个有向非循环图，描述一个克隆群的直系演化史即无分支的演化过程。在直系克隆中，第V_i个版本的克隆群是由第V_i-1个版本克隆群演化而来的。由克隆群映射及其演化模式就可以完整地描述一个直系克隆。克隆谱系(Clone Genealogy)是起源于同一个克隆群的直系克隆的集合，一个克隆谱系反映了克隆代码如何创建、繁殖和演化的过程。另外，将克隆群的演化模式分为了6种：SAME(相同)、SUBSTRACT(减少)、ADD(增加)、CONSISTENT CHANGE(一致性变化)、INCONSISTENT CHANGE(不一致性变化)以及SHIFT(漂移)。Saha等^[9]对克隆谱系作了进一步的研究，开发了一款克隆谱系提取器gCad，在函数映射的基础上进行克隆映射。先使用转换程序语言(Transformations Programmers Language)-TXL提取函数，然后根据函数的签名、类名及文件名等属性映射两个版本之间的函数。如果在系统演化过程中，函数被重命名或移动到不同文件或目录，则根据函数名称和内容的相似性来查找起源。所有函数映射好之后，问题规模从两个版本之间程序内克隆的映射缩减到函数内克隆的映射，因此计算速度很快。但该研究存在的不足是如果克隆片段被移动到其他函数，则无法进行准确映射。此外，为了描述克隆群在规模和内容上没有发生变化的情况，在Kim等^[13]研究的基础上提出了STATIC(静态)模式。

Ci等^[10]提出了基于CRD克隆群映射的克隆谱系构建方法，此方法结合文本相似度和位置重叠率获取克隆映射关系，同时改进了演化模式，并最终提取出克隆谱系。但该研究的映射阶段易受代码结构变化的影响，因此克隆谱系构建的准确率也相对较低。

涂颖等^[12]基于克隆代码Token及位置等属性跨版本跟踪克隆，并提出五种简单演化模式，并由此分层识别克隆类演化模式。从软件多版本中自动提取克隆谱系，并获取克隆在整个演化过程中表现的特征和模式。但该研究对象仅仅是Type-1和Type-2克隆代码，缺乏对Type-3克隆代码演化过程的分析。

2 基于软件演化信息的克隆谱系提取方法 2.1 方法概述

本文提出了克隆谱系提取框架，并实现了一款克隆谱系提取工具。此工具以开源软件系统的n个版本为输入，映射连续版本中的克隆，提取克隆在软件演化过程中的变化模式。克隆谱系提取方法分为四个阶段：1)克隆检测阶段；2)克隆映射(克隆群映射和克隆片段映射)阶段；3)克隆演化模式识别阶段；4)克隆谱系提取阶段。图 2显示了软件系统克隆谱系提取得步骤。

2.2 克隆映射

提取克隆谱系之前需要跨版本的映射克隆代码，即确定从一个版本到另一版本中的克隆关系。映射两个相邻版本之间的克隆是追踪克隆的基础，因此准确的克隆映射是构建克隆谱系的关键步骤。本文采用一种基于词频向量计算、克隆距离关系和克隆特征相结合的分层映射方法^[14]，在克隆群映射的基础上再进行克隆片段的映射，充分利用克隆的文本、结构和特征等信息，准确地映射版本间的克隆。克服了仅仅依靠文本相似度、中间表示形式或者基于主题模型算法的映射算法的局限，在保证克隆映射准确性的同时提高映射的效率。图 3展示了克隆映射的过程，包括克隆检测和克隆群映射两方面。

克隆映射阶段包括两方面的内容：一是版本间克隆群关系的映射，此部分采用基于词频统计的向量空间和克隆群特征匹配相结合的算法完成；二是克隆群之间克隆片段关系的映射，此部分采用基于词频统计的向量空间、克隆片段特征和代码行距相结合的算法完成。

2.2.1 克隆检测

软件多版本的克隆检测为克隆谱系的研究提供基础数据，是整个研究工作的基础。本研究使用本团队前期预研成果FClones^[15]获得软件版本的克隆检测结果。FClones是一款基于Token编辑距离检测的方法的检测工具，能够较精确地检测出Type-1、Type-2以及Type-3克隆代码。此工具以软件多个版本为输入，得到克隆群信息，信息中包含文件名、函数名、开始行、结束行等信息以及克隆片段的相关信息。这些数据以可扩展标记语言(Extensible Markup Language,XML)方式保存，便于后期研究的提取和处理，克隆检测结果如图 4所示。

2.2.2 克隆映射

在获取克隆检测结果之后，接下来就要进行克隆映射。克隆谱系的构建是以连续版本间的克隆群作为线索组成的集合，而软件版本中克隆片段的数量要远多于克隆群的数量，因此先进行克隆群映射可很大程度上减少克隆片段的映射次数。

1) 克隆群映射阶段。

在克隆群映射阶段，首先通过基于词频统计的向量空间计算克隆群之间的相似度，满足阈值的克隆群作为具有映射关系的候选克隆群，再匹配克隆群特征，特征包括：克隆群所处的文件名、开始行、结束行和代码行数。最后通过匹配克隆群特征确定克隆群的映射关系。

本文采用了余弦相似度(Cosine Similarity)算法公式计算出克隆群权重向量之间的相似程度。假设两个克隆群的权重向量分别为ω_i和ω_j，采用优化空间的CosSimilarity (ω_i，ω _j)算法计算它们的相似性，则有：

$CosSimilarity(\omega i,\omega j)=\frac{\sum\limits_{i,j=1}^{n}{\omega i*\omega j}}{\sqrt{\sum\limits_{i=1}^{n}{\mathop{\omega }_{i}^{2}}\sum\limits_{j=1}^{n}{\mathop{\omega }_{j}^{2}}}}$

(1)

其中：ω_i*ω_j指的是克隆群权重向量的内积；CosSimilarity的取值范围是[0, 1]。当克隆群在演化过程中发生了变化，CosSimilarity的值小于等于1，本文启发式地设置一个阈值t，把所有CosSimilarity≥t的克隆群当作具有映射关系的克隆群对。

2) 克隆片段映射阶段。

在克隆片段映射阶段，首先通过基于词频统计的向量空间计算克隆片段的相似度，再通过匹配代码行距和克隆片段的特征确定克隆片段的映射关系。本文定义了LocDistance用来衡量克隆片段的代码行距关系，一般来说，虽然Type-3克隆代码会发生修改，但其修改幅度不会太大，即便是代码进行了添加或者删除操作，变化行数也不会大于总的代码行数一半。因此，如果代码行数差距较大，则不认为具有映射关系。

$LocDistance(CFi,CFj)=\frac{\min (Loc.CFi,Loc.CFj)}{\max (Loc.CFi,Loc.CFj)}$

(2)

另外，还定义了CffSimilarity用来匹配克隆片段的特征。其特征包括：1)克隆片段所在的文件名；2)克隆片段的函数名；3)克隆片段的起始行号；4)克隆片段的结束行号；5)克隆片段的代码行距。其中的文件名、克隆的起止行号均可从克隆检测结果中提取出，函数名从克隆片段源代码中抽取。在计算出克隆片段的相似度之后就要对其进行克隆片段位置关系和特征进行匹配来完成版本间的克隆片段映射。

2.3 克隆演化模式识别

克隆演化模式能够帮助开发和研究人员更加直观地了解克隆代码在演化过程中的变化方式和特征。而现有文献中缺乏对此问题的深入研究，特别是对Type-3克隆代码的演化过程。

本文方法以软件多版本克隆代码为研究对象，针对Type-1、Type-2以及Type-3函数克隆，开展关于克隆演化模式分类与识别的相关研究。目的是识别出克隆随软件多个版本演化的模式特征，然后分析演化模式对克隆维护产生的影响，以便于开展有针对性的维护与管理。由于将研究范围扩展到Type-3克隆代码，因此识别的难度也会加大。本文克隆演化模式的识别过程是：首先将单个克隆片段进行分类，接着在克隆片段的基础上分类并识别克隆群演化模式。由于克隆群中包含多个克隆片段，因此分阶段识别克隆演化模式能够较大程度地减少识别次数，提高识别效率。

2.3.1 克隆片段演化模式

根据克隆片段的数量以及内容变化方式将具有映射关系的克隆群中克隆片段的变化分为新增、去除、无变化和有变化四种情况：

1) 新增(数量)：片段CF是版本V_i+1中新产生的，在版本V_i中不存在。

2) 消失(数量)：片段CF在版本V_i中存在，在版本V_i+1中消失不见。

3) 没变化(内容)：片段CF从版本V_i到后一版本V_i+1内容没有发生任何变化。

4) 有变化(内容)：片段CF从版本V_i到版本V_i+1内容发生了变化，例如，标识符的重命名，语句的增删改等。

2.3.2 克隆群演化模式

在深入研究并分析版本间克隆群以及克隆片段的内部关系之后，将关注点定位在克隆代码内容和数量上的变化方面，由于Type-3克隆代码的位置易随代码行的删除和增加操作而变化，对于研究克隆代码的演化特征无法提供准确参考，因此漂移模式不作为研究内容。另外，在分析了克隆代码的演化过程及关系，发现克隆群还存在分离情况，因此本文增加了分离模式。为满足对克隆谱系后期演化分析的需要，并根据克隆群内克隆片段的数量以及内容的变化方式将克隆群分为八种短期演化模式：

1) 静态模式(Static)：克隆群CG从版本V_i到版本V_i+1的变化过程中，克隆片段的数量和内容上未发生变化。

2) 增加模式(Add)：克隆群CG从版本V_i到版本V_i+1的变化过程中，克隆片段的数量至少增加了一个。

3) 减少模式(Subtract)：克隆群CG从版本V_i到版本V_i+1变化过程中，克隆片段的数量至少减少了一个。

4) 分离模式(Separate)：克隆群CG从版本V_i到版本V_i+1变化过程中，克隆群在经历不一致变化后发生了分离。

5) 合并模式(Merge)：克隆群CG₁和克隆群CG₂从版本V_i到版本V_i+1变化过程中，两个克隆群在经历不一致变化后发生了合并。

6) 相同模式(Same)：克隆群CG从版本V_i到版本V_i+1的变化过程中，克隆片段的数量来发生变化。

7) 一致模式(Consistent)：克隆群CG从版本V_i到版本V_i+1变化过程中，克隆片段内容发生了相同变化。

8) 不一致模式(Inconsistent)：克隆群CG从版本V_i到版本V_i+1变化过程中，克隆片段发生了内容不同变化，导致至少一个克隆片段不再属于同一克隆群。

根据克隆片段的内容和数量变化情况，为克隆群添加演化模式，具体识别过程(假设版本V_i中的克隆群CG_i和版本V_i+1中的克隆群CG_i+1存在克隆映射关系)：

步骤1 若克隆群CG_i和克隆群CG_i+1中片段数量相同，则添加Same模式，若内容未发生任何变化，则添加Static模式，若克隆片段内容发生了相同变化，则添加Consistent模式。

步骤2 若克隆群CG_i+1中的CF在为新增片段，则添加Add模式，若克隆片段内容也发生了相同的变化，则添加Consistent模式。

步骤3 片段CF在下一版本V_i+1中消失，则添加Subtract模式，若克隆片段内容也发生了变化，则添加Inconsistent模式。

步骤4 若版本V_i+1中两个克隆群都起源于版本V_i中的克隆群CG_i，则添加Split模式，若版本V_i中两个克隆群都对应版本V_i+1中的克隆群CG_i+1，则添加Merge模式。

2.4 提取克隆谱系

在克隆映射和克隆演化模式识别完成之后，得到克隆群以及克隆片段的映射关系以及版本间克隆的变化信息。本文以软件的历史演化版本为时间轴，将相邻版本间的映射关系进行整合，同时匹配克隆群ID号，从而构成一个完整的克隆直系(Lineage Clone)。克隆直系描述了一个克隆群在整个演化周期内没有发生分离的演化过程。例如，版本V_i-1中的1号克隆群CG_i－1¹和版本V_i中的克隆群CG_i¹具有映射关系(CG_i－1¹为源克隆群、CG_i¹目标克隆群)，同时版本V_i中的克隆群CG_i¹和版本V_i+1中的克隆群CG_i+1²具有映射关系(CG_i¹为源克隆群、CG_i+1²目标克隆群)，则根据每个版本中克隆群ID号进行串联，得到一条克隆直系CG_i－1¹→CG_i¹→CG_i+1²。克隆直系构建过程如图 7所示。

每一条克隆直系都有相对应的属性值，属性包括克隆直系的源克隆群所在的版本号以及克隆群ID号。在获得版本间所有的克隆直系后，识别起源于同一条克隆群的所有克隆直系，从而构建出克隆谱系(Clone Genealogy)，克隆谱系描述的是起源于同一个克隆群的直系克隆的集合。克隆谱系构建过程如图 8所示。

克隆谱系能够体现出克隆群在软件生命周期内的演化过程，一个克隆谱系反映了克隆代码如何创建、繁殖和变化的过程。图 9描述了具有两个克隆直系的克隆谱系，图中有两条克隆直系，V_i表示版本号，箭头表示映射关系，克隆片段数量的变化表示其个数发生了变化，克隆片段形状的变化表示其内容发生了变化。

3 实验结果与分析 3.1 实验目标软件

依据上述方法，实现了一款自动提取克隆谱系的工具ECG，该方法选取了4款C语言开源软件共64个发布版本作为实验基础数据。这些实验目标软件具有不同领域、不同规模以及持续更新等特点，以保证实验的准确性及可靠性。实验目标软件如表 1所示。

在检测开源软件版本中克隆代码时，使用本团队开发的检测工具FClones，此工具检测方法基于Token编辑距离，能够高效检测出开源软件中的Type-1、Type-2以及Type-3克隆代码，并将检测结果存储在XML文件中，便于后期数据的提取和使用。

3.2 实验参数及结果

本实验在Windows 7环境下运行，环境配置为：Intel Core i5-3210M CPU @2.50 GHz，8 GB内存。

实验以版本号为时间线，往后追踪映射关系，查找克隆变化。本文进行了大量的对比实验并验证相似度在[0.6,1.0]范围内且以0.05为验证间隔的查全率和查准率，经过人工验证，将克隆映射相似度阈值设为0.85时效果最好，因此将映射相似度范围设置为[0.85,1.0]。阈值是根据特定软件的映射结果验证得到，因此在更换实验的软件系统时，相似度阈值需要重新验证设置。

在克隆群和克隆片段映射工作完成之后，要根据版本间的克隆变化情况添加克隆演化模式。图 10展示了软件版本Bluefish-1.0.5 和Bluefish-1.0.6添加了克隆演化模式后的克隆群演化结果和第3个克隆群中的克隆片段演化结果。

在为克隆群添加演化模式之后，合并所有版本的克隆映射关系和演化模式，得到克隆谱系。克隆谱系提供了一个软件系统多个版本中所有克隆群的变化历史，并包含克隆的相关信息，信息包括：具有映射关系的克隆群所在文件的版本号、克隆群之间的映射关系、克隆演化模式以及对应克隆片段的相关信息。本文将提取到的克隆谱系存储在XML文件中，图 11展示了克隆谱系存储结果。

图 11中展示了已构建的一条克隆谱系部分存储方式，文件中第一个标签(第一行)为克隆谱系的ID号；第二个标签展示了系统和环境运行信息(文件名、工具名、克隆粒度以及阈值)；第三个标签存储了软件总的克隆群以及克隆片段数，接下来是相邻版本之间克隆群的演化情况，包括软件版本号、克隆群ID号、克隆演化模式以及克隆片段的对应关系。

3.3 实验数据与分析

本文研究的是Type-1、Type-2以及Type-3的函数克隆，并对4款开源软件中64个版本进行提取实验。在完成克隆映射和识别克隆演化模式实验之后，再串联所有版本间的克隆演化模式，从而得到克隆直系和克隆谱系。

针对每一款软件，统计出各个演化模式数量后，计算出了在软件演化期间每一种克隆群演化模式的比例，表 2展示了克隆群演化模式的统计结果。

从表 2中可以看到，静态演化模式所占的比例约为41.98%，说明绝大多数克隆在版本更新过程中并没有发生变化。另外，一致和不一致变化比例约为2.66%和3.48%，在所有的软件版本中发生较少，并且发生不一致变化比例比一致变化稍高，说明在软件演化过程存在部分克隆未被一致维护。因此，应该更多地关注那些发生不一致变化而可能引入的潜在Bug。

此外，实验统计了克隆谱系的相关信息，信息包括：克隆谱系数量、克隆群数量、克隆片段数量、生命周期、运行时间等等。克隆谱系由多个克隆群组成，若一个克隆群在一个版本中出现，而在下一版本中被去除，由于此类情况无法为后期提供软件的演化信息，因此不算作一个克隆谱系，克隆谱系信息如表 3所示。

经过研究和分析发现，影响实验结果的原因可能有三方面：

1) 函数重命名。

在克隆片段映射阶段，本文使用了基于词频统计、代码行距和片段属性相结合的映射方法，而克隆片段属性匹配时的属性之一为函数名，因此若函数被重命名，可能会导致匹配失败，从而影响映射结果。

2) 人工验证。

当前研究中并没有验证和评价标准方法，只能人工手动验证。然而，由于缺乏领域知识和人工错误，人工验证过程中可能不仅会出现一些无意的错误影响实验数据评价结果，而且会花费大量时间。

3) 阈值的选取。

克隆映射阶段采用了基于词频相似度计算的方法，阈值的设定和选取的软件有密切关系，随着版本的不同，阈值的选取可能不尽相同，而阈值又是通过对比实验和人工验证映射结果得到。

4 结语

本文将基于词频向量计算、代码行距以及克隆特征相结合并分阶段映射版本间克隆，同时从克隆群和克隆片段两个角度对克隆演化模式进行分类和识别，从而构建出克隆谱系，并最终实现一款克隆谱系自动提取工具ECG，该工具能够自动识别其演化模式并快速且准确地提取Type-1、Type-2以及Type-3克隆谱系。实验结果表明克隆谱系提取工具ECG能够高效提取出克隆谱系，同时研究成果能为克隆演化分析和克隆管理提供数据和参考。本文得到的基础数据也将应用于本团队克隆有害性预测^[16]以及克隆质量评估的后期研究中。

本研究工作仍存在问题，例如克隆映射阈值的设置是由人为经验确定的，可能会影响克隆谱系提取的准确度。另外，存储完成后缺乏对克隆谱系的可视化。在未来研究工作中将逐渐解决这些问题，拟通过图形化表示，可以直观了解这些版本中某个克隆群的产生、变化及死亡的整个历史过程，将这些文本信息以良好的方式反馈给用户，同时为克隆管理及维护提供有价值的参考。