互联网上病毒传播数学模型的研究
|
摘要
近几年来,计算机技术逐渐成熟,互联网日益普及,计算机病毒技术更是飞速增长,危害越来越大,造成的损失更是不容忽视,网络病毒在互联网上的传播早已引起了很多国家和的学者的高度重视,已经进行了大量的研究。
这几年,复杂网络的研究正处于蓬勃发展的阶段。其研究者来自图论,计算机网络,统计物理等多个领域。大量的研究表明,复杂网络与规则网络和随机网络有不同的统计特征,现实中存在的大量的复杂系统可以用复杂网络来描述。互联网虽然是人们亲手建立起来,但却没有人能够知道这个庞然大物是什么样子,如何运作。互联网依其高度的复杂性,可以看做是一个由计算机组成的“生态系统”。钱学森指出,互联网是一个典型的复杂巨系统,互联网网络是一个复杂网络。
计算机在互联网上的传播和蔓延,可以看作是符合某种规律的网络传播行为,互联网的拓扑结构影响和制约着病毒的传播行为,本文就是从互联网的复杂性角度分析其网络结构对病毒传播的影响,介绍了典型的计算机病毒数学传播模型,最后在前人工作的基础上建立了一种电子邮件传播模型,在一定程度上回避了网络结构对病毒传播的影响,能够比较客观的反应邮件病毒的传播特征。
In recent years, the computer technology is becoming mature and Internet is becoming widespread gradually. in the same time, the computer virus technology is increasing rapidly and the harm to us becomes more and more serious. We can not neglect the damage which it brings to us. The high attention has been paid to spread of network virus on the Internet and a lot of researches have been done.
These years, the research for complex network is developing vigorously. Researchers are from the domain of graph theory, network and statistic physics etc. Lots of researches indicate that complex network, regular network and stochastic network have different statistical characters. The exiting complex system in the reality can be described by the complex network. Although Internet is built up by human, nobody can know what the buster is and how it runs. Depending on its high complexity, Internet can be thought as a ecosystem which consists of computers. Professor Xuesen Qian said Internet is a typical complex large system and Internet network is a complex network.
The spread and extent of computer virus on the Internet can be considered to be a certain network publishing. The Internet topologic structure effects and restricts the virus spread. This text is to analyzing the influence of network structure to virus spread in terms of Internet complexity; introducing the typical computer virus mathematics propagation model and establishing an email propagation model on the basis of previous work. This has avoided the influence of the network structure to the virus spread to a certain extent and can reflect objectively the spread characteristics of the email virus.
这几年,复杂网络的研究正处于蓬勃发展的阶段。其研究者来自图论,计算机网络,统计物理等多个领域。大量的研究表明,复杂网络与规则网络和随机网络有不同的统计特征,现实中存在的大量的复杂系统可以用复杂网络来描述。互联网虽然是人们亲手建立起来,但却没有人能够知道这个庞然大物是什么样子,如何运作。互联网依其高度的复杂性,可以看做是一个由计算机组成的“生态系统”。钱学森指出,互联网是一个典型的复杂巨系统,互联网网络是一个复杂网络。
计算机在互联网上的传播和蔓延,可以看作是符合某种规律的网络传播行为,互联网的拓扑结构影响和制约着病毒的传播行为,本文就是从互联网的复杂性角度分析其网络结构对病毒传播的影响,介绍了典型的计算机病毒数学传播模型,最后在前人工作的基础上建立了一种电子邮件传播模型,在一定程度上回避了网络结构对病毒传播的影响,能够比较客观的反应邮件病毒的传播特征。
In recent years, the computer technology is becoming mature and Internet is becoming widespread gradually. in the same time, the computer virus technology is increasing rapidly and the harm to us becomes more and more serious. We can not neglect the damage which it brings to us. The high attention has been paid to spread of network virus on the Internet and a lot of researches have been done.
These years, the research for complex network is developing vigorously. Researchers are from the domain of graph theory, network and statistic physics etc. Lots of researches indicate that complex network, regular network and stochastic network have different statistical characters. The exiting complex system in the reality can be described by the complex network. Although Internet is built up by human, nobody can know what the buster is and how it runs. Depending on its high complexity, Internet can be thought as a ecosystem which consists of computers. Professor Xuesen Qian said Internet is a typical complex large system and Internet network is a complex network.
The spread and extent of computer virus on the Internet can be considered to be a certain network publishing. The Internet topologic structure effects and restricts the virus spread. This text is to analyzing the influence of network structure to virus spread in terms of Internet complexity; introducing the typical computer virus mathematics propagation model and establishing an email propagation model on the basis of previous work. This has avoided the influence of the network structure to the virus spread to a certain extent and can reflect objectively the spread characteristics of the email virus.
引文
1 张运凯,王方伟,张玉清,马建峰.无尺度网络上的蠕虫传播行为研究[J].通讯和计算机,2005,2(2) 14-18
2 Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology [J]. ACM SIGCOMM Computer Communication Review,1999,29(4):251-262
3 Jin S.D., Bestavros, A. Small-world Internet topologies:possible causes and implications on scalability of end-system multicast [J]. Technical report, BUCS-TR-2002—004, Calvert K, Doar M, Zegura E. Modeling Internet topology[J]. IEEE Communication Magazine,1997,35(6):160-163
4 Bu T, Towsley D. On distinguishing between Internet power law topology generators [J]. Proceeding of INFOCOM, New York,2002,2:638-647
5 Newman M E J.The structure and function of complex networks [J].SIAM Reviewer,2003,45:167～ 256
6 Siganos G, Faloutsos M, Faloutsous P, Faloutsous C。Power laws and the AS-level Internet topology [J].IEEE/ACM Transactions on Networking,2003,11 (4):514-524
7 Jaiswal S, Rosenberg A L, Towsley D. Comparing the structure of power-law graph and the Internet AS graph [J].12th IEEE Internetional Conference on Network Protocols (ICNP'04),2004, 294-303.
8 Cai S L, Gao L X, Gong W B, Xu W Q. On generating Internet hierarchical topology [J]. IEEE Conference on Decision and Control,2004.43.178-183
9 Mahadevan P, Krioukov D, Fomenkov M, et al. Lessons form three views of the Internet topology[J].arXiv:cs.2005.120-24
10 Zhou S, Mondragon R J. Accurately modeling the Internet topology [J]. Phys. Rev. E,2004,70: 066108
12 Waxman B M. Routing of multipoint connections [J]. IEEE Journal on Selected Areas in communications,1988,6(9):1617-1622.
13 Matthew Doar,Ian Leslie.How Bad is Natve Multicast Routing[C].Proc.of IEEE INFOCOM'93,1993.82-88
14 Ellen W Zegura.How to Model an Internetwork [J].Proc.IEEE INFOCOM,San Francisco,CA,1996
15 Ellen W Zegura.How to Model an Internetwork [J].Proc.IEEE INFOCOM,San Francisco,CA,1996
16 Waxman B M.Routing of multipoint connections [J].IEEE Journal of Selected Areas in Communication,1988,6(9):1617-1622
17 Palmer C R, Steffan J G. Generating network topologies that obey power laws[J]. in:Proc of the GLOBECOM 2000,Vol 1.San Francisco:IEEE,2000.434-438
18 Aiello W Chung, LuLy. A randon graph model for massive graphs [J]. In:Proc.of the ACM STOC 2000.Portland:ACM Press,2000.171-180
19 Bu T, Towsley D. On distinguishing between Internet power law topology generators [J]. Proceeding of INFOCOM, New York,2002,2:638-647
20 Zhou S, Mondragon R J. Towards modeling the Internet topology-the Internet growth model [J]. Teletraffic science an engineering,2003,5:121-130
21 Park S T、Pennock D、Glies C L. Comparing static and dynamic measurements and models of the Internet's topology [J]. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies,2004,3:1616-1627
22汪小帆李翔陈关荣. 复杂网络理论及其应用[M]北京清华大学出版社2006 66-68
23 R. Pastor-Satorras and A. Vespignani. Epidemic dynamics and endemic states in com-plex networks[J]. Phys. Rev. E 63(6 Ⅱ):066117/1-066117/8,2001.[6] R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks[J].. Phys.Rev.Lett.2001.86(14):3200-3203,
24 Pastor-Satorras and Vespignani. Epidemics and immuinzation[J]. Wiley-VCH,2002.113-132
25 R. Pastor-Satorras and A. Vespignani. Epidemic dynamics in finite size scale-free net-works [J]. Phys. Rev E,2002.65(3 2A):351081-351084,
26 Z. Liu and B. Hu. Epidemic spreading in community networks [J]. EUROPHYSICS LETTERS, 2005.72(2):315-321,
27 A. Barrat、M. Barthelemy、and A. Vespignani. Modeling the evolution of weighted networks [J]。Phys. Rev E,2004.70(6):66149,和 Alain Barrat, Marc Barthelemy, and Alessandro Vespignani. Weighted evolving net-works:Coupling topology and weight dynamics. Phys. Rev Lett..200492(22):228701,
28 Anderson R M, May R M. Infections diseases in humans[M]. Oxfard UnivPress,1992
29 Cohen R, Havlin S, Ben-Avraham D. Efficient immunization strategies for computernetworks and populations. Pays. Rev. Lett,2003,91:247801
30 Balthrop J、Forrest S、Newman M E J、Williamson M M. Technological networks and the spread of computer viruses[J].Science,2004,304:527～529
31 Pastor-Satorras R, Vespignani A. Immunization of complex net-works[J]. Physical Review E,2002
32 Lakhina A, Byers JW, Crovella M, Xie P. Sampling biases in IP topology measurements[J]. Proc. of the IEEE INFOCOM 2003,Vol 1.San Francisco:IEEE_2003.332-341
2 Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology [J]. ACM SIGCOMM Computer Communication Review,1999,29(4):251-262
3 Jin S.D., Bestavros, A. Small-world Internet topologies:possible causes and implications on scalability of end-system multicast [J]. Technical report, BUCS-TR-2002—004, Calvert K, Doar M, Zegura E. Modeling Internet topology[J]. IEEE Communication Magazine,1997,35(6):160-163
4 Bu T, Towsley D. On distinguishing between Internet power law topology generators [J]. Proceeding of INFOCOM, New York,2002,2:638-647
5 Newman M E J.The structure and function of complex networks [J].SIAM Reviewer,2003,45:167～ 256
6 Siganos G, Faloutsos M, Faloutsous P, Faloutsous C。Power laws and the AS-level Internet topology [J].IEEE/ACM Transactions on Networking,2003,11 (4):514-524
7 Jaiswal S, Rosenberg A L, Towsley D. Comparing the structure of power-law graph and the Internet AS graph [J].12th IEEE Internetional Conference on Network Protocols (ICNP'04),2004, 294-303.
8 Cai S L, Gao L X, Gong W B, Xu W Q. On generating Internet hierarchical topology [J]. IEEE Conference on Decision and Control,2004.43.178-183
9 Mahadevan P, Krioukov D, Fomenkov M, et al. Lessons form three views of the Internet topology[J].arXiv:cs.2005.120-24
10 Zhou S, Mondragon R J. Accurately modeling the Internet topology [J]. Phys. Rev. E,2004,70: 066108
12 Waxman B M. Routing of multipoint connections [J]. IEEE Journal on Selected Areas in communications,1988,6(9):1617-1622.
13 Matthew Doar,Ian Leslie.How Bad is Natve Multicast Routing[C].Proc.of IEEE INFOCOM'93,1993.82-88
14 Ellen W Zegura.How to Model an Internetwork [J].Proc.IEEE INFOCOM,San Francisco,CA,1996
15 Ellen W Zegura.How to Model an Internetwork [J].Proc.IEEE INFOCOM,San Francisco,CA,1996
16 Waxman B M.Routing of multipoint connections [J].IEEE Journal of Selected Areas in Communication,1988,6(9):1617-1622
17 Palmer C R, Steffan J G. Generating network topologies that obey power laws[J]. in:Proc of the GLOBECOM 2000,Vol 1.San Francisco:IEEE,2000.434-438
18 Aiello W Chung, LuLy. A randon graph model for massive graphs [J]. In:Proc.of the ACM STOC 2000.Portland:ACM Press,2000.171-180
19 Bu T, Towsley D. On distinguishing between Internet power law topology generators [J]. Proceeding of INFOCOM, New York,2002,2:638-647
20 Zhou S, Mondragon R J. Towards modeling the Internet topology-the Internet growth model [J]. Teletraffic science an engineering,2003,5:121-130
21 Park S T、Pennock D、Glies C L. Comparing static and dynamic measurements and models of the Internet's topology [J]. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies,2004,3:1616-1627
22汪小帆李翔陈关荣. 复杂网络理论及其应用[M]北京清华大学出版社2006 66-68
23 R. Pastor-Satorras and A. Vespignani. Epidemic dynamics and endemic states in com-plex networks[J]. Phys. Rev. E 63(6 Ⅱ):066117/1-066117/8,2001.[6] R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks[J].. Phys.Rev.Lett.2001.86(14):3200-3203,
24 Pastor-Satorras and Vespignani. Epidemics and immuinzation[J]. Wiley-VCH,2002.113-132
25 R. Pastor-Satorras and A. Vespignani. Epidemic dynamics in finite size scale-free net-works [J]. Phys. Rev E,2002.65(3 2A):351081-351084,
26 Z. Liu and B. Hu. Epidemic spreading in community networks [J]. EUROPHYSICS LETTERS, 2005.72(2):315-321,
27 A. Barrat、M. Barthelemy、and A. Vespignani. Modeling the evolution of weighted networks [J]。Phys. Rev E,2004.70(6):66149,和 Alain Barrat, Marc Barthelemy, and Alessandro Vespignani. Weighted evolving net-works:Coupling topology and weight dynamics. Phys. Rev Lett..200492(22):228701,
28 Anderson R M, May R M. Infections diseases in humans[M]. Oxfard UnivPress,1992
29 Cohen R, Havlin S, Ben-Avraham D. Efficient immunization strategies for computernetworks and populations. Pays. Rev. Lett,2003,91:247801
30 Balthrop J、Forrest S、Newman M E J、Williamson M M. Technological networks and the spread of computer viruses[J].Science,2004,304:527～529
31 Pastor-Satorras R, Vespignani A. Immunization of complex net-works[J]. Physical Review E,2002
32 Lakhina A, Byers JW, Crovella M, Xie P. Sampling biases in IP topology measurements[J]. Proc. of the IEEE INFOCOM 2003,Vol 1.San Francisco:IEEE_2003.332-341