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

展佳俊，趙逢禹，艾 均

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

0 引 言

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

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

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

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

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

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

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

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

1 相關概念

1.1 代碼相似定義

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

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

S(P,X)=

(1)

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

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

1.2 代碼特征

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

1.2.1 注 釋

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

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

1.2.2 型 構

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

(1)方法名稱；

(2)方法返回值類型；

(3)參數類型列表；

(4)參數個數。

1.2.3 代碼文本語句

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

(1)代碼行數；

(2)賦值語句數量；

(3)選擇語句數量；

(4)迭代語句數量；

(5)switch語句數量；

(6)case語句數量；

(7)返回語句數量；

(8)try語句數量；

(9)catch語句數量；

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

(11)表達式語句數量；

(12)變量類型數量。

1.2.4 代碼結構

代碼結構特征主要考慮if語句與循環語句之間相互嵌套的數量以及表達式語句、變量聲明語句、控制語句之間前后相繼關系的數量，代碼結構主要特征如下：

(1)if語句嵌套循環語句數量；

(2)循環語句嵌套if語句數量；

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

(4)循環語句嵌套循環語句數量；

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

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

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

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

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

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

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

2 特征提取

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

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

圖1 代碼特征提取流程

流程主要包括以下步驟：

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

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

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

2.1 預處理

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

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

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

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

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

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

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

2.2 注釋特征提取

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

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

輸入：注釋文本commentText。

輸出：注釋文本對應的主題特征向量。

①根據所有注釋文本commentText創建文本數組documents；

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

③去除texts數組中詞頻為1的詞；

④調用corpora.Dictionary(texts)函數創建字典對象dictionary；

⑤對texts中的每一個text調用dictionary.doc2bow(text)構建詞庫對象corpus；

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

⑦根據注釋文本輸出對應的注釋主題特征向量。

2.3 型構特征提取

型構特征主要包含方法名稱、方法返回值類型、參數類型、參數個數。自定義CodeSignature類，創建CodeSignature對象來存儲代碼型構的特征。

型構特征提取算法如下：

算法2：型構特征提取算法。

輸入：源代碼。

輸出：型構特征對象codeSignature。

①創建codeSignature=(methodName, returnType, paramType)對象用于存儲型構特征值；

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

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

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

⑤從methodParam提取出一個或多個參數類型并存儲在codeSignature對象的字符串數組屬性paramType中；

⑥輸出codeSignature對象。

2.4 代碼文本結構特征提取

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

創建特征統計數組CodeStructure來存儲代碼結構特征。代碼結構特征提取算法如下：

算法3：代碼結構特征提取算法。

輸入：源代碼code。

輸出：代碼結構特征統計數組codeStructure。

①創建代碼文本與結構特征統計數組codeStructure[1..10]，初始值均為0；

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

③遍歷ASTNode獲得methodDeclaration對象節點；

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

⑤將特征值賦值給代碼結構特征統計數組codeStructure；

⑥輸出codeStructure，

2.5 代碼文本語句特征提取

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

2.6 相似度計算模型

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

S源代碼=S注釋×α+S型構×β+S文本語句×γ+

S結構×δ

(2)

3 實 驗

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

3.1 實驗步驟

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

圖2 實驗流程

3.2 構造源代碼數據集

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

(1)修改注釋；

(2)重新排版；

(3)重命名標識符；

(4)更改代碼塊順序；

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

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

(7)修改數據類型；

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

(9)替換控制結構為等價的控制結構。

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

3.3 特征提取與相似度計算

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

3.3.1 注釋相似度計算

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

3.3.2 型構相似度計算

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

(3)

3.3.3 代碼文本語句與結構相似度計算

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

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

表1 代碼文本語句特征數組

表2 代碼結構特征數組

3.4 相似度計算

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

4 實驗結果與分析

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

表3 平均相似度檢測結果

圖3 平均相似度檢測結果

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

5 結束語

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

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