基于字符串的代码克隆检测方法的分析

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

代码克隆检测研究进展

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

克隆代码分析方法研究

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

软件源代码中的代码克隆现象及其检测方法

如果软件源程序中的一个代码段和同一程序中的另一个代码段在结构或语义上类似,这些代码段就成了代码克隆.概述代码克隆存在的各种形式,分析代码克隆产生的原因,并在概括了代码克隆检测的一般过程以后进一步阐述两类代码克隆检测方法:基于语义抽象树的检测方法和基于Token序列的检测方法.     

一种基于特征矩阵的软件脆弱性代码克隆检测方法

提出了一种基于特征矩阵的软件代码克隆检测方法.在此基础上,实现了针对多类脆弱性的检测模型.基于对脆弱代码的语法和语义特征分析,从语法分析树抽取特定的关键节点类型描述不同的脆弱性类型,将4种基本克隆类型细化拓展到更多类,通过遍历代码片段对应的语法分析树中关键节点的数量,构造对应的特征矩阵.从公开漏洞数据库中抽取部分实例作为基本知识库,通过对代码进行基于多种克隆类型的聚类计算,达到了从被测软件代码中检测脆弱代码的目的.与基于单一特征向量的检测方法相比,对脆弱性特征的描述更加精确,更具有针对性,并且弥补了形式化检测方法在脆弱性类型覆盖能力上的不足.在对android-kernel代码的测试中发现了9个脆弱性.对不同规模软件代码的测试结果表明,该方法的时间开销和被测代码规模成线性关系.     

基于Token语义构建的代码克隆检测

传统的基于Token的克隆检测方法利用代码字符串的序列化特性,可以在大型代码仓中快速检测克隆.但是与基于抽象语法树(AST)、程序依赖图(PDG)的方法相比,由于缺少语法及语义信息,针对文本有较大差异的克隆代码检测困难.为此,提出一种赋予语义信息的Token克隆检测方法.首先,分析抽象语法树,使用AST路径抽象位于叶子节点的Token的语义信息;然后,在函数名和类型名角色的Token上建立低成本索引,达到快速并有效地筛选候选克隆片段的目的.最后,使用赋予语义信息的Token判定代码块之间的相似性.在公开的大规模数据集BigCloneBench实验结果表明,该方法在文本相似度较低的Moderately Type-3和Weakly Type-3/Type-4类型克隆上显著优于主流方法,包括NiCad、Deckard、CCAligner等,同时在大型代码仓上需要更少的检测时间.     

基于分组的代码克隆增量检测方法

代码克隆是指软件程序中一组相同或相近的代码片段,它广泛存在于软件中,因此如何发现代码克隆成为软件维护的一个重要问题。目前已有的克隆检测工具大多针对单一版本进行完整的克隆检测,然而对于大规模、复杂软件系统而言,在软件演化过程中随着代码的改变,不断重新检测代码克隆将花费较高的代价。针对这一问题,提出了一种基于分组的增量克隆检测方法。该方法根据前后两个版本的差异将源代码分为发生变化和未发生变化的两组,通过组内和组间的克隆分析实现增量的克隆检测。基于所提出的方法,在克隆检测工具CCFinderX的基础上实现了一个名为ICDBG（incremental clone detector based on grouping）的原型工具。实验证明,在变更较小时,该方法能够在保证正确性的同时显著减少克隆检测时间。     

基于代码克隆检测的代码来源分析方法

随着软件生态系统和开源社区的发展,代码常在多个软件系统中复制、传播和演化,给软件系统带来了软件质量的不确定性和风险,因此,高效地查找软件系统代码可能的来源是当前研究的热点之一。提出一种基于代码克隆检测的代码来源分析方法,将目标软件代码以方法为单位切割为代码片段,转换为词袋后,在大规模代码资源库中进行并行化代码克隆检测,从而实现方法粒度的代码来源分析。基于该方法,设计并实现了一个代码来源分析工具。该工具能自动分析被测软件项目代码与代码资源库中多个项目以及版本之间的可能来源。实验结果表明,该系统能够有效地找出目标项目在大规模代码库中的代码来源信息,辅助软件维护人员理解和维护代码。     

基于代码克隆检测的操作系统脆弱性分析方法

基于代码克隆检测技术进行软件脆弱性检测,是软件脆弱性静态分析中的一个重要方向.目前,已有软件脆弱性检测工具在面向大规模代码集的脆弱性检测方面存在不足,且缺乏针对操作系统脆弱性的优化.为此,基于代码克隆检测技术,提出了一种操作系统脆弱性检测方法.首先在一般的"代码表征—提取特征—特征比对"检测流程的基础上,加入了基于操作系统软件包类型和函数代码规模的预筛选机制,在进行代码表征之前排除大部分无关代码.其次选择函数基本信息、符号序列和控制流路径三个角度提取代码特征,逐级比较脆弱代码和待测代码的相似度.最后从公开脆弱性数据库获取脆弱样本,对典型开源操作系统进行了实验,结果显示预筛选能够有效缩减实验对象的代码规模,而检测结果的平均精确度达到了84％.     

基于序列聚类的相似代码检测算法

为了提高源程序代码之间相似性的检测效率,提出一种基于序列聚类的相似代码检测算法.算法首先把源代码按照其自身的结构进行分段提取,然后对各个分段进行部分代码变换,再以带权重的编辑距离为相似度量标准对这些符号进行序列聚类,得到相似的程序代码片段,以达到对源程序进行相似功能检测的目的.使用多个真实和仿真程序对上述算法进行了实验,实验结果验证了算法的有效性和可伸缩性.     

大规模代码克隆的检测方法

代码克隆检测在剽窃检测、版权侵犯调查、软件演化分析、代码压缩、错误检测,以及寻找bug,发现复用模式等方面有重要作用。现有的代码克隆检测工具算法复杂,或需要消耗大量的计算资源,不适用于规模巨大的代码数据。为了能够在大规模的数据上检测代码克隆,提出了一种新的代码克隆检测算法。该算法结合数据消重中的基于内容可变长度分块（content-defined chunking,CDC）思想和网页查重中的Simhash算法思想,采用了对代码先分块处理再模糊匹配的方法。在一个包含多种开源项目,超过5亿个代码文件,共约10 TB代码内容的数据源上,实现了该算法。通过实验,比较了不同分块长度对代码克隆检测率和所需要时间的影响,验证了新算法可以运用于大规模代码克隆检测,并且能够检测出一些级别3的克隆代码,达到了较高的准确率。     

软件克隆检测技术研究

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

IBFET: Index-based features extraction technique for scalable code clone detection at file level granularity

Many techniques have been developed over the years to detect code clones in different software systems to maintain security measures. These techniques often require the source code to compare the subject system against a very large data set of big code. This paper presents index-based features extraction technique (IBFET) to detect code clones at a very large-scale level to billions of LOC at file level granularity. We performed preprocessing, indexing, and clone detection for more than 324 billion of LOC using a Hadoop distributed environment, which is quite faster and more efficient as compared to existing distributed indexing and clone detection techniques; meanwhile, it detects all three types of clones efficiently. The MapReduce rule of divide and conquer is used for a count and retrieve the similar features between different systems. We evaluated the execution time, scalability, precision, and recall of IBFET by using a well-known clone detection data set IJaDataset and BigCloneBench; furthermore, we compared the results with other state-of-the-art tools. Our approach is faster, flexible, scalable, and provides accurate results with high authenticity and can be implemented at a large-scale level.     

基于Token编辑距离检测克隆代码

针对当前Type-3克隆代码检测工具较少、效率偏低等问题,提出了一种基于Token的能有效检测Type-3克隆代码的检测方法。该方法同时能有效检测Type-1和Type-2克隆代码。首先将源代码Token化得到特定代码粒度的Token串,其次将所有Token串的定长子串进行映射,在对映射信息进行查询的基础上,利用编辑距离算法确定克隆对,然后通过并查集算法快速构建克隆群,最终反馈克隆代码信息。实现了原型工具FClones,利用基于代码突变的框架对工具进行了评价,并与领域内较优秀的两款工具NiCad及SimCad进行了对比。实验结果表明,FClones在检测三类克隆代码时查全率均不低于95%,查准率均不低于98%,能更好地检测Type-3克隆代码。     

基于图像相似度检测代码克隆

目前在代码克隆检测领域，学者们主要从文本、词汇、语法和语义四种角度展开研究，然而长期以来代码克隆检测效果并未取得新的突破。针对这一问题，从图像处理角度提出了一种基于图像相似度的新型代码克隆检测（CCIS）方法。首先对源代码进行移除注释、空白符等操作，以获取"干净"的函数片段，并将函数中的标识符、关键字等进行高亮处理；然后将处理好的源代码转换为图像，并对图像进行规范化处理；最后使用Jaccard距离和感知哈希算法进行检测，得到代码克隆信息。为了验证实验的有效性，使用6款开源软件构建评价数据集进行测试。实验结果表明，CCIS方法能够检测出100%的类型一代码克隆、88%的类型二代码克隆与60%的类型三代码克隆，因此CCIS方法可以很好地进行代码克隆检测。     

克隆代码技术研究综述

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