基于Word2vec的克隆代码检测方法研究

贾 清，杨 抒

(新疆农业大学 计算机与信息工程学院，新疆 乌鲁木齐 830052)

0 引 言

近年来随着软件开发环境、操作系统及软件相关领域的不断发展，导致软件复用的规模越来越大，为了提高软件的开发效率，越来越多的软件开发成果被开发人员直接复用，这种被开发人员复用并且具有相似语法及语义特征的代码段称为克隆代码[1]。

目前学界对克隆代码的定义有很多。比如文献[1]中将克隆代码定义为：代码文件中多个相同或相似的代码片段[1]。文献[2]将克隆代码定义为：具有相似语法及语义特征的代码段[2]。文中统一将克隆代码定义为：具有相似语法及语义特征的代码段。

由于代码克隆被认为会降低软件的可维护性[1]，有学者通过对两个开源软件系统的案例研究，发现1%到3%的克隆不一致的更改会导致软件缺陷，而在其他研究报告中的百分比要更高[2]。针对该问题，提出了几种代码克隆检测技术和工具，例如文献[3-11]。近年来，深度学习成为热门话题，有学者提出利用深度学习的相关技术对相似记录进行检测，例如文献[12-15]。文中利用Word2vec模型对新疆马业电子商务交易平台中的克隆代码进行检测。

新疆维吾尔自治区重大科技专项“马产业升级技术创新工程”子课题“马产业科技创新平台建设”中的“新疆马业电子商务交易平台”，实现了包括在线马匹拍卖为主要功能的信息发布管理、信息展示管理、订单管理、资金结算管理的在线电商服务。在开发该系统的过程中，为了提高开发效率，开发人员针对已经实现的并具有相似功能的代码进行粘贴复制的操作，在开发者的思维中，这样的操作代码效率高并且错误率最低，可以节省开发系统的时间与成本，所以开发人员会复用大量代码，导致生成了大量的克隆代码，并且随着系统的不断更新，需要对系统进行增加功能或者修改功能，造成系统的体积越来越大，并且产生越来越多的克隆代码。为了解决该问题，利用基于Word2vec的克隆代码检测方法对新疆马业电子商务交易平台的代码进行克隆检测。

1 Word2vec模型

Word2vec本质为双层的神经网络，其作用是将词转换成向量，这些模型可以将词汇以固定维数的向量表示出来。较为常用的one-hot编码方式，可能每个词都是百万维的向量，占用大量内存，并且在判断意思相似的词语，相似的句子的时候效果不理想。而Word2vec会根据上下文，对上下文进行训练。每个词不再是稀疏向量(只有某一位为1，其余位均为0)，而是一个稠密的拥有固定维数的向量，可以大大减少存储空间和计算时间。其次，Word2vec经过训练后的词向量可以使用上下文信息来判断并且找到具有类似含义的词语。Word2vec一共包含两种模型，分别是CBOW模型(continue bag of word)，即用上下文预测中心词，以及skip-gram模型(跳字模型)，即用中心词预测上下文。Word2vec的本质是无监督学习，从词向量中可以看出该神经网络只有一层，因此必须要有输入和输出。而训练过程或者目标不是得到预测结果词，而是得到隐藏层的权重。

1.1 skip-gram模型

数学描述为：skim-gram模型需要最大给定任意中心词生成所有背景词的概率：

(1)

上式的最大似然估计与以下最小化损失函数等价：

(2)

U和V分别用来表示背景词及中心词的词向量。词典中下标为i的词，中心词和背景词的词向量可以表示为vi和ui，skip-grams所要学习的模型参数正是词典中这两种词向量。损失函数为了放入该模型参数，需要使用模型参数表达损失函数中的给定中心词生成背景词的条件概率。假设中心词为wc，背景词为wo，所以输入中心词向量生成背景词向量的条件概率可以定义为：

(3)

当序列长度T较大时，为了计算该子序列的损失，常用做法是在每次迭代时就随机采样一个相对短的子序列，会根据该损失来计算词向量的梯度及迭代词向量。随机采样的子序列的损失其本质是对子序列中确定中心词生成的背景词的条件概率的对数再求其平均数，然后再通过微分运算，可以获得上面公式中条件概率的对数关于中心词向量vc的梯度。

(4)

经过转换后该公式可简化为：

(5)

在训练模型的过程中，迭代运算其实是用梯度来迭代子序列中出现过的中心词和背景词的向量；在结束训练后，对于词典中任意索引为i的词，均得到该词作为中心词和背景词的两组词向量vi和ui，其中skip-gram模型网络结构如图1所示。

图1 skip-gram模型网络结构

1.2 CBOW模型

CBOW模型预测该中心词，需要用一个中心词在文本序列前后的背景词来预测。其数学描述为：CBOW模型需要最大化给定任意背景词生成任意中心词的概率：

(6)

上式的最大似然估计与最小化损失函数等价：

(7)

用V和U来表示中心词和背景词的向量。对于词典中某个位置为i的词，它在作为中心词和背景词时的向量可以分别表示为vi和ui。而词典中的这两种向量正是CBOW所要学习的模型参数。损失函数需要将模型参数植入，需要使用模型参数表达损失函数中的给定背景词生成中心词的概率。设中心词wc在词典中索引为c，背景词wo1,…,wo2m，损失函数中的背景词生成中心词的概率可以使用softmax函数定义为：

(8)

与skip-gram模型一样，当序列T较大时，通常在每次迭代时随机采样一个较短的子序列来计算有关该子序列的损失。根据损失计算词向量的梯度并迭代词向量。通过微分，可以计算出上式中条件概率的对数有关任一背景词向量Voi(i=1,2,…,2m)的梯度为：

(9)

该式子也可写为：

(10)

对于词典中索引为i的词，会在训练结束后得到该词作为背景词和中心词的两组词向量vi和ui，其CBOW模型的网络结构如图2所示。

图2 CBOW模型网络结构

2 克隆代码检测

新疆马业电子商务交易平台是一款基于Django框架的马匹在线竞拍系统，服务于马匹竞拍的日常管理，为了满足新疆马业的发展，科学管理，提高效率而开发的一款系统。而开发过程中为了提高开发效率，降低开发的时间成本，在实现相同或者相似的功能时，开发人员大都使用了粘贴复制的方式进行开发，所以在该系统中存在克隆代码。本研究中的数据即为新疆马产业科技创新平台中的所有代码，该平台共有五个子平台，分别为马业生产过程数据采集平台、马业电子商务交易平台、赛马赛事组织管理信息平台、马产业大数据决策支持平台、马业科技信息服务管理平台，实验训练集选取该平台中的16 914行代码，验证集1 000行以及测试集1 251行。

本研究的目的在于能够利用Word2vec检测出新疆马业电商平台中存在的克隆代码。找到系统中具有高相似度的克隆函数，为后期代码重构、系统维护提供数据支持，其流程为：

①获取源代码：马产业科技创新平台建设中的部分代码。

②数据预处理：将数据分为训练集、验证集、测试集，并且删除注释、停用词、空格、标点符号。

②获得语料库：经过数据预处理后的数据。

④训练模型：选择skim-gram模型训练。

⑤获取词向量：训练结束后会获得vocab字典，包含了所有语料库中的词(去除了出现频数较少的词汇)。

⑥计算相似度：利用夹角余弦的方式分别计算两个列表的距离。

⑦结果输出：根据相似度计算的结果，根据序号找到对应代码，将结果输出至txt文件中。

基于Word2vec克隆代码检测流程如图3所示。

图3 克隆代码检测流程

2.1 数据预处理

将新疆马产业创新平台中的所有view作为训练集的代码提取到一个名为test.csv的文件中。该文件中的代码不能直接用于Word2vec的训练，需要对其进行一些预处理。

以字符串的格式读取train.csv文件，按照换行符分割字符串，此分割方式可以将每个方法单独分割成一个字符串；循环遍历方法字符串，删除字符串中的换行符(/n)、回车符(/r)；利用jieba分词器对代码进行分词。结巴分词器会根据已经写好的停用词文件将代码中的停用词进行删除操作。

将数据加载到Python Pandas DataFrame中，pandas库将DataFrame定义为具有行和列的二维数据，大小可变的数据结构，每行代表一个数据样本。

将经过处理后的test数据写入一个名为test_after_process_text_dir.csv的文件中。

经过数据预处理的代码，保留了关键词、逻辑符等。

2.2 模型训练

在本次实验中用到的模型为skip-grams，即用中心词来预测文本序列背景词的概率。

在通过Word2vec训练模型时，会将训练集中的所有词存入vocab中，如果有新词出现，则存入，如果已经有该词汇，不再重复操作。同时，每次存储一个新词汇，都要检测vocab的size是否达到上限。若达到上限，会将出现次数不达标的词汇对应的vocab空间释放。在新疆马产业科技创新平台中，选取部分函数，共计有118 572个词汇用来训练模型，训练完成后会自动生成一个扩展名为.model的模型。

2.3 相似度计算

计算相似度的方法有欧氏距离(Euclidean distance)、曼哈顿距离(Manhattan distance)、标准化欧氏距离(standardized Euclidean distance)、夹角余弦(cosine)。在此次实验中用到计算相似度的方法为夹角余弦，用该方法来衡量样本向量之间的差异，其公式为：

(11)

在本次实验中，将马匹竞拍系统中的代码作为测试集，共有92个函数。将test中的数据与train中的代码进行相似度计算，但是在计算相似度之前，程序会将每个函数中的词汇与训练模型vocab中的词汇进行对比，删除不在vocab中的词汇，否则在计算相似度时，会因为某些没有转换成词向量的词汇导致程序错误。然后将每一个函数分别与马匹竞拍系统中的所有代码一一进行相似度计算。计算完成后可以将相似度的值输出至pycharm的run窗口中，如图4所示。

图4 相似度计算结果

2.4 结果输出

根据sim_result的计算结果，将sim_result.csv中序号对应的代码一一找出：

图5 部分检测结果输出

①构建文档字典：遍历文件，此处的文件分别为test_after_process_text_dir.csv及train_after_process_text_dir.csv。将每行结果去除/r及/n，以“，”作为分割符，判断列表长度是否为2，若不做此操作，可能会报数字越界的错误。以列表的序号为key值，以内容为value值。

②相似结果输出：打开sim_result.csv文件，以“，”作为分割符，在对应id与test_after_process_text_dir.csv及train_after_process_text_dir.csv分别进行匹配，找出相应的内容，将结果输出至result.txt文件中，部分结果如图5所示。

3 结束语

基于Word2vec的克隆代码研究将新疆马业电商平台中的代码作为语料库，利用Word2vec训练词向量模型，使用的模型为skip-grams，开发工具为pycharm，开发语言为python，分词器选用jieba分词器。

将新疆马产业创新平台中的view中部分代码作为训练集，包含400个方法，验证集包含59个方法，测试集包含92个方法，共计551个方法，用到118 572个词汇。

在基于Word2vec的克隆代码研究中，①将新疆马产业创新平台中的view中部分代码进行预处理，去除空白符、注释、标识符、回车符号；②将处理后的数据作为Word2vec的语料库，利用Word2vec训练向量模型,其中模型选择skip-grams，sentences是要训练模型时的语料库，该研究中，sentences是遍历文件所得。size是构造的词向量的维数，默认值是100，该维数的大小取决于sentences的大小，在该实验中size为150。Window是词向量的上下文最大距离，若Window越大，和某一次较远的词也会产生上下文关系，默认值为5。sg是Word2vec关于选择两个模型，如果sg的值为0，选择的是CBOW模型，若取值为1，则选择的是skip-grams模型，若未写sg，则该值默认选择的是CBOW模型。min_count是计算词向量出现的最小频数。这个值可以自动过滤很多出现次数小于该值的词汇，默认是5。如果语料库较小，其值可以更改得更低一些。Iter为随机梯度下降法中迭代的最大次数，默认为5，该值的大小取决于语料库的大小。alpha是随机梯度下降法中迭代的初始步长，默认是0.025。min_alpha给出了最小迭代步长值，这是由于算法支持在迭代的过程中逐渐减小步长；③将验证集的代码进行预处理，去除空白符、注释、标识符、回车符号；④将处理后的验证集进行相似度计算，相似度计算之前需要先去除不在词汇表中的词汇。

基于Word2vec的克隆代码研究根据词向量可以很好地计算出代码的相似度，从而找到文件中的克隆代码，为后续代码优化提供数据支持。