1-前言
代码克隆（Code clone），是指存在于代码库中两个及两个以上相同或者相似的源代码片段，是软件开发中的常见现象。代码克隆能够提高效率，但也可能意外引入外部漏洞。下文是对代码克隆检测技术的简单整理。
2-克隆的类型
代码克隆的类型主要分为两大类，句法克隆(syntactic clones)和语义克隆(semantic clones)。句法克隆指文本相似的代码片段, 语义克隆则是指功能相似的代码片段。基于这两大类，代码克隆可以被划分为四小类，其中前三种为句法克隆，第四种为语义克隆。
| 类型 | ||
|---|---|---|
| Type-1 | 句法克隆 | 去除空格，空行和注释后，完全相同 |
| Type-2 | 句法克隆 | 除了对一些unique identifiers（函数名，类名，变量）重命名以外，完全相同 |
| Type-3 | 句法克隆 | 片段部分被修改，如添加或删除了部分代码片段，或是重新排序了部分代码片段 |
| Type-4 | 语义克隆 | 语义相似，但句法不相似（非常难检测） |
当前，学术界对Type1,2,3类克隆的检测已颇为成熟，尤其是对Java和C++语言的克隆检测； 而对Type4类克隆的检测准确率仍不高，无法达到工业界应用标准。
四类的代码示例可参照下图——
其中s1,s2,s3,s4 分别对照Type-1，2，3，4类的代码形式，加粗部分为修改部分。
3-克隆检测的通用流程
通览代码克隆检测领域的相关论文，可以发现代码克隆检测通常分三步走。
- 将源码拆分为对比单元（comparison units, 如class，function，block，statement）
- 将对比单元转化为中间表达（IR, Intermediate Representation，如token，AST, PDG）
- 再对这些对比单元的IR进行match detection（对比），通常是将对比单元组成clone pair的形式：一次对比两个（c1, c2）或是多个（c1, c2, c3）
4-克隆检测算法的分类
代码克隆检测发展至今，主要分为五大类检测思想: Textual, Token, Syntactic, Semantic, Learning.其具体分类见下图。
- Textual：代码片段以文本/字符串/词法的形式相互比较，并且只有在两个代码片段在文本内容方面确实相同时才被发现被克隆。
- Token：在编译器的词法分析阶段，所有源代码行都被划分为一系列Token。 然后将所有Token转换回Token序列。
- Syntactic（句法分析）：
- 基于树: 提取的AST用于子树比较以识别相似区域。
- 基于度量：通过源代码收集度量，然后使用这些度量为每个代码片段生成向量。然后使用向量对代码的相似度进行对比。
- Semantic：主要检测代码片段不同，但功能相同的函数（Type4）
- Learning : 通过机器学习和统计分析的方式来进行克隆检测
这几类对应的具体算法见下——
1. Textual
图中的oss指open source software
2. Token
3. Syntactic
3.1 Tree
3.2 Metric
4. Semantic
4.1 PDG
4.2 Other
5. Learning
5.1 ML
5.2 Other Learning
克隆检测的历史趋势
有关代码克隆检测的最早和最开创性的工作是在1990年代初期完成的，如下表所示。可以看出除了近年兴起的ML方法以外，代码克隆检测的开创性工作均在90年代和00年代就已完成，这也是笔者说该领域已颇为成熟的原因。
| 名称 | 算法思想 | 检测级别 |
|---|---|---|
| Baker,1992 | line-by-line comparison | Type-1,2 |
| Dup,1995 | parameterization | Type-1,2 |
| CloneDR，1998 | AST | Type-1,2 |
| CCFinder，2002 | token stream, a prefix tree and a novel matching algorithm, | Type-1,2 支持在分钟内实现百万行代码的检测。支持代码类型：C，C++，Java，COBOL |
| CP-Miner,2004 | 类CCFinder | bug-detection |
| Deckard, 2007 | tree-based | 在大型数据集上有很好的表现，如Linux Kernel。可以检测 Type-1,2,3类的代码克隆 |
Benchmarks 基准
除了工具本身之外，在代码克隆检测工具的基准测试和有效性测试领域也有许多发展。其中比较有名的是Bellon’s benchmark（2007）和 BigCloneBench（2015）
| 基准 | 发布时间 | 描述 |
|---|---|---|
| Bellon’s benchmark | 2007 | 在两个小型C程序和两个小型Java程序上运行六个不同的代码克隆工具，并收集克隆结果。 将这些结果与真实代码克隆的主体进行比较，创建出代码克隆数据集。 |
| BigCloneBench | 2015 | BigCloneBench是IJaDataset-2.0（一个包含25,000个开源Java系统的大数据软件存储库）中800万个经过验证的克隆的集合。包含项目内和项目间的全部四种主要克隆类型。 |
开源工具
笔者整理了部分已开源的学术成果，地址见下。
References
[1] Walker A, Cerny T, Song E. Open-source tools and benchmarks for code-clone detection: past, present, and future trends[J]. ACM SIGAPP Applied Computing Review, 2020, 19(4): 28-39.
[2] Roy C K, Cordy J R, Koschke R. Comparison and evaluation of code clone detection techniques and tools: A qualitative approach[J]. Science of computer programming, 2009, 74(7): 470-495.
