Hadoop集群下的并行克隆代碼檢測(cè)*

葉 林，姚國(guó)祥

（暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州510632）

在軟件項(xiàng)目的開發(fā)過程中，由于能夠降低開發(fā)者的工作量，“復(fù)制粘貼”也許是最常使用的操作。但這也帶來(lái)了克隆代碼的問題。

克隆代碼的存在給軟件維護(hù)帶來(lái)了困難，當(dāng)開發(fā)者試圖修改代碼時(shí)，他們很可能修改了克隆代碼中的一處而忘記了別的地方，這顯然會(huì)帶來(lái)代碼的不一致。為了避免這個(gè)難題，大量的克隆代碼檢測(cè)技術(shù)被提出。但問題在于克隆代碼的精確定義本身就不明確，現(xiàn)有的每一種方法都有其對(duì)于克隆代碼自己的定義。因此，同樣的源代碼，如果用不同的克隆代碼檢測(cè)方法檢測(cè)，可能會(huì)得到完全不同的結(jié)果。

基于程序依賴圖的方法能夠探測(cè)語(yǔ)義克隆代碼，而且它還具有一個(gè)其他方法所不具有的能力：能夠探測(cè)非連續(xù)性的克隆代碼[1]。非連續(xù)性的克隆代碼是被其他代碼或文件所分割開來(lái)的克隆代碼，克隆代碼中的代碼并不是連續(xù)的。而開發(fā)者往往會(huì)在粘貼克隆代碼后做一些修改，這樣，基于程序依賴圖的檢測(cè)方法就能夠檢測(cè)出這種克隆代碼。

但是基于程序依賴圖的方法有一個(gè)很大的缺點(diǎn)，即運(yùn)行非常緩慢。程序依賴圖的同構(gòu)檢測(cè)是著名的圖同構(gòu)匹配問題，該問題為NP完全問題，需要指數(shù)級(jí)的時(shí)間復(fù)雜度，這導(dǎo)致了運(yùn)行時(shí)間呈指數(shù)級(jí)增長(zhǎng)。

本文提出了一種并行執(zhí)行程序依賴圖同構(gòu)匹配的方法。通過使用這種方法，減少了這一特定問題的圖同構(gòu)匹配算法所需要的時(shí)間。并使用MapReduce這一流行的并行框架來(lái)并行該方法。

1 背景知識(shí)

1.1 程序依賴圖

程序依賴圖是一個(gè)有向圖，該圖的頂點(diǎn)代表了源代碼中的代碼，而邊代表了兩個(gè)頂點(diǎn)之間的依賴。在程序依賴圖中只有兩種邊：代表控制依賴的邊和代表數(shù)據(jù)依賴的邊。以下展示了一個(gè)源代碼的例子，圖1為該源代碼所產(chǎn)生的程序依賴圖。

1.2 MapReduce

MapReduce[2]是一個(gè)流行的編程模型，該模型能夠通過一個(gè)運(yùn)行在集群上的并行的、分布式的算法對(duì)大數(shù)據(jù)集進(jìn)行處理。它提供了一個(gè)簡(jiǎn)單易用的并行算法編程框架，使用該框架的開發(fā)者只需要定義兩個(gè)函數(shù)：Map和Reduce。原始數(shù)據(jù)被該框架轉(zhuǎn)換成鍵值對(duì)，每一個(gè)Map進(jìn)程每一次處理一個(gè)鍵值對(duì)（key，value）：

Map函數(shù)在集群中并行執(zhí)行，MapReduce框架將所有相同的key的鍵值對(duì)傳遞給一個(gè)Reduce函數(shù)。Reduce函數(shù)產(chǎn)生最終的結(jié)果：

2 程序設(shè)計(jì)算法

圖1 由源代碼產(chǎn)生的程序依賴圖

首先把源代碼轉(zhuǎn)換成以靜態(tài)形式表示數(shù)據(jù)流和控制流的程序依賴圖，將其記為s-PDG。程序依賴圖的節(jié)點(diǎn)代表了源代碼中的語(yǔ)句(聲明、賦值、表達(dá)式、控制邏輯等)，同時(shí)記錄所有節(jié)點(diǎn)對(duì)應(yīng)源代碼的類別以便在后面的比對(duì)中使用。然后選擇一段程序塊所對(duì)應(yīng)的s-PDG的子圖，作為查找與圖同構(gòu)的樣本，將這個(gè)子圖記為b-PDG。隨后對(duì)s-PDG和b-PDG進(jìn)行比對(duì)，以檢測(cè)除了b-PDG本身以外是否還有別的s-PDG的子圖與b-PDG同構(gòu)。如果有，則這個(gè)子圖所對(duì)應(yīng)的代碼就與b-PDG對(duì)應(yīng)的程序塊為克隆代碼。

經(jīng)典的算法在檢測(cè)子圖同構(gòu)時(shí)只能順序執(zhí)行，本文所要做的是將s-PDG切分成多個(gè)小圖，然后并行子圖同構(gòu)檢測(cè)。在論述切分s-PDG的方法之前，先給出會(huì)在切分中使用的偽圓的定義。

在圖 G=（V，E）中，任給 A∈V，以 A 為圓心，以一個(gè)正數(shù)為半徑，對(duì)于任意節(jié)點(diǎn)B∈V，如果AB之間的最短路徑長(zhǎng)度(對(duì)于邊無(wú)權(quán)值的圖，最短路徑長(zhǎng)度為最短路徑所經(jīng)過的節(jié)點(diǎn)的個(gè)數(shù))小于半徑，則B位于該偽圓中。當(dāng)計(jì)算最短路徑時(shí)忽略邊的方向。

按照參考文獻(xiàn)[3]中提出的方法切割s-PDG：

(1)根據(jù)s-PDG節(jié)點(diǎn)的種類分別計(jì)數(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)計(jì)算s-PDG中所有這些種類l的節(jié)點(diǎn)與其他節(jié)點(diǎn)的距離，將最大值定為偽半徑。

(4)以上面計(jì)算出的偽半徑，以s-PDG中種類為l的節(jié)點(diǎn)為圓心，可以得到一些偽圓。這些偽圓就是切割s-PDG的最終結(jié)果。將它們記為c-PDG的集合。

在查找同構(gòu)子圖的過程中必須檢查節(jié)點(diǎn)的種類，對(duì)應(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所示。

圖2 基本流程圖

3 算法的實(shí)現(xiàn)

使用JavaPDG[4]生成整個(gè)項(xiàng)目的程序依賴圖。JavaPDG是一個(gè)靜態(tài)的Java字節(jié)碼分析器。這個(gè)工具能夠產(chǎn)生各種不同的對(duì)源代碼的圖形展示，例如系統(tǒng)依賴圖、程序依賴圖、控制流圖和函數(shù)調(diào)用圖。

使用Hadoop[5](一個(gè)MapReduce框架的開源實(shí)現(xiàn))來(lái)并行這個(gè)子圖集的同構(gòu)匹配。

使用Igraph[6]來(lái)檢測(cè)子圖同構(gòu)匹配。Igraph是一個(gè)針對(duì)圖的操作的開源軟件包，由于Igraph是用C語(yǔ)言寫成的，必須通過Hadoop流來(lái)將這個(gè)軟件包用于并行同構(gòu)檢測(cè)。

4 實(shí)驗(yàn)與評(píng)價(jià)

通過對(duì)兩個(gè)開源項(xiàng)目的檢測(cè)來(lái)評(píng)價(jià)本文的算法，結(jié)果如表1所示。通過代碼行數(shù)和對(duì)應(yīng)程序依賴圖的節(jié)點(diǎn)和邊的個(gè)數(shù)來(lái)對(duì)比項(xiàng)目的大小。將經(jīng)典PDG匹配算法與以3臺(tái)機(jī)器組成的集群上并行為例的本文算法所消耗的時(shí)間進(jìn)行了比較。

表1 實(shí)驗(yàn)結(jié)果

結(jié)果顯示，本文算法極大地提高了同構(gòu)匹配的性能，經(jīng)典的程序依賴圖同構(gòu)匹配算法需要花費(fèi)幾個(gè)小時(shí)，而本文并行算法僅僅花費(fèi)幾分鐘。這是因?yàn)椴⑿兴惴ㄒ瞥顺绦蛞蕾噲D中的部分節(jié)點(diǎn)，而且并行了同構(gòu)匹配的過程。

本文提出了一種提高基于程序依賴圖的克隆代碼檢測(cè)性能的方法。把程序依賴圖分割成若干個(gè)小圖并使用Hadoop并行執(zhí)行子圖同構(gòu)檢測(cè)，使得算法的性能得到了提高。使用兩個(gè)得到廣泛使用的開源項(xiàng)目來(lái)測(cè)試本文算法，測(cè)試結(jié)果顯示該算法顯著地提高了克隆代碼檢測(cè)的性能。

[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 Proceedingsof 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 forcomplex network research[C].InterJournal，Complex Systems，1695.2006.