使用哈希值和標(biāo)識(shí)符沖突率的克隆代碼檢測(cè)的誤檢消除方法

邊奕心　王甜甜　蘇小紅　馬培軍

摘要：針對(duì)采用基于token的克隆代碼檢測(cè)方法檢測(cè)語法相似的克隆代碼時(shí)存在的部分誤檢問題，提出一種使用哈希值和標(biāo)識(shí)符沖突率來消除克隆代碼檢測(cè)的部分誤檢的方法。該方法首先通過語句的哈希值判斷語句結(jié)構(gòu)的相似性，然后計(jì)算標(biāo)識(shí)符沖突率，通過沖突率的變化，來確定誤檢消除的方向和消除情況。對(duì)于存在誤檢的克隆代碼，最終通過修改克隆代碼的相對(duì)行號(hào)來消除誤檢。實(shí)驗(yàn)結(jié)果表明，提出的方法可以消除由于插入結(jié)構(gòu)相同的語句而引起的克隆代碼的誤檢問題，并在此基礎(chǔ)上，有效消除了語句形式一樣但由于語句順序顛倒而引起的克隆代碼誤檢問題，提高了克隆代碼檢測(cè)及克隆代碼相關(guān)缺陷檢測(cè)的準(zhǔn)確性，有利于后續(xù)克隆代碼重構(gòu)的研究。

關(guān)鍵詞：克隆代碼； 哈希值； 標(biāo)識(shí)符沖突率； 誤檢； 重構(gòu)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-2163（2013）05-0046-04

0引言

克隆代碼（Cloned Code），又稱作重復(fù)代碼（Duplicated Code），是指源代碼文件中多個(gè)相同或相似的代碼片段[1]。

克隆代碼在大多數(shù)情況下是有害無益的，因其增加了軟件系統(tǒng)代碼的長(zhǎng)度，使得軟件系統(tǒng)愈加復(fù)雜、難以維護(hù)，同時(shí)系統(tǒng)運(yùn)行效率也會(huì)降低，并且給軟件引入大量的程序缺陷。

近年來，代碼克隆的研究已成為軟件工程領(lǐng)域的前沿課題。各國(guó)的軟件研究人員競(jìng)相提出了多種檢測(cè)克隆代碼的方法，并陸續(xù)開發(fā)了多款自動(dòng)檢測(cè)大規(guī)模軟件系統(tǒng)中克隆代碼的工具[2]。國(guó)際上研究克隆代碼檢測(cè)的國(guó)家主要有日本、美國(guó)、英國(guó)等。國(guó)內(nèi)研究克隆代碼檢測(cè)的科研院所主要有南京大學(xué)[3]、大連理工大學(xué)[4]和汕頭大學(xué)[5]等。ZhenminLi和Shan Lu 等人在文獻(xiàn)[6]中將數(shù)據(jù)挖掘與克隆代碼檢測(cè)結(jié)合，開發(fā)了克隆代碼檢測(cè)工具CP-Miner。另外，高效的序列模式挖掘算法既可顯著提升檢測(cè)速度，降低時(shí)間復(fù)雜性，也可以容忍經(jīng)過增、刪、改和變量重命名的克隆代碼片段，并且對(duì)“拷貝-粘貼-修改”行為所導(dǎo)致的變量重命名不一致的軟件缺陷也能即時(shí)進(jìn)行檢測(cè)。

但是，通過分析實(shí)際的程序卻發(fā)現(xiàn)該方法存在一些誤檢問題。首先，如圖1中程序所示（圖中++用于標(biāo)記克隆的語句）。其中可以看出，（a）和（b）中的第5行克隆語句的映射發(fā)生了錯(cuò)誤（（a）中的第5行語句應(yīng)該映射到（b）中第5行語句的下一行語句）。其次，如圖2中程序所示。從中可以看出，由于語句順序顛倒，圖2（a）和（b）中的語句3和4的映射發(fā)生了錯(cuò)誤?？寺〈a片段的映射錯(cuò)誤，不僅會(huì)導(dǎo)致后續(xù)對(duì)克隆代碼相關(guān)缺陷檢測(cè)的誤檢，如圖3所示（由圖1中的克隆代碼檢測(cè)的誤檢引起），而且會(huì)導(dǎo)致錯(cuò)誤的語句相似度分析，從而影響克隆代碼重構(gòu)的準(zhǔn)確性。

為解決上述問題，本文提出了使用語句哈希值和標(biāo)識(shí)符沖突率來消除克隆代碼部分誤檢的方法。該方法不僅可以處理由于插入相同語法結(jié)構(gòu)的語句而導(dǎo)致的克隆代碼的誤檢問題，而且還可以消除語句形式一樣但由于語句順序顛倒而引起的克隆代碼誤檢問題。通過分析實(shí)際的程序代碼證明本文方法可以增強(qiáng)克隆代碼檢測(cè)能力及提高克隆代碼相關(guān)缺陷檢測(cè)的準(zhǔn)確性。

1.1基于頻繁子序列挖掘克隆代碼檢測(cè)模型

基于頻繁子序列挖掘克隆代碼檢測(cè)模型[3]可將程序代碼轉(zhuǎn)化為token串，再將token串轉(zhuǎn)化為數(shù)字序列（每一行語句映射成一個(gè)數(shù)字），相同結(jié)構(gòu)的語句則映射成相同的數(shù)字，如圖1所示，生成數(shù)字序列數(shù)據(jù)庫(kù)。引入數(shù)據(jù)挖掘算法中頻繁子序列挖掘技術(shù)，將重復(fù)代碼檢測(cè)轉(zhuǎn)化為序列挖掘問題，解決了以往算法時(shí)間復(fù)雜度過高，且不能識(shí)別經(jīng)過修改的拷貝-粘貼代碼的缺點(diǎn)。

1.2克隆代碼相關(guān)軟件缺陷檢測(cè)模型

克隆代碼檢測(cè)的目的是為了解決與克隆代碼相關(guān)的問題?；谛蛄型诰虻腃克隆代碼及相關(guān)軟件缺陷檢測(cè)模型在克隆代碼檢測(cè)后，根據(jù)其生成的克隆代碼集合以及克隆代碼相關(guān)源程序信息，進(jìn)行了克隆代碼相關(guān)缺陷的檢測(cè)。

1.3標(biāo)識(shí)符沖突率

為了識(shí)別標(biāo)識(shí)符不一致的情況，通過計(jì)算克隆代碼對(duì)的標(biāo)識(shí)符沖突率來判斷標(biāo)識(shí)符不一致的發(fā)生位置。每個(gè)標(biāo)識(shí)符的映射沖突率的計(jì)算公式如式（1）所示

該模型基本思路如下：首先對(duì)C源代碼進(jìn)行克隆代碼檢測(cè)，然后計(jì)算克隆代碼對(duì)中每個(gè)標(biāo)識(shí)符的沖突率。對(duì)于具有沖突的標(biāo)識(shí)符，在上面兩步的基礎(chǔ)上，根據(jù)沖突發(fā)生的代碼行位置，判斷當(dāng)前語句行的下一條語句與當(dāng)前語句行的哈希值是否相等，如果相等，則將對(duì)應(yīng)位置標(biāo)識(shí)符作為當(dāng)前匹配的標(biāo)識(shí)符，計(jì)算標(biāo)識(shí)符沖突率。如果新的標(biāo)識(shí)符沖突率為零，說明發(fā)生了誤檢，則根據(jù)記錄的語句行號(hào)調(diào)整克隆代碼標(biāo)記的相對(duì)行號(hào)。如果新的標(biāo)識(shí)符沖突率不為零，則繼續(xù)對(duì)當(dāng)前行的上一條語句計(jì)算標(biāo)識(shí)符沖突率。如果當(dāng)[JP3]前語句行的下一條及上一條語句均已完成了標(biāo)識(shí)符沖突率的計(jì)算，結(jié)果仍不為零，則表明沒有發(fā)生誤檢，輸出當(dāng)前的檢測(cè)結(jié)果即可。

2.2算法舉例

以圖1所示程序?yàn)槔谙`檢之前，輸出如圖3所示的缺陷檢測(cè)結(jié)果。此種誤檢產(chǎn)生的原因是由于插入了一條語句所致，CloSpan算法可以成功識(shí)別插入或刪除語句的克隆代碼，但圖1 （b） 中插入的是與克隆語句結(jié)構(gòu)相同的語句，這種結(jié)構(gòu)相同的語句則映射成相同的數(shù)字。以圖1為例，即語句ll_puts （ buf ） 和語句va_end（args）均映射成相同的數(shù)字（76781968），數(shù)據(jù)挖掘之后，算法就誤將語句（b）中的ll_puts （ buf ）與（a）中的va_end（args）當(dāng)作克隆語句，進(jìn)行匹配。這種錯(cuò)誤的匹配將導(dǎo)致后續(xù)克隆代碼相關(guān)缺陷檢測(cè)的誤檢，仍如圖3所示。

基于本文方法，首先，根據(jù)當(dāng)前的標(biāo)識(shí)符沖突率（1/4），記錄當(dāng)前沖突發(fā)生的位置（語句的行號(hào)），判斷當(dāng)前語句的下一條語句與當(dāng)前語句的哈希值是否相等，即兩條語句是否是結(jié)構(gòu)相同；然后，將下一條語句對(duì)應(yīng)位置的標(biāo)識(shí)作為將匹配的標(biāo)識(shí)符，重新計(jì)算標(biāo)識(shí)符沖突率。如果沖突率為零，則說明當(dāng)前語句的下一條語句是真正的克隆語句，進(jìn)而，將當(dāng)前語句的行號(hào)與下一條語句的行號(hào)交換，修正克隆代碼檢測(cè)結(jié)果。結(jié)果如圖6所示。

這種方法不僅消除了插入語句的克隆代碼的誤檢，而且，還消除了語句結(jié)構(gòu)相同（數(shù)字相同）而語句順序顛倒產(chǎn)生的誤檢。如果沖突率不為零，則說明當(dāng)前語句的下一條語句不是真正的克隆語句。此時(shí)，本文方法繼續(xù)判斷當(dāng)前語句的上一條語句與當(dāng)前語句的哈希值是否相等，即兩條語句是否為相同結(jié)構(gòu)的語句，如果相等，則將上一條語句對(duì)應(yīng)位置的標(biāo)識(shí)符作為被匹配的標(biāo)識(shí)符，重新計(jì)算標(biāo)識(shí)符沖突率。如果沖突率為零，則說明當(dāng)前語句的上一條語句是真正的克隆語句，進(jìn)而，將當(dāng)前語句的行號(hào)與下一條語句的行號(hào)交換，修正克隆代碼檢測(cè)結(jié)果。如果當(dāng)前語句行的下一條及上一條語句計(jì)算完成標(biāo)識(shí)符沖突率后，結(jié)果仍不為零，則表明沒有發(fā)生誤檢，即輸出當(dāng)前的檢測(cè)結(jié)果。

文中采用克隆代碼檢測(cè)工具CPBugdetector[7]分別對(duì)Linux_2.6.6源程序中的arch、net和kernel模塊進(jìn)行克隆代碼及相關(guān)缺陷檢測(cè)。比較消除誤檢之前和消除誤檢之后的缺陷檢測(cè)結(jié)果如表1所示。

針對(duì)基于token的克隆代碼檢測(cè)方法進(jìn)行語法相似的克隆代碼檢測(cè)時(shí)存在的部分誤檢問題，本文提出了一種克隆代碼檢測(cè)的部分誤檢消除的方法。該算法通過語句哈希值的比較找到結(jié)構(gòu)相同的語句，再根據(jù)標(biāo)識(shí)符沖突率確定誤檢消除情況。實(shí)驗(yàn)結(jié)果表明，本文算法能夠消除傳統(tǒng)克隆代碼檢測(cè)方法中的部分誤檢，提高了克隆代碼檢測(cè)的準(zhǔn)確性。