基于软件多版本演化提取克隆谱系

2024年5月7日发(作者：)

基于软件多版本演化提取克隆谱系

摘要：针对单个版本克隆检测结果不足以体现克隆特

征这一问题，从软件多版本中自动提取克隆谱系，获得克隆

在软件演化过程中表现出的模式和特征。首先基于克隆代码

Token表示及其所在文件名称、函数名称等位置属性，准确

映射软件历时演化版本间的克隆代码，进而识别克隆演化模

式；然后匹配克隆类ID号，合并所有相邻版本间的映射结

果及演化模式信息，得到克隆谱系。同时开发了相应的克隆

谱系自动提取工具FCG对6款开源软件进行了测试，发现当

前版本中克隆代码平均生命周期占所研究版本总数的70%

以上，且大部分没有发生变化，说明大部分克隆能被较好地

维护，但也存在少量不稳定的克隆可能导致软件缺陷，需要

修改或重构。实验结果表明FCG可高效提取克隆谱系，有助

于更好地理解克隆及有针对性地管理克隆。

关键词：克隆代码；克隆谱系；多版本；克隆演化；软

件维护

中图分类号：TP311.5

文献标志码：A

Abstract：Since clone detection results cannot fully reflect

the features of clones， clone genealogies extraction from

multiple versions can be used to uncover the patterns and

characteristics exhibited by clones in the evolving system. A

clone genealogy extraction method named FCG was proposed.

FCG first mapped clones between each adjacent versions and

then identified clone evolution patterns. All of the results were

combined to get clone genealogies. Experiments on 6 open

source systems found that the average lifetime of clones in

current version is over 70 percent of the total number of studied

versions， and most of them do not change， which indicates

that majority of clones can be well maintained. While some

unstable clones may be defect potential， and needs to be

modified or refactoring. Results show that FCG can efficiently

extract clone genealogies， which contributes to a better

understanding of clones and provides insights on targeted

management of clones.

英文关键词Key words：clone code； clone genealogy；

multiversion； clone evolution； software maintenance

0 引言

克隆代码在软件中普遍存在[1]，且与软件工程中的各种

问题紧密相关。一方面，克隆代码可以带来一些维护的益处

[2]，例如，复用一段经过良好测试的代码，可以降低开发人

员编写新代码引入的风险，还可以节约设计编写新代码的时

间和成本；另一方面，克隆代码在有些情况下是有害的，例

如，缺陷可能被繁殖，代码片段之间必须保持一致的某种关

联可能丢失[3]。

由于克隆代码对软件开发及维护的双重影响，大量重构

克隆并不可取[4]。许多近期研究[5-7]表明克隆需要进行有效

的管理。一个软件系统可能存在数千段克隆代码，针对单个

版本的克隆分析不能很好地去除或者评价这些克隆，而利用

克隆谱系跨版本跟踪克隆类的直系变化过程，研究克隆在软

件演化过程中表现出来的模式和特征，开发人员可以利用这

些信息更有效地管理克隆[8]。例如，重构有些不稳定的克隆

可能降低软件的维护成本，一致变化的克隆可能需要使用文

档标记防止丢失一致性。本文从软件多版本演化角度，跨版

本跟踪克隆，识别克隆演化模式，提取克隆谱系。

2005年，Kim等[9]首次提出了克隆谱系，利用协作版本

系统（Concurrent Versions System， CVS）对两款Java软件

进行了克隆谱系的提取，分析了克隆类在软件多个版本中的

演化情况。之后克隆谱系模型被其他研究人员作为研究克隆

演化的一种基本方法。Aversano等[10]利用克隆谱系研究了

维护活动对克隆的影响；Zibran等[11]利用克隆谱系研究了

克隆在演化过程中的去除活动；Xie等[12]利用克隆谱系研究

了克隆迁移现象对代码缺陷的影响。虽然克隆谱系被广泛应

用于克隆演化相关研究，但可用的克隆谱系提取工具很少。

本文实现了一款克隆谱系提取工具――FCG，可快速从软件

多个版本中自动提取克隆谱系。

提取克隆谱系的一个关键问题是构建相邻版本间的克

隆映射，映射的准确性决定了克隆演化研究的意义与价值

[13]。Thummalapenta等[14]利用CVS等版本控制系统中的

修改日志信息，计算版本间的变化，得到映射关系。由于该

方法以某一选定版本中的克隆为映射起源，因而无法研究后

期版本中新产生的克隆。Bakota[15]提出了一种基于相似度

距离函数的克隆代码映射方法，结合克隆代码的词法表示和

抽象语法树衡量其相似性。该方法需要提取抽象语法树，耗

时较高。Gode等[16]使用增量的算法将克隆检测和映射结合

在一起，该方法时间复杂度低，适合处理给定版本的软件；

但添加新版本时整个检测与映射需重新执行，空间复杂度

高。国内哈尔滨工业大学的慈萌[17]改进了克隆区域描述符

（Clone Region Descriptor， CRD）[18]的概念，采用基于

CRD的克隆类映射算法完成相邻版本间克隆类映射，最后基

于二元关系合成构建克隆谱系。采用CRD描述克隆区域存

在一定的局限性，如果代码某些部分（如循环终止条件、条

件语句的分支谓词）发生变化或代码嵌套结构发生变化，会

导致CRD失效，影响映射准确率。 本文提出一种基

于Token的克隆映射方法，不依赖版本控制系统中的信息，

能快速地从软件多个版本中提取克隆谱系。和本文研究最相

似的是Saha等[19]的研究，他们在函数映射的基础上进行克

隆映射，开发了一款克隆谱系提取工具gCad[20]。主要有以

下两个不同点：

1）Saha等利用TXL提取函数，先映射相邻版本间的函

数，再在函数内进行克隆片段的映射，将问题规模缩小，因

此计算速度快。但不足的是，如果函数被重命名或被移动到

其他文件，会影响函数映射的准确性，从而降低克隆映射的

准确率。本文基于Token先映射相邻版本间的克隆类，再利

用克隆片段的位置信息进行片段映射，不易丢失克隆片段之

间的映射关系，具有很高的查全率。

2）Saha等关注克隆谱系的类别，将其分为活谱系、死

亡谱系、句法相似谱系、一直变化谱系四个类别，并分析了

它们所占的比例。而本文关注克隆代码的演化特征，从克隆

生命周期和演化模式两方面分析了克隆的演化。克隆生命周

期可以反映克隆的稳定性，演化模式描述了克隆在软件演化

过程中不同的变化方式，了解这些演化特征对有效管理克隆

十分有益。

1 克隆谱系提取方法

1.1 版本间克隆映射

提取克隆谱系需要跨版本跟踪克隆，也就是将某一版本

中的克隆代码映射到下一个版本中对应的克隆代码。相邻版

本间的克隆映射是跟踪克隆的基础，也是提取克隆谱系的一

个关键问题。本文采用分层次的克隆映射方法，在克隆类映

射的基础上，进行单个克隆片段的映射。图1简要描述了相

邻版本间克隆映射的基本过程。

1.1.1 获取克隆检测结果

软件各个版本的克隆检测结果是研究克隆演化的先决

条件。本研究使用我们的克隆检测工具FCD[21]获得克隆检

测结果。FCD是一款基于优化后缀数组的克隆检测工具，可

以高效地检测Type1和Type2的函数克隆，以克隆类的形式

返回检测结果，具有较好的查全率和查准率。本研究编写

shell脚本实现FCD对一款软件多个版本的自动化检测。针

对研究需要，获取有价值的检测结果，包括每个版本中的克

隆类及其Token串，以及克隆类中每个克隆片段的大小及位

置信息。

1.1.2 构建克隆映射

相邻版本间克隆的准确映射是提取克隆谱系的基础。本

研究在获得软件各个版本的克隆检测结果后，综合利用克隆

代码的文本和词法结构，以及所在文件名称、函数名称等多

个属性进行相邻版本间的克隆映射。

本文选用LCS的动态规划算法，并利用滚动数组优化存

储空间，时间复杂度为O（mn），空间复杂度为O（n）。求

LCS还有一种算法是将其转换为最长递增子序列问题，算法

复杂度下界为O（n log n），上界为O（mn log （mn）），大

于 O（mn）。由于在Token序列中，重复出现的字符很多，

源代码转换成Token串时，所有数据类型都用D替换，所有

变量名都用V替换，这种情况下该算法不能取得较好的时间

复杂度，因此不选用。

当克隆类中的克隆片段在演化过程中发生变化时，

TokenSimilarity的值小于1。启发式地设置一个阈值t，对于

一个克隆类，把相邻版本中和它TokenSimilarity值大于等于

t的克隆类当作候选的具有映射关系的克隆类。如果存在多

种可能，则选取源代码相似性最高的那个克隆类为最终的映

射结果。

定义Location来衡量克隆片段的位置信息，Location为

能反映克隆片段位置的各个属性的集合，包括：1）克隆片

段所在文件名称；2）克隆片段所在函数名称；3）起始行号；

4）结束行号。其中1）、3）、4）可以从克隆检测结果中获得，

通过这些属性可以从源文件中获得克隆片段的源代码，从而

提取函数名称，获取2）。通过匹配Location中的各个元素来

完成相邻版本间克隆片段的映射。

1.2 添加克隆演化模式

克隆演化模式可用于研究克隆现象，帮助维护人员及相

关研究者了解克隆在软件版本历时演化过程中表现出的模

式及特征，分析克隆可能导致的问题。目前，研究人员已定

义了一些克隆演化模式，有的是对克隆片段定义的，有的是

对克隆类定义的，这些模式之间具有很强的相关性。本文深

入分析各种克隆演化模式之间的关系，选用其中部分演化模

式，并提出新的克隆片段的简单演化模式，由它可以分层导

出克隆类的演化模式。

1.2.1 克隆片段演化模式

在建立好完整的相邻版本间的克隆映射后，基于克隆片

段的映射结果及其与克隆类中其他克隆片段的成员关系，为

单个克隆片段添加如下4种简单演化模式（如图2所示）：

1）新增。片段f是版本Vi+1中新产生的克隆片段，即

不存在于版本Vi中。

2）消失。片段f在版本Vi中被修改或移除，不再属于

版本Vi+1中的任意一个克隆类。

3）没变化。片段f从版本Vi到版本Vi+1没有发生变化。

4）有变化。片段f从版本Vi到版本Vi+1发生了变化。

例如，标识符的重命名，语句的增删改等。

图2中椭圆代表克隆类，椭圆中的小圆圈代表克隆类中

包含的克隆片段，不同灰度代表克隆片段发生了变化，虚线

小圆圈代表片段f。

1.2.2 克隆类演化模式

每个克隆类都是由多个克隆片段组成的，根据版本间的

克隆类映射，结合克隆类中所有克隆片段的简单演化模式，

为克隆类添加如下5种演化模式（如图3所示）：

1）无变化。克隆类从版本Vi到版本Vi+1没有发生变化。

2）增加。从版本Vi到版本Vi+1至少有一个克隆片段添

加到了克隆类。

3）去除。从版本Vi到版本Vi+1至少有一个克隆片段从

克隆类中去除了。

4）一致变化。克隆类中所有克隆片段从版本Vi到版本

Vi+1作了一致的修改，即片段之间的相似程度不变，仍属于

同一克隆类。 2.3.2 演化模式信息

本文统计了软件演化过程中各个演化模式发生的比例，

对于不同的软件，克隆演化模式所占比例并不完全一样，说

明软件的规模、类型或开发人员编程习惯可能对克隆演化有

影响。但总体上看，大部分克隆没有发生变化，一致变化和

不一致变化模式在所有目标软件中都较少发生。而对于发生

变化的克隆代码，一致变化比不一致变化的比例要高，说明

大部分克隆代码在演化过程中能被比较好地维护。在所有目

标软件中，dovecot和ffmpeg两款软件发生增加和去除模式

的比例明显高于其他软件。通过人工检查这类克隆的源代

码，发现大部分都是由于相同或相似API的使用而导致的克

隆，且这类克隆的代码行数通常不超过10行。特定API的

使用通常需要一系列的函数调用或其他有序的命令序列。对

于相似问题，同一个开发人员或不同开发人员之间都可能由

于使用常用的问题解决模式而导致克隆，这类无意的克隆在

演化过程中容易发生增加和去除。

2.3.3 对克隆代码管理的启示

从维护角度讲，应有选择地对克隆代码进行管理，避免

浪费不必要的维护成本。那些长期存在且没有发生过变化的

克隆代码，通常是无害的，不需要过多关注，可用文档进行

记录或注释。而发生不一致变化的克隆危险性较高，开发或

维护人员在对一段克隆代码进行修改或bug修复时，很可能

忘了对这段代码的所有其他克隆片段进行一致性的修改，导

致潜在缺陷或bug修复的不完全，关注这类克隆可帮助降低

克隆代码的负面影响。

此外，统计一个克隆谱系中每种演化模式发生的次数，

可以反映克隆类的稳定性。不一致变化、增加及去除这3种

模式发生的次数越多，克隆类就越不稳定，应进行修改或去

除等操作。而如果一个克隆谱系中仅包含无变化和一致变化

两种模式，说明该克隆类在软件演化过程中一直稳定地演

化，若在维护过程中发生修改，可提示维护人员对克隆类中

所有克隆片段进行一致的修改。

2.3.4 研究的不足与受限

本研究主要存在以下几方面的不足与受限：1）映射方

法中相似度阈值的选取，不能同时保证极低的误检率和漏检

率，通过对比实验，人工验证映射结果来选择合适的阈值；

2）文件重命名，实验主要根据克隆片段所在文件名称来追

踪克隆片段，如果软件在演化过程中文件被重命名，可能无

法准确跟踪克隆片段；3）软件版本的选取，本文分析软件

多版本的克隆演化信息，实验选择软件稳定更新的多个连续

发布版本进行克隆谱系提取，同一软件不同版本的选取会给

实验结果带来差异；4）人工验证，目前该研究领域尚没有

对映射及克隆谱系结果评价的标准集，只能人工检查，需要

大量时间，且实验结果难以有效评价。

3 结语

本文基于克隆代码Token及位置等属性跨版本跟踪克

隆，并提出克隆片段的简单演化模式，由此分步层层筛选导

出克隆类演化模式，最终实现了一款克隆谱系自动提取工具

FCG。对6款开源软件进行了实验，从软件多版本演化角度，

分析了克隆历时演化模式及特征。实验结果表明FCG可高效

提取克隆谱系，为克隆演化分析提供支持。获得的克隆生命

周期和演化模式信息可反映克隆代码在演化过程中的稳定

性和变化方式，了解这些特征有助于对克隆代码进行针对性

的管理。研究人员还可利用克隆谱系进一步提取其他克隆演

化度量，如克隆变化频率、不一致变化次数等，从大量克隆

检测结果中发现潜在有害的克隆。

参考文献：

[1]ZIBRAN M F， SAHA R K， ASADUZZAMAN M，

et al. Analyzing and forecasting nearmiss clones in evolving

software： an empirical study[C]// Proceedings of the 16th IEEE

International Conference on Engineering of Complex Computer

Systems. Piscataway： IEEE Press， 2011： 295-304.

[2]HARDER J， GODE N. Cloned code： stable code[J].

Journal of Software： Evolution and Process， 2013， 25（10）：

1063-1088.

[3]CHATTERJI D， CARVER J C， KRAFT N A， et al.

Effects of cloned code on software maintainability： a replicated

developer study[C]// Proceedings of the 20th IEEE Working

Conference on Reverse Engineering. Piscataway： IEEE Press，

2013： 112-121.

[4]GODE N， KOSCHKE R. Frequency and risks of

changes to clones[C]// Proceedings of the 33rd IEEE

International Conference on Software Engineering. Piscataway：

IEEE Press， 2011： 311-320.

[5]NGUYEN H A， NGUYEN T T， PHAM N H， et al.

Clone management for evolving software[J]. IEEE Transactions

on Software Engineering， 2012， 38（5）： 1008-1026.

[6]ZHANG G， PENG X， XING Z， et al. Towards

contextual and ondemand code clone management by

continuous monitoring[C]// Proceedings of the 28th IEEE/ACM

International Conference on Automated Software Engineering.

Piscataway： IEEE Press， 2013： 497-507. [7]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： IEEE Press， 2014：18-33.

[8]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.

[9]KIM M， SAZAWAL V， NOTKIN D， et al. An

empirical study of code clone genealogies[C]// Proceedings of

the 10th European Software Engineering Conference Held

Jointly with 13th ACM SIGSOFT International Symposium on

Foundations of Software Engineering. New York： ACM Press，

2005： 187-196.

[10]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： IEEE Press， 2007： 81-90.

[11]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

Symposium on Applied Computing. New York： ACM Press，

2013： 1123-1130.

[12]XIE S， KHOMH F， ZOU Y， et al. An empirical

study on the faultproneness of clone migration in clone

genealogies[C]// Proceedings of the 2013 10th IEEE Working

Conference on Mining Software Repositories. Piscataway：

IEEE Press，2014： 94-103.

[13]SHI Q， MENG F， ZHANG L， et al. Survey of

research on code clone technique[J]. Application Research of

Computers， 2013， 30（6）：1617-1623.（史庆庆，孟繁军，

张丽萍，等.克隆代码技术研究综述[J]. 计算机应用研究，

2013， 30（6）： 1617-1623.）

[14]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.

[15]BAKOTA T. Tracking the evolution of code clones[C]//

Proceedings of the 37th International Conference on Current

Trends in Theory and Practice of Computer Science. Berlin：

SpringerVerlag，2011： 86-98.

[16]GODE N， KOSCHKE R. Studying clone evolution

using incremental clone detection[J]. Journal of Software：

Evolution and Process， 2013， 25（2）： 165-192.

[17]CI M. Research on clone genealogy extracting method

based on CRD clone group mapping[D]. Harbin： Harbin

Institute of Technology， 2013.（慈萌. 基于CRD克隆群映射

的克隆家系提取方法研究[D]. 哈尔滨：哈尔滨工业大学，

2013.）

[18]DUALAEKOKO E， ROBILLARD M P. Clone region

descriptors： representing and tracking duplication in source

code[J]. ACM Transactions on Software Engineering and

Methodology， 2010， 20（1）： 1-31.

[19]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 Working

Conference on Source Code Analysis and Manipulation.

Piscataway： IEEE Press， 2010： 87-96.

[20]SAHA R K， ROY C K， SCHNEIDER K A. gCad：

a nearmiss clone genealogy extractor to support clone evolution

analysis[C]// Proceedings of the 29th International Conference

on Software Maintenance. Piscataway： IEEE Press， 2013：

488-491.

[21]SHI Q， ZHANG L， YIN L， et al. Clone detection

based on suffix array[J]. Computer Engineering， 2013， 39

（9）：123-127.（史庆庆， 张丽萍， 尹丽丽， 等. 基于后

缀数组的克隆检测[J]. 计算机工程， 2013， 39（9）：123-127.）