基于多特征值的源代碼相似性檢測技術(shù)

展佳俊，趙逢禹，艾 均

(上海理工大學(xué) 光電信息與計算機工程學(xué)院，上海 200093)

0 引 言

隨著計算機技術(shù)以及互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，軟件系統(tǒng)已經(jīng)應(yīng)用于各行各業(yè)，軟件的規(guī)模也越來越大。在軟件系統(tǒng)開發(fā)的過程中，為了滿足敏捷開發(fā)的快速迭代需求，大多數(shù)軟件開發(fā)工程師通過直接復(fù)制粘貼或者在復(fù)制的基礎(chǔ)上進行若干修改后來重用代碼，這是一種十分常見的現(xiàn)象。因此，相似代碼在軟件系統(tǒng)中是十分常見的，開發(fā)人員直接拷貝粘貼或者在此基礎(chǔ)上進行若干修改實質(zhì)上是一種簡單的代碼復(fù)用機制。這種復(fù)用機制是非正式和不可控的，并且會帶來一系列負面影響[1]。隨著開源軟件的迅速發(fā)展，一些開源項目和商業(yè)軟件項目中存在大量復(fù)用的開源代碼，這樣可以幫助軟件開發(fā)工程師加快項目的開發(fā)進度，但是也帶來了一些風(fēng)險，可能會出現(xiàn)嚴重的安全漏洞。如今代碼抄襲現(xiàn)象也是經(jīng)常發(fā)生的[2-3]，而源代碼相似性檢測是代碼抄襲檢測的核心，源代碼相似性檢測技術(shù)的研究具有重要意義。

目前的源代碼相似性檢測技術(shù)主要有基于token的代碼相似檢測技術(shù)、基于抽象語法樹的代碼相似檢測技術(shù)、基于程序依賴圖的代碼相似檢測技術(shù)和基于深度學(xué)習(xí)的代碼相似檢測技術(shù)等。

Wang等人提出了一種基于token的代碼相似性檢測技術(shù)[4]，在源代碼預(yù)處理之后，他們利用一個滑動窗口掃描源代碼，將窗口中的源代碼進行哈希，最后進行多重對比從而檢測代碼相似。國內(nèi)學(xué)者王春輝也提出了一種基于串匹配的程序代碼相似檢測方法[5]，該技術(shù)將源代碼轉(zhuǎn)化成token，使用高效的RKR-GST串匹配算法找出每對token的所有最長公共子串，然后計算相似度?；趖oken的技術(shù)沒有考慮到代碼行的順序，如果代碼行順序被改變了，相似代碼將不會被檢測到。并且該技術(shù)沒有充分利用源代碼信息，比如它會忽略掉源代碼語法結(jié)構(gòu)信息。

Jiang等人提出了一種基于抽象語法樹的相似性檢測技術(shù)[6]，并使用歐氏距離來計算代碼相似度。該方法首先將源代碼生成語法樹，然后再將語法樹生成一個向量集用于承載語法樹的結(jié)構(gòu)信息，接著使用局部敏感哈希算法對這些向量進行聚類，通過尋找一個向量的近鄰檢測代碼相似。國內(nèi)學(xué)者朱波等人也提出了一種AST的代碼相似檢測技術(shù)[7]，該技術(shù)通過預(yù)處理去除生成AST時的冗余信息,再進行詞法語法分析,得到相應(yīng)的AST;然后通過自適應(yīng)閾值的選取方式,利用AST遍歷得到的程序?qū)傩浴⒎椒ㄐ蛄?對AST進行相似度計算,最終判定代碼是否相似。

GPLAG[8]是一種基于程序依賴圖的源代碼相似性檢測技術(shù)，它將代碼表示為程序依賴圖，并使用程序依賴圖子圖對比算法來進行源代碼相似檢測。國內(nèi)學(xué)者呂利也提出了一種基于PDG的相似檢測算法[9]，該算法主要包括構(gòu)造代碼段的PDG，檢測PDG的最大同構(gòu)子圖，和判斷同構(gòu)子圖對應(yīng)的代碼是否為克隆代碼三步。

隨著機器學(xué)習(xí)和自然語言處理工具的發(fā)展，學(xué)者開始將機器學(xué)習(xí)、自然語言處理等技術(shù)應(yīng)用于代碼相似檢測研究中。Wei等人[10]提出了基于深度學(xué)習(xí)的相似性技術(shù)來檢測代碼相似。他們將相似性檢測問題轉(zhuǎn)化為學(xué)習(xí)源代碼的哈希特征的有監(jiān)督學(xué)習(xí)問題,首先將源代碼用抽象語法樹表征之后用一定的編碼規(guī)則進行編碼,然后將編碼后的數(shù)據(jù)輸入一個修改過的卷積神經(jīng)網(wǎng)絡(luò)當(dāng)中進行訓(xùn)練，最后用訓(xùn)練到的特征進行代碼相似檢測。阿卡什等人提出了基于源代碼注釋的源代碼相似性檢測技術(shù)[11]，他們的方法是基于LDA來檢測相似代碼，該方法僅使用了源代碼注釋來進行源代碼相似性檢測。

以上研究分別從代碼token、代碼的抽象語法樹、代碼的程序依賴圖以及代碼注釋等維度來進行源代碼相似性檢測研究，他們的方法分別從不同的維度對特定類型的代碼進行相似性分析。

由于代碼的結(jié)構(gòu)與語義的復(fù)雜性，使得這些相似性檢測技術(shù)效果并不令人滿意，而如果將多維度信息綜合考慮在一起，對于相似代碼檢測的準(zhǔn)確度應(yīng)該還有較大提升空間。為了提高源代碼相似性度量的準(zhǔn)確性，該文以方法級別的源代碼相似為研究對象提出了一種基于多特征值的源代碼相似性度量技術(shù)，該技術(shù)主要從代碼注釋、方法型構(gòu)、代碼文本語句與結(jié)構(gòu)等方面來進行分析并研究，從這些方面來提取特征進行方法級別源代碼相似性檢測。

1 相關(guān)概念

1.1 代碼相似定義

目前對于源代碼相似并沒有一個權(quán)威的定義，早期研究者認為：“如果一份代碼能夠通過少量的常規(guī)變換手段得到，這兩份代碼就是相似的”[12]，少量的意思是付出的代價較少，常規(guī)手段是指普通的文本置換。然而，隨著計算機技術(shù)的不斷發(fā)展，人們可以使用更高級的代碼抄襲方式來對代碼進行大規(guī)模的修改。該文采用文獻[8]所定義的相似：“源代碼之間滿足一些抄襲變化方式，就可以認為是相似的”。目前對于代碼抄襲手段還沒有精確的分類。Jones總結(jié)了常見的10種抄襲手段[13]，這10種常見的抄襲手段為：完整拷貝、修改注釋、重新排版、標(biāo)識符重命名、更改代碼塊順序、調(diào)整代碼塊里語句的順序、更改表達式中操作符和操作數(shù)的順序、更改數(shù)據(jù)類型、添加冗余代碼、控制結(jié)構(gòu)的等價變換。因此，筆者認為只要兩段代碼之間滿足以上一種抄襲變化方式，就可以認為這兩段代碼是相似的。

Yamamoto等[14]給出了兩個軟件系統(tǒng)的相似度定義。對于兩個軟件P和X，軟件P是由元素P1,P2,…,Pm組成，P的集合構(gòu)成表示為{P1,P2,…,Pm}，軟件X是由元素X1,X2,…,Xn組成，X的集合構(gòu)成表示為{X1,X2,…,Xn}。P、X中的元素表示為軟件P、X中的文件或者代碼。P和X的相似性定義為：

S(P,X)=

(1)

其中，集合Rs表示所有匹配對(Pi,Xj)的集合。根據(jù)式(1)可看出，相似性S為一個比值，由Rs中的元素個數(shù)比上P、X中元素個數(shù)之和。

目前對于代碼相似度沒有一個統(tǒng)一的定義，代碼相似度與上述軟件系統(tǒng)相似度類似，該文將代碼分為注釋、型構(gòu)、代碼文本語句與結(jié)構(gòu)這四個維度，通過加權(quán)計算這四個維度的相似度來計算源代碼之間的相似度，其結(jié)果用數(shù)值表示。

1.2 代碼特征

將源代碼轉(zhuǎn)換成中間產(chǎn)物或者從源代碼中提取特征從而進行相似度檢測是十分常見的。該文將從多個維度來度量代碼的相似性，主要從代碼注釋、方法的型構(gòu)、代碼文本語句與結(jié)構(gòu)這些維度來進行特征提取。

1.2.1 注 釋

代碼注釋對于研究源代碼相似性具有重要的意義。隨著自然語言處理技術(shù)的不斷發(fā)展，將自然語言處理技術(shù)應(yīng)用到源代碼相似檢測中可以有效利用源代碼注釋中包含的語義信息，從而提高代碼相似檢測的準(zhǔn)確性。

對于源代碼注釋，該文使用LDA模型[15]來處理。LDA模型是用來預(yù)測文檔的主題概率分布的，該模型將文本的主題以概率分布的形式給出，可以用來進行文本主題聚類或者文本分類。文本使用LDA模型來提取注釋的主題特征。

1.2.2 型 構(gòu)

該文以方法級別的源代碼為研究對象，因此提出方法型構(gòu)的概念，型構(gòu)主要包括：方法名稱、方法返回值類型、參數(shù)類型、參數(shù)個數(shù)。由于參數(shù)類型和數(shù)量比順序更重要，因此該文忽略參數(shù)之間的順序。方法型構(gòu)主要特征如下：

(1)方法名稱；

(2)方法返回值類型；

(3)參數(shù)類型列表；

(4)參數(shù)個數(shù)。

1.2.3 代碼文本語句

代碼文本語句特征主要度量代碼行數(shù)與各類語句的數(shù)量。代碼文本語句主要特征如下：

(1)代碼行數(shù)；

(2)賦值語句數(shù)量；

(3)選擇語句數(shù)量；

(4)迭代語句數(shù)量；

(5)switch語句數(shù)量；

(6)case語句數(shù)量；

(7)返回語句數(shù)量；

(8)try語句數(shù)量；

(9)catch語句數(shù)量；

(10)變量聲明語句數(shù)量；

(11)表達式語句數(shù)量；

(12)變量類型數(shù)量。

1.2.4 代碼結(jié)構(gòu)

代碼結(jié)構(gòu)特征主要考慮if語句與循環(huán)語句之間相互嵌套的數(shù)量以及表達式語句、變量聲明語句、控制語句之間前后相繼關(guān)系的數(shù)量，代碼結(jié)構(gòu)主要特征如下：

(1)if語句嵌套循環(huán)語句數(shù)量；

(2)循環(huán)語句嵌套if語句數(shù)量；

(3)if語句嵌套if語句數(shù)量；

(4)循環(huán)語句嵌套循環(huán)語句數(shù)量；

(5)表達式語句→控制語句數(shù)量；

(6)表達式語句→變量聲明語句數(shù)量；

(7)變量聲明語句→表達式語句數(shù)量；

(8)變量聲明語句→控制語句數(shù)量；

(9)控制語句→表達式語句數(shù)量；

(10)控制語句→變量聲明語句數(shù)量。

其中“A→B”的含義為A語句后面緊接B語句。

2 特征提取

代碼文本本身的相似性度量，可以通過AST或者PDG技術(shù)分析代碼的結(jié)構(gòu)相似性。以往的研究在對源代碼進行預(yù)處理時都去除了源代碼注釋，而重點關(guān)注代碼本身，然而注釋對于研究源代碼相似具有重要意義，特別是在對源代碼語義相似檢測時更是如此。

文中特征主要從代碼注釋、方法的型構(gòu)、代碼文本語句與結(jié)構(gòu)等方面進行特征提取，基于多特征值來進行代碼相似性度量，這樣可以提高準(zhǔn)確度。圖1給出了代碼特征提取的流程。

圖1 代碼特征提取流程

流程主要包括以下步驟：

第1步：對源代碼進行預(yù)處理，提取注釋將源代碼分為注釋文本和代碼文本兩部分。

第2步：對注釋進行預(yù)處理后，使用gensim庫的LDA模型來提取注釋文本的主題特征。

第3步：對于代碼分別從型構(gòu)、代碼文本語句、代碼結(jié)構(gòu)三方面，構(gòu)建算法對代碼文本語句以及代碼的抽象語法樹進行處理從而提取特征。

2.1 預(yù)處理

優(yōu)雅的程序設(shè)計語言源代碼會有規(guī)范的注釋，特別是對于方法級別的源代碼而言，注釋能夠反映代碼的功能，能夠直接體現(xiàn)出源代碼的語義信息。然而，在早期的源代碼相似性檢測的研究中，學(xué)者往往把重點放在代碼文本本身，而忽略了注釋，在預(yù)處理的時候會去除所有的注釋，這樣做往往是因為自然語言語法語義的復(fù)雜性，但是這樣會丟失大量的語義信息，特別是對于代碼方法級別的注釋而言。

隨著自然語言處理技術(shù)的進一步發(fā)展，可以將自然語言處理技術(shù)應(yīng)用到源代碼相似性檢測的研究中，從注釋中獲取所蘊含的重要的源代碼語義信息。因此該文在進行預(yù)處理的時候需要將注釋提取出來而不是刪除。以Java源代碼為研究對象，預(yù)處理步驟如下：

(1)提取所有在符號“//”之后、“/* */”和“/* * */”之間的程序注釋內(nèi)容，將注釋與代碼文本分離，將提取注釋文本內(nèi)容存儲在commentText中；

(2)刪除“import”開頭的引包代碼；

(3)刪除源代碼中的空行；

(4)刪除每一行代碼中的第一個非空字符之前的所有空格和“Tab”鍵；

(5)將代碼存儲在codeText中。

2.2 注釋特征提取

使用python自然語言處理庫gensim的LDA(latent Dirichlet allocation)模型來提取注釋文本的主題特征。主要步驟如下：

算法1：注釋文本主題特征向量生成算法。

輸入：注釋文本commentText。

輸出：注釋文本對應(yīng)的主題特征向量。

①根據(jù)所有注釋文本commentText創(chuàng)建文本數(shù)組documents；

②去除停用詞“a, for, of, the, and, to, in”，將分詞后的結(jié)果存儲在texts數(shù)組中；

③去除texts數(shù)組中詞頻為1的詞；

④調(diào)用corpora.Dictionary(texts)函數(shù)創(chuàng)建字典對象dictionary；

⑤對texts中的每一個text調(diào)用dictionary.doc2bow(text)構(gòu)建詞庫對象corpus；

⑥根據(jù)字典對象dictionary和詞庫對象corpus調(diào)用models.ldamodel.LdaModel構(gòu)建注釋文本的LDA(latent Dirichlet allocation)模型lda；

⑦根據(jù)注釋文本輸出對應(yīng)的注釋主題特征向量。

2.3 型構(gòu)特征提取

型構(gòu)特征主要包含方法名稱、方法返回值類型、參數(shù)類型、參數(shù)個數(shù)。自定義CodeSignature類，創(chuàng)建CodeSignature對象來存儲代碼型構(gòu)的特征。

型構(gòu)特征提取算法如下：

算法2：型構(gòu)特征提取算法。

輸入：源代碼。

輸出：型構(gòu)特征對象codeSignature。

①創(chuàng)建codeSignature=(methodName, returnType, paramType)對象用于存儲型構(gòu)特征值；

②逐行掃描代碼提取第一個“(”之前的代碼存儲在methodSignature字符串中，將第一個“(”和“)”之間的代碼存儲在methodParam字符串中；

③過濾methodSignature字符串，去除“public”、“private”、“static”、“synchronized”等方法修飾符；

④將返回值類型和拆分后的方法名分別存儲在codeSignature對象的字符串?dāng)?shù)組屬性methodName和字符串屬性returnType中；

⑤從methodParam提取出一個或多個參數(shù)類型并存儲在codeSignature對象的字符串?dāng)?shù)組屬性paramType中；

⑥輸出codeSignature對象。

2.4 代碼文本結(jié)構(gòu)特征提取

對于代碼結(jié)構(gòu)特征，該文使用Eclipse JDT AST生成源代碼對應(yīng)的抽象語法樹，獲得方法對應(yīng)的節(jié)點MethodDeclaration類，通過解析MethodDeclaration類的屬性來提取特征。

創(chuàng)建特征統(tǒng)計數(shù)組CodeStructure來存儲代碼結(jié)構(gòu)特征。代碼結(jié)構(gòu)特征提取算法如下：

算法3：代碼結(jié)構(gòu)特征提取算法。

輸入：源代碼code。

輸出：代碼結(jié)構(gòu)特征統(tǒng)計數(shù)組codeStructure。

①創(chuàng)建代碼文本與結(jié)構(gòu)特征統(tǒng)計數(shù)組codeStructure[1..10]，初始值均為0；

②創(chuàng)建ASTParser對象parser，再通過調(diào)用parser.createASTs(code)方法創(chuàng)建抽象語法樹；

③遍歷ASTNode獲得methodDeclaration對象節(jié)點；

④通過methodDeclaration對象的方法體對象body，獲得IfStatement、ForStatement、ExpressionStatement等節(jié)點以及它們之間嵌套或者前后關(guān)系從而提取代碼結(jié)構(gòu)的特征值；

⑤將特征值賦值給代碼結(jié)構(gòu)特征統(tǒng)計數(shù)組codeStructure；

⑥輸出codeStructure，

2.5 代碼文本語句特征提取

代碼文本語句特征提取與代碼型構(gòu)特征提取類似，這里不再給出算法。

2.6 相似度計算模型

文中代碼相似度計算主要從代碼注釋、型構(gòu)、代碼文本語句以及結(jié)構(gòu)這些方面來考量。先分別計算代碼注釋、型構(gòu)、文本語句和結(jié)構(gòu)的相似度，再進行加權(quán)計算得出源代碼的最終相似度。計算公式如式(2)所示，最終源代碼的相似度為代碼注釋、型構(gòu)、文本與結(jié)構(gòu)相似度的線性組合，其中的參數(shù)α、β、γ、δ均設(shè)定為0.25。

S源代碼=S注釋×α+S型構(gòu)×β+S文本語句×γ+

S結(jié)構(gòu)×δ

(2)

3 實 驗

為了更好地驗證基于多特征值的源代碼相似性檢測技術(shù)的有效性，選取了12種算法以及每個算法對應(yīng)的9種相似代碼作為實驗數(shù)據(jù)，并通過對比實驗來驗證基于多特征值的源代碼相似性檢測技術(shù)的有效性。

3.1 實驗步驟

實驗主要分為三個步驟：構(gòu)建源代碼數(shù)據(jù)集、特征提取、相似度計算。實驗流程如圖2所示。

圖2 實驗流程

3.2 構(gòu)造源代碼數(shù)據(jù)集

由于沒有開源的相似代碼的分析數(shù)據(jù)包，該文選取帶有注釋的12個程序作為實驗基礎(chǔ)源代碼。這些程序包括選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序、桶排序、KMP算法、最小生成樹算法、最短路徑算法、關(guān)鍵路徑算法、貪心算法。為了構(gòu)建足夠的實驗數(shù)據(jù)，對每個算法分別使用文獻[11]中介紹的除去完整拷貝剩下的9種抄襲變換來手動構(gòu)造相似源代碼，并分為多組來進行實驗。每組包含以下數(shù)據(jù)集：基礎(chǔ)源代碼T0以及9個修改后的相似代碼T1，T2，…，T9。修改主要包括：

(1)修改注釋；

(2)重新排版；

(3)重命名標(biāo)識符；

(4)更改代碼塊順序；

(5)更改代碼塊內(nèi)語句順序；

(6)修改表達式操作符或操作順序；

(7)修改數(shù)據(jù)類型；

(8)增加冗余語句或者變量；

(9)替換控制結(jié)構(gòu)為等價的控制結(jié)構(gòu)。

9個修改后的源代碼分別對應(yīng)T1-T9。每一組數(shù)據(jù)集中的T0-T1、T0-T2、T0-T3、T0-T4、T0-T5、T0-T6、T0-T7、T0-T8、T0-T9源代碼對均為相似源代碼。

3.3 特征提取與相似度計算

該步驟分別對源代碼按照代碼注釋、型構(gòu)、代碼文本語句與結(jié)構(gòu)進行特征提取。然后分別計算注釋、型構(gòu)、代碼文本語句與結(jié)構(gòu)的相似度。

3.3.1 注釋相似度計算

首先，將源代碼的注釋文本轉(zhuǎn)化為與之對應(yīng)的主題特征向量，然后，計算不同源代碼注釋的主題特征相似度。以插入排序與選擇排序的注釋生成的主題特征向量為例，如果取主題數(shù)為2，則二者的主題特征向量分別為(0.927 850 2，0.072 149 83)和(0.976 045 8，0.023 954 21)，將這兩個向量的余弦相似度作為對應(yīng)的注釋之間相似度S注釋。

3.3.2 型構(gòu)相似度計算

該文用SigVector表示方法的型構(gòu)，SigVector定義為SigVector=(X1,X2,X3,X4)，其中X1為兩個型構(gòu)的方法名中相同單詞數(shù)與每個型構(gòu)總單詞數(shù)之比；X2為返回類型是否相同，相同為1，不相同為0；X3為兩個型構(gòu)中參數(shù)類型相同數(shù)與每個型構(gòu)總參數(shù)數(shù)量之比；X4為參數(shù)數(shù)量是否相同，相同為1，不相同為0。型構(gòu)相似度計算如式(3)所示。

(3)

3.3.3 代碼文本語句與結(jié)構(gòu)相似度計算

對于代碼文本語句與結(jié)構(gòu)，以特征屬性值組成的向量之間的余弦相似度作為代碼文本語句與結(jié)構(gòu)之間的相似度S文本語句、S結(jié)構(gòu)。

以插入排序與選擇排序代碼為例，它們的代碼文本語句特征數(shù)組、代碼結(jié)構(gòu)特征數(shù)組分別如表1、表2所示。

表1 代碼文本語句特征數(shù)組

表2 代碼結(jié)構(gòu)特征數(shù)組

3.4 相似度計算

在分別得到代碼注釋、型構(gòu)、代碼文本語句與結(jié)構(gòu)的相似度之后，再通過相似度計算模型S源代碼=S注釋×00.25+S型構(gòu)×0.25+S文本語句×.25+S結(jié)構(gòu)×0.25計算出源代碼之間的相似度。

4 實驗結(jié)果與分析

該文使用Moss[16]抄襲檢測系統(tǒng)來進行實驗對比，該系統(tǒng)是一個權(quán)威的代碼抄襲檢測系統(tǒng)，能夠檢測代碼相似性，它采用串匹配算法通過將代碼作為字符串放入哈希表再從表中選取一個子集進行比較，以此進行相似度度量。分別對12組代碼程序進行實驗，并以12組實驗數(shù)據(jù)的相似度檢測結(jié)果的平均值作為最終結(jié)果進行比較，表3和圖3給出了平均相似度檢測結(jié)果。

表3 平均相似度檢測結(jié)果

圖3 平均相似度檢測結(jié)果

通過實驗對比可以看出，由于全面考慮了代碼的多種特征，該文采用的方法能更準(zhǔn)確地檢測出多種抄襲手段修改后的相似代碼。對于Moss方法檢測結(jié)果較差的修改類型，如修改數(shù)據(jù)類型、替換控制結(jié)構(gòu)為等價的控制結(jié)構(gòu)等，都能檢測到較高的相似度。

5 結(jié)束語

提出的基于多特征值的源代碼相似性檢測技術(shù)，將代碼的相似問題轉(zhuǎn)化為特征向量相似的問題，并且考慮了代碼多個維度的特征，特別是考慮了源代碼注釋這一維度，這樣能夠有效地提取出代碼的語義信息，從而能夠提高源代碼相似性檢測的準(zhǔn)確性。

然而，文中實驗只是在一個很小的數(shù)據(jù)集上對基于多特征值的源代碼相似性檢測技術(shù)進行了驗證。該源代碼相似性檢測技術(shù)還需要在更大的數(shù)據(jù)集上做更進一步的驗證，通過擴大數(shù)據(jù)集，并使用機器學(xué)習(xí)的方法來提高實驗的效率。另外，相似度計算采用了一個線性組合的方法，而且權(quán)重都取0.25，還可以進一步研究并調(diào)整各維度的權(quán)重從而優(yōu)化檢測結(jié)果。