展佳俊，趙逢禹，艾 均

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

0 引 言

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

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

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

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

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

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

以上研究分別從代碼token、代碼的抽象語(yǔ)法樹(shù)、代碼的程序依賴(lài)圖以及代碼注釋等維度來(lái)進(jìn)行源代碼相似性檢測(cè)研究，他們的方法分別從不同的維度對(duì)特定類(lèi)型的代碼進(jìn)行相似性分析。

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

1 相關(guān)概念

1.1 代碼相似定義

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

Yamamoto等[14]給出了兩個(gè)軟件系統(tǒng)的相似度定義。對(duì)于兩個(gè)軟件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表示所有匹配對(duì)(Pi,Xj)的集合。根據(jù)式(1)可看出，相似性S為一個(gè)比值，由Rs中的元素個(gè)數(shù)比上P、X中元素個(gè)數(shù)之和。

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

1.2 代碼特征

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

1.2.1 注 釋

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

對(duì)于源代碼注釋?zhuān)撐氖褂肔DA模型[15]來(lái)處理。LDA模型是用來(lái)預(yù)測(cè)文檔的主題概率分布的，該模型將文本的主題以概率分布的形式給出，可以用來(lái)進(jìn)行文本主題聚類(lèi)或者文本分類(lèi)。文本使用LDA模型來(lái)提取注釋的主題特征。

1.2.2 型 構(gòu)

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

(1)方法名稱(chēng)；

(2)方法返回值類(lèi)型；

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

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

1.2.3 代碼文本語(yǔ)句

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

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

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

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

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

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

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

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

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

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

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

(11)表達(dá)式語(yǔ)句數(shù)量；

(12)變量類(lèi)型數(shù)量。

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

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

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

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

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

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

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

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

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

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

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

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

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

2 特征提取

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

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

圖1 代碼特征提取流程

流程主要包括以下步驟：

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

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

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

2.1 預(yù)處理

優(yōu)雅的程序設(shè)計(jì)語(yǔ)言源代碼會(huì)有規(guī)范的注釋?zhuān)貏e是對(duì)于方法級(jí)別的源代碼而言，注釋能夠反映代碼的功能，能夠直接體現(xiàn)出源代碼的語(yǔ)義信息。然而，在早期的源代碼相似性檢測(cè)的研究中，學(xué)者往往把重點(diǎn)放在代碼文本本身，而忽略了注釋?zhuān)陬A(yù)處理的時(shí)候會(huì)去除所有的注釋?zhuān)@樣做往往是因?yàn)樽匀徽Z(yǔ)言語(yǔ)法語(yǔ)義的復(fù)雜性，但是這樣會(huì)丟失大量的語(yǔ)義信息，特別是對(duì)于代碼方法級(jí)別的注釋而言。

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

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

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

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

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

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

2.2 注釋特征提取

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

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

輸入：注釋文本commentText。

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

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

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

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

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

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

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

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

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

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

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

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

輸入：源代碼。

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

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

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

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

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

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

⑥輸出codeSignature對(duì)象。

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

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

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

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

輸入：源代碼code。

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

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

②創(chuàng)建ASTParser對(duì)象parser，再通過(guò)調(diào)用parser.createASTs(code)方法創(chuàng)建抽象語(yǔ)法樹(shù)；

③遍歷ASTNode獲得methodDeclaration對(duì)象節(jié)點(diǎn)；

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

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

⑥輸出codeStructure，

2.5 代碼文本語(yǔ)句特征提取

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

2.6 相似度計(jì)算模型

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

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

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

(2)

3 實(shí) 驗(yàn)

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

3.1 實(shí)驗(yàn)步驟

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

圖2 實(shí)驗(yàn)流程

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

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

(1)修改注釋?zhuān)?/p>

(2)重新排版；

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

(4)更改代碼塊順序；

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

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

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

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

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

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

3.3 特征提取與相似度計(jì)算

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

3.3.1 注釋相似度計(jì)算

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

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

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

(3)

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

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

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

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

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

3.4 相似度計(jì)算

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

5 結(jié)束語(yǔ)

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

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