張瑞霞，張麗萍，王春暉，侯 敏

（內(nèi)蒙古師范大學(xué) 計算機與信息工程學(xué)院，內(nèi)蒙古 呼和浩特010022）

0 引 言

程序員為了提高開發(fā)效率對源代碼進行的拷貝、粘貼及修改活動通常會導(dǎo)致軟件中出現(xiàn)很多語法或語義特征相同或相似的代碼段，這類代碼段被稱為克隆代碼 （code clone）［1，2］。為了更好的管理克隆代碼，近年來學(xué)者們從克隆演化的角度，以動態(tài)的方式來探索克隆代碼存在、發(fā)展、變化的規(guī)律，即對同一軟件系統(tǒng)多版本中的克隆進行跟蹤，發(fā)現(xiàn)克隆在歷時演化過程中表現(xiàn)出的模式和特征，為進一步管理克隆提供依據(jù)。

本文的克隆群映射方法正是根據(jù)克隆代碼演化研究的需要提出的，克隆群映射反映克隆群由前一版本到當(dāng)前版本的演化過程，是研究多版本演化的核心技術(shù)之一。目前的克隆群映射方法多是基于文本或位置的相似度或兩者結(jié)合判斷或利用版本管理工具 （SVN、CVS）映射克隆群，但這些方法存在準(zhǔn)確率偏低、耗時較高、必須借助版本管理軟件中的日志等缺陷。本文將自然語言研究領(lǐng)域的主題建模技術(shù)應(yīng)用于克隆代碼，提出一種克隆群映射方法。主題建模技術(shù)能充分利用源代碼的文本和結(jié)構(gòu)信息，將映射問題由高維的代碼空間轉(zhuǎn)化到低維的主題空間上，通過映射主題來準(zhǔn)確地構(gòu)建相鄰版本克隆群的映射關(guān)系。

1 克隆群及其映射方法

1.1 克隆群相關(guān)定義

現(xiàn)有研究中，克隆主要有以下兩種分類方法［2］。根據(jù)檢測粒度，將其分成：文件克隆、類克隆、函數(shù)克隆、塊克隆以及語句克隆等5種類型。依據(jù)源代碼的文本與功能相似性，分成Type－1、Type－2、Type－3和Type－4這4種類型。Type－1：除空白符與注釋變化外完全相同的代碼段；Type－2：除空白符、注釋、標(biāo)識符、類型替換外句法結(jié)構(gòu)完全相同的代碼段；Type－3：除空白符、注釋、標(biāo)識符、類型替換外，句法結(jié)構(gòu)基本相同，但含有少量語句的增加、刪除或修改的代碼段；Type－4：功能相同但句法結(jié)構(gòu)不同的代碼段。

克隆對 （clone pair）是指相互之間存在克隆關(guān)系的代碼段；克隆群是一些克隆代碼段的集合，其中任意兩個代碼段都是克隆對。

1.2 克隆群映射及方法

一款軟件在不斷升級過程中會產(chǎn)生多個版本，某個版本中的克隆群在下個相鄰版本中究竟發(fā)生了怎樣的變化，需要我們通過對軟件相鄰兩個版本中的克隆群進行映射來做出判斷?？寺∪河成涫侵府?dāng)前版本的克隆群由上一版本的哪個克隆群演化而來的，反映了軟件各個版本中的克隆群的對應(yīng)關(guān)系。

目前，研究者已提出多種克隆群映射方法。主要有：基于克隆代碼位置進行判斷，必要時輔以標(biāo)識符匹配［3］；基于文本相似性映射版本間的克隆群［4］；在函數(shù)映射的基礎(chǔ)上，進行克隆代碼的匹配［5］；通過版本管理工具 （CVS或SVN）中的修改信息確定映射關(guān)系［6］；使用增量的克隆檢測算法進行映射［7］；基于CRD （抽象的克隆區(qū)域描述）來映射［8］。

以上幾種方法都有其局限性：首先，基于位置的映射結(jié)果極易受代碼其它部分變化的影響，一旦其它部分代碼的變化導(dǎo)致克隆代碼位置漂移，就很有可能導(dǎo)致映射不上，或者映射到錯誤的目標(biāo)；在位置映射基礎(chǔ)上輔以標(biāo)識符匹配，一定程度上減少了映射受位置變化影響的程度，提高了準(zhǔn)確率，但是仍難于處理近似克隆代碼的情況；基于文本的映射，以克隆代碼間的文本相似程度作為映射的主要依據(jù)，其采用的文本相似度值通常是通過最長公共子序列算法或編輯距離算法來獲得，這兩種算法的時間和空間復(fù)雜度都是O（n2），這直接導(dǎo)致克隆群映射的效率低下，無法適用于克隆代碼規(guī)模較大的情況；基于函數(shù)映射的克隆映射方法，一定程度上提高了映射的效率和準(zhǔn)確度，但由于對函數(shù)信息存在過度依賴，當(dāng)克隆代碼不在函數(shù)內(nèi)部或者函數(shù)在下一版本發(fā)生分裂或合并等情況時，映射就會失?。皇褂冒姹竟芾砉ぞ哂成?，所需的時間復(fù)雜度高；利用增量的克隆檢測算法能去除冗余計算，節(jié)省了時間，降低了時間復(fù)雜度，但是不能分析后期版本中新產(chǎn)生的克隆群。

本文提出一種新的基于主題建模技術(shù)的克隆群映射方法，與基于文本的映射方法不同的是，本文映射的基礎(chǔ)集合是克隆群主題，不是代碼的中間表示形式 （如token串、AST 等），相比之下，主題具有面向語義、粒度大、抽象層次更高的特點，并且，同一版本的不同克隆群的主題差異很大，不同版本的有映射關(guān)系的克隆群的主題差異很小，甚至沒有差異?？寺〈a的這一特征決定了本文提出的基于主題映射克隆群的方法的可行性及有效性。

2 基于主題建模技術(shù)的克隆群映射方法

2.1 主題建模技術(shù)簡介

主題建模技術(shù)最早產(chǎn)生并應(yīng)用于信息檢索和自然語言處理領(lǐng)域［9］。主題模型是一種概率生成模型［10］，描述了一種用以生成文檔的概率過程。LDA 是目前應(yīng)用最廣的主題模型，本文同樣采用LDA。

LDA 是一種對文本建模的方法，它將文本表示成一個由文檔 （document）、主題 （topic）和詞 （word）組成的3層概率模型，常被用來做主題分析［11］。文檔可以看成是由多個主題組成的，同樣地，主題可以看成是由多個詞組成的。反過來，也可以將文檔中的每個詞看成由某主題生成的。那么，我們就可以通過某個主題生成單詞的數(shù)量來確定該主題的重要程度。例如，有的主題可能生成文檔中20%的詞，但有的主題可能只生成2%的詞。

在LDA 主題模型中，LDA 建模技術(shù)能挖掘文檔中的主題，每個主題由一些經(jīng)常出現(xiàn)在一起的詞組成。例如，如果從某文章提取的主題包含詞 ｛bank，finance，money，cash，loan｝，則該主題可能是關(guān)于finance industry話題的，另一個主題包含詞 ｛river，bank，water，stream，fish｝，則該主題可能代表river的話題，所以，每個文檔能被它們各自的主題代表。這樣一來，通過LDA 建模，可以將文本映射到主題空間上，從而對其進行主題分類和判斷相似度等操作。

與傳統(tǒng)的代碼元素 （類、方法等）相比，主題具有面向語義、粒度更大、抽象層次更高等特點［12］，這為代碼分析研究提供了新的研究方法與研究視角。近年來，應(yīng)用主題建模技術(shù)研究代碼及相關(guān)軟件制品成為研究熱點之一。Kuhn等［13］最先嘗試將主題建模技術(shù)應(yīng)用于代碼，并嘗試從中挖掘功能性主題；Thomas等［14］用主題建模技術(shù)研究軟件的演化，通過主題的演化信息來分析軟件在多版本的演化情況；Asuncion等［15］將主題建模技術(shù)用于軟件的可追蹤性研究；Tian等［16］則嘗試使用LDA 對軟件資源庫中的軟件進行自動分類；Gethersd等［17］通過開發(fā)集成開發(fā)環(huán)境插件，進一步將代碼主題建模的結(jié)果與現(xiàn)有軟件開發(fā)工具結(jié)合，幫助開發(fā)人員應(yīng)用主題建模結(jié)果；北京航空航天大學(xué)的劉超等［18］將LDA 用于文檔和代碼間的相關(guān)性分析和檢查其相互之間的可追蹤性問題上；北京大學(xué)的謝冰［19］等運用LDA 識別代碼功能以支持軟件開發(fā)人員的代碼復(fù)用。此外，主題模型還被用于類的內(nèi)聚性Liu［20］和bug定位［10］等研究中。

本文將主題建模技術(shù)應(yīng)用于克隆代碼的研究，提出一種新的克隆群映射方法，利用克隆群中提取的主題的相似性來確定相鄰版本中克隆群的映射關(guān)系。

2.2 克隆群映射算法

2.2.1 克隆群映射算法框架

本文使用LDA 主題建模技術(shù)實現(xiàn)克隆群的映射，從克隆群代碼中挖掘主題，通過主題間的相似性來映射主題，進而間接實現(xiàn)版本間克隆群的映射。算法的框架如圖1所示。

圖1 克隆群映射算法框架

本算法采用提取主題、主題相似度計算、確定映射關(guān)系相結(jié)合的方式來進行克隆群的映射。算法的基本思路是，按特定的順序，首先用主題建模技術(shù)分別對后一版本和前一版本的每個克隆群分別提取主題 （克隆群主題），此時提取到的主題能唯一表征該克隆群，這樣就將映射問題由高維的代碼空間轉(zhuǎn)化到低維的主題空間上，之后通過判定相鄰版本的主題相似性來映射克隆群主題，進而間接達到準(zhǔn)確映射相鄰版本克隆群的目的?？寺∪河成渌惴枋鋈缦拢?/p>

下面從兩方面對該算法進行說明。

2.2.2 提取克隆群主題

軟件在規(guī)范編程風(fēng)格下，適宜用LDA 模型提取主題。本文使用MALLET 主題建模工具包來提取主題，MALLET 是基于java的自然語言處理工具箱，用于文本的分類、聚類、主題建模、信息抽取等涉及機器學(xué)習(xí)在文本方面的應(yīng)用。MALLET 是基于抽樣的LDA 實現(xiàn)來進行主題建模的。

每個克隆群中提取到的主題是能唯一表征該克隆群信息的單詞組合，但是，代碼中包含大量停用詞，而這些詞對表征克隆群信息起的作用較小，它們的頻繁出現(xiàn)會對主題產(chǎn)生噪音，所以在提取主題時需要先去掉停用詞。本文中的停用詞主要有三類：①編程語言中的一些關(guān)鍵字，例如 “for”、 “return”和 “class”等；②常用的編程相關(guān)詞匯，例如 “main”、“arg”和 “util”等；③通用的英語語言停用詞，例如 “the”、“it”和 “on”。

為使主題更準(zhǔn)確的代表源代碼的信息，提取適當(dāng)數(shù)量的主題是影響克隆群映射準(zhǔn)確性的關(guān)鍵。如果對每個克隆群提取的主題個數(shù)太多，會使主題過于分散，不易集中反映本克隆群的代碼信息；如果提取的主題個數(shù)太少，將導(dǎo)致一個主題包含太多信息，主題間的區(qū)分度不佳，不能準(zhǔn)確反映克隆群的真實情況。我們經(jīng)過實驗分析論證發(fā)現(xiàn)，對每個克隆群提取一個主題為最佳。這是因為，同一克隆群中的克隆都是結(jié)構(gòu)和內(nèi)容完全或近似相同的代碼段，這些代碼段實現(xiàn)的是同一種功能，即整個克隆群就是同一個克隆的多個副本，也就是說，一個克隆群就是關(guān)于一個主題的，故選擇提取一個主題作為每個克隆群的主題代表。MALLET 提取到的某克隆群的主題如圖2所示。

圖2 MALLET 提取的某克隆群的主題

2.2.3 映射克隆群主題

克隆群映射是通過對比兩個版本間克隆群中克隆代碼的匹配程度來判斷它們是否是同一個對象。目前在克隆代碼演化研究領(lǐng)域應(yīng)用的代碼相似度度量主要是基于位置的度量和基于文本的度量?；谖谋镜亩攘渴鞘褂锰囟ǖ奈谋鞠嗨贫?（TextSimilarity）計算方法，如最長公共子序列（longest common subsequence，LCS）或編輯距離 （edit distance，也叫l(wèi)evenshtein distance，LD）來判斷代碼間的相似程度?；谖恢玫亩攘恐饕怯嬎銉啥未a的位置重疊率 （Location OverlappingRate）。首先將克隆代碼的起止行號表示成基于函數(shù)或塊的相對行號，然后依據(jù)特定計算公式計算位置重疊率。

本文克隆群映射關(guān)系是間接通過克隆群主題確定的。相鄰版本中的克隆群主題具有映射關(guān)系的依據(jù)是：這兩個主題相似度最高，且相似度值都不低于某個閾值δ。實驗發(fā)現(xiàn)，凡是有映射關(guān)系的克隆群，它們主題的相似度都很接近于1；而只有極少一部分有映射關(guān)系的克隆群，其主題相似度在0.8到1之間，這部分克隆群一般都是type2，type3類型的克?。欢黝}相似度低于0.8的，一般不具有映射關(guān)系。故將克隆相似度閾值δ定為0.8。

本文的克隆群映射算法，映射是從后一版本向前一版本進行的。這是因為軟件在版本更迭過程中，克隆群數(shù)量一般呈上升趨勢，如果從后面版本向前面版本映射，那么消失的克隆群就映射不上；反之，新產(chǎn)生的克隆群就映射不上。由于在克隆代碼演化研究中，我們對當(dāng)前版本臨近版本的克隆代碼比較感興趣，也就是相對于消失的克隆群，我們對新產(chǎn)生的克隆群更加感興趣，基于這種考慮，本文從后面版本向前面版本進行映射，即本文的映射工作是克隆群找起源的過程。

當(dāng)建立了相鄰版本的克隆群主題的映射關(guān)系后，就間接實現(xiàn)了對應(yīng)克隆群的映射關(guān)系。

3 實驗結(jié)果與分析

3.1 實驗數(shù)據(jù)

由于軟件系統(tǒng)的規(guī)模不一、開發(fā)方式不同，每個版本中所含克隆代碼數(shù)量有很大差異，平均每個版本中的克隆群數(shù)量從幾十到上千不等，鑒于人工驗證的局限性，所以本文選用的是4款來自不同領(lǐng)域、使用不用語言編寫的中小規(guī)模的開源軟件作為目標(biāo)軟件，并從每款軟件中選用了適當(dāng)數(shù)量的版本，對本文提出的基于主題建模技術(shù)的克隆群映射進行了實驗，以檢驗該方法的有效性。目標(biāo)軟件的詳細信息見表1。

表1 實驗所用軟件的信息

需要說明的是，克隆檢測工具為克隆群映射工作提供基礎(chǔ)數(shù)據(jù)，克隆代碼檢測結(jié)果是否準(zhǔn)確、全面直接影響映射的有效性。因此，本文選用的是目前一款成熟的檢測完全克隆和近似克隆的工具Nicad，它能檢測多種語言 （C、JAVA、C＃）編寫的Type－1、Type－2和Type－3克隆代碼，有很高的查準(zhǔn)率和查全率。本實驗首先用Nicad在Linux平臺上對各目標(biāo)軟件的相鄰版本進行functions粒度下的克隆代碼檢測，然后，將檢測結(jié)果中的克隆群文件移至Win－dows平臺，進行克隆群映射。

3.2 評價方法

為檢驗本方法的有效性，本文采用人工驗證的方法從查準(zhǔn)率和查全率兩方面進行衡量。定義如下

其中，查準(zhǔn)率能體現(xiàn)算法的正確度，而查全率能體現(xiàn)算法的搜索能力。

3.3 實驗結(jié)果及分析

以軟 件bluefish 為例，bluefish 的連續(xù)版本2.2.4 和2.2.3克隆群映射結(jié)果如圖3所示。

圖3 bluefish的2.2.4和2.2.3克隆群映射結(jié)果

圖中第2、3 列的數(shù)字表示相應(yīng)版本的克隆群編號，bluefish2.2.4有0號到18號共19個克隆群，bluefish2.2.3有0號到19號共20個克隆群，箭頭表示克隆群有映射關(guān)系，例如，bluefish2.2.4版本的14 號克隆群映射到bluefish2.2.3版本的16號克隆群；bluefish2.2.4的8號克隆群在bluefish2.2.3中沒有找到映射，即bluefish2.2.4中的8號克隆群可能是新出現(xiàn)的克隆群，也可能是在上一版本到當(dāng)前版本的演化中發(fā)生較大變化，超過了映射所允許的閾值；bluefish2.2.3的8號和9號克隆群沒有出現(xiàn)在列表中，說明bluefish在由2.2.3版本演化到2.2.4版本時，8號和9號克隆群可能被刪除，或者是發(fā)生了較大的修改，從映射關(guān)系中脫離的克隆群。圖中第1列表示，后一版本的某克隆群和前一版本中的克隆群所能達到的最大相似度值，該值不小于0.8即表示找到了映射。圖中可以看出，大部分具有映射關(guān)系的克隆群的相似度值高達1，即說明大部分克隆群在版本更迭過程中沒有改變；極少部分的相似度值不為1，是因為該克隆群中的克隆代碼在更迭過程中做了某種程度上的改變，或整個克隆群被刪除，或有少量語句的增加或去除等。

對其它目標(biāo)軟件的某些連續(xù)版本的克隆群映射，并人工驗證映射的查準(zhǔn)率和查全率，結(jié)果見表2和表3。

表2 本方法的實驗結(jié)果1

表3 本方法的實驗結(jié)果2

從表2和表3可以看出，本方法的查準(zhǔn)率可達0.99以上，而查全率也基本在0.99以上，實驗結(jié)果體現(xiàn)了本文的克隆群映射方法的有效性。相鄰版本間克隆群映射所花費的時間在可以接受的范圍內(nèi)，而且查準(zhǔn)率與查全率比較理想。因為某些軟件中克隆群數(shù)量較大，再加上人工驗證的局限性，僅在上述4款軟件的12個版本上進行了驗證，但上述結(jié)果足以說明本算法的有效性。

進一步分析發(fā)現(xiàn)，影響算法有效性的原因可能有以下幾個方面：

（1）主題相似度閾值。本文的主題相似度閾值是人為指定的，且所有軟件都使用相同的閾值，這在一定程度上影響了映射的準(zhǔn)確性。首先，人為制定的相似度閾值不能發(fā)揮映射算法的最大效能。其次，不同的系統(tǒng)所用語言不同，代碼風(fēng)格不同，版本間的差異程度也不同，使用相同的閾值不能很好適應(yīng)目標(biāo)的實際，同樣會使映射算法的有效性降低。

（2）克隆檢測工具的性能?？寺z測工具為克隆群映射提供基礎(chǔ)數(shù)據(jù)，克隆代碼檢測結(jié)果是否準(zhǔn)確，全面直接影響克隆群映射的有效性。因此，選用一款準(zhǔn)確高效的克隆代碼檢測工具對映射工作非常關(guān)鍵。

（3）版本間的差異。由實驗結(jié)果發(fā)現(xiàn)，版本間的差異越小，映射的準(zhǔn)確率越高。如果克隆群在版本更迭過程中沒有改變或改變很小時，具有映射關(guān)系的克隆群的相似度高達1，但是如果克隆群做了較大改變超過了映射所允許的閾值，這樣會使本來具有映射關(guān)系的克隆群不能準(zhǔn)確映射。即突變或較大差異會使映射的有效性降低。因此，使用差異較小的修訂版而不是發(fā)布版，是提高克隆群映射有效性的方法。

4 結(jié)束語

軟件系統(tǒng)中大量克隆代碼對軟件產(chǎn)生了一定的影響，而在克隆代碼的演化研究中，克隆群映射起著非常重要的作用。本文提出的基于主題建模技術(shù)的克隆群映射方法，運用主題建模技術(shù)將映射問題由高維的代碼空間轉(zhuǎn)化到低維的主題空間上，通過相鄰版本的克隆群主題的映射，進而間接實現(xiàn)了準(zhǔn)確映射相鄰版本克隆群的目的。最后在4款軟件的12個版本上進行了實驗，對實驗結(jié)果進行人工判斷，發(fā)現(xiàn)本方法的查準(zhǔn)率和查全率都高達0.99，充分驗證了本方法的可行性和有效性。

［1］Bettenburg N，Shang W，Ibrahim W，et al.An empirical study on inconsistent changes to code clones at release level［C］//Proc of the 16th Working Conference on Reverse Engineering.IEEE Press，2009：85－94.

［2］Zibran M F，Roy C K.The road to software clone management：A survey ［R］.Technical Report，The University of Saskatchewan，2012：1－66.

［3］Saha R K，Asduzzaman M，Zibran M F，et al.Evaluating code clone genealogies at release level：An empirical study［C］//Proceedings of the 10th IEEE Working Conference on Source Code Analysis and Manipulation. Washington DC：IEEE Computer Society，2010：87－96.

［4］Bakota T，F(xiàn)erenc R，Gyimothy T.Clone smells in software evolution ［C］//IEEE International Conference on Software Maintenance. Washington DC：IEEE Computer Society，2007：24－33.

［5］Saha R K，Roy C K，Schneider K A.An automatic framework for extracting and classifying near－miss clone genealogies［C］//27th IEEE International Conference on Software Maintenance，2011：293－302.

［6］Barbour L，Khomh F，Zou Y.Late propagation in software clones［C］//Proceedings of the 27th IEEE International Conference on Software Maintenance. Washington DC：IEEE Computer Society，2011：273－282.

［7］Gode N，Koschke R.Incremental clone detection ［C］//Proceedings of the European Conference on Software Maintenance and Reengineering.Washington DC：IEEE Computer Society，2009：219－228.

［8］Duala－Ekoko E，Robillard M P.Tracking code clones in evolving software ［C］//Proceedings of the 29th International Conference on Software Engineering.Washington DC：IEEE Computer Society，2007：158－167.

［9］Grant S，Cordy J.Estimating the optimal number of latent concepts in source code analysis［C］//10th IEEE Working Conference on Source Code Analysis and Manipulation，2010：65－74.

［10］Lukins S，Kraft N，Etzkorn L.Bug localization using latent Dirichlet allocation ［J］.Information and Software Technology，2010，52 （9）：972－990.

［11］De Lucia A，Oliveto R，Vorraro L.Using structural and semantic metrics to improve class cohesion ［C］//IEEE International Conference on Software Maintenance，2008：27－36.

［12］Marcus A，Poshyvanyk D，F(xiàn)erenc R.Using the conceptual cohesion of classes for fault prediction in object－oriented systems ［J］.IEEE Transactions on Software Engineering，2008，34 （2）：287－300.

［13］Kuhn A，Ducasse S，Gírba T.Semantic clustering：Identifying topics in source code ［J］.Information and Software Technology，2007，49 （3）：230－243.

［14］Thomas S W，Adams B，Hassan A E，et al.Studying software evolution using topic models ［J］.Science of Computer Programming，2012.

［15］Asuncion H，Asuncion A，Taylor R.Software traceability with topic modeling ［C］//32nd ACM/IEEE International Conference on Software Engineering，2010：95－104.

［16］Tian K，Revelle M，Poshyvanyk D.Using Latent Dirichlet Allocation for automatic categorization of software［C］//6th IEEE International Working Conference on Mining Software Repositories，2009：163－166.

［17］Gethers M，Savage T，Di Penta M，et al.CodeTopics：Which topic am I coding now？［C］//33rd International Conference on Software Engineering，2011：1034－1036.

［18］HAN Xiaodong，WANG Xiaobo，LIU Chao.Retrieval method for traceability links between source code and Chinese documentation［J］.Journal of Hefei University of Technology：Natural Science，2010，33 （2）：188－192（in Chinese）. ［韓曉東，王曉博，劉超.中文文檔與源代碼間關(guān)聯(lián)關(guān)系提取方法的研究［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33 （2）：188－192.］

［19］JIN Jing，LI Meng，HUA Zhebang，et al.Code function recognition approach based on LDA and static analysis ［J］.Computer Engineering and Applications，2013，49 （15）：37－31 （in Chinese）.［金靖，李萌，華哲邦，等.一種基于LDA和靜態(tài)分析的代碼功能識別方法 ［J］.計算機工程與應(yīng)用，2013，49 （15）：27－31］.

［20］Liu Y，Poshyvanyk D，F(xiàn)erenc R，et al.Modeling class cohesion as mixtures of latent topics ［C］//IEEE International Conference on Software Maintenance，2009：233－242.