基于LSH的代碼相似度檢測研究

陳秀芳 岳江寧 渠艷琪 蔡旺 王旭

摘要：代碼相似度檢測研究是軟件工程領(lǐng)域許多很重要的任務(wù)的基礎(chǔ)操作，而現(xiàn)有的代碼相似度檢測方法普遍存在著緯度高、計算復(fù)雜和執(zhí)行成本高的問題。為了解決這些問題，本文提出了局部敏感哈希（Locality Sensitive Hash，LSH）算法：它能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行最近鄰快速查找，挖掘出相似的數(shù)據(jù)，從而實現(xiàn)代碼相似度的檢測研究。實驗結(jié)果表明：LSH算法可以對海量數(shù)據(jù)進(jìn)行處理，對與代碼相似度的檢測檢測有很大的好處，本文還將LSH算法與其他檢測方法進(jìn)行了比較，實驗結(jié)果表明LSH算法優(yōu)于Word2vec檢測方法。

關(guān)鍵詞：代碼相似度;局部敏感哈希;代碼分類;代碼檢測

1簡介

代碼相似性檢測是用來衡量兩個代碼片段之間的相似程度。度量代碼相似性是許多軟件工程任務(wù)的前端基礎(chǔ)。研究代碼相似性能夠提升代碼質(zhì)量，這對許多軟件工程的開發(fā)有很大的研究價值。

現(xiàn)存的代碼相似性檢測方法可以分成三類：屬性計數(shù)方法、結(jié)構(gòu)度量技術(shù)和深度學(xué)習(xí)技術(shù)。屬性計數(shù)方法的基本原理是統(tǒng)計源程序中的某些屬性計數(shù)作為相似性判斷的依據(jù)。如：Grier[1]等人分別使用了20和24種統(tǒng)計特征來檢測代碼的相似性。結(jié)構(gòu)度量技術(shù)主要是對源程序進(jìn)行結(jié)構(gòu)分析以及執(zhí)行程序流程。具有代表性的研究有：北京郵電大學(xué)[2]采用了基于XML方法對結(jié)構(gòu)度量技術(shù)進(jìn)行相似度計算。深度學(xué)習(xí)技術(shù)是學(xué)習(xí)樣本數(shù)據(jù)的內(nèi)在規(guī)律和表示層次。如：White[3]等人提出的基于深度學(xué)習(xí)技術(shù)的代碼相似性檢測方法。這三種技術(shù)既有優(yōu)點也有缺點：屬性技術(shù)方法語法結(jié)構(gòu)容易被人所理解，實現(xiàn)簡單，但是精確率比較差;結(jié)構(gòu)度量技術(shù)對于語法相似性檢測有較好效果但是忽略了語義層面的信息;深度學(xué)習(xí)技術(shù)方法性能很好但是需要很大的數(shù)據(jù)集，并且受數(shù)據(jù)集、參數(shù)的好壞影響，具有不穩(wěn)定性和不可解釋性。

針對上面提出的問題以及現(xiàn)有的方法，我們提出使用LSH算法去更好的解決問題，LSH能夠?qū)⒑Ａ繑?shù)據(jù)進(jìn)行清洗與降維用于解決海量數(shù)據(jù)與高維空間的困難，將K最近鄰（K-NearestNeighbor，KNN）分類算法的時間復(fù)雜度縮減到亞線性。實驗結(jié)果表明：LSH算法通過降維和過濾操作極大地縮短了查詢計算時間，提高了效率。

2相關(guān)工作

2.1代碼相似度檢測方法

在現(xiàn)有技術(shù)中，SourcererCC[4]是基于token的代碼克隆檢測器， 它可以在不同的粒度級別和不同語言上進(jìn)行檢測。但它只考慮代碼片段在詞匯層次上的相似性，忽略了語法信息。Word2vec[5]是一個將單詞轉(zhuǎn)換成詞向量的工具，它的模型以大規(guī)模語料庫作為輸入，通過模型的訓(xùn)練后映射到一個幾百維度的向量空間中。這些都是現(xiàn)存的在代碼相似性方面做的較好的方法，其余不再介紹。在代碼相似度研究領(lǐng)域，LSH算法一開始是用來做引擎的，現(xiàn)在我們將它用做代碼相似度的檢測。在使用LSH算法之前，首先要對源程序進(jìn)行代碼表征，現(xiàn)有的代碼表征的方法主要有：基于文本、基于Token、基于AST樹和基于圖的表征代碼發(fā)方法。具體方法可自行查詢。

3基于LSH的代碼相似度檢測模型

為了能夠?qū)^大數(shù)據(jù)集進(jìn)行代碼相似度的檢測，本文提出了基于LSH算法的模型。如圖3-1所示，該模型主要由數(shù)據(jù)預(yù)處理、數(shù)據(jù)特征向量化和LSH算法三部分組成。

在此過程中需要將讀取的數(shù)據(jù)進(jìn)行初步處理，具體步驟如下：第一步數(shù)據(jù)抽取：對指定文件中的代碼進(jìn)行讀取，從中提取出數(shù)據(jù)的實體和關(guān)系，經(jīng)過關(guān)聯(lián)和聚合之后采用統(tǒng)一定義的結(jié)構(gòu)來存儲這些數(shù)據(jù)。第二步數(shù)據(jù)清理：通過填寫缺失值，光滑噪聲數(shù)據(jù)，識別或刪除離群點，并解決不一致性“清理”數(shù)據(jù)。本文采用了nltk（Natural Language Toolkit）自然語言處理工具庫中的word_tokenize進(jìn)行分詞。

本文為了進(jìn)行詞集的向量化表現(xiàn)采用了one-hot的詞袋模型，將進(jìn)行分詞之后獲取到的詞典數(shù)據(jù)集進(jìn)行特征詞提取，生成一個詞典。用該詞在代碼中出現(xiàn)的次數(shù)去表示所出現(xiàn)的頻率，分別為1或0。如上過程在數(shù)據(jù)特征向量化模型中得到每篇代碼的詞向量之后，就可以送入到LSH模型中進(jìn)行下一步計算。

3.1 LSH算法

將提取出的特征向量進(jìn)行局部敏感哈希處理，使得在一個大的原始數(shù)據(jù)集合內(nèi)查找相似特征向量的問題轉(zhuǎn)化為在一個小集合內(nèi)查找相似特征向量的問題，極大降低了時間復(fù)雜度。

定義1 局部敏感哈希。給定一族哈希函數(shù)H，H是一個從歐式空間S到哈希編碼空間U的映射。對于H中的函數(shù)h，若都滿足以下條件，則稱此哈希函數(shù)是敏感的，其中為敏感散列函數(shù)。

（1）如果，那么

（2）如果，那么

其中，表示兩個具有多維屬性的數(shù)據(jù)對象，為2個對象的相異程度。

代碼相似度檢測過程中的LSH算法偽代碼如下所示。

算法1?LSH算法：其功能是將原始高維空間中的點映射到一個或多個哈希表中的不同位置，該術(shù)語位置稱為桶。它的映射原理是：在高維空間中非常接近的點將以高概率映射到同一哈希桶上。

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實驗

在本節(jié)中，我們在真實數(shù)據(jù)集上進(jìn)行實驗并報告結(jié)果。實驗旨在檢測LSH模型在中小型數(shù)據(jù)集上的效果。Word2vec根據(jù)上下文進(jìn)行訓(xùn)練后的詞向量可以使用上下文信息來判斷并找到具有類似含義的詞語，用該結(jié)果對文本語義上的相似度進(jìn)行一定的度量，且采用與LSH詞向量化方法原理相同的數(shù)據(jù)處理方法。本文是將基于LSH算法的代碼相似度實驗和基于Word2Vec算法的代碼相似度實驗進(jìn)行比較。我們所有的LSH實驗都是在I5CPU服務(wù)器上完成的。

4.1實驗設(shè)置

4.1.1數(shù)據(jù)準(zhǔn)備

我們在兩個真實數(shù)據(jù)集下進(jìn)行實驗：OJ系統(tǒng)的OJClone（C++_DATA）和網(wǎng)絡(luò)上搜集整合的數(shù)據(jù)集（C_DATA）。

在數(shù)據(jù)預(yù)處理的過程中，我們先對代碼中容易引起歧義的字符進(jìn)行清除，去除空白、停用詞等，保證代碼內(nèi)容不引起歧義;并將代碼中出現(xiàn)的特征詞訓(xùn)練為對應(yīng)的詞向量，以便用于LSH模型的函數(shù)輸入和查詢;接著通過計算歐式距離得到各個相似度，歐式距離越小則越相似。表4-1列出了數(shù)據(jù)集的總體信息。

4.2性能評價指標(biāo)

代碼相似度計算屬于二分類問題，兩個代碼文件若被判斷為相似則分類為1，不相似則被分類為0。對于這樣的問題，本文使用了sklearn庫中的metrics進(jìn)行計算，通過精確率、召回率、準(zhǔn)確率和F1值等參數(shù)來評價我們所使用的LSH模型的好壞。

4.3實驗結(jié)果及分析

針對本文提出的模型，實施了兩個實驗進(jìn)行驗證：

（1）對LSH模型使用不同編程語言數(shù)據(jù)集來判斷模型的優(yōu)劣;

（2）將本文提出的LSH模型和其他的基準(zhǔn)模型Word2Vec模型進(jìn)行對比。

4.3.1 LSH模型的相似度計算實驗

（1）模型的搭建

LSH算法的模型搭建主要利用了Lshash函數(shù)以及nltk語料庫進(jìn)行英文分詞實現(xiàn)。并采用了sklearn庫中model_selection來同時進(jìn)行訓(xùn)練集和測試集的劃分來進(jìn)行相似度計算。對于輸入的數(shù)據(jù)集數(shù)據(jù)采用隨機打亂的方式，訓(xùn)練集和測試集的比值為7：3。主要調(diào)節(jié)的參數(shù)為LSH主函數(shù)初始化時的二進(jìn)制散列的長度，程序中名稱為hash_size（最終選定值為64）。通過不斷調(diào)整hash_size參數(shù)和訓(xùn)練，直到模型的精確度最高、語義相似度的F1值最大為止。

為了研究hash_size對于該模型的Precision和Recall值的影響，本文選擇了不同的hash_size對C++_DATA數(shù)據(jù)集進(jìn)行了重復(fù)計算，得到的結(jié)果如下圖4-2所示：

（2）Word2Vec模型的相似度計算實驗

本實驗是針對本文提出的LSH模型實驗所作的對比實驗，實驗過程中嚴(yán)格控制變量，最終通過LSH添加標(biāo)簽的LSH算法和直接進(jìn)行Word2Vec算法的相似度計算兩種方式在實驗數(shù)據(jù)集上的優(yōu)劣來分析得出結(jié)論。

（3）實驗結(jié)果

實驗采用不同數(shù)據(jù)集重復(fù)進(jìn)行，通過四次實驗的比對查看模型效率在數(shù)據(jù)量方面的變化以及在不同編程語言下的效果。LSH模型和Word2Vec模型在處理后的各個數(shù)據(jù)集上實驗，評價指標(biāo)對比如下表4-2。

4.3.2 實驗結(jié)果分析

通過表4-2模型指標(biāo)數(shù)據(jù)，我們可以得出LSH模型在處理較大規(guī)模數(shù)據(jù)時效果比小規(guī)模數(shù)據(jù)效果要好;以及不論是數(shù)據(jù)量較大的C數(shù)據(jù)集還是數(shù)據(jù)量較小的C++數(shù)據(jù)集，LSH模型的準(zhǔn)確率和召回率都保持在0.9以上;此外，四組不同數(shù)據(jù)集下的數(shù)據(jù)可以看出，Word2Vec模型準(zhǔn)確率保持較為良好，但在召回率和F1值上顯示結(jié)果很差，這說明Word2Vec模型對正樣本的識別能力弱以及模型不穩(wěn)健。

LSH模型在處理較大規(guī)模數(shù)據(jù)時效果優(yōu)于處理小規(guī)模數(shù)據(jù)，同時，LSH函數(shù)通過對詞向量再次降維處理，并且通過查詢的操作搜索相似對有利于代碼分類結(jié)果的效率提升，在對于本實驗給定的數(shù)據(jù)集下，LSH模型檢測代碼相似度明顯優(yōu)于Word2Vec模型，這充分體現(xiàn)了LSH本身的優(yōu)勢特點。

5結(jié)論

比較實驗結(jié)果表明：LSH的模型在進(jìn)行較大規(guī)模的數(shù)據(jù)處理時依舊能夠保持一個不錯的性能計算，與Word2Vec方法比較，多加一步局部敏感哈希算法的處理能使數(shù)據(jù)更加輕量化，更有利于進(jìn)行代碼相似度計算;與其他模型的比較，雖然LSH模型的表現(xiàn)更加突出，但缺乏對上下文語義的分析，得到結(jié)果為近似值，若想使LSH模型的代碼相似度檢測結(jié)果更加精準(zhǔn)，可以另外引入AST語法樹解析代碼語法。

參考文獻(xiàn)：

[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]王繼遠(yuǎn).一種用于軟件作業(yè)評判系統(tǒng)的程序結(jié)構(gòu)分析算法的設(shè)計與實現(xiàn)[D].北京郵電大學(xué)，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詞語相似度計算研究》.計算機工程與應(yīng)用.CSCD.2021-03-16

基金項目：江蘇省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目。

作者簡介：陳秀芳（2000—），女，廣西玉林人，江蘇師范大學(xué)智慧教育學(xué)院本科在讀，研究方向：軟件工程。