（计算机应用技术专业论文）基于向量空间范围搜索的大型软件相似度检测.pdf

浙江大学硕士学位论文 摘要 摘要 不同软件系统中相近似的代码模块的出现，是理解和重构软件系统的一个重 要出发点。就软件工程的角度而言，相似代码模块的检测可以更好的检验系统； 可以方便对软件系统进行重构；可以在度量相似和差异的基础上协助版本管理； 进而还可以在产品线的层面上，给出量化的版本之间相似度的结果，从而有助于 更有效的项目管理。由此可见软件相似度的研究有其重要的现实意义。 本文关注于大型软件系统的相似检查。现有的软件相似检测的方法基于对软 件相似的不同定义，没有一个坚实的框架来支持大型软件系统的相似分析。本文 比较了当前的检测技术，针对大型软件系统相似检测需要，指出了基于度量空间 的解决方向。文章在分析软件特征的基础上挑选了适当的软件系统度量，并给出 了软件相似度及其量化结果的形式化定义。然后在向量空间搜索的理论框架下探 讨了近似搜索算法，得到了适合大型软件向量空间应用的合适算法。最后，本文 基于上述解决方案给出了一个大型软件系统相似检测器的设计实现，并在大的模 拟样本数据集上进行了实验。对于软件度量空间相似检测时涉及的重要参数，实 验分析指出了它们对相似检测结果以及效率的影响，为其它软件系统的度量相似 检测实践提供了有力的参考。自此形成了一个对大型软件系统进行相似检测的完 整框架。 关键词：大型软件，软件度量，相似检测 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t n l eo c c u l l r e n c e so fs i m i l a rc o d e si nd i f f e r e n ts o f t w a r es y s t e m sa r et h ef o u n d a t i o n o fu n d e r s t a n d i n g 柚dr e f a c t o r i n gt h eo r i 舀n a lp r o d u c t f r o mas o f t w a r ee n 舀n e e r i n g s p e r s p e c t i v e ，t h ed e t e c t i o no fs i m i l a rc o d e sc a nh e l pu st ot e s tt h es y s t e m s ，t of a c i i i t a t e t h eo r i 舀n a l s y s t e m sr e f a c t o r i n g ， t o p r o m o t ev e r s i o nm a i n t e n a n c e b a s e do nt h e m e 筋u f e dd i s c r e p a n c y ，a sw e l la st 0g a u g caq u a n t i t a t i v es i m i l a r i t yr e s u l tw h i c hw i l l h e i pu st om a n a g eap r o j e c tm o r ee f ! f i c i e n t ly i ti se a s yt os e et h a tt h er e s e a r c h0 f s o f t w a r es i m i l a r i t yd e t e c t i o ni so f 伊e a ti m p o n a n c ei nap r a c t i c a lw a y 1 1 l i sp a p e rf o c u s e so nt h es i m i l a r i t yd e t e c t i o no fl a r g es o f t w a r es y s t e m s t h e e x i s t i n g s o f t w a r e s i m i l a r i t y d e t e c t i o n t e c h n 0 i o g y e m b o d i e sd i f f e r e n td e f i n i t i o n a s s u m p t i o n ，a n dt h e r c sn of i 肺仃a m e w o r kt oa s s i s tt h ea n a l y s i so fl a r g es o f l w a r c s y s t e m s s i m i l a r i t yd e t e c t i o n t h i sp a p e r 舀v e sa n a l y s i st o t h ep r e s e n ts i m i l a r i t y d e t e c t i o nt e c h n o l o g j e s ，a n dp r o m o t e st h em e t r i cd e t e c t i o na p p r o a c h ，t a r g e t i n gv e r y l a r g es o f t w a r es y s t e m s a f t e rp i c k i n gs o m ep r o p e rs o f l w a r es y s t e mm e t r i c s ，af 0 珊a l a n dq u a n t i t a t i v ed e f j n i t i o no fs o 胁a r es i m i l a r i t yi sl a i do u t t h e nt h ee x i s i i n gm e t r i c s p a c er a n g es e a r c ha l g o r i t h m sa r eb r o w s e do nat h e o r e t i c a lb a s i sa n daf i t t e do n e c o m e so u t ap r a c t i c a lc o d es i m j l a r i t yd e t e c t o r sd e s i g ni sg i v e n ，a n de x p e r i m e n t sa r e c o n d u c t e do ns o m el a 唱es i m u l a t e ds a m p i ed a t es e t s f o rt h o s ei m p o r t a n tp a r a m e t e r si n s o f t w a r em e t r i cs p a c es i m i l a r i t yd e t e c t i o n ，a n a l y s i sf r o me x p e r i m e n t sr e s u l tp o i n t so u t t h e i re f ! f e c t0 nt h ed e t e c t i o nr e s u l ta n do p e r a t i n ge 币c i e n c y ，w h i c hw i l lg i v eas t r o n g r e f e r e n c ep o i n tf o rs o f t w a r es i m i l a r i t yd e t e c t i o n h e r e i nt h i sp a p e rf o 册sac o m p l e t e f r a m e w o r kf o r l a 唱es o 讯v a r es y s t e m ss i m i l a r i t yd e t e c t i o n k e y w o r d s ：i 捌- g es o f t 、a r e ，s o r w a r em e t r i c s ，s i m i l a r i t yd e t e c t i o n 浙江大学硕士学位论文 表目录 图目录 图1 1 基于注释、空白符和段落结构差异的相似。7 图1 2 基于变量名差异的相似7 图1 3 基于表达式修改差异的相似7 图1 4 功能相似8 图1 5 伪相似一访问方法o 。8 图1 6 伪相似一连续的方法调用。9 图1 7 伪相似一连续的i f 和i f - e l s e 表达式1 0 图1 。8 伪相似一连续的c 蹴表达式：1 l 图1 9 伪相似一连续的变量申明1 1 图1 1 0 伪相似一连续的赋值语句一1 2 图1 1 l 伪相似一连续的c a t c h 语句1 2 图1 1 2 伪相似一连续的ca t i c h 语句1 3 图3 1 收缩性的扩展距离定义2 7 图4 1 捌唱e = o 3 0 ，相似结果( 纵轴) 与度量数目( 横轴) 关系4 0 图4 2m n g e = o 3 2 ，相似结果( 纵轴) 与度量数目( 横轴) 关系4 0 图4 3 瑚g e = 0 3 4 ，相似结果( 纵轴) 与度量数目( 横轴) 关系：4 1 图4 4 瑚g e = o 3 6 ，相似结果( 纵轴) 与度量数目( 横轴) 关系4 1 图4 5 眦g c = o 3 8 ，相似结果( 纵轴) 与度量数目( 横轴) 关系4 2 图4 6 m g e = o 4 0 ，相似结果( 纵轴) 与度量数目( 横轴) 关系4 2 图4 7m e t r i c s = 5 相似结果大小( 纵轴) 和搜索范围( 横轴) 关系4 4 图4 8m e t r i c s = 1 0 相似结果大小( 纵轴) 和搜索范围( 横轴) 关系4 4 图4 9 m e t r i c s = 1 5 相似结果大小( 纵轴) 和搜索范围( 横轴) 关系4 4 图4 1 0p u 玛ei i o ( 纵轴) 和轴点( 横轴) 个数关系4 6 图4 1 1 优化程度z ( 纵轴) 与轴点数目( 横轴) 关系4 7 浙江大学硕士学位论文 表目录 表目录 表2 1 软件相似检测技术比较1 7 i i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确的说明并表示谢意。 学位论文作者魏弛签字隰知多年如朋 学位论文版权使用授权书 本学位论文作者完全了解盘姿盘鲎有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权逝鎏盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者躲磁 签字日期：孑。多年么月f 。日 导师签名： e l 特a 规j 少髫年黾l 。黾 浙江大学硕士学位论文 第1 章绪论 第1 章绪论 1 1 课题背景 相似代码的存在是大型软件系统，特别是遗产系统( l e g a c ys y s t e m ) 中的 常见现象。相似代码可能是通过直接的拷贝和粘贴实现，很多时候也会通过在原 有代码的基础上保留主要功能，做出适当修改的形式出现。相似代码的存在源于 软件功能的必然重复性，比如下一个版本的软件需要实现一些和上一个版本相似 的功能，但又暂时没有重构的必要，这时借用原来的代码是一个比较现实的快速 达到开发目的方法。在这个层面的意义上，需要评估版本之间相似度的大小，由 此作为衡量版本变动大小的依据，以辅助项目的进度成本管理和资源分配。 在另一方面，相似代码又是造成软件维护困难和复杂的重要原因。相似代码 弱化了软件丌发人员对软件系统的控制，会将同样的程序问题通过相似代码的存 在散布到系统的不同地方，而这种分散性在大型软件系统的维护中是一个比较严 重的问题。在遗产系统中这样的问题更严重，因为遗产系统往往经历了不同丌发 人员的在不同时期长久的开发维护，往往存在着大量的重复代码，包括重复的语 句块，重复的函数，重复的类，甚至是重复的子系统，很难有某个开发人员能够 对遗产系统中所有的重复代码都了如指掌。随着软件系统的规模变得越来越大， 结构也越来越复杂，软件的寿命也越来越长，这些重复代码的量也越来越大，对 遗产系统的维护和进化的任务也变得越来越艰巨。有研究表明，对现存软件的维 护可能占据开发组织花费的所有努力的6 0 以上，而且随着更多的软件被生产出 来，这个百分比还在继续上升1 1 1 。软件维护已经成为现代软件业面临的重要课题 和难点之一。 对克隆代码自动检测技术的研究可以追溯到上世纪9 0 年代，如1 9 9 2 年的 d u p ，随着软件同益强调代码重用，研究者们提出了各种不同的自动检测克隆代 码的思路，并进一步研究了如何在自动检测克隆代码的基础上进行代码重构、软 件再工程、软件维护支持、方面挖掘等问题。在国外众多研究者中，日本大阪大 浙江大学硕士学位论文第1 章绪论 学计算机系软件工程实验室在本领域进行了深人研究，他们的成果包括：克隆代 码自动检测工具c c f i n d e 、克隆代码重构支持工具a r i e s 和基于克隆检测的软件 维护支持环境g e m i n i 等。克隆代码检测技术成为最近几年来国际软件维护领域 的重要关注点，2 0 0 2 年和2 0 0 3 年连续举办了两届国际软件克隆检测w o r k s h o p ， 仿照信息检索领域有名的年度t r e c 竞赛，组织者预先准备了测试集以及答案， 以此来客观评价各类克隆代码检测工具的性能。此外，几种可以自动检测克隆代 码的商用工具如s i m i a n ，s i m s c a n 和c 1 0 n ed o c t o 等也在软件开发组织中等到了 广泛应用。 1 2 研究内容和目标 现有的软件相似检测基于不同的假设和相似度定义。本文感兴趣的是大型软 件系统的相似检测和量化表达，这里的相似性基于类文件上的功能相似，给出的 量化相似结果是为了辅助理解版本差别和协助项目管理。大型软件系统往往有几 十上百万行的代码量，大量隐含其中的相似代码给软件维护带来了巨大挑战，也 给系统重构指出了方向。对已有的软件相似检测方法在一个统一的框架下进行衡 量，分析它们的相似定义和应用环境，找到能够扩展到巨大代码量上的检测方法 因此就显得特别重要。本文首先分析了软件相似的检测手段。在确定度量空间相 似检测的方向后，分析了进行软件系统表达的度量，给出了软件相似的形式化定 义，分析了空问相似搜索的算法。最后文章在实验的基础上分析了在度量空间下 软件相似检测需要考虑的参数，以及它们对相似检测结果和效率的影响。 1 3 论文组织 本文共分5 章： 第一章：绪论。交代本文的研究背景。 第二章：软件相似度及其检测方法比较。基于软件相似定义分类、软件相似 检测流程和衡量标准研究分析了当前的检测方法，并指出了度量空间检测的方 向。 2 浙江大学硕士学位论文第1 章绪论 第三章：软件系统的度量空问表达及搜索算法优化。在对软件系统特征进行 分析的基础上，挑选了适合对软件系统进行度量空间表达的度量。给出了软件度 量空间相似的形式化定义和一个量化值来表示软件系统的相似度，并基于度量空 间相似搜索的理论框架，研究分析了目前的搜索算法，得到了适合软件相似检测 的特定算法，并分析比较了其他软件度量相似检测器的特点。 第四章：设计实现了一个基于上述构架的软件相似检测器。通过一系列的实 验，分析了在度量空间上进行软件相似检测时不同参数对检测结果和效率的影 响。 第五章：总结与展望。对本文的研究结果作出自我评价，并指出将来工作的 方向。 3 浙江大学硕士学位论文第2 章软件相似度及其检测方法综述 第2 章软件相似度及其检测方法综述 我们可以看到大量的软件相似的现象，或者说，软件克隆的现象一大学程序 设计课期末作业提交时的学生作业抄袭情况就是其中之一。学生将以前的程序改 变一个变量名，或者文件名，重组一下代码段的位置，或者拆分、合并原来的几 个文件，然后就当做自己的作业提交。为了保证课堂教学的质量，我们当然希望 学生最后的程序作业都是自己独立完成的。如果有自动的检测工具告诉助教那些 可能的抄袭代码，再辅以人工检验，那期末程序设计作业批改就会更加有效。 我们也能在正常的软件开发维护过程中发现软件相似性的概念。”拷贝、粘贴、 修改”的开发习惯，对遗留系统保护性地修改及扩充、开发语言缺乏抽象机制及不 良的系统架构设计等诸多原因，导致克隆代码在较大规模的软件系统中十分常 见。根据文献【2 l 统计，在软件系统中，一般有5 一1 0 的代码是克隆代码。这种 复用机制常常是非j 下式的、不可控的，一般也不会有文档记录这种复用，因而会 带来一系列的软件维护问题。克隆代码的主要危害体现在：( 1 ) 软件错误难以修 改，因为同样的错误会出现在多处克隆代码中，更为严重的是，负责维护的程序 员可能并不知道这些克隆代码的存在，这可能会导致非常致命的软件问题；( 2 ) 需求变更、功能扩充变得难以实现，为了增加一项新功能，不得不修改多处克隆 代码，还得小心地保证修改的一致性；( 3 ) 代码数量不必要地膨胀，加重了维护 人员阅读、理解代码的负担，增大了维护代价。软件相似性的检测将在这里协助 我们b u g 检测和程序维护。 另外，同一个软件系统不同版本之间也存在着显然的相似性。通过文件结构 重组和软件重构，相似的部分可能会存在于软件系统不不同位置。不同版本软件 的合并产生的新版本，也会把相似的软件通过这种演化的机制带入新的系统中。 理清各个版本和软件系统之间的关系对我们理解整个开发的构架和进展历史非 常重要。同时，如果可以把版本之间的相似度进行量化表达，那项目经理就可以 更好的评估产品开发的资源分配效率。这些都有助于大型软件系统的项目管理。 那么，“软件相似 具体的定义和分类是什么? 现有的软件检测技术有着怎样 4 浙江丈学硕士学位论文第2 章软件相似度及j 检测方法综述 的特点? 哪些才能适用于大型软件系统的相似检测? 本节将对这些问题予以回 答。 2 1 软件相似度以及定义 在比较各种软件相似方法的时候我们可以看出，实际上，尽管在软件系统的 开发维护中有许多的“相似”问题，但目前还没有一个对软件“相似”的统一定 义，软件相似从一开始就有其定义的模糊性。比如，对应相似度的最小相似量的 问题就是个开放问题，也就是说，到底多少个单位的元素匹配成功，我们才把两 段代码判断为相似? 有的研究【1 2 ，1 3 ，1 4 1 表明对于以令牌为基础的相似度检测技 术，3 0 个令牌是一个比较合适的最小相似量，即小于3 0 个令牌大小的匹配序列 都不算作”相似”。有人推荐以代码行作为评判相似最小量的依据，但究竟多少行 的匹配算是相似”，却仍是有不同标准。b e l i o nf 6 ，1 5 】的工具检测实验定义为6 行， b a k e r l l 6 】把1 5 行为注释代码行作为最小相似量，而j o h n s o n 【17 】的标准却是5 0 行。 有的研究把语法树或者程序依赖图的节点个数作为衡量相似量的参考标准【1 8 ，1 9 】， 而有些只对函数相似度感兴趣的研究者就只把相似量定义在相应函数体的大小 卜【l o ，2 0 】 lo 人为主观判断也同样给我们的相似度定义引入了模糊性，因为如果基于专家 评判来对不同的检测工具有效性做出比较，那专家的意见就成了模糊性的唯一度 量。但在【2 1 】的研究中，三个专家在超过6 0 的自动检测出的相似代码段上，对代 码是否真的相似( 或克隆) 存在者不同的意见。 与此同时，软件的相似性定义的模糊性还存在于编程语言的语义层面。例如 j a v a 的c l o n e ( ) 方法，作为重用机制的实现，我们可以认为c l o n e 出的对象和原 来的对象间的应该不会有文本的相似关系；但由于c l o n e 出的对象和原来的对象 会有功能上的覆盖性，因而我们又可以把两者在语义的层面上当作”相似”。 从上面的介绍我们可以看出，软件相似度或者软件克隆在不同的场合有着不 同的应用环境，从而也对应了不同的具体定义。事实上，目前还没有一个对软件 相似或者克隆的统一定义。现存的定义依赖于具体的使用环境，而不同的检测算 5 浙江大学硕士学位论文 第2 章软件相似度及其检测方法综述 法因为应用环境和相似定义的不同，也有着各自不同的未经统一的输出。软件相 似度定义的这种模糊性我们可以从以往的文献中得之一览。b a x t e r l 3 j 将克隆相似定 义为基于某些阀值的树的相似；l ( a m i y a 【4 】将相似定义为源程序中”相同”或相互” 近似”的部分。此处的”相同”指完全的照抄，但却没有对”相似”有一个j 下式定义。 在b u r d 【5 l 对不同的软件克隆检测工具的评价文章中，他们把相似定义为同样的代 码段不经过或者经过很少的修改后，出现于不同的软件系统。而这里的”很少”其 实并没有确切的定义。而在文献【6 ，7 ，8 ，9 j 中，作者尝试把不同的相似度检测结果合并 到一起从而克服相似度的定义问题。 2 2 软件相似的表现 为了解决”相似”定义的模糊性，软件相似或者说克隆的分类学应运而生。例 如，m a v r a n d l l 0 】给出了八种不同克隆的分类量表，其中的一些分类有着非常简单 明确的定义。比如，”d i s t i n c t n a m e ”这一类的克隆中，只有标识符的名字可以不一 样。当然，他们的分类也还员不足以对相似给出充分的定义。例如他们 将”s i m i l a r e x p r e s s i o n ”定义为有不同的却仍”相似”的表达式，可见在他们的分类中 仍然存在相似定义的模糊性。b a l a z i n s k a 【1 1 】给出了另外的1 8 种克隆分类，他的依 据是语法元素被修改的种类和被重复方法的数量。尽管他们的大多数分类都对应 于代码段的单独改变，他们也同时给出了”o n el o n gd i 骶r e n c e ”来指代程序中表达 式或者代码段一个单元的令牌序列的差别，t w ol 伽gd i f f e r e n c e s ”来指代两个单元 的令牌序列的差别，”s e v e r a l l o n gd i f ! f e r e n c e s ”来指代多个单元的令牌序列的差别。 然而这些定义中或多或少存在不同程度的相似定义模糊性。 基本上，我们可以把软件的相似归为两类：一是文本层面的；一是功能层面 的。文本层面的可以是在源程序的空白符、注释以及段落结构上的，例如图1 1 所示的两段代码就只是在注释的段落结构上有所差异。 6 浙江大学硕上学位论文第2 章软件相似度及其检测方法综述 图1 1 基于注释、空白符和段落结构差异的相似 也可以是保留了关键字和程序结构，但变量名不同，例如图1 2 。 图1 2 基于变量名差异的相似 在更进一步的层面上，文本的相似也可以包括一些表达式的改变、添加和删 除，如图1 3 的两段代码就是基于表达式少量修改的相似。 图1 3 基于表达式修改差异的相似 7 浙江大学硕士学位论文第2 章软件相似度及其检测方法综述 而功能层面的软件相似，则反应了程序在逻辑表现上的相似性，这样的检测 是建立在程序功能的属性和输入输出的判断上。例如图1 4 中计算阶乘的两段代 码，其中一个利用递归实现。尽管两段代码在语法和结构上都大不相同，但从语 义的角度出发，它们实现了同样的功能，因而也就可以算作”相似”的。 图1 4 功能相似 另外，软件相似中有一些尽管符合上面的表现和分类，却由于语言的语义或 者相似检测的具体应用，是我们并不感兴趣的的相似情况，或者说是伪相似。例 如，连续的方法申明，比如图1 5 的访问方法： f r a g m e n t1 ： p u b l i cs t a t i cb 0 0 1 e a ni s a b s t r a c t ( i n ta c c e s s _ n a g s ) r e t u m ( a c c e s s f l a g s & a c c a b s t r a ( 了r ) ! = 0 ； f r a g m e n t 2 ： p u b l i cs t a t i cb o o l e a ni s p u b l i “i n ta c c e s s n a g s ) r e t u m ( a c c e s s f l a g s & a c c - p u b u c ) ! = 0 ； ) f r a g m e n t 3 ： p u b l i cs t a t i cb o o l e a ni s s t a t i c ( i n ta c c e s s - n a g s ) r e t u m ( a c c e s s j l a 萨& a c c s 豇玎i c ) ! = 0 ；) f r a g m e n t4 ： p u b l i cs t a t i cb o o l e a ni s n a t i v e ( i n ta c c e s s j l a g s ) r e t u m ( a c c e s s _ n a g s & a c c - _ n a t i v e ) ! = 0 ；) 图1 5 伪相似一访问方法 8 浙江大学硕士学位论文第2 章软件相似度及其检测方法综述 连续的方法调用被当作相似。比如图1 6 的情况。这种相似其实并无助与我 们理解软件的结构相似性和重构可能，因而是伪相似。 图1 6 伪相似一连续的方法调用 连续的i f 和i f e l s e 表达式。这些变量判断的表达式对程序并没有很大的影 响，在考虑软件维护性而关注软件相似度时，这些判断语句的相似也并非我们感 兴趣的，如图1 7 。 另外，连续的c a s e 语句也被认为是假相似。这个和上面的情况类似，连续的 c a s e 语句并非我们感兴趣的结构性相似，但是却在归一化的过程中容易被判断为 相似，如图1 8 。 9 浙江大学硕士学位论文 第2 章软件相似度及其检测方法综述 图1 7 伪相似一连续的i f 和i f e l s e 表达式 l o 浙江人学硕上学位论文第2 章软件相似度及其检测方法综述 图1 8 伪相似一连续的c a 表达式 连续的变量申明。这种相似性是显然的伪相似，如图1 9 。 图1 9 伪相似一连续的变量中明 1 1 浙江大学硕士学位论文第2 章软件相似度及】检测方法综述 连续的赋值语句，如图1 1 0 。 图1 1 0 伪相似一连续的赋值语句 连续的c a t c h 语句。这种情况的出现只是出于j a v a 的语言特性，因而也不应 该被当作相似的代码，如图1 1 1 图1 1 1 伪相似一连续的c a t c h 语句 连续的简单w h i l e 语句。如果连续的结构性w h i l e 语句逻辑简单，那这样的相 似也并不是我们感兴趣的如图1 1 2 。 1 2 浙江大学硕士学位论文 第2 章软件相似度及其检测方法综述 图1 1 2 伪相似一连续的c a t c h 语句 如果逻辑复杂，那又另当别论。 这些伪相似代码的存在除了会影响最后相似检测返回结果的有效性，还会对 检测的中间过程引入”噪音”。因而定义并识别伪相似代码在相似检测的构建中有 着重要的意义。 2 3 软件相似检测流程 软件的相似度必须基于软件系统的源程序文件的相互匹配程度，寻找软件系 统之间的匹配代码段是得到定义的软件相似度的前提。由于事先不知道某段程序 段会被匹配多少次，本质上而言，我们需要将每一个可能的程序段和所有的其他 程序段做一比较，而这从计算效率的角度来考虑是及其耗费资源，也是不具备良 好可扩展性的。因此，在真正的进行匹配计算前我们需要采用适当的方法来降低 匹配域的大小。另外，即便找到了潜在的匹配程序段，我们也需要后期的处理方 法和工具来找到真正的匹配段。下面简要介绍一下软件检测流程的各个步骤： 源程序预处理 在任何的相似检测运用之前，我们都需要先对源程序进行预处理，以分离出 需要检测的代码，并确定匹配的域。首先，对于匹配阶段不相关的代码文本( 如 进行语义比较时的程序中的空白符、注释等) ，以及可能产生伪相似性的代码段 ( 如很多初始化语句) 需要从源程序移除。然后要在定义好的粒度上( 关键词、 1 3 浙江大学硕士学位论文 第2 章软件相似度及其检测方法综述 表达式、连续的行、程序块、函数、类或者是文件，包等) 划分出不相交的源代 码单元，单元之间没有有序关系，是我们进行匹配分析的基本单元。 软件系统转换表达 为了提取匹配属性并方便比较，我们需要将匹配单元从源代码转换为其他合 适的表达方式。这种转换可以是简单的移除不相关的代码段，像预处理的作用一 样，或者是复杂的p d g 图的生成。一些相关的程序表达处理模型包括： 源程序文本规则化，统一文本格式，移除注释和空白符号等，基于文本的相 似性比较多需要这样的处理。 令牌化，在以令牌为基础的相似检测方法中，每一行程序将会依据程序语言 的l e x i c a l 规则转化为相应的令牌( t o k e n ) ，由此形成一个可比较的令牌序列。 语法解析，基于解析树的检测方法将对整个源代码进行解析从而生成解析树 或者抽象语法树( a b s t r a c ts v n t a xt r e e ) ，每个匹配单元以子树的形式表达，树的 比较算法将用于相似性的检测。 生成程序依赖图，匹配程序单元在由整个源程序生成的程序依赖图( p r o 掣a m d e p e n d e n c eg r a p h s ) 中以子图的形式表达，同构检测的算法将用于匹配相似的程 序单元。 标识符归一化，将程序中的不同标识符以同样的令牌表达从而实现标识符的 归一化。 计算测度值，以测度( m e t r i c s ) 为基础的检测算法需要在此时从原始的代码 或者转变后的代码( 如语法抽象树、程序依赖图等) 中计算相应的测度值。 匹配检测 由前述步骤得到的源程序表达此时被用于不同的相应相似度比较算法。相邻 的源程序匹配单元可以聚集为一个更大的相似单元，如果是固定粒度的相似性检 查，则聚集过程到规定的粒度为止；如果是自由粒度的相似性检查，则匹配单元 聚集的过程直至最大的匹配单元集找到为止。匹配检测的结果输出为对应的匹配 程序单元对，其中包含了匹配单元在源程序中的位置信息。 格式化和后期处理 1 4 浙江大学硕上学位论文第2 章软件相似度及其检测方法综述 检测到的转换后的代码中的匹配程序单元在这个阶段被还原为源程序中的代 码和位置信息。每个匹配的程序单元对可以用程序中的行数和一个多元组来表 达： ( 文件名，起始行，结束行) ，( 文件名，起始行，结束行) ) 。再之后可以对 之前的匹配单元进行可视化表达，再结合对应的源程序中的代码，运用人工分析 将伪相似的匹配单元去处。 检测结果聚集 为了减少数据量进行后期的分析，我们可以在得到的匹配结果上做聚类或者 分类处理。 2 4 软件系统相似检测算法比较 由前所述，软件相似度的检测主要由代码变换和比较两个阶段组成。在代码 变换阶段，源代码的文本被转化为更适合有效比较的内部表达形式。然后在比较 阶段再根据代码的表达方式选择适当的相似比较算法。因而我们在研究相似检测 算法的时候也以代码的表达方式为基准来进行分类。 基于文本的检测 基于文本的检测将源程序看成字符串序列，相似程序单元通过共同字符串( 定 义长度以上) 来进行识别。由于是基于文本，这种检测方法几乎不需要代码变换， 而它也对程序结构层面上的相似无法检测。 这种基于文本的行与行比较的检测技术有以下一些问题： 断行符会将本来相似的代码段分割，从而在行的粒度上难以匹配 不同的编码风格，括号的不同使用习惯等，会使本来相似的代码在文本的层 面上难以被检测。 令牌检测算法 基于令牌的相似检测算法将源程序进行词法语法分析后，转变为相应的令牌 ( t o k e n ) 序列，再通过在序列上寻找相似的子列来匹配程序单元。相对基于文本 的相似检测而言，基于令牌的检测技术对程序格式和空格等变化的情况有更好的 适应健壮性。 1 5 浙江大学硕士学位论文 第2 章软件相似度及j e 检测方法综述 语法树检测算法 语法数检测算法将源程序转换为解析树或者抽象语法树，再用树的匹配算法 寻找相似的子树。 结构度量检测算法 结构度量检测算法基于软件系统的度量空间表达。一个代码单元可以用它本 身的很多性质特点来表示，这些性质特点都可以说是软件的某个度量。结构度量 检测算法先将软件系统的比较单元用一些度量值来表示，然后通过定义良好的度 量空间的距离函数，输入一定的距离阀值( t h r e s h o l d ) ，并通过度量空间搜索算法 来有效的找到离某个代码片断“最近”的代码段。 程序依赖图检测算法 基于程序依赖图( p r o g r 拥d e p e n d e n c yg r a p h - p d g ) 的相似检测通过考虑源 程序的语义从而在一个更抽象的层面上比较软件系统之间的相似度。p d g 由于包 含了控制流和数据流的信息从而更好的携带了源程序的语义内容。一旦源程序的 p d g 被抽象出来，基于同构子图的搜索算法就会被用于寻找相似的代码单元。 由于存在很多不同的软件相似检测算法和工具，为了针对特定的运用环境和 目的使用合适的算法和工具，我们有必要对这些它们加以比较。这些比较的点同 时也可以看作是软件相似比较算法面临的不同的挑战。它们分别是可移植性，准 确性，以及可扩展性。 可移植性是指检测算法应该通过简单的配置而适应尽可能多的语言和语言下 的不同分支。由于编程语言语义之间的差异，理想的软件相似检测算法需要针对 不同的语言语义而做适当的调整并能够整合结果，这种适应性在比较由多种语言 生成的软件系统时显得尤为重要。 准确性有两层含意。首先是完整性，算法能尽可能将所有相似的代码单元都 检测出来，减少遗漏。很多相似的代码并非在文本的层面上相似，健壮的检测算 法应该可以检测到程序结构层面上的相似。然后是精确性，算法要尽可能的减少 伪相似代码单元的返回。检测算法的完整度和精确度应该能够适应和解决不同情 1 6 浙江大学硕士学位论文 第2 章软件相似度及其检测方法综述 况和层面的程序相似问题。 可扩展性是指检测算法要能够适应大规模的软件系统，因为往往是这样的系 统需要我们进行自动程序相似检测。算法应该在有效利用内存的基础上能够处理 大型复杂的软件系统。 表2 1 给出了在这三个方面对不同的软件相似检测算法的比较结果。 表2 1 软件相似检测技术比较 检测方法 基于字符串 基于令牌 可移植性 高，最多只需 要一个1 e x e r 中，需要1 e x e r 将源程序转化 基于解析树 霪菥需要词法 基于程序依赖图蕞蒜雷蚕墓主 基于度量 依赖于度量的 选取 准确性 1 0 0 ，冈为 基于字符完全 匹配 低，归一化和 令牌转换会带 来很多f a l s e p o s i t i v e 的相 似 高，词法解析 器返同了结构 信息 高，依赖图携 带了结构和语 义信息 高，度量携带 了结构信息 完整性 低，只能找到 完全匹配的相 似段 高，大多数相 似都能检测刽 低，不能检测 所有类型的相 似 中，有些类型 的相似不能枪 测 中，有些类型 的相似不能检 测 可扩展性 依赖于比较算 法 高，基于前缀 树算法 依赖于比较算 法 低，图的搜索 配对开销比较 大 高，度量值的 比较相对树和 图更快 可以看出，基于文本的相似检测算法的可移植性最好，在处理不同的编程语 言时，最多只需要一个词法分析器( 1 e x e r ) 。由于是基于文本的完全对应，它的 精确性也相当好。但是完整性却不好，很多结构相似的代码都不能被检测出来。 其可扩展性依赖于具体使用的算法和优化的文本处理方法。 基于令牌的方法的移植性稍微逊色，因为它至少需要词法分析器来对不同的 语言生成相应的令牌序列。尽管由于对文本的归一处理( n o 加a l i z e ) 会返回很多 伪相似代码使其精确性不够好，但它的完整性确也由此得到很大的提高。而使用 前缀树的算法则可以使其运用到大型软件系统的令牌序列，因而可以说有很好的 扩展性能。 解析树的方法在移植性、完整性和可扩展性方面都乏善可陈，却有着很好的 1 7 浙江大学硕士学位论文第2 章软件相似度及其检测方法综述 精确性。由于解析树反应了程序的结构特征，这种方法很少会返回伪相似的代码。 同样，基于程序依赖图的方法也由于携带了程序结构以及控制流和数据流的信息 而使得检测结果有很好的精确性。当然，其语言依赖的特点以及p d g 匹配算法 的耗时使其移植性和扩展性都不好。 基于度量空间的方法在完整性和精确性方面都有很好的表现，尽管因为要通 过生成解析树和程序依赖图的方式来获得程序度量空间值而使其移植性不好，但 就软件相似检测质量而言，这种方法有其独特的优势。而在大型软件系统上的可 扩展性正是本文试图要解决的问题，将在后面的章节中详述。 2 5 本章小节 本章在列举出常见软件相似的基础上，总结了软件相似的各种表现形式以及 分类，给出了伪相似的说明，进而分析了软件相似定义本身固有的模糊性，指出 了在定义软件相似时应该要注意确定的地方。 然后本文总结出了一个通用的软件相似检测流程，并基于软件系统的不同中 间表现形式，对现有的各种软件相似检测技术作了简介和比较。通过比较发现， 就本文的大型软件系统功能相似比较的出发点而言，基于软件向量空间表达的相 似检测技术在准确性、完整性和可扩展性上都满足要求。下一节将要解决的是软 件度量的挑选，度量空间相似的形式化表达，以及相关空间近似搜索算法的探讨。 1 8 浙江大学硕士学位论文 第3 章基于软件系统度量窄问的搜索算法 第3 章基于软件系统度量空间的搜索算法 软件系统的度量属性从丌始被提出的时候就不断得到扩充和添加，现在当人 们需要对一个软件进行度量时，面临的问题往往不是度量的缺乏，而是怎样从各 种各样的度量中挑选出适合具体应用的度量来。 我们至今也还没有给出一个软件相似的确切定义。在软件系统度量表达的基 础上，一个形式化的软件相似性定义不仅界定了相似检测的范围，也对搜索算法 的表达、分析和优化非常有好处。进而，在给出一个软件度量空间上的相似的形 式化定义后，又应该采用怎样的算法才能在平衡时间和空间开销的基础上得到高 质量的软件相似的检测结果? 本节将对以上的问题进行研究。 3 1 软件系统的度量 软件度量的概念最先起于软件工程的质量管理的领域。6 0 年代术期的大型软 件所面临的危机反映了软件开发中管理的重要性。而对于管理层人员来说，没有 对软件过程的可见度就无法管理；而没有对见到的事物有适当的度量或适当的准 则去判断、评估和决策，也无法进行优秀的管理。软件工程的方法论主要在提供 可见度方面下功夫，这就需要使用度量。在不同层面上的对软件系统的不同度量提 供了对程序的相应表征，这些表征的度量值都可以用来对不同的软件进行比较。 实际上，度量的目的就是为了比较；因为假使没有比较的话，任何度量上面计算 出的数值都毫无意义。早期的软件度量是在确立所关心的软件属性的基础上，通 过度量的准则把属性的经验关系系统映射到形式关系系统上，再去评估这个度量 准则来确定度量系统。随着软件度量理论发展更加严密，度量评估被纳入形式化 范畴。度量专家w e y u k e r 【2 4 】提出一组形式化评估软件度量性质的定理。定理要求 所有程序的度量值不会都相同，需要度量准则有足够的精度，认为功能相同的两 个程序，由于实现细节不同，其度量值不一定相同，并对度量值的单调性，以及 程序变量名和程序结构顺序修改对度量值的影响做了形式化说明。定理并提供了 用于评估度量的语言，是度量评估的良好出发点。下面先介绍软件系统已有的各 1 9 浙江大学硕士学位论文第3 章基于软件系统度量空间的搜索算法 种经典度量，然后从易得性和表达性出发，挑选出本文使用的软件系统度量。 软件的各种度量从软件质量保证被关注的时候开始就一直被提出，直到现在 也是。f e n t o n 【2 5 1 、s h e p p e r d l 2 6 】和其他一些人都有专门的著作阐述各种各样的软件 度量。这些度量中间很多可以用于各种不同的语言，另有一些是针对特定的语言 集合而提出的，比如有关面向对象语言的一些继承性的度量，就无法运用到结构 性的语言中去( 如c ) 。而反过来，因为类的方法很大程度上可以看作过去的函数， 所以绝大多数针对过程语言的度量也就可以直接用于面向对象的语言。实际上， 问题并不是这样的度量太少；恰恰相反，这样的度量太多，构建软件系统的度量 空间表达需要的是挑选出合适的度量，以满足当前任务的需要。 针对各种各样的度量，为了解决挑选适当度量以满足特定任务的需要，人们 于是试图对度量进行分类。a b r e u 【2 8 】提出了针对产品和过程的度量分类法， 1 = a p r o o t 。这种分类法基于两个向量的乘积，它们是( 设计，大小，复杂度， 重用性，有效性，质量) 以及( 方法，类，系统) 。由此产生的1 8 种类别用来对 不同