基于圖像相似度檢測(cè)代碼克隆

王亞芳 劉東升 侯敏

摘 要：目前在代碼克隆檢測(cè)領(lǐng)域，學(xué)者們主要從文本、詞匯、語法和語義四種角度展開研究，然而長(zhǎng)期以來代碼克隆檢測(cè)效果并未取得新的突破。針對(duì)這一問題，從圖像處理角度提出了一種基于圖像相似度的新型代碼克隆檢測(cè)（CCIS）方法。首先對(duì)源代碼進(jìn)行移除注釋、空白符等操作，以獲取“干凈”的函數(shù)片段，并將函數(shù)中的標(biāo)識(shí)符、關(guān)鍵字等進(jìn)行高亮處理;然后將處理好的源代碼轉(zhuǎn)換為圖像，并對(duì)圖像進(jìn)行規(guī)范化處理;最后使用Jaccard距離和感知哈希算法進(jìn)行檢測(cè)，得到代碼克隆信息。為了驗(yàn)證實(shí)驗(yàn)的有效性，使用6款開源軟件構(gòu)建評(píng)價(jià)數(shù)據(jù)集進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，CCIS方法能夠檢測(cè)出100%的類型一代碼克隆、88%的類型二代碼克隆與60%的類型三代碼克隆，因此CCIS方法可以很好地進(jìn)行代碼克隆檢測(cè)。

關(guān)鍵詞：代碼克隆;克隆檢測(cè);Jaccard距離;感知哈希算法;語法高亮

Abstract： At present， scholars mainly focus on four perspectives of text， vocabulary， grammar and semantics in the field of clone code detection. However， few breakthroughs have been made in the effect of clone code detection for a long time. In view of this problem， a new method called Clone Code detection based on Image Similarity （CCIS） was proposed. Firstly， the source code was preprocessed by removing comments， white space， etc.， from which a “clean” function fragment was able to be obtained， and the identifiers， keywords， etc. in the function were highlighted. Then the processed source code was converted into images and these images were normalized. Finally， Jaccard distance and perceptual Hash algorithm were used for detection， obtaining the clone code information from these images. In order to verify the validity of this method， six open source softwares were used to constitute the evaluation dataset for testing. The experimental results show that CCIS method can detect 100% type-1 clone code， 88% type-2 clone code and 60% type-3 clone code， which proves the good effect of CCIS method on clone code detection.

Key words： clone code; clone detection; Jaccard distance; perceptual Hash algorithm; syntax highlighting

0 引言

在軟件開發(fā)與維護(hù)過程中，開發(fā)人員經(jīng)常使用“復(fù)制—粘貼”或者使用開發(fā)框架的開發(fā)方式，使得軟件系統(tǒng)中出現(xiàn)大量的代碼克隆。代碼克隆是軟件工程領(lǐng)域的重要研究?jī)?nèi)容，具體體現(xiàn)在軟件維護(hù)、軟件演化、軟件質(zhì)量、軟件復(fù)用及軟件授權(quán)、反剽竊等眾多領(lǐng)域。經(jīng)實(shí)證研究發(fā)現(xiàn)[1-3]，代碼克隆廣泛存在于各項(xiàng)開源與閉源代碼中，并且占據(jù)了相當(dāng)比例，因此有必要檢測(cè)代碼克隆并對(duì)其進(jìn)行良好的維護(hù)與管理。針對(duì)這一問題，學(xué)術(shù)界已經(jīng)提出許多種代碼克隆檢測(cè)技術(shù)，然而所有的方法都需要將源代碼按照各自制定的規(guī)則轉(zhuǎn)換為Token、抽象語法樹或者程序依賴圖等，中間過程復(fù)雜，并沒有對(duì)源代碼規(guī)范化的統(tǒng)一標(biāo)準(zhǔn)，為此本文提出了一種基于圖像相似度代碼克隆檢測(cè)（Code Clone detection based on Image Similarity， CCIS）方法。在開發(fā)過程中，程序員在集成開發(fā)環(huán)境（Integrated Development Environment， IDE）中查看源代碼時(shí)，首先看到的就是代碼的可視圖像，開發(fā)人員手動(dòng)查找克隆時(shí)是通過粗略掃描代碼的形狀與布局確定視覺上的相似代碼片段，進(jìn)而對(duì)這些視覺上的相似文本進(jìn)行更細(xì)粒度的檢查，并確定是否為真正的克隆代碼。本文正是遵循這種使用源代碼圖像之間在視覺上相似性的直覺來尋找代碼克隆，通過將源代碼片段表示為圖像，檢測(cè)圖像之間的相似度確定代碼克隆。本文檢測(cè)方法與傳統(tǒng)檢測(cè)方法相比，提出了一種基于圖像相似度的代碼克隆檢測(cè)方法，為代碼克隆分析研究在源代碼的表征方式上提供了全新的視角。

1 相關(guān)工作

從20多年前學(xué)者們就開始研究代碼克隆[4]，在該領(lǐng)域中，目前被研究者廣泛認(rèn)可的代碼克隆分類標(biāo)準(zhǔn)是由Bellon等[5]依據(jù)代碼克隆程度不同提出的四分類標(biāo)準(zhǔn)：類型一是指除去空格與注釋完全相同的代碼對(duì);類型二是指除去類型名、標(biāo)識(shí)符以及常量外都相同的代碼對(duì);類型三是指部分語句增刪改或標(biāo)識(shí)符、類型有所替換但句法結(jié)構(gòu)基本相同的代碼對(duì);類型四是指語義相似但是句法結(jié)構(gòu)不同的代碼對(duì)。

至今學(xué)術(shù)界已有一些優(yōu)秀的代碼克隆檢測(cè)方法[6-13]，主要是以基于文本、詞匯、語法以及語義四種表征方式進(jìn)行檢測(cè)。

基于文本的代碼克隆檢測(cè)方法主要有NICAD（Accurate Detection of Near-miss Intentional Clones）[6]、SDD（Similar Data Detection）[7]、Duploc[14]、Dup[15]等。Roy等[6]提出的NICAD工具與Lee等[7]提出的SDD方法是本領(lǐng)域內(nèi)現(xiàn)在被廣泛認(rèn)可的基于文本的檢測(cè)方法。NICAD工具首先對(duì)源代碼預(yù)處理，然后按照特定規(guī)則進(jìn)行轉(zhuǎn)換，最后利用動(dòng)態(tài)匹配模式尋找最長(zhǎng)相同子序列從而進(jìn)行文本比較，最終能夠檢測(cè)類型一到類型三的代碼克隆。SDD方法直接對(duì)源代碼建立倒排索引，使用n近鄰算法進(jìn)行代碼克隆檢測(cè)，可以檢測(cè)類型一到類型三的代碼克隆。然而將源代碼簡(jiǎn)單表征為文本，會(huì)丟失大量代碼的特殊信息。

基于詞匯的代碼克隆檢測(cè)技術(shù)主要有CCFinder（Code Clone Finder）[8]、CP-Miner[9]、Boreas[16]、CCLearner[17]等。Kamiya等[8]提出的CCFinder與Li等[9]提出的CP-Miner是兩種知名的基于詞匯的代碼克隆檢測(cè)技術(shù)。CCFinder將源代碼按照一定規(guī)則轉(zhuǎn)換為正則化序列以及參數(shù)化符號(hào)，然后使用后綴樹匹配算法進(jìn)行代碼克隆檢測(cè)，該工具能夠檢測(cè)類型一與類型二的代碼克隆。CP-Miner采用頻繁子項(xiàng)挖掘技術(shù)對(duì)大規(guī)模系統(tǒng)進(jìn)行克隆檢測(cè)，可以檢測(cè)類型一與類型二的代碼克隆?；谠~匯表征代碼，會(huì)忽略源代碼的結(jié)構(gòu)信息。

基于語法的代碼克隆檢測(cè)方法主要有DECKARD[10]、CloneDR[11]、CDLH（Clone Detection with Learning to Hash）[18]、Wahler等[19]的工作等。Jiang等[10]提出的DECKARD與Baxter等[11]提出的CloneDR是被目前廣泛使用的基于語法的代碼克隆檢測(cè)方法。兩者的原理都是將源代碼解析為抽象語法樹（Abstract Syntax Tree， AST），再分別利用樹匹配技術(shù)與局部敏感哈希（Locality Sensitive Hashing， LSH）匹配算法進(jìn)行相似度對(duì)比。DECKARD可以檢測(cè)到類型一到類型三的代碼克隆，CloneDR可以檢測(cè)到類型一與類型二的克隆片段?；跇涞臋z測(cè)方法由于需要遍歷樹，計(jì)算開銷相對(duì)較大。

基于語義的代碼克隆檢測(cè)技術(shù)主要有Duplix[12]、ConQAT[13]、利用同構(gòu)程序依賴圖的切片檢測(cè)克隆的方法[20]等。Krinke等[12]提出的Duplix和Hummel等提出的ConQAT[13]是兩種知名的基于語義的檢測(cè)方法。Duplix利用程序依賴圖表示源代碼，使用K-length patch算法對(duì)代碼片段進(jìn)行相似性對(duì)比，可以檢測(cè)到類型一與類型四的代碼克隆;ConQAT將源代碼符號(hào)化，使用基于后綴樹和索引的檢測(cè)算法，可以檢測(cè)到類型一與類型二的代碼克隆?；趫D的檢測(cè)技術(shù)需要程序依賴圖的生成器，且計(jì)算開銷十分大。

本團(tuán)隊(duì)在克隆代碼檢測(cè)方面也作了許多研究，史慶慶等[21]提出了一種基于后綴數(shù)組的克隆檢測(cè)方法，利用后綴數(shù)組查找相同Token子串，從而確定代碼克隆，此方法只能檢測(cè)出類型一和類型二的代碼克隆。張久杰等[22]提出了一種基于Token編輯距離檢測(cè)代碼克隆的方法，通過對(duì)Token的定長(zhǎng)子串映射，進(jìn)而利用編輯距離查找克隆對(duì)，此方法中源代碼轉(zhuǎn)換規(guī)則復(fù)雜。

此外，目前基于圖像的代碼克隆檢測(cè)方法只有Ragkhitwetsagul等[23]提出的Vincent，該方法利用EMD（Earth Movers Distance）和高斯模糊濾波器對(duì)代碼圖像之間進(jìn)行相似度比較，從而檢測(cè)出類型一到類型三的代碼克隆，只適用于Java語言的系統(tǒng)，具有一定的局限性。

2 基于圖像相似度的代碼克隆檢測(cè)方法

本文所提出的基于圖像相似度代碼克隆檢測(cè)（CCIS）方法的流程如圖1所示，主要由4個(gè)核心步驟組成：1）首先移除源代碼中的注釋及空白符等非函數(shù)代碼，提取代碼函數(shù)片段，并為代碼添加高亮;2）然后將經(jīng)過預(yù)處理的代碼片段轉(zhuǎn)換為圖像;3）接著對(duì)圖像進(jìn)行裁剪、填充以及調(diào)整大小等操作;4）最終使用Jaccard距離（Jaccard Distance）與感知哈希算法對(duì)標(biāo)準(zhǔn)化的代碼圖像進(jìn)行檢測(cè)，得到代碼克隆信息，并返回檢測(cè)結(jié)果。

2.1 源代碼預(yù)處理

源代碼預(yù)處理是基于圖像相似度檢測(cè)代碼克隆的基礎(chǔ)性工作。本文以Python語言為研究對(duì)象，對(duì)源代碼預(yù)處理的步驟主要包括移除源代碼中的單行注釋、多行注釋及空白符等非函數(shù)代碼，以函數(shù)粒度進(jìn)行識(shí)別并標(biāo)記代碼片段，根據(jù)關(guān)鍵字、數(shù)據(jù)類型、函數(shù)名稱、標(biāo)識(shí)符以及數(shù)字或字符串在代碼中所占權(quán)重不同，對(duì)代碼進(jìn)行高亮。

基于圖像相似度檢測(cè)代碼克隆是根據(jù)源代碼圖像中像素分布匹配來計(jì)算相似度，若兩個(gè)代碼片段為克隆關(guān)系，則它們之間大部分代碼像素對(duì)齊，反之亦然，因此，代碼預(yù)處理會(huì)直接影響后續(xù)過程以及檢測(cè)結(jié)果。

本文所提取的函數(shù)包括循環(huán)嵌套深度，而不是僅僅限制于考慮詞法層面的信息[22]。函數(shù)提取算法主要步驟如下：

2.2 圖像轉(zhuǎn)換

經(jīng)過預(yù)處理的源代碼需要轉(zhuǎn)換為圖像，然后根據(jù)計(jì)算圖像之間的相似度，進(jìn)行代碼克隆檢測(cè)，確定代碼克隆對(duì)。本文借助文本處理工具Highlight（http：//www.andre-simon.de）將經(jīng)過預(yù)處理提取的函數(shù)代碼批量添加高亮并轉(zhuǎn)換為超級(jí)文本標(biāo)記語言（HyperText Markup Language， HTML）文件，使得所占權(quán)重高的代碼在圖像相似度檢測(cè)中發(fā)揮作用，從而降低數(shù)字、字符串等不重要代碼在結(jié)果中所占的比重。如圖2所示，為工具Highlight的使用界面截圖。

本文使用Python imgkit （https：//pypi.org/project/imgkit/）將文件中每個(gè)函數(shù)的HTML文件都轉(zhuǎn)換為便攜式網(wǎng)絡(luò)圖形（Portable Network Graphics， PNG）。圖像以大小為m×n的二維矩陣方式讀入存儲(chǔ)器，矩陣中每一項(xiàng)數(shù)值的取值范圍為0到255，代表原始圖像的8位灰度圖，而灰度值是根據(jù)像素點(diǎn)色彩通道中的紅色、綠色和藍(lán)色（RGB）值求平均值所取。

2.3 圖像規(guī)范化

經(jīng)過圖像化的函數(shù)代碼片段無法直接進(jìn)行相似度檢測(cè)，這是由于直接轉(zhuǎn)換后的圖像之間像素以及比例不同，不滿足Jaccard距離（Jaccard Distance）與感知哈希算法（perceptual Hash， pHash）的檢測(cè)條件。為了解決這一問題，需要對(duì)源代碼轉(zhuǎn)換后的圖像進(jìn)行規(guī)范化處理。

本文將圖像背景即非源代碼像素設(shè)置為黑色，其灰度值為0，而源代碼的像素是通過該像素點(diǎn)的RGB值求平均計(jì)算所得，這意味著可以根據(jù)矩陣中非零元素的數(shù)量來計(jì)算圖片中所包含源代碼的像素?cái)?shù)量。

在進(jìn)行圖像相似度檢測(cè)時(shí)，需要被檢測(cè)的原始圖像相互之間大小相同，且不能經(jīng)過隨意縮放，避免造成因圖像中代碼的字體大小不一樣，而導(dǎo)致圖像中像素點(diǎn)錯(cuò)位，從而丟失克隆對(duì)的情況。基于此，需要對(duì)所有圖像進(jìn)行規(guī)范化處理。對(duì)于長(zhǎng)度不同的圖像，使用黑色補(bǔ)全相對(duì)短的圖像，從而與較長(zhǎng)的圖像長(zhǎng)度相等。由于生成的圖像寬度是統(tǒng)一像素的，為了在pHash檢測(cè)過程中減小因非代碼像素所占比重過大而造成相似度過高的問題，需要極大限度地在寬度方面裁剪非代碼像素，并還要保證圖像之間寬度一致。圖像規(guī)范化的算法主要步驟如下：

2.4 相似度檢測(cè)

本文選取兩種計(jì)算圖像相似度的方法：Jaccard距離與感知哈希算法。

使用Jaccard距離檢測(cè)代碼克隆片段速度相對(duì)較快，可以處理大量的數(shù)據(jù)，但是效果并不理想，該方法只能檢測(cè)到較簡(jiǎn)單的代碼克隆，對(duì)于比較復(fù)雜的情況無法準(zhǔn)確地識(shí)別，因此使用pHash算法進(jìn)一步檢測(cè)，pHash算法通過離散余弦變換最大限度上保留圖片中低頻部分，只要圖像的整體結(jié)構(gòu)保持不變，其對(duì)應(yīng)的哈希值基本不變，能較好地識(shí)別相對(duì)復(fù)雜的克隆情況。

2.4.1 Jaccard距離

Jaccard距離[23-26]是用來衡量?jī)蓚€(gè)集合差異性的一種指標(biāo)，它是Jaccard相似系數(shù)（Jaccard similarity coefficient）的補(bǔ)集，被定義為1減去Jaccard相似系數(shù)。為了計(jì)算Jaccard距離，本文將基于零范數(shù)的兩個(gè)代碼圖像的差異給出如下定義。給定兩個(gè)尺寸相等的圖像，分別用大小為m×n的二維矩陣A和B表示。矩陣D是由矩陣A和B衍生的逐元差分矩陣，其中第i行第j列的元素記為dij。這兩個(gè)圖像之間的差異用矩陣D中的非零元素的個(gè)數(shù)表示，記作diff。如圖3（a）與圖3（b）所示，給定一對(duì)源代碼圖像bubble_sort1和bubble_sort2，它們的區(qū)別如圖3（c）所示，diff值為圖像中白色實(shí)線區(qū)域內(nèi)的非零像素的個(gè)數(shù)：

本文將矩陣A和B相加得到的矩陣記為矩陣S，sij表示矩陣S中第i行第j列的元素。這兩個(gè)圖像中所包含源代碼文本的區(qū)域用矩陣S中的非零元素的個(gè)數(shù)表示，記作sum。為了將距離限制于（0，1）區(qū)間，本文借助sum對(duì)距離進(jìn)行標(biāo)準(zhǔn)化處理。如圖3（d）所示，sum的值為圖中黑色實(shí)線區(qū)域內(nèi)的非零像素的個(gè)數(shù)：

由于背景在圖像中所占比例較大，且背景之間始終相互匹配，為了防止該情況所造成的影響，即產(chǎn)生比實(shí)際情況遠(yuǎn)遠(yuǎn)要小的距離值，本文選取代碼區(qū)域像素個(gè)數(shù)總和，而不是圖像中所有像素的總數(shù)，然后根據(jù)diff值與sum值計(jì)算歸一化距離，其相似性與距離的互補(bǔ)。矩陣A和B之間的歸一化距離記為distance，用矩陣A與B表示的兩張圖像之間的相似度記作similarity：

2.4.2 感知哈希算法

本文使用感知哈希（perceptual hash，pHash）算法[27-28]進(jìn)行代碼圖像的克隆檢測(cè)，pHash算法使用離散余弦變換（Discrete Cosine Transform， DCT）將像素域的圖像轉(zhuǎn)換為頻率域，得到其頻率系數(shù)矩陣，選取矩陣左上角區(qū)域元素計(jì)算圖像哈希值。通過比較兩張圖像哈希值的距離，進(jìn)而判斷圖像是否相似。pHash算法主要步驟如下：

使用最大pHash距離對(duì)計(jì)算出的距離進(jìn)行歸一化，相似度與距離互補(bǔ)。矩陣A和B之間的pHash距離用pHash（A，B）表示，任意兩個(gè)矩陣之間最大的pHash距離記作pHashmax，用矩陣A與B表示的兩張圖像之間的相似度用變量similarity表示：

3 實(shí)驗(yàn)及分析

3.1 數(shù)據(jù)描述

由于研究者們所提出的克隆檢測(cè)方法在檢測(cè)粒度、針對(duì)語言以及系統(tǒng)規(guī)模等方面并不統(tǒng)一，所以目前還沒有用于評(píng)價(jià)代碼克隆檢測(cè)工具的國(guó)際標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。Svajlenko等[29]提出了一個(gè)Java代碼集——BigCloneBench，但是它受語言和只有10種功能的限制，并不能適用于全部檢測(cè)工具。為了準(zhǔn)確而客觀地評(píng)價(jià)CCIS方法，本文借鑒Roy團(tuán)隊(duì)提出的變異插入[30]測(cè)試方法，該方法不依賴于任何工具與編程語言，可以比較公平且獨(dú)立地評(píng)價(jià)檢測(cè)結(jié)果，其核心思想是在給定的源代碼片段中通過人為修改、增加或刪除一些語句，產(chǎn)生類型一到類型三的代碼克隆對(duì)。例如對(duì)源代碼進(jìn)行更改類型名稱、修改常量值、增加空白符等操作，產(chǎn)生類型二的代碼對(duì)。所有源代碼片段經(jīng)過變異插入后得到的代碼片段為變異代碼片段，在此過程中，所有變異相關(guān)信息的信息都會(huì)被記錄，便于對(duì)所提出的方法檢測(cè)結(jié)果進(jìn)行召回率與精確度的計(jì)算。數(shù)據(jù)集的構(gòu)建與變異相關(guān)信息的記錄人員包括作者本人、校內(nèi)代碼克隆研究專家5名以及企業(yè)軟件開發(fā)人員6名。

本文以函數(shù)粒度作為研究對(duì)象，選取來自6款開源項(xiàng)目中的219個(gè)源代碼片段，具體變異插入過程包括三種情況：第一種情況就是對(duì)源代碼片段進(jìn)行增加、刪除空白符或注釋，以及修改注釋的操作，使經(jīng)過變異插入的代碼片段與源代碼片段形成類型一的代碼克隆對(duì);第二種情況是對(duì)源代碼片段進(jìn)行修改數(shù)據(jù)類型、標(biāo)識(shí)符以及常量數(shù)值等操作，使源代碼片段和變異插入的代碼片段形成類型二的代碼克隆對(duì);第三種情況是對(duì)源代碼片段中的少量語句刪除、修改或者增加，并且修改后的代碼片段與源代碼片段的功能要相同，形成類型三的代碼克隆對(duì)。經(jīng)過變異插入過程之后，得到275個(gè)變異片段，因此數(shù)據(jù)集當(dāng)中共有494個(gè)代碼克隆片段。為了使結(jié)果更加客觀，又在此基礎(chǔ)上加入了72個(gè)非代碼克隆片段，即噪聲片段，且任意兩個(gè)噪聲片段之間都互不為代碼克隆。項(xiàng)目基本信息見表1所示。

3.2 評(píng)價(jià)指標(biāo)

檢測(cè)的結(jié)果是二分類問題，即該代碼片段是克隆片段或者不是克隆片段，因此采用召回率與精確度兩個(gè)度量指標(biāo)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)價(jià)[22，30-31]。召回率（Recall）指所有被檢測(cè)到的代碼克隆數(shù)量占總體克隆數(shù)量的比例：

精確度（Precision）指克隆檢測(cè)算法所檢測(cè)到候選代碼克隆中真實(shí)代碼克隆的比例：

其中：TP（True Positive）代表CCIS方法檢測(cè)出的克隆片段與真實(shí)代碼克隆片段的交集;FP（False Positive）代表CCIS方法檢測(cè)出是克隆片段但實(shí)際并不是真實(shí)克隆片段的代碼克隆片段集合;FN（False Negative）代表CCIS方法未檢測(cè)出的真實(shí)代碼克隆片段集合。

3.3 實(shí)驗(yàn)結(jié)果及分析

代碼克隆檢測(cè)最終結(jié)果以可擴(kuò)展標(biāo)記語言（eXtensible Markup Language， XML）形式反饋，為后續(xù)對(duì)代碼克隆數(shù)據(jù)進(jìn)一步分析提供數(shù)據(jù)交換基礎(chǔ)。圖4為XML的部分結(jié)果展示。

實(shí)驗(yàn)將494個(gè)代碼克隆片段與72個(gè)非代碼克隆片段整合到一起作為一個(gè)待檢測(cè)的項(xiàng)目，然后使用CCIS方法進(jìn)行檢測(cè)。根據(jù)檢測(cè)結(jié)果顯示，該數(shù)據(jù)集中共有414個(gè)代碼克隆片段。為了驗(yàn)證檢測(cè)出的代碼克隆片段在不同項(xiàng)目中分布是否均衡，表2顯示出了源項(xiàng)目中的494個(gè)真實(shí)代碼克隆片段與414個(gè)所檢測(cè)到的代碼克隆片段在6個(gè)項(xiàng)目中的分布情況。

表2中出現(xiàn)的錯(cuò)檢與漏檢情況，針對(duì)這一問題進(jìn)行了分析，漏檢的主要原因是由于這些片段與其對(duì)應(yīng)的代碼克隆片段在替換的標(biāo)識(shí)符等長(zhǎng)度發(fā)生較大變化從而導(dǎo)致大量像素點(diǎn)整體偏移發(fā)生錯(cuò)位，且包含一些語句的增加刪除，從而導(dǎo)致代碼片段的整體結(jié)構(gòu)輪廓發(fā)生改變，在對(duì)代碼圖像進(jìn)行相似度檢測(cè)時(shí)，只有少數(shù)像素點(diǎn)可以匹配。發(fā)生錯(cuò)檢的主要原因是兩個(gè)代碼片段雖然不是克隆對(duì)，但是其代碼結(jié)構(gòu)輪廓相似，從而使得大部分像素點(diǎn)相互可以匹配，造成兩幅圖像之間計(jì)算距離比實(shí)際距離小，然而這種情況相對(duì)比較少見，在后續(xù)的實(shí)驗(yàn)中會(huì)改進(jìn)算法去改善該問題。

根據(jù)變異插入過程的記錄信息，對(duì)檢測(cè)結(jié)果進(jìn)行分析，發(fā)現(xiàn)檢測(cè)出的414個(gè)代碼克隆片段中包含412個(gè)真實(shí)的代碼克隆片段，即這些代碼克隆片段來自包括源代碼片段與變異插入代碼片段在內(nèi)的494個(gè)代碼克隆片段，還有一個(gè)檢測(cè)出的克隆代碼片段來自于噪聲代碼片段。利用式（8）、（9）對(duì)CCIS方法得到的克隆檢測(cè)結(jié)果進(jìn)行召回率與精確度的計(jì)算，本次實(shí)驗(yàn)的召回率為430/494=87.04%，精確度為412/414=96.38%。由于數(shù)據(jù)集中設(shè)置的噪聲片段所占總體克隆代碼片段的比例較小，而且噪聲片段與變異插入的代碼片段相似度較低，使得本次實(shí)驗(yàn)的精確度相對(duì)較高。在后續(xù)的工作中，將會(huì)不斷擴(kuò)大數(shù)據(jù)集中的代碼克隆片段數(shù)量與噪聲代碼片段。

為了分析CCIS方法對(duì)于類型一、類型二與類型三的代碼克隆檢測(cè)效果，本文根據(jù)數(shù)據(jù)集中的變異插入記錄信息對(duì)實(shí)驗(yàn)最終檢測(cè)結(jié)果中三種類型的代碼克隆數(shù)量進(jìn)行統(tǒng)計(jì)，并分別計(jì)算出了使用Jaccard與pHash兩種方法所檢測(cè)到每種類型代碼克隆的召回率與精確度，具體信息如表3所示。

根據(jù)表3的結(jié)果發(fā)現(xiàn)，使用Jaccard方法能準(zhǔn)確地檢測(cè)出所有類型一的代碼克隆與60%類型二的克隆，而僅能檢測(cè)到10%類型三的代碼克隆。使用pHash算法可以檢測(cè)檢測(cè)出100%的類型一克隆、88%類型二的代碼克隆以及60%類型三的克隆?？梢缘贸鍪褂胮Hash算法檢測(cè)代碼克隆比使用Jaccard方法檢測(cè)具有更準(zhǔn)確且更全面的效果，即可以使用pHash算法對(duì)Jaccard方法檢測(cè)不到的克隆進(jìn)一步檢測(cè)。

3.4 對(duì)比實(shí)驗(yàn)及分析

為了驗(yàn)證CCIS方法的有效性，本實(shí)驗(yàn)與NICAD工具在同款檢測(cè)軟件和相同實(shí)驗(yàn)環(huán)境的條件下進(jìn)行了對(duì)比。選取NICAD是因?yàn)樗诋?dāng)前的代碼克隆檢測(cè)方法的評(píng)價(jià)與對(duì)比性研究[4，32]中有較優(yōu)秀的表現(xiàn)，目前可以對(duì)Python語言進(jìn)行代碼克隆檢測(cè)的方法較少，而NICAD可以檢測(cè)Python語言中的代碼克隆，并且被代碼克隆領(lǐng)域廣泛認(rèn)可。NICAD可以檢測(cè)類型一、類型二與部分類型三的代碼克隆。

使用上文中構(gòu)建好的實(shí)驗(yàn)評(píng)價(jià)數(shù)據(jù)集以及變異插入相關(guān)信息，分別利用CCIS方法與NICAD進(jìn)行代碼克隆檢測(cè)，得到不同的召回率與精確度如表4所示。

通過對(duì)比實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，兩種代碼克隆檢測(cè)方法對(duì)6款軟件都有很好的檢測(cè)效果。在6款測(cè)試的軟件中，使用NICAD與使用CCIS方法檢測(cè)代碼克隆的精確度都很高，幾乎都可以達(dá)到100%。根據(jù)召回率與精確度各自的平均值來講，CCIS方法在檢測(cè)代碼克隆時(shí)比NICAD所檢測(cè)的代碼克隆結(jié)果的召回率約高出5個(gè)百分點(diǎn)。經(jīng)過人為查驗(yàn)檢測(cè)出的克隆信息發(fā)現(xiàn)，CCIS方法的精確度與NICAD的精確度不相上下，雖然CCIS方法漏檢了一些真正的代碼克隆片段，但是CCIS方法可以檢測(cè)到NICAD檢測(cè)不到的代碼克隆片段。結(jié)果的查驗(yàn)與分析人員包括作者本人、校內(nèi)代碼克隆研究專家5名以及企業(yè)軟件開發(fā)人員6名。

3.5 實(shí)驗(yàn)有效性說明

本文中代碼預(yù)處理主要通過Python語言編程實(shí)現(xiàn)，代碼轉(zhuǎn)換為圖像使用文本處理工具Highlight 3.4.8和調(diào)用Python imgkit 1.0.1包實(shí)現(xiàn)，圖像處理與基于圖像相似度的代碼克隆檢測(cè)方法使用Python編程與Python Imaging Library （PIL） （http：//pythonware.com/products/pil/）圖像處理工具、numpy 1.15.2 （http：//www.numpy.org/）科學(xué)計(jì)算與分析工具，其余工作借助Python實(shí)現(xiàn)。研究中所使用的數(shù)據(jù)集已上傳到百度網(wǎng)盤，鏈接https：//pan.baidu.com/s/1zwll924jGtYo1ILVH8oOIQ（提取碼：wihx）。

4 結(jié)語

本文提出了一種基于圖像相似度的代碼克隆檢測(cè)方法，根據(jù)圖像語義的相似性進(jìn)行代碼克隆檢測(cè)，是一種新的源代碼表征方式，為代碼克隆分析提供了一種全新的視角。利用圖像表征源代碼片段進(jìn)行克隆檢測(cè)，為后續(xù)進(jìn)行深度學(xué)習(xí)方面的研究奠定了基礎(chǔ)。

本文的研究工作仍有不足之處，例如由于選取的代碼行數(shù)受到限制會(huì)導(dǎo)致漏檢一些代碼克隆，檢測(cè)的算法還可以進(jìn)一步優(yōu)化，只能針對(duì)Python語言的項(xiàng)目進(jìn)行檢測(cè)等。在今后的工作中，本文將會(huì)繼續(xù)研究并解決這些問題，并且擬通過結(jié)合深度學(xué)習(xí)技術(shù)對(duì)代碼克隆檢測(cè)進(jìn)行更深入的研究，從而取得更好的結(jié)果。

參考文獻(xiàn) （References）

[1] VERENA K， WAGNER S， KOSCHKE R. Are there functionally similar code clones in practice？[C]// Proceedings of the 12th International Workshop on Software Clones. Washington， DC： IEEE Computer Society， 2018： 2-8.

[2] ROY C K. Large scale clone detection， analysis， and benchmarking： An evolutionary perspective （Keynote）[C]// Proceedings of the 12th International Workshop on Software Clones. Washington， DC： IEEE Computer Society， 2018： 1.

[3] ABDULLAH S， JUGAL K. A survey of software clone detection techniques [J]. International Journal of Computer Applications， 2016， 137（10）： 1-21.

[4] ROY C K， CORDY J R， KOSCHKE R. Comparison and evaluation of code clone detection techniques and tools： a qualitative approach [J]. Science of Computer Programming， 2009， 74（7）： 470-495.

[5] BELLON S， KOSCHKE R， ANTONIOL G， et al. Comparison and evaluation of clone detection tools [J]. IEEE Transactions on Software Engineering， 2007， 33（9）： 577-591.

[6] ROY C K， CORDY J R. NICAD： accurate detection of near-miss intentional clones using flexible pretty-printing and code normalization [C]// Proceedings of the 16th IEEE International Conference on Program Comprehension. Piscataway， NJ： IEEE， 2008： 172-181.

[7] LEE S. SDD： high performance code clone detection system for large scale source code [C]// Proceedings of the 20th ACM SIGPLAN Conference on Object-Oriented Programming. New York： ACM， 2005： 140-141.

[8] KAMIYA T， KUSUMOTO S， INOUE K. CCFinder： a multilinguistic token-based code clone detection system for large scale source code[J]. IEEE Transactions on Software Engineering， 2002， 28（7）： 654-670.

[9] LI Z， LU S， MYAGMAR S， et al. CP-Miner： finding copy-paste and related bugs in large-scale software code[J]. IEEE Transactions on Software Engineering， 2006， 32（3）： 176-192.

[10] JIANG L， MISHERGHI G， SU Z， et al. DECKARD： scalable and accurate tree-based detection of code clones [C]// Proceedings of the 29th International Conference on Software Engineering. Washington， DC： IEEE Computer Society， 2007： 96-105.

[11] BAXTER I D， YAHIN A， MOURA L， et al. Clone detection using abstract syntax trees [C]// Proceedings of the 1998 IEEE International Conference on Software Maintenance. Piscataway， NJ： IEEE， 1998： 368.

[12] KRINKE J. Identifying similar code with program dependence graphs[C]// Proceedings of the 8th Working Conference on Reverse Engineering. Piscataway， NJ： IEEE， 2001： 301-309.

[13] HUMMEL B， JUERGENS E， HEINEMANN L， et al. Index-based code clone detection： incremental， distributed， scalable [C]// Proceedings of the 2010 IEEE International Conference on Software Maintenance. Washington， DC： IEEE Computer Society， 2010： 1-9.

[14] DUCASSE S， RIEGER M， DEMEYER S. A language independent approach for detecting duplicated code[C]// Proceedings of the 1999 International Conference on Software Maintenance. Piscataway， NJ： IEEE， 1999： 109-118.

[15] BAKER B S. On finding duplication and near-duplication in large software systems[C]// Proceedings of the 2nd Working Conference on Reverse Engineering. Piscataway， NJ： IEEE， 1995： 86-95.

[16] YUAN Y， GUO Y. Boreas： an accurate and scalable token-based approach to code clone detection[C]// Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering. Piscataway， NJ： IEEE， 2012： 286-289.

[17] LI L， FENG H， ZHUANG W， et al. CCLearner： a deep learning-based clone detection approach[C]// Proceedings of the 2017 IEEE International Conference on Software Maintenance and Evolution. Washington， DC： IEEE Computer Society， 2017： 249-260.

[18] WEI H H， LI M. Supervised deep features for software functional clone detection by exploiting lexical and syntactical information in source code[C]// Proceedings of the 26th International Joint Conferences on Artificial Intelligence Organization. Piscataway， NJ： IEEE， 2017： 303-309.

[19] WAHLER V， SEIPEL D， WOLFF J， et al. Clone detection in source code by frequent itemset techniques[C]// Proceedings of the 4th IEEE International Workshop on Source Code Analysis and Manipulation. Piscataway， NJ： IEEE， 2004： 128-135.

[20] KOMONDOOR R， HORWITZ S. Using slicing to identify duplication in source code[C]// Proceedings of the 8th International Symposium on Static Analysis. Berlin： Springer， 2001： 40-56.

[21] 史慶慶，張麗萍，尹麗麗，等.基于后綴數(shù)組的克隆檢測(cè)[J].計(jì)算機(jī)工程，2013，39（9）：123-127.（SHI Q Q， ZHANG L P， YIN L L， et al. Clone detection based on suffix array[J]. Computer Engineering， 2013， 39（9）： 123-127.）

[22] 張久杰，王春暉，張麗萍，等.基于Token編輯距離檢測(cè)克隆代碼[J].計(jì)算機(jī)應(yīng)用，2015，35（12）：3536-3543.（ZHANG J J， WANG C H， ZHANG L P， et al. Clone code detection based on Levenshtein distance of token[J]. Journal of Computer Applications， 2015， 35（12）： 3536-3543.）

[23] RAGKHITWETSAGUL C， KRINKE J， MARNETTE B. A picture is worth a thousand words： Code clone detection based on image similarity[C]// Proceedings of the 12th International Workshop on Software Clones. Washington， DC： IEEE Computer Society， 2018： 44-50.

[24] MCCORMICK W P， LYONS N I， HUTCHESON K. Distributional properties of Jaccards index of similarity[J]. Communications in Statistics， 1992， 21（1）： 51-68.

[25] 俞婷婷，徐彭娜，江育娥，等.基于改進(jìn)的Jaccard系數(shù)文檔相似度計(jì)算方法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2017，26（12）：137-142.（YU T T， XU P N， JIANG Y E， et al. Text similarity method based on the improved Jaccard coefficient[J]. Computer Systems and Applications， 2017， 26（12）： 137-142.）

[26] 田星，鄭瑾，張祖平.基于詞向量的Jaccard相似度算法[J].計(jì)算機(jī)科學(xué)，2018，45（7）：186-189.（TIAN X， ZHENG J， ZHANG Z P. Jaccard text similarity algorithm based on word embedding[J]. Computer Science， 2018， 45（7）： 186-189.）

[27] 宋博，姜萬里，孫濤，等.快速特征提取與感知哈希結(jié)合的圖像配準(zhǔn)算法[J].計(jì)算機(jī)工程與應(yīng)用，2018，54（7）：206-212.（SONG B， JIANG W L， SUN T， et al. Image registration algorithm based on fast feature extraction and perceptual hash[J]. Computer Engineering and Applications， 2018， 54（7）： 206-212.）

[28] 李丹平，楊超，姜奇，等.一種支持所有權(quán)認(rèn)證的客戶端圖像模糊去重方法[J].計(jì)算機(jī)學(xué)報(bào)，2018，41（6）：1047-1063.（LI D P， YANG C， JINAG Q， et al. A client-based image fuzzy deduplication method supporting proof of ownership[J]. Chinese Journal of Computers， 2018， 41（6）： 1047-1063.）

[29] SVAJLENKO J， ROY C K. BigCloneEval： a clone detection tool evaluation framework with BigCloneBench [C]// Proceedings of the 2016 IEEE International Conference on Software Maintenance and Evolution. Piscataway， NJ： IEEE， 2016： 131-140.

[30] ROY C K， CORDY J R. A mutation/injection-based automatic framework for evaluating code clone detection tools[C]// Proceedings of the 2009 IEEE International Conference on Software Testing Verification and Validation Workshop. New York： ACM， 2009： 157-166.

[31] 蘇小紅，張凡龍.面向管理的克隆代碼研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2018，41（3）：628-651.（SU X H， ZHANG F L. A survey for management-oriented code clone research[J]. Chinese Journal of Computers， 2018， 41（3）： 628-651.）

[32] SVAJLENKO J， ROY C K. Evaluating modern clone detection tools[C]// Proceedings of the 2014 IEEE International Conference on Software Maintenance and Evolution. Piscataway， NJ： IEEE， 2014： 321-330.