软件克隆检测技术研究

软件克隆检测在软件维护、软件结构优化等方面具有重要价值和意义。综述了软件克隆的定义与分类,对软件克隆的检测过程进行了划分和讨论,介绍了软件克隆检测领域最为活跃的代码克隆检测技术和模型克隆检测技术。最后对软件克隆检测的研究现状和急需解决的问题进行了分析,展望了该领域未来的研究方向。     

代码克隆检测研究进展

代码克隆（code clone）,是指存在于代码库中两个及以上相同或者相似的源代码片段.代码克隆相关问题是软件工程领域研究的重要课题.代码克隆是软件开发中的常见现象,它能够提高效率,产生一定的正面效益.但是研究表明,代码克隆也会对软件系统的开发、维护产生负面的影响,包括降低软件稳定性,造成代码库冗余和软件缺陷传播等.代码克隆检测技术旨在寻找检测代码克隆的自动化方法,从而用较低成本减少代码克隆的负面效应.研究者们在代码克隆检测方面获得了一系列的检测技术成果,根据这些技术利用源代码信息的程度不同,可以将它们分为基于文本、词汇、语法、语义4个层次.现有的检测技术针对文本相似的克隆取得了有效的检测结果,但同时也面临着更高抽象层次克隆的挑战,亟待更先进的理论、技术来解决.着重从源代码表征方式角度入手,对近年来代码克隆检测研究进展进行了梳理和总结.主要内容包括：（1）根据源代码表征方式阐述并归类了现有的克隆检测方法;（2）总结了模型评估中使用的实验验证方法与性能评估指标;（3）从科学性、实用性和技术难点这3个方面归纳总结了代码克隆研究的关键问题,围绕数据标注、表征方法、模型构建和工程实践4个方面,阐述了问题的可能解决思路和研究的未来发展趋势.     

预训练增强的代码克隆检测技术

代码克隆检测是软件工程领域的一项重要任务,对于语义相似但语法差距较大的四型代码克隆的检测尤为困难.基于深度学习的方法在四型代码克隆的检测上已经取得了较好的效果,但是使用人工标注的代码克隆对进行监督学习的成本较高.提出了两种简单有效的预训练策略来增强基于深度学习的代码克隆检测模型的代码表示,以减少监督学习模型中对大规模训练数据集的需求.首先,使用ngram子词丰富对词嵌入模型进行预训练,以增强克隆检测模型对词表之外的词的表示.同时,采用函数名预测作为辅助任务对克隆检测模型参数进行预训练.通过这两个预训练策略,可以得到一个有更准确的代码表示能力的模型,模型被用来作为克隆检测中的代码表示模型并在克隆检测任务上进行有监督训练.在标准数据集BigCloneBench (BCB)和OJClone上进行实验.结果表明采用两种预训练增强的模型仅仅使用极少量的训练样例(BCB上100个克隆对和100个非克隆对, OJClone上200个克隆对和200个非克隆对)就能达到现有方法使用超过6百万个训练样例得到的结果.     

克隆代码技术研究综述

软件系统中克隆代码的检测与管理是软件工程中的基本问题之一, 在软件的质量、维护、架构、进化、专利和剽窃等众多领域有着广泛的应用需求。综述了克隆检测的过程、技术及其优缺点、克隆进化方向上的相关研究, 以及克隆管理的一些技术, 并特别介绍了克隆重构技术。最后概括了该领域所取得的研究成果, 并讨论了目前克隆代码研究中所遇到的挑战性问题。     

克隆代码分析方法研究

针对已有克隆代码检测工具只输出克隆组形式的检测结果,而无法分析克隆代码对软件质量的影响问题,提出危害软件质量的关键克隆代码的识别方法。首先,定义了克隆代码的统一表示形式,使之可以分析各种克隆检测工具的检测结果;接下来,解析源程序和克隆检测结果,识别标识符命名不一致性潜在缺陷;然后,定义了克隆关联图,在此基础上检测跨越多个实现不同功能的文件、危害软件可维护性的克隆代码;最后,对检测结果进行可视化统计分析。本文的克隆代码分析工具被应用于分析开源代码httpd,检测出了1组标识符命名不一致的克隆代码和44组危害软件可维护性的关键克隆类,实验结果表明,本文方法可以有效辅助软件开发和维护人员分析、维护克隆代码。     

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

在软件系统中,相同或相似的代码片段称为代码克隆。目前研究人员已经提出了一些克隆检测方法。这些方法通常仅针对软件系统单个版本进行克隆检测,而在部分场景下,如构建克隆演化谱系时,需要对系统每个版本进行克隆检测,则尤为耗时。为此,提出一种针对多版本软件系统的克隆检测加速技术,可以快速得到每个版本的克隆情况。该技术通过版本间方法映射技术为不同版本代码内容高度相似的同一方法构建方法版本组,选取每个方法版本组中最早的版本作为样本方法,样本方法的集合构成历史映像,对历史映像进行克隆检测,同时建立样本方法和方法版本组间的方法索引。根据历史映像克隆检测结果及方法索引恢复原始的全量克隆关系。采用该克隆检测加速技术在251个开源项目的3 234个版本共计3亿行代码上进行克隆检测实验,与未加速相比,效率提升了近4倍。     

一种改进的静态克隆选择算法及其应用研究

建立了一个基于人工免疫原理的入侵检测系统模型，该模型融合了智能协议分析、克隆选择、人工免疫、遗传算法等多种智能技术，对其中的克隆选择算法进行了研究，对Forrest的静态克隆选择算法提出了改进方案。仿真实验表明，改进算法在性能上优于Forrest的静态克隆选择算法。     

基于图模型的克隆代码演化痕迹构建及模式识别

针对克隆跟踪不精确、演化模式识别繁琐以及克隆群合并现象处理困难等问题,提出一种改进的克隆代码演化痕迹构建及模式识别方法。在相邻版本使用主题概率模型实现克隆群初步映射,计算代码位置重叠率及文本相似度完成克隆片段映射,修复克隆群映射得到精确的相邻版本克隆映射结果。依据相邻版本间建立映射的克隆群数量关系及交叉程度识别短期演化模式,构建图模型,将克隆群作为点、映射关系作为边,并根据产生形式为克隆群标注短期演化模式。使用广度优先搜索算法提取克隆家系,按照克隆家系中包含的克隆群种类及是否有环识别长期演化模式。对5款开源软件的70个版本进行实验,结果表明,运用该方法约95%的克隆在演化中保持稳定,约1%的克隆经历了合并复合,并且80%左右克隆代码的生命周期未超过发布版本总数的一半。     

基于动态克隆选择的入侵检测模型

建立了一种基于扩展动态克隆选择的入侵检测模型，将IP抗原化与未成熟免疫细胞、成熟免疫细胞、记忆免疫细胞进行匹配，不断学习记忆，检测出各种已知或未知攻击。在动态克隆中引入变异，提高了学习效率和检测效率。     

基于类粒度的克隆代码群稳定性实证研究

克隆代码研究与软件工程中的各类问题密切相关。现有的克隆代码稳定性研究主要集中于克隆代码与非克隆代码的比较以及不同克隆代码类型之间的比较,少有研究对克隆代码的稳定性与克隆群所分布的面向对象类进行相关分析。基于面向对象类的粒度进行了克隆群稳定性实证研究,设计了4项与克隆群稳定性相关的研究问题,围绕这些研究问题,将克隆群分为类内、类间和混合3组,并基于4种视角下的9个演化模式进行了克隆群稳定性的对比分析。首先,检测软件系统所有子版本中的克隆代码,识别并标注所有克隆代码片段所属的类信息;其次,基于克隆片段映射方法完成相邻版本间克隆群的演化映射和演化模式的识别与标注,并将映射和标注结果合并为克隆代码演化谱系;然后,在不同视角下,针对3组克隆群进行稳定性计算;最后,根据实验结果对比分析了3组克隆群的稳定性差异。在7款面向对象开源软件系统总共近7700个版本上进行的克隆群稳定性实验结果表明:约60%的类内克隆群的生命周期率达到50%及以上,类间克隆和混合克隆群的生命周期率达到50%及以上的占比均约为35%;类内克隆群发生变化的次数最少,类间克隆群发生合并、分枝和延迟修复演化模式的次数相对略多,混合克隆群发生片段减少、内容一致变化和不一致变化的次数最多。总体而言,类内克隆群的稳定性表现最佳,混合克隆群在演化中可能需要重点跟踪或优先重构。克隆代码稳定性分析方法及实验结论将为克隆代码的跟踪、维护以及重构等克隆管理相关软件活动提供有力的参考和支持。     

Software clone detection: A systematic review

ContextReusing software by means of copy and paste is a frequent activity in software development. The duplicated code is known as a software clone and the activity is known as code cloning. Software clones may lead to bug propagation and serious maintenance problems.ObjectiveThis study reports an extensive systematic literature review of software clones in general and software clone detection in particular.MethodWe used the standard systematic literature review method based on a comprehensive set of 213 articles from a total of 2039 articles published in 11 leading journals and 37 premier conferences and workshops.ResultsExisting literature about software clones is classified broadly into different categories. The importance of semantic clone detection and model based clone detection led to different classifications. Empirical evaluation of clone detection tools/techniques is presented. Clone management, its benefits and cross cutting nature is reported. Number of studies pertaining to nine different types of clones is reported. Thirteen intermediate representations and 24 match detection techniques are reported.ConclusionWe call for an increased awareness of the potential benefits of software clone management, and identify the need to develop semantic and model clone detection techniques. Recommendations are given for future research.     

面向高级别代码克隆检测方法的设计与实现

代码克隆检测是软件工程中的基础研究，在软件分析和维护方面有着广泛应用。目前对于有文本差异的高级别（即学术界定义的级别3和级别4）克隆检测，现有方法存在检出率（回收率）不高的问题。基于程序依赖图PDG的检测方法是高级别克隆检测的一类重要方法，但这类方法依赖子图同构的精确图匹配算法，算法时间复杂度高且回收率较低。为此，提出了一种新的高级别代码克隆检测方法，使用基于 Weisfeiler-Lehman图核的非精确图匹配算法进行代码克隆检测。实验结果表明，与已有的代码克隆检测方法相比， 该方法可以检出更多的高级别克隆且计算时间较短。     

Tuning research tools for scalability and performance: The NiCad experience

Clone detection is a research technique for analyzing software systems for similarities, with applications in software understanding, maintenance, evolution, license enforcement and many other issues. The NiCad near-miss clone detection method has been shown to yield highly accurate results in both precision and recall. However, its naive two-step method, involving a parsing first step to identify and normalize code fragments, followed by a text line-based second step using longest common subsequence (LCS) to compare fragments, has proven difficult to migrate to the efficiency and scalability required for large scale research applications. Rather than presenting the NiCad tool itself in detail, this paper focuses on our experience in migrating NiCad from an initial rapid prototype to a practical scalable research tool. The process has increased overall performance by a factor of up to 40 and clone detection speed by a factor of over 400, while reducing memory and processor requirements to fit on a standard laptop. We apply a sequence of four different kinds of performance optimizations and analyze the effect of each optimization in detail. We believe that the lessons of our experience in migrating NiCad from research prototype to production performance may be beneficial to others who are facing a similar problem.     

Comparison and evaluation of code clone detection techniques and tools: A qualitative approach

Over the last decade many techniques and tools for software clone detection have been proposed. In this paper, we provide a qualitative comparison and evaluation of the current state-of-the-art in clone detection techniques and tools, and organize the large amount of information into a coherent conceptual framework. We begin with background concepts, a generic clone detection process and an overall taxonomy of current techniques and tools. We then classify, compare and evaluate the techniques and tools in two different dimensions. First, we classify and compare approaches based on a number of facets, each of which has a set of (possibly overlapping) attributes. Second, we qualitatively evaluate the classified techniques and tools with respect to a taxonomy of editing scenarios designed to model the creation of Type-1, Type-2, Type-3 and Type-4 clones. Finally, we provide examples of how one might use the results of this study to choose the most appropriate clone detection tool or technique in the context of a particular set of goals and constraints. The primary contributions of this paper are: (1) a schema for classifying clone detection techniques and tools and a classification of current clone detectors based on this schema, and (2) a taxonomy of editing scenarios that produce different clone types and a qualitative evaluation of current clone detectors based on this taxonomy.     

Code clones and developer behavior: results of two surveys of the clone research community

The literature presents conflicting claims regarding the effects of clones on software maintainability. For a community to progress, it is important to identify and address those areas of disagreement. Many claims, such as those related to developer behavior, either lack human-based empirical validation or are contradicted by other studies. This paper describes the results of two surveys to evaluate the level of agreement among clone researchers regarding claims that have not yet been validated through human-based empirical study. The surveys covered three key clone-related research topics: general information, developer behavior, and evolution. Survey 1 focused on high-level information about all three topics, whereas Survey 2 focused specifically on developer behavior. Approximately 20 clone researchers responded to each survey. The survey responses showed a lack of agreement on some major clone-related topics. First, the respondents disagree about the definitions of clone types, with some indicating the need for a taxonomy based upon developer intent. Second, the respondents were uncertain whether the ratio of cloned to non-cloned code affected system quality. Finally, the respondents disagree about the usefulness of various detection, analysis, evolution, and visualization tools for clone management tasks such as tracking and refactoring of clones. The overall results indicate the need for more focused, human-based empirical research regarding the effects of clones during maintenance. The paper proposes a strategy for future research regarding developer behavior and code clones in order to bridge the gap between clone research and the application of that research in clone maintenance.     

A systematic literature review on the use of machine learning in code clone research

Context:Research related to code clones includes detection of clones in software systems, analysis, visualization and management of clones. Detection of semantic clones and management of clones have attracted use of machine learning techniques in code clone related research.Objective:The aim of this study is to report the extent of machine learning usage in code clone related research areas.Method:The paper uses a systematic review method to report the use of machine learning in research related to code clones. The study considers a comprehensive set of 57 articles published in leading conferences, workshops and journals.Results:Code clone related research using machine learning techniques is classified into different categories. Machine learning and deep learning algorithms used in the code clone research are reported. The datasets, features used to train machine learning models and metrics used to evaluate machine learning algorithms are reported. The comparative results of various machine learning algorithms presented in primary studies are reported.Conclusion:The research will help to identify the status of using machine learning in different code clone related research areas. We identify the need of more empirical studies to assess the benefits of machine learning in code clone research and give recommendations for future research.