面向大规模多版本软件系统的代码克隆检测加速技术

方维康 吴毅坚 赵文耘

(复旦大学软件学院 上海 200438) (复旦大学上海市数据科学重点实验室 上海 200438)

0 引 言

在软件项目的开发过程中，开发人员经常会通过拷贝粘贴已有代码片段并伴随着或多或少的修改来提升开发效率，这种复用方式会导致代码中存在一些完全相同或极其相似的代码片段，这种完全相同或极其相似的代码片段通常被称为代码克隆。现有的研究报告和经验证据表明，一个典型软件系统的9%～17%是由克隆代码组成的[1]。

代码克隆通常被认为是一种特殊的代码味道，对软件系统的开发和维护有诸多负面的影响。目前已有许多研究揭示了代码克隆与程序的缺陷率、软件稳定性、软件质量、软件维护成本等的关系[2-9]。所以，为方便克隆研究与维护工作的进行，首要任务是检测系统中的代码克隆。

目前，已经有许多研究人员针对克隆检测方法和技术进行了研究[10-21]，但这些工具仅针对软件系统的单个版本进行克隆检测。而在许多应用场景下，例如代码来源分析、构建代码克隆谱系等[22]，需要获取软件系统各个版本的代码克隆信息。传统的做法是对软件系统的各个版本进行克隆检测。但在软件系统规模较大、版本较多时，这种检测方式往往比较耗时，尤其是对多个系统进行跨项目克隆检测，这种方式甚至难以进行。经研究表明，软件系统每次经历版本更新时，变更的代码量只占系统代码总量的一小部分，当系统趋于稳定时则尤为明显。因此实际上，在对系统的各个版本进行克隆检测时，有许多重复的代码被反复检测，造成很大的性能浪费。如果能够在检测过程中自动识别版本间重复的代码而不需要重复检测，将会大大节约检测的资源和时间。

针对以上问题，本文设计并实现一种面向多版本软件系统的代码克隆检测加速技术。该方法首先将不同版本、代码内容相同或高度相似的同一方法构建方法版本组，再选取每个方法版本组中最早的版本作为样本方法，样本方法的集合称为历史映像，然后对所有的历史映像进行克隆检测，同时建立起样本方法和方法版本组间的方法关系。最终根据样本方法的克隆检测结果和方法索引恢复原始的全量克隆关系。其中，如何快速分析出系统所有版本中的每个方法，基于局部相似性比较在前后版本快速建立演化关系，基于索引快速恢复所有克隆关系，都是该方法需要解决的问题。

1 代码克隆

1.1 代码克隆相关定义

代码克隆认可度较高的定义是，如果软件系统代码库中的两个或多个代码片段彼此相同或近似，则称之为代码克隆[23-24]。按照克隆之间的相似程度划分，克隆被分为四种类型。

Ⅰ型克隆：除去空白符和注释之外完全一样的代码片段。

Ⅱ型克隆：除了空白符、注释、标识符、类型和字面值有可能不同之外，语法结构上完全一致的代码片段。

Ⅲ型克隆：除了空白符、注释、标识符、类型和字面值有可能不同之外，还有可能添加、修改或删除了一些代码行的代码片段。

Ⅳ型克隆：功能上一致但代码本身相似度较低的代码片段。该种克隆类型比较特殊，它通常不是由复制粘贴产生的，而是不同开发人员对同一种功能的不同实现，例如不同的排序算法。

不难发现，从Ⅰ型克隆到Ⅲ型克隆，克隆片段之间的语法相似度逐渐降低。而Ⅳ型克隆类型的克隆从代码文本和语法结构层面已经难以直观地看出克隆实例之间的相似性，通常检测难度较大，因此本文的克隆检测加速方法仅面向前三种类型的克隆。

为了后文阐述方便，下面对一些专用名词或术语进行简单的解释。

克隆对：存在克隆关系的两个代码片段被称为一组克隆对。

克隆组(类)：一组存在克隆关系的代码片段被称为克隆组。

克隆实例：克隆对或克隆组中的每一个代码片段都称为一个克隆实例。

方法级克隆：如果两个或多个方法是彼此克隆的，则将这种克隆称为方法级克隆。方法级克隆的克隆实例是完整的方法。

1.2 大规模多版本克隆检测的背景与挑战

在过去几十年的代码克隆研究中，已经提出了许多用于检测代码克隆的技术，并实现了许多克隆检测工具。这些技术和工具根据所基于的代码特征大致分为基于文本[10-11]、基于token[12-13]、基于程序依赖图[14-15]、基于抽象语法树[16-17]、基于代码底层表示[18]等。其中，只有SourcererCC[25]和SAGA[26]在大规模克隆检测(亿行级)上依旧表现良好。

这些工具通常仅面向软件系统的单个版本进行克隆检测。在许多场景下，例如为项目构建克隆演化谱系时[12]，需要先获取软件系统的各个版本的克隆情况。传统做法是采用已有的克隆检测工具分别对系统的每个版本进行克隆检测，而在软件规模较大或者软件版本较多时，这种方式会非常耗时。

针对多版本的克隆检测，研究人员提出过一些优化措施。例如，只对目标项目的初始版本进行克隆检测，接着根据版本控制工具记录的修改信息追踪克隆，但这种方式实际上会丢失所有初始版本之后出现的克隆[22]。另一种优化方式是采用增量克隆检测[14]，但这种方式不适用于跨项目克隆检测。

由上可知，在处理大规模多版本软件系统进行克隆检测，尤其是多个多版本系统进行跨项目克隆检测时，现有的克隆检测工具通常耗时过长甚至无法正常运行。而实际上，多版本系统中不同版本间的代码存在大量重复，反复检测这些重复代码浪费了大量的工具性能。如果能够在检测过程中快速识别这些重复代码以避免重复检测，将会大大提升大规模多版本系统克隆检测的效率，也使得检测更大规模的多版本系统成为可能。鉴于此，本文提出一种独立于克隆检测工具的针对多版本软件系统的克隆检测加速技术。

2 基于版本间代码压缩的多版本克隆检测加速技术

本节将对所提出的多版本软件系统克隆检测加速技术的具体设计及流程进行详细介绍。该技术不仅可以对单个多版本软件系统进行克隆检测，还可以对多个多版本软件系统进行跨项目克隆检测，下面将以跨项目克隆检测为例介绍该技术。考虑到片段级克隆数量较多、过于细碎且不同的克隆检测工具对片段的界定方式有所不同，所以本文只讨论方法级克隆的检测。多版本软件系统克隆检测方法主要分为以下几个步骤：(1) 项目信息预处理;(2) 构建目标项目的历史映像;(3) 对目标项目的历史映像进行克隆检测;(4) 恢复全量克隆关系。

2.1 项目信息预处理

本文将所有待检测的项目称为目标项目集。在进行后续步骤之前，需要先对目标项目进行预处理，主要包括项目版本信息提取和项目方法信息提取。

版本信息提取：对于每个目标项目，需要收集该项目所有发布版本的相关信息，包括每个版本的名称、发布时间、各个版本的代码，同时将该项目的各个版本按照发布时间先后进行组织排序。该步骤相对比较简单，其主要目的是为后续的步骤做准备。本文的目标是提出一个通用的多版本软件系统克隆检测加速方法，所有对于任何形式的多版本软件系统，只需要按照规定的信息格式给出版本相关信息并准备好各个版本的代码即可。例如，对于由Git、SVN等源代码版本管理工具管理的项目，可以非常方便地使用相关命令导出版本信息。而对于没有版本管理工具介入的项目，也可以按照规定格式手动地给出版本信息。

方法信息提取：对目标项目的每个版本，设计一个方法提取器来提取代码中所有方法的相关信息，其中根据该项目所使用的编程语言采用了相关的语法解析工具(例如JavaParser、TXL等)。这些信息包括方法签名、方法完全限定名、方法所在文件的路径、方法起止行，最后将这些信息以方法为单位保存到一个集合中，将其称为该版本的方法信息集合。

2.2 构建历史映像

鉴于传统的全量克隆检测方法需要对目标项目的所有版本进行克隆检测，而这些重复的代码也会在检测中被反复比较而浪费大量时间。因此，提出一种面向多版本代码的克隆检测加速技术。我们不再过多地关注克隆检测本身如何加速，而是将工作重心转移到版本间重复代码的标记识别以及去除上，通过大幅度地压缩被检测的代码量来缩减克隆检测时间，压缩后的代码称为历史映像。

构建历史映像的主要过程包括，为不同版本中方法名及所属文件路径一致且代码内容相同或高度相似的同一方法(下文简称为相同方法)构建方法版本组，再选取每个方法版本组中最早的版本作为样本方法，样本方法的集合则称为历史映像。构建单个项目历史映像主要包括构建方法版本组和选择样本方法两个步骤。

构建方法版本组：在项目信息进行预处理之后，得到了每个目标项目的各个版本的方法信息集合。接下来，需要根据这些方法信息，寻找并标记版本间相同的方法。为此，我们实现了一个方法映射器用于将含有多个版本的项目基于方法名及文件路径构建将不同版本、代码内容相同或高度相似的相同方法构建方法版本组。值得注意的是，本文所指的相同方法并不是完全指代码文本完全一致的方法，而是指符合本文规定的判定标准的方法。本文相同方法的具体判定标准是方法完全限定名相同、方法所在的文件的路径一致且方法源代码间有非常高的文本相似度，我们使用的是最长公共子序列长度来衡量文本相似程度。这里没有限定方法文本必须完全相同，是因为在很多情况下，部分方法在演化过程中经历的修改可能会非常细微，就方法整体而言几乎看不出任何变化，这样的方法被当作新方法并不合适。另一方面，由于不同版本中只有方法完全限定名相同且方法所在的文件的路径一致的方法才会进行本文相似度的比较，而在具体某个版本中方法完全限定名及其文件路径实际上可以唯一确定一个方法，所以每个方法至多只需要进行一次相似度比较，整体效率较高。

具体的对于单个目标项目的方法版本组构建规则如下：首先将该项目的各个版本按照发布时间排好顺序，接着按顺序处理该项目的每个版本。具体处理规则是，首先提取当前版本中的所有方法，对于每个方法，判断其是否已经属于某个方法版本组，是则跳过；否则，建立一个新的方法版本组，对于该方法，提取其方法名与所在文件的相对路径，查找所有后续版本中与该相对路径、方法名都相同且文本高度相似的方法，将这些方法添加到该新的方法版本组。

构建方法版本组最重要的是建立版本间相同方法的关联，其中相同方法判定依据是方法完全限定名相同、方法所在的文件的路径一致且方法源代码间有非常高的相似度。按照这样的限定规则，更名方法以及移动到其他文件方法都将被视作新的方法，在克隆检测过程中它们仍将参与比较，这似乎有悖于我们的初衷。但实际上，如果仅考虑方法间的相似度，则在为某个方法构建方法版本组时，将不得不与后续版本中的所有方法进行相似度比较，时间复杂度将会达到O(n2)级别(n为方法数)，并且相似度的比较本身也比较复杂，所以整个过程会相当耗时，导致整个过程可能比进行全版本克隆检测更加低效。而加上方法完全限定名和文件路径的限制后，效率会大幅提升，方法的时间复杂度降为O(n)级别。因为文件路径和完全限定名可以唯一确定一个方法，所以在为某个方法构建方法版本组时，只需与后续的每个版本中至多一个方法进行相似度比较。虽然，这样的限制会导致一些更名和移动的方法仍需参与克隆检测，但考虑到方法的更名或移动所占比例非常小，即使会浪费一部分时间，但与其带来的整体性能提升相比微不足道，所以这样的权衡非常具有价值。

在相同方法的判定过程中，当发现某个方法还未存在于某个方法版本组，则意味着该方法首次出现在该项目中。该方法的相同方法的查找，是将所有后续版本中与该方法完全限定名及所在文件路径相同的方法与该方法依次做比较。这表明最终形成的方法版本组中的所有方法实际上都是与同一个方法进行比较，即出现时间最早的那个方法，这样做的主要目的是避免误差累积。

选择样本方法：在上一步中我们将版本间相同的方法都构建为方法版本组，据此实现了一个历史映像提取器用于构建基准项目的历史映像。根据步骤二中的描述，每条方法版本组中包含一系列不同版本中的相同方法，根据设定的相似度阈值，相同方法间的相似度阈值高于克隆检测器判定克隆的相似度阈值，所以为了尽量减少进行克隆检测的代码规模，只需要从每个方法版本组中选取一个方法作为样本参与克隆检测即可。为了实现方便，本文统一选取所有方法版本组中最早的版本作为样本方法，一个项目中所有样本方法的集合被称作该项目的历史映像。最后，建立样本方法和方法版本组间的索引关系，该索引称为方法索引。根据这些方法索引可以快速根据样本方法定位到其所属的方法版本组。

包含三个发布版本的项目的历史映像构建过程如图1所示，图中实线方框圈出的部分表示其中一个版本的所有方法，每个方块表示一个方法。首先为不同版本的同一方法构建方法版本组，图中由一系列箭头串联起来的方法则是方法版本组。接着从方法版本组中选择出现时间最早的方法作为样本方法，即图中标记为黑色方块的方法。最后，这些被提取出的样本方法的集合就构成了该项目的历史映像。图中带有杠的箭头表示，虽然这两个方法的方法名及文件路径相同，但文本相似度较低，因此需要分别构建方法版本组。将每个项目的历史映像分别保存到一个文本文件中，以便后续的克隆检测。

图1 包含三个发布版本的项目历史映像构建示意图

2.3 克隆检测

在得到所有目标项目的历史映像后，接下来将对所有的历史映像进行跨项目克隆检测。因为我们只关心方法级的克隆，所以将克隆检测粒度设为方法级，最终经检测得到跨历史映像的方法级克隆组的集合。考虑到我们的目标项目集代码规模较大，一般的克隆检测工具可能难以支持，因此特地采用了在大规模代码上依然运行良好的克隆检测工具SAGA[26]。其支持Ⅰ型到Ⅲ型克隆的检测，利用GPU的计算能力来加速检测过程。此外，SourcererCC[25]也能支持亿行级代码的克隆检测，只是速度相对稍慢。该步骤理论上可以采用任何克隆检测工具，只需要保证检测结果能够转换成规定的形式即可。该步骤相对简单，主要是借助已有克隆检测工具对目标项目的历史映像集合进行跨项目克隆检测。

2.4 恢复全量克隆关系

在得到所有目标项目历史映像的跨项目方法级克隆组之后，结合2.2节中保存的方法索引即可恢复完整的全量克隆关系。图2给出了单个历史映像克隆组和全量克隆的大致关系。其中黑虚线方框圈出的部分为一个历史映像克隆组，该克隆组中有四个克隆方法实例，每个黑色方块表示一个样本方法，其中A、B、C方法分别来自不同的项目，A′和A来自同一个项目。图中样本方法后箭头连接的部分为其所属方法版本组的其余方法，方法所属的方法版本组可以通过追踪之前保存的方法索引得到。图中四个克隆方法所属的方法版本组则构成了该历史映像克隆组所对应的全量克隆关系。

图2 历史映像克隆组和全量克隆关系

2.5 优化方案

在基于多版本克隆检测加速技术实现工具时，为了进一步提高效率，对其中一些步骤进行了优化。

在构建方法版本组的过程中，需要进行较多的I/O操作并且方法间的相似度比较等也比较复杂，所以即使算法整体之间的复杂度为O(n)，但整体仍比较耗时。为了更快地进行大规模项目方法版本组的构建，本文使用多线程技术对方法版本组构建算法进行并行化改造，进一步加快了构建速度。在方法版本组构建过程中，不同方法的方法版本组构建之间互不影响，它们是完全独立的。这满足了并行化技术要求子任务间相互独立的前提，因此适合并行化处理。

算法1为并行化构建方法版本组算法的伪代码。首先根据经验以及多次实验比较，将并行粒度即线程池的核心线程数设置为CPU可用核数的两倍(2行-3行)。接着对于项目中每个版本的每个方法，如果该方法已经被标记，则表明该方法与更早的版本中的方法相同；否则，表明该方法是当前版本新出现的方法，将其称为目标方法，首先将其标记，接着检测后续版本中与该方法相同的方法(4行-11行)。其中，DetectSameFunction函数执行具体的相同方法的检测。该函数中，从目标版本的下个版本开始，首先查找是否存在与目标方法完全限定名及所属文件路径一致的方法，如果没有则跳过；否则比较两个方法间的相似度是否超过给定阈值，超过则表明该方法和目标方法是相同的方法，将其添加到目标方法的方法版本组中并将其标记(16行-27行)。该函数是并行化的主体部分，每当需要对某个方法进行相同方法检测时，从线程池取出一个空闲线程执行该函数，最终，等待所有线程执行完毕，算法结束。

算法1并行化构建方法版本组算法

1.functionFUNCVERGROUPCONSTRUCT(FuncInfoSetList)

2. coreSize←availableProcessors()*2

3. exec←Executors.newFixedThreadPool(coreSzie)

4.forcurrentVer∈AllVersdo

5.forcurrentFunc∈currentVers.getFuncInfoSet()do

6.ifcurrentFunc.isUnmarked()then

7. currentFunc.mark()

8. exec.submit(DetectSameFunc())

9.endif

10.endfor

11.endfor

12. exec.shutdown()

13.returnfuncVerGroupMap

14.endfunction

15.

16.functionDETECTSAMEFUNC()

17.forifromcurrentVertolastVerdo

18. targetVer←FuncInfoSetList.get(i)

19.iftargetVer.getFuncInfoSet()

.contains(currentFunc)then

20. targetFunc←targetVer

.getFuncInfoSet().get(currentFunc)

21.ifgetSimilarity(currentFunc,targetFunc)>

thresholdthen

22. funcVerGroupMap.get(currentFunc)

.add(targetFunc)

23. targetFunction.mark()

24.endif

25.endif

26.endfor

27.endfunction

3 实 验

本节我们将通过实验评估本文提出的多版本软件系统克隆检测加速技术的性能和效果。因为本文提出的是一种与具体克隆检测工具无关的克隆检测加速技术，所以不单独考虑工具的准确率等指标。实验主要采用对比实验的方式来评估与完整的全版本代码克隆检测相比，使用克隆检测加速技术，性能提升了多少。

所有实验均在一台独立的服务器上进行，其主要配置为：英特尔i7- 7820X型CPU(8核心，16线程)，32 GB主存，1 TB固态存储硬盘，CentOS7操作系统。

3.1 准备数据

首先，在目标项目的选择上，我们以Java项目为例。为了使实验更加具有说服力，我们以星数超过50、有多个发布版本为标准，从GitHub上挑选了来自不同领域的高质量Java开源项目，包括Android、Jedis、Gradle等共计251个知名项目，它们的版本时间跨度从2004年到2019年。对于每个项目，我们借助版本管理工具Git，将其所有的版本源代码抽取出来并保存，同时将其所有的版本信息保存到数据库。考虑到只关注Java源代码，同时为了节省空间以及方便后期处理，我们只保留了项目中所有的Java代码文件(.java文件)。经统计，这251个项目共有3 234个发布版本，这些发布版本共包含4 626 144个Java代码文件，总代码行数达到3亿行。

3.2 实验结果及分析

基于准备好的实验数据集，首先单独使用SAGA工具对数据集中所有项目的所有版本进行跨项目克隆检测，耗时约1 h 37 min(为保证结果可信，经过多次执行取平均值，下同)。

同样使用SAGA工具，但结合本文提出的多版本软件系统克隆检测加速技术，在同样的数据集上进行了跨项目克隆检测，以下分别统计了四个主要步骤的执行时间以便分析。

项目信息预处理：加载项目版本信息到内存，并逐个提取每个项目的方法信息，共耗时10 min 20 s。该步骤耗时较长，因为需要读取所有的近462万个Java文件并解析出其中的方法。

构建历史映像：我们的工具为251个项目的3 234个release构建历史映像并保存方法索引，共耗时7 min 30 s。所生成的251个项目的历史映像共计约四千万行代码，788 120个方法。

克隆检测：使用SAGA工具对第二步生成的历史映像进行跨项目克隆检测，共耗时1 min 36 s。

恢复全量克隆关系：在得到历史映像克隆检测结果后，需要为每个克隆组恢复全量的克隆关系，其间需要借助方法索引查找每个克隆方法所属的方法版本组，整个恢复过程共耗时5 min 20 s。

综上所述，使用SAGA工具并结合多版本软件系统克隆加速技术，整个检测过程四个步骤共耗时约25 min。与原先的1 h 37 min相比，效率提升了近4倍。

实际上，第二步生成的所有项目历史映像代码量共约四千万行，而原本所有项目的release的代码约三亿行，代码量缩减了近87%。所以真正的克隆检测只耗时1 min 36 s，效率明显提高。而在构建历史映像的过程中，用样本方法代表整个方法版本组，容忍了部分代码差异，因此克隆检测的精确度会有一定的损失。

由以上可知，采用本文的多版本克隆检测加速技术，一方面可以大大提升多版本克隆检测的效率；另一方面，极大缩小了克隆检测工具实际需要处理的代码规模，使得传统克隆检测工具能够检测更大规模的多版本软件系统。

4 结 语

在软件项目的开发过程中，开发人员出于诸多方面的考虑，往往会倾向于通过拷贝粘贴已有代码片段并伴随着或多或少的修改来满足需要，这导致软件项目中存在许多代码克隆。而代码克隆多数情况下被认为是一种代码坏味道，但在特殊情况下却是唯一选择。为了管理克隆，通常需要了解项目中各个版本的克隆情况。因此，本文提出一种快速的多版本软件系统克隆检测加速技术，并据此实现了一个多版本软件系统克隆检测加速工具，它可以快速地在亿行级代码中检测克隆，并且可以很好地适配不同的克隆检测工具。通过在大规模项目上进行实验，证明了该方法的高效性和可用性。

目前，本文的工具还处于雏形阶段，仍有许多细节亟待完善。一方面，在进行版本间相同方法映射时仍然耗费较多的时间；另一方面，该工具目前只提供了方法级的克隆检测加速。本文下一步将在此基础上针对片段级的克隆检测加速制定类似的解决方案，并考虑设计更加高效的版本间方法映射技术。