劉復(fù)星　魏金津　任女爾

摘要：在實(shí)際軟件項(xiàng)目中，復(fù)制粘貼式的代碼復(fù)用或者解決相似問題的模式化思維會(huì)造成軟件源代碼重復(fù)出現(xiàn)相同或相似的代碼片段。代碼克隆檢測分析作為衡量代碼復(fù)用的一種有效方式，在軟件開發(fā)、維護(hù)以及質(zhì)量保證中發(fā)揮著重要作用。提出以深度學(xué)習(xí)為基礎(chǔ)的代碼克隆檢測技術(shù)能夠很好地補(bǔ)充常用檢測辦法無法檢測到的場景，如相同含義不同寫法的代碼段；基于sonar做插件式研發(fā)，具有重要的工程意義與實(shí)踐指導(dǎo)作用。

關(guān)鍵詞：代碼克??；深度學(xué)習(xí)；代碼質(zhì)量管控

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）18-0178-02

1 引言

代碼克隆是指在程序設(shè)計(jì)中表示一段源代碼在一個(gè)程序，或者一個(gè)團(tuán)體所維護(hù)的不同程序中重復(fù)出現(xiàn)，是不希望出現(xiàn)的現(xiàn)象【5】。在實(shí)際項(xiàng)目中，復(fù)制粘貼式的代碼復(fù)用或者解決相似問題的模式化思維會(huì)造成軟件源代碼重復(fù)出現(xiàn)相同或相似的代碼片段。為避免巧合，只有超過一定數(shù)量的代碼相似才能判定為代碼克隆。不好的代碼復(fù)用方式會(huì)對(duì)整個(gè)軟件系統(tǒng)的開發(fā)和維護(hù)帶來很多不利因素，因此對(duì)于代碼復(fù)用的分析顯得越來越重要。代碼克隆分析作為衡量代碼復(fù)用的一種有效方式，在軟件開發(fā)、維護(hù)以及質(zhì)量保證中發(fā)揮著重要作用。

軟件行業(yè)內(nèi)常將Sonar作為技術(shù)債務(wù)管控的主流工具，Sonar插件式模式，方便自身被其他平臺(tái)所引入，且有利于擴(kuò)展第三方插件。通過不同的插件對(duì)檢測結(jié)果進(jìn)行再加工處理，量化代碼質(zhì)量，方便對(duì)不同規(guī)模和種類的項(xiàng)目進(jìn)行代碼質(zhì)量管理[1]。

自動(dòng)檢測代碼重復(fù)的過程叫作克隆檢測，實(shí)現(xiàn)基于Sonar的代碼克隆自動(dòng)檢測技術(shù)，從根源上解決軟件代碼質(zhì)量問題帶來的風(fēng)險(xiǎn)并提供解決方案，指導(dǎo)軟件項(xiàng)目研發(fā)質(zhì)量改進(jìn)。

基于深度學(xué)習(xí)算法研發(fā)代碼克隆檢測技術(shù)，并以插件形式集成進(jìn)Sonar，用來檢測項(xiàng)目代碼中高相似部分從而對(duì)代碼進(jìn)行重構(gòu)，減少代碼量和重復(fù)功能點(diǎn)，達(dá)到節(jié)約成本的目的。

2 代碼克隆分類

一型克?。喝绻懦绦虼a在換行、空白、制表符等格式上的區(qū)別，以及注釋語句等的區(qū)別以后，兩段代碼完全相同。

二型克?。涸谝恍涂寺〉幕A(chǔ)上， 如果在兩段代碼之間的常數(shù)值以及變量名、函數(shù)名等標(biāo)識(shí)符不同， 其余部分相同，那么這就是參變克隆。

三型克?。涸诙涂寺』A(chǔ)之上，如果兩段代碼之間存在個(gè)別行不同，比如在一段代碼中間新增兩條語句，或是刪除兩條語句， 那么它們是斷層克隆。

四型克?。喝绻麅啥未a在結(jié)構(gòu)，形式上不同，但是在邏輯功能上完全相同，即給定相同的輸入，總是能得到相同的輸出，那么它們就形成了一對(duì)功能克隆?！?】

3 代碼克隆檢測技術(shù)

基于純文本：基于 Text 的克隆檢測方法是通過直接比較源代碼文本，使用字符串匹配等算法來檢測克隆代碼。因?yàn)闆]有考慮到代碼的形式和結(jié)構(gòu)等信息，因此主要檢測Type1型克隆，而對(duì)其余類型克隆的支持較弱。

基于Token：基于Token的克隆檢測方法是通過對(duì)源代碼進(jìn)行詞法分析生成源代碼的Token序列，然后通過尋找Token序列中相似的子序列來檢測克隆代碼。因其對(duì)源代碼進(jìn)行了詞法分析，所以可以較好地支持Type 2克隆的檢測。但由于缺乏語法和語義分析，更高級(jí)的Type3，Type4型克隆無法較好地支持。

基于語法（AST）：AST，即Abstract Syntax Tree（抽象語法樹）【6】，這種克隆檢測方法是將源代碼表示為如抽象語法樹、代碼解析樹等樹的形式，然后通過樹匹配算法從中尋找相似的子樹來檢測克隆代碼。因其對(duì)源代碼進(jìn)行了語法分析，所以提高了克隆代碼檢測的準(zhǔn)確率，可以較好地支持Type3克隆的檢測。但是由于樹匹配算法的時(shí)間復(fù)雜度較高，這類算法的檢測速度會(huì)低于基于純文本和Token的方法。

基于深度學(xué)習(xí)（deep learning）：（1）使用深度學(xué)習(xí)中遞歸神經(jīng)網(wǎng)絡(luò)，通過訓(xùn)練語言模型，將token表示成向量，構(gòu)造一棵樹型結(jié)構(gòu)（橄欖樹），自定義規(guī)則列表，對(duì)樹結(jié)構(gòu)壓縮到根結(jié)點(diǎn)， 最后生成一個(gè)向量， 比較向量研究克隆。（2）從已知的克隆和非克隆方法級(jí)代碼中提取token，用來訓(xùn)練分類器，然后使用分類器檢測給定代碼庫中的克隆。通過深度學(xué)習(xí)，可以有效地克隆代碼中相似的token的使用模式，從而訓(xùn)練數(shù)據(jù)以檢測測試數(shù)據(jù)中的克隆。【2】

4 基于深度學(xué)習(xí)的代碼克隆檢測技術(shù)

檢測粒度到方法級(jí)別，認(rèn)為方法是功能實(shí)現(xiàn)的主體，檢測兩個(gè)方法之間是否存在克隆，總體實(shí)現(xiàn)過程如下：

4.1 生成抽象語法樹

1）代碼預(yù)處理：使用ANTLR，將源代碼轉(zhuǎn)換為AST，過程中需要對(duì)一部分結(jié)點(diǎn)（如與克隆檢測無關(guān)的編譯類型的結(jié)點(diǎn)）做過濾。

2）遍歷AST并過濾無關(guān)節(jié)點(diǎn)，進(jìn)行優(yōu)化：生成的AST中存在一部分內(nèi)部結(jié)點(diǎn)與編譯工作關(guān)系比較大而對(duì)克隆的檢測工作卻可能造成誤差影響。通過多次實(shí)驗(yàn)和觀察AST結(jié)構(gòu)，發(fā)現(xiàn)這種對(duì)克隆檢測工作無用的節(jié)點(diǎn)共有37種。在這一步將這些節(jié)點(diǎn)進(jìn)行了過濾。

3）生成語料庫：由AST深度遍歷得到的內(nèi)部節(jié)點(diǎn)序列，把每一個(gè)方法對(duì)應(yīng)的節(jié)點(diǎn)序列， 類比為一句話或是一段文字， 用于后續(xù)skip-gram模型的語料庫輸入，這個(gè)語料庫需要足夠大，能夠涵蓋所有的方法節(jié)點(diǎn)。實(shí)驗(yàn)中， 使用的是jdk作為生出語料庫的輸入， 生出的語料庫總共90MB， 涵蓋了53000個(gè)方法（c_corpus.txt）. 這個(gè)過程只需要進(jìn)行一次。

4.2 獲取詞向量

上一個(gè)過程中生成的語料庫（c_corpus.txt）， 用于作為skip-gram模型的輸入。

在實(shí)驗(yàn)中發(fā)現(xiàn)，將隱藏層神經(jīng)元個(gè)數(shù)設(shè)置為128， 迭代次數(shù)設(shè)置在100，000次時(shí)效果最好。這樣通過使用skip-gram模型， 將147種與方法相關(guān)的節(jié)點(diǎn)， 一一對(duì)應(yīng)成為多維向量， 并最終生成一個(gè)字典. 然后將上一步得到的檢測對(duì)象的規(guī)則節(jié)點(diǎn)序列， 依據(jù)這個(gè)字典中規(guī)則節(jié)點(diǎn)和向量的一一映射關(guān)系， 轉(zhuǎn)換為詞向量序列。

由于這些向量攜帶語義信息，因此還可以為type4型克隆的檢測提供新思路。比如代碼中的int， double， float等表示數(shù)值類型的token，它們?cè)贏NTLR轉(zhuǎn)為對(duì)應(yīng)的規(guī)則節(jié)點(diǎn)，這些節(jié)點(diǎn)最終轉(zhuǎn)換成的詞向量，向量之間的距離相近。另外類似的還有for， while等。

經(jīng)過此步驟，將檢測對(duì)象中的每一個(gè)方法都轉(zhuǎn)換為對(duì)應(yīng)的詞向量序列，這樣就將代碼的研究轉(zhuǎn)換為研究向量間關(guān)系。

4.3 獲取句向量

經(jīng)過上一個(gè)步驟，將檢測對(duì)象中的每一個(gè)方法都轉(zhuǎn)換為對(duì)應(yīng)的詞向量序列。但是每個(gè)方法的代碼行長度都不盡相同， 因此對(duì)應(yīng)的詞向量序列長度也不同。為了能夠?qū)崿F(xiàn)比較任意兩個(gè)方法相似度的功能，使用了scikit-learn中的主成分分析PCA， 目的是將詞向量序列壓縮為一個(gè)向量， 這個(gè)向量稱之為方法向量， 這樣就解決了詞向量序列長度不同的問題。

通過使用PCA的數(shù)據(jù)降維，將每一個(gè)方法對(duì)應(yīng)的詞向量序列轉(zhuǎn)換為一個(gè)方法向量， 且這個(gè)方法向量通過解壓得到的詞向量序列與壓縮之前類似，因此能夠很好地代表這個(gè)詞向量序列。

通過研究向量之間的關(guān)系與代碼之間的克隆關(guān)系。

如果兩個(gè)方法是type1， type2型克隆， 那么這兩個(gè)方法的AST節(jié)點(diǎn)類型和AST結(jié)構(gòu)是一樣的， 所以形成的兩個(gè)詞向量序列也是一樣的，最終計(jì)算出的向量距離是0。

如果兩個(gè)方法是type3型克隆， 它們的AST節(jié)點(diǎn)類型和結(jié)構(gòu)整體相似， 它們最后的詞向量序列，也都是類似的。因此在計(jì)算它們的距離時(shí)， 最終會(huì)得到一個(gè)數(shù)值比較小的向量距離。通過大量研究和實(shí)驗(yàn)，把判斷type3型克隆的向量距離閾值設(shè)置為3e-5，即如果兩個(gè)方法對(duì)應(yīng)的句向量距離大于0且小于這個(gè)閾值，就判斷它就是type3型的克隆。

名詞解釋：

1）抽象語法樹（AST）：抽象語法樹（縮寫為AST），或者語法樹（syntax tree），是源代碼的抽象語法結(jié)構(gòu)的樹狀表現(xiàn)形式，這里特指編程語言的源代碼。樹上的每個(gè)節(jié)點(diǎn)都表示源代碼中的一種結(jié)構(gòu)。之所以說語法是“抽象”的，是因?yàn)檫@里的語法并不會(huì)表示出真實(shí)語法中出現(xiàn)的每個(gè)細(xì)節(jié)。

2）skip-gram：skip-gram模型是word2vec中兩個(gè)實(shí)現(xiàn)word embedding獲取詞向量的模型之一， 本質(zhì)上是只有一個(gè)隱藏層的神經(jīng)網(wǎng)絡(luò)， 這個(gè)隱藏層的神經(jīng)元個(gè)數(shù)通常會(huì)很大，將代碼中的每個(gè)方法看作是一段文字， 將每一個(gè)內(nèi)部節(jié)點(diǎn)看作是一個(gè)單詞， 這樣通過skip-gram模型. 可以將每一個(gè)節(jié)點(diǎn)轉(zhuǎn)換為一個(gè)向量。

3）PCA：使用了scikit-learn中的主成分分析PCA，它是機(jī)器學(xué)習(xí)中常用的數(shù)據(jù)降維算法之一，本質(zhì)上是一種數(shù)學(xué)統(tǒng)計(jì)方法。使用PCA可以很好地解決因變量太多而復(fù)雜性、計(jì)算量增大的弊端。在這里使用PCA的目的是將詞向量序列壓縮為一個(gè)向量。

5 檢測結(jié)果

檢測對(duì)象：jEdit，文件數(shù)：597，方法數(shù)：8041。

NiCad（當(dāng)下一款比較流行的克隆檢測工具）共檢測出447個(gè)克隆對(duì)， 預(yù)處理和檢測總共用時(shí)64.9秒。

基于深度學(xué)習(xí)方法：共檢測出631個(gè)克隆對(duì)，預(yù)處理和檢測總共用時(shí)423.9秒。

檢測對(duì)象：Future30，文件數(shù)：427，方法數(shù)： 2664。

NiCad共檢測出171個(gè)克隆對(duì)， 預(yù)處理和檢測總共用時(shí)14.7秒。

基于深度學(xué)習(xí)方法：共檢測出331個(gè)克隆對(duì)，預(yù)處理和檢測總共用時(shí)58.7秒。

結(jié)果分析：NiCad是基于文本實(shí)現(xiàn)的克隆檢測工具，這種方式在檢測速度上比較有優(yōu)勢，但是由于沒有對(duì)代碼進(jìn)行詞法和語法分析，因此主要檢測Type 1，2型克隆， 對(duì)于更高級(jí)的3型克隆檢測效果很一般。基于深度學(xué)習(xí)方法首先把源碼轉(zhuǎn)換為AST， 這個(gè)轉(zhuǎn)換過程相對(duì)耗時(shí)， 但是能檢測出更多類型和數(shù)目的克隆對(duì)?！?】

6 優(yōu)勢

基于文本或基于token的檢測工具主要只能檢測出1型和2型克隆，方法可以很好地檢測1，2型和3型克?。?，2型克隆的準(zhǔn)確率近似百分之百），并且對(duì)4型克隆的發(fā)現(xiàn)提供了新的思路。

傳統(tǒng)的基于AST的方式除了能檢測出1，2型克隆， 也能很好檢測出3型克隆， 但是它們往往使用時(shí)間復(fù)雜度比較大的子樹匹配算法，進(jìn)而判斷代碼克隆，這種算法時(shí)間開銷往往比較大。與傳統(tǒng)的基于AST的克隆檢測方法相比，方法雖然也把源碼轉(zhuǎn)換為AST，但是并不直接比較兩個(gè)AST的相似度，而是通過遍歷AST生成結(jié)點(diǎn)的序列， 隨后通過對(duì)向量進(jìn)行相關(guān)數(shù)值計(jì)算，來研究兩段代碼的相似度，這樣就避免了使用時(shí)間開銷比較大的子樹匹配算法，這種將AST轉(zhuǎn)換為向量的方式， 比傳統(tǒng)方法在時(shí)間效率上得到了大大提升，檢測效果也比較好。

基于機(jī)器學(xué)習(xí)的檢測工具，如CCLearner，從已知的克隆和非克隆方法級(jí)代碼中提取token，用來訓(xùn)練分類器，然后使用分類器檢測給定代碼庫中的克隆。這種方法需要有標(biāo)注的數(shù)據(jù)，即數(shù)據(jù)集需要知道哪些方法是克隆，哪些不是克隆。方法不需要標(biāo)注數(shù)據(jù)。而且使用skip-gram模型得到的向量字典只需生成一次，依照這個(gè)字典可以將方法轉(zhuǎn)換為一個(gè)向量。

7 總結(jié)

基于深度學(xué)習(xí)開發(fā)的代碼克隆檢測技術(shù)，可以作為插件集成進(jìn)Sonar，以比較高的效率掃描項(xiàng)目的克隆代碼，開發(fā)者根據(jù)掃描結(jié)果對(duì)項(xiàng)目代碼重復(fù)部分進(jìn)行優(yōu)化和重構(gòu)，可以提高項(xiàng)目質(zhì)量節(jié)約項(xiàng)目成本。

參考文獻(xiàn)

[1] 柳萌宇，鐘浩，于海波.基于變更相似性的跨語言克隆檢測方法[J].計(jì)算機(jī)與現(xiàn)代化，2016（4）.

[2] 林嬋，李俊杰，饒飛，等.基于索引的分布式代碼克隆檢測[J].信息安全研究，2016（3）.

[3] 甘水滔，秦曉軍，陳左寧，等.一種基于特征矩陣的軟件脆弱性代碼克隆檢測方法[J].軟件學(xué)報(bào)，2015（2）.

[4] 郭穎，陳峰宏，周明輝.大規(guī)模代碼克隆的檢測方法[J].計(jì)算機(jī)科學(xué)與探索，2013（12）.

[5] 王國莉，白昊昱.程序設(shè)計(jì)語言中代碼克隆的研究[J].計(jì)算機(jī)與網(wǎng)絡(luò)，2013（3）.