摘 要： 克隆代碼會導致項目的維護困難，削弱項目的健壯性，并且克隆代碼中所包含的bug會破壞整個項目。當前克隆代碼檢測技術或者拘泥于只能檢測少數幾種克隆代碼，或者需要極高的檢測時間。而且如果需要檢測大量的源代碼，一臺機器的主存也許無法存儲所有的信息。對克隆代碼檢測技術的并行運行進行了可能性研究，使用基于程序依賴圖的克隆代碼檢測技術，這種技術不僅可以檢測出語法上的克隆，也可以檢測出語義上的克隆，提出了一個并行子圖同構檢測方法并使用MapReduce并行實現，實驗結果極大地提高了該方法的運行速度。
關鍵詞： 克隆代碼；程序依賴圖；同構匹配檢測；Hadoop
在軟件項目的開發過程中，由于能夠降低開發者的工作量，“復制粘貼”也許是最常使用的操作。但這也帶來了克隆代碼的問題。
克隆代碼的存在給軟件維護帶來了困難，當開發者試圖修改代碼時，他們很可能修改了克隆代碼中的一處而忘記了別的地方，這顯然會帶來代碼的不一致。為了避免這個難題，大量的克隆代碼檢測技術被提出。但問題在于克隆代碼的精確定義本身就不明確，現有的每一種方法都有其對于克隆代碼自己的定義。因此，同樣的源代碼，如果用不同的克隆代碼檢測方法檢測，可能會得到完全不同的結果。
基于程序依賴圖的方法能夠探測語義克隆代碼，而且它還具有一個其他方法所不具有的能力：能夠探測非連續性的克隆代碼[1]。非連續性的克隆代碼是被其他代碼或文件所分割開來的克隆代碼，克隆代碼中的代碼并不是連續的。而開發者往往會在粘貼克隆代碼后做一些修改，這樣，基于程序依賴圖的檢測方法就能夠檢測出這種克隆代碼。
但是基于程序依賴圖的方法有一個很大的缺點，即運行非常緩慢。程序依賴圖的同構檢測是著名的圖同構匹配問題，該問題為NP完全問題，需要指數級的時間復雜度，這導致了運行時間呈指數級增長。
本文提出了一種并行執行程序依賴圖同構匹配的方法。通過使用這種方法，減少了這一特定問題的圖同構匹配算法所需要的時間。并使用MapReduce這一流行的并行框架來并行該方法。
1 背景知識
1.1 程序依賴圖
程序依賴圖是一個有向圖，該圖的頂點代表了源代碼中的代碼，而邊代表了兩個頂點之間的依賴。在程序依賴圖中只有兩種邊：代表控制依賴的邊和代表數據依賴的邊。以下展示了一個源代碼的例子，圖1為該源代碼所產生的程序依賴圖。
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define BUFFER_SIZE 1024
#define DELIM "\t"
int main(int argc, char *argv[]){
char strLastKey[BUFFER_SIZE];
char strLine[BUFFER_SIZE];
int count = 0;
*strLastKey = '\0';
*strLine = '\0';
while( fgets(strLine, BUFFER_SIZE - 1, stdin) ){
char *strCurrKey = NULL;
char *strCurrNum = NULL;
strCurrKey = strtok(strLine, DELIM);
strCurrNum = strtok(NULL, DELIM);
/* necessary to check error but.... */
if( strLastKey[0] == '\0'){
strcpy(strLastKey, strCurrKey);
}
if(strcmp(strCurrKey, strLastKey)){
printf("%s\t%d\n", strLastKey, count);
count = atoi(strCurrNum);
}else{
count += atoi(strCurrNum);
}
strcpy(strLastKey, strCurrKey);
}
printf("%s\t%d\n", strLastKey, count);
/* flush the count */
return 0;
}
1.2 MapReduce
MapReduce[2]是一個流行的編程模型，該模型能夠通過一個運行在集群上的并行的、分布式的算法對大數據集進行處理。它提供了一個簡單易用的并行算法編程框架，使用該框架的開發者只需要定義兩個函數：Map和Reduce。原始數據被該框架轉換成鍵值對，每一個Map進程每一次處理一個鍵值對（key，value）：
Map: <k1, v1> → <k2, v2>
Map函數在集群中并行執行，MapReduce框架將所有相同的key的鍵值對傳遞給一個Reduce函數。Reduce函數產生最終的結果：
Reduce: <k2,v2> → <k3,v3>
2 程序設計算法
首先把源代碼轉換成以靜態形式表示數據流和控制流的程序依賴圖，將其記為s-PDG。程序依賴圖的節點代表了源代碼中的語句(聲明、賦值、表達式、控制邏輯等)，同時記錄所有節點對應源代碼的類別以便在后面的比對中使用。然后選擇一段程序塊所對應的s-PDG的子圖，作為查找與圖同構的樣本，將這個子圖記為b-PDG。隨后對s-PDG和b-PDG進行比對，以檢測除了b-PDG本身以外是否還有別的s-PDG的子圖與b-PDG同構。如果有，則這個子圖所對應的代碼就與b-PDG對應的程序塊為克隆代碼。
經典的算法在檢測子圖同構時只能順序執行，本文所要做的是將s-PDG切分成多個小圖，然后并行子圖同構檢測。在論述切分s-PDG的方法之前，先給出會在切分中使用的偽圓的定義。
在圖G=（V，E）中，任給A∈V，以A為圓心，以一個正數為半徑，對于任意節點B∈V，如果AB之間的最短路徑長度(對于邊無權值的圖，最短路徑長度為最短路徑所經過的節點的個數)小于半徑，則B位于該偽圓中。當計算最短路徑時忽略邊的方向。
按照參考文獻[3]中提出的方法切割s-PDG：
(1)根據s-PDG節點的種類分別計數。
(2)取出s-PDG中數量最少的節點的種類，將其記為種類l。然后選取出b-PDG中屬于種類l的節點。如果b-PDG中沒有種類l的節點，則變更種類l為s-PDG中第二少種類的節點。如果種類l仍然在b-PDG中沒有節點，則繼續變更種類l為s-PDG中第三少種類的節點，直到b-PDG中存在種類l的節點。
(3)計算s-PDG中所有這些種類l的節點與其他節點的距離，將最大值定為偽半徑。
(4)以上面計算出的偽半徑，以s-PDG中種類為l的節點為圓心，可以得到一些偽圓。這些偽圓就是切割s-PDG的最終結果。將它們記為c-PDG的集合。
在查找同構子圖的過程中必須檢查節點的種類，對應的節點必須有同樣的種類。所以同構子圖必須有種類為l的節點。考慮到b-PDG的尺寸大小，在s-PDG中的節點如果距步驟(4)中選取的圓心距離過大，則這些節點不可能處于同構子圖中，因此可以把這些節點切除不再考慮。
該算法的基本流程如圖2所示。
3 算法的實現
使用JavaPDG[4]生成整個項目的程序依賴圖。JavaPDG是一個靜態的Java字節碼分析器。這個工具能夠產生各種不同的對源代碼的圖形展示，例如系統依賴圖、程序依賴圖、控制流圖和函數調用圖。
使用Hadoop[5](一個MapReduce框架的開源實現)來并行這個子圖集的同構匹配。
使用Igraph[6]來檢測子圖同構匹配。Igraph是一個針對圖的操作的開源軟件包，由于Igraph是用C語言寫成的，必須通過Hadoop流來將這個軟件包用于并行同構檢測。
4 實驗與評價
通過對兩個開源項目的檢測來評價本文的算法，結果如表1所示。通過代碼行數和對應程序依賴圖的節點和邊的個數來對比項目的大小。將經典PDG匹配算法與以3臺機器組成的集群上并行為例的本文算法所消耗的時間進行了比較。
結果顯示，本文算法極大地提高了同構匹配的性能，經典的程序依賴圖同構匹配算法需要花費幾個小時，而本文并行算法僅僅花費幾分鐘。這是因為并行算法移除了程序依賴圖中的部分節點，而且并行了同構匹配的過程。
本文提出了一種提高基于程序依賴圖的克隆代碼檢測性能的方法。把程序依賴圖分割成若干個小圖并使用Hadoop并行執行子圖同構檢測，使得算法的性能得到了提高。使用兩個得到廣泛使用的開源項目來測試本文算法，測試結果顯示該算法顯著地提高了克隆代碼檢測的性能。
參考文獻
[1] 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.
[2] DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM, 2008，51(1)：107-113.
[3] LI J，ERNST M D.CBCD：cloned buggy code detector[C]. ICSE 34th International Conference on Software Engineering, 2012：310-320.
[4] SHU G，SUN B, HENDERSON T A，et al.JavaPDG：a new platform for program dependence analysis[C].In Proceedings of the 6th IEEE International Conference on Software Testing，Verification and Validation, Testing Tools Track，Luxembourg，2013：18-22.
[5] Hadoop.The apache software foundation[EB/OL].[2013-09-10].http：//hadoop.apache.org/.
[6] CSARDI G，NEPUSZ T.The igraph software package for complex network research[C].InterJournal，Complex Systems, 1695.2006.