收录于话题 现有的克隆代码检测工作中基于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个样本,将有