(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 浙江 杭州 310023)

隨著互聯(lián)網(wǎng)高速發(fā)展及軟件需求的不斷增加，代碼克隆和代碼復(fù)用頻繁地出現(xiàn)在軟件快速開發(fā)和重構(gòu)過程中。研究數(shù)據(jù)表明：一般的軟件開發(fā)過程中包含5%～20%的重復(fù)代碼，在很多知名的軟件系統(tǒng)中也包含大量的代碼復(fù)用，如Linux核心代碼中就存在15%～25%的復(fù)用代碼，而在開源項(xiàng)目中更是有超過50%的代碼被復(fù)用[1]。隨著開源項(xiàng)目的不斷發(fā)展、代碼復(fù)用不斷擴(kuò)大，代碼復(fù)用的廣泛程度可以作為代碼質(zhì)量的評(píng)判標(biāo)準(zhǔn)和選擇所復(fù)用的代碼模塊的參考依據(jù)[2]。代碼復(fù)用也存在兩面性：一方面，重用高質(zhì)量的代碼不僅可以提高開發(fā)效率，而且能規(guī)避編寫新代碼帶來(lái)的風(fēng)險(xiǎn)；另一方面，惡意或?yàn)E用低質(zhì)量的代碼則會(huì)導(dǎo)致系統(tǒng)出現(xiàn)大量Bug、軟件運(yùn)行效率低下以及影響系統(tǒng)安全[3]等問題，且克隆代碼給軟件維護(hù)帶來(lái)影響，當(dāng)克隆代碼出現(xiàn)Bug時(shí)，其他相似代碼則存在相同Bug。通過代碼克隆檢測(cè)可以判斷應(yīng)用系統(tǒng)中是否存在克隆代碼，若存在克隆代碼則對(duì)其進(jìn)行重構(gòu)，從而提高代碼質(zhì)量。因此，對(duì)于軟件開發(fā)項(xiàng)目的代碼克隆檢測(cè)就顯得十分必要。代碼克隆檢測(cè)有很多不同種類的檢測(cè)技術(shù)及應(yīng)用場(chǎng)景，主要分為5 類：基于Text(文本)方法[4]、基于Token(詞法)方法[5]、基于AST(抽象語(yǔ)法樹)方法[6]、基于PDG(程序依賴圖)方法[7]和基于Metrics(度量值)方法[8]。基于Text檢測(cè)方法通常是對(duì)源代碼之間的字符串進(jìn)行比較，對(duì)代碼文本布局、注釋進(jìn)行規(guī)范化處理外不進(jìn)行其他形式轉(zhuǎn)換。基于Token方法首先使用詞法或語(yǔ)法分析工具把源代碼的每一行都轉(zhuǎn)換成token序列，并將所有序列連接成token串；接著掃描這個(gè)token串并找到相似的token子序列即為克隆代碼。基于AST方法使用語(yǔ)法分析器將檢測(cè)代碼轉(zhuǎn)化為抽象語(yǔ)法樹，再使用子樹匹配算法檢測(cè)?；赑DG方法是將檢測(cè)代碼轉(zhuǎn)換為程序依賴圖，再使用檢測(cè)子圖同構(gòu)方法進(jìn)行檢測(cè)?；贛etrics方法是通過提取檢測(cè)代碼的度量值間接對(duì)代碼中可能存在的類似代碼進(jìn)行檢測(cè)[9]。

經(jīng)過對(duì)以上克隆檢測(cè)方法的研究：一方面，基于AST，PDG等方法有較高的準(zhǔn)確率及召回率，但算法復(fù)雜，實(shí)現(xiàn)較為困難，消耗過多的計(jì)算資源，并且可擴(kuò)展性有限，不適用于大量代碼的克隆檢測(cè)；另一方面，基于Text，Token，Metrics等方法有較快的檢測(cè)速度，但檢測(cè)準(zhǔn)確率和召回率較低。因此，提出了基于Simhash[10]算法的代碼克隆檢測(cè)方法，并在Simhash指紋簽名的計(jì)算過程中使用TF-IDF[11]及馬爾科夫模型優(yōu)化關(guān)鍵詞權(quán)重分配，計(jì)算出L位二進(jìn)制01串代碼指紋簽名。文檔相似度計(jì)算存在很多不同的方法和應(yīng)用[12]，筆者采用漢明距離[13]來(lái)計(jì)算待檢測(cè)代碼的相似度。

1 Simhash算法

Simhash算法由Google公司的Charikar等在2007年第一次提出，是一種降低維度的算法，其核心是將一篇文檔離散化轉(zhuǎn)換成高維的特征向量再映射成唯一的L位二進(jìn)制指紋簽名，進(jìn)而比較所產(chǎn)生的指紋簽名，得出各文檔之間的相似度。指紋越接近，則表明文檔越相似。Simhash算法計(jì)算步驟描述如下：

步驟1初始化：待檢測(cè)代碼作為輸入，輸出為L(zhǎng)位的二進(jìn)制指紋簽名S，初始化為0；定義L維向量V，初始化為0。

步驟2預(yù)處理：對(duì)代碼文件進(jìn)行分詞處理，將文檔轉(zhuǎn)化為一組特征。

步驟3指紋計(jì)算：對(duì)于每一項(xiàng)特征，使用Hash算法得出L位的簽名b，在Hash值得基礎(chǔ)上，給所有特征向量進(jìn)行加權(quán)，即w=Hash×Weight，如果b的第i(1≤i≤f)位為1，則向量V的第i個(gè)元素加上該特征的權(quán)重；否則V的第i個(gè)元素減去該特征的權(quán)重。

步驟4輸出簽名：如果向量V的第i個(gè)元素大于0，則簽名S的第i位為1，否則為0，輸出指紋簽名S。

具體計(jì)算步驟如圖1所示。

圖1 Simhash算法流程圖Fig.1 The flow chart of Simhash algorithm

Simhash算法的核心優(yōu)勢(shì)在于可以將一篇高維特征的文檔轉(zhuǎn)換為二進(jìn)制指紋簽名，提高相似度檢測(cè)速度，但該算法是將代碼中的所有單詞作為關(guān)鍵詞，代碼中單詞出現(xiàn)的次數(shù)作為關(guān)鍵詞的權(quán)重，以此作為衡量標(biāo)準(zhǔn)計(jì)算得到的權(quán)重準(zhǔn)確度不高，計(jì)算得到的指紋簽名準(zhǔn)確度也會(huì)降低。此外，Simhash算法是基于大量網(wǎng)頁(yè)文檔的查重技術(shù)，在少量文檔的情況下，檢測(cè)準(zhǔn)確率較低。結(jié)合Simhash算法的優(yōu)缺點(diǎn)，并針對(duì)Simhash算法中權(quán)重計(jì)算準(zhǔn)確度等問題，提出了一種結(jié)合TF-IDF及馬爾科夫模型的Simhash優(yōu)化算法Ad-Sim。

2 Simhash算法研究與改進(jìn)

2.1 代碼預(yù)處理

為了提高代碼檢測(cè)的準(zhǔn)確率，剔除代碼中一些無(wú)關(guān)特征或者毫無(wú)意義特征對(duì)代碼的影響，需要在指紋計(jì)算前進(jìn)行代碼歸一化預(yù)處理。Ad-Sim算法中歸一化處理過程主要包括：去除引用代碼、詞法分析和轉(zhuǎn)換。

實(shí)驗(yàn)中代碼克隆檢測(cè)的測(cè)試用例代碼使用的語(yǔ)言為Java，首先去除項(xiàng)目代碼中參考引入或開源項(xiàng)目的部分代碼；其次利用Java本身的詞法規(guī)則對(duì)待檢測(cè)代碼進(jìn)行詞法分析，將每行代碼解析成關(guān)鍵詞序列。在經(jīng)過詞法分析后得到的關(guān)鍵詞序列，為了提高檢測(cè)準(zhǔn)確率，還需要對(duì)關(guān)鍵詞序列進(jìn)行必要的添加、刪除或修改，具體規(guī)則如下：

1) 刪除單行注釋、塊注釋以及文檔注釋等無(wú)關(guān)內(nèi)容。

2) 刪除package包名與類導(dǎo)入語(yǔ)句、數(shù)字和字符串等常量的無(wú)關(guān)代碼。

3) 替換變量名、方法名和類名關(guān)鍵詞為VARIABLE。

4) 替換各符號(hào)關(guān)鍵詞為SYMBOL。

2.2 基于TF-IDF的關(guān)鍵詞權(quán)重計(jì)算

(1)

用IDF表示逆向文件頻率，即該關(guān)鍵詞在所有文件中出現(xiàn)的頻率。假設(shè)代碼庫(kù)中文件總數(shù)為M，包含關(guān)鍵詞i的文件數(shù)為Ni，那么關(guān)鍵詞i的逆向文件詞頻IDF為

(2)

關(guān)鍵詞i對(duì)這份代碼文檔的重要程度為

(3)

Ad-Sim算法中采用TF-IDF計(jì)算代碼中關(guān)鍵詞的權(quán)重，優(yōu)勢(shì)在于可以過濾掉代碼中對(duì)代碼克隆檢測(cè)沒有用處的關(guān)鍵詞。在計(jì)算IDF時(shí)，假設(shè)關(guān)鍵詞序列中的代碼文件總數(shù)以及包含某一關(guān)鍵詞的代碼文件總數(shù)相等，從而計(jì)算出該關(guān)鍵詞IDF值為0，即表明該關(guān)鍵詞在克隆檢測(cè)中不起作用。例如在Java代碼中，幾乎所有的Java文件都會(huì)出現(xiàn)“public”“class”等關(guān)鍵詞，利用TF-IDF去掉這些詞后使得相對(duì)重要的關(guān)鍵詞得到保留，從而提高指紋簽名計(jì)算的精確度。

2.3 基于馬爾科夫模型的關(guān)鍵詞權(quán)重優(yōu)化

如果把代碼中出現(xiàn)的關(guān)鍵詞作為一個(gè)狀態(tài)來(lái)看的話，那么馬爾科夫模型的狀態(tài)轉(zhuǎn)移矩陣恰好彌補(bǔ)TF-IDF的缺點(diǎn)。TF-IDF的缺點(diǎn)在于它只是記錄單個(gè)關(guān)鍵詞對(duì)代碼文檔相似度計(jì)算方面的影響，即TF-IDF關(guān)注的是個(gè)體，而馬爾科夫模型則主要研究的是鏈，僅僅將TF-IDF值作為權(quán)重，還是會(huì)降低檢測(cè)的準(zhǔn)確度，于是將兩者有機(jī)的結(jié)合起來(lái)以達(dá)到更好的檢測(cè)效果。根據(jù)Java代碼語(yǔ)義、語(yǔ)法規(guī)范可知：代碼中所有關(guān)鍵詞存在較強(qiáng)的相關(guān)性，如Java關(guān)鍵字之間的先后關(guān)系等，并據(jù)此在Ad-Sim算法中引入馬爾科夫模型。首先建立源代碼的關(guān)鍵詞的馬爾科夫鏈；其次計(jì)算馬爾科夫鏈中前一關(guān)鍵詞到后一關(guān)鍵詞之間的馬爾科夫轉(zhuǎn)移概率，得出所有代碼中所有關(guān)鍵詞的馬爾科夫概率轉(zhuǎn)移矩陣；最后結(jié)合TF-IDF計(jì)算待檢測(cè)代碼中關(guān)鍵詞的權(quán)重。

馬爾科夫模型描述的是具有一定規(guī)律的離散狀態(tài)隨時(shí)間變化而不斷轉(zhuǎn)移的過程的模型化[14]。馬爾科夫過程是指具有馬爾科夫性的隨機(jī)過程，而參數(shù)集與狀態(tài)集均為離散的馬爾科夫過程稱為馬爾科夫鏈[15]。

在關(guān)鍵詞轉(zhuǎn)移概率矩陣的構(gòu)建中，轉(zhuǎn)移概率通過代碼庫(kù)關(guān)鍵詞各種狀態(tài)轉(zhuǎn)移出現(xiàn)的概率來(lái)獲得，即每種關(guān)鍵詞狀態(tài)轉(zhuǎn)移占代碼庫(kù)中所有狀態(tài)轉(zhuǎn)移百分比。利用馬爾科夫狀態(tài)轉(zhuǎn)移矩陣計(jì)算方法求算出現(xiàn)有代碼庫(kù)部分關(guān)鍵詞狀態(tài)轉(zhuǎn)移概率如表1所示，表1中行為前一個(gè)關(guān)鍵詞，列為后一個(gè)關(guān)鍵詞。

表1 代碼庫(kù)中部分關(guān)鍵詞狀態(tài)轉(zhuǎn)移概率Table 1 State transition probability of part keywords in code library

通過對(duì)關(guān)鍵詞TF-IDF以及馬爾科夫模型的研究，在結(jié)合TF-IDF以及馬爾科夫模型兩者計(jì)算待檢測(cè)代碼中每個(gè)關(guān)鍵詞的權(quán)重時(shí)，需要符合以下原則：

原則1權(quán)重的計(jì)算公式要體現(xiàn)出馬爾科夫模型的作用，考慮代碼中關(guān)鍵詞的前后關(guān)系，利用馬爾科夫轉(zhuǎn)移矩陣來(lái)表示代碼上下文對(duì)關(guān)鍵詞權(quán)重的影響。

原則2與關(guān)鍵詞的IDF值相結(jié)合，利用關(guān)鍵詞的IDF值來(lái)表示關(guān)鍵詞的稀有程度對(duì)權(quán)重的影響，使之能夠繼承TF-IDF的優(yōu)點(diǎn)。

原則3在條件允許的情況下適當(dāng)考慮算法的時(shí)間和空間復(fù)雜度的影響。

根據(jù)以上原則，權(quán)重計(jì)算式為

(4)

式中：i為第i個(gè)關(guān)鍵詞；jn為原代碼中第n個(gè)詞。

2.4 代碼克隆檢測(cè)步驟

根據(jù)上述算法基本思想，給出結(jié)合基于漢明距離、TF-IDF及馬爾科夫模型的代碼克隆檢測(cè)流程如圖2所示，具體步驟如下：

輸入：待檢測(cè)代碼

輸出：是否存在克隆代碼

1) 對(duì)實(shí)驗(yàn)樣本代碼進(jìn)行歸一化預(yù)處理，消除對(duì)克隆檢測(cè)無(wú)關(guān)的代碼。

2) 對(duì)實(shí)驗(yàn)樣本代碼進(jìn)行分詞處理，建立代碼關(guān)鍵詞序列，并使用mmh 3計(jì)算關(guān)鍵詞Hash值。

3) 利用TF-IDF計(jì)算代碼中所有關(guān)鍵詞權(quán)重，并結(jié)合使用馬爾科夫模型優(yōu)化關(guān)鍵詞權(quán)重，使用式(4)。

4) 在Hash值的基礎(chǔ)上進(jìn)行加權(quán)累加、合并和降維得出指紋簽名。

5) 使用漢明距離計(jì)算待檢測(cè)代碼的相似度，根據(jù)閾值判斷是否存在克隆代碼。

圖2 優(yōu)化算法代碼克隆檢測(cè)流程圖Fig.2 The flow chart of optimized code clone detection

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

3.1 實(shí)驗(yàn)數(shù)據(jù)及評(píng)價(jià)方法

實(shí)驗(yàn)選取100 組Java代碼作為測(cè)試用例，測(cè)試用例均取自開源項(xiàng)目的不同迭代版本。測(cè)試用例代碼庫(kù)中代碼總量在150 萬(wàn)行以上，代碼數(shù)量上保證了足夠的測(cè)試樣本用例，其中包含算法、框架、設(shè)計(jì)模式和應(yīng)用系統(tǒng)，在代碼復(fù)用和擴(kuò)展等方面都具有代表性。

基于改進(jìn)的Simhash算法代碼克隆檢測(cè)方法通過準(zhǔn)確率、召回率及F-Measure值等3 方面來(lái)綜合性評(píng)價(jià)。

1) 準(zhǔn)確率：用于衡量代碼克隆檢測(cè)方法的查準(zhǔn)率，通過算法檢測(cè)出正確的組數(shù)與檢測(cè)出克隆的所有組數(shù)的比值來(lái)計(jì)算。計(jì)算式為

(5)

2) 召回率：用于衡量代碼克隆檢測(cè)方法的查全率，通過算法檢測(cè)正確的結(jié)果數(shù)與人工檢測(cè)出克隆的所有組數(shù)的比值來(lái)計(jì)算。計(jì)算式為

(6)

3)F-Measure值：用于綜合評(píng)價(jià)準(zhǔn)確率及召回率，因?yàn)閱我坏臏?zhǔn)確率或召回率高并不能綜合算法檢測(cè)效果，F(xiàn)-Measure值通過準(zhǔn)確率和召回率的調(diào)和平均值來(lái)計(jì)算。計(jì)算式為

(7)

3.2 實(shí)驗(yàn)對(duì)比

3.2.1 不同K，L值下Simhash及Ad-Sim算法F-Measure比較

根據(jù)相似度判斷源代碼是否是克隆代碼，而指紋簽名長(zhǎng)度L及漢明距離K對(duì)實(shí)驗(yàn)最終結(jié)果的影響比較大，因此需要分析不同的K，L對(duì)克隆代碼檢測(cè)效果的影響，分別取不同的K，L值對(duì)Simhash算法及優(yōu)化后Ad-Sim算法進(jìn)行分析，計(jì)算克隆代碼檢測(cè)的F-Measure值。使用Simhash及Ad-Sim算法下，不同K值情況下的F值如圖3，4所示。

圖3 Ad-Sim算法下不同K，L值下F-Measure值情況Fig.3 F-Measure of Ad-Sim algorithm with different K，L

圖4 Simhash算法下不同K，L值下F-Measure值情況Fig.4 F-Measure of Simhash algorithm with different K，L

當(dāng)K取值較小時(shí)，有較高的準(zhǔn)確率但召回率很低，而K取值較大時(shí)，會(huì)導(dǎo)致檢測(cè)準(zhǔn)確率較低，此外不同位數(shù)的二進(jìn)制指紋簽名也會(huì)影響檢測(cè)準(zhǔn)確率，不同位數(shù)的指紋簽名能代表源代碼的關(guān)鍵詞信息不同。從圖3，4可知：當(dāng)K=4，L=64時(shí)，優(yōu)化后Ad-Sim算法克隆檢測(cè)的F-Measure值最大；當(dāng)K=6，L=64時(shí)，Simhash算法克隆檢測(cè)的F-Measure值最大。

3.2.2 Ad-Sim算法與Simhash，Dup，CCFinder的準(zhǔn)確率比較

確定Ad-Sim，Simhash算法K，L值后，對(duì)Simhash及Ad-Sim算法的準(zhǔn)確率及召回率進(jìn)行測(cè)試，使用Simhash算法及優(yōu)化后Ad-Sim算法計(jì)算100 組測(cè)試用例的64 位指紋簽名，并比較每組測(cè)試用例的漢明距離及相似度，漢明距離及其相似度使用文獻(xiàn)[12]中的公式計(jì)算，Simhash算法及優(yōu)化后Ad-Sim算法部分測(cè)試結(jié)果如表2所示。

表2 原算法與優(yōu)化算法漢明距離及相似度結(jié)果

Table 2 Results of Simhash and Ad-Sims’ Hamming distance and similarity

序號(hào)Simhash算法漢明距離漢明距離相似度Ad-Sim算法漢明距離漢明距離相似度150.960 940.968 8260.953 130.976 63320.750 0470.632 84410.679 7350.726 6540.968 840.968 8?????96280.781 3410.679 79750.960 930.976 698690.460 9560.562 59960.953 1390.695 310030.976 640.968 8

由表2可知：100 組實(shí)驗(yàn)中，每組實(shí)驗(yàn)的漢明距離及其相似度的原算法以及優(yōu)化后Ad-Sim算法的克隆檢測(cè)結(jié)果。表2第99 號(hào)數(shù)據(jù)中，Ad-Sim算法計(jì)算得到的漢明距離大于Simhash算法，進(jìn)一步分析發(fā)現(xiàn)該組的2 份源代碼關(guān)鍵詞詞頻接近，使用Simhash算法出現(xiàn)誤檢現(xiàn)象，而Ad-Sim算法很好地解決了該問題。將筆者提出的Ad-Sim算法與Simhash算法、Dup[3]及CCFinder[4]代碼克隆檢測(cè)工具進(jìn)行對(duì)比實(shí)驗(yàn)，表3為人工檢測(cè)與各種算法檢測(cè)的對(duì)比結(jié)果，從表3可以看出：優(yōu)化后的Ad-Sim算法在代碼克隆檢測(cè)準(zhǔn)確率及召回率相比較Simhash算法有所提高，且Ad-Sim算法相較于基于Text方法的Dup有更高的檢測(cè)準(zhǔn)確率，因?yàn)榛赥ext的方法在檢測(cè)對(duì)源代碼進(jìn)行修改后的檢測(cè)準(zhǔn)確度、召回率較低，但相對(duì)于基于Token的CCFinder的檢測(cè)準(zhǔn)確率和召回率相對(duì)較低。

表3 Simhash算法與優(yōu)化Ad-Sim算法檢測(cè)結(jié)果準(zhǔn)確率及召回率對(duì)比表

Table 3 Results of original and optimized algorithm’s precision and recall rate

檢測(cè)方法克隆組檢測(cè)組數(shù)正確組數(shù)非克隆組檢測(cè)組數(shù)正確組數(shù)準(zhǔn)確率/%召回率/%人工檢測(cè)73732727Simhash算法8065201281.2589.04Ad-Sim算法7669262190.7994.52Dup7866221584.6290.41CCFinder7571252394.6797.26

3.2.3 不同代碼量下Ad-Sim算法與Simhash算法比較

為測(cè)試代碼量對(duì)Simhash算法及優(yōu)化后Ad-Sim算法的影響，實(shí)驗(yàn)選擇代碼量大小從50 kB到800 kB，以50 kB為區(qū)間，對(duì)Simhash及Ad-Sim算法進(jìn)行準(zhǔn)確率測(cè)試。圖5為不同代碼量對(duì)各算法準(zhǔn)確率的影響，可以看出：優(yōu)化后Ad-Sim算法合適的測(cè)試代碼量范圍為250～700 kB，準(zhǔn)確率達(dá)到90%以上，代碼克隆檢測(cè)范圍優(yōu)于Simhash算法，且優(yōu)化后Ad-Sim算法的代碼克隆檢測(cè)準(zhǔn)確度更趨于穩(wěn)定。此外，在實(shí)驗(yàn)中當(dāng)代碼量小于200 kB時(shí)，由于源代碼中關(guān)鍵詞數(shù)量較少，僅通過詞頻作為權(quán)重使得Simhash算法生成的指紋信息準(zhǔn)確度不高，導(dǎo)致Simhash算法的檢測(cè)準(zhǔn)確率明顯低于Ad-Sim算法。

圖5 原算法與優(yōu)化算法隨代碼量變化下準(zhǔn)確率對(duì)比圖Fig.5 Results of original and optimized algorithm with change of code amount

4 結(jié) 論

在Charikar提出的大量網(wǎng)頁(yè)文檔查重的Simhash算法基礎(chǔ)上，提出了一種結(jié)合TF-IDF及馬爾科夫模型的改進(jìn)Simhash代碼克隆檢測(cè)算法Ad-Sim。首先對(duì)代碼進(jìn)行歸一化預(yù)處理，并進(jìn)行分詞、Hash、加權(quán)以及降維；其次在加權(quán)過程中對(duì)關(guān)鍵詞權(quán)重計(jì)算時(shí)引入TF-IDF及馬爾科夫模型；最終通過計(jì)算待檢測(cè)代碼指紋簽名與代碼庫(kù)中代碼的指紋簽名的漢明距離相似度判斷是否存在克隆代碼。通過理論分析及實(shí)驗(yàn)驗(yàn)證，與Simhash算法相比，優(yōu)化后Ad-Sim算法在檢測(cè)準(zhǔn)確率及召回率上更高，并且在少量代碼的檢測(cè)準(zhǔn)確率提升更明顯。