← 返回列表

基于语义token分析的克隆代码检测系统

聚合站 SecWiki技术 作者 穿过丛林 发布 2021年1月4日 09:55 入库 2026-11-18T21:17:59

现有的克隆代码检测工作中基于token的方法效率最高,可以扫描检测以亿为单位的代码量。然而,由于这些方法没有考虑程序的语义信息,导致其精确度并不理想,不能检测语义克隆。为了可以检测语义克隆,研究者将程序语义用图进行刻画,并利用图匹配来检测语义克隆。但是,图匹配本身是个高开销的工作,使得这些基于图的方法可扩展性很低。为了解决这些挑战,我们提出了一个基于语义token分析的系统,以将基于token方法的高效率和基于图方法的高精度进行结合,实现高效率、高精度的语义克隆代码检测。

该成果“SCDetector: Software Functional Clone Detection Based on Semantic Tokens Analysis”发表于IEEE/ACM International Conference on Automated Software Engineering 2020。IEEE/ACM International Conference on Automated Software Engineering 是软件工程领域顶级会议,是CCF A类会议。

论文链接:https://conf.researchr.org/details/ase-2020/ase-2020-papers/28/SCDetector-Software-Functional-Clone-Detection-Based-on-Semantic-Tokens-Analysis

论文下载:http://youngwei.com/pdf/SCDetector.pdf

背景与动机

代码克隆检测旨在挖掘具有相似功能的代码片段,这在软件工程中引起了广泛的关注。一般情况下,代码克隆类型根据句法或语义级别的差异分为四类。前三种类型的克隆属于句法克隆,而最后一种类型的克隆属于语义克隆。对于句法相似性,通常发生在程序员进行代码复制和粘贴时,而当开发人员从头开始实现某些功能相似的代码时,就会引入语义克隆代码。现有的克隆代码检测工作中基于token的方法效率最高,它们适用于大规模的克隆代码扫描,然而,为了实现快速扫描,这些工作没有考虑程序的语义信息,导致不能检测语义克隆。为了可以检测语义克隆,研究者将程序语义用图进行展示,并利用图匹配来检测语义克隆。但是,当遇到复杂图的时候,图计算会产生很高的开销,使得不能扩展至大规模的克隆检测。为了解决这些问题,我们提出了一个基于语义token分析的系统(SCDetector),以将基于token方法的高效率和基于图方法的高精度进行结合,实现高效率、高精度的语义克隆代码检测。

设计与实现

如图1所示,SCDetector主要分为3个阶段:1)静态分析,输入是一个函数的源代码,输出是函数代码的控制流程图(CFG);2)中心性分析,输入是控制流程图,输出是带有中心性的“语义token”;3)克隆检测,输入是一对待检测函数代码,输出是它们是一个克隆对的概率。如果概率大于0.5,我们则认为这两个函数是一个克隆对。

图1 SCDetector系统框架图

在静态分析阶段,由于实验数据集的编程语言是Java,因此我们采用Java优化框架Soot来实现我们的静态分析,该框架已被许多论文使用。实际上,静态分析的目的是将函数代码转换为图表征。它并不局限于编程语言,因为不同的编程语言具有相应的静态分析工具来对其进行分析。例如,我们利用Soot获得Java函数代码的CFG,而其他人可以使用Joern提取C函数代码的CFG。

在中心性分析阶段, 给定函数代码的CFG,我们首先提取CFG中所有基本块的度中心性。一个基本块由多个token组成,这些token可以通过词法分析获得。例如,基本块“if b = 0 goto label0”由6个token组成,分别是if,b,=,0,goto和label0。经过度中心性分析后,我们将相应的中心性分配给基本块中的所有token,并计算不同基本块中同一token的总中心性。为了更好地描述主要步骤,我们在图2中给出一个详细的示例。如图2所示,两个基本块“return a”和“return temp $ 1”的度中心性均为0.11。以此我们可以计算出token“return”的总度中心性为0.11 + 0.11 = 0.22。经过中心性分析后,我们可以获得CFG中所有token相应的总度中心性(权重)。我们将这些权重token称为“语义token”。

图2 语义token的生成步骤

在克隆代码检测阶段,我们使用孪生网络作为我们的检测网络。孪生网络是一类神经网络体系结构,其中包含两个相同的子网络,它们具有相同的配置,并且共享参数和权重。孪生网络已广泛应用于许多领域,例如复述评分,其中输入是两个句子,输出是它们相似程度的分数。使用孪生神经网络的一个重要特征是可以通过使用成对的输入而不是单个输入来扩大数据集。给定一个类别的n个样本,将有𝑛∗(𝑛− 1)/ 2个positive对和许多negative对。孪生网络的另一个优点是,与具有相同层数的普通神经网络相比,跨子网共享权重使其需要更少的参数进行训练。

图3 克隆检测的具体步骤

图3展示了SCDetector中使用的孪生神经网络。两个相同的子网络是共享权重的两个GRU神经网络。GRU网络的输入是通过中心性分析获得的语义tokens。我们首先使用word2vec训练token的embedding,以将token转换为固定长度的向量,维度我们设置为100。在乘以相应的总中心性(权重)后,我们将语义向量输入两个相同的GRU子网络中。最后,一个比较器网络将这两个子网络的输出作为输入来计算距离。在本文中,我们采用余弦距离作为我们的距离度量,比较器网络的输出是两个输入函数代码是一个克隆对的概率。如果概率大于0.5,我们则认为这两个函数是一个克隆对。

为了验证SCDetector在检测克隆代码上的有效性,我们在两个数据集上进行了实验测试,包括GoogleCodeJam和BigClonebench。GoogleCodeJam中的程序是从Google举办的在线编程比赛中收集的,一共包含来自12个不同比赛问题的1,669个回答(一个回答对应一个函数)。其中,解决相同比赛问题的回答在语义上相似,而针对不同问题的回答则不同。而且,在比赛问题中,很少有回答在句法上相似。因此,我们可以假定同一问题的回答中代码克隆对最有可能是语义克隆。我们实验中使用的第二个数据集是BigCloneBench数据集,它由来自25,000个项目的超过六百万个带标签的克隆对组成。BigCloneBench中的克隆对的代码粒度也是函数级别的,并且每个克隆对都被手动分配了相应的克隆类型。

在实验过程中,我们一共选择了4个对比工具:SourcererCC (ICSE’16),、Deckard (ICSE’07)、RtvNN (ASE’16)和ASTNN (ICSE’19)。实验结果如表1所示,从表1可以看到,SCDetector的检测效果比其他几个工具都要更好。由于ASTNN在处理GoogleJam数据集时会报错,所以我们只和ASTNN在BigClonebench数据集上做了对比实验。

另一方面,为了测试SCDetector在克隆检测上的开销,我们从我们的数据集中随机选择了100万对函数对,然后针对这些数据进行详细的开销统计,统计结果如图4所示。从图4可以看到,SCDetector在检测代码克隆时速度比基于token的方法要慢,但是较RtvNN和ASTNN都要快很多。

图4 克隆检测的开销对比

原文链接:https://mp.weixin.qq.com/s/e_NvzMbOqDspns3VLXBjYw