基于K-最近鄰的C克隆代碼重構方法

摘要： 在軟件開發過程中，克隆代碼已經成為引起軟件缺陷的一個重要因素。針對現有的方法不能很好地處理內聚度低、功能交叉的克隆代碼的問題，提出了一種基于Ｋ－最近鄰的克隆代碼重構方法。首先，對克隆代碼進行靜態分析，搜集控制依賴信息和數據流信息，再經過Ｋ－最近鄰聚類方法，形成便于提取、功能獨立的代碼片段，然后對代碼片段進行過程提取，使之成為一個獨立的過程，并用過程調用替代原來的克隆代碼。實驗結果表明，該方法能夠對克隆代碼進行有效組織，并對功能獨立的部分進行提取。

關鍵詞：

中圖分類號： ＴＰ３１１ 文獻標識碼：Ａ 文章編號：２０９５－２１６３（２０１１）０１－００４７－０４

０引言

隨著計算機軟件的不斷發展，研究人員提出了軟件復用的概念。人們希望通過復用已有的高質量開發成果，避免重新開發可能引入的錯誤，提高軟件的質量。當在開發過程中碰到一些熟悉問題的時候，編程人員就從已有的系統中尋找實現類似功能的代碼，稍作修改，以滿足需求，然后應用到當前系統中。隨著時間的推移和系統功能的增加，拷貝－粘貼的方法很容易導致整個軟件系統充斥著大量的克隆代碼。

克隆代碼在大多數情況下是有害的，增加了軟件系統代碼的長度，使得軟件系統愈加復雜、難以維護，系統運行效率降低，并且給軟件引入大量的程序缺陷。對克隆代碼使用的重構技術主要是過程提取，就是將出現在源代碼中的克隆代碼提取為一個新的過程，這在一定程度上降低了克隆代碼帶來的危害。

過程提取這個概念最早出現在１９７７年，由ＢＵＲＳＴＡＬＬ和ＤＡＲＬＩＮＧＴＯＮ首次提出[１]。但是直到９０年代初，才由ＧＲＩＳＷＯＬＤ 和ＮＯＴＫＩＮ第一次在其著作[２，３]中提出ｅｘｔｒａｃｔ－ｆｕｎｃｔｉｏｎ（過程提取）這個詞。比較早的過程提取方法有ＬＡＫＨＯＴＩＡ提出的ｔｕｃｋ[４]方法，該方法可以將連續的語句和不連續的語句提取成單獨的過程。隨后，ＫＯＭＯＮＤＯＯＲ和ＨＯＲＷＩＴＺ提出了語義保持的自動過程提取方法[５－６]，來提取可能含有跳轉語句的不連續的代碼片段。ＨＡＲＭＡＮ和ＢＩＮＫＬＥＹ針對自動過程提取方法又做了一些改進[７]，減少了要提取的代碼數量。但是上述方法都是注重將代碼變換為連續一致的形式，計算復雜度較高，并且沒有涉及到內聚度低、功能交叉的代碼的處理。

為了處理內聚度低的代碼，文獻[８－９]在源代碼級別上使用了聚類算法，選取可執行語句作為實體，根據實體的數據屬性和控制屬性計算相似度，將彼此關聯的元素歸類，但是文獻中算法對語句之間的控制依賴考慮較少，導致聚類結果不準確，也沒有將聚類算法應用到克隆代碼的重構中。

針對上述方法中存在的不足，提出一種基于Ｋ－最近鄰的克隆代碼重構方法，結合控制依賴圖和Ｋ－最近鄰聚類算法，形成便于提取和功能獨立的代碼片段，然后基于抽象語法樹，應用過程提取算法，將代碼片段提取為一個新的過程。該方法能夠有效改進程序結構，對克隆代碼進行重構。

１基于Ｋ－最近鄰的克隆代碼重構算法

１．１基于Ｋ－最近鄰的克隆代碼重構模型

本文提出的克隆代碼重構模型如圖１所示。該模型的基本思路為：首先讀入Ｃ克隆代碼，接著進行詞法分析和語法分析，在此基礎上生成抽象語法樹，然后建立程序依賴圖，獲得控制流信息和數據流信息。其次，采用控制依賴圖和Ｋ－最近鄰聚類算法相結合的方法分析代碼，分離出便于提取、功能獨立的代碼片段。最后，調用基于抽象語法樹的過程提取算法，解決參數相關問題，將代碼片段提取為獨立的過程，并用過程調用取代其在源代碼中的位置。

１．２改進的基于控制依賴圖的Ｋ－最近鄰聚類算法

通過建立和分析程序的控制依賴圖[１０]，可以求得代碼語句的定值－引用變量信息。在此基礎上，對代碼執行聚類算法[８]，將語句進行歸類，可以提高提取、功能獨立的代碼片段的準確性。

基于這樣一種思路，本文在文獻[８－９]的基礎上提出一種改進的基于控制依賴圖的Ｋ－最近鄰聚類算法。該聚類算法結合控制依賴圖，查找、記錄控制語句的作用域，重新調整語句之間的控制依賴關系，使得聚類結果更加準確；并且利用相似度矩陣和控制依賴關系，調整分類結果，使其可以作為過程提取算法的輸入，支持克隆代碼重構。改進的基于控制依賴圖的Ｋ－最近鄰算法如圖２所示。

本文聚類算法選取程序語句作為聚類的實體對象，控制變量和數據變量作為實體的屬性，以實體屬性矩陣作為算法的輸入，矩陣的行表示語句的行號，列表示實體相關的屬性。

算法步驟如下：

（１）根據實體屬性矩陣，計算兩兩實體之間的相似度，構建相似度矩陣；

（２）處理聲明類型節點，初始化每個實體的類標簽，類標簽用來記錄該實體在聚類過程中的分類情況；

（３）執行Ｋ－最近鄰算法，對語句進行層次聚類。再遍歷實體集合，對每個控制實體，結合控制依賴圖，建立其與所有子結點的列表，形成控制實體集合；

（４）去掉每個聚類結果中相似度為零的分類；

（５）對于處于控制語句作用域中的語句，添加其控制節點，重建控制依賴；

（６）最后輸出結果。

１．３基于抽象語法樹的過程提取算法

代碼經過聚類之后，形成了便于提取、 功能獨立的代碼片段，可以將其提取為獨立的過程。此時，主要需要解決待提

取的過程的參數相關問題，為此，本文在進行過程提取的同時，也加入了抽象語法樹。當需要解決參數類型問題時，查找抽象語法樹，獲得需要的信息。過程提取的算法如圖３所示。

具體涉及如下幾個關鍵問題：

（１）提取變量的到達－定值信息

由于控制依賴圖包含控制流信息，可通過控制依賴圖獲得節點之間的控制依賴關系，從而獲得各個節點的到達——定值信息，因此可以在創建完成控制依賴子圖后對其執行數據流分析，得到變量定值——引用信息[１１]。

（２）根據變量的定值——引用信息，確定變量類型

確定變量類型時，若是函數體中的聲明變量，則遍歷控制依賴圖，找到聲明語句，然后轉到語法樹，找到其對應的聲明類型的語法樹節點，根據語法規則，聲明類型節點的最左孩子節點即為該變量的類型。若是函數參數列表中的變量，則首先根據函數定義得到變量所處位置信息，再遍歷語法樹，找到其對應的類型。

（３）確定要提取的過程的參數類型及個數

在將語句提取為新的過程時，需要確定新過程的參數類型。參數類型主要分為兩類：傳引用類型和傳值類型。對定值（ｄｅｆ）變量集合進行計算，去掉聲明（ｄｅｌ）集合中的變量，剩下的變量就是引用類型的參數，計算公式如下：

ｐａｒａ（＆）＝Ｖａｒｓ（ｄｅｆ）－Ｖａｒｓ（ｄｅｌ）（１）

其中，ｐａｒａ（＆）表示引用類型參數的集合，Ｖａｒｓ（ｄｅｆ）表示定值變量的集合，Ｖａｒｓ（ｄｅｌ）表示聲明變量的集合。

對引用集合（ｒｅｆ）中的變量經過處理作為傳值類型，其計算公式如下：

ｐａｒａ（ｖ）＝Ｖａｒｓ（ｒｅｆ）－Ｖａｒｓ（ｄｅｆ）∪Ｖａｒｓ（ｄｅｌ）（２）

其中，ｐａｒａ（ｖ）表示傳值類型參數的集合，Ｖａｒｓ（ｒｅｆ）表示引用變量的集合。

ｐａｒａ（＆）和ｐａｒａ（ｖ）兩個集合的元素個數即為新過程的參數個數。

此外，還要特別對待臨時變量，此變量的定義和使用都在要提取的語句范圍內。對于臨時變量，不作為新過程的參數，直接放到新的過程體中。

（４）解決過程的返回值問題

在將代碼提取為新的過程的時候，需要確定新過程是否有返回值。目前分為兩種情況：新過程沒有返回值和新過程有一個或多個返回值。如果新過程沒有返回值，則直接將代碼提取為新的過程。如果新過程有一個或多個返回值，統一采用傳引用方式解決，將返回值以引用形式添加到新過程的參數列表。

采用數據流分析的方法來確定新過程是否有返回值。先計算標記語句后面語句的變量的信息，然后與標記語句的聲明變量做對比，若二者有交集，則認為新的過程有返回值，計算公式如下：

ｒｅｔｕｒｎｖａｌｕｅｓ＝Ｖａｒｓ（ｄｅｌ）－Ｖａｒｓ（ｎｂｍ） （３）

其中，ｒｅｔｕｒｎｖａｌｕｅｓ表示返回值集合，Ｖａｒｓ（ｎｂｍ）表示要提取的語句之后的變量集合。

（５）將代碼提取為新的過程

在確定了新過程的參數和返回值之后，就可以將代碼提取為新的過程了。這里，特別要注意的是新過程有返回值的情況。因為如果新過程有返回值，就可能要對標記語句節點進行分裂，使之成為兩個聲明語句，一條語句需要提取，一條語句不需要提取。例如對于標記聲明語句ｉｎｔ ｘ，ｙ＝１，ｚ；如果只有ｘ是返回值涉及到的變量，則該語句需要分裂成兩個節點：ｉｎｔ ｘ和ｉｎｔ ｙ＝１，ｚ。其中前者變為不需要提取的語句，作為新方法的引用參數；后者依然為需要提取的語句。

２實驗結果與分析

為了驗證以上算法，選取兩組實驗程序：第一組是文獻[８]中使用的示例程序，第二組使用開源程序。

２．１文獻中程序的實驗

本文選取文獻[８]中的代碼來測試重構算法。文獻中是ｊａｖａ代碼，聚類結果只給出樹形表示形式，也沒有給出重構方法。本文用Ｃ語言將其改寫，示例代碼如圖４所示，其中有＋＋符號的為待提取的克隆代碼。

示例里的克隆代碼是一段功能交叉的代碼，包含計算數組元素的平均值ａｖｇ和數組元素所有項的乘積ｐｒｏｄ兩項功能。首先使用基于控制依賴圖的Ｋ－最近鄰聚類算法，形成功能獨立的代碼，聚類結果如圖５所示。代碼分成兩類，有＋＋標記的語句計算平均值ａｖｇ，沒有標記的語句計算成績ｐｒｏｄ。在文獻[８]的聚類結果中，沒有指明ｆｏｒ的控制范圍，本文結果中，ｆｏｒ語句的控制范圍直接到語句，因而更加精確。

然后，對克隆代碼執行過程提取算法，將其提取為單獨的過程，并用新的過程調用取代其在源代碼中的位置，結果如圖６所示。文獻[８]中并沒有給出重構方法；本文提出了過程提取算法，處理了過程提取中參數相關問題，給出了具體的重構方案。文獻[６]中的過程提取方法沒有涉及到功能交叉的代碼的處理，本方法能夠更準確地提取功能內聚的代碼。

２．２開源代碼的實驗

本文選取若干開源軟件的克隆代碼來進行實驗。克隆代碼的檢測使用ＣＰＢｕｇｄｅｔｅｃｔｏｒ[１２]。實驗結果如表１所示。其中，＃ｆｉｎｄ表示檢測到的克隆代碼組數，＃ｓｕｉｔ表示適合重構的克隆代碼組數，＃ｃｌｕｓｔｅｒ表示聚類準確的克隆代碼組數，＃ｅｘｔｒａｃｔ表示成功提取的克隆代碼組數。從表１中可以看出，本文方法對需要重構的絕大部分克隆代碼都能進行正確的重構，但是對原子操作代碼的處理還存在一些不足，因為原子操作可能會受到其他語句的影響不能夠聚在一起。

相比于文獻[８]的方法，本文方法結合控制依賴圖，有效地處理了語句之間的控制依賴關系，并將聚類結果應用于克隆代碼的重構中，能夠處理更多的情況。分別用本文方法和文獻[８]的方法對上述開源軟件進行實驗，結果如表２所示。其中，＃ｃｏｎｔｒｏｌ表示有嵌套控制克隆代碼組數。從表２中可以看出，本文算法對控制依賴有更好的處理。例如對圖７中來自ｌｉｂｍｅｍｃａｃｈｅｄ－０．２６中的克隆代碼，文獻[８]中的方法將兩個ｗｈｉｌｅ聚在同一個類中，使第二個ｗｈｉｌｅ脫離了ｆｏｒ的控制，如圖８所示。本文方法則能夠保持圖７所示的控制依賴。

３結束語

本文提出一種基于Ｋ－最近鄰的克隆代碼重構方法。該方法結合控制依賴圖和Ｋ－最近鄰聚類算法，形成功能獨立、便于提取的代碼，再使用過程提取算法，對克隆代碼進行重構。與文獻[６]方法相比，本文方法能夠較好地提取內聚度低、功能交叉的克隆代碼；與文獻[８]方法相比，本文方法能夠較好地處理程序語句的控制依賴關系，具有較高的聚類準確性。

參考文獻：

[１] ＢＵＲＳＴＡＬＬ Ｊ， ＤＡＲＬＩＮＧＴＯＮ Ｊ． Ａ ｔｒａｎｓｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ｆｏｒ ｄ－ ｅｖｅｌｏｐｉｎｇ ｒｅｃｕｒｓｉｖｅｐｒｏｇｒａｍｓ[Ｊ]． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ，１９７７，２４ （１）：４４－６７．

[２] ＧＲＩＳＷＯＬＤ Ｗ Ｇ， ＮＯＴＫＩＮ Ｄ． Ａｕｔｏｍａｔｅｄ ａｓｓｉｓｔａｎｃｅ ｆｏｒ ｐｒｏｇｒ－ ａｍ ｒｅｓｔｒｕｃｔｕｒｉｎｇ[Ｊ]． ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｏｆｔｗａｒｅ Ｅｎｇｉｎｅｅｒｉｎｇ， １９９３，２（３）：２２８－２６９．

[３] ＧＲＩＳＷＯＬＤ Ｗ Ｇ． Ｐｒｏｇｒａｍ Ｒｅｓｔｒｕｃｔｕｒｉｎｇ ａｓ ａｎ ａｉｄ ｔｏ ｓｏｆｔｗａｒｅｍａｉｎｔｅｎａｎｃｅ[Ｄ]． Ｗａｓｈｉｎｇｔｏｎ：Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｗａｓｈｉｎｇｔｏｎ，１９９１．

[４] ＬＡＫＨＯＴＩＡ Ａ， ＤＥＰＲＥＺ Ｊ． Ｒｅｓｔｒｕｃｔｕｒｉｎｇ－ ｐｒｏｇｒａｍｓ ｂｙ ｔｕｃｋｉｎｇ ｓｔａｔｅｍｅｎｔｓ ｉｎｔｏｆｕｎｃｔｉｏｎｓ[Ｃ]／／ ＨＡＲＭＡＮ Ｍ， ＧＡＬＬＡＧＨＥＲ Ｋ，ＥＤＳ． Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｓｏｆｔｗａｒｅ Ｔｅｃｈｎｏｌｏｇｙ Ｓｐｅｃｉａｌ Ｉｓｓｕｅ ｏｎ Ｐｒ－ ｏｇｒａｍ Ｓｌｉｃｉｎｇ． Ｅｌｓｅｖｉｅｒ，１９９８，４０（１１－１２）：６７７－６８９．

[５] ＫＯＭＯＮＤＯＯＲ Ｒ， ＨＯＲＷＩＴＺ Ｓ． Ｓｅｍａｎｔｉｃｓ－ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｃｅｄｕｒｅ ｅｘｔｒａｃｔｉｏｎ[Ｃ]／／ Ｐｒｏｃ．ｔｈｅ ２７ｔｈ Ａｃｍ ＳＩＧＰＬＡＮ－ＳＩＧＡＣＴ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｐｒｏｇｒａｍｍｉｎｇ ｌａｎｇｕａｇｅｓ． ＮｅｗＹｏｒｋ：ＡＣＭ Ｐｒｅｓｓ， ２０００：１５５－１６９．

[６] ＫＯＭＯＮＤＯＯＲ Ｒ， ＨＯＲＷＩＴＺ Ｓ． Ｅｆｆｅｃｔｉｖｅ， ａｕｔｏｍａｔｉｃ ｐｒｏｃｅｄｕ－ ｒｅ ｅｘｔｒａｃｔｉｏｎ[Ｃ]／／ Ｐｒｏｃ．ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ ＰｒｏｇｒａｍＣｏｍｐｒｅｈｅｎｓｉｏｎ．Ｗａｓｈｉｎｇｔｏｎ：ＩＥＥＥ Ｐｒｅｓｓ，２００３：３３－４３．

[７] ＨＡＲＭＡＮ Ｍ， ＢＩＮＫＬＥＹ Ｄ， ＤＡＮＩ－ＣＩＣ Ｓ． Ａｍｏｒｐｈｏｕｓ ｐｒｏｇｒａｍ ｓｌｉｃｉｎｇ[Ｊ]． Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍｓ ａｎｄ Ｓｏｆｔｗａｒｅ， ２００３，６８（１）：４５－６４

[８] ＡＬＫＨＡＬＩＤ Ａ， ＹＥＢ Ｍ Ａ， ＭＡＨＭＯＵＤ Ｓ． Ｓｏｆｔｗａｒｅ ｒｅｆａｃｔｏｒｉｎｇ ａｔ ｔｈｅ ｆｕｎｃｔｉｏｎ ｌｅｖｅｌ ｕｓｉｎｇ ｎｅｗ Ａｄａｐｔｉｖｅ Ｋ－Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ ａ－ ｌｇｏｒｉｔｈｍ[Ｊ]． Ａｄｖａｎｃｅｓ ｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｓｏｆｔｗａｒｅ，２０１０：４１：１１６０－ １１７８．

[９] ＬＵＮＧ Ｃ Ｈ，ＸＵ Ｘ，ＺＡＭＡＮ Ｍ，ｅｔ ａｌ． Ｐｒｏｇｒａｍ ｒｅｓｔｒｕｃｔｕｒｉｎｇ ｕｓ－ ｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ｔｅｃｈｎｉｑｕｅｓ[Ｊ]． Ｔｈｅ Ｊｏｕｒｎａｌ ｏｆＳｙｓｔｅｍｓ ａｎｄ Ｓｏｆｔ－ ｗａｒｅ， ２００６：７９，１２６１－１２７９．

[１０] 王偉． Ｃ冗余代碼及相關缺陷檢測方法研究[Ｄ]． 哈爾濱：哈爾濱工業大學計算機與科學技術學院，２００９．

[１１] 王甜甜． 基于語義相似度的編程題自動評分系統研究[Ｄ]． 哈爾濱：哈爾濱工業大學計算機與科學技術學院，２００５．

[１２] 蘇小紅，馬培軍，王偉，等． 克隆Ｃ程序代碼引起的軟件缺陷檢測工具 [簡稱：ＣＰＢｕｇＤｅｔｅｃｔｏｒ] Ｖ１．０． ２０１０ＳＲ０４９１６１[Ｐ]． ２００９－６－２６．