使用哈希值和標識符沖突率的克隆代碼檢測的誤檢消除方法

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

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

關鍵詞：克隆代碼； 哈希值； 標識符沖突率； 誤檢； 重構

中圖分類號：TP311 文獻標識碼：A 文章編號：2095-2163（2013）05-0046-04

0引言

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

克隆代碼在大多數情況下是有害無益的，因其增加了軟件系統代碼的長度，使得軟件系統愈加復雜、難以維護，同時系統運行效率也會降低，并且給軟件引入大量的程序缺陷。

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

但是，通過分析實際的程序卻發現該方法存在一些誤檢問題。首先，如圖1中程序所示（圖中++用于標記克隆的語句）。其中可以看出，（a）和（b）中的第5行克隆語句的映射發生了錯誤（（a）中的第5行語句應該映射到（b）中第5行語句的下一行語句）。其次，如圖2中程序所示。從中可以看出，由于語句順序顛倒，圖2（a）和（b）中的語句3和4的映射發生了錯誤。克隆代碼片段的映射錯誤，不僅會導致后續對克隆代碼相關缺陷檢測的誤檢，如圖3所示（由圖1中的克隆代碼檢測的誤檢引起），而且會導致錯誤的語句相似度分析，從而影響克隆代碼重構的準確性。

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

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

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

1.2克隆代碼相關軟件缺陷檢測模型

克隆代碼檢測的目的是為了解決與克隆代碼相關的問題。基于序列挖掘的C克隆代碼及相關軟件缺陷檢測模型在克隆代碼檢測后，根據其生成的克隆代碼集合以及克隆代碼相關源程序信息，進行了克隆代碼相關缺陷的檢測。

1.3標識符沖突率

為了識別標識符不一致的情況，通過計算克隆代碼對的標識符沖突率來判斷標識符不一致的發生位置。每個標識符的映射沖突率的計算公式如式（1）所示

該模型基本思路如下：首先對C源代碼進行克隆代碼檢測，然后計算克隆代碼對中每個標識符的沖突率。對于具有沖突的標識符，在上面兩步的基礎上，根據沖突發生的代碼行位置，判斷當前語句行的下一條語句與當前語句行的哈希值是否相等，如果相等，則將對應位置標識符作為當前匹配的標識符，計算標識符沖突率。如果新的標識符沖突率為零，說明發生了誤檢，則根據記錄的語句行號調整克隆代碼標記的相對行號。如果新的標識符沖突率不為零，則繼續對當前行的上一條語句計算標識符沖突率。如果當[JP3]前語句行的下一條及上一條語句均已完成了標識符沖突率的計算，結果仍不為零，則表明沒有發生誤檢，輸出當前的檢測結果即可。

2.2算法舉例

以圖1所示程序為例，在消除誤檢之前，輸出如圖3所示的缺陷檢測結果。此種誤檢產生的原因是由于插入了一條語句所致，CloSpan算法可以成功識別插入或刪除語句的克隆代碼，但圖1 （b） 中插入的是與克隆語句結構相同的語句，這種結構相同的語句則映射成相同的數字。以圖1為例，即語句ll_puts （ buf ） 和語句va_end（args）均映射成相同的數字（76781968），數據挖掘之后，算法就誤將語句（b）中的ll_puts （ buf ）與（a）中的va_end（args）當作克隆語句，進行匹配。這種錯誤的匹配將導致后續克隆代碼相關缺陷檢測的誤檢，仍如圖3所示。

基于本文方法，首先，根據當前的標識符沖突率（1/4），記錄當前沖突發生的位置（語句的行號），判斷當前語句的下一條語句與當前語句的哈希值是否相等，即兩條語句是否是結構相同；然后，將下一條語句對應位置的標識作為將匹配的標識符，重新計算標識符沖突率。如果沖突率為零，則說明當前語句的下一條語句是真正的克隆語句，進而，將當前語句的行號與下一條語句的行號交換，修正克隆代碼檢測結果。結果如圖6所示。

這種方法不僅消除了插入語句的克隆代碼的誤檢，而且，還消除了語句結構相同（數字相同）而語句順序顛倒產生的誤檢。如果沖突率不為零，則說明當前語句的下一條語句不是真正的克隆語句。此時，本文方法繼續判斷當前語句的上一條語句與當前語句的哈希值是否相等，即兩條語句是否為相同結構的語句，如果相等，則將上一條語句對應位置的標識符作為被匹配的標識符，重新計算標識符沖突率。如果沖突率為零，則說明當前語句的上一條語句是真正的克隆語句，進而，將當前語句的行號與下一條語句的行號交換，修正克隆代碼檢測結果。如果當前語句行的下一條及上一條語句計算完成標識符沖突率后，結果仍不為零，則表明沒有發生誤檢，即輸出當前的檢測結果。

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

針對基于token的克隆代碼檢測方法進行語法相似的克隆代碼檢測時存在的部分誤檢問題，本文提出了一種克隆代碼檢測的部分誤檢消除的方法。該算法通過語句哈希值的比較找到結構相同的語句，再根據標識符沖突率確定誤檢消除情況。實驗結果表明，本文算法能夠消除傳統克隆代碼檢測方法中的部分誤檢，提高了克隆代碼檢測的準確性。