第6卷第3期 智能系统学报 Vol.6 No.3 2011年6月 CAAI Transactions on Intelligent Systems Jun.2011 doi:10.3969/i.issn.1673-4785.2011.03.003 基于复杂网络的软件结构度量方法综述 孙世温2，夏承遗12，王莉12 (1.天津理工大学计算机与通信工程学院，天津300191；2.天津理工大学天津市智能计算及软件新技术重点实验 室，天津300191) 摘要：计算机软件复杂性与软件质量、开发成本和生产效率等密切相关，软件复杂性的度量和控制是计算机科学 的挑战性问题之一，近年来复杂网络研究的兴起为研究软件系统结构复杂性提供了新的理论、方法和工具，该方法 克服了传统软件结构度量方法侧重微观统计、缺乏全局性和整体性等缺点，构成了复杂网络与传统软件工程的交叉 研究领域.对该领域的研究工作进展进行了介绍，从软件网络结构特征分析、建模以及研究成果的初步应用3个方 面总结已有工作，并对今后有意义的研究方向进行了展望，如基于加权模型的软件网络建模、软件网络动态演化机 制等， 关键词：复杂网络；软件结构复杂性；软件度量；建模 中图分类号：TP311.5文献标识码：A文章编号：16734785(2011)03020805 Survey of the measurement of software structures based on complex networks SUN Shiwen'2,XIA Chengyi2,WANG Li.2 (1.School of Computer and Communication Engineering,Tianjin University of Technology,Tianjin 300191,China;2.Tianjin Key La- boratory of Intelligence Computing and Novel Software Technology,Tianjin University of Technology,Tianjin 300191,China) Abstract:Software complexity is closely related to software quality,development cost,and development efficiency. Thus the measurement and control of software structural complexity is one of the most challenging problems in com- puter science.Recently,the research of complex networks has been providing new theories,methods,and tools for the study of software structural complexity,and overcoming some shortcomings of traditional measurement methods, such as only focusing on the microstructures and a lack of structural integrality,which results in the interdisciplinar- y field of complex network and traditional software engineering.In this paper,the following aspects of the research work in this new area were summarized and reviewed:topological structure analysis,network modeling,and the ap- plication of complexity controls and structural optimization.A perspective for meaningful future research emphasis was given including aspects such as network modeling based on weighted models and dynamical evolving mechanism of software systems. Keywords:complex network;software structural complexity;software metrics;modeling 现代计算机软件系统的复杂程度越来越高，越复效应”.大型软件系统由无数细节构成，一个极小的错 杂的软件就越难以保证其产品质量、开发成本和生产 误就可能引发灾难性后果.因此，如何认识、度量、管 效率，软件开发极易处于失控状态，甚至形成“雪崩 理和控制软件复杂性已成为软件工程领域中极其重 要且极具挑战性的问题.对软件结构复杂性度量和评 收稿日期：2010-03-30. 估的前提是需要对软件结构（信息）进行合理描述和 基金项目：国家自然科学基金资助项目(60904063)；天津市应用基础 及前沿技术研究计划资助项目(11 JCYBJC06600);中国博 有效量化12.传统软件度量方法35注重从单一模块 土后研究基金资助项目(20090460694)：天津市高等学校 出发，忽略了软件系统结构的整体性，侧重微观上的 科技发展基金资助项目(20090717,20090811,20090813)； 统计，缺乏全局和整体上对软件结构的度量；而计算 国家大学生创新性实验计划资助项目(091006007， 101006019). 机软件作为一类复杂系统，系统（拓扑）结构必然会 通信作者：孙世温.E-mail:sunsw80@gmail.com 影响其功能、性能和质量等.近年来，复杂网络研究取
第3期 孙世温，等：基于复杂网络的软件结构度量方法综述 ·209· 得了相当大的进展61，其理论、技术、方法和成果为 一些计算公式，包括：程序容量V=W×b(n1+ 从整体和全局角度研究软件系统结构和行为复杂性 n2)、程序级别L=(2/n1)(n2/N2)、编制程序所用 提供了新的工具， 工作量E=V/L、程序中错误数预测值B=N× 按照软件工程的观点，在不同粒度上，计算机软 b(n1+2)/3000等. 件是由多个功能实体（类、对象、方法、函数、子程序 Halstead度量实际上只考虑了程序的数据流而 等)相互关联、共同作用构成的一类复杂系统；从网 没有考虑程序的控制流，因而不能从根本上反映出 络化的角度，实体映射为节点，实体间存在某种联系 程序的复杂性。 映射为相应节点的连接边，软件系统的结构可以通 1.3C&K度量 过网络模型进行描述和刻画.应用复杂网络研究领 1994年Chidanber和Kemerer阐述了面向对象 域的理论、技术和方法，从整体和全局的角度来探索 软件度量学的理论基础，提出了基于继承树的面向 软件系统的结构和行为特性，弥补了传统软件度量 对象度量方法（简称为C&K度量方法）4，包括6 技术的欠缺，构成了复杂网络和软件工程的交叉研 个度量指标：1)类的加权方法数；2)继承树的深度， 究领域（以下简称为“复杂软件网络”）. 若为多重继承则计算从节点到树根的最大深度；3) 本文着眼于复杂网络方法在软件结构复杂性度 子类数目，即一个类的直接子类数目；4)对象间耦 量方面的应用，在概述和分析几种传统度量方法的 合程度，当一个类使用其他类的成员变量或方法 基础上，从软件系统网络化特征分析、软件网络建 时，则称这2个类是耦合的：5)类的响应个数，即为 模、研究成果应用3个方面简要阐述了国内外在复 类中所有方法所调用的类外方法的总数目：6)类方 杂软件网络领域的一些主要研究工作，并尝试对该 法中内聚缺乏度 领域的研究热点和难点进行了归纳和总结。 1.4M00D方法 1995年Bito提出的MO0D方法间接度量了面 1传统的软件结构度量方法 向对象软件的封装性、继承性、耦合性和多态性5] 传统软件结构度量方法包括基于控制流的Mc 包括：1)封装性：方法隐藏因子、属性隐藏因子分别 Cabe环复杂度度量3]、基于程序体积的Halstead方法、 度量隐含方法数、属性数相对于方法总数、属性总数 面向对像软件的C&K度量4]、MOOD方法5]等 的比例；2)继承性：方法继承因子和属性继承因子 l.1 MeCabe环复杂度 分别度量直接继承的方法数、属性数相对于方法总 McCabe度量方法[3]根据图论和程序结构控制 数、属性总数的比例；3)耦合性：耦合因子是对系统 理论，把程序结构的控制流程图转化为有向图（即 中所有成类对间的关联程度大小的度量；4)多态 程序图)，然后将强连通有向图的环数作为程序结 性：多态性因子表示重载方法数相对于新方法总数 构的环形复杂度V(G)=m-n+1,其中m和n分 的比例 别为有向图G中的弧数和节点数，V(G)还等于程序 上述几种传统度量方法从不同侧面描述了软件 图中判定结点的数目加1. 结构的复杂性，但偏重于分析软件系统中功能个体 McCabe度量方法的计算过程表明程序复杂性 (类、过程、方法等)的性质和局部结构，因而缺乏全 很大程度上取决于程序结构控制流的复杂性.环形 局和整体上对软件结构的度量 复杂度高的程序往往是最容易出现错误的程序，实 践表明程序规模以V(G)≤10为宜. 2复杂网络概述 l.2 Halstead方法 20世纪90年代以来，借助于计算机运算能力 Halstead方法通过计算程序中运算符和操作数 的增强以及数据存储、处理技术的快速发展，科学家 的数目对程序复杂性加以度量.设1为程序中不同 将现实世界中复杂系统的结构进行网络化处理，将 运算符的数目，2为程序中不同操作数数目，N1为 系统中的个体抽象为网络的节点，个体间存在的相 程序中运算数总数，N2为程序中操作符总数，令H 互联系和作用视为节点间存在连边.研究发现许多 和N分别表示程序的预测长度和实际长度，Hl- 真实存在的复杂系统都具有，以小的节点间距和高 stead给出计算公式： 的节点聚集程度为特征的小世界效应(small- H=n1×lbn1+n2×lbn2, world)[6]和以节点度分布服从幂律为特征的无标度 N=N1+N2: 特性(scale---free)[).小世界和无标度的发现促成了 Halstead的重要结论之一是程序的实际长度与 复杂网络这一新的研究领域的产生，此后物理、生 预测长度非常接近，即使程序还未编写完成也能估 物、数学、计算机、经济、管理、金融学等不同学科领 算出程序的实际长度.Halstead方法还给出了另外 域的研究者都着重关注复杂系统的拓扑连接结构与
210 智能系统学报 第6卷 系统功能及动力学性质之间的相互作用和影 匀、度分布“胖尾”、权分布服从幂律、“强强联合”效 响8101 应等特征. 3 3.2软件网络建模研究 基于复杂网络的软件结构 软件网络建模是在分析真实网络特征和捕捉网 基于复杂网络的软件结构模型用形式化的方法 络特征形成机制基础上，建立数学模型和算法，揭示 来描述软件系统中实体之间的关系，具有良好的数 软件系统中网络特征的形成机理和演化规律， 学基础，为从系统整体上分析软件结构的复杂性提 复杂网络领域中建模研究成果对构建软件网络 供了新的思路，能够得到由软件系统中单个个体的 演化模型具有借鉴意义.Watts和Strogztz提出了著 性质累加所无法得到的整体性质.国内外研究者在 名的小世界模型6，通过在规则网络中按照一定概 复杂软件网络领域的研究工作大致可以分为3类， 率添加长程边解释了“小世界”的产生原因； 分别是软件系统网络化结构特征分析、基于建模的 Barabasi和Albert在揭示Internet和万维网中度分 网络特征形成机理和演化规律研究，以及研究成果 布服从幂律这一重大发现后，提出了著名的无标度 在软件复杂性控制、结构优化等方面的应用. 模型)，揭示无标度特性的出现取决于2点—网 3.1软件系统网络化结构特征分析 络的动态增长（新节点加入）和边择优连接，即新加 Valverde等人四将面向对象软件中类及类间 入的节点依概率倾向于与连接边多的节点相连.在 的继承、关联等关系映射为无向网络，发现类网络表 BA模型的基础上研究人员对无标度的产生机制进 现出无标度和小世界特征，无标度特性表明软件系 了一系列深入探索，如考虑初始吸引度、非线性择优 统中各个模块间不是毫无规律地随机连接，系统中 连接、择优连接更迭、增长制约条件、增长方式及局 存在少量连接度极高的类，因而这些类耦合程度较 部作用等[810 高，小世界特征表明节点平均间距较小且节点聚集 考虑软件网络的演化特性，文献[20,23]认为软 程度较高.通过赋予边方向特性，Myes21基于有向 件网络中无标度特性的出现也归因于软件本身的进化 网络模型对类网络进行连通特性、出度入度匹配关 及进化过程中存在的“择优连接”机制，即软件网络中 系、层次结构等方面的深入研究，发现节点出度和人 存在着关键个体（模块、类、对象、函数等），新个体添加 度分布都服从幂律，且两者具有负相关性，即出度小 到系统时往往倾向于和这些关键个体连接， 的节点通常入度较大，文献从“模块复用”角度给出 Valverde等人[4]认为全局性约束和设计优化， 了解释：出度小的类很少依赖其他类，较为简单且被 即以较小代价（较短的平均最短路径）获得可靠的 重用的次数多的类其人度就可能较大， 节点间通信是软件系统展现出“小世界”特性的主 Shi等人[]首次分析了类网络的演化性，即随 要因素，在此基础上，Valverde等人还提出了一个基 着开发时间或版本变更软件系统中网络结构特征的 于复制和分岔规则的软件演化模型2]，发现软件网 变化规律.韩明畅等人[4、陈焘等人[s]对Java类库 络的生长遵循某种对数规律（如系统的总边数、平 中类以及类关系的研究，进一步验证了类网络中小 均度随时间变化呈对数增长) 世界和无标度规律的普适性.Ma等人[16提出了一 Myes等人121认为软件系统中的优先连接实质 个复合度量模型，从代码级、类级和系统级3个层面 上是一种软件重用机制，节点的入度越大表明其重 给出面向对象软件系统的度量.Concas等人[n]发现 用率越高，通过有效的重用能形成度很大的中枢节 面向对象属性分布符合幂律，且网络结构存在自相 点，从而有利于节点间的通信.He等人提出了基 似、分形等特点[18] 于模式冷冻的生长算法，为研究软件系统的演化规 此外，Challet等人[]利用有向网络，描述了 律提供了新的思路和方法.李兵等人[1则提出了一 Redhat8.O源代码中包的关联关系和函数间调用关 种生长的网络演化模型CN-EM,借鉴了遗传算法中 系，统计了网络入度和出度分布、出度入度关联等特 的交叉、变异等演化算法，通过对比性分析显示模型 征，并最早将复杂网络传播动力学的思想引入到软 网络等能较好地刻画实际软件系统中复杂网络特性 件缺陷传播研究中.Lai等人[20采用无权网络刻画 出现的演化过程， 了开源软件中源代码文件间的引用关系，发现了软 3.3研究成果应用 件网络中的小世界和无标度特征.笔者2122]对 将软件网络特征分析和度量结果付诸软件工程 Linux kernel源代码进行解析，提出一种基于依赖关 实践，探讨在软件复杂性控制、质量预测、结构设计 系密切程度的权值表征方法，构建了2类加权网络 优化等方面的应用研究也得到不少学者的关注.Va- 模型(HFCN-I和HFCN-Ⅱ)来刻画功能模块（头文 a等人[9]根据网络边数和节点数之间的关系研 件)的依赖关系，发现网络具有小世界、连接极不均 究结构稳定性变化，从而预测软件规模和开发成本；
第3期 孙世温，等：基于复杂网络的软件结构度量方法综述 211· Girolamo等人[3o根据介数等指标在类层、网络层和 低开发风险和成本、进行早期软件质量预测、制定正 设计层中识别和检测软件结构缺陷以及隐患类，进 确测试策略等提供科学的理论依据.总之，基于复杂 行软件质量预测；Melton等人[311发现类间形成依赖 网络的软件结构复杂性研究是一个非常有实用价值 环会导致系统复杂度增加、稳定性降低；Ma等人[m1 的研究方向，并且有待进一步深入 发现网络中重要子图结构都较稳定且没有环出现， 参考文献： 从2个不同的角度验证了“避免环产生”这一结构 设计准则的合理性 [1]杨芙清.软件工程技术发展思索[J].软件学报，2005， 针对软件复杂性问题，基于复杂网络的研究方 16(1):1-7. 法及目前取得的研究成果不仅丰富了对软件系统结 YANG Fuging.Thinking on the development of software en- 构复杂性特征的刻画，更为控制软件系统复杂性，指 gineering technology J].Journal of Software,2005,16 (1):1-7. 导软件结构设计等提供了一个新的研究途径，对于 [2]NORMAN E F,SHARI L P.Software metrics M].2nd 复杂软件体系结构优化、软件质量提高等方面都具 ed.Beijing:China Machine Press,2003:5-10. 有重要的现实意义 [3]MCCABE T J.A complexity measurement[J].IEEE Trans- action on Software Engineering,1976,2(4):302-308. 结论 [4]CHIDAMER S R,KEMERER C F.A metrics suite for ob- ject-oriented design[J].IEEE Transactions on Software En- 目前，复杂软件网络领域的研究还处于初期探 gineering,1994,20(6):476493. 索阶段，要最终形成成熟的应用技术还需要大量更 [5]ABREU F B E.The MOOD metrics set[C]//Proceedings 具创新性的细致和完善的工作.展望未来，复杂网络 of ECOOP'95 Workshop on Metrics.Aarhus,Denmark, 理论和方法在计算机软件系统中的研究和应用需要 1995:150-152. 更好地结合软件系统本身的特点，建立更适合软件 [6]WATTS D J,STROGATZ S H.Collective dynamics of small 系统的网络模型。 world networks[J].Nature,1998,393(6684):440-442. 1)基于网络模型的软件系统拓扑结构分析发 [7]BARABASI A L,ALBERT R.Emergence of scaling in ran- 现了传统软件度量方法所忽略的结构特征，但由于 dom networks[J].Science,1999,286(5439):509-512. [8]BOCCALETTIA S,LATORAB V,MORENOD Y,et al. 上述研究均采用无权网络，不能体现软件系统中个 Complex networks:structure and dynamics J].Physics 体间交互作用的强度与差异对系统的影响：因此将 Reports,2006,424(4/5):175-308. 度量要素以权重的形式赋予节点和边，建立加权网 [9]WANG Xiaofan,CHEN Guanrong.Complex networks: 络模型，将会更加全面细致地刻画软件系统的结构 small-world scale-free and beyond J].IEEE Circuit Sys- 和行为.另外，如何将传统的软件度量方法和基于网 tem Magazine,2003,3(1):6-20. 络模型的软件结构分析相结合，并分析不同度量指 [10]陈关荣.复杂网络及其新近研究进展简介[J].力学进 标之间的内在联系等问题也有待深入研究。 展，2008,38(6)：653662. 2)已有软件网络建模研究借鉴了一般复杂网 CHEN Guanrong.Introduction to complex networks and 络的演化机制（如“节点新增”、“边择优连接”等）， their recent advances[J].Advances in Mechanics,2008, 探求了软件网络中静态拓扑结构特征（小世界、无 38(6):653-662. [11]VALERDE S,CANCHO R F,SOL R V.Scale-free net- 标度等)的形成机理；但软件作为一种人工设计和 works from optimal design[J].Europhysics Letters,2002 开发的智能化产物，软件设计开发技术和方法（如 60(4):512517. 面向对象原则、代码重构技术等)的应用是软件系 [12]MYERS C.Software systems as complex networks:struc- 统结构自身不断演化的重要原因之一，而现有的演 ture,function,and evolvability of software collaboration 化模型在这方面没有深入考虑.由此在进一步的研 graphs[J].Physical Review E,2003,68(4):046116. 究中要着眼于分析软件设计开发技术和方法对软件 [13 ]SHI Mingjiang,LI Xiang,WANG Xiaofan.Evolving topol- 系统局部结构的作用，探索局部规则作用下如何产 ogy of Java networks[C]//Proceedings of 6th World Con- 生软件网络整体特征的涌现。 gress Control on and Automation.Dalian,China,2006, 1:2123. 在“软件的网络观”得到计算机科学领域研究 [14]韩明畅，李德毅，刘常昱，等.软件中的网络化特征及其 者认可和日渐重视的背景下，笔者有理由坚信复杂 对软件质量的贡献[J],计算机工程与应用，2006 网络与计算机软件工程的交叉研究将有助于更加客 (20):29-31. 观全面地定量评估软件结构，在软件产品的设计、开 HAN Mingchang,LI Deyi,LIU Changyu,et al.Net- 发、测试和维护等阶段，能够为实施复杂性控制、降 worked characteristic in software and its contribution to
212. 智能系统学报 第6卷 software quality[J].Computer Engineering and Applica- [27]李兵，王浩，李增扬，等.基于复杂网络的软件复杂性度 tion,2006(20):29-31. 量研究[J].电子学报，2006,34(12A):2371-2375. [15]陈焘，李孔文，王树森，等.基于复杂网络的Java程序分 LI Bing,WANG Hao,LI Zengyang,et al.Software com- 析工具设计与实现[J].计算机科学，2009,36(4)： plexity metrics based on complex networks[J].Acta Elec- 145-150. tronica Sinica,2006,34(12A):2371-2375. CHEN Tao,LI Kongwen,WANG Shusen,et al.Design [28]VASA R,SCHNEIDER J G,WOODWARD C,et al.De- and implementation of a tool of Java program analysis based tecting structural changes in object oriented software sys- on complex networks[J].Computer Science,2009,36 tems C]//Proceedings of International Symposium on (4):145-150. Empirical Software Engineering.Noosa Heads,Australia, [16]MA Yutao,HE Keqing,DU Dehui,et al.A complexity 2005:479486. metrics set for large-scale object-oriented software systems [29]VASA R,SCHNEIDER J G,NIERSTRASZ O.The inevi- [C]//Proceedings of 6th IEEE International Conference on table stability of software change[C]/Proceedings of 23nd Computer and Information Technology.Seoul,Korea, IEEE International Conference on Software Maintenance. 2006:189-194. Paris,France:IEEE Press,2007:4-13. [17]CONCAS G,MARCHESI M,PINNA S,et al.On the [30]GIROLAMO A,NEWMAN L I,RAO R.The structure suitability of Yule process to stochastically model some and behavior of class networks in object-oriented software properties of object-oriented systems [J].Physica A, design[EB/OL].[2010-03-15].www.eecs.umich.edu/ 2006,370(2):817-831. eenewm/documents/classnetworks. [18]CONCAS G,LOCCI M F,MARCHESI M,et al.Fractal [31]MELTON H,TEMPERO E.Static members and cycles in dimension in software networks[J].Europhysics Letters, Java software[C]//Proceedings of 1st International Sympo- 2006,76(6):1221-1227. sium on Empirical Software Engineering and Measurement. [19]CHALLET D,LOMBARDONI A.Bug propagation and de- Madrid,Spain,2007:136-145. bugging in asymmetric software structures [J].Physical [32]MA Yutao,HE Keqing,LIU Jing.Network motifs in ob- Review E,2004,70(4):046109. ject-oriented software systems[J].Dynamics of Continu- [20]MOURA A,LAI Yingcheng,MOTTER A E.Signatures of ous,Discrete and Impulsive Systems Series B:Applica- small world and scale-free properties in large computer pro- tions and Algorithms,2007,14(S6):166-172. grams[J].Physical Review E,2003,68(1):017102. 作者简介： [21 SUN Shiwen,LIU Zhongxin,CHEN Zengqiang,et al. 孙世温，女，1980年生，讲师，博士， Header file collaboration networks:weight,topology and 主要研究方向为复杂动态网络、网络鲁 statistical properties[J].Dynamics of Continuous,Dis- 棒性、软件工程.目前主持天津市高等 crete and Impulsive Systems Series B:Applications Al- 学校科技发展基金项目1项，发表学术 gorithms,2007,14(S6):142-147. 论文近10篇，其中被SCI检索3篇、E 22]SUN Shiwen,XIA Chengyi,CHEN Zhenhai,et al.Gener- 检索4篇。 alized collaboration networks in software systems:a case study of Linux kernels[J].Frontiers of Computer Science 夏承遗，男，1976年生，副教授，博 in China,2009,3(3):421426. 士，主要研究方向为复杂系统与复杂网 [23]间栋，祁国宁.大规模软件系统的无标度特性与演化模 络建模与分析、传播动力学.目前主持 型[J].物理学报，2006,55(8)：3799-3804. 国家自然科学基金项目1项、天津市应 YAN Dong,QI Guoning.The scale-free feature and evol- 用基础及前沿技术研究计划项目1项、 ving model of large-scale software systems[].Acta Phys- 中国博士后研究基金项目1项、天津市 ica Sinica,2006,55(8):3799-3804. 高等学校科技发展基金项目1项.发表学术论文10余篇，其 [24]VALVERDE S,SOLE R V.Hierarchical small worlds in 中被SCI检索3篇、EI检索6篇. software architecture EB/OL].[2010-03-15 ]http:// arxiv.org/abs/cond-mat/0307278. 王莉，女，1979年生，讲师，博士，主 [25]VALVERDE S,SOLE R V.Logarithmic growth dynamics 要研究方向为复杂网络、多智能体系统 in software networks[J].Europhysics Letters,2005,72 的协调与控制.目前主持天津市高等学 (5):858864. 校科技发展基金项目1项.发表学术论 [26]HE Keqing,PENG Rong,LIU Jing,et al.Design meth- 文近10篇，其中被SC检索1篇、EI检 odology of networked software evolution growth based on 索3篇. software patterns[].Joumal of Systems Science and Com- plexity,2006,19(2):157-181