基于改進(jìn)向量空間模型的克隆群映射方法

1、 基于改進(jìn)向量空間模型的克隆群映射方法 陳桌 張麗萍 王歡 張久杰 王春暉Summary：針對(duì)Type3克隆代碼映射方法少且效率低等問(wèn)題，提出了一種基于改進(jìn)向量空間模型（VSM）的映射方法。該方法將改進(jìn)的VSM引入到克隆代碼分析中，從而得到一種可有效映射Type1、Type2以及Type3克隆代碼的克隆群映射方法。首先，將克隆群文檔預(yù)處理得到去除無(wú)用詞的代碼文檔，同時(shí)提取克隆群文檔的文件名、函數(shù)名等特征項(xiàng)；其次，提取并構(gòu)建克隆群詞頻向量空間，利用余弦算法計(jì)算出克隆群相似度；然后，通過(guò)克隆群相似度和特征項(xiàng)的匹配構(gòu)建克隆群映射，最終得到克隆群映射結(jié)果。對(duì)5款開(kāi)源軟件進(jìn)行實(shí)驗(yàn)并人工驗(yàn)證，所提方法能在

2、低時(shí)耗的前提下，保證查全率和查準(zhǔn)率均不低于96.1%和97.1%。實(shí)驗(yàn)結(jié)果表明了所提方法的可行性，為后期軟件演化分析提供數(shù)據(jù)支撐。Key：克隆代碼；克隆群映射；向量空間模型；特征項(xiàng)；詞頻： TP311.5 文獻(xiàn)標(biāo)志碼：A0引言在軟件開(kāi)發(fā)和維護(hù)過(guò)程中，開(kāi)發(fā)人員經(jīng)常采用復(fù)制粘貼的方式修改代碼，導(dǎo)致重復(fù)的代碼片段出現(xiàn)，即克隆代碼1。以前的研究2已經(jīng)表明，一個(gè)軟件系統(tǒng)中會(huì)有9%15%的克隆代碼，有時(shí)甚至高達(dá)50%以上，相同或相似的代碼會(huì)增加軟件的維護(hù)費(fèi)用。例如，如果一個(gè)bug在代碼片段中被檢測(cè)出來(lái)，所有和它相似的片段都應(yīng)該被調(diào)查，檢查相同的錯(cuò)誤，加強(qiáng)或調(diào)整這些代碼。所以對(duì)系統(tǒng)版本中的克隆進(jìn)行追蹤非常有

3、意義。相鄰版本間的克隆群映射是研究克隆代碼演化3工作的關(guān)鍵步驟，克隆演化研究關(guān)注的是一段克隆代碼在軟件多個(gè)版本中的變化情況，而克隆群映射是整個(gè)演化過(guò)程的紐帶。本文提出的克隆群映射方法是根據(jù)自然語(yǔ)言領(lǐng)域中計(jì)算文章相似度的向量空間模型（Vector Space Model， VSM）改進(jìn)的。向量空間模型4就是把對(duì)文本內(nèi)容的處理簡(jiǎn)化為向量空間中的向量運(yùn)算，并且以空間上的相似度表達(dá)文本的相似度，直觀易懂。當(dāng)文檔被表示為文檔空間的向量，就可以通過(guò)計(jì)算向量之間的相似性來(lái)度量文檔間的相似性。在克隆代碼方面，改進(jìn)的向量空間模型的基本思想是把每個(gè)版本中的克隆群簡(jiǎn)化為以特征項(xiàng)（Key）的權(quán)重為分量的N維向量，結(jié)果

4、用十分簡(jiǎn)單的向量表示，使得模型具備了可計(jì)算性，有效衡量克隆群之間的相似性，并建立版本間的映射。1相關(guān)工作1.1克隆定義與分類(lèi)克隆代碼的定義目前廣受采納的是將具有相似語(yǔ)法及語(yǔ)義特征5的代碼段稱(chēng)為克隆代碼。系統(tǒng)同一版本中的兩段相似代碼片段稱(chēng)為克隆對(duì)。兩個(gè)或多個(gè)相似代碼片段組成一個(gè)克隆群。追蹤從前一版本到當(dāng)前版本克隆群的變化過(guò)程稱(chēng)為克隆群映射?，F(xiàn)有研究中，克隆主要有以下兩種分類(lèi)方法6：一是相似程度，二是代碼段的粒度。按源代碼文本相似性將克隆分為T(mén)ype1型至Type4型克隆（定義見(jiàn)表1），其中Type1至Type3體現(xiàn)了語(yǔ)法上的相似程度，Type4體現(xiàn)了語(yǔ)義上的相似程度。按克隆關(guān)系中代碼段的粒度分為

5、文件、塊、函數(shù)、類(lèi)及語(yǔ)句等類(lèi)型。1.2克隆映射克隆映射（Clone mapping）是對(duì)軟件版本間的兩個(gè)克隆建立映射關(guān)系，其映射條件是具有映射關(guān)系的兩個(gè)克隆具有同源性。如何計(jì)算這些相似關(guān)系，并找出最大相似的克隆實(shí)例對(duì)它們建立映射關(guān)系，是克隆映射過(guò)程需要解決的問(wèn)題。目前構(gòu)建克隆映射的方法主要有7類(lèi)6。1）先檢測(cè)軟件第一個(gè)版本中的克隆，然后根據(jù)并發(fā)版本系統(tǒng)（Concurrent Version System， CVS）代碼庫(kù)中提供的修改日志，計(jì)算版本間的變化，最終得到映射關(guān)系7。由于以第一個(gè)版本中的克隆為映射源，因而無(wú)法研究在后期版本中引入的克隆。2）檢測(cè)所有版本中的克隆，然后基于文本相似性及位置

6、關(guān)系追溯映射8-9。此方法適用于多種不同的克隆演化研究，但時(shí)間復(fù)雜度高，且映射的最小閾值是經(jīng)驗(yàn)值，易受克隆中大變化的影響。3）對(duì)所有版本進(jìn)行克隆檢測(cè)，將檢測(cè)到的克隆代碼抽象成克隆區(qū)域描述符（Clone Region Descriptor， CRD），然后在不同版本中跟蹤C(jī)RD，通過(guò)檢測(cè)CRD中的文本區(qū)別構(gòu)建映射關(guān)系10。此方法映射的建立不受克隆位置信息的影響，易實(shí)現(xiàn)克隆的一致修改，但映射誤報(bào)率偏高。4）使用增量的算法將克隆檢測(cè)與映射結(jié)合在一起11。該方法時(shí)間復(fù)雜度低，適合處理給定版本的軟件，但添加新版本時(shí)整個(gè)檢測(cè)與映射需重新執(zhí)行，空間復(fù)雜度高。5）先映射相鄰版本間的函數(shù)，在此基礎(chǔ)上實(shí)現(xiàn)克隆映射

7、12。該方法減少了運(yùn)行時(shí)間，但易受重載函數(shù)與覆蓋的函數(shù)影響。6）利用源代碼的文本和結(jié)構(gòu)信息，將映射問(wèn)題由高維的代碼空間轉(zhuǎn)化到低維的主題空間13上，通過(guò)映射主題來(lái)準(zhǔn)確地構(gòu)建相鄰版本克隆群的映射關(guān)系，但沒(méi)有考慮每個(gè)主題詞所占的整體比例。7）先將克隆群源代碼Token化14，得到克隆群的Token序列，然后比較其Token串之間的相似度，并最終得到克隆群的映射關(guān)系，但無(wú)法準(zhǔn)確映射Type3類(lèi)型的克隆代碼，且演化過(guò)程中文件被重命名，可能無(wú)法準(zhǔn)確追蹤。1.3向量空間模型向量空間模型（VSM）是由Salton等15于20世紀(jì)年代提出的一種文本表示模型，并應(yīng)用于文本檢索系統(tǒng)。其基本思想就是將文本文檔以Key

8、向量的形式表示，每個(gè)文本文檔可以表示成一個(gè)Key的特征向量，再計(jì)算得到Key的權(quán)重向量；最后計(jì)算權(quán)重向量中間的余弦相似度，并返回結(jié)果。權(quán)重向量為：V（d）=（t1，w1（d）；t2，w2（d）；tn，wn（d），其中：V（d）是文檔d的向量表示，ti表示文檔中的特征項(xiàng)，wi（d）表示特征項(xiàng)ti在文檔d中的權(quán)值，ti在文檔d中出現(xiàn)的頻率，即wi（d）=（tfi（d）。計(jì)算方法中每一個(gè)特征項(xiàng)的權(quán)重取決于兩個(gè)元素：特征項(xiàng)ti在文檔d中的詞頻（Term Frequency， TF）和在整個(gè)文檔集的逆向文件頻率（Inverse Document Frequency， IDF）。信息檢索中最常用到權(quán)重計(jì)算

9、方法是TFIDF（Term FrequencyInverse Document Frequency）函數(shù)，此計(jì)算公式為：=tfi（d）lb （N/ni）（1）其中：N表示原文檔的數(shù)目，ni表示含有詞條ti的所有文檔的數(shù)目。計(jì)算公式：wi（d）=tfi（d） lb （N/ni+0.1）ni=1（tfi（d）2lb2（N/ni+0.1）（2）log的底是多少？是2吧？那么縮寫(xiě)為lb？其上面的2是上標(biāo)嗎？請(qǐng)明確。一方面，在整個(gè)文檔集中包含文檔中某一詞的數(shù)量越多，則說(shuō)明其重要程度代表性越低，其重要程度也就越??；另一方面，某一詞在文檔中出現(xiàn)的頻率越高，則說(shuō)明其重要程度的代表性越強(qiáng)，其重要程度也就越大。一

10、種常見(jiàn)的相似度測(cè)量是著名的余弦測(cè)量，當(dāng)文檔向量與查詢(xún)向量被表示成向量時(shí)，它決定了兩者之間的角度，如式（3）：Sim（di，dj）=cos =nk=1k（di）k（dj）/（ni=12k（di）（nj=12k（dj）（3）特征項(xiàng)的權(quán)重被確定以后，需要一個(gè)排名函數(shù)來(lái)測(cè)量查詢(xún)和文檔向量之間的相似度。一個(gè)文檔Di和一個(gè)查詢(xún)Q之間的相似度定義為：1.4改進(jìn)向量空間模型基于TFIDF算法思想，本文將自然語(yǔ)言領(lǐng)域中的向量空間模型應(yīng)用于代碼克隆領(lǐng)域，提出了一種新的克隆群映射方法。然而現(xiàn)有的向量空間模型并不完全適用于克隆代碼，TFIDF的核心思想為：某一特征項(xiàng)權(quán)重的高低依據(jù)的是在文檔中出現(xiàn)的頻率，出現(xiàn)頻率越高，

11、并且包含此項(xiàng)的文檔數(shù)越少，表示其權(quán)重越高，關(guān)聯(lián)程度更強(qiáng)，但這些僅僅是經(jīng)驗(yàn)公式，并不能真實(shí)反映出每個(gè)特征項(xiàng)的重要程度。這種思想并沒(méi)有考慮每一個(gè)特征項(xiàng)的整體比例，所以在確定每一個(gè)特征項(xiàng)權(quán)重時(shí)存在缺陷。另外，和形式語(yǔ)言不同，代碼文檔中的詞在整個(gè)文檔集中的出現(xiàn)比例并不能反映其重要程度，所以IDF的計(jì)算在軟件代碼文檔中并不適用，因此在代碼克隆領(lǐng)域中，須引入其他能表示克隆代碼重要程度的度量值?；谙蛄靠臻g模型的思想，利用TF概念以及代碼中的文件名、函數(shù)名等特征項(xiàng)，來(lái)表征克隆代碼的相似性。一方面，首先通過(guò)表示一個(gè)詞出現(xiàn)在文檔中的次數(shù)，統(tǒng)計(jì)詞頻建立詞頻向量，然后對(duì)其進(jìn)行規(guī)范化，最終利用cosine定理得到兩個(gè)

12、權(quán)重向量的相似度；另一方面，利用文件名以及函數(shù)名等特征項(xiàng)來(lái)匹配代碼片段的相似性權(quán)重。2基于改進(jìn)向量空間模型的克隆群映射方法2.1算法框架本文使用的是改進(jìn)的向量空間模型克隆群映射方法，從檢測(cè)結(jié)果中提取克隆群文檔，再?gòu)目寺∪何臋n中抽取詞頻向量進(jìn)行相似度計(jì)算，并匹配特征項(xiàng)，從而實(shí)現(xiàn)對(duì)版本間克隆群的映射。克隆群映射的流程如圖1所示。本文映射算法的思路為：首先對(duì)軟件的前一版本和后一版本中的每一個(gè)克隆群計(jì)算詞頻，得到每個(gè)克隆群的詞頻字典，然后構(gòu)建權(quán)重向量，得到克隆群相似度。同時(shí)提取克隆群中的特征項(xiàng)（文件名、函數(shù)名、起始行、結(jié)束行、代碼行數(shù)），通過(guò)特征項(xiàng)匹配得到特征相似度，最終得到克隆群映射結(jié)果，實(shí)現(xiàn)了從高

13、維度的代碼文檔空間到低維度的向量空間的轉(zhuǎn)換。克隆群映射算法如下所示。有序號(hào)的程序Shift+Alt+Y程序前輸入：FClones檢測(cè)結(jié)果。輸出：克隆群映射結(jié)果。1）對(duì)后一版本Vn+1中的每一個(gè)克隆群CGn+1，i2）統(tǒng)計(jì)CGn+1，i中每個(gè)詞的詞頻，存入字典Dn+1，i3）提取每個(gè)CGn+1，i的特征項(xiàng)，存入特征字典Tn+1，i4）對(duì)詞頻字典規(guī)范化5）對(duì)前一版本Vn中的每一個(gè)克隆群CGn， j6）統(tǒng)計(jì)CGn， j中每個(gè)詞的詞頻，存入字典Dn， j7）提取每個(gè)CGn，i的特征項(xiàng)，存入特征字典Tn，i8）對(duì)詞頻字典規(guī)范化9）遍歷比較Dn+1，i和Dn， j之間相似度，存儲(chǔ)到數(shù)組cosin中10）遍

14、歷匹配Tn+1，i和Tn， j，并存儲(chǔ)到數(shù)組T中11）IF cosink=t & Tk=True12）THEN CGn+1，i映射到CGn， j13）即CGn+1，i CGn， j14）ELSE15）CGn+1，i NULL16）返回映射結(jié)果程序后2.2克隆群向量空間2.2.1克隆群文檔預(yù)處理預(yù)處理是克隆群映射的基礎(chǔ)工作。相比自然語(yǔ)言文本信息，形式語(yǔ)言中代碼不僅包括與其功能相關(guān)的信息，也包括大量的程序語(yǔ)言信息。與編程相關(guān)的信息在其領(lǐng)域內(nèi)大多是相對(duì)獨(dú)立的，幾乎不包含代碼以及軟件的功能信息。為保證克隆群映射更加準(zhǔn)確，須將源代碼中的編程相關(guān)信息進(jìn)行過(guò)濾。本文使用檢測(cè)結(jié)果是由本團(tuán)隊(duì)開(kāi)發(fā)的檢測(cè)工具Fcl

15、ones16檢測(cè)得到，檢測(cè)結(jié)果存儲(chǔ)在可擴(kuò)展標(biāo)記語(yǔ)言（Extensible Markup Language， XML）文件中，存儲(chǔ)方式如圖2所示。static void done_state_str （）str_list_destroy （on_list）；str_list_destroy （off_list）；str_list_destroy （on_off_list）；2.2.3構(gòu)建詞頻向量空間并規(guī)范化經(jīng)過(guò)研究之后發(fā)現(xiàn)，假設(shè)版本中克隆群有i個(gè)詞頻：D=D1，D2，Di，每個(gè)目標(biāo)都有相應(yīng)的關(guān)鍵字。不同關(guān)鍵字之間的數(shù)量級(jí)差異可能很大，如果直接用詞頻計(jì)算余弦距離，就不能很好地平均反映出每個(gè)關(guān)鍵字的

16、特性，所以必須對(duì)詞頻進(jìn)行規(guī)范化。詞頻規(guī)范化的方法如下：i=Di/（ni=0Di）（5）其中：Di是克隆群向量中詞頻的實(shí)際值；i為規(guī)范化后得到的權(quán)重值。獲得克隆群目標(biāo)權(quán)重向量：=1，2，i2.2.4計(jì)算向量空間相似度目前，克隆代碼領(lǐng)域內(nèi)判斷相似程度的方法主要有基于文本和位置的映射方法。基于文本的相似度計(jì)算方法包括：最長(zhǎng)公共子序列（Longest common subsequence）、杰卡德距離（Jaccard distance）、編輯距離（Levenshtein distance）等?；谖恢玫南嗨贫扔?jì)算方法是位置重疊率（Location overlapping rate）的計(jì)算，其原理就是將

17、克隆代碼的起止行號(hào)表示為克隆粒度的相對(duì)行號(hào)，然后依據(jù)特定的公式計(jì)算其重疊率。本文使用的相似性計(jì)算方式是余弦距離。計(jì)算兩個(gè)文本相似度時(shí)采用的相似度計(jì)算公式如下：CosSimilarity（i，j）=（ni， j=1（i*j）/ni=12inj=12j（6）其中：i*j指的是克隆群詞頻向量的內(nèi)積；CosSimilarity（i*j）的取值范圍是0，1。當(dāng)克隆群中的克隆片段在演化過(guò)程中發(fā)生了變化，CosSimilarity的值小于等于1，本文啟發(fā)式地設(shè)置一個(gè)閾值，把所有CosSimilarityt的克隆群對(duì)當(dāng)作候選的具有映射關(guān)系的克隆群對(duì)。如果一個(gè)克隆群在相鄰版本中有多個(gè)克隆群可能與其具有映射關(guān)系，則分別計(jì)算源代碼的相似性，選取源代碼相似性符合閾值條件的那些克隆群作為具有映射關(guān)系的候選克隆群。2.3克隆群特征項(xiàng)2.3.1選取克隆群特征項(xiàng)為了保證克隆群映射的準(zhǔn)確度，須匹配克隆群中的函數(shù)名等多個(gè)特征項(xiàng)，本文選取了文件名、函數(shù)名、起始行、結(jié)束行以及代碼行數(shù)5個(gè)特征項(xiàng)來(lái)衡量一個(gè)克隆群的屬性信息。具體特征項(xiàng)如表3所示。2.3.2提取特征項(xiàng)確定克隆群特征項(xiàng)之后，需提取出所需的克隆群特征項(xiàng)，并放入特征項(xiàng)字典中。文件名的屬性字典表示為：File=“文件名”：FileName，函數(shù)名屬性字典表示為：Fun=“函數(shù)名i”：FunNamei，每一個(gè)克隆群可能包含多個(gè)函數(shù)，所以字典中包含多