● 摘要
经过几十年的发展，计算机软件开发方法经历了面向过程、面向对象、面向方面以及面向服务等多个阶段。现在大规模复杂软件系统广泛应用于工业、农业、军事、科研等有关国计民生的重要领域之中，然而在1969 年提出的软件危机直到今日仍未解决，超出预算和项目延期仍然是困扰软件公司的头等难题。软件的生命周期中包括需求、设计、开发、测试以及维护等多个阶段，随着软件项目为方便组织开发不断采用的自动化工具越来越多（如需求管理工具、软件配置管理工具、缺陷追踪管理工具等），软件在开发过程中被记录的数据和信息也在不断增加。以著名的开源项目GCC、Linux为例，在其代码版本管理系统和缺陷追踪系统中记录了超过十年的历史记录，随着开源软件运动的蓬勃发展，研究者可以从互联网上获取大量开源软件开发过程中记录的数据，因此如何分析这些历史数据并将它用于指导今后的软件开发成为软件工程领域中的一个热点问题。近年来，研究者们发现大规模复杂软件系统的静态结构图都具有小世界、高簇系数以及度分布为幂律分布等典型的复杂网络特征。由于网络的分布为幂律分布，他们还基于优先选择策略提出了一些无标度网络演化模型。但是这些模型并没有考虑软件系统的历史变化数据，因此模拟生成的结果与实际网络不能较好的吻合。本文将主要研究如何基于软件变化历史和复杂网络理论建立软件静态结构网络的演化模型，同时还将研究软件结构网络的可视化以辅助理解结构网络的演化过程。代码版本管理工具记录了软件系统所有的历史变化信息，我们可以从中取出软件系统任何时刻的源代码，那么从这些历史变化信息中我们能否总结出一些规律来描述软件演化的过程，进而建立软件演化的模型来预测和控制软件的演化趋势呢？本文重点研究了软件静态结构的变化规律，我们通过将代码中类、接口、函数等软件实体抽象为节点而它们之间的关系抽象为边建立了一个网络结构。在此基础上本文从一个新的视角-软件静态结构网络来研究软件系统的变化规律，我们首先分析代码管理系统中代码文件变化的原始记录，并通过分析文件版本之间的语法树差异，得到这些差异对软件结构网络的影响。这一步中得到结构网络变化历史主要用于基于演化网络序列进行分析和建模。然后，本文通过分析软件结构网络在演化过程中度分布、基本统计特征、结构复杂度以及Motif显著程度的变化规律建立了软件结构网络演化模型。最后，提出了嵌套类图层次化自动布图算法以支持软件结构网络可视化展现。下面列出了本文主要的贡献和创新：1. 发现了软件结构网络中新节点连线和随机边选择端点的策略服从亚线性优先选择策略，提出了基于亚线性优先选择策略的随机优选演化模型，同时解析地推导了该模型生成的度分布结果；2. 提出了基于度信息熵的网络结构复杂度度量和并行Motif 识别算法，发现了在演化过程中软件结构网络Motif 特性所呈现出的与BA 无标度网络完全不同的变化趋势（在均值附近震荡变化）；3. 提出了一种基于层次化框架的嵌套类图自动布图算法，它主要用于软件结构网络的可视化；4. 为支持连续版本代码文件之间的语法树差异分析，设计了模糊程序分析策略，并提出了基于滑动时间窗口的软件变化事务提取算法。各项实验结果表明，文中设计的演化数据处理方法和策略具有效率高、稳定性好的优点；而软件结构网络演化模型与实际软件结构网络演化序列契合性良好，其中模型生成的终态网络度分布的模拟结果与解析结果具有很高的一致性。因此，本文提出的方法和模型对于进一步深入开展软件演化分析与建模方面的研究有较为重要的参考价值。