克隆代码检测技术研究

2019-08-22张丽萍

计算机技术与发展 2019年8期

关键词：源代码克隆代码

侯敏，张丽萍

(内蒙古师范大学计算机与信息工程学院，内蒙古呼和浩特 010022)

0 引言

在软件开发和维护过程中复制代码片段是常见的操作，这种重复使用的代码被称为克隆代码(clone code)，其与软件工程领域中各种问题密切相关，如：软件质量、演化、复杂性、架构、复用，以及软件授权、反剽窃等[1]。

研究人员发现克隆代码可能会影响软件系统的质量，特别是对软件的维护和阅读理解[2]，也可能导致引入潜在Bug。因此大多数时候克隆被认为对软件的演化有负面影响，是一种坏气味[3]。

检测大型软件系统的克隆代码并进行相应的维护是非常重要的。大量的克隆代码不仅增加了系统的规模且会降低软件代码质量，如遗漏的继承或缺失的程序抽象。现有技术可以自动找到这些克隆代码[4-5]，然后通过源代码重构等操作修改或删除有害的克隆代码。近年来，克隆代码检测的相关研究成为代码分析领域中一个十分活跃的分支[4]。

文中对相关的克隆检测技术进行了总结，首先描述了文献中常用的克隆术语，以及常用克隆类型；其次分析了现有的克隆检测框架、检测方法、检测工具，并对不同检测技术进行了比较；然后指出了克隆检测技术在软件工程其他领域中的应用。

1 相关概念

1.1 克隆

克隆片段(clone fragment)：源代码中一段连续的代码序列(有或者无注释)，可能是一个函数、方法或者代码块。两个克隆片段之间的相似程度达到某一设定的阈值就构成了克隆关系(clone relationship)。两个具有克隆关系的片段组成一个克隆对(clone pair)，多个具有克隆关系的片段则形成了一个克隆群(clone group)，即克隆类(clone class)。在研究软件中的克隆时，会按照不同的克隆粒度进行分析，研究粒度[6-8]通常可分为文件、类、函数、语句和块等。

1.2 克隆类型

尽管研究者将克隆代码称为相同或者相似的代码，但并没有给出明确的定义。现有研究[6]根据代码片段之间文本和功能的差异将克隆分为了Type-1、Type-2、Type-3以及Type-4，四种克隆类型的描述如表1所示。

表1 克隆类型描述

2 克隆检测过程

一般来说，克隆检测通常会遵循一定的步骤和阶段(有些阶段并不是必须的)，具体检测过程如图1所示。不同的检测方法会侧重其中某几个阶段。

图1 克隆检测过程

(1)预处理阶段：在这个阶段的克隆检测过程包括三部分：①去除无关项：统一源代码布局和去除检测无关的字符串(如空白符、注释)，为的是减少比较和计算次数从而降低无关项对检测结果的影响；②确定源单元：剩余的源代码分成一组不相交的片段称为源单元，这些单元都参与了直接克隆关系的相互关系；③确定比较单元：根据所使用的源单元的比较算法，可能需要进一步划分成更小的单元。

(2)转换阶段：这一阶段除了基于文本的方法都会用到，将源代码的变量、标识符转换成一个相应的中间表示形式进行比较。①提取Tokens串：通过词法分析器将源代码进行Token化，每行源代码转化为一组Token序列；②提取抽象语法树(abstract syntax tree，AST)：将源代码转换为一组抽象语法树，通过比较子树获取检测结果；③程序依赖图(program dependency graph，PDG)：一个程序依赖图表示控制和数据图，每个节点表示程序的语句和条件，通过语义技术从源代码生成子图进行比较。

(3)检测匹配阶段：源代码预处理和转换之后的结果作为此阶段的输入，并根据相应的算法对源单元和比较单元进行计算，之后将相邻的小的单元合并成大的单元。匹配检测的输出是表示或聚集的转化代码中的匹配列表，形成一组候选克隆对。每个克隆对通常表示为变换后的代码中每一个对应相匹配的片段源坐标。常见的匹配算法有动态模式匹配(dynamic pattern matching，DPM)[9]、最长公共子序列(longest common subsequence，LCS)[10]、后缀数组(suffix-trees)[11]等等。

(4)格式化阶段：在这个阶段中，将在上一阶段通过比较算法所获得的克隆对列表转换成与原始源代码相对应的新克隆对列表。本阶段实现的是从上一阶段获得的克隆结果与原始结果的映射，得到新克隆对和克隆类的位置之后，将其转换成原始源文件上对应的位置。

(5)后处理阶段(过滤)。

此阶段并不是所有克隆检测工具必须的，通过使用手动分析[6]或自动启发式的方式过滤或排名检测出的克隆代码，筛选出误报或漏报的克隆。自动启发式过滤根据多样性、频率、长度或克隆的其他特性自动排列和过滤候选克隆。此外，为了减少数据量，克隆对应该被聚集成克隆类、克隆群或者集合。

(6)检测结果可视化阶段。

为了能够让研究人员更加直观清晰地看到软件系统中的克隆代码，需要一种易于理解的方式对检测结果进行存储和可视化。较为常用的存储方式有超文本标记语言(hypertext markup language，HTML)和可扩展标记语言(extensible markup language，XML)，它们都有相对应的节点，可以清晰地表示克隆之间的链接关系和包含关系。此外还通过一些饼图、散点图、折线图以及柱状图展示克隆片段的分布和数量。

3 克隆代码检测方法及工具

现有研究中存在较多不同的克隆检测方法，这些技术都能够找到软件系统中的克隆代码，绝大多数的克隆检测技术被分为五种类型。这一部分主要阐述每一类克隆检测技术的详细细节。

3.1 基于文本的克隆检测方法

基于文本的克隆检测技术[12]将软件系统中的源代码看作字符序列，并去除源代码中的注释、空白符和新增行等无用部分，然后比较代码中每个字符序列相似度并返回字符串匹配结果集。

研究者们研究和开发出了各种基于文本的克隆检测工具。Baker[13]使用基于代码行的字符匹配算法开发出了克隆检测工具—Dup，但此工具不能检测不同风格的程序代码。Cordy等[14]使用基于文本的方法检测HTML网页中的近似克隆，但它无法标准化所有的代码，且使用的也是最小的比较单元。基于字符串的动态模式匹配算法由Ducasse等[15]提出，该算法可以独立于程序设计语言使用，由于代码的内聚性，这种技术不能以独立于程序设计语言的方式确定有意义的克隆代码。此后，Roy等[16]开发的 NICAD应用灵活的过滤和规范化机制对文本检测进行改进，可有效检测Type-1、Type-2以及Type-3克隆。

3.2 基于Token的克隆检测方法

与基于文本的检测方法类似，此方法在检测之前先基于Token的转换工具进行解析，将源代码转化成一种中间表示形式—Token序列，基于Token的检测工具会规定每个克隆片段的最小Token长度。在检测过程中，利用匹配规则比较Token序列以便定位。

Kamiya等[17]开发了一款名为CCFinder的克隆检测工具。该工具将源代码中每一行单独转化为Token序列，然后合并所有的Token序列，这样做是因为即使变量名和代码结构发生变化也不会影响检测结果。Baker[18]也使用Token方法检测克隆，但没有使用任何转化技术，导致较多的误报率。更为灵活的Token化方法RTF[19]使用后缀数组(suffix array)而不是后缀树(suffix tree)，后缀数组可以删除不必要的Token序列从而降低虚假检测次数，但此技术实现较为复杂。张久杰等[20]提出了基于Token编辑距离的检测方法，并实现了一款名为FClones的原型工具。

3.3 基于树的克隆检测方法

基于语法树的检测方法在匹配定位克隆对之前也要进行代码解析。在解析过程中，检测工具创建一棵解析树或者抽象语法树(abstract syntax tree，AST)来表示源代码。

Baxter等[21]利用抽象语法树开发出了一款检测工具CloneDR，是基于树的一款非常好的检测工具，生成解析树，然后通过哈希函数匹配子树。但是这款工具不能够识别类似的克隆。为了克服这一问题，Bauhaus等基于避免散列和相似性度量的方法开发了CCdiml[22]工具，但是不能够识别重命名的标识符。Wahler等[23]将源代码解析成AST并存入可标记扩展语言(extensive markup language，XML)，然后通过数据挖据技术检测并提取克隆。

3.4 基于程序依赖图的检测方法

基于程序依赖图(program dependency graph，PDG)的技术利用静态分析方法将源代码抽取成控制流和数据流图，再通过比较及匹配子图定位并检测克隆。由于程序依赖图保留了源程序的语义特征，因此此类方法的准确度相对较高并且能够检测出Type-4克隆代码。

Komondoor等[24]使用一种名为PDG-DUP的技术，此技术使用程序切片(program slicing)的方法在不改变其语义的前提下识别克隆群。Gallagher等[25]扩展了Komomdoor等的工作，将程序切片应用到了所有的代码变量，但是并没有得到任何结论。Krinke[5]将PDG技术当作一种迭代方法，以便寻找最相似的子图，但却不能给一个适用任何类型系统寻找克隆的公式。2008年，Gabel等[26]将PDG中的子图同构问题规约为子树同构问题，再利用DECKARD进行检测，以提高检测的速度和可扩展性。最近，Higo等[27]报告了一种基于启发式策略的PDG检测技术，较好地推进了该类技术的实用性。

所有的研究人员使用PDG技术之后得出的结论是：虽然基于程序依赖图的检测技术可以找到非连续的克隆，但它不能应用于大型系统。

3.5 基于度量的检测方法

基于度量(metrics)的方法将源代码分割成若干个小的度量单元(例如，一行，一种方法，一个类)，这种方法并没有直接比较源代码，而是计算度量单位之间的不同。若代码段的计算值相同，则被确定为克隆。

Mayrand等[4]利用这一技术，根据代码的名称、布局的度量和控制流进行计算，但是无法识别基于复制粘贴操作的代码段。Kontogiannis等[28]利用马尔可夫链模型进行检测，但此方法只能计算代码之间的相似性而不是精确地寻找克隆。Lanubile Calefato使用eMetrics工具识别克隆，然后通过手动检查来发现已提取的克隆正确与否，但显然这种手动方法不适合大型系统[29]。Grant等[30]将数字信号处理领域的独立分量分析(independent component analysis)技术用于代码克隆的检测，初步结果显示该方法具有较好的效果。南京大学计算机软件新技术国家重点实验室的董加星[31]针对C语言程序提出了一种面向功能类似程序的克隆检测方法，通过提取代码的度量特征进行检测。

3.6 其他检测方法

国外在克隆检测方面的研究较多，Sudhamani等[32]提出了一种基于控制语句顺序和内容的克隆代码检测方法。该方法独立于程序设计语言，并能够检测多种类型的克隆代码；Sheneamer等[33]提出一种基于粗粒度和细粒度混合的克隆代码检测方法，提高了准确率。国内的相关研究中，哈尔滨工业大学的边奕心等提出一种使用哈希值和标识符冲突率来消除克隆代码检测的部分误检的方法[34]；复旦大学的王海等在2013年提出了基于分组的代码克隆增量检测方法[35]。另外，北京大学的王浩宇等在2014年提出一种基于代码检测技术的Android应用重打包检测方法[36]。

3.7 克隆检测技术小结

现有研究中有较多克隆检测技术以及对应的检测工具，文中从抽象过程、表示形式、代表工具、优缺点等几个方面对上述检测技术进行分析比较，具体如表2所示。

表2 克隆检测技术比较

4 克隆检测技术应用

4.1 克隆重构

克隆代码重构是一种重组现有的克隆代码而不改变其外部行为或功能的技术，它能够提高设计、灵活性和简单性，而不改变程序的外部行为。克隆代码重构或去除是用来提高系统的可维护性和可理解性的一种技术[38]。Kim等[39]在克隆检测的基础上分析了克隆代码的重构性，发现克隆代码的生命周期较短，且对于被修改的长寿命克隆代码处在同一类中，认为克隆代码重构并不是提高软件质量的完美方式。Meng等[40]设计并实现了一款名为RASE的自动重构代码工具，RASE包括四种不同类型的克隆重构方法。

4.2 抄袭检测

克隆代码检测方法可用于软件代码的抄袭检测。DUP[41]是一个用来发现软件代码部分相似的匹配技术。JPlag[42]是另一种能够通过文本和程序结构的字节比较，找到C，C++，Java程序语言编写的相似之处的工具。

4.3 克隆避免

现有研究中有三种方法，两种方法主要讨论如何检测克隆和如何去除克隆，另一种为如何避免克隆。Lague等[43]在软件开发中使用两种方式的克隆代码检测工具，第一种方法是使用代码克隆检测作为预防性控制，即在系统写入代码片段之前，检查任何附加的代码片段是否是任何现有代码片段的复制版本；第二种方式为问题挖掘，在系统中搜索并修改相互之间类似的代码片段。

4.4 Bug检测

克隆检测和软件缺陷检测也有密切的关系。特别是可以通过克隆检测工具检测到复制粘贴的软件Bug。现有的可用于查找代码缺陷的检测工具有CPMiner[44]。Higo等提出了一种有效地检测由复制粘贴编程引起错误的方法。他们的算法都是使用现有的克隆检测工具，如CCFinderX[17]。然而，目前还不清楚错误检测技术如何帮助克隆检测研究。