基于LSH的代码相似度检测研究

陈秀芳 岳江宁 渠艳琪 蔡旺 王旭

摘要：代码相似度检测研究是软件工程领域许多很重要的任务的基础操作，而现有的代码相似度检测方法普遍存在着纬度高、计算复杂和执行成本高的问题。为了解决这些问题，本文提出了局部敏感哈希（Locality Sensitive Hash，LSH）算法：它能够对大量数据进行最近邻快速查找，挖掘出相似的数据，从而实现代码相似度的检测研究。实验结果表明：LSH算法可以对海量数据进行处理，对与代码相似度的检测检测有很大的好处，本文还将LSH算法与其他检测方法进行了比较，实验结果表明LSH算法优于Word2vec检测方法。

关键词：代码相似度;局部敏感哈希;代码分类;代码检测

1简介

代码相似性检测是用来衡量两个代码片段之间的相似程度。度量代码相似性是许多软件工程任务的前端基础。研究代码相似性能够提升代码质量，这对许多软件工程的开发有很大的研究价值。

现存的代码相似性检测方法可以分成三类：属性计数方法、结构度量技术和深度学习技术。属性计数方法的基本原理是统计源程序中的某些属性计数作为相似性判断的依据。如：Grier[1]等人分别使用了20和24种统计特征来检测代码的相似性。结构度量技术主要是对源程序进行结构分析以及执行程序流程。具有代表性的研究有：北京邮电大学[2]采用了基于XML方法对结构度量技术进行相似度计算。深度学习技术是学习样本数据的内在规律和表示层次。如：White[3]等人提出的基于深度学习技术的代码相似性检测方法。这三种技术既有优点也有缺点：属性技术方法语法结构容易被人所理解，实现简单，但是精确率比较差;结构度量技术对于语法相似性检测有较好效果但是忽略了语义层面的信息;深度学习技术方法性能很好但是需要很大的数据集，并且受數据集、参数的好坏影响，具有不稳定性和不可解释性。

针对上面提出的问题以及现有的方法，我们提出使用LSH算法去更好的解决问题，LSH能够将海量数据进行清洗与降维用于解决海量数据与高维空间的困难，将K最近邻（K-NearestNeighbor，KNN）分类算法的时间复杂度缩减到亚线性。实验结果表明：LSH算法通过降维和过滤操作极大地缩短了查询计算时间，提高了效率。

2相关工作

2.1代码相似度检测方法

在现有技术中，SourcererCC[4]是基于token的代码克隆检测器， 它可以在不同的粒度级别和不同语言上进行检测。但它只考虑代码片段在词汇层次上的相似性，忽略了语法信息。Word2vec[5]是一个将单词转换成词向量的工具，它的模型以大规模语料库作为输入，通过模型的训练后映射到一个几百维度的向量空间中。这些都是现存的在代码相似性方面做的较好的方法，其余不再介绍。在代码相似度研究领域，LSH算法一开始是用来做引擎的，现在我们将它用做代码相似度的检测。在使用LSH算法之前，首先要对源程序进行代码表征，现有的代码表征的方法主要有：基于文本、基于Token、基于AST树和基于图的表征代码发方法。具体方法可自行查询。

3基于LSH的代码相似度检测模型

为了能够对较大数据集进行代码相似度的检测，本文提出了基于LSH算法的模型。如图3-1所示，该模型主要由数据预处理、数据特征向量化和LSH算法三部分组成。

在此过程中需要将读取的数据进行初步处理，具体步骤如下：第一步数据抽取：对指定文件中的代码进行读取，从中提取出数据的实体和关系，经过关联和聚合之后采用统一定义的结构来存储这些数据。第二步数据清理：通过填写缺失值，光滑噪声数据，识别或删除离群点，并解决不一致性“清理”数据。本文采用了nltk（Natural Language Toolkit）自然语言处理工具库中的word_tokenize进行分词。

本文为了进行词集的向量化表现采用了one-hot的词袋模型，将进行分词之后获取到的词典数据集进行特征词提取，生成一个词典。用该词在代码中出现的次数去表示所出现的频率，分别为1或0。如上过程在数据特征向量化模型中得到每篇代码的词向量之后，就可以送入到LSH模型中进行下一步计算。

3.1 LSH算法

将提取出的特征向量进行局部敏感哈希处理，使得在一个大的原始数据集合内查找相似特征向量的问题转化为在一个小集合内查找相似特征向量的问题，极大降低了时间复杂度。

定义1 局部敏感哈希。给定一族哈希函数H，H是一个从欧式空间S到哈希编码空间U的映射。对于H中的函数h，若都满足以下条件，则称此哈希函数是敏感的，其中为敏感散列函数。

（1）如果，那么

（2）如果，那么

其中，表示两个具有多维属性的数据对象，为2个对象的相异程度。

代码相似度检测过程中的LSH算法伪代码如下所示。

算法1 LSH算法：其功能是将原始高维空间中的点映射到一个或多个哈希表中的不同位置，该术语位置称为桶。它的映射原理是：在高维空间中非常接近的点将以高概率映射到同一哈希桶上。

1： function LSH（V ： vectors， r ： distance， p1 ： prob）： rcANs

2：N←∅; LSH（V，r ， p1）

3：repeatpick a ν ∈ V

4：rcAN ←queryLSH（ν）

5：if rcAN > 1 then

6：N ←N ∪ {rcAN＼Un∈Nn}

7：end if

8：V ←V＼rcAN

9：until v =∅

10：return PostProcessing（N）

11： end function

4实验

在本节中，我们在真实数据集上进行实验并报告结果。实验旨在检测LSH模型在中小型数据集上的效果。Word2vec根据上下文进行训练后的词向量可以使用上下文信息来判断并找到具有类似含义的词语，用该结果对文本语义上的相似度进行一定的度量，且采用与LSH词向量化方法原理相同的数据处理方法。本文是将基于LSH算法的代码相似度实验和基于Word2Vec算法的代码相似度实验进行比较。我们所有的LSH实验都是在I5CPU服务器上完成的。

4.1实验设置

4.1.1数据准备

我们在两个真实数据集下进行实验：OJ系统的OJClone（C++_DATA）和网络上搜集整合的数据集（C_DATA）。

在数据预处理的过程中，我们先对代码中容易引起歧义的字符进行清除，去除空白、停用词等，保证代码内容不引起歧义;并将代码中出现的特征词训练为对应的词向量，以便用于LSH模型的函数输入和查询;接着通过计算欧式距离得到各个相似度，欧式距离越小则越相似。表4-1列出了数据集的总体信息。

4.2性能评价指标

代码相似度计算属于二分类问题，两个代码文件若被判断为相似则分类为1，不相似则被分类为0。对于这样的问题，本文使用了sklearn库中的metrics进行计算，通过精确率、召回率、准确率和F1值等参数来评价我们所使用的LSH模型的好坏。

4.3实验结果及分析

针对本文提出的模型，实施了两个实验进行验证：

（1）对LSH模型使用不同编程语言数据集来判断模型的优劣;

（2）将本文提出的LSH模型和其他的基准模型Word2Vec模型进行对比。

4.3.1 LSH模型的相似度计算实验

（1）模型的搭建

LSH算法的模型搭建主要利用了Lshash函數以及nltk语料库进行英文分词实现。并采用了sklearn库中model_selection来同时进行训练集和测试集的划分来进行相似度计算。对于输入的数据集数据采用随机打乱的方式，训练集和测试集的比值为7：3。主要调节的参数为LSH主函数初始化时的二进制散列的长度，程序中名称为hash_size（最终选定值为64）。通过不断调整hash_size参数和训练，直到模型的精确度最高、语义相似度的F1值最大为止。

为了研究hash_size对于该模型的Precision和Recall值的影响，本文选择了不同的hash_size对C++_DATA数据集进行了重复计算，得到的结果如下图4-2所示：

（2）Word2Vec模型的相似度计算实验

本实验是针对本文提出的LSH模型实验所作的对比实验，实验过程中严格控制变量，最终通过LSH添加标签的LSH算法和直接进行Word2Vec算法的相似度计算两种方式在实验数据集上的优劣来分析得出结论。

（3）实验结果

实验采用不同数据集重复进行，通过四次实验的比对查看模型效率在数据量方面的变化以及在不同编程语言下的效果。LSH模型和Word2Vec模型在处理后的各个数据集上实验，评价指标对比如下表4-2。

4.3.2 实验结果分析

通过表4-2模型指标数据，我们可以得出LSH模型在处理较大规模数据时效果比小规模数据效果要好;以及不论是数据量较大的C数据集还是数据量较小的C++数据集，LSH模型的准确率和召回率都保持在0.9以上;此外，四组不同数据集下的数据可以看出，Word2Vec模型准确率保持较为良好，但在召回率和F1值上显示结果很差，这说明Word2Vec模型对正样本的识别能力弱以及模型不稳健。

LSH模型在处理较大规模数据时效果优于处理小规模数据，同时，LSH函数通过对词向量再次降维处理，并且通过查询的操作搜索相似对有利于代码分类结果的效率提升，在对于本实验给定的数据集下，LSH模型检测代码相似度明显优于Word2Vec模型，这充分体现了LSH本身的优势特点。

5结论

比较实验结果表明：LSH的模型在进行较大规模的数据处理时依旧能够保持一个不错的性能计算，与Word2Vec方法比较，多加一步局部敏感哈希算法的处理能使数据更加轻量化，更有利于进行代码相似度计算;与其他模型的比较，虽然LSH模型的表现更加突出，但缺乏对上下文语义的分析，得到结果为近似值，若想使LSH模型的代码相似度检测结果更加精准，可以另外引入AST语法树解析代码语法。

参考文献：

[1]Faidhi J A W，Robinson S K，An empirical approach for detecting program similarity and plagiarism within a university programming environment[J].Computer Education， 1987， 11（1）：11-19

[2]王继远.一种用于软件作业评判系统的程序结构分析算法的设计与实现[D].北京邮电大学，2007

[3]White M，Tufano M，Vendome C，et al.Deep Learning code fragments for code c-lone detection[C]//IEEE/ACM International Conference on Automated Software Engineerin-g.IEEE，2016.

[4]Hitesh Sajnani; VaibhavSaini; Jeffrey Svajlenko; Chanchal K. Roy; Lopes. SourcererCC.Software Enginee-ing.2016.PP 1157-1168

[5]陈丹华、王艳娜、周子力等人.《基于Word2Vec的WordNet词语相似度计算研究》.计算机工程与应用.CSCD.2021-03-16

基金项目：江苏省高等学校大学生创新创业训练计划项目。

作者简介：陈秀芳（2000—），女，广西玉林人，江苏师范大学智慧教育学院本科在读，研究方向：软件工程。