基于复杂网络的操作系统演化与结构稳定性研究

Many empirical studies have shown that the topologies of large-scale software systems exhibit complex network features such as "small world"' and "scale-free". In this project, we combine the complex network and software evolution theories to accomplish four tasks: First, we explore the formation mechanism and evolution law of complex network in an operating system (OS) by studying the topology of the OS and constructing an evolution model for it under the "generative theory". Second, we build a software structure stability evaluation model base on the evolution model of the OS. The evaluation combines insights from static (various features of complex network) and dynamic (laws of code change propagation) analysis. Third, we study the quantitative relationship between complex network features, code change propagation, and software structure stability to identify inherent patterns and their formation mechanisms, which impact structure stability in the evolution. Last, we analyze the "ripple effect" in code change propagation under the percolation theory to study critical states and its prediction methods for structural stability in the evolution of the OS. This project will contribute to a scientific and comprehensive understanding of the nature of software evolutions as well as provide a reliable basis for future optimization of software systems.

大量实证研究表明，大型软件的内部拓扑结构具有"小世界"和"无标度"等复杂网络特征，本项目将复杂网络理论与软件演化研究相结合，进行以下研究：1）以操作系统的内部拓扑结构为研究对象，探索操作系统中复杂网络的形成机理和演化规律，从"生成论"的角度提出适于操作系统的演化模型；2）以操作系统演化模型为基础，综合静态（复杂网络的各种特征值）和动态（代码变更传播规律）两方面因素，提出一个软件结构稳定性评估模型；3）研究复杂网络特征、代码变更传播与软件结构稳定性的量化关系，发现演化过程中影响结构稳定性的内在模式及其形成机理；4）结合"渗透理论"，分析代码变更传播的"雪崩效应"，研究在操作系统演化过程中结构稳定性的临界状态及其预测方法。本项目的研究有助于科学、全面地认识软件演化的本质规律，为将来软件系统的优化提供可靠依据。

本课题将复杂网络理论与软件演化研究相结合，探索软件系统中复杂网络的形成机理和演化规律，以及代码变更传播与软件结构的关系。主要完成以下科研成果：..1. 基于Linux函数调用图，计算了操作系统函数调用网络结构的特征。通过对函数调用图中出入度分布不对称性的分析，我们发现函数之间基于度和年龄的偏好依附是形成操作系统网络特征的关键，该项发现更合理地解释了软件网络的形成和演化机理。以此为基础，我们提出了基于函数年龄的αβ演化模型，很好地模拟了Linux操作系统的演化过程。同时，我们对操作系统中函数生命周期进行了分析，发现其符合指数分布。这些工作为操作系统演化的预测奠定了良好的基础。.2. 为了量化分析代码变更传播与软件结构的关系，我们提出了边的不稳定性和传播范围等概念，并发现软件网络的特征与经典的BA、ER模型有很大区别。通过对这些软件网络数据的分析，我们发现聚类系数和边的不稳定性对函数变更传播有重大影响，并设计了一个能够调节聚类系数和边的不稳定性的模型。该模型展示，在同等条件下边的不稳定性对变更传播的影响要超过聚类系数，因此边的不稳定性更深刻地描述了影响变更传播的网络结构特征。.3. 受网络鲁棒性研究的启发，我们定义了新的软件鲁棒性概念。对软件网络应用了边的度、边的不稳定性、随机等三种移除策略，研究了在不同移除策略下的软件鲁棒性。通过研究发现，边的不稳定性对软件鲁棒性的影响要远大于其他两种策略。在我们将这项成果应用于一些社交网络时发现它同样有效。.4. 由于涉及大量数据处理工作，本课题还对文件系统、Key-value存储系统和操作系统的噪声等方面进行了优化。..截止2016年12月，已发表论文16篇。在国内外重要期刊已发表SCI检索论文3篇，平均影响因子大于1.213（最高1.785，最低0.66）；另发表EI索引的论文8篇（包括CCF-B类、C类会议论文各1篇）；申请3项发明专利和1项软件著作权。此外，还有2篇论文准备向CCF-A类的重要期刊和会议投出。