（计算机软件与理论专业论文）java代码相似性判定方法的研究.pdf

摘要 摘要 成功的大规模系统被称为遗留系统。这些系统具有巨大的商业价值。但是因 为它们的体积庞大，并且缺乏文档信息，所以难于维护。其中相似性代码是困扰 工程师们的一大问题。在一个大型的软件项目中，大约有1 0 至3 0 的代码是 相似性代码。由于相似性代码的存在，导致了软件维护时7 0 的开销。 相似性代码是指相同的或者近似相同的源代码片断。在软件维护的过程中， 相似性代码的出现会造成多种问题。这篇论文对相似性代码产生的原因及其造成 的安全隐患进行了阐述。 由于使用目的不同，不同工具对相似性代码的种类进行了不同的划分。在总 结了现有的相似性代码分类与检测方法之后，这篇论文将相似性代码划分为五类： 简单的相似性代码片断、重命名的相似性代码片断、不邻接的相似性代码片断、 乱序的相似性代码片断和纠缠的相似性代码片断。这篇论文将相似性代码的检测 方法划分为四类：基于串的分析方法、基于度量的分析方法、基于抽象语法树的 分析方法和基于程序依赖图的分析方法。一个相似性代码集合中的相似性代码片 断可能具有。类或者多类相似性问题。不同种类的相似性代码可以使用不同的方 法进行判断。 这篇论文详细阐述了基于串的代码相似性判定方法、基于软件度量的代码相 似性判定方法和基于程序依赖图的代码相似性判定方法在实现过程中所需的理 论及算法知识。这些内容主要包括：k a r p r a b i n 算法、基于k a r p r a b i n 的g s t 算法、软件度量理论、程序依赖图理论及相关算法。 此外，针对j a v a 语言，这篇论文介绍了基于串的代码相似性判定工具、基 于软件度量的代码相似性判定工具和基于程序依赖图的代码相似性判定工具的 设计方案，并详细阐述了工具的实现方法。 关键词相似性代码；j a v a 语言；串匹配；软件度量；程序依赖图 a b s t r a c t a b s t r a c t ，n l es u c c e s s f u ll a r g e s c a l es y s t e m sa r ec a l l e da sl e g a c ys y s t e m s t h e s es y s t e m s h a v et r e m e n d o u sb u s i n e s sv a l u e b u tc a u s eo ft h eg i g a n t i cv o l u m e sa n dl a c k i n go f d o c u m e n t s ，t h es y s t e m sa r en o tm a i n t a i n a b l e o n eo ft h ep r o b l e m sc o n f u s e dt h e s o f t w a r ee n g i n e e r si st h ec o d ec l o n e al a r g e s c a l es y s t e mm a yc o n t a i nm o r et h a n10 c o d e sw h i c ha r es i m i l a r n ec o d ec l o n et a k em o r et h a n7 0 c o s td u r i n gt h es o f t w a r e m a i n t e n a n c e 1 1 1 ec o d ec l o n e sa r et h es a m eo rt h es i m i l a rc o d ef r a g m e n t s d u r i n gt h e m a i n t a i n i n go fs o f t w a r es y s t e m s ，t h ec o d ec l o n e sm a yb r i n gm a n yp r o b l e m s t h e d i s s e r t a t i o ne x p a t i a t e so nt h er e a s o n sf o rp r o d u c i n gc o d ec l o n e sa n dh i d d e nt r o u b l eo f t h e m a st h eu s a g ep u r p o s e sa r ed i v e r s e ，d i f f e r e n tt o o l su s ed i f f e r e n ts t a n d a r d st o c l a s s i f yt h ec o d ec l o n e s a t l e rs u m m a r i z i n gt h ec l a s s i f i c a t i o n sa n dt h ed e t e c t i n g m e t h o d so fc o d ec l o n e s ，t h ed i s s e r t a t i o nd i v i d e st h ec o d ec l o n e si n t of i v ec l a s s e s ， d i v i d e st h ed e t e c t i n gm e t h o d si n t of o u rc l a s s e sf r o man e w p e r s p e c t i v e o n ec o d e c l o n es e tw o u l dh a v em a n yc l a s s e so fc o d ec l o n e d i f f e r e n tc l a s s e so fc o d ec l o n e s h o u l du s ed i f f e r e n tm e t h o d st od e t e c tt h e m a f t e re x p o u n d i n gt h ed e t e c t i n gm e t h o d sb a s e do ns t r i n g 、m e t r i c s 、p d g ，t h e d i s s e r t a t i o na l s op r o p o s e st h ec o n c e p t sa n dt h e o r i e sc o n c e r n i n gt h em e t h o d sa n d i n t r o d u c e st h ed e s i g ns c h e m e sa n di m p l e m e n tm e t h o d so ft h e m k e y w o r d s c l o n ec o d e ；j a v a ；s t r i n gm a t c h i n g ；s o f t w a r em e t r i c s ；p d g - - 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：一净 关于论文使用授权的说明 日期：垫! 墨：竺：竺 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：型导师签名：日期：幽、丐 第l 章绪论 1 1 研究背景 第1 章绪论 成功的大规模系统被称为遗留系统【1 】。这些系统具有巨大的商业价值。但是 因为它们的体积庞大，并且缺乏文档信息，所以难于维护【2 】【3 】。其中相似性代码 是困扰工程师们的一大问题【4 1 。在一个大型的软件项目中，大约有1 0 至3 0 的代码是相似性代码。例如，g c c 中有8 7 的相似性代码，j d k 中有2 9 的相 似性代码，l i n u x 中有2 2 7 的相似性代码【5 】。 这些相似性代码的出现是南以下几种原凶造成的： ( 1 ) 使用复制与粘贴的方式书写代码比重新书写代码更简单、更快捷。此外， 被复制的代码往往经过了反复测试，比重新书写的代码存在更少的错误。 ( 2 ) 在软件开发中，往往根据+ 个程序员书写的代码量对程序员的表现进行 评价。 ( 3 ) 出于对运行时效率的考虑，调用一个过程可能会导致系统开销过大，采 用代码复制的方法会减小这种开销。 由于相似性代码的存在，导致了软件维护时7 0 的开销【6 】。卡内基梅隆大学 的t h o m a s 与微软公司的g i n a 及r o b e r t 在微软公司内部，针对软件开发人员， 就软件开发过程中存在的问题进行了调查。大约5 9 的程序开发人员指出：找 出所有的相似性代码是令人头疼的事情【7 】。 相似性代码的存在可能会为程序带来严重的安全隐患： ( 1 ) 在程序员对相似性代码中的一处进行了修改之后，忘记更新其它位置的 相似性代码，可能会造成程序的错误执行。 ( 2 ) 相似性代码不仅增加了代码长度，而且延长了程序的编译时间及执行时 间。 ( 3 ) 相似性代码揭示了程序设计时可能存在的问题，如缺少继承或者过程抽 象。 在软件维护过程巾，由低级的、面向实现的抽象级别，提取出设计级别，甚 至需求级别的过程被称为逆向上程【8 】。在逆向上程过程中，判断构件相似性是维 护构件库的重要环节【9 】。通过判断相似的代码构件，可以缩小构件库的大小，帮 助开发人员快速发现构件，方便基于构件的开发过程。 北京r t 、l k 大学二厂学硕十学位论文 1 2 研究内容 本课题主要讨论了i a v a 代码相似性判定方法中的相关算法及程序实现，并对 相似性代码的种类、各个种类的特点及相似性代码的检测方法，进行了一定的研 究与分类。通过总结不同的文献，本文将相似性代码划分为五类，分别是简单的 相似性代码、重命名的相似性代码、不邻接的相似性代码、乱序的相似性代码、 纠缠的相似性代码。本文将相似性代码的检测方法划分为四类，分别是基于串的 相似性代码判定方法、基于软件度量的相似性代码判定方法、基于抽象语法树的 相似性代码判定方法和基于程序依赖图的相似性代码判定方法。 根据词法、语法、语义三种层次信息进行分析，本文详细阐述了基于串的代 码相似性判定方法、基于软件度量的代码相似性判定方法、基于程序依赖图的代 码相似性判定方法的理论基础及设计方案。三种方法各有长短，根据不同的应用 场景，可以选择使用不同的分析方法。 基于串的代码相似性判定方法，根据i a v a 语言的词法信息及简单的语法信息， 对源代码进行比较。该方法成功的关键在于比较算法，通过对比较过程进行优化， 可以获得较高的计算速度。该方法的缺点是比较的精度较低。 基于软件度量的代码相似性判定方法，根据j a v a 语言的语法信息及简单的语 义信息，对源代码进行比较。通过选用适当的度量变量及聚类算法，可以获得较 快的计算速度。该方法的缺点是比较的速度较慢。 基于程序依赖图的代码相似性判定方法，根据l a v a 语言的语义信息，对源代 码进行比较。这种方法可以获得较高的比较精度，但是运算速度较慢，空间复杂 度也较高。 1 3 研究方法 本课题的研究方法主要为： 首先，针对代码相似性比较领域，调查并研究已有的解决方案，分析并讨论 它们的优缺点，吸收其r f l 的一些通用策略，改造为适合本课题的方案。 其次，研究面向对象编译器的实现机制【1 0 】【1 1 】，及编译优化机制【1 2 】【1 3 】【1 4 】。 最后，在程序实现时，扩展j a v a l 4 的文法，使其符合l a v a s 0 的一些特性， 从词法、语法、语义三个层次逐步实现代码相似性的判定。 第1 章绪论 1 4 论文结构 第1 章详细阐述了相似性代码产生的原因及其可能造成的危害，介绍了相似 性代码检测在软件维护过程r f l 的应用。此外，还阐述了论文研究的内容及研究方 法。 第2 章详细阐述了研究中涉及到的理论、概念、算法。其中主要阐述了代码 相似性问题、串匹配算法、软件度量理论、程序依赖图四个方面的问题。 第3 章详细阐述了基于串的代码相似性判定工具、基于软件度量的代码相似 性判定上具与基于程序依赖图的代码相似性判定工具的设计方案。 结论部分对本文的工作进行总结，对下一步任务进行展望，并提出了进一步 研究的设想。 第2 章研究现状与理论基础 第2 章研究现状与理论基础 2 1 相似性代码概述 尽管国内外已经在相似性代码领域开展了大量的研究工作【1 5 】，但是学术界对 相似性代码这一概念仍然没有一个统一的、精确的定义。基于不同的相似性代码 检测方法的计算过程，相似性代码也有不同的定义。普遍认可的定义是：相似性 代码是相同的或者近似相同的源代码片断 1 6 1 1 1 7 。大阪大学的y o s h i k ih i g o 给出 了相似性代码更精确地定义【1 8 】：相似性关系( c l o n er e l a t i o n ) 是一种代码片断 ( c o d ef r a g m e n t s ) 间的等价关系。当且仅当两个代码片断具有相同的序列时，它 们被称为具有相似性关系。具有相似性关系的一对代码片断被称为相似性代码对 ( c l o n ep a i r ) 。具有最大代码片断数量的，并且任何代码片断之间均具有相似性 关系的代码集合，被称为相似性代码集合( c l o n es e o ，相似性代码集合中的代码 片断被称为相似性代码( c o d ec l o n e ) 。 由于使用目的不同，不同工具对相似性代码的种类进行了不同的划分。工具 c g e 1 9 根据代码演化过程中执行的操作，将相似性代码划分为六类。工具s m c 2 0 根据相似性程度，将相似性代码划分为十八类。工具d a t r i x 2 x 根据相似性的范 围，将相似性代码划分为八类。工具d u p l o c 2 2 根据可视化的显示效果，将相似 性代码划分为四类。文献【7 】根据相似性的频率及代码的重要性，将相似性代码 划分为六类。文献 2 3 】根据程序中的依赖关系，将相似性代码划分为四类。 通过总结以上这些分类情况，本文将相似性代码划分为以卜五类： ( 1 ) 简单的相似性代码片断。 一般指逐字逐句，一字不差的完全一致的代码片断。 ( z ) 重命名的相似性代码片断。 相似性代码集合中的代码片断之间，除了变量名称不同、初始化赋值不 一致以外，其他的逻辑关系均相同的代码片断。 ( 3 ) 不邻接的相似性代码片断。 相似性代码集合r f l 的代码片断之问，夹杂一些不影响代码片断输出的无 用语句。代码片断的语句序列可能是不邻接的。 ( 4 ) 乱序的相似性代码片断。 相似性代码集合巾的代码片断之问，语句的执行顺序可能被打乱，但是 代码执行的结果不会因为语句执行的顺序不同而不同。 北京t 、l k 大学丁学硕士学位论文 ( 5 ) 纠缠的相似性代码片断。 如果相似性代码集合中的代码片断位于同一代码文件中，并且对应语句 的位置出现交错，则会产生纠缠的相似性代码。在纠缠的相似性代码集合巾， 每个代码片断中的任意一条语句都位于该相似性代码集合中任意一个相似 性代码片断的第。条语句与最后+ 条语句之间。 一个相似性代码集合巾的相似性代码片断可能具有一类或者多类相似性问 题。不同种类的相似性代码可以使用不同的方法进行判断。其中，第一类相似性 问题可以通过简单的词法分析方法实现；第二类和第三类相似性问题可以通过语 法分析方法实现；最后两类相似性问题需要通过语义分析方法实现。这三种分析 方法中，词法分析方法具有执行速度快的优点，但是准确度不高。语法分析方法 具有速度较快，精度较高的特点。语义分析方法具有精度高，但是执行速度慢的 特点。 如图2 1 所示，相似性代码的检测过程一般包括三个阶段：序列化、比较、 可视化表示。序列化阶段将获取的源代码文件转换为比较阶段所需的内部表示形 式。序列化的过程往往是词法分析、语法分析、语义分析的过程。比较阶段是在 源代码的内部表示形式上进行操作，并输出可视化表示阶段需要的数据。可视化 表示阶段将比较的结果呈现给用户。这三个阶段中，第二阶段的比较工作是较关 键的步骤，其余各阶段的执行都服务于比较。比较阶段的数据结构可能具有四种 形式：串、度量值、抽象语法树、程序依赖图。 r 开始 、 ， i序列化 上 i比较 i ， i町视化表示 厂 绍柬 、 图2 - 1 相似性代码的检测过程 f i g u r e2 - 1t h ep r o c e s so fd e t e c t i n gc o d ec l o n e 根据比较工作可能具有的四种数据结构，可以将相似性代码的检测方法归纳 为以下四类【1 6 】： ( 1 ) 基于串的分析方法。 本类方法的比较基础是串，因此具有速度快、精度低、比较结果语义不 6 第2 章研冗现状与珂论基础 完整的特点。代表性实现有：d u p z q 、a r i e s i s 等。 本类比较方法，通过比较源代码行 z q 、源代码标记【1 8 】【2 5 】或者源代码标 记的哈希值等，实现对源代码的比较分析。在比较的过程巾，往往仅存在词 法分析，以及简单的语法分析【1 8 】。有些基于串的分析方法甚至不进行词法分 析【2 4 】。本方法的主要研究点在于，选择合适的串匹配算法，尽量降低比较所 需的时间复杂度与空问复杂度。通过选用优秀的串匹配算法，可以实现工程 化的应用。 基于串的分析方法能够识别出第一类与第二类相似性问题，不能识别其 他类型的相似性问题。 ( 2 ) 基于度量的分析方法。 本类方法的比较基础是源代码的度量值，比较的过程往往具有试验性质。 凶此具有速度快、精度低、比较结果语义完整的特点。代表性实现有：c g e s 、 文献【2 6 】等。 本类比较方法，通过提取源代码的度量信息，进行聚类运算，获取语义 完整的结构单元，作为比较的结果。不同的度量信息，适用于不同的应用场 景。 基于度量的分析方法能够识别出第一类的相似性代码问题。根据度量的 依据不同、待比较语言的种类不同，该方法比较的结果差异较大，也可以部 分的检测出后四类的相似性问题。 ( 3 ) 基于抽象语法树的分析方法。 本类方法的比较基础是抽象语法树【1 2 】【1 3 】，冈此具有速度慢、精度较高、 比较结果语义完整的特点。代表性实现有：c l o n e d r 2 r l 。 基于抽象语法树的分析方法能够识别出第一类与第二类相似性问题，不 能识别其他类型的相似性问题。 ( 4 ) 基于程序依赖图的分析方法。 本类方法的比较基础是程序依赖图【2 8 】【1 0 】【1 1 】，凶此具有速度慢、精度高、 比较结果语义完整的特点。本类方法还没有典型的实现。文献 2 3 2 9 3 0 】 提出了使用程序切片构建同构程序依赖图，进行检测代码相似性问题的方法。 理论上，基于程序依赖图的分析方法，能够识别出所有的五种相似性问题。 在以上的四种方法中，基于抽象语法树的分析方法，在运算速度方面，不及 基于串的分析方法与基于度量的分析方法；在比较精度方面，不及基于程序依赖 图的分析方法，因此本文不对其进行阐述。下面将详细阐述其余三种方法的理论 基础与研究现状。 北京t , i p 人学t 学硕十学付论文 2 2k a r p - r a b i n 算法 2 2 1 简单问题的算法描述 k a r p r a b i n 算法【3 l 】是一个用于解决串匹配问题的随机算法。给定模板s x 与 文本串y ，其中x 的长度为n ，y 的长度为m ，7 l m 。该算法用于找出在y 中首次 出现的x 。通过将x 与一个指纹函数仍( 的相关联，e ( x ) 的长度远小于x 的长度， k a r p r a b i n 算法可以快速的解决串匹配问题。 指纹函数d ) 可以是任意一个易于计算的函数。当两个串匹配时，指纹函数 的值一定相等；反之，当两个指纹函数的值相等时，两个串未必匹配，此时称为 错误匹配。通过使用指纹函数，可以大幅压缩比较的时问。 令模板串x 与文本串l ，分别定义为： x = z l x 2 ，x i ( 0 ，1 ) ， 1 i 住 y = y l y 2 y m ，y i f 0 ，1 ) ， 1 f m 为简单起见，令( 0 ，1 ) 为字母表。针对其他语言，可以使用其它字母表。 令y ( i ) = y f y t + 1 y i + n 一1 ；当x = y ( f ) 时，两个串匹配。 定义口= x 1 2 n 一1 + x 2 2 n 一2 + + z ，t ， 6 ( ) = y i 2 n 一1 + y i 一1 2 n 一2 + + y i + 1 l - 1 ， 1 m n + 1 当两个串匹配时，必然存在指纹函数a = 6 ( f ) 。 给定整数c ，d 。令7 e s ( gd ) 代表c 被d 整除的余数。又令p 为任意一个质数，p 在 f 1 ，7 l m 2 】中，定义r e s ( c ，p ) = 已。 令代表盯m o dp ，其巾d r = + 广，。 k a r p r a b i n 算法初始时，计算瓦= ( z 1 p2 + p x 2 ) p2 + p x 3 与6 ( 1 ) 。该运算 可以在固定的时间内完成。在第i + 1 步，1 i + 1 m 一7 i ，计算6 ( + 1 ) ，递推公 式为灰丽= ( 丽一p 虿再py i ) p2 + p y i + n 。当且仅当五- - - 一a ( d r a ，x 与y ( f ) 可 能相等。若x = y ( f ) ，则两个串匹配。若x y ( f ) ，为错误匹配，再次随机选择 质数p 2 u 。 推论1 ：若u 2 9 且a 2 u ，则口具有少于7 r ( u ) 个不同的质数除数。 引理2 ：当u 1 7 时，兰l 7 r ( ) 1 2 5 5 0 6 u 一。 n u 。 i n l l 定理3 ：g s = 扫i p 为质数，p m ) 执行算法2 或者算法3 ，任意一个实例 ( x ，y ( r ) ) ，r 尺) 出现错误匹配的概率蓑等，其中n 2 9 。 1 n 第2 章研究现状与理论摹础 定理4 ：m s = 扫i p 为质数，p m ) 及= 执行算法1 ，任意一个实例 ( 伍，y ( r ) ) ，r 尺) 出现错误匹配的概率k ，其中n 2 9 ，且k ， 其中n 2 9 。 推论4 ( a ) ：m s = 伽旧为质数，p n t 2 ) 及= 执行算法2 或者算法3 ， 对于任意的输入数据7 l 、t ( n t 2 9 ) ，任意一个实例( zy ( r ) ) ，r r ) 出现错误匹 配的概率2 5 1 1 # ，其中k 为任选的参数。 推论4 ( b ) ：g s = 扫旧为质数，p n t 2 ) 执行算法1 ，对于任意的输入数据 n ( n 2 9 ) 、t ，任意一个实例( ( 墨y ( r ) ) ，r r ) 出现错误匹配的概率 ( 1 2 5 5 ) 七t 一( 2 良一1 ) ( 1 + 0 6i n ) k ，其中j ；= 为任选的参数。 定理5 ：算法1 是一个实时算法。对于每一个长度为n 的模板串和长度为m 的 文本串，算法2 或者算法3 的预期运行时间为d + m ) 。 定理6 ：若应用算法3 求解一般的串匹配问题( 伍，y ( r ) ) ，r 尺) ，其中i r i = t ， 且串x 与串y ( r ) 的长度均为n 。如果s = 函i p 为质数，p 冬n t 2 ) ，m = n t 2 且 = ，则出现错误匹配的概率( 2 5 1 1 # ) 七。 若算法3 中的指纹函数基于任意的模数而非质数，存在引理7 和引理8 。 引理 7 ：存在常数b ，对任意正整数x ， 有 川n z + b 一赤 2 s t h e n s ：= m “ e l s e m a r k a r r a y s ( s ) i fs 2 m i n i m u m _ m a t c h _ l e n g t ht h e ns ：2sd i v2 e l s ei fs m i 几i m u n l m a t c h _ l e n g t ht h e ns ：= m i n i m u m _ m a t c h _ i e n g t h e l s es t o p ：= t r u e u n t i ls t o p k 代表最长匹配。通过多次调用s c a n p a t t e m ( s ) 函数，可以获得k 的值。当 最长匹配找到后，则执行m a r k a r r a y s ( s ) ，进行标记。由于在第一次迭代以后，不 会存在长度超过当前搜索长度两倍的匹配，所以该算法是有效的。 在基于k a r p - r a b i n 的g s t 算法执行过程中，k a r p r a b i n 算法保证了查找的 速度；g s t 算法保证了查找的精度。因此，基于k a r p - r a b i n 的g s t 算法能够又 快速又准确的找到相似性代码片断。 2 3 软件度量 2 3 1 软件度量理论 工程学科是。个量化的学科，工程师使用数字进行设计和评估要制造的产品。 - 1 4 - 第2 章研究现状与理论基础 测量是任何工程过程的一个关键环节，通过测量可以较好地理解模型的属性，评 估工程产品或系统的质量。测度( m e a s u r e m e n t ) 为产品或过程属性的程度、数量、 维数、容量、大小提供量化指标。测量( m e a s u r e ) 是确定测度的过程。度量( m e t r i c s ) 【3 6 】是对具有给定属性的系统、构件、过程的定量测量 3 7 】。 度量是种能够用于决策的可比较对象。度量已知的事物是为了进行跟踪和 评估。度量未知的事物是为了预测。在软件开发巾，软件度量的目的是方便管理。 因为无法管理不能度量的事物，所以需要利用度量对软件过程进行改进。上个世 纪6 0 年代末期的大型软件所面临的软件危机反映了软件开发中管理的重要性。 对于管理层人员而言，没有对软件过程的可见度就无法管理：没有对见到的事物 用适当的度量或适当的准则去判断、评估和决策，也无法进行优秀的管理。软件 工程的方法论主要是为了提高软件的可见度。 软件工程中的度量是一种有模型和理论支持的方法。软件度量的实质是将现 实世界中的数字或符号指定给实体的某一属性，提供明确的描述规贝j j 3 8 。通过 使用软件度量，能够科学地评价软件质量；有效地控制和管理软件开发过程；合 理地组织和分配资源；制定切实可行的软件开发计划；提高软件的可理解性和可 维护性；以低成本获得高质量的软件。 为真实世界中的某 些宴体确定属性 为属性确定经验关系 上 确定与每种经验关系 相对应的数字关系 上 定义从真实t 址界的 实体到数字的映射 图2 - 2 度量的关键阶段 f i g u r e2 - 2t h ep i v o t a lp h a s e so fm e t r i c s 任何一个度量都包含以卜四个要素： ( 1 ) 被度量的客体或事件； ( 2 ) 度量的属性； ( 3 ) 赋予客体或事件的数值或符号： ( 4 ) 使客体与数值相联系的映射。 北京丁业大学丁学硕：卜学位论文 如图2 2 所示，度量包含五个关键阶段。 尽管已经提出了数再种计算机软件的度量方法，但并不是所有的度量都能够 为软件工程师提供实用的支持。e j i o g u 定义了一组有效软件度量所应具有的属性。 度量及度量的测量应该是： ( 1 ) 简单的和可计算的； ( 2 ) 在经验上和直觉上有说服力； ( 3 ) 一致和客观的； ( 4 ) 单位与量纲的使用是一致的； ( 5 ) 编程语言的独立性； ( 6 ) 高质量的反馈机制。 令p ，q ，尺表示代码片断；i v l 表示代码片断p 的复杂度，i p l 的值与p 的某个度 量值相关联。对于任意一个代码片断p 的任意一个度量值i p i ，i p i 为非负值。 w e y u k e r 提出了一组用于判定度量方法是否实用的形式化准则【3 9 】： 性质1 ：( 3 p ) ( 3 q ) ( i p i i q i ) ，即同一度量方法对所有代码的度量结果不全 相同。 性质2 ：对于非负实数c ，只有有限个代码片断具有度量值c 。 性质3 ：( j p ) ( 了q ) ( p qai p i = i q i ) ，即度量准则不能精细到令所有代码 片断的度量值都相同。 性质4 ：( | p ) ( | q ) ( p 三qai p i l q i ) ，即功能相同的代码片断，由于实现 细节不同，所具有的度量值可能不同。 性质5 ：( v p ) ( v q ) ( i p i i p ；q iai q i i p ；q i ) ，即度量准则的单调性，两个 代码片断合并后的度量值不小于其中任意个代码片断的度量值。 性质 6 ( | p ) ( | q ) ( | 尺) ( i p i = i q lai p ；r l i q ；r lvi p i = l q iai 尺；p i l 尺；q i ) - ，即代码片断p 与q 度量值相同，但它们分别与代码片断尺合并后的度量 值可能不同。 性质7 ：存在代码片断p 与q ，其中q 是p 中语句重新排列后组成的代码片断， 但i p i i q i 。即语句顺序影响度量值。 性质8 ：若p 是q 的重命名，则i p i = i q l ，即代码片断的变量改名不影响度量 值。 性质9 ：( 3 p ) ( 3 q ) ( i p i + i q l l k 大学工学硕l 学竹论文 2 4 程序依赖图 2 4 1 程序依赖图描述 程序依赖 ( p r o g r a md e p e n d e n c eg r a p h ，p d g ) 是一种统一的框架，被有效的 应用于常规计算机、向量计算机及并行计算机上，实现优化编译器的代码内部表 示。通过将代码中的数据依赖及控制依赖显式化，揭示代码潜在的并行性，它已 经被广泛的应用在软件分析、软件理解、软件调试、软件测试、软件度量、软件 质量保证、逆向工程等领域。 程序依赖图由控制流图、控制依赖图( c o n t r o ld e p e n d e n c eg r a p h ，c d g ) 和数据 依赖 ( d a t ad e p e n d e n c eg r a p h ，d d g ) 组成【4 0 】。其巾，控制流图捕述了程序r f l 的 控制流，它类似于程序的流程图。控制依赖图描述了程序中的控制依赖。数据依 赖图描述了程序中的数据依赖。 程序依赖图中的结点既可以表示语句或断言表达式，也可以表示操作或操作 符。指向结点的边既可以表示该结点的操作所依赖的数据值，也可以表示该操作 执行所依赖的控制条件。不同的结点内涵可以满足不同需求领域。结点间所有依 赖关系组成了。个偏序的语句及断言的集合，该集合保持了原始程序的语义信息。 依赖是两方面不同作用的结果。首先，若两条语句交换顺序，其r f l 任意一个 变量值可能不正确，则两条语句存在数据依赖。例如，假设存在s 1 与s 2 两条语 句。 a = b cs 1 d = a e + 1s 2 若将s 2 置于s 1 前，则可能导致s 2 中的4 不正确，因此s 2 依赖s 1 。这类依赖被 称为数据依赖。 其次，语句与控制该语句执行条件的断言之间存在依赖。例如，假设存在以 下语句序列。 圹c a ) ( s 1 b = c ds 2 ) 冈为断言a 的值决定s 2 是否能够被执行，所以s 2 依赖断言a 。这类依赖被称 为控制依赖。 2 4 2 控制流图描述 定义1 控制流i 虱( c o n t r o lf l o wg r a p h ，c f g ) 是一种有向图，它存在一个入口结 一2 0 - 第2 覃研究现状与珂论基础 点s t a r t 和一个出口结点s t o p 。控制流图可以用四元组g = ( ，e s t a r t ，s t o p ) 表 示。其中，是结点的集合，表示代码中的基本块。e 是边的集合，表示基本块 之间的前驱后继关系。每条边是一个有序结点对( n ，7 l f ，表示从n f 到n ，可能存 在的控制转移。s t a r t 和s t o p 分别表示子程序的入口和出口结点。 控制流图是程序分析领域中个非常重要的概念。它将源代码用图的形式表 示出来。在控制流图上，可以方便的分析语句问的前驱后继关系、支配结点、 后必经结点以及程序执行路径等问题。通过分析控制流图，可以获取语句间的控 制依赖和数据依赖关系。在控制流图中，结点表示代码中的基本块，边表示基本 块之间的关系。 性质1 在控制流图中，结点n 和结点m 之间有一条边连接的充要条件是程序 执行过程能从对应结点n 的语句到达对应结点m 的语句。 定义2 在控制流图中，若( n 1 ，n 2 ) e ，则称n 1 是n 2 的直接前驱，礼2 是t t l 的 直接后继。结点n 的所有直接前驱组成的集合称为n 的直接前驱集，记为 d - p r e