Linux内核函数调用关系的复杂网络分析

丁德武

（池州学院 数学与计算机科学系，安徽 池州 247000）

近年来，研究人员发现现实世界中的大多数复杂系统都可以用网络来描述，即：使用节点来表示系统中的元素，使用连线来表示它们之间的关系[1]。在过去的十数年间，众多的复杂网络模型吸引了研究人员浓厚的兴趣，也引领了诸如数学、物理学、生物学和社会学等多个学科领域的快速发展[1-2]。但是，计算机科学特别是软件工程领域的复杂网络研究还处于初期阶段，当前的研究内容主要包括：对软件系统的内部拓扑结构进行实证分析；对软件系统的复杂性进行度量和评估；学习软件系统的形成和演化过程；等等[3-4]。

图1 一个简单的函数调用图

一般地，可以用节点表示大型软件系统中的函数，用连线表示函数之间的调用关系（图1）[5]。这种函数调用图可以用来反映软件系统中函数之间的调用关系，在程序理解、程序分析、软件测试与维护等众多软件工程领域都有着广泛的应用[5]，是该领域的一种重要复杂网络模型[3-4]。本文从复杂网络的角度，使用函数调用图分析了Linux内核的源代码结构，完成了对其内部重要拓扑结构特征的实证分析，同时也使用几种主流的中心化分析方法考察了其中的关键函数。

1 Linux内核函数调用图

我们首先获取了一个Linux内核源码，随后以节点表示函数，节点间的连线表示函数之间的调用关系，构造了Linux内核的函数调用图，该模型包含了12390个节点和 33553条连线[6]。随后，我们依据复杂网络的蝴蝶结结构特征，将Linux内核的函数调用图分解成如下4个部分：巨强连通体，底物子集，产物子集和孤立子集。……