摘 要： 克隆代码是指在软件源程序中存在的相同或相似的代码片段。克隆代码在很多软件工程中，例如程序理解，代码质量分析，剽窃检测，漏洞查找和病毒检测，都需要通过找出语义或语法上相似的代码片段来实现。目前常用的检测方法有四种：基于文本（text-based）的检测，基于字符序列（token-based）的检测，基于语法树（tree-based）的检测和基于关系图（PDG-based）的检测。基于字符序列的克隆检测首先对源程序进行预处理转换，再经过匹配算法得到克隆检测结果。克隆代码的检测是软件分析的一个重要的部分。

　　关键词：克隆代码；克隆检测；标识符；代码转换；检测算法

　　　Abstract: In source codes, the code clone is usually referred to as a code fragment that is identical or near-identical to another. Many other software engineering tasks, such as program understanding, code quality analysis, plagiarism detection, virus detection and bug detection may require the extraction of syntactically or semantically similar code fragments. There are currently four types of clone detection techniques: text-based technique, token-based technique, tree-based technique and PDG-based technique. The token-based detection technique should preprocess the sources code and then carry out clone detection result by the matching algorithm. Clone code detection is an important part of software analysis.

　　Key words: clone code; clone detection; token based; code transformation; detection algorithm

　　1  引 言

　　什么是克隆代码？通常的克隆代码定义是指在软件中存在的相同或相似的代码片段。“相同”和“相似”这两个单词对定义很模糊，目前大部分关于克隆代码分析的资料也没有给出一个明确的定义[1]。在程序开发中，对代码的“复制-粘贴”并经过稍微的改动或者不改动，是一种常见的对代码的再利用，但这种方式导致了程序中存在相似或相同的代码。以前的研究表明，在一个典型的软件系统中，很大一部分（7％至23％的代码）是被克隆的[2]。尽管这种克隆是故意的而且高质量的代码克隆方式能反映出程序的设计意图，可以节省开发成本，但克隆代码的存在对软件的维护和更新有很大的危害，维护或更新一段克隆代码会使工作量翻倍。这种复用克隆机制是非正式的、不可控的，一般为不会有文档记录这种复用，因而会带来一系列的软件维护问题[6]。尤其在大型软件系统中，假如在一段克隆代码中检测出了一个bug，那么所有的这个代码的克隆代码都必须要修改。因此在大型软件系统中对克隆代码的检测和分析是十分必要的。

　　2. 克隆代码检测过程

　　2.1 克隆对和克隆类的定义

　　两个代码片段之间当且仅当他们是相似的序列时，称他们之间存在克隆关系。根据克隆关系可以定义克隆对和克隆类：满足克隆关系的一对代码片段被称作克隆对。克隆类是一个由克隆对组成的最大集合，在这个集合里任意两个代码片段都满足克隆关系[4]。

　　2.2 代码的预处理

　　克隆检测分析流程，Fig 2.2,在进行克隆检测之前，通常会对源程序进行预处理，来减少检测的范围。通过程序语言的词法分析把源程序的每一行都转换成token，再把所有的token都转换成一个token字符串。

　　Fig 2.2 程序分析流程图                              Fig.2.3.1 Java示例

　　2.3 原代码的转换

　　为了有效地对软件中的克隆代码进行分析，首先要对源程序进行转换，生成抽象的中间形式。通过第一步把每个源程序文件都对应生成一个token串，每个生成的token串中含有大量与克隆代码检测无关的信息，在检查之前要去掉 与克隆检测无关的信息，对源代码进行转换。转换流程包括：（1）制定转化规则，去掉不影响检测结果的字符，例如源代码中的空格、注释行等。（2）在源程序中变量、类型和常量都有一个标识符，完成第一步后用一个特殊的符号来替换这些标识符。（3）最终把源程序转换成一个长的字符串序列

　　Fig.2.3.1 Java的转换规则

　　用一个简单的Java的程序例子，Fig.2.3.1，来说明如何对源代码进行转换。左边的数字是行号，把每一行的输入划分成字符串，通过Fig.2.3.1的规则把源代码转换，删掉3、5的注释行和1的关键字。再用符号$p来代替源代码中的参数，最终生成一个长的token序列：

　　$p $p （ $p $p ） { $p $p = $p ; for （； $p < $p; $p++ ）{ $p.$p.$p（ $p ） } }

　　3 相似阀值

　　为了判断两条token序列之间是否存在克隆关系，需要引入一个参数来判定，这个参数称为相似阀值。用户预先要指定一个最小的相似度，即相似阀值θ，如果两条token序列的相似度检测超过了相似阀值，那么就可判断这两条序列之间存在克隆关系，构成了克隆对。

　　根据Baxter的定义，假设序列A和序列B，这两个序列的相似度sim（A,B）的计算如下：

　　S = 两个序列的公共子序列中的元素个数

　　L = 序列A中除去S以外的元素的个数

　　R = 序列B中除去S以外的元素的个数

　　序列A和B之间存在克隆关系  Sim（A,B）≥θ，0≤θ≤1

　　4 相似度检测算法

　　对程序源代码进行转换预处理转换后生成的标记（token）序列进行相似度的检测。常用的字符串匹配技术算法有LCS算法。

　　LCS（Longest Common Subsequence, 简称LCS）算法用于计算两个字符串的最长公共子序列。最长公共子序列是将两个给定的字符串分别删去零个或多个字符后得到的最长的相同字符串序列。有两个序列 A = <> 和 B = <>,假设存在序列C = <| ?1 ≤ i ≤ k, ci∈ B>, 如果存在一个递增的序列<>, 这个递增序列最大就是C的长度，并且对于所有的 j = 1, 2, … , k, ，那么序列C就是序列A和B的最长公共子序列。例如字符串paceddaa和paddaeca的最长公公子序列为：paddaa.传统上，LCS算法一般可采用动态规划策略求解，其解发可用一个递归函数来表示，如下[1]：

　　其中：

　　Sl = Sl（1）S1（2）…Sl（n） 和 S2 = S2（1）S2（2）…S2（m）为两个序列片段；

　　Sk（i,j）表示Sk（i） Sk（i+1）…Sk（j）的子字符串（其中K=1或2）。

　　M（i,j）表示S1（1,i）和S2（1,j）之间的LCS的长度。

　　通过计算所有的M（i,j）可以得到一个得分矩阵。从矩阵的右下角最大的得分开始通过回溯可以得到是S1和S2的LCS[5]。LCS算法的时间复杂度为。

　　5  结 论

　　本文说明了克隆代码的概念和产生的原因，以及介绍了基于token序列的代码克隆检测的方法。

　　克隆代码检测技术，目前问题就是检测精度和检测所需的时间以及空间，如何在占用更短更少的时间和空间下，更精确的检测出所有的克隆代码。可以通过改进算法来实现这一目的。LCS算法也有很大的局限，比如不能检测出改变了位置的克隆。以后主要任务在于改进优化匹配检测算法，以减少测试时间或者减少对内存的使用量。

　　参考文献：

　　[1]B.S. Baker. A Program for Identifying Duplicated Code[C]. Proc. Computing Science and Statistics: 24th Symp. Interface, vol. 24, pp. 49-57, Mar. 1992.

　　[2] Chanchal Kumar Roy, James R. Cordy. A Survey on Software Clone Detection Research[R]. School of Computing,

　　Queen's University at Kingston, Tech. Rep. 2007-451, 2007.

　　[3] Toshihiro Kamiya, Shinji Kusumoto, Katsuro Inoue. CCFinder: A Multilinguistic Token-Based Code Clone Detection System for Large Scale Source Code[C].IEEE translations on software engineering, VOL. 28, NO. 7, JULY 2002.

　　[4] 曹羽中，金茂忠，刘超。克隆代码检测技术综述[J]. 计算机工程于应用，2006,28（z2）。

　　[5]王映龙，杨炳儒， 等。 基因序列相似程度的LCS算法研究[J]. 计算机工程于应用，2007,43（31）。