摘  要： 克隆代碼會導(dǎo)致項(xiàng)目的維護(hù)困難，削弱項(xiàng)目的健壯性,，并且克隆代碼中所包含的bug會破壞整個項(xiàng)目,。當(dāng)前克隆代碼檢測技術(shù)或者拘泥于只能檢測少數(shù)幾種克隆代碼，或者需要極高的檢測時間,。而且如果需要檢測大量的源代碼,，一臺機(jī)器的主存也許無法存儲所有的信息。對克隆代碼檢測技術(shù)的并行運(yùn)行進(jìn)行了可能性研究,，使用基于程序依賴圖的克隆代碼檢測技術(shù),，這種技術(shù)不僅可以檢測出語法上的克隆，也可以檢測出語義上的克隆,，提出了一個并行子圖同構(gòu)檢測方法并使用MapReduce并行實(shí)現(xiàn),，實(shí)驗(yàn)結(jié)果極大地提高了該方法的運(yùn)行速度。
關(guān)鍵詞： 克隆代碼,；程序依賴圖,；同構(gòu)匹配檢測,；Hadoop

    在軟件項(xiàng)目的開發(fā)過程中，由于能夠降低開發(fā)者的工作量,，“復(fù)制粘貼”也許是最常使用的操作,。但這也帶來了克隆代碼的問題。
    克隆代碼的存在給軟件維護(hù)帶來了困難,，當(dāng)開發(fā)者試圖修改代碼時，他們很可能修改了克隆代碼中的一處而忘記了別的地方,，這顯然會帶來代碼的不一致,。為了避免這個難題，大量的克隆代碼檢測技術(shù)被提出,。但問題在于克隆代碼的精確定義本身就不明確,，現(xiàn)有的每一種方法都有其對于克隆代碼自己的定義。因此,，同樣的源代碼,，如果用不同的克隆代碼檢測方法檢測，可能會得到完全不同的結(jié)果,。
    基于程序依賴圖的方法能夠探測語義克隆代碼,，而且它還具有一個其他方法所不具有的能力：能夠探測非連續(xù)性的克隆代碼[1]。非連續(xù)性的克隆代碼是被其他代碼或文件所分割開來的克隆代碼,，克隆代碼中的代碼并不是連續(xù)的,。而開發(fā)者往往會在粘貼克隆代碼后做一些修改，這樣,，基于程序依賴圖的檢測方法就能夠檢測出這種克隆代碼,。
    但是基于程序依賴圖的方法有一個很大的缺點(diǎn)，即運(yùn)行非常緩慢,。程序依賴圖的同構(gòu)檢測是著名的圖同構(gòu)匹配問題,，該問題為NP完全問題，需要指數(shù)級的時間復(fù)雜度,，這導(dǎo)致了運(yùn)行時間呈指數(shù)級增長,。
    本文提出了一種并行執(zhí)行程序依賴圖同構(gòu)匹配的方法。通過使用這種方法,，減少了這一特定問題的圖同構(gòu)匹配算法所需要的時間,。并使用MapReduce這一流行的并行框架來并行該方法。
1 背景知識
1.1 程序依賴圖
    程序依賴圖是一個有向圖,，該圖的頂點(diǎn)代表了源代碼中的代碼,，而邊代表了兩個頂點(diǎn)之間的依賴。在程序依賴圖中只有兩種邊：代表控制依賴的邊和代表數(shù)據(jù)依賴的邊,。以下展示了一個源代碼的例子,，圖1為該源代碼所產(chǎn)生的程序依賴圖,。

    #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]是一個流行的編程模型，該模型能夠通過一個運(yùn)行在集群上的并行的,、分布式的算法對大數(shù)據(jù)集進(jìn)行處理,。它提供了一個簡單易用的并行算法編程框架，使用該框架的開發(fā)者只需要定義兩個函數(shù)：Map和Reduce,。原始數(shù)據(jù)被該框架轉(zhuǎn)換成鍵值對,，每一個Map進(jìn)程每一次處理一個鍵值對（key，value）：
    Map:  <k1, v1> → <k2, v2>
    Map函數(shù)在集群中并行執(zhí)行,，MapReduce框架將所有相同的key的鍵值對傳遞給一個Reduce函數(shù),。Reduce函數(shù)產(chǎn)生最終的結(jié)果：
    Reduce: <k2,v2> → <k3,v3>
2 程序設(shè)計算法
    首先把源代碼轉(zhuǎn)換成以靜態(tài)形式表示數(shù)據(jù)流和控制流的程序依賴圖，將其記為s-PDG,。程序依賴圖的節(jié)點(diǎn)代表了源代碼中的語句(聲明,、賦值、表達(dá)式,、控制邏輯等),，同時記錄所有節(jié)點(diǎn)對應(yīng)源代碼的類別以便在后面的比對中使用。然后選擇一段程序塊所對應(yīng)的s-PDG的子圖,，作為查找與圖同構(gòu)的樣本,，將這個子圖記為b-PDG。隨后對s-PDG和b-PDG進(jìn)行比對,，以檢測除了b-PDG本身以外是否還有別的s-PDG的子圖與b-PDG同構(gòu),。如果有，則這個子圖所對應(yīng)的代碼就與b-PDG對應(yīng)的程序塊為克隆代碼,。
    經(jīng)典的算法在檢測子圖同構(gòu)時只能順序執(zhí)行,，本文所要做的是將s-PDG切分成多個小圖，然后并行子圖同構(gòu)檢測,。在論述切分s-PDG的方法之前,，先給出會在切分中使用的偽圓的定義。
    在圖G=（V,，E）中,，任給A∈V，以A為圓心,，以一個正數(shù)為半徑,，對于任意節(jié)點(diǎn)B∈V，如果AB之間的最短路徑長度(對于邊無權(quán)值的圖,，最短路徑長度為最短路徑所經(jīng)過的節(jié)點(diǎn)的個數(shù))小于半徑,，則B位于該偽圓中。當(dāng)計算最短路徑時忽略邊的方向,。
    按照參考文獻(xiàn)[3]中提出的方法切割s-PDG：
    (1)根據(jù)s-PDG節(jié)點(diǎn)的種類分別計數(shù),。

    (2)取出s-PDG中數(shù)量最少的節(jié)點(diǎn)的種類,，將其記為種類l。然后選取出b-PDG中屬于種類l的節(jié)點(diǎn),。如果b-PDG中沒有種類l的節(jié)點(diǎn),，則變更種類l為s-PDG中第二少種類的節(jié)點(diǎn)。如果種類l仍然在b-PDG中沒有節(jié)點(diǎn),，則繼續(xù)變更種類l為s-PDG中第三少種類的節(jié)點(diǎn),，直到b-PDG中存在種類l的節(jié)點(diǎn)。
    (3)計算s-PDG中所有這些種類l的節(jié)點(diǎn)與其他節(jié)點(diǎn)的距離,，將最大值定為偽半徑,。
    (4)以上面計算出的偽半徑，以s-PDG中種類為l的節(jié)點(diǎn)為圓心,，可以得到一些偽圓。這些偽圓就是切割s-PDG的最終結(jié)果,。將它們記為c-PDG的集合,。
    在查找同構(gòu)子圖的過程中必須檢查節(jié)點(diǎn)的種類，對應(yīng)的節(jié)點(diǎn)必須有同樣的種類,。所以同構(gòu)子圖必須有種類為l的節(jié)點(diǎn),。考慮到b-PDG的尺寸大小,，在s-PDG中的節(jié)點(diǎn)如果距步驟(4)中選取的圓心距離過大,，則這些節(jié)點(diǎn)不可能處于同構(gòu)子圖中，因此可以把這些節(jié)點(diǎn)切除不再考慮,。
    該算法的基本流程如圖2所示,。

3 算法的實(shí)現(xiàn)
    使用JavaPDG[4]生成整個項(xiàng)目的程序依賴圖。JavaPDG是一個靜態(tài)的Java字節(jié)碼分析器,。這個工具能夠產(chǎn)生各種不同的對源代碼的圖形展示,，例如系統(tǒng)依賴圖、程序依賴圖,、控制流圖和函數(shù)調(diào)用圖。
    使用Hadoop[5](一個MapReduce框架的開源實(shí)現(xiàn))來并行這個子圖集的同構(gòu)匹配,。
    使用Igraph[6]來檢測子圖同構(gòu)匹配,。Igraph是一個針對圖的操作的開源軟件包，由于Igraph是用C語言寫成的,，必須通過Hadoop流來將這個軟件包用于并行同構(gòu)檢測,。
4 實(shí)驗(yàn)與評價
    通過對兩個開源項(xiàng)目的檢測來評價本文的算法，結(jié)果如表1所示,。通過代碼行數(shù)和對應(yīng)程序依賴圖的節(jié)點(diǎn)和邊的個數(shù)來對比項(xiàng)目的大小,。將經(jīng)典PDG匹配算法與以3臺機(jī)器組成的集群上并行為例的本文算法所消耗的時間進(jìn)行了比較,。

    結(jié)果顯示，本文算法極大地提高了同構(gòu)匹配的性能,，經(jīng)典的程序依賴圖同構(gòu)匹配算法需要花費(fèi)幾個小時,，而本文并行算法僅僅花費(fèi)幾分鐘。這是因?yàn)椴⑿兴惴ㄒ瞥顺绦蛞蕾噲D中的部分節(jié)點(diǎn),，而且并行了同構(gòu)匹配的過程,。
    本文提出了一種提高基于程序依賴圖的克隆代碼檢測性能的方法。把程序依賴圖分割成若干個小圖并使用Hadoop并行執(zhí)行子圖同構(gòu)檢測,，使得算法的性能得到了提高,。使用兩個得到廣泛使用的開源項(xiàng)目來測試本文算法，測試結(jié)果顯示該算法顯著地提高了克隆代碼檢測的性能,。
參考文獻(xiàn)
[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.