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.