克隆代码研究综述

1克隆代码技术研究综述1研究背景软件系统中克隆代码的检测与管理是软件工程中的基本问题之一，在软件的质量维护架构进化专利和剽窃等众多领域有着广泛的应用需求。程序员为了提高开发效率经常对软件系统的源代码进行拷贝粘贴及修改活动，这种重用机制通常会导致在源代码库中出现很多相同或相似的代码段，这类代码段被称为克隆代码。2由于使用特定的设计模式、框架及API等来完成相似的程序任务，也会产生一些无意的克隆代码。克隆代码在软件工程中是有益的，但在许多情况下也可能是有害的。31.1克隆代码的益处复制一段无缺陷的源代码，可降低编写新代码的潜在风险；节省开发和设计新代码的时间与成本；克隆代码能解耦组件或类之间的关联，使得相似功能的代码容易独立进化；在实时软件中，代码的复制可降低函数调用的时间成本。41.2克隆代码的害处克隆代码导致源代码的规模增大即冗余，增加了资源的需求，这对于嵌入式系统和手持设备等的不利影响尤为明显;复制一段含有未知bug的代码，可能会导致bug的繁殖;维护者修改一段代码时，需对这段代码的所有克隆进行一致的修改，若修改不一致则会引入新的bug;52克隆代码的相关术语依据源代码的文本相似性与功能相似性将克隆代码分成四类：a)除了空格与注释外都相同的代码段;b)除了标志符类型空格和注释外句法上都相同的代码段；c)对语句做了增/删/改的复制代码段;d)功能上相同但句法上不同的代码段；第1类称为完全克隆，将第2、3类称为近似克隆，第4类称为语义克隆；6研究者时常使用到克隆对这一概念，它是指一对相似的代码段；克隆群(clonegroup)是由两个或多个克隆代码组成的集合，其中任意一对克隆代码都相同或相似；由于研究的对象和目标不同，克隆代码会有不同的粒度，主要是文件克隆、类克隆、函数克隆、块克隆以及语句克隆；72克隆代码的检测克隆检测是指在软件系统的源代码中找出具有高相似性的代码段，它是克隆研究领域的基础性工作，为后期更深入的探究提供基础数据。该过程非常耗时，需比较所有代码段的相似性。82.1克隆检测过程预处理：将目标语言的源文件选择出来，过滤掉与目标语言无关的源代码，将源代码分割成不相交的比较单元。转换：比较单元的源代码转换成中间表示形式（token、AST、PDG、低级语言）。匹配检测：选用合适的算法匹配前期处理过的比较单元，聚类相似的比较单元即形成克隆群。克隆报告92.2克隆检测的技术与工具基于文本的检测：该方法是在软件系统的源代码上直接进行比较处理。基于词法(token)的检测：首先使用词法分析工具将所有源代码的每一行转换成一个token序列，并将所有序列连接成一个token串;接着扫描这个token以查找相似的token子序列，然后报告这些相似子串所对应的源代码为克隆。10基于语法的检测：根据相似的代码段应该也有相似的句法结构而设计的程序被解析成一棵语法树，其中相似的子树所对应的源代码段就是克隆代码。基于语义的检测：主要以PDG(程序依赖图)方法为代表，即给定一个程序，根据程序语句之间的数据流和控制依赖关系建立一个PDG的集合，在此集合中的同构子图所对应的代码段为克隆代码。11基于metrics(度量标准)的检测：首先将源代码解析成AST或CFG(控制流图)，然后在AST或CFG上统计相应的metrics，最后通过metrics向量的相似性比较得出克隆代码。基于低级语言的检测：该技术通过比较由编译器产生的低级语言代码(如汇编代码、 Java字节码）的相似性进而识别出源代码的相似性。122.3克隆检测技术的优缺点基于文本的方法不需考虑程序句法的正确性，时空复杂度最低，该方法主要用来检测第1类克隆。基于token的方法拥有上述方法的优点，且独立于源代码，但在处理第3类的克隆时会有许多误检。基于语法的方法能有效地检测第1～3类克隆，但由于需将源代码解析成AST后再查找相似子树，所以时空复杂度偏高。13基于pdg的技术从更高层面去分析获得程序的语义，该技术能检测到一些被打乱顺序但语义相同的代码段，但建立pdg和寻找同构子图代价高昂。基于metrics的方法与基于AST方法的时空复杂度相近，由于不同代码段的metrics的值有时会相同，导致较高的误检率。基于低级语言的方法消除了高级语言的不一致书写格式，但源代码上一个细小差异可能会导致低级语言的字节序列显著不同，进而漏检掉一些克隆代码142.4克隆检测在其他领域的应用检测克隆代码相关的bug模型克隆检测源代码的抄袭检测为程序库(library)检测候选代码软件的版权153克隆代码的进化随着软件系统的升级或维护，克隆代码也会发生相应的进化。通过分析克隆进化能揭示克隆代码的动态特征，有助于开发者更全面地理解和管理克隆。克隆进化的研究主要集中在两方面:从宏观的角度分析软件系统中克隆代码的密度变化，从微观角度研究克隆代码在软件进化过程中的变化并评价其有害性或稳定性。16为了从微观的角度去观察克隆群的演化，故提出了克隆家系。首先收集N个版本的源代码并按时间排序，接着使用克隆检测工具检测出每个版本中的克隆群，然后利用CVS中的位置关系将后版本中的克隆群往前版本映射，根据克隆群的变化情况标记上相应的进化模式，进而得到直系克隆，最后起源于相同克隆群的直系克隆组成了一个克隆家系。17一个克隆家系描述了某个克隆群在软件系统版本间的进化历史，也反映了程序员如何创建繁殖和进化克隆代码。18194克隆代码的管理4.1避免克隆代码在软件开发时，通过克隆检测相关技术阻止克隆代码的产生。两种方式来管理克隆:a)在加入一个新函数时保证其在源代码中没有复本或存在特殊原因可使它以克隆的形式加入到系统中;b)在修改一个函数时，能一致地修改克隆函数204.2克隆代码的重构克隆重构可降低系统的复杂性减少由克隆代码所引起的错误和提高系统的可理解性，不过应有选择地对克隆代码进行重构。目前最常用的两种克隆重构方法是exstractmethod和pull-upmethodExstractmethod是指选取一个代码块作为一个新的方法(函数)，然后用此方法的调用来替换原先的克隆代码，它适合应用在目标代码与周围代码耦合程度低的场景21

Pull-upmethod是通过在公共父类

中引入通用方法以替换几个子类中相似的方法(函数)该方法适合对具有公共父类的子类重构。224.3其他的克隆代码管理

由于软件系统中克隆代码的不一致修改可能会引入一些新bug，所以研究者通过开发一些集成了克隆检测的同步编辑器来降低这类风险。

Toomim等人研发了一款能对克隆代码进行同步修改的工具Codelink。235.总结在克隆进化方面，研究者提出了许多研究方法与策略以期获得更好的效果;

研究者对克隆重构极为关注，并提出了一些重构技术和重构调度策略以降低克隆代码给软件维护带来的危害;在克隆管理方面，出现了许多管理技术，如克隆的避免克隆的一致修改和克隆的跟踪等.24亟待解决的问题:a)克隆代码的定义具有很大的模糊性，限制了克隆代码研究的进一步发展，并导致没有统一的标准去有效地衡量克隆检测技术和工具的性能与准确性;b)现有的克隆检测工具在检测第3~4类克隆时存在一定的缺陷;c)克隆代码检测及相邻版本间克隆映射的准确性决定了克隆进化研究的意义与价值，而现有的方法与技术在解决这两个问题时存在一定的不足;25d)由于一