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

丁德武

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

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

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

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

1 Linux内核函数调用图

我们首先获取了一个Linux内核源码，随后以节点表示函数，节点间的连线表示函数之间的调用关系，构造了Linux内核的函数调用图，该模型包含了12390个节点和 33553条连线[6]。随后，我们依据复杂网络的蝴蝶结结构特征，将Linux内核的函数调用图分解成如下4个部分：巨强连通体，底物子集，产物子集和孤立子集。考虑到复杂网络的巨强连通体部分是网络中最大的强连通分支，它决定了整个复杂网络的拓扑结构特征；同时，为了使问题简化，文章主要考察Linux内核的函数调用图的巨强连通体部分，该部分包含了637个节点和1415 条连线（图 2）。

图2 Linux内核函数调用图的巨强连通体部分

2 复杂网络分析

2.1 重要结构特征

我们首先分析了Linux内核函数调用图的巨强连通体部分的两个重要结构特征：

（1）小世界性质，即网络的平均路径长度较小[7]。我们计算了该部分所有可达节点间的路径长度（图3），随后计算出该网络的平均路径长度，结果为21。可见尽管网络规模非常大，但是网络的可达节点间的平均路径长度较小，因此该网络是一种特殊的小世界网络。

图3 Linux内核函数调用图的巨强连通体部分的路径长度分布图

（2）无尺度性质，即节点的度分布P(k)遵循函数P(k)=ak-r(a>0，r>0)[7]。为了分析Linux内核函数调用图的巨强连通体部分的度分布情况，我们首先统计了网络中各节点的连接度（入度，出度，和总的度）。然后，根据这些数据，绘制出了网络度分布的log-log图（图4）。得到的网络连接度分布符合幂律分布，表明这些网络均具有比较明显的无尺度特性，是无尺度网络。

图4 Linux内核函数调用图的巨强连通体部分的度分布图

3.2 关键函数分析

一般地，复杂网络中的关键元素可以通过网络的中心化分析得到。这里，复杂网络中节点的中心化程度主要是指依据一定原则为其分配的一个函数。当前已经提出多种中心化分析方法，例如：度中心化分析指标用网络中每个节点的连线数来确定节点的重要程度，介数中心化分析指标用通过某节点的最短路径数量来确定节点的重要程度，而紧密度中心化分析指标可用于识别网络的核心和外围部分，等等[8]。但是，研究表明单一的中心化分析指标往往是不太可靠的，需要综合考虑多种中心化分析指标。这里，我们以度、介数和紧密度中心化分析指标考察了Linux内核函数调用图的巨强连通体部分的关键节点，并综合加以分析。

依据度中心化分析指标（这里是总的度，表1给出了入度与出度的结果），排在前20位的关键函数 是 ：printk，warn_on_slowpath，kmem_cache_free，put_page，kfree，kmem_cache_alloc，do_exit，do_filp_open，_cond_resched，__alloc_pages_internal，dput， futex_lock_pi， schedule， mntput_no_expire，audit_log_exit，mutex_unlock，up_read，wake_up_process，handle_mm_fault和 mutex_lock.

表1 Linux内核函数调用图的巨强连通体部分的入度与出度中心化

依据介数中心化分析指标（图5），排在前20位的关键函数是：schedule，math_state_restore，__switch_to，do_group_exit，do_exit，__alloc_pages_internal，cache_grow，cache_alloc_refill，kmem_getpages，kmem_cache_alloc，group_send_sig_info，check_kill_permission，__audit_signal_info，send_sigio，send_sigio_to_task，print_oops_end_marker，extract_entropy，kill_fasync，get_random_bytes 和__kill_fasync.

图5 Linux内核函数调用图的巨强连通体部分的介数中心化

依据紧密度中心化分析指标（图6），排在前20位 的 关 键 函 数 是 ：do_exit，do_group_exit，math_state_restore，exit_mm，futex_wait，do_futex，futex_lock_pi，__switch_to，do_filp_open，schedule，get_user_pages， handle_mm_fault， sys_futex，rwsem_down_failed_common， audit_log_exit，__link_path_walk， audit_free， rt_mutex_slowlock，ptrace_stop和 filp_open。

图6 Linux内核函数调用图的巨强连通体部分的紧密度中心化

显然，不同的中心化指标确定的关键节点是不同的，我们从中选出最少有两种中心化指标同时确定其为关键节点的函数，它们是：do_exit，schedule，__alloc_pages_internal，__switch_to，audit_log_exit，do_filp_open，do_group_exit，futex_lock_pi，handle_mm_fault，kmem_cache_alloc 和 math_state_restore.

3 小结

当前，复杂网络已经被成功应用于数学、物理学、生物学和社会学等多个学科领域[1-2]。本文考察了复杂网络在软件工程领域的应用[3-4]。我们使用函数调用图[5]分析了Linux内核的源代码结构，完成了对其内部重要拓扑结构特征的实证分析，同时也使用度、介数和紧密度中心化分析指标等几种主流的中心化分析方法考察了其中的关键函数。

[1]Newman M E J.Complex systems:A survey[J].Am.J.Phys.，2011，79:800-810.

[2]Barabasi A L.Scale-free networks:a decade and beyond[J].Science，2009，325:412-413.

[3]Jenkins S and Kirk S R.Software architecture graphs as complex networks:A novel partitioning scheme to measure stability and evolution[J].Information Sciences，2007，177:2587-2601.

[4]李兵，马于涛，刘靖，等.软件系统的复杂网络研究进展[J].力学进展，2008，25:805-814.

[5]Ryder B G.Constructing the call graph of a program[C]//IEEE transactions on software engineering，1979，SE-5:216-226.

[6]Yan K K，Fang G，Bhardwaj N，et al.，Comparing genomes to computer operating systems in terms of the topology and evolution of their regulatory control networks[J].PNAS，2010，107:9186-9191.

[7]Wang X F and Chen G R.Complex networks:small-world，scale-free and beyond[J]//IEEE Circuits and Systems Magazine，2003(3):6–20.

[8]丁德武，刘涛，陆克中.复杂网络的中心化及其在代谢网络中的应用[J].计算机与应用化学，2008，25:1508-1510.