自然界有许多复杂系统都可以用复杂网络来描述^[1]，如蛋白质网^[2]、铁路网^[3]、航空网^[4]等。复杂网络为研究软件系统的结构提供了一种有力的工具^[5]。2002年，Valverde等^[6]首次将复杂网络理论应用到软件系统的拓扑结构中。Valverde^[7]和Myers^[8]等分析了开源软件，用有向网络表征软件系统，得出有向软件网络的“小世界”和“无标度”特征。李兵等^[9]提出了一种软件演化复杂性度量模型。汪北阳和吕金虎^[10]通过分析软件网络中节点的特性，提出了一种含权软件网络模型，能够准确描述软件网络节点间的依赖关系。Huang等^[11]提出了一种基于软件动态执行的软件网络模型，发现该软件网络具有“小世界”和“无标度”特性。何鹏等^[12]研究表明基于类的网络演化特征最好。Zhao等^[13]提出了一种基于重复度和邻居聚类系数的节点重要性度量方法，结果表明，该方法可以有效评价网络中节点的重要性。Pan等^[14]提出了一种多粒度软件网络模型，结果表明，所有被调查的软件网络都具有有界度指数及小世界等特征。Xia等^[15]引入软件镜像的概念作为复杂网络的新模型, 发现软件执行过程中的度分布可以遵循幂律。
复杂网络理论是研究复杂系统鲁棒性的重要工具^[16-18]。目前，科研人员从不同角度对复杂软件系统鲁棒性进行了研究。王小龙等^[19]提出了一种软件动态执行加权网络的建模方法，结果表明，更大的外部扰动强度会加速级联故障扩散。He等^[20]提出了一种级联故障扩散分析(Cascading Failure Diffusion Analyzing，CFDA)算法，结果显示，攻击强传播能力的节点对软件系统的破坏性更大。许多重要的大型软件主要基于函数调用模式开发，如操作系统Linux、数据库系统MySQL等，因此，对函数调用网络开展深入研究是有必要的。另外，现有函数调用网络的研究大多基于无向网络^[21]，而函数调用网络是典型的有向网络。本文构建了tar和MySQL的有向软件网络模型，对有向软件网络的静态鲁棒性研究有重要意义。
1 模型 1.1 函数调用网络 构建基于函数调用的有向软件网络，步骤如下：
步骤1 ??下载tar-1.23和MySQL-5.7.13源码，使用工具Cflow分解源码中函数调用关系。
步骤2??使用tree2dotx工具将步骤1中的函数调用关系转换为dot格式。
步骤3?? 用Gephi软件解析出dot格式中节点与边的依赖关系，生成函数调用网络。
图 1为函数调用网络结构示意图，图中不同颜色代表软件网络中的不同软件功能模块。

图 1 函数调用网络结构示意图 Fig. 1 Schematic diagram of function call software network structure

图选项

1.2 攻击策略 引入如下8种攻击策略研究函数调用网络静态鲁棒性：
1) HODS(High Out-Degree Strategy)策略。在有向软件网络中，节点i的出度k_i^out是指从节点i指向其他直接邻居节点的边的数目。给定网络G的邻接矩阵A=(a_ij)_N×N，如果有从节点i指向节点j的边，则a_ij=1，否则a_ij=0。节点i的出度表示为。在HODS策略中，本文将初始网络中节点的出度由大到小排序，出度大的节点先被移除。
2) HIDS(High In-Degree Strategy)策略。节点i的入度k_iⁱⁿ指从其直接邻节点指向节点i的连边数目。节点i的入度表示为。在HIDS策略中，本文将初始网络中节点的入度由大到小排序，入度大的先移除。
3) RS(Random Strategy)策略。该策略在网络中随机选择节点进行移除。
4) HHS(High Hub Strategy)策略。超文本敏感标题搜索(Hyperlink-Induced Topic Search, HITS)是评价有向软件网络节点重要性的一个经典算法。在HHS策略中，将初始网络中节点的枢纽值由大到小排序。
5) HAS(High Authority Strategy)策略。先计算初始网络中节点的权威值，将其按照从大到小的顺序排序，并先删除权威值大的节点。
6) HPS(High PageRank Strategy)策略。另一个评价有向软件网络节点重要性的算法是PageRank。在HPS策略中，将初始网络中节点PR值由大到小排序，值大的节点先被移除。
7) HDS(High Dependency Strategy)策略。依赖度定义为：设x, y∈V(G)，如果从x到y有一条任意长度的有向路径，则称x可以到达y。T(x)表示网络G中x可以到达的所有节点(不包括x)的集合。节点x的依赖度定义为集合T(x)中元素的个数，记为D_G(x)=|T(x)|。
8) HIS(High Influence Strategy)策略。影响度定义为：设x, y∈V(G)，如果从y到x有一条任意长度的有向路径，则称y可以到达x。D(x)表示网络G中可以到达x的所有节点(不包括x)的集合。节点x的影响度定义为集合D(x)中元素的个数，记为I_G(x)=|D(x)|。
1.3 鲁棒性指标 在有向图中，任取一对节点i和j，若同时存在一条从节点i到j和从节点j到i的路径，则称该图为强连通图。若将有向图的每条有向边都替换为无向边，则得到的图称为有向图的基图。若一个有向图的基图是连通图，则该有向图是弱连通图。两者的区别就在于：强连通图中各节点之间都存在相互到达的路径，而弱连通图中可能只存在单向到达的路径。最大强(弱)连通子图是有向网络中节点数最多的强(弱)连通子图。
弱连通指标W=N_W/N，N_W为网络受到攻击后的最大弱连通子图的节点总数，N为初始网络的节点总数。强连通指标S=N_S/N，N_S为网络受到攻击后的最大强连通子图的节点总数。
2 仿真结果 2.1 结构属性分析 表 1列出了tar网络和MySQL网络的参数。表中：N为节点数，M为边数，< K>为平均度，< L>为平均路径长度，C为聚类系数，d为网络直径(网络中任意两节点间距离的最大值)，为平均影响度，< D>为平均依赖度。在计算 < K>、< L>、C、d时把软件网络看作无向软件网络，计算、< D>时把软件网络看作有向软件网络。从表 1可以看出，2个软件网络平均路径长度都小于4.3，聚类系数都大于0.08，符合“小世界”特征；每个网络的平均影响度与平均依赖度是相等的。MySQL网络的平均影响度达到了1 176.345，远大于tar网络的35.322，表明MySQL网络的函数重用程度远高于tar网络的函数重用程度。MySQL网络的规模比tar网络的规模大，达到了4 598个节点。2个网络的网络直径都为11，说明网络直径与网络规模没有必然联系。
表 1 软件网络的结构属性 Table 1 Structural properties of software networks

软件名称	N	M	< K>	< L>	C	d	< I>	< D>
tar	1 204	3 285	5.384	4.132	0.087	11	35.322	35.322
MySQL	4 598	16 018	6.514	4.294	0.119	11	1 176.345	1 176.345

表选项






表 2为tar的前5个软件模块的结构属性。可以看出，这5个模块的聚类系数相对较小，最大的软件模块src的聚类系数只有0.037，远小于0.087，说明tar网络的聚类系数由于5个软件模块耦合而显著提高了，才使得tar网络具有了高聚类的“小世界”特征。src模块有687个节点，相对于整个tar网络，src模块的平均路径长度、聚类系数、平均影响度等结构属性均有明显减少，特别是平均影响度和平均依赖度只有7.760，远小于整个tar网络的35.322，说明src模块的复杂性明显低于整个tar网络的复杂性。gnu是tar网络的第2大功能模块，可以看出gnu网络比较稀疏，平均度只有3.840；gnu的平均路径长度为4.405，比整个tar网络的4.132还要大，gnu的网络直径为14，也大于整个tar网络的直径11，这说明gnu模块内部函数的互相调用效率不高，通过和其他软件模块的耦合提高了gnu模块的函数调用效率。另外3个软件模块(lib、tests、rmt)的平均影响度和平均依赖度都远小于1，说明这3个模块各自内部函数之间的耦合程度较低，函数重用程度不高。
表 2 tar软件模块的结构属性 Table 2 Structural properties of software modules in tar

模块序号	模块名称	N	M	< K>	< L>	C	d	< I>	< D>
1	src	687	1 817	5.287	3.059	0.037	9	7.760	7.760
2	gnu	563	1 104	3.840	4.405	0.049	14	6.350	6.350
3	lib	110	151	2.745	1.543	0.026	9	0.242	0.242
4	tests	79	112	2.835	1.620	0.024	6	0.181	0.181
5	rmt	57	101	3.544	1.760	0.058	6	0.190	0.190

表选项






表 3列出了MySQL的前5个软件模块的结构属性。可以看出，这5个模块的最大聚类系数只有0.075，明显小于0.119，即完整MySQL网络的聚类系数，表明MySQL网络的聚类系数由于主要软件模块的耦合而提高了。最大的软件模块mysys的平均路径长度只有2.991，明显小于MySQL网络的4.294，说明mysys模块内部函数之间的平均调用效率较高。软件模块strings平均影响度和平均依赖度小于1，说明该模块内部各函数互相调用的较少，函数重用程度不高。
表 3 MySQL软件模块的结构属性 Table 3 Structural properties of software modules in MySQL

模块序号	模块名称	N	M	< K>	< L>	C	d	< I>	< D>
1	mysys	1 042	2 718	5.217	2.991	0.046	12	2.513	2.513
2	libevent	667	2 219	6.654	4.139	0.041	9	4.090	4.090
3	storagemyisam	568	1 839	6.475	4.392	0.053	8	3.201	3.201
4	cmd-line-utils	556	1 179	4.241	3.522	0.057	10	2.890	2.890
5	strings	342	628	3.673	2.049	0.075	12	0.303	0.303

表选项






图 2为tar和MySQL网络的节点依赖度和影响度分布图。

图 2 不同网络节点依赖度和影响度的分布 Fig. 2 Distribution of node dependency and influence of different networks

图选项

由图 2(a)、(b)可得节点的依赖度与节点出现的频率成反比关系。tar网络中有489个节点的依赖度是0，占网络总节点数的41%(见图 2(a))，MySQL网络中有1 753个节点的依赖度是0，占网络总节点数的38%(见图 2(b))。由图 2(c)、(d)可得，随着影响度增大，节点的出现频率总体上呈下降趋势。tar网络有127个节点的影响度是0，占网络总节点数的11%(见图 2(c))，MySQL网络有654个节点的影响度是0，占网络总节点数的14%(见图 2(d))。
表 4列出了tar和MySQL网络中依赖度最大的节点的属性。可以看出，tar网络中具有最大依赖度的函数为getopt_long，该节点的依赖度达到了731，超过了网络总节点数(N=1 204)的一半，即该函数直接或间接调用了软件中超过一半的函数。同时该节点的影响度和入度都为0，只有出度大于0，表明该节点的依赖度只与出度相关。MySQL中依赖度最大的函数为mi_open_share，该节点的依赖度达到了2 224，接近网络总节点数(N=4 598)的一半，即该函数直接或间接调用了软件中将近一半的函数，同时该节点的影响度和入度均为0，出度为59，表明该节点的依赖度只与出度相关。
表 4 依赖度最大的节点属性 Table 4 Properties of node with maximum dependency

软件名称	节点编号	函数名称	依赖度	出度	入度	影响度
tar	379	getopt_long	731	2	0	0
MySQL	2 337	mi_open_share	2 224	59	0	0

表选项






表 5列出了tar和MySQL网络中具有最大影响度的节点的属性。tar网络中strlen函数的影响度最大，达到了456，该节点的依赖度和出度都为0，入度为97，表明该节点的影响度只与入度相关。MySQL网络中free函数的影响度最大，达到了1 087，该节点的依赖度和出度均为0，入度为129，表明该节点的影响度只与入度相关。
表 5 影响度最大的节点属性 Table 5 Properties of node with maximum influence

软件名称	节点编号	函数名称	影响度	出度	入度	依赖度
tar	976	strlen	456	0	97	0
MySQL	1 151	free	1 087	0	129	0

表选项






随着依赖度的增加，tar网络的出度呈现递增趋势(见图 3(a))。对于MySQL网络，节点的出度随依赖度的增大而增大(见图 3(b))。随着影响度的增大，tar网络的入度有递增的趋势(见图 3(c))。MySQL网络的入度随着影响度的增大有递增的趋势(见图 3(d))。

图 3 度与依赖度和影响度关系 Fig. 3 Relationship between degree of nodes and node dependency and influence

图选项

由图 4可得，影响度与依赖度具有负相关性；有大量节点位于图的左下角，表明函数调用网络中存在大量依赖度和影响度均很小的节点；tar网络中最大依赖度的值(731)大于其最大影响度的值(456)，MySQL网络中最大依赖度的值(2 224)大于其最大影响度的值(1 087)，表明软件网络中依赖度的最大值通常大于影响度的最大值。在复杂软件系统中，依赖度大的函数因为直接或间接调用了大量的其他函数，使得该函数内部结构比较复杂，导致其被重用的概率就会比较低，影响度就低。

图 4 节点的影响度与依赖度的关系 Fig. 4 Relationship between node influence and dependency

图选项

2.2 鲁棒性分析 图 5为tar和MySQL网络弱连通指标W和强连通指标S与攻击比率f=N′/N的关系，N′为被攻击节点的总数，N为初始网络的节点总数。随着f的增大，鲁棒性指标值减少。在tar网络中，对于弱连通指标，HODS策略的攻击效果最好，当f>0.33时整个网络崩溃了(见图 5(a))；对于强连通指标，当f较小时，HODS策略的攻击效果最好。当f较大时，HIDS的攻击效果最好(见图 5(b))。在MySQL网络中，对于弱连通指标，HIDS策略的攻击效果最好(见图 5(c))。对于强连通指标，HODS策略的攻击效果最好(见图 5(d))。由此得出，节点的出度或入度对函数调用网络的静态鲁棒性具有更重要的影响，即基于高出度或高入度的攻击策略通常是最好的攻击策略。对于tar网络，当攻击比率f较小时，高出度策略明显优于高入度策略，但当攻击比率较大时，两者的区别不再明显；对于MySQL网络，在弱连通指标下，高入度策略比高出度策略更容易使网络崩溃。而在强连通指标下，情况正好相反。

图 5 tar和MySQL网络鲁棒性指标与攻击比率的关系 Fig. 5 Relationship between tar and MySQL network robustness and attack rate

图选项

3 结论 本文基于开源软件源码中的函数调用关系，对软件网络的结构属性及其静态鲁棒性进行研究。结果表明：
1) 节点的依赖度与出度存在正相关性，节点的影响度与入度呈正相关性，节点的依赖度和影响度具有负相关性。
2) 引入8种节点攻击策略对tar和MySQL网络的静态鲁棒性进行研究，结果显示，节点的出度或入度对函数调用网络的静态鲁棒性具有更重要的影响，即基于高出度或高入度的攻击策略通常是最佳的攻击策略。

参考文献

[1]	BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. DOI:10.1126/science.286.5439.509
[2]	胡赛, 熊慧军, 李学勇, 等. 多关系蛋白质网络构建及其应用研究[J]. 自动化学报, 2015, 41(2): 2155-2163. HU S, XIONG H J, LI X Y, et al. The construction and application of multi-relational protein networks[J]. Acta Automatica Sinica, 2015, 41(2): 2155-2163. (in Chinese)
[3]	ZHANG J H, HU F N, WANG S L, et al. Structural vulnerability and intervention of high speed railway networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 462(c): 743-751.
[4]	HONG C, ZHANG J, CAO X B, et al. Structural properties of the Chinese air transportation multilayer network[J]. Chaos, Solitons and Fractals, 2016, 86: 28-34. DOI:10.1016/j.chaos.2016.01.027
[5]	VASA R, SCHNEIDER J G, WOODWARD C, et al. Detecting structural changes in object oriented software systems[C]//Proceedings of the 2005 International Symposium on Empirical Software Engineering. Piscataway: IEEE Press, 2005: 479-486.
[6]	VALVERDE S, CANCHO R F, SOLé R V. Scale-free networks from optimal design[J]. Europhysics Letters, 2002, 60(4): 512-517. DOI:10.1209/epl/i2002-00248-2
[7]	VALVERDE S, SOLé R V. Network motifs in computational graphs: A case study in software architecture[J]. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 2005, 72(2): 147-154.
[8]	MYERS C R. Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs[J]. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 2003, 68(4): 046116. DOI:10.1103/PhysRevE.68.046116
[9]	李兵, 王浩, 李曾扬, 等. 基于复杂网络的软件复杂性度量研究[J]. 电子学报, 2006, 34(S1): 2372-2375. LI B, WANG H, LI Z Y, et al. Study on software complexity measure based on complex network[J]. Acta Electronica Sinica, 2006, 34(S1): 2372-2375. (in Chinese)
[10]	汪北阳, 吕金虎. 复杂软件系统的软件网络结点影响分析[J]. 软件学报, 2013, 24(12): 2814-2829. WANG B Y, LV J H. Analysis of software network node impact of complex software systems[J]. Journal of Software, 2013, 24(12): 2814-2829. (in Chinese)
[11]	HUANG L Z, AI J, PEI H Y. Software network models based on dynamic execution for fault propagation research[C]//IEEE International Conference on Software Quality. Piscataway: IEEE Press, 2015: 56-61.
[12]	何鹏, 王鹏, 李兵. 基于多粒度软件网络模型的软件系统演化分析[J]. 电子学报, 2018, 46(2): 258-267. HE P, WANG P, LI B. Evolution analysis of software system based on multi-granularity software network model[J]. Acta Electronica Sinica, 2018, 46(2): 258-267. (in Chinese)
[13]	ZHAO X S, ZHANG H H, ZHANG M Y, et al. Identifying influential nodes in large-scale software networks[C]//IEEE Information Technology and Mechatronics Engineering Conference. Piscataway: IEEE Press, 2017: 764-767.
[14]	PAN W F, LI B, MA Y T, et al. Multi-granularity evolution analysis of software using complex network theory[J]. Journal of Systems Science and Complexity, 2011, 24(6): 1068-1082. DOI:10.1007/s11424-011-0319-z
[15]	XIA Y X, ZHANG W P, ZHANG X J. The effect of capacity redundancy disparity on the robustness of interconnected networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 447: 561-568. DOI:10.1016/j.physa.2015.12.077
[16]	TAN F, XIA Y, WEI Z. Robust-yet-fragile nature of interdependent networks[J]. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 2015, 91(5): 052809. DOI:10.1103/PhysRevE.91.052809
[17]	WANG J W, SUN E H, XU B, et al. Robust-yet-fragile nature of interdependent networks[J]. Chao, Solitons and Fractals, 2015, 91(5): 052809.
[18]	王尔申, 李宇, 宏晨, 等. Linux软件网络的结构属性及静态稳健性[J]. 电信科学, 2019, 11(11): 9-18. WANG E S, LI Y, HONG C, et al. Structural properties and static robustness of Linux software network[J]. Telecommunication Science, 2019, 11(11): 9-18. (in Chinese)
[19]	王小龙, 侯刚, 任龙涛, 等. 软件动态执行网络建模及其级联故障分析[J]. 计算机科学, 2014, 41(8): 109-114. WANG X L, HOU G, REN L T, et al. Software dynamic execution network modeling and its cascading failure analysis[J]. Computer Science, 2014, 41(8): 109-114. (in Chinese)
[20]	HE H T, REN R, ZHANG B, et al. Analysis on impact of node failure in software execution network[J]. Journal of Computational Information Systems, 2015, 11(6): 2217-2225.
[21]	王竣德, 老松杨, 阮逸润, 等. 基于节点负载容忍度的相依网络鲁棒性研究[J]. 系统工程与电子技术, 2017, 39(11): 2477-2483. WANG J D, LAO S Y, RUAN Y R, et al. Research on robustness of dependent networks based on node load tolerance[J]. Systems Engineering and Electronics, 2017, 39(11): 2477-2483. DOI:10.3969/j.issn.1001-506X.2017.11.13 (in Chinese)