函数调用网络的结构属性及其静态鲁棒性

王尔申; 任虹帆; 宏晨; 孙庆华; 刘畅; 徐嵩

doi:10.13700/j.bh.1001-5965.2020.0039

函数调用网络的结构属性及其静态鲁棒性

doi: 10.13700/j.bh.1001-5965.2020.0039

王尔申^{1, 2},
任虹帆¹,
宏晨^{3, 4, ,},
孙庆华^{3, 4},
刘畅^{3, 4},
徐嵩¹

1.
沈阳航空航天大学电子信息工程学院, 沈阳 110136
2.
辽宁通用航空研究院(沈阳航空航天大学), 沈阳 110136
3.
北京联合大学北京市信息服务工程重点实验室, 北京 100101
4.
北京联合大学机器人学院, 北京 100101

基金项目:

国家重点研发计划 2018AAA0100804

国家自然科学基金 61571309

国家自然科学基金 61703287

国家自然科学基金 61972040

辽宁省重点研发计划 2020JH2/10100045

辽宁省“兴辽英才计划” XLYC1907022

沈阳市高层次创新人才计划 RC190030

详细信息

作者简介:
王尔申男, 博士, 教授, 博士生导师。主要研究方向: 卫星导航、航空监视技术

宏晨男, 博士, 副教授。主要研究方向: 多智能体系统、复杂网络

通讯作者:
宏晨. E-mail: hchchina@sina.com

中图分类号: V221⁺.3;TB553
计量
- 文章访问数: 568
- HTML全文浏览量: 111
- PDF下载量: 130
- 被引次数: 0
出版历程
- 收稿日期: 2020-02-08
- 录用日期: 2020-05-01
- 网络出版日期: 2021-04-20

Structural properties and static robustness of function call networks

WANG Ershen^{1, 2},
REN Hongfan¹,
HONG Chen^{3, 4
, ,},
SUN Qinghua^{3, 4},
LIU Chang^{3, 4},
XU Song¹

1.
College of Electronic and Information Engineering, Shenyang Aerospace University, Shenyang 110136, China
2.
Liaoning General Aviation Academy(Shenyang Aerospace University), Shenyang 110136, China
3.
Beijing Key Laboratory of Information Service Engineering, Beijing Union University, Beijing 100101, China
4.
College of Robotics, Beijing Union University, Beijing 100101, China

Funds:

National Key R & D Program of China 2018AAA0100804

National Natural Science Foundation of China 61571309

National Natural Science Foundation of China 61703287

National Natural Science Foundation of China 61972040

Key R & D Projects of Liaoning Province 2020JH2/10100045

Talent Project of Revitalization Liaoning XLYC1907022

High-Level Innovation Talent Project of Shenyang RC190030

More Information

Corresponding author: HONG Chen. E-mail: hchchina@sina.com

摘要

摘要:
通过对开源软件tar和MySQL源码的分析，构建基于函数调用的有向软件网络模型，研究函数调用网络的度分布、聚类系数等多个结构属性。结果表明，多个主要软件模块的耦合才使得整个函数调用网络具有高聚类特性；节点的依赖度(影响度)与节点的出度(入度)存在正相关性；节点的依赖度与影响度具有负相关性。基于有向软件网络鲁棒性的弱连通和强连通指标，采用不同节点攻击策略验证函数调用网络的静态鲁棒性。研究结果表明，对于tar网络，高出度策略对网络的弱连通性具有最佳的攻击效果；对于MySQL网络，高入度策略对网络的弱连通性具有最佳的攻击效果。
- 软件网络 /
- 网络属性 /
- 网络鲁棒性 /
- 复杂网络 /
- 攻击策略
Abstract:
In this paper, we build a directed function call software network model by analyzing the source code of the open source software tar and MySQL. The network structural properties, such as degree distribution and clustering coefficient, are investigated. The results indicate that the coupling of multiple major software modules leads to a high clustering coefficient of the entire software network; the node dependence (influence) is of a positive correlation with the node's out-degree (in-degree); the node influence has a negative correlation with its dependence. Based on the weak connectivity and strong connectivity robustness measure of directed networks, we use different node attack strategies to investigate the static robustness of function call networks. The experimental results show that, for tar network, high out-degree strategy obtains the best attack effect with respect to weak connectivity; in the case of MySQL network under weak connectivity, high in-degree strategy achieves the best attack effect.
- software network /
- network property /
- network robustness /
- complex network /
- attacking strategy

HTML全文

图 1 函数调用网络结构示意图

Figure 1. Schematic diagram of function call software network structure

下载: 全尺寸图片幻灯片

图 2 不同网络节点依赖度和影响度的分布

Figure 2. Distribution of node dependency and influence of different networks

下载: 全尺寸图片幻灯片

图 3 度与依赖度和影响度关系

Figure 3. Relationship between degree of nodes and node dependency and influence

下载: 全尺寸图片幻灯片

图 4 节点的影响度与依赖度的关系

Figure 4. Relationship between node influence and dependency

下载: 全尺寸图片幻灯片

图 5 tar和MySQL网络鲁棒性指标与攻击比率的关系

Figure 5. Relationship between tar and MySQL network robustness and attack rate

下载: 全尺寸图片幻灯片

表 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

下载: 导出CSV

表 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

下载: 导出CSV

表 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

下载: 导出CSV

表 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

下载: 导出CSV

表 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

下载: 导出CSV

参考文献(21)

[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. https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201512016.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-MOTO201512016.htm
[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. http://www.sciencedirect.com/science/article/pii/S0378437116304071
[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. http://www.ncbi.nlm.nih.gov/pubmed/16196644
[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. https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU2006S1007.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU2006S1007.htm
[10]	汪北阳, 吕金虎. 复杂软件系统的软件网络结点影响分析[J]. 软件学报, 2013, 24(12): 2814-2829. https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201312004.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201312004.htm
[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. https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201802001.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-DZXU201802001.htm
[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. http://smartsearch.nstl.gov.cn/paper_detail.html?id=142519bbdeebafe0725d472efeb01485
[18]	王尔申, 李宇, 宏晨, 等. Linux软件网络的结构属性及静态稳健性[J]. 电信科学, 2019, 11(11): 9-18. https://www.cnki.com.cn/Article/CJFDTOTAL-DXKX201911002.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-DXKX201911002.htm
[19]	王小龙, 侯刚, 任龙涛, 等. 软件动态执行网络建模及其级联故障分析[J]. 计算机科学, 2014, 41(8): 109-114. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201408025.htm 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). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJA201408025.htm
[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. http://www.researchgate.net/publication/283128915_Analysis_on_impact_of_node_failure_in_software_execution_network
[21]	王竣德, 老松杨, 阮逸润, 等. 基于节点负载容忍度的相依网络鲁棒性研究[J]. 系统工程与电子技术, 2017, 39(11): 2477-2483. doi: 10.3969/j.issn.1001-506X.2017.11.13 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(in Chinese). doi: 10.3969/j.issn.1001-506X.2017.11.13