代码克隆检测是软工领域的重要研究方向,难以兼顾高效性和准确性是其亟需解决的痛点问题。基于文本或令牌的克隆检测是一种高效的检测方式,但由于缺失对代码语义的考虑而无法保证准确性;基于程序依赖图的方式则由于需要代码编译而导致可用性低,即不具备高效性且无法适用于任意粒度的代码片段;基于抽象语法树的方式虽然可以达到较高的准确率,却因为树匹配的高复杂度问题需要过多的时间开销。为此,论文提出了一种高效且准确的代码克隆检测方式。该方法将复杂的抽象语法树转换成了一种简单的图表示,并采用中心性算法将该图转化为一个具有图结构信息的定长向量,然后基于该定长向量进行克隆检测器的训练和测试。实验结果表明,文中提出的克隆检测方法在两个标准数据集上能够分别达到0.99和0.95的准确率,均高于其他方法。在时间开销方面,该方法比目前同类方法的检测速度提高79倍。
该成果“TreeCen: Building Tree Graph for Scalable Semantic Code Clone Detection”发表在国际会议IEEE/ACM International Conference on Automated Software Engineering(ASE 2022)。ASE与ICSE、ISSTA和FSE并称为软件工程领域的四大顶级会议,在软件工程领域具有举足轻重的地位。ASE 2022共接收论文投稿531篇,其中直接录用的仅有78篇。会议于2022年10月10日至2022年10月14日在美国密歇根州奥克兰中心举办。
论文链接:https://doi.org/10.1145/3551349.3556927
代码链接:https://github.com/CGCL-codes/TreeCen
背景与动机
代码克隆检测是软件工程的一个重要研究领域,克隆代码是指与另一个代码片段相同或相似的代码片段。通常,克隆根据代码相似程度分为四种类型(即,Type 1-4克隆)。前三种克隆类型(Type 1-3克隆)是具有语法相似性的代码对,因为其文本高度相似,因此很容易被检测;最后一种克隆类型(Type-4克隆)是指一对代码在代码语义上具有相似性,对Type-4的克隆检测是一个复杂的研究问题。
目前许多检测代码克隆的方法被相继提出,根据检测效果可分为两类:大规模克隆检测和语义克隆检测。大规模克隆检测的主要方法基于文本和基于令牌实现,其直接将代码片段转换为文本或令牌序列,然后对其进行相似性比较。虽然这些方法仅需较短的执行时间,但由于缺乏对代码语义的考虑,无法应用于语义克隆检测。为了有效地检测语义克隆,研究人员提出了基于代码中间表示的检测方法,并证明了基于图和基于树的检测方法可以有效检测语义克隆,但现有的方法不适用于大规模的克隆检测。其中,对于基于图的方法,程序依赖图(Program Dependency Graphs,PDGs)和控制流图(Control Flow Graphs,CFGs)都具有复杂的结构,因此在进行图相似性比较时的开销很大。此外,生成精确的代码图表征需要事先编译代码,这会导致对某些代码片段(例如,单个函数、代码片段)的检测能力受限。因此,为了减少代码编译带来的影响,一些研究人员提出了基于抽象语法树(ASTs)的克隆检测方法。然而,现有的基于树的方法的主要缺陷在于树的结构非常复杂,导致树的相似性比较开销很大。为此,本文提出了一种基于抽象语法树的大规模语义代码克隆检测器,旨在减少基于树的方法的运行开销。
设计与实现
本文面临一个主要挑战:如何将复杂的树转换为一种更简单的表示形式,同时能够保留树的结构信息?为了解决该问题,我们发现中心性分析方法被广泛应用于社交网络分析领域,用来评价网络中节点的重要性。而其他领域的研究人员也证实中心性分析可以有效地揭示图或网络的结构。对于代码分析,AST作为通用和基本的代码中间表示,能够反映代码的语法和语义信息。与PDG或CFG相比,AST可以在不编译的情况下获取,因此基于AST的方法在代码克隆检测中的可扩展性更高。然而,目前还没有研究证明中心性分析方法能否有效地揭示树的结构特征,所以中心性分析只能用于图的分析,不能直接适用于树的分析。
为此,本文对以下问题进行了初步研究:1)AST能否转换成更简单的图表示?2)中心性分析能否有效地反映AST的结构信息,从而表现出克隆代码对的高相似度和非克隆代码对的低相似度?
图1 基于不同中心性分析方法的代码对余弦相似度分布
为了解决以上问题,本文对BigCloneBench(BCB)数据集中的克隆和非克隆代码对进行了初步研究。给定一个代码片段,本文首先对其进行静态分析以提取AST。为了将AST简化为图表示,本文将AST中的每个节点类型设置为图的一个节点,然后根据AST中的边关系为图分配边和边权重。得到图后,本文选择四种常用的中心性分析方法(即,特征向量中心性、接近中心性、中介中心性和度中心性)生成中心性向量。最后,本文计算这些中心性向量的余弦相似度,从而检验中心性分析是否能够显示克隆代码对与非克隆代码对之间的内在差异。其中,代码对越相似,余弦相似度越收敛于1。反之,代码对的差异越大,余弦相似度越收敛于0。从图1中的箱线图中可以看到,克隆代码和非克隆代码之间存在显著差异,克隆代码对(橙色)的分布显然比非克隆代码对(蓝色)更接近于1。因此,测试结果可以回答上述两个问题:AST可以简化为图形表示;中心性分析方法可以表现出克隆与非克隆代码对的相似度之间存在的显著差异。受到上述启发,本文提出了一种新的方法,将复杂的AST转换为图(即树形图),并对树形图进行中心性分析后获得更简短的代码表征向量,并将其用于可扩展的代码克隆检测。
本文首先基提取源代码的AST。AST是一个树结构,由令牌节点、类型节点和边组成。具体来说,令牌节点是AST(图2中的双层矩形)的叶子节点,其中包含节点类型和相应的代码。其他节点是类型节点(图2中的单层矩形),表示该节点的类型(例如,ReturnStatement, Literal)。AST的语法和语义信息主要从这些节点类型和边中获得。
本文将AST的节点类型和边关系压缩为更紧密的数据结构,这有助于为大规模克隆检测保留全面的代码信息。根据统计,AST有57种类型节点和15种令牌节点,共72种节点类型。基于以上观察,本文设计了一种表示AST抽象的无向图,称为树图。我们将AST中的每个节点类型都视为树图中的一个节点,AST中的父-子节点关系视为树图中父类型和子节点类型之间的边。此外,树图中边的权重取决于AST中相应节点类型之间边的出现次数。简而言之,本文将AST简化为最多包含72个节点的图表示(即,树图)。因此,TreeCen可以在树图的帮助下进行大规模的代码克隆检测。
图2 具体实例
针对上一阶段生成的树图,我们对其节点进行中心性特征提取。即,将树图转换成反映代码语义和语法的特征向量表示。以度中心性分析方法举例,给定树图,本文依次计算72种节点中的每一种的中心度。例如,在图2中,树图有72个度,其中,6个来自Identifier节点(橙色圆形),8个连接到MemberReference(浅红色圆形),4个用于MethodInvocation(浅蓝色圆形)。因此,Identifier的度数为6。根据Degree Centrality公式,Identifier节点的度中心性可计算为0.08。此外,如果没有该类型的节点,则将该向量的对应位置设为零。因此,在对AST进行特征提取后,即可得到72维中心性向量。
最后是克隆检测阶段,用于识别代码对为克隆或非克隆。本文选择了五种候选机器学习算法,分别为1-近邻算法(1-NN)、3-近邻算法(3-NN)、决策树(DT)、随机森林(RF)和逻辑回归(LR)。首先,本文如下式所示,将代码对的两个中心性向量V1和V2拼接得到向量表示V。然后根据其是克隆对或非克隆对标注或检测该代码对的向量V。
V=V1⊕V2
发现与讨论
在检测有效性方面,本文首先在Google Code Jam (GCJ)数据集上与最先进的克隆检测器进行对比实验(GCJ数据集中的所有克隆对都可以被认为是Type-4克隆)。因此,在该数据集上进行实验可以有效证明TreeCen在语义克隆检测方面的有效性(结果如表1所示)。表2展示了针对BCB数据集的检测结果,可以看出TreeCen的性能明显优于其他克隆检测器,其Precision和Recall都在0.99以上。
表1 针对Google Code Jam数据集的实验结果
表2 针对BigCloneBench数据集的实验结果
在时间开销方面,TreeCen也取得了优异的性能,如表3所示。具体来说,TreeCen检测100万个代码对需要239.2秒,比另一种基于树的语义代码克隆检测器ASTNN至少快79倍,比最快的基于图的方法SCDetector快13倍左右,甚至比一次性训练的基于token的检测器RtvNN快22倍左右。以上结果表明,TreeCen适合于大规模代码克隆检测。综合实验和分析结果表明,TreeCen能够有效地检测语义克隆,并实现大规模克隆检测。
表3 时间开销测试结果
详细内容请参见:
Yutao Hu, Deqing Zou, Junru Peng, Yueming Wu, Junjie Shan, and Hai Jin. TreeCen: Building Tree Graph for Scalable Semantic Code Clone Detection. In Proceedings of the 37th IEEE/ACM International Conference on Automated Software Engineering (ASE’22), ACM, 2022: 1-12.
https://doi.org/10.1145/3551349.3556927