邊奕心，趙 松，杜 軍

?

保持語義不變的C克隆代碼預(yù)處理方法

邊奕心1,2，趙 松2，杜 軍2

(1.中國科學(xué)院軟件研究所 北京 海淀區(qū) 100190；2. 哈爾濱師范大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院 哈爾濱 150025)

克隆代碼檢測(cè)工具的輸出結(jié)果由于存在克隆檢測(cè)不一致性缺陷的誤檢和檢測(cè)出的克隆代碼不能直接用于重構(gòu)的問題，需要對(duì)檢測(cè)工具的輸出結(jié)果進(jìn)行預(yù)處理。為了解決該問題，提出一種新的克隆代碼預(yù)處理方法。首先，將自適應(yīng)K-最近鄰聚類方法與程序依賴圖相結(jié)合，用于降低克隆不一致性相關(guān)缺陷檢測(cè)的誤檢。然后，使用基于代價(jià)-收益分析的評(píng)估方法，在消除缺陷后的克隆代碼中識(shí)別可重構(gòu)的克隆代碼。實(shí)驗(yàn)結(jié)果表明，該預(yù)處理方法，不僅降低了克隆不一致性相關(guān)缺陷檢測(cè)工具產(chǎn)生的誤檢，提高了可重構(gòu)克隆代碼的數(shù)量，而且將克隆代碼檢測(cè)與克隆代碼重構(gòu)兩個(gè)過程連接為一個(gè)有機(jī)的整體，有利于提高軟件的質(zhì)量，降低軟件維護(hù)的成本。

自適應(yīng)K-最近鄰聚類; 克隆代碼; 克隆不一致性缺陷檢測(cè); 程序依賴圖; 重構(gòu)

克隆代碼(clone code)是程序源代碼中多個(gè)具有相似語法或語義的代碼片段，是程序員的拷貝-粘貼行為造成的[1]，被列為軟件中低質(zhì)量、難以理解、難以維護(hù)的代碼中最著名的一種“壞味道(bad smell)”。研究顯示，克隆代碼增加了源代碼的長度和軟件系統(tǒng)的復(fù)雜性，使其更加難以維護(hù)，并可能在降低系統(tǒng)運(yùn)行效率的同時(shí)，引入大量缺陷[2]。通過對(duì)代碼進(jìn)行重構(gòu)可消軟件系統(tǒng)中的部分克隆代碼，提高程序的質(zhì)量。但是，克隆代碼檢測(cè)工具的輸出結(jié)果，一般情況下不能直接用于重構(gòu)，原因如下：首先，本文使用的檢測(cè)工具CPBugdetector[3]在檢測(cè)克隆代碼的同時(shí)，還能對(duì)拷貝-粘貼的相關(guān)缺陷進(jìn)行檢測(cè)。但是，工具的輸出結(jié)果存在一定的誤檢，對(duì)拷貝-粘貼相關(guān)缺陷檢測(cè)結(jié)果的準(zhǔn)確性，及對(duì)后續(xù)克隆代碼的重構(gòu)結(jié)果都會(huì)產(chǎn)生負(fù)面影響。其次，并非所有檢測(cè)出來的克隆代碼都適于重構(gòu)[4-6]。為解決以上問題，本文提出了一種預(yù)處理方法，該方法結(jié)合程序依賴圖和自適應(yīng)K-最近鄰聚類兩種方法，減少克隆不一致性相關(guān)缺陷檢測(cè)的誤檢，然后，使用基于代價(jià)-收益分析的評(píng)估方法，在消除缺陷后的克隆代碼片段中識(shí)別可重構(gòu)的克隆代碼，目的是降低維護(hù)克隆代碼的代價(jià)。

1 相關(guān)研究

1.1 克隆不一致性相關(guān)缺陷檢測(cè)存在的問題

1.1.1 拷貝-粘貼相關(guān)缺陷的檢測(cè)

克隆代碼通常是由開發(fā)人員的拷貝-粘貼行為產(chǎn)生的，這種行為極易引入缺陷。通過分析操作系統(tǒng)中的缺陷，文獻(xiàn)[7]認(rèn)為拷貝-粘貼是導(dǎo)致軟件出現(xiàn)缺陷的一個(gè)重要原因。研究結(jié)果表明：在Linux driver/i20的一個(gè)源文件中，發(fā)現(xiàn)的35個(gè)bug中有34個(gè)是由代碼的拷貝-粘貼導(dǎo)致的。

開發(fā)人員在編寫程序時(shí)，由于實(shí)踐需要，通常會(huì)對(duì)復(fù)制后的代碼進(jìn)行修改，這是導(dǎo)致克隆不一致性缺陷的主要原因。如，如果程序的源代碼片段被拷貝后，在被拷貝片段的相應(yīng)位置的標(biāo)識(shí)符經(jīng)過修改后，出現(xiàn)了兩個(gè)或兩個(gè)以上不同的名稱，這種不一致性通常預(yù)示著軟件缺陷，被稱為標(biāo)識(shí)符重命名不一致性缺陷。文獻(xiàn)[8]把這種標(biāo)識(shí)符重命名不一致性缺陷稱之為“忘記修改某標(biāo)識(shí)符”。文獻(xiàn)[9]又提出了另一種標(biāo)識(shí)符不一致性缺陷：“錯(cuò)誤修改某標(biāo)識(shí)符”。兩種缺陷的含義如下：

忘記修改某標(biāo)識(shí)符缺陷[8]：源代碼片段被拷貝-粘貼后，如果原片段的某個(gè)標(biāo)識(shí)符在被拷貝片段的所有位置上，除了一兩處為，其余的位置都被重命名為，這很可能是開發(fā)者由于忘記修改了某處而引入的缺陷。

錯(cuò)誤修改某標(biāo)識(shí)符缺陷[8]：源代碼片段被拷貝-粘貼后，如果原片段的某個(gè)標(biāo)識(shí)符在被拷貝的片段的所有出現(xiàn)位置上，除了一兩處被重命名為，剩下位置的為，這很可能是開發(fā)者在重命名其他位置的標(biāo)識(shí)符時(shí)，不小心將此處的標(biāo)識(shí)符錯(cuò)誤地重命名為而引入的缺陷。

圖1所示程序是在Linux 2.6.6版本中，由檢測(cè)工具CPBugdetector檢測(cè)出來的一個(gè)錯(cuò)誤修改某標(biāo)識(shí)符缺陷，其中，片段1的標(biāo)識(shí)符“ops”在片段2中的映射出現(xiàn)了不一致(映射“ops”4次，映射“claimed”1次)。這種缺陷很可能是開發(fā)人員“錯(cuò)誤修改某標(biāo)識(shí)符”而引入的軟件缺陷。

圖1 從Linux2.6.6中檢測(cè)出的一個(gè)錯(cuò)誤修改某標(biāo)識(shí)符缺陷

1.1.2 拷貝-粘貼相關(guān)缺陷檢測(cè)的誤檢

代碼中出現(xiàn)標(biāo)識(shí)符映射的不一致并不意味著一定是缺陷，也有可能是拷貝-粘貼相關(guān)缺陷的檢測(cè)工具造成的誤檢。因?yàn)榈侥壳盀橹?，還沒有檢測(cè)工具的輸出結(jié)果是不存在誤檢的。原因可以分為3類：1)錯(cuò)誤匹配拷貝-粘貼片段；2)語句順序發(fā)生變換；3)插入或刪除結(jié)構(gòu)相同的語句。前兩種類型的誤檢出現(xiàn)在文獻(xiàn)[8]中，但文獻(xiàn)并沒有提出誤檢消除的方法。本文主要研究后兩種誤檢并給出具體的誤檢消除方法。本文前期的工作[10]對(duì)消除拷貝-粘貼相關(guān)缺陷檢測(cè)的誤檢方法進(jìn)行了初步研究，在此基礎(chǔ)上，增加了可以消除的誤檢類型，并與度量方法相結(jié)合，在消除誤檢后的克隆代碼中，識(shí)別可重構(gòu)的克隆代碼。

圖2所示程序是第二種類型的誤檢??可交換的語句順序。如圖2b所示，片段1的標(biāo)識(shí)符“l(fā)astdirent”映射到片段2中，發(fā)生了映射不一致，在片段2中該標(biāo)識(shí)符被映射成“l(fā)astdirent”3次，一次被映射成標(biāo)識(shí)符“error”。從缺陷檢測(cè)結(jié)果看，這種映射的不一致是由于程序員錯(cuò)誤修改某標(biāo)識(shí)符而引起的缺陷。但是，通過分析可以發(fā)現(xiàn)，這個(gè)檢測(cè)結(jié)果是由于片段1和片段2中存在可交換的語句順序(語句15與16順序顛倒)引起的，并不是真正的軟件缺陷。

本文需要處理兩種類型的誤檢：1)插入或刪除相同結(jié)構(gòu)的語句；2)可交換的語句順序。這兩種誤檢都是在原代碼片段被拷貝粘貼后，在被拷貝片段的出現(xiàn)位置的語句的順序發(fā)生了變化引起的，為確定誤檢發(fā)生的位置(行號(hào))，本文引入了自適應(yīng)K-最近鄰聚類方法。該方法通過計(jì)算實(shí)體(程序語句)之間的相似度，把功能相近的語句聚到一起，然后對(duì)源代碼進(jìn)行聚類，將關(guān)系最密切的實(shí)體(語句的行號(hào))分到一個(gè)聚類集合中，以便對(duì)原代碼片段和被拷貝片段的聚類集合中的行號(hào)及其相應(yīng)語句的哈希值進(jìn)行比較，確定誤檢發(fā)生的位置。

a. 誤檢

b.標(biāo)識(shí)符映射關(guān)系

圖2 從Linux 2.6.6 版本中檢測(cè)出的一個(gè)語句位置互換引起的誤檢

1.1.3 識(shí)別克隆代碼可重構(gòu)機(jī)會(huì)的挑戰(zhàn)

檢測(cè)克隆代碼是重構(gòu)克隆代碼的前提，但是，以下原因?qū)е聶z測(cè)工具的輸出結(jié)果并不都適于重構(gòu)：首先，有些克隆代碼是程序員的有意行為，因此，克隆代碼不一定對(duì)軟件系統(tǒng)產(chǎn)生威脅[4,11]，檢測(cè)出來的克隆代碼有多少會(huì)對(duì)軟件系統(tǒng)產(chǎn)生不利影響，目前尚不清楚[5]。其次，由于大規(guī)模軟件系統(tǒng)的程序復(fù)雜性，導(dǎo)致很難消除某些對(duì)系統(tǒng)存在真正威脅的克隆代碼[6]。如，一些僅由聲明語句組成的克隆代碼是不適于提取的[12]。最后，有些克隆代碼使用傳統(tǒng)方法很難消除，如果采用特殊手段消除這些克隆代碼，會(huì)導(dǎo)致代碼難于理解，有時(shí)甚至有引入缺陷的可能性，這樣的結(jié)果是克隆代碼對(duì)系統(tǒng)的威脅仍然沒有消除。本文前期研究[13]對(duì)克隆代碼的識(shí)別方法進(jìn)行了初步探索，在此基礎(chǔ)上，提出了一種新的預(yù)處理克隆代碼的方法。該方法將程序依賴圖和自適應(yīng)K-最近鄰聚類相結(jié)合，消除或減少克隆不一致性相關(guān)缺陷檢測(cè)結(jié)果中存在的誤檢，然后，使用基于代價(jià)-收益分析的評(píng)估方法，在消除缺陷的克隆代碼中識(shí)別適于重構(gòu)的克隆代碼片段，在提高克隆代碼識(shí)別安全性的同時(shí)降低克隆代碼維護(hù)的代價(jià)。

1.2 預(yù)處理算法的相關(guān)理論基礎(chǔ)

1.2.1 自適應(yīng)K-最近鄰聚類方法

自適應(yīng)K-最近鄰(adaptive K-nearest neighbor) 聚類方法由文獻(xiàn)[14]提出，用于處理多種問題。該方法通過計(jì)算實(shí)體(程序語句)之間的相似度，把功能相近的語句放到一個(gè)聚類集合中，以便重構(gòu)。該方法與程序切片方法的思想類似，都是要找到相關(guān)度最高的語句，然后聚類。但是，程序切片方法需要先建立程序依賴圖，然后分析語句間的各種依賴關(guān)系，算法的復(fù)雜度非常高，不能分析較大規(guī)模的程序。而聚類方法是通過計(jì)算實(shí)體(程序語句)之間的相似度把最相關(guān)的語句聚集到一起，計(jì)算簡(jiǎn)單，算法的復(fù)雜度低，適用于分析大規(guī)模的程序代碼。

1.2.2 程序依賴圖

程序依賴圖(program dependence graph, PDG)是一種程序的中間圖形表示形式，是一個(gè)帶有標(biāo)記的有向多重圖。文獻(xiàn)[15]提出程序依賴圖的概念，并給出建圖的詳細(xì)算法。在程序依賴圖上，程序語句被表示成節(jié)點(diǎn)，語句之間的依賴關(guān)系用圖的邊表示。

2 克隆代碼的預(yù)處理算法

本文提出的預(yù)處理算法由兩個(gè)步驟組成。首先，消除兩種誤檢：插入或刪除相同結(jié)構(gòu)的語句和可交換的語句順序。其次，在消除缺陷后的克隆代碼中采用本文提出的識(shí)別方法識(shí)別可重構(gòu)的克隆代碼。

2.1 算法描述

本文提出的結(jié)合自適應(yīng)K-最近鄰聚類和程序依賴圖的克隆代碼預(yù)處理方法流程如圖3所示。

該方法首先使用工具CPBugdetector[3]分別檢測(cè)待測(cè)系統(tǒng)中的克隆代碼和拷貝-粘貼相關(guān)的缺陷，使用基于代價(jià)-收益的評(píng)估方法對(duì)未檢測(cè)出缺陷的克隆代碼片段，識(shí)別適于重構(gòu)的克隆代碼；對(duì)檢測(cè)出有缺陷的克隆代碼，使用本文提出的結(jié)合A-KNN聚類和程序依賴圖的方法消除這些誤檢。然后，再對(duì)拷貝-粘貼相關(guān)缺陷進(jìn)行檢測(cè)，加入人工參與部分，由人工來確認(rèn)缺陷和對(duì)缺陷進(jìn)行修正，將非誤檢又不屬于疑似缺陷的克隆代碼作為下一步的輸入，識(shí)別適于重構(gòu)的克隆代碼。最后，對(duì)適于重構(gòu)的克隆代碼采用相應(yīng)的重構(gòu)方法進(jìn)行重構(gòu)，目的是消除程序中的克隆代碼。

圖3 可重構(gòu)克隆代碼的預(yù)處理算法框圖

2.1.1 自適應(yīng)K-最近聚類與程序依賴圖相結(jié)合的誤檢消除算法

誤檢消除算法將自適應(yīng)K-最近鄰聚類與程序依賴圖相結(jié)合，目前該方法主要用來分析C語言編寫的程序，算法也可經(jīng)修改后應(yīng)用于其他類型的編程語言。算法描述如下。

算法：PruneFalsePositives

輸入：含有缺陷的克隆代碼的程序依賴圖P

輸出：消除誤檢后的克隆代碼

Begin

構(gòu)建實(shí)體屬性矩陣creatmatrix()；

計(jì)算相似度矩陣similarity()；

分類結(jié)果添加到結(jié)果集合stackre_1和stackre_2中；

湯翠是第二天下午返回來的。院子平了，碎磚碎瓦也都被推走了，南菜已經(jīng)天翻地覆了，過了今天，南菜恐怕只能在照片中看到了。幾臺(tái)鏟掘機(jī)還在工作，它們?cè)谄茐?，也在建設(shè)。鏟掘機(jī)們張開巨大的鐵手，毫不費(fèi)勁地插入堅(jiān)硬的土地里。湯翠沒想到，新翻上來的土呈紅褐色，像人的血。湯翠暈血，趕緊閉上眼。

while(stackre_1&&stackre_2不空){

比較兩個(gè)棧頂元素node1和node2的行號(hào)；

if(match){

stackre_1.pop(node1)；stackre_2.pop(node2);}

else{將未匹配節(jié)點(diǎn)放入集合collect中；}}\endwhile

for(collect的節(jié)點(diǎn)){

if(一行未匹配){

else\兩行未匹配{

if(未匹配節(jié)點(diǎn)的hashvalue相等){

collect中節(jié)點(diǎn)指針分別指回其PDG，判斷它們之間是否有依賴; }}}

End

算法由3個(gè)步驟組成：1) 進(jìn)行數(shù)據(jù)的收集；2) 聚類；3) 消除誤檢。經(jīng)過步驟2)聚類之后，代碼中關(guān)系最密切的實(shí)體(語句的行號(hào))被聚集到一個(gè)集合中，然后比較每個(gè)聚類集合中的行號(hào)，確定發(fā)生誤檢的位置。

如果一個(gè)聚類集合中的兩條語句與另一個(gè)聚類因以下兩種原因引起的誤檢：“插入或刪除結(jié)構(gòu)相同的語句”和“可互換語句順序”。經(jīng)過步驟2)聚類，關(guān)系最密類集合中的兩條語句未匹配，則比較它們的哈希值。如果哈希值相等(哈希值相同的語句是結(jié)構(gòu)相同的語句)，即為“語句可交換順序”而引起的誤檢，然后在程序依賴圖上執(zhí)行結(jié)構(gòu)語義分析，判斷兩條語句是否可交換，如果兩條語句之間存在著數(shù)據(jù)依賴，此時(shí)不可交換，反之可交換。

如果一個(gè)集合中的語句未在另一個(gè)集合中找到可與之匹配的語句，存在兩種可能：一種是疑似缺陷，另一種是因插入或刪除相同結(jié)構(gòu)的語句而引起的誤檢。此時(shí)，在程序依賴圖上尋找與未找到匹配語句的哈希值相同的語句節(jié)點(diǎn)，如果找到，即為因“插入或刪除相同結(jié)構(gòu)的語句”而引起的誤檢，然后在程序依賴圖上進(jìn)行結(jié)構(gòu)語義分析。如果在程序依賴圖上未找到與未匹配語句的哈希值相同的語句節(jié)點(diǎn)，則為疑似缺陷。下面以圖2程序?yàn)槔瑢?duì)算法進(jìn)行詳述。圖2所示程序的誤檢是由于兩個(gè)程序片段中的語句15和語句16的順序發(fā)生顛倒產(chǎn)生的，表1所示為片段1的實(shí)體-屬性矩陣。程序的實(shí)體-屬性矩陣作為算法的輸入，程序語句為算法的實(shí)體，控制變量和數(shù)據(jù)變量為屬性。如表1所示，矩陣的行是該變量所在的語句行號(hào)。

步驟如下：首先，待分析程序的實(shí)體-屬性矩陣作為算法的輸入，用以構(gòu)建程序的相似度矩陣，結(jié)果如表2所示。然后，算法處理聲明語句節(jié)點(diǎn)，得到每個(gè)實(shí)體的類標(biāo)簽。最后，執(zhí)行聚類算法，對(duì)語句進(jìn)行層次聚類，得到聚類結(jié)果。

片段1:{12,15}{13,14}{16,19,17,18}，片段2:{12,16}{13,14}{15,19,17,18}。

表1 示例程序(圖2)中片段1程序的實(shí)體-屬性矩陣

表2 示例程序(圖2)中片段1程序的相似度矩陣

經(jīng)過聚類后，首先比較3個(gè)聚類集合中的行號(hào)，找出不匹配的行號(hào)，在本例中，語句15和16不匹配。對(duì)為匹配的語句，先比較它們的哈希值，如果哈希值相等，則對(duì)相應(yīng)的程序依賴圖進(jìn)行結(jié)構(gòu)語義分析，目的是確定兩個(gè)語句間是否存在數(shù)據(jù)依賴，片段1程序的程序依賴圖如圖4所示。語句15和16間不存在數(shù)據(jù)依賴，因此可以交換語句15和16的順序。

2.1.2 基于代價(jià)-收益分析的評(píng)估方法識(shí)別可重構(gòu)的克隆代碼

過程提取作為重構(gòu)方法之一，可減少系統(tǒng)中的克隆代碼，但經(jīng)過過程提取，函數(shù)間的耦合度增加了，因而增大了軟件維護(hù)的代價(jià)，而過程提取引起的代碼規(guī)模的減少是其帶來的收益。文獻(xiàn)[6]通過代碼間的耦合度計(jì)算來度量代碼遷移的難易程度，然后，根據(jù)難易程度對(duì)語句進(jìn)行排序，識(shí)別并提取可重構(gòu)的克隆代碼，認(rèn)為使用外部定義的變量(被引用和被賦值)越少，代碼的遷移難度越低。文獻(xiàn)[12]在過長方法中識(shí)別可以被提取的片段，將代價(jià)和收益進(jìn)行相除，根據(jù)比率對(duì)候選的片段進(jìn)行排序，比率最高的片段被認(rèn)為是適于提取的。本文在文獻(xiàn)[6,12]的基礎(chǔ)上，提出了基于代價(jià)-收益評(píng)估的方法，識(shí)別可重構(gòu)的克隆代碼。該算法將代碼行的減少視為重構(gòu)的收益，而重構(gòu)的代價(jià)是被提取的函數(shù)和周圍代碼之間的傳遞參數(shù)的數(shù)量。

圖4 示例程序(圖2)中片段1的程序依賴圖

1) 收益分析

Benefit()=(|cf|?1) (1)

式中，|cf|是中每個(gè)片段內(nèi)能被提取代碼語句數(shù)量。在某些克隆代碼中，存在一定數(shù)量的非克隆代碼，但由于語句間的依賴關(guān)系，這些非克隆語句不能被移出。在已有的方法中，由于過程提取產(chǎn)生了一個(gè)過程調(diào)用，因此，實(shí)際語句的減少量為|cf|-1。

舉例：圖5所示程序含有克隆代碼的片段的行數(shù)減少了5行(其中加粗顯示的是克隆代碼語句)，但由于過程調(diào)用，收益是8。

圖5 Linux 2.6.6中檢測(cè)出的克隆代碼

2)代價(jià)分析

耦合度表示過程提取的代價(jià)。克隆代碼與它周圍代碼的耦合度越低，則克隆代碼越易被移動(dòng)[12]。在常見的7種耦合關(guān)系中，本文主要計(jì)算數(shù)據(jù)耦合，原方法和新方法(過程提取的結(jié)果)之間的耦合度通過計(jì)算新方法的參數(shù)來計(jì)算，有：

舉例：圖5中所示的片段，old_fs和ret是輸入?yún)?shù)，ret為輸出參數(shù)，因此，此例中過程提取的代價(jià)為6。

綜上所述，代價(jià)-收益分析的評(píng)估方法為：

表3 被測(cè)開源軟件中克隆代碼的檢測(cè)結(jié)果

3 實(shí)驗(yàn)結(jié)果與分析

本文選取了9個(gè)由C語言編寫的開源程序作為實(shí)驗(yàn)對(duì)象。首先采用克隆代碼檢測(cè)工具CPBugdetector[3]對(duì)這9個(gè)開源程序進(jìn)行克隆代碼檢測(cè)及其相關(guān)缺陷的檢測(cè)，克隆代碼檢測(cè)結(jié)果如表3所示。然后，使用本文提出的方法對(duì)測(cè)試程序進(jìn)行誤檢消除，誤檢消除的實(shí)驗(yàn)結(jié)果如表4所示。

表4中記錄了誤檢消除前后，分別針對(duì)檢測(cè)出的“忘記修改某標(biāo)識(shí)符”和“錯(cuò)誤修改某標(biāo)識(shí)符”的缺陷，檢測(cè)工具報(bào)告的bug數(shù)量。表4的最后4列數(shù)據(jù)記錄了本文提出的算法能夠消除的誤檢的成因及缺陷類型。

表4 不同類型分類結(jié)果比較

表5 識(shí)別可重構(gòu)克隆代碼

結(jié)合表3和表4進(jìn)行分析，被測(cè)程序的規(guī)模越大，檢測(cè)出來的bug越多，同時(shí)能被消除的誤檢也越多。最后，采用基于代價(jià)-收益分析的方法對(duì)消除誤檢之后的克隆代碼識(shí)別適于重構(gòu)的克隆代碼，實(shí)驗(yàn)結(jié)果如表5所示。誤檢消除之后增加了適于重構(gòu)的克隆代碼的數(shù)量，同時(shí)，檢測(cè)出來的克隆代碼約70%是適于提取的。

[1] CAI D, KIM M. An empirical study of long-lived code clones[J]. Fundamental Approaches to Software Engineering Lecture Notes in Computer Science, 2011, 6603: 432-446.

[2] 于冬琦, 彭鑫, 趙文耘.使用抽象語法樹和靜態(tài)分析的重復(fù)代碼自動(dòng)重構(gòu)方法[J]. 小型微型計(jì)算機(jī)2009, 30(9): 1752-1760.

YU Dong-qi, PENG Xin, ZHAO Wen-yun. Automatic refactoring method of cloned code using abstract syntax tree and static analyis[J]. Journal of Chinese Computer Systems, 2009, 30(9): 1752-1760.

[3] 蘇小紅, 馬培軍, 王倩, 等. C克隆代碼缺陷檢測(cè)工具: 中國, [CPBugdetector] V1.0[CP/DK]. 2010.

SU Xiao-hong, MA Pei-jun, WANG Qian, et al. A defects detection tool for C clones, China, [CPBugdetector] V1.0[CP/DK]. 2010.

[4] KIM M, BERG L, LAU T, et al. An ethnographic study of copy and paste programming practices in oopl[C]// International Symposium on Empirical Software Engineering. Washington DC, USA: IEEE, 2004: 83-92.

[5] CODE N, KOS R. Frequency and risks of changes of clones[C]//33rd Internaitonal Conference on Software Engineering. Hawaii, USA: IEEE, 2011: 311-320.

[6] HIGO Y, KUSU S, INOUE K. Identifying refactoring opportunities for removing code clones with a metrics-based approach[M]. Hong Kong, China: CreateSpace Independent Publising Platform, 2011: 1-26.

[7] CHOU A, YANG J, CHELF B, et al. An empirical study of operating systems error[J]. SIGOPS Operating Systems Review, 2001, 35(1): 73-88.

[8] LI Z, LU S, MYAGMAR S, et al. CP-miner: Finding copy-paste and related bugs in large-scale software code[J]. IEEE Transactions on Software Engineering, 2006, 32(3): 176-192.

[9] 王倩. 基于序列挖掘的C克隆代碼及相關(guān)軟件缺陷的檢測(cè)[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2009.

WANG Qian. Detection of clones and related software defects of C programs via sequential pattern mining[D]. Harbin: Harbin Institute of Technology, 2009.

[10] MA Pei-jun, BIAN Yi-xin. A clustering method for pruning false positive of clone code detection[C]// International Conference on Mechatronic Sciences, Electric Engineering and Computer (MEC 2013). Shenyang, China: IEEE, 2013: 1917-1920.

[11] KAPSER C, GODFREY M W. “Cloning considered harmful” considered harmful[C]//The 13th Working Conference on Reverse Engineering. Washington DC: USA: IEEE, 2006: 19-28.

[12] YANG L, LIU HUI, NIU Z. Identifying fragments to be extracted from long methods[C]//Asia-Pacific Software Engineering Conference. Washington DC, USA, IEEE, 2009: 43-49.

[13] BIAN Yi-xin, SU Xiao-hong, MA Pei-jun. Identifying accurate refactoring opportunities using metrics[C]// International Conference on Soft Computing Techniques and Techniques and Engineering Application. Shenyang, China: IEEE, 2013: 141-146.

[14] ALKHALID A, ALSHAYEB M, MAHMOUD S. Software refactoring at the function level using new adaptive K-nearest neighbor algorithm[J]. Advances in Engineering Software, 2010, 41(10-11): 1160-1178.

[15] FERRANTE J, OTTENSTEIN K J, WARREN J D. The program dependence graph and its use in optimization[J]. ACM Transaction on Program Language System, 1987, 9(3): 319-349.

編 輯 漆 蓉

Semantic-Preserving Pre-Processing Method for C Clone Code

BIAN Yi-xin1,2, ZHAO Song2, and DU Jun2

(1. Institute of Software Chinese Academy of Sciences Haidian Beijing 100190; 2. College of Computer Science and Information Engineering, Harbin Normal University Harbin 150025)

The output results of clone code detection tool cannot be directly refactored because of the two reasons: one is the false positives of clone inconsistency related bugs detection and the other is that all the detected clones cannot be suitable for refactoring. Therefore, the output results of clone code detection tool need to be pre-processed for reducing the error checking of cloning inconsistencies defect. A pre-processing approach combing adaptive K-nearest neighbor clustering with program dependence graph is proposed in this paper to solve these problems. First, adaptive K-nearest neighbor clustering and program dependence graph are used to reduce the false positives of clones inconsistency related bugs detection. And then the refactorable clone code is identified to reduce the cost of clone maintenance. The results of the study show that our approach not only effectively prunes the false positives of clone inconsistency related bugs but also eliminates the gap between clone code detection and clone refactoring. Therefore, our method contributes to improving the quality of the software and decreasing the cost of software maintenance.

adaptive K-nearest neighbor clustering; clone code; clone inconsistency related bugs detection; program dependence graph; refactoring

TH133; TP183

A

10.3969/j.issn.1001-0548.2017.06.023

2016-09-14；

2017-05-18

黑龍江省自然科學(xué)基金(F2016030)

邊奕心(1979-)，女，博士，主要從事軟件重構(gòu)、程序分析、缺陷檢測(cè)方面的研究.