基于主題建模技術的克隆群映射方法

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

（內蒙古師范大學 計算機與信息工程學院，內蒙古 呼和浩特010022）

0 引 言

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

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

1 克隆群及其映射方法

1.1 克隆群相關定義

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

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

1.2 克隆群映射及方法

一款軟件在不斷升級過程中會產生多個版本，某個版本中的克隆群在下個相鄰版本中究竟發生了怎樣的變化，需要我們通過對軟件相鄰兩個版本中的克隆群進行映射來做出判斷。克隆群映射是指當前版本的克隆群由上一版本的哪個克隆群演化而來的，反映了軟件各個版本中的克隆群的對應關系。

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

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

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

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

2.1 主題建模技術簡介

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

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

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

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

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

2.2 克隆群映射算法

2.2.1 克隆群映射算法框架

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

圖1 克隆群映射算法框架

本算法采用提取主題、主題相似度計算、確定映射關系相結合的方式來進行克隆群的映射。算法的基本思路是，按特定的順序，首先用主題建模技術分別對后一版本和前一版本的每個克隆群分別提取主題 （克隆群主題），此時提取到的主題能唯一表征該克隆群，這樣就將映射問題由高維的代碼空間轉化到低維的主題空間上，之后通過判定相鄰版本的主題相似性來映射克隆群主題，進而間接達到準確映射相鄰版本克隆群的目的。克隆群映射算法描述如下：

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

2.2.2 提取克隆群主題

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

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

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

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

2.2.3 映射克隆群主題

克隆群映射是通過對比兩個版本間克隆群中克隆代碼的匹配程度來判斷它們是否是同一個對象。目前在克隆代碼演化研究領域應用的代碼相似度度量主要是基于位置的度量和基于文本的度量。基于文本的度量是使用特定的文本相似度 （TextSimilarity）計算方法，如最長公共子序列（longest common subsequence，LCS）或編輯距離 （edit distance，也叫levenshtein distance，LD）來判斷代碼間的相似程度。基于位置的度量主要是計算兩段代碼的位置重疊率 （Location OverlappingRate）。首先將克隆代碼的起止行號表示成基于函數或塊的相對行號，然后依據特定計算公式計算位置重疊率。

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

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

當建立了相鄰版本的克隆群主題的映射關系后，就間接實現了對應克隆群的映射關系。

3 實驗結果與分析

3.1 實驗數據

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

表1 實驗所用軟件的信息

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

3.2 評價方法

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

其中，查準率能體現算法的正確度，而查全率能體現算法的搜索能力。

3.3 實驗結果及分析

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

圖3 bluefish的2.2.4和2.2.3克隆群映射結果

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

對其它目標軟件的某些連續版本的克隆群映射，并人工驗證映射的查準率和查全率，結果見表2和表3。

表2 本方法的實驗結果1

表3 本方法的實驗結果2

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

進一步分析發現，影響算法有效性的原因可能有以下幾個方面：

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

（2）克隆檢測工具的性能。克隆檢測工具為克隆群映射提供基礎數據，克隆代碼檢測結果是否準確，全面直接影響克隆群映射的有效性。因此，選用一款準確高效的克隆代碼檢測工具對映射工作非常關鍵。

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

4 結束語

軟件系統中大量克隆代碼對軟件產生了一定的影響，而在克隆代碼的演化研究中，克隆群映射起著非常重要的作用。本文提出的基于主題建模技術的克隆群映射方法，運用主題建模技術將映射問題由高維的代碼空間轉化到低維的主題空間上，通過相鄰版本的克隆群主題的映射，進而間接實現了準確映射相鄰版本克隆群的目的。最后在4款軟件的12個版本上進行了實驗，對實驗結果進行人工判斷，發現本方法的查準率和查全率都高達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，Ferenc 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，Ferenc 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）. ［韓曉東，王曉博，劉超.中文文檔與源代碼間關聯關系提取方法的研究［J］.合肥工業大學學報：自然科學版，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和靜態分析的代碼功能識別方法 ［J］.計算機工程與應用，2013，49 （15）：27－31］.

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