云环境下基于Java字节码的多粒度代码克隆检测方法

摘要

本发明公开了一种云环境下基于Java字节码的多粒度代码克隆检测方法。本发明通过对Java字节码指令进行分析来提取块粒度的代码，从而能够同时检测方法粒度的克隆与块粒度的克隆。在计算代码相似度时，不仅考虑指令之间的相似性同时还引入了方法调用之间的相似性，从而能够更好地检测出语义克隆。与传统的基于Java字节码的代码克隆检测方法相比，本发明能够同时检测方法粒度与块粒度的代码克隆，并且由于加入了方法调用的相似性比较，本发明的克隆检测结果更加准确。

说明书

技术领域

本发明属于软件分析中的代码克隆检测技术领域，具体涉及到云环境下一种基于Java字节码的多粒度代码克隆检测方法。

背景技术

云计算的出现为传统软件开发提供了一种新型的协同工作模式。在这种模式下，不同的软件团队和个人分布在不同地方，为共同开发同一个软件系统作出贡献。基于云环境的协同开发模式在给软件开发人员带来便利的同时也给软件的管理带来了一定的困难，特别地由于地域和团队的不同，对开发人员通过复制-粘贴或者添加少量修改来复用代码的行为缺乏有效的监管。这些重复代码(或称之为代码克隆)会严重影响软件的维护工作。通过对软件源码中的代码克隆进行检测，可以发现不必要的重复代码，从而为后续的代码重构提供支持。

现有的代码克隆检测技术主要有基于文本(Text)、基于Token、基于抽象语法树(AST)、基于程序依赖图(PDG)和基于度量值几类。基于Text的方法不需要对源代码进行转换，其准确率较高但是召回率底；基于Token的方法检测速度较快并且不依赖于开发语言，但是却很难检测Type-3类代码克隆；基于AST和基于PDG的方法需要把源代码转换成AST或者PDG然后再进行相应的比较，这两种方法所花费的代价都比较大；由于不同的代码段对应的度量值可能会相同，所以基于度量值的方法误报率较高。

发明内容

本发明针对现有技术的不足，提供了一种云环境下基于Java字节码的多粒度代码克隆检测方法。

本发明方法的具体步骤是：

步骤(1)获取云环境下分布于不同地点的Java源代码，编译得到它们的字节码文件即.class文件，并通过javap命令将.class文件转换为txt格式文件；每个txt格式文件包含一个或多个Java方法，每个方法都由一系列字节码指令以及相关的方法调用构成；

步骤(2)提取步骤(1)中所得到的txt格式文件中的方法与代码块，其中，通过直接读取每个方法所对应的字节码指令提取方法；代码块的提取则需要对一些控制转移指令进行分析，如goto、switch、以及if相关的字节码指令；

步骤(3)根据Java字节码指令的分类构建字节码指令的分类层次架构并进行编码，该架构主要分为三层：第一层是Java字节码指令中除Type之外的其余九个大类，第二层是对每个大类进行的详细子类划分，第三层则是对应的字节码指令；

步骤(4)对步骤(2)所提取出的两种粒度(方法粒度、代码块粒度)的代码段(方法或代码块)进行特征提取，主要提取的特征包括指令序列IS＝(I₁,I₂,I₃,...,I_i,...,I_k)与方法调用序列MCS＝{M₁,M₂,M₃,...M_i,...,M_r}，其中k、r为自然数。

在特征提取之后使用字节码指令的分类层次架构对指令序列进行归一化处理，将指令序列转化为一级指令序列与二级指令序列，其中一级指令序列对应分类层次架构中的第一层Java字节码指令大类，二级指令序列对应分类层次架构中的第二层Java字节码指令子类；

步骤(5)对于两个代码段(方法或代码块)，利用步骤(4)中得到的指令序列与方法调用序列，分别进行Type-1、Type-2克隆检测与Type-3克隆检测。

在Type-1、Type-2克隆检测中，首先计算两个代码段的二级指令序列的哈希值，如果哈希值相等，再比较两个代码段的方法调用序列，如果方法调用序列中的方法个数相同并且每个方法的参数个数也相同，则这两个代码段为代码克隆实例。

在Type-3克隆检测中，计算两个代码段的一级指令序列相似度、二级指令序列相似度与方法调用序列相似度，然后对一级指令序列相似度、二级指令序列相似度与方法调用序列相似度进行加权来确定最终的代码段相似度值，如果相似度值超过预先设定的阈值，则它们为代码克隆实例；其中，使用编辑距离计算一级指令序列相似度、二级指令序列相似度；在计算两个方法调用序列相似度时，采用递归的方式将两个方法调用序列的相似度计算转换成这两个方法调用序列中每个方法所对应的代码段的相似度的计算；

本发明所提供的云环境下基于Java字节码的多粒度的代码克隆检测方法由一组功能模块组成，它们包括：预处理模块、特征提取模块以及代码克隆检测模块。

预处理模块首先对云环境中分布于不同地点的Java源代码进行编译，将其转换为.class文件，进而转换为txt格式的字节码文件。随后在字节码文件的基础上进行方法粒度与块粒度的代码段提取。

特征提取模块用于提取代码段中指令序列与方法调用序列，并将提取出的指令序列进行归一化处理。

代码克隆检测模块对Type-1、Type-2克隆与Type-3克隆采用不同的方法进行检测。Type-1、Type-2克隆检测主要通过比较指令序列所对应的哈希值以及每个方法调用的参数个数来判断，Type-3克隆检测则主要通过比较指令序列的相似性与方法调用序列的相似性来判断。

本方明提出的云环境下基于Java字节码的多粒度代码克隆方法，通过对Java字节码指令进行分析来提取块粒度的代码，从而能够同时检测方法粒度的克隆与块粒度的克隆。在计算代码相似度时，不仅考虑指令之间的相似性同时还引入了方法调用之间的相似性，从而能够更好地检测出语义克隆。与传统的基于Java字节码的代码克隆检测方法相比，本发明能够同时检测方法粒度与块粒度的代码克隆，并且由于加入了方法调用的相似性比较，本发明的克隆检测结果更加准确。

附图说明

图1本发明的整体流程图；

图2代码块提取实例图；

图3为字节码分类层次架构图；

图4为特征提取图；

图5为克隆检测流程图。

具体实施方式

本发明所提供的云环境下基于Java字节码的多粒度代码克隆检测方法的具体实施方式主要分3步(如图1所示)：

1)预处理

预处理阶段主要包含以下两个步骤：

(1)源代码编译

首先将云环境下分布于不同地点的Java源代码编译为.class文件，并将.class文件转换为txt格式的Java字节码文件，作为下一步克隆检测的输入。每个Java字节码文件包含一个或多个方法，每个方法都由一系列指令以及相关的方法调用构成。由于Java编译时会自动处理空行和注释，同时也去除了变量重命名的影响，所以无需对空行和注释以及变量名进行预处理。

(2)方法提取与代码块提取

由于Java字节码文件将每个Java方法单独解析为一段字节码指令，所以提取方法粒度的代码段时直接读取每个方法所对应的字节码指令，而提取块粒度的代码段时需要对Java字节码的控制转移指令进行分析。具体的分析方法为(以图2为例)：

a)读取代码段所对应的字节码指令，如果遇到goto指令则读取该指令的当前编号与跳转编号，然后将当前编号的下一编号与跳转编号之间的指令加入gotoSet中。

b)如果遇到if指令，若当前编号大于跳转编号，则将gotoSet中当前编号与其跳转编号相同的指令移除，并将当前标号与跳转编号的上一编号之间的指令加入到ifReverseSet中，否则加入ifSet。

c)如果在读取字节码指令时遇到switch的分支指令(tableswitch、lookupswitch)，将对应的跳转指令编号提取出来并添加到numArr中，然后对numArr中的编号从小到大进行遍历，提取编号所对应的字节码指令。在提取块的过程中如果包含switch则递归调用步骤c)。

2)特征提取

(1)为了在字节码的基础上检测代码克隆，需要对字节码提取相应的特征。本发明所提取的特征主要是指令序列IS和方法调用序列MCS(如图3所示)。其中指令序列代表了源代码的执行流程，而方法调用序列则代表了源代码中的方法调用情况。在提取方法调用序列时，保存了每个方法的参数调用个数，用以在克隆检测阶段使用。

(2)根据字节码指令的分类层次架构(如图4所示)，可以对字节码指令序列进行归一化处理，本发明将归一化的结果分为两个序列：NIS1与NIS2。其中NIS1是字节码指令序列第一层的归一化结果(称为一级指令序列)，NIS2是字节码指令序列第二层归一化的结果(称为二级指令序列)。例如，给定一个字节码指令序列(aload_0,new,dup,ldc_w,invokespecial,aload_1,invokevirtual,ldc_w,invokevirtual,invokevirtual,iconst_4,invokevirtual)，其第一层的归一化序列(一级指令序列)为：ADEAGAGDGGAG,第二层的归一化序列(二级指令序列)为：A1D1E2A3G3A1G1D2G1G1A3G1。

3)代码克隆检测

代码克隆检测过程中将Type-3克隆检测与Type-1、Type-2的克隆检测分开以提高代码克隆检测的效率(如图5所示)。

在Type-1和Type-2克隆检测阶段，首先判断两个代码段的二级指令序列是否相同，如果相同则比较方法调用序列中每个方法以及该方法的参数个数是否相同，如果都相同则可以判定为Type-1和Type-2克隆。在二级指令序列比较阶段，为了加快比较速度，同时结合Type-1、Type-2克隆的特征，对每个代码段的二级指令序列计算一个哈希值，如果两个二级指令序列的哈希值相同，则进一步比较方法调用序列中每个方法以及该方法的参数个数。因为Type-1和Type2克隆的方法调用的参数是一样的，所以在进行方法调用序列的比较时，考虑了参数调用个数的一致性。这里用到的哈希算法为Java自带的哈希方法。

在Type-3克隆检测阶段，分别对指令序列与方法调用序列进行相似度比较，然后对指令调用序列相似度与方法调用序列的相似度进行综合来确定最终的相似度值。如果总的相似度值大于最小相似度阈值，则对应的两个代码段为代码克隆。在指令相似度计算时，使用编辑距离来计算指令之间的相似度，这里的相似度是NIS1与NIS2的相似度加权累计值。在方法调用序列的相似度计算时，采用递归的方式将两个方法调用序列的相似度计算转换成这两个方法调用序列中每个方法所对应的代码段的相似度的计算。

本发明可用于云环境下Java软件系统的代码克隆检测，从而帮助软件开发人员更好地对软件系统进行维护和管理。