基于改进向量空间模型的克隆群映射方法

1、 基于改进向量空间模型的克隆群映射方法 陈桌 张丽萍 王欢 张久杰 王春晖Summary：针对Type3克隆代码映射方法少且效率低等问题，提出了一种基于改进向量空间模型（VSM）的映射方法。该方法将改进的VSM引入到克隆代码分析中，从而得到一种可有效映射Type1、Type2以及Type3克隆代码的克隆群映射方法。首先，将克隆群文档预处理得到去除无用词的代码文档，同时提取克隆群文档的文件名、函数名等特征项；其次，提取并构建克隆群词频向量空间，利用余弦算法计算出克隆群相似度；然后，通过克隆群相似度和特征项的匹配构建克隆群映射，最终得到克隆群映射结果。对5款开源软件进行实验并人工验证，所提方法能在

2、低时耗的前提下，保证查全率和查准率均不低于96.1%和97.1%。实验结果表明了所提方法的可行性，为后期软件演化分析提供数据支撑。Key：克隆代码；克隆群映射；向量空间模型；特征项；词频： TP311.5 文献标志码：A0引言在软件开发和维护过程中，开发人员经常采用复制粘贴的方式修改代码，导致重复的代码片段出现，即克隆代码1。以前的研究2已经表明，一个软件系统中会有9%15%的克隆代码，有时甚至高达50%以上，相同或相似的代码会增加软件的维护费用。例如，如果一个bug在代码片段中被检测出来，所有和它相似的片段都应该被调查，检查相同的错误，加强或调整这些代码。所以对系统版本中的克隆进行追踪非常有

3、意义。相邻版本间的克隆群映射是研究克隆代码演化3工作的关键步骤，克隆演化研究关注的是一段克隆代码在软件多个版本中的变化情况，而克隆群映射是整个演化过程的纽带。本文提出的克隆群映射方法是根据自然语言领域中计算文章相似度的向量空间模型（Vector Space Model， VSM）改进的。向量空间模型4就是把对文本内容的处理简化为向量空间中的向量运算，并且以空间上的相似度表达文本的相似度，直观易懂。当文档被表示为文档空间的向量，就可以通过计算向量之间的相似性来度量文档间的相似性。在克隆代码方面，改进的向量空间模型的基本思想是把每个版本中的克隆群简化为以特征项（Key）的权重为分量的N维向量，结果

4、用十分简单的向量表示，使得模型具备了可计算性，有效衡量克隆群之间的相似性，并建立版本间的映射。1相关工作1.1克隆定义与分类克隆代码的定义目前广受采纳的是将具有相似语法及语义特征5的代码段称为克隆代码。系统同一版本中的两段相似代码片段称为克隆对。两个或多个相似代码片段组成一个克隆群。追踪从前一版本到当前版本克隆群的变化过程称为克隆群映射。现有研究中，克隆主要有以下两种分类方法6：一是相似程度，二是代码段的粒度。按源代码文本相似性将克隆分为Type1型至Type4型克隆（定义见表1），其中Type1至Type3体现了语法上的相似程度，Type4体现了语义上的相似程度。按克隆关系中代码段的粒度分为

5、文件、块、函数、类及语句等类型。1.2克隆映射克隆映射（Clone mapping）是对软件版本间的两个克隆建立映射关系，其映射条件是具有映射关系的两个克隆具有同源性。如何计算这些相似关系，并找出最大相似的克隆实例对它们建立映射关系，是克隆映射过程需要解决的问题。目前构建克隆映射的方法主要有7类6。1）先检测软件第一个版本中的克隆，然后根据并发版本系统（Concurrent Version System， CVS）代码库中提供的修改日志，计算版本间的变化，最终得到映射关系7。由于以第一个版本中的克隆为映射源，因而无法研究在后期版本中引入的克隆。2）检测所有版本中的克隆，然后基于文本相似性及位置

6、关系追溯映射8-9。此方法适用于多种不同的克隆演化研究，但时间复杂度高，且映射的最小阈值是经验值，易受克隆中大变化的影响。3）对所有版本进行克隆检测，将检测到的克隆代码抽象成克隆区域描述符（Clone Region Descriptor， CRD），然后在不同版本中跟踪CRD，通过检测CRD中的文本区别构建映射关系10。此方法映射的建立不受克隆位置信息的影响，易实现克隆的一致修改，但映射误报率偏高。4）使用增量的算法将克隆检测与映射结合在一起11。该方法时间复杂度低，适合处理给定版本的软件，但添加新版本时整个检测与映射需重新执行，空间复杂度高。5）先映射相邻版本间的函数，在此基础上实现克隆映射

7、12。该方法减少了运行时间，但易受重载函数与覆盖的函数影响。6）利用源代码的文本和结构信息，将映射问题由高维的代码空间转化到低维的主题空间13上，通过映射主题来准确地构建相邻版本克隆群的映射关系，但没有考虑每个主题词所占的整体比例。7）先将克隆群源代码Token化14，得到克隆群的Token序列，然后比较其Token串之间的相似度，并最终得到克隆群的映射关系，但无法准确映射Type3类型的克隆代码，且演化过程中文件被重命名，可能无法准确追踪。1.3向量空间模型向量空间模型（VSM）是由Salton等15于20世纪年代提出的一种文本表示模型，并应用于文本检索系统。其基本思想就是将文本文档以Key

8、向量的形式表示，每个文本文档可以表示成一个Key的特征向量，再计算得到Key的权重向量；最后计算权重向量中间的余弦相似度，并返回结果。权重向量为：V（d）=（t1，w1（d）；t2，w2（d）；tn，wn（d），其中：V（d）是文档d的向量表示，ti表示文档中的特征项，wi（d）表示特征项ti在文档d中的权值，ti在文档d中出现的频率，即wi（d）=（tfi（d）。计算方法中每一个特征项的权重取决于两个元素：特征项ti在文档d中的词频（Term Frequency， TF）和在整个文档集的逆向文件频率（Inverse Document Frequency， IDF）。信息检索中最常用到权重计算

9、方法是TFIDF（Term FrequencyInverse Document Frequency）函数，此计算公式为：=tfi（d）lb （N/ni）（1）其中：N表示原文档的数目，ni表示含有词条ti的所有文档的数目。计算公式：wi（d）=tfi（d） lb （N/ni+0.1）ni=1（tfi（d）2lb2（N/ni+0.1）（2）log的底是多少？是2吧？那么缩写为lb？其上面的2是上标吗？请明确。一方面，在整个文档集中包含文档中某一词的数量越多，则说明其重要程度代表性越低，其重要程度也就越小；另一方面，某一词在文档中出现的频率越高，则说明其重要程度的代表性越强，其重要程度也就越大。一

10、种常见的相似度测量是著名的余弦测量，当文档向量与查询向量被表示成向量时，它决定了两者之间的角度，如式（3）：Sim（di，dj）=cos =nk=1k（di）k（dj）/（ni=12k（di）（nj=12k（dj）（3）特征项的权重被确定以后，需要一个排名函数来测量查询和文档向量之间的相似度。一个文档Di和一个查询Q之间的相似度定义为：1.4改进向量空间模型基于TFIDF算法思想，本文将自然语言领域中的向量空间模型应用于代码克隆领域，提出了一种新的克隆群映射方法。然而现有的向量空间模型并不完全适用于克隆代码，TFIDF的核心思想为：某一特征项权重的高低依据的是在文档中出现的频率，出现频率越高，

11、并且包含此项的文档数越少，表示其权重越高，关联程度更强，但这些仅仅是经验公式，并不能真实反映出每个特征项的重要程度。这种思想并没有考虑每一个特征项的整体比例，所以在确定每一个特征项权重时存在缺陷。另外，和形式语言不同，代码文档中的词在整个文档集中的出现比例并不能反映其重要程度，所以IDF的计算在软件代码文档中并不适用，因此在代码克隆领域中，须引入其他能表示克隆代码重要程度的度量值。基于向量空间模型的思想，利用TF概念以及代码中的文件名、函数名等特征项，来表征克隆代码的相似性。一方面，首先通过表示一个词出现在文档中的次数，统计词频建立词频向量，然后对其进行规范化，最终利用cosine定理得到两个

12、权重向量的相似度；另一方面，利用文件名以及函数名等特征项来匹配代码片段的相似性权重。2基于改进向量空间模型的克隆群映射方法2.1算法框架本文使用的是改进的向量空间模型克隆群映射方法，从检测结果中提取克隆群文档，再从克隆群文档中抽取词频向量进行相似度计算，并匹配特征项，从而实现对版本间克隆群的映射。克隆群映射的流程如图1所示。本文映射算法的思路为：首先对软件的前一版本和后一版本中的每一个克隆群计算词频，得到每个克隆群的词频字典，然后构建权重向量，得到克隆群相似度。同时提取克隆群中的特征项（文件名、函数名、起始行、结束行、代码行数），通过特征项匹配得到特征相似度，最终得到克隆群映射结果，实现了从高

13、维度的代码文档空间到低维度的向量空间的转换。克隆群映射算法如下所示。有序号的程序Shift+Alt+Y程序前输入：FClones检测结果。输出：克隆群映射结果。1）对后一版本Vn+1中的每一个克隆群CGn+1，i2）统计CGn+1，i中每个词的词频，存入字典Dn+1，i3）提取每个CGn+1，i的特征项，存入特征字典Tn+1，i4）对词频字典规范化5）对前一版本Vn中的每一个克隆群CGn， j6）统计CGn， j中每个词的词频，存入字典Dn， j7）提取每个CGn，i的特征项，存入特征字典Tn，i8）对词频字典规范化9）遍历比较Dn+1，i和Dn， j之间相似度，存储到数组cosin中10）遍

14、历匹配Tn+1，i和Tn， j，并存储到数组T中11）IF cosink=t & Tk=True12）THEN CGn+1，i映射到CGn， j13）即CGn+1，i CGn， j14）ELSE15）CGn+1，i NULL16）返回映射结果程序后2.2克隆群向量空间2.2.1克隆群文档预处理预处理是克隆群映射的基础工作。相比自然语言文本信息，形式语言中代码不仅包括与其功能相关的信息，也包括大量的程序语言信息。与编程相关的信息在其领域内大多是相对独立的，几乎不包含代码以及软件的功能信息。为保证克隆群映射更加准确，须将源代码中的编程相关信息进行过滤。本文使用检测结果是由本团队开发的检测工具Fcl

15、ones16检测得到，检测结果存储在可扩展标记语言（Extensible Markup Language， XML）文件中，存储方式如图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构建词频向量空间并规范化经过研究之后发现，假设版本中克隆群有i个词频：D=D1，D2，Di，每个目标都有相应的关键字。不同关键字之间的数量级差异可能很大，如果直接用词频计算余弦距离，就不能很好地平均反映出每个关键字的

16、特性，所以必须对词频进行规范化。词频规范化的方法如下：i=Di/（ni=0Di）（5）其中：Di是克隆群向量中词频的实际值；i为规范化后得到的权重值。获得克隆群目标权重向量：=1，2，i2.2.4计算向量空间相似度目前，克隆代码领域内判断相似程度的方法主要有基于文本和位置的映射方法。基于文本的相似度计算方法包括：最长公共子序列（Longest common subsequence）、杰卡德距离（Jaccard distance）、编辑距离（Levenshtein distance）等。基于位置的相似度计算方法是位置重叠率（Location overlapping rate）的计算，其原理就是将

17、克隆代码的起止行号表示为克隆粒度的相对行号，然后依据特定的公式计算其重叠率。本文使用的相似性计算方式是余弦距离。计算两个文本相似度时采用的相似度计算公式如下：CosSimilarity（i，j）=（ni， j=1（i*j）/ni=12inj=12j（6）其中：i*j指的是克隆群词频向量的内积；CosSimilarity（i*j）的取值范围是0，1。当克隆群中的克隆片段在演化过程中发生了变化，CosSimilarity的值小于等于1，本文启发式地设置一个阈值，把所有CosSimilarityt的克隆群对当作候选的具有映射关系的克隆群对。如果一个克隆群在相邻版本中有多个克隆群可能与其具有映射关系，则分别计算源代码的相似性，选取源代码相似性符合阈值条件的那些克隆群作为具有映射关系的候选克隆群。2.3克隆群特征项2.3.1选取克隆群特征项为了保证克隆群映射的准确度，须匹配克隆群中的函数名等多个特征项，本文选取了文件名、函数名、起始行、结束行以及代码行数5个特征项来衡量一个克隆群的属性信息。具体特征项如表3所示。2.3.2提取特征项确定克隆群特征项之后，需提取出所需的克隆群特征项，并放入特征项字典中。文件名的属性字典表示为：File=“文件名”：FileName，函数名属性字典表示为：Fun=“函数名i”：FunNamei，每一个克隆群可能包含多个函数，所以字典中包含多