（计算机软件与理论专业论文）大规模软件的静态结构复杂性分析工具及度量方法.pdf

东北大学硕士学住论文摘要 大规模软件的静态结构复杂性分析工具及度量方法 摘要 传统的软件度量方法已经提供了很多评价和控制软件质量的手段，但是随着软件规 模的逐渐增大，软件复杂性的不断提高，软件各组成部分之间的相互作用使得软件系统 在部分之和以外又产生了作为整体而具备的新特点，这些特点就蕴藏在软件的结构之 中。软件的结构复杂性成为了软件质量的主要影响因素。在软件体系结构方面，软件的 结构已经出现了多种层次、不同粒度、多种集成方式的组织方法。但是目前还没有有效 的度量方法对软件结构中蕴含的复杂性进行量化研究。 针对上述问题，为了能够度量软件结构中蕴含的特性与规律，进而控制现代软件的 质量问题，本文结合新兴的复杂网络理论知识，将软件看作是由模块和模块之间的关系 组成的一种特殊的网络结构，进而可以将软件的结构组织通过网络拓扑特征来进行量化 插述。本文实现了一种软件静态结构网络化特征分析工具，将软件静态结构抽取为网络 拓扑，利用网络拓扑特征对软件结构进行量化描述和计算分析。通过总结软件结构的具 体特性及其展现的网络拓扑特征值之间的关系，构造了一种软件静态结构的测度集，并 对其进行验证实验。 该测度集的度量值与实际系统的特性相吻合，度量正确有效，可以作为对现有软件 度量方法的一个补充。此外，对软件结构的网络化描述和研究方法也在软件的容错性与 鲁棒性控制、软件的迭代开发与重构、软件的测试与估计预测等方面有重要的现实意义 与应用前景。 关键词：软件工程；软件度量；软件结构复杂性；复杂网络；无尺度；小世界； 拓扑特征 一i i 东北大学硕士学位论文 a b s 仃a c t a n a n a l y t i c a l1 o o la n dam e t r i c ss e tf b rt h es t a t i cs t r u c t u r a l c o m p i e x i t yi nt h el a r g e - s c a l es o l t w a r e a b s t r a c t n 坨仃a d i t i o n a ls o f h a r em e t r i c sh a v ea l r e a d yp r o v i d e dal o to fm e t h o d sf o rt h e f t w a r cq i l a l i t y “a l u a t i l l ga i l dc o n t r o l l i i l g h o w e v e r ，硒t l l e f h 钌es c a l e sa r eg r a d l l a l l y i n c f e a s i n g ，t h ec o m p l e x i t i e so fs o f t w 甜ea r ec o n l i n u o 璐l y 洒p r o v i n gt o o ，t h ei n t e r a c t j o 璐 锄o n gt h ev a r i o 邶c o m p o n 印t si n 血es o f h a i cs y s 地咀b r i n go u ts o m en e w c h a r a c t e r i s t i c s 勰 aw h o l e t h e s en e wc l 姗c t e i i s 虹c so f 曲哈s o 矗w a r cc o n t a i ni nt h es t n i c m l l e t h es o r w 撤 s 拉1 j c t i l 糟ic o m p l e x i t 主e sb e c o m et h em a i 王lf 缸t o f sa 丑 e c 出培t h es o f 奴a r 。q u 盆l i t i e s ，i ns o 最嘴 a r c h i t e c t l i r e ，t h e a r ev a i i o u sf o m l so fi n t e g 阿t i o ni nd i 任b r c n tl e v e l s ，d i 任b r e 玎ts i z e s ，8 n d d i 肪r e mo f g 觚i z i l l gt y p e s t h e r ei ss t i i ln oe 舵c t i v em e 也0 df c rt h eq 啪t i 枷v e m e a s u r e m e n tt os h o wt h ec o m p l e x i t ye m b e d d e di nt h e 蚰1 “湘鹏o f t h es o 衔硼r c i nv i e wo f 锄c hp r o b l e m s ，t om e 邪u 地t h ec h a r a 耽e f i s t i c s 柚dl a 、v sc o n t a i n e di nm e s 咖c t u r eo fs o f t 眦e ，a n dt h e nt ot a k ec o n 昀lo ft h em o d e ms o n w a r eq l l a l i t i e s ，c o m b i n i i l g an e wd i s c i p l i n en a m e d 卿l e xn e 嘲o r _ k s ，也ei n o d u l e s 主ns o f 飘a r e 跹d 也er c l a t i o n s l l i p s a m o n gt b e s em o d 谢e s 啪b e e n 鹬as p e c i a l 鼬do fn e t w o 矗咖m r e s 仇l c t t i r eo f 擗 行w a r c 啪t h e nb ec o n v e r t e di d t on 钟w o 出t o p o l o g yf o rq 啪t i t a t i v ed e s c r i p t i o mt h i s t h e s i sd e s 曲b e s 越i m p l e m e n t a t i o no f 锄a n a l ”i c a ls o 胁a t o o lf o r 也en c t 、o r kt o p o l o 西e s c o n v e r t e d 自o ms o 矗w a r cs t a t i cs 臼1 1 c t i l r e s ，缸dt l l ef e a t i l r e so ft l l en e t w o r kt o p o l o g yc a nb e l l 辩df o rq u 锄t i t a t i v ed e s c r i p t i n g 孤da n a l y z i i l gt h es o f t w a 托b yc o r r e s p o n d i n g 谢mm e f 蛔甜es 帆l c t t l r a lc h a r a c t e r i 姬c st 0t h en e t w o r kt o p o l o g i c a lf e a t i i r e s ，ac o m p l e x i t ym e t r i c s tf b rt h es t a t i cs t m c t 硼o fs o b w a 佗w 嬲f o n n e d ，锄da ne x p e r i i n e mt e s tw 船t a k c n t h e r e 辄ho ft h ee x p e 咖e n ts b o w sm a tt h em e 啊c ss c ta c t u a j i y 丘t sm es y s t e mf e a m r e s ，m c c o n e c t i l e s sa n de 丘b c t i v e n e s so f t h em 弼c ss 武w e 心p r o v e d t 1 l i sm e t r i c ss e tc a nb el l s e d 嬲ac o m p l e m e n t a r ym e t l l o df o rt h e 仃a d i t i o n a ls o f t 、硼睇 m 耐s i na d d i t i o n t h en 咖o r k - b 鹊e dd e s c r i p t i o no ft h es o f h m ea r c h i t e c t i l r e 觚di t s r e s e a r c hm e t h o d sh a v ei m p o n a n tp r a c t i c a ls i g t l i f i c a i l c e s 锄d 撕g h tp r o s p e c t si nt h e f h v a r e sf a l l l t t o l e 啪t ，r o b 髑tc o n n _ o l ，i t c 硎v ed c v e l o p i l l g 趾dr e f 如t o r i n g ，a n ds o f t w 鹏 一h i 一， 东北大学硕士学位论文 a b s 打a c t t e s t i n go rp r e d i 幽g 1 ( e ，唧o r d s ：s o f h v a r ee n g i e r i n g ；s o n w a f em e t r i c s ；f t 、愀s t m c t l l r a lc o 玎叩l c x i t y ； c o m p l e xn e 撕o r k s ；舭e s c a i e ；s m a l l w o d d ；t o p o l o g ) ，c h 锄c t e r i s t i c 一一 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位面使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名：祧 签字日期：涧1 1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下 学位论文作者签名：崔魅 签字日期：、o 门l 1 ) 1 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 软件复杂性问题和软件度量的新挑战 1 1 1 软件和软件复杂性问题 软件是影响世界各个领域的强大“驱动力”，如何更有效更快捷的开发高质量的软 件是软件界孜孜以求的目标【l 】。计算机软件在跨越5 0 余年的时问内已经经历了很大的变 化。硬件性能的极大提高、计算机体系结构的深远变化、网络的大规模应用等等都使得 构造更为高级和更为复杂的软件系统成为了可能。人们也倚仗于这些大规模软件来处理 现实中难以解决的复杂问题。当一个大规模软件系统成功时，这种高级性和复杂性能够 产生出奇迹般的效果，但是，这些大规模软件系统却给建造它们的软件开发人员带来了 极大的问题。随着软件规模和目标问题领域的复杂程度增加，软件的复杂性也随之水涨 船高，而处理这些复杂性带来的开发困难，几乎是指数级的增长。据2 0 0 4 年p cw 硎d 杂志的调查，美国3 0 的软件项目被取消，5 0 的项目超预算，6 0 的项目被发起单 位认为是失败的，9 0 的项目不能按时完成。另据美国政府下属研究机构国家标 准局( n i s t ) 的数据显示，美国经济因软件错误每年要损失高达5 9 5 亿美元脚。 无论是在过去还是在现在，大规模软件系统的开发就犹如一个“史前的焦油坑”【3 l ， 各种团队，大型的和小型的，庞杂的和精干的，一个接一个的淹没在了焦油坑中。表面 上看起来好像没有任何一个单独的问题会导致困难，每个问题都成功获得解决，但是当 它们相互纠缠和累积在一起的时候，团队的行动就会变得越来越缓慢。对问题的麻烦程 度，每个人似乎都会感到惊讶，并且很难看清问题的本质。东北大学辽宁省嵌入式技术 重点实验室自创立以来在大规模软件系统开发领域进行了不断的实践和研究，经历过大 规模软件开发中的起起落落和痛苦磨砺，对大规模软件开发中的复杂性问题印象深刻。 为了有效快速的开发出高质量的大规模复杂软件系统，必须对软件中的复杂性进行了解 和控制。 1 1 2 软件度量学和复杂性管理 在各种各样的系统之中，度量活动始终处于一个核心的地位。度量有助于了解系统 一1 一 东北大学硕士学位论文第一章绪论 的面貌，以便做出有助于提高系统质量的分析和改进。如果要提高软件工程领域中对复 杂性的控制程度，也必须对软件系统进行度量，“但凡是不能度量的，便是不能对其进 行预测和控制的”【4 】。软件的属性不能仅有定性的研究，还必须有定量的研究，软件度 量学正是顺应这种趋势而产生的。 软件度量这一术语所包含的活动有很多，这些活动都会程度不同地涉及到软件开发 中的问题管理。其中以复杂性的控制为目的，比较常用的是结构复杂性度量。在可运行 版本未生成之前，是无法对诸如可靠性和可维护性之类的理想属性进行测量的。然而， 工程师希望能够在系统还没有完成之前进行这样一些预测：软件系统中哪个部分的可靠 性交叉? 哪个部分的测试难度较大? 哪个部分较其他部分需要更多的维护? 甚至 希望在系统还在设计阶段就进行这样的预测。因此，需要在软件成型之前( 甚至无须运 行系统) 就能够获得软件表示的结构属性进行测量；然后再试图建立各种经验预测理论， 以便为质量保证、质量控制和质量预测提供支持。 h a l s t e a d 【5 1 、m c c a b e 【6 1 、c & k 1 7 1 和m o o d 【8 1 等度量方法提供了该类方法的经典实例， 它们都定义了从合适的源代码表示中提取出来的度量。但是，随着软件开发技术的发展 和实际需求的变化，今日的软件结构较之以前发生了比较大的进化，而对与需要度量的 特性提出了新的要求。 1 1 3 现代软件的新特性和度量要求 从结构化程序设计到面向对象的程序设计，从模块化的软件构造到基于构件的软件 开发乃至现在炙手可热的s 0 a ，软件设计和实现的重点已经从单一的如何解决局部的困 难问题，转化为如何将代码有效的组织起来。近十年来关于软件体系结构的研究已经成 为一个热点课题。一个好的软件结构组织方式可以更好的帮助软件工程师有效地、快速 地开发易修改、易维护、工作可靠的软件系统。 在软件体系结构方面，软件的结构已经出现了多种层次、不同粒度、多种集成方式 的组织方法。传统的软件结构和复杂性度量方法：有的是针对文本复杂性( 如h a l s t e a d ) ； 有的是针对结构化程序的结构复杂性( 如m c c a b e ) ；有的是针对面向对象程序设计的抽 象数据类型单元的复杂性( 如c & k 、m o o d ) 。它们的局限性在于，更多的考虑了软件 中组分单元的属性度量，对于软件组织结构本身蕴含的复杂性信息没有足够的评价。而 事实上，随着软件规模的增大，在软件结构中蕴含的属性就变得越来越重要，有效的度 量软件系统的结构复杂性成为一个十分紧迫的任务。b r o o l 【s 认为度量在结构中蕴含的信 一2 一 东北大学硕士学位论文第一章绪论 息是计算机科学发展中的三大挑战之一【9 】。 再者，传统度量方法大多属于单一粒度下的度量手段，对于目前由不同粒度的组分 混杂集成的复杂软件系统，显得有些无能为力。 综上所述，传统的软件复杂性度量方法尽管被认为在一定程度上有效的反应了软件 的特性，并给软件开发的管理与控制带来一定的好处。但是它们的实际应用效果并没有 人们期望的那样显著，也没有得到广泛的认可和应用。而且在现代软件工程中极其重视 的体系结构度量方面还缺少有效的度量手段，需要一种能够反映不同粒度组分构成的软 件系统结构复杂性的度量方法。 1 2 大规模软件静态结构复杂性的度量研究 1 2 1h l t e m e t 复杂性的研究与发展 在自然界和人类社会中的很多复杂系统的结构都体现出了一种网络化的组织结构， 如互联网、人际网络、人体神经脉络、电力网络等。而“复杂网络”作为研究这些复杂 的网络结构的一门新兴学科，以数学中的图论为理论基础，大量地应用统计物理学的方 法，对网络的几何性质、形成机制、演化规律、结构稳定性和动力学等方面进行了大量 的研究，也取得了丰硕的研究成果【埘。科学家发现在复杂网络的复杂背后蕴含着一些普 遍的规律性，可以使用一些方法来定量的表示和进行分析，其规律呈现的形式十分直观， 成为了不同学科领域共同关心的热点。 1 9 9 9 年以来，人们逐渐发现了i n t 锄吐作为一种复杂网络的拓扑结构特点，并在 m t c m e t 的拓扑结构研究方面进行了大量的有重要意义的研究，东北大学嵌入式技术实 验室从2 0 0 1 开始进行h t e f n e t 拓扑结构的复杂性研究，并取得了许多丰硕的研究成果， 基础积累雄厚，2 0 0 5 年2 月，n e m e t 结构及数据进行研究的国际合作机构c a d a 中国 第一节点落户东北大学。 对i n t l e t 结构和数据的研究基础，实验室积累了大量的相关研究方法和手段，也 提供了研究复杂系统结构复杂性的独特视角。 1 2 2 软件结构和复杂网络 大规模软件系统的复杂性已经是老生常谈了，而作为一个复杂系统，软件系统也展 现出了另外一种很重要的复杂网络结构。自从复杂网络开始得到重视以来，不断有研究 一3 一 东北大学硕士学住论文第一章绪论 提及软件系统作为复杂网络的案例，但是这种微妙的关系在复杂网络研究的前几年间一 直没有得到足够的重视。 软件由很多互相有联系和交互的单元或者子程序构成，这些单元的种类繁多，拥有 不同的粒度( 如函数、类、源代码文件、程序库、组件等) 。这些部分的关联和交互可 以被用来定义一种网络拓扑，进而作为一种软件结构特性的模型来进行研究。2 0 0 3 年的 一篇论文【1 i 】以软件系统作为复杂网络为主题描述了软件结构和复杂网络的关系和研究 前景，些相关的研究【协1 5 】也在不同的角度尝试利用复杂网络的研究进展在软件领域做 出突破性的成果。但是总体来说，目前国内外的研究还停留在初始敏感点上，当前的首 要任务是通过分析和计算，获取足够的软件结构的网络拓扑特征，结合软件工程学的实 践，理解特征的本质。可以说通过复杂网络的理论基础，对软件结构的拓扑特征进行分 析和研究引起了一定的关注，本类课题的研究是一种对软件结构复杂性全新诠释。 1 2 3 本文的研究内容和方法 针对传统软件度量方法无法满足现代软件度量要求的问题和软件结构度量与分析 方面的迫切需求，结合软件结构作为复杂网络进行研究的最新进展。本文在应用复杂网 络理论进行量化表示和度量软件静态结构复杂性方面进行了若干研究，研究的内容包 括：如何将软件系统表示为可以做量化分析的网络模型；软件系统作为一种复杂网络具 有何种基本特征；在特征分析的基础上研究软件系统的结构复杂性测度。 本文采用的研究方法： ( 1 ) 将软件系统的静态结构表示为一种网络拓扑以便进行研究； ( 2 ) 实现一种基于源代码作为输入的软件静态结构的网络化特征分析工具； ( 3 ) 对一定量的软件进行实验计算，分析其实验结果； ( 4 ) 在实验分析的基础上，总结现象和规律，初步研究软件静态结构网络拓扑特 征的现实意义， 1 2 4 本文研究的现实意义 ( 1 ) 更好的理解软件开发的“规则” 复杂网络理论，提供了一种前所未有的手段，可以跨越尺度的得到对软件结构观察 的特别角度，借助这种角度，可以获取到潜藏在结构中的软件特性，从而更好的理解软 件开发中的设计规则。 一4 一 东北大学硕士学位论文第一幸绪论 ( 2 ) 软件的质量度量 控制软件的质量是十分必要的，大规模软件的质量控制十分困难，复杂网络首先提 供给了一种方法，可以定量的研究软件的质量问题，尤其在把握软件结构表现出的质量 信息有特别的优势，可以作为软件结构复杂性度量的重要补充。 ( 3 ) 软件鲁棒性、容错性 软件系统的需求和应用环境是多变的，软件系统的行为和结构是复杂的。这样一种 复杂的结构导致鲁棒性和脆弱性共存的特点，脆弱性会导致系统开发和使用中的一系列 问题。软件工程从各个方面出发，致力于解决这些问题。自然界中，种群的演化过程是 个体数量在增长的同时以某种偏好依附等方式选择丽形成的稳定的网络结构，这种结构 经过了时间的考验。软件作为人工系统，可以借鉴这种进化模式和网络结构，以解决软 件开发中的问题。从复杂网络的角度出发，可以着重对网络拓扑特征进行研究，设计容 错性更好，鲁棒性更佳的系统结构。 ( 4 ) 模式、迭代和重构 设计模式是一种使用已有模式的方式组织特定对象之阿交互关系的方法，模式在解 决特定关系的时候具有重要意义，它可以避免由于系统内部随意约束而导致的难以进化 的问题。软件的复杂网络特征恰好表达了软件的结构，可以从中寻找到模式和反模式， 在迭代和重构中改进现有的软件结构。值得注意的是，软件网络拓扑的无尺度特征可以 平衡系统的自然进化和人工控制的关系，在整体的层面上全面地设计并重构出符合模式 的软件结构。利用这种度量方法可以在开发阶段中利用度量结果对系统进行预测，以便 找到下一次迭代和重构中需要注意的方面。 ( 5 ) 定制软件测试策略 随着软件规模的不断扩展和复杂程度的不断提高，软件的测试难度也不断增大。软 件的网络化研究可以提供设计全面软件测试过程的新思路。 1 3 本文组织结构 本文共六章，本章为引言部分，主要对本文目标问题的产生背景，研究动态以及工 作思路和内容作以介绍。在下面的第二章到第六章主要阐述本人在本课题研究中的主要 工作。本文以下各章安排如下： 在第二章中，参照复杂网络的相关定义，给出了软件静态结构的网络拓扑定义，为 应用复杂网络理论进行软件结构的研究提供了理论依据和基本模型。 一5 一 东北大学硕士学住论文第一章绪论 在第三章中，针对研究软件结构的网络特征的实际需要，分析、设计弗实现了一个 专用于软件静态结构网络拓扑的度量分析工具，该工具是完成论文工作的基础和必要条 件。 在第四章中，应用软件结构网络化度量工具，对若干软件系统进行了特征量的度量 和计算分析，总结了软件结构特征与网络拓扑特征量之间的影响关系，为最终利用软件 结构网络拓扑特征量做好了准备。 第五章中，将结合第二章的网络概念模型，依据第四章中总结的规律和对应关系， 提出一种基于网络拓扑特征的软件静态结构复杂性测度集，并通过实例度量进行验证， 第六章，对全文工作的主要贡献进总结，并提出进一步的工作展望。 一6 一 东北大学硕士学位论文第二章软件静态结构的网络化表示 第二章软件静态结构的网络化表示 2 1 软件静态结构网络拓扑 2 1 1 网络和复杂网络 早在1 9 2 2 年，社会学家斯梅尔( gs i r r 蚰e 1 ) 就曾不经意地创造了“网络”这一词 汇，未曾料想到这个词汇会在社会学领域中使用极为频繁，并成为社会网络分析方法的 主导词汇；更没有想到的是，在今天的自然科学中，网络研究也成为重要课题。今天的 社会已经成为网络的社会，人们的日常生活已经无法离开网络。网络是一个由许多节点 及连接节点的边组成的集合【1 6 】，其中节点用来代表真实系统中不同的个体，而边则用来 表示个体间的关系，如果两个节点之间具有某种特定的关系则认为有边相连。 【定义2 1 】网络( n e t w o f k ) ；称= ( 矿，e ，g x ，y ) 为一个网络，如果 ( 1 ) g = ( y ，e ) 是一个有向图。 ( 2 ) c 是e 上正整数，称为容量函数，对于每条边e ，c ( p ) 称为边p 的容量。 ( 3 ) j 与，是矿的两个非空不相交子集，分别称为g 的发点集与收点集， i = f v l x u y ) 称为是e 的中间点集，j 的顶点称为发点( 源) ，j ，的顶点称为收点( 汇) ， ，的顶点称为中间点。 在图论中网络g = ( v ，e ) 是指由点集w 和边集e 矧组成的图，且e 囝中的每条 边略有w 中的一对点 ，v ) 与之对应。记顶点数为= m ，边数为三= l 矧。如果任意 ( “，v ) 与( v ，“) 对应同一条边，则称为无向网络，否则为有向网络；如果任意k ，l = l 则称 为无权网络，否则为加权网络i ”l 。 在统计物理学中把网络看成包含大量个体以及个体之间相互作用的系统，是把某种 现象或某类关系抽象为个体( 顶点) 以及个体之间相互作用抽象成边而形成的图。 网络可用来描述节点之间的相互关系：如人与人之间的社会关系，物种之阅的食物 链关系，词与词之间的语义联系，手机与手机之间的通话联系，网页之间的超链接，科 研文章之间的引用关系，以及科学家之间的合作关系，甚至产品的生产与被生产关系都 可以用网络来描述。这就使得真实世界可以通过抽象化的网络模型来进行研究和分析。 最近几年，由于计算机数据处理和计算能力的飞速发展，科学家们发现大量的真实网络 既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统计特征的网络。这样 一1 一 东北大学硕士学位论文第二章软件静态结构的网络化表示 的网络被科学家们叫做复杂网络。 【定义2 2 】复杂网络( c o m p l e ) 【n 酣o r k s ) 是指大量具有紧密联系和彼此间相互 作用的单元所组成的网络。这是一种处于混沌边缘的特殊网络结构，既不是规则网络， 也不是随机网络。 按照网络的各种特征量对网络进行分类，可分为规则网络、随机网络【1 8 1 、小世界网 络1 9 1 和无尺度网络【捌等等。人们在此基础上从不同的角度出发提出了各种各样的拓扑特 征结构模型【2 1 ，2 2 】。这些模型和基于模型的方法可以有效的帮助人们认识和理解真实世界 中的结构和关系特性。 复杂网络从得到重视以来，被映射到了许多学科领域的研究之中。复杂网络真实存 在于复杂系统的结构与联系之中。作为一种复杂系统，大规模软件系统中因为结构化和 模块化的发展也呈现出一种独特的复杂网络。 2 1 2 软件静态结构 在软件工程领域，为了解决复杂性，软件开发的一种最常用的构造方法就是将复杂 的计算问题分解成为许多相对简单的但是相互关联的颗粒。为了节约成本，这些软件颗 粒又尽可能的被设计和实现为可以在多种环境中能够重用的程序单元，为此程序员开发 了抽象的函数和数据类型。对这些程序单元的重用极大的提高了再次开发的速度，节约 了成本的同时，因为这些重用单元已经得到成功的验证，又在很大程度上提高了新开发 系统的局部可靠性。于是模块化开发成为了一种十分有效的软件工程方法。 当软件规模越来越大，领域问题越来越复杂时，软件的模块化设计与实现也遭遇了 困难。软件的计算任务需要由各种各样的职责分散的计算单元来共同协作完成。这些单 元可能是类、函数、模块、组件甚至是单独的程序进程；而协作关系则包括单元之间的 数据共享、消息传递、功能重用等。如何安排这些单元的协作关系，成为了软件开发中 极其重要的问题。而这些单元组合构造成为软件系统的过程和方法的表示就叫做软件的 结构。软件结构又分为软件静态结构和动态行为。 软件静态结构，可以把系统的静态方面看作是对系统的相对稳定的骨架的表示，它 由子程序、数据结构、类、接口、协作、构件或者节点等事物的布局组成。静态结构定 义了系统中重要组成单元的属性和职责以及这些单元之间的相互关系。一个软件系统的 静态结构是固定的，只有改变软件系统本身才能够改变软件的静态结构，软件的静态结 构不受系统运行的环境、状态和时间所影响。 软件动态结构定义了软件系统的组成单元的时间特性和这些单元为完成目标任务 一8 一 东北大学硕士学位论文 第二章软件静态结构的网络化表示 而相互进行通信的事件。动态结构反映系统的运行时行为，与系统运行的环境，系统状 态和时间有关。同时，软件动态结构受静态结构所约束。 软件设计和开发的一个目标就是构造一个最优的或者较优的软件结构。现代软件开 发的现实要求是，软件不仅能够正确的工作，软件系统还必须易于改变和扩展。而这种 要求直接取决于软件结构的设计与实现，结构良好的软件可以提高软件的可靠往和易维 护性。而静态结构特性是软件结构的主要方面。 2 1 3 静态结构中的个体和关系 现代软件系统几乎全部由各种各样的组成部分组合而成，软件静态结构描述了这样 一种组合式的结构。软件的组成部分的粒度是多种多样的，在任何一种粒度之下，这些 组成部分之间都通过互相的协作关系联系在一起共同组成软件系统或者软件系统中高 一级的一部分。随着软件规模的增大，这些关系也变得错综复杂。如果把软件系统中的 组成部分看作是个体，它们之间的协作关系作为个体之间的关系，这样就拥有了一个定 义2 1 中的网络。由此便可以获取一个关于软件静态结构的网络，这个网络在软件本身 不发生变化的情况下具有唯一的拓扑特性。 衰2 i 面向过程程序源码示例 ；t“blc2 1 a 蛐p l eo f p l o c e d i 球c m 记n 把dp f o g 髓ms r v 0 1 口m l n u f l tl s ( ) f r e t u z ns 恤： ) f l o a t4 - “o r e t u t n ： f 1 0 4 t4 j y r o f f l ti = a _ m ( ) ： r e t u r ni f l o a t0 0 l 在蕊向过程的结构化程序设计中，组成软件系统的基本单元是子程序或函数。各个 子程序或者函数之间以一种“调用”关系组合在一起完成复杂的任务。在软件工程领域， 一9 一 o o o 嚣一 眦晰毗呲呲眦 东北大学硕士学位论文第二章软件静态结构的网络化表示 调用图就描述了子程序或者函数之间彼此调用、互相依赖、协作构成软件系统的结构。 调用图通常包含两个方面，一方面动态调用图在程序运行期间真实的反映在一定条件下 的系统运行过程；另一方面，不考虑程序运行时带来的环境状态时序等因素，将所有可 能的子程序和函数之间的调用全部描述出来，并且加上对于数据结构元素的依赖关系， 于是就可以用软件的调用图描述出面向过程的结构化软件系统的静态结构。下面是一个 示例，表2 1 中为一个面向过程程序的样例，图2 1 左图描述了使用反向工程工具生成 的表2 1 中程序对应的调用图。 图2 1 面向过程的结构化程序中源代码与静态调用图和网络拓扑的对应 f 培2 1t h e c o 鹏s p 衄d i n gs 忸1 缸n g 唧h 瓤d t h e t o p o l 0 时n e t w o 出o f t h e u f c o d e j n g 舡1 l c t i 删 畔d l 矾卸r j m t e dp r n 邑即m 咄 而在面向对象的软件系统中，对象和对象之间的交互占据了主导位置，这也使得面 向对象的软件系统其结构更加接近于真实世界。当系统运行时，这些对象根据状态和环 境的变化产生或者消灭，主导或者和协助其他的对象完成任务，其关联程度十分复杂。 对象和对象之间的交互是面向对象系统的动态结构。通过将对象抽象起来，用抽象数据 类型来描述和定义对象的形式和行为，对象在运行时根据抽象数据类型的描述实例化并 参与到计算任务中去。抽象数据类型和他们之间的关系构成了面向对象软件系统的静态 结构。 抽象数据类型在软件开发的发展中根据实际的需要逐渐演化出了许多许多的类型， 在面向对象系统中，典型的抽象数据类型包括：类、接口、结构体、枚举、联合体等， 在高一级的层次上还有包，组件等。这些不同的抽象数据类型通过多种关系组合在一起 在运行时完成复杂的任务。在面向对象系统中，抽象数据类型之间的关系包括：关联、 泛化、依赖和抽象。这些关系之中最常见的是聚合、继承和调用；聚合指一个数据类型 的对象需要持有另外一些数据类型的对象实例；继承关系则是一些数据类型具有另一些 数据类型的特性；调用是最常见的关系，对象的交互很大程度上依赖于调用，一个数据 类型的对象若要调用另外一个数据类型的对象，则调用者对象的抽象数据类型必须知晓 一1 0 一 东北大学硕士学位论文第二章软件静态结构的网络化表示 被调用的数据类型。无论是哪一种关系，都蕴含的同样的含义，即一种抽象数据类型的 工作需要由它所聚合、继承或调用的对象的抽象数据类型来协作。这种协作关系中，责 任者必须依赖于协作者的存在。通常，可以通过源代码找到这些协作关系，在软件设计 和开发过程中经常借助u l l 图来表示抽象数据类型之间的关系。图2 2 左图描述了面 向对象软件系统中借助u 地表示的抽象数据类型协作图的一个示倒。 无论是面向过程的软件系统还是面向对象的软件系统，都可以将其静态结构图中的 程序单元看作是组成网络的个体，将这些程序单元之问的调用、协作看作是这些个体在 网络之中的关系，从而可以将软件的静态结构网络化。图2 1 右图和图2 2 右图分别展 示了这一网络化的过程。 图2 2 面向对象程序中静态类图和网络拓扑的对应 f i g 2 2 1 k c 0 玳s p d i n g 幽函cc l a s sg r a p h 柚dt h et o p o l o g yn 咖0 r l 【o f n 坼8 0 u c o d ei n o b j “炳即把dp i q 驴m m i i n g 2 1 4 软件静态结构网络拓扑 前面的小节已经讨论了网络的定义和软件系统静态结构中的个体和关系，软件系统 可以通过调用图和协作图的方式抽象为由程序单元和单元之间的关系构成的网络拓扑。 这种网络拓扑反映了软件的静态结构特征 【定义2 3 】软件静态结构网络拓扑( s 雠i cs t n l c t u r a l l o p o l o 盱n e 晰o r ko f s o 胁r a m ) ， 对于软件系统s ，三元组g 0 = 称为软件静态结构的网络拓扑，这个三元组包 括：一个顶点集矿限) = v ，i v ，s ，f = 1 ，雄，打2 ) ，其中1 ，是软件系统s 中的抽象数 东北大学硕士学位论文第二章软件静态结构的网络化表示 据类型( 对于面向对象的软件系统) 或者子程序( 对于面向过程的软件系统) ；一个边 集e ( g 。) = 伯，ig ，蜀，= 1 ，辨，朋l ，其中p f 是系统s 中组分之间的关系；和一个关 系厂，这个关系使得每一条边和两个顶点相关联：对于发点和收点分别为v 。v ，的边p ， 有，( 力= ，其中，为关系的类型( 在带权网络中为边权) 。 由上面给出的定义，可以看出软件静态结构的网络拓扑的描述形式是一个带权的有 向图。对应定义2 1 中的网络描述，同样的，在软件静态结构网络拓扑的研究中，忽略 掉关系，中的关系类型，就得到了软件静态结构的有向无权网络拓扑；如果在有向无 权网络中对于边e i 有八q ) = ，同时对于边乞有，( 巳) v ，v ， 的情况下， q = e ：，则得到了软件静态结构的无向无权网络拓扑。 软件静态结构网络拓扑的特征直接反映了软件系统的结构特性，可以基于软件静态 结构网络拓扑利用复杂网络的研究方法获取蕴含在软件系统结构中的信息，从而度量软 件的结构复杂度，指导软件开发。 2 2 软件静态结构网络拓扑中的特征量 2 2 1 度和度分布 度( d e 铲) 是单独节点的属性中简单而又重要的概念。节点v j 的度屯定义为与该 节点连接的其他节点的数目。有向网络中一个节点的度分为出度( o u t d e g r e e ) 和入度 ( n d c g 聆e ) 。节点的出度是指从该节点指向其他节点的边的数目，节点的入度是指从其 他节点指向该节点的边的数目。直观上看，一个节点的度越大就意味着这个节点在某种 意义上对整个网络的影响越大。网络中所有节点的度的平均值称为网络的节点平均度， 记为( 七) 。 网络中节点的度的分布情况可用尸( ) 来描述。p ( 七) 表示的是一个随机选定的节点 的度恰好为七的概率。规则网络有着简单的度序列，因为所有的节点具有相同的度，所 以其度分布为d c 妇分布，它是单个尖峰。完全随机网络的度分布近似于p o i s s 分布， 其形状在远离峰值处呈指数下降，即度值七集中在一定的范围之内，完全随机网络又叫 做均匀网络。然而近年来，大量的研究表明，许多实际网络的度分布明显的不同于p o i s s 分布，特别地，许多网络的度分布符合幂率分布形式p ( 七) a c 七一。幂率分布也成为无尺 度分布，无尺度网络中绝大部分的节点度相对很低，但存在少量的度相对很高的节点。 一1 2 东北大学硕士学住论文第二章软件静态结构的网络化表示 度分布与网络是完全对应的，度分布可以完整地描述网络，网络也只需要用度分布来描 述。n e 煳把它称为“匹配模式”，实质上是研究度值大的节点倾向于和度值大的节 点连接，还是和度值小的节点连接雎3 1 。 。 在软件静态结构网络拓扑中，对应网络中的概念可以借用如下的定义。 【定义2 4 】度( 节点度) ：在软件静态结构网络无向拓扑图瓯= 中，顶 点v 的度d 。是指与此顶点1 ，连接的边的数量，v 矿。即： d ，= 万，” ( 2 1 ) 其中6 i 记号取值为1 ，当厂( ，) = 时，有v = x 或v = y ，否则为零，即： 巧：nt 雌朋 ( 2 2 ) 【q 矿疗d 在有向网络中，同样使用2 1 式，当y = z 时，群记号取值为l ，否则为零，可以 得到顶点v 的出度；当v = y 时，6 i 记号取值为1 ，否则为零，可以得到顶点v 的入度。 “出度加1 ”即该节点代表的软件模块拥有一个对其他模块的依赖，而“入度加l ”则 表示该节点代表的软件模块被一个其他模块所依赖。例如对于两个类彳和矗，若4 是b 的子类，则4 和口之阃有一条有向边由彳指向b ，爿拥有一个出度，b 拥有一个入度。 【定义2 5 】边的度分布相关性：通过网络g 埘的任意一条边f 眠，有 ，( ，) v | ，y 2 ，进而得到两个度值d 。，d 。，通过网络所有边就可以得到两个序列，序 列的相关性即得到一种度分布的相关性。边的度分布相关性用来度量“匹配模式”。用 来分析何种节点倾向于与何种节点进行连接。 【定义2 6 】节点的度分布相关性：通过有向网络g _ 的任意一个节点v ，v y ( g 0 ) 有 一个出度d 和一个入度d ，。，通过网络的所有节点就可以得到两个序列，反映网络 6 _ 的另一种度分布的相关性。节点的度分布相关性用来度量网络中节点的连接属性。 对于软件系统的静态结构来说，度值反映了重要的程序单元复杂性，度分布的研究 展现了软件静态结构的宏观拓扑特征，同时度相关的度量可以得到更多关于软件是如何 组织的结构信息。 2 2 2 聚集系数 【定义2 7 】群聚性( 聚集系数) ：集聚程度的意义是网络集团化的程度，即考察连 一1 3 一 东北大学硕士学位论文 第二章软件静态结构的网络化表示 接在一起的集团节点各自的近邻之中有多少是共同的近邻。对于每一个顶点 v w ) ，找到其近邻集合n ，记n = in ，i ，中存在的边的数量为， 则有集聚程度， m= 6 淄 ( 2 3 ) c + ：! ( 2 4 ) c ： 对网络中所有顶点的集聚程度的统计分布是描述网络特征的重要几何特征量，其平 均值称为平均聚集系数c 。对应每个节点的度值和聚集系数可以得到一组序列，称为簇 度分布，这一分布表述了网络中的聚集条件特性。 对于平均聚集系数c ，很明显有o c l 。当且仅当网络中所有的节点均为孤立节 点时，c = 0 ，即没有任何连接；当且仅当网络是全局耦合时，c = l ，即网络中任意两 个节点之间都有连接。对于一个含有个节点的完全随机网络，当很大时， c = d ( 1 ) 。而许多实际的大规模网络都有明显的聚集效应，他们的聚集系数尽管小于 1 但却比d ( - 1 ) 要大很多。这意味着实际的网络并不是完全随机的，实际网络中存在着 吸引聚集的因素也有着约束聚集的条件。 在软件系统中，许多不同的模块聚集在一起完成相对复杂的功能，对聚集系数的研 究可以展现出模块集成的相关属性。簇度分布也可以反映模块组织结构的特性，为软件 开发提供指导性度量。 2 2 3 平均路径长度 【定义2 8 】路径长度：网络中任意选取一个节点对v 。，节点u 到节点”的距离 办定义为连接两者的最短路径上的边数。网络的平均路径长度j 定义为任意两个节点之 间距离的平均值：( 其中为网络节点数) d ：可熹忑嘭 ( 2 5 ) 拈莉轳 娌5 网络中任意两个节点之间的距离的最大值称为网络的直径d ，即 d 2 学岛 2 6 ) 网络的平均路径长度也称为网络的特征路径长度。为了便于数学处理，在公式( 2 5 ) 一1 4 一 东北大学硕士学位论文第二章软件静态结构的网络化表示 中包含了节点到自身的距离( 为零) ，如果不考虑节点到自身的距离，准确的算出平均 路径长度则需要在( 2 5 ) 式右端乘以( + 1 ) ( 一1 ) 。在实际计算中，尤其是网络规模 十分庞大的时候这个差别是可以忽略不计的。一个含有n 个节点和m 条边的网络的平 均路径长度可以用时问复杂度为d ( 切v ) 的广度优先搜索算法来确定。但另一方面当网 络规模达到一定数量级之后计算平均路径长度会变得十分缓慢。 近期的研究发现，尽管许多实际复杂网络的规模巨大，但是其平均路径长度与其规 模相比却小的惊人。如果对于固定的网络节点平均度( 七) ，平均路径长度d 的增加速度 至多与网络规模的对数成正比，则网络是具有小世界效应的。 平均路径长度在软件系统结构网络中也是很重要的属性，一个系统的平均路径长度 维持在怎样的一个级别，才不至于破坏程序的可扩展和可维护性。一个大规模的软件系 统如果平均路径长度过长，则可能软件的组织形式就较为松散，软件复用程度不高，软 件功能有限；反之如果一个