Special Issue: Computer Networks and Distributed Computing

• Articles • Previous Articles     Next Articles

Targeted Local Immunization in Scale-Free Peer-to-Peer Networks

Xin-Li Huang1, Fu-Tai Zou2, and Fan-Yuan Ma1   

  1. 1Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200030, China 2School of Information Security Engineering, Shanghai Jiao Tong University, Shanghai 200030, China
  • Received:2006-08-03 Revised:2006-10-31 Online:2007-05-10 Published:2007-05-10

The power-law node degree distributions of peer-to-peer overlay networks make them extremely robust to random failures whereas highly vulnerable under intentional targeted attacks. To enhance attack survivability of these networks, DeepCure, a novel heuristic immunization strategy, is proposed to conduct decentralized but targeted immunization. Different from existing strategies, DeepCure identifies immunization targets as not only the highly-connected nodes but also the nodes with high {\it availability} and/or high {\it link load}, with the aim of injecting immunization information into just {\it right} targets to cure. To better trade off the cost and the efficiency, DeepCure deliberately select these targets from 2-{\it local} neighborhood, as well as topologically-remote but semantically-close friends if needed. To remedy the weakness of existing strategies in case of sudden epidemic outbreak, DeepCure is also coupled with a local-hub oriented {\it rate throttling} mechanism to enforce proactive rate control. Extensive simulation results show that DeepCure outperforms its competitors, producing an arresting increase of the network attack tolerance, at a lower price of eliminating viruses or malicious attacks.

Key words: dependability; reliability; availability; safety; security;

[1] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. In -\it Proc. SIGCOMM}, Cambridge, MA, 1999, pp.251--262.

[2] Pastor-Satorras R, Vazquez A, Vespignani A. Dynamical and correlation properties of the Internet. -\it Phys. Rev. Lett.}, 2001, 87: 258701.

[3] Vazquez A, Pastor-Satorras R, Vespignani A. Large-scale topological and dynamical properties of the Internet. -\it Phys. Rev. E.}, 2002, 65: 66130.

[4] Pastor-Satorras R, Vespignani A. Evolution and Structure of the Internet: A Statistical Physics Approach. Hardcover: Cambridge University Press, 2004.

[5] Ripeanu M. Peer-to-peer architecture case study: Gnutella network. Technical Report TR-2001-26, University of Chicago, 2001.

[6] Sen S, Wang J. Analyzing peer-to-peer traffic across large networks. -\it IEEE/ACM Transactions on Networking}, 2004, 12(2): 137--150.

[7] Barab\'asi A-L, Albert R. Emergence of scaling in random networks. -\it Science}, 1999, 286(5439): 509--512.

[8] Dorogovtsev S N, Mendes J F F. Evolution of Networks: From Biological Nets to the Internet and the WWW. Oxford, UK: Oxford University Press, 2003.

[9] Newman M. The structure and function of complex networks. -\it SIAM Review}, 2003, 45(2): 167--256.

[10] Bornholdt S, Schuster H G. Handbook of Graphs and Networks: From the Genome to the Internet. Germany: John Wiley-VCH, 2003.

[11] Albert R, Jeong H, Barab\'asi A-L. Error and attack tolerance of complex networks. -\it Nature}, 2000, 406: 378--382.

[12] Pastor-Satorras R, Vespignani A. Immunization of complex networks. -\it Phys. Rev. E.}, 2002, 65: 036104.

[13] Ratnasamy S, Francis P, Handley M -\it et al}. A scalable content-addressable network. In -\it Proc. SIGCOMM}, San Diego, CA, 2001, pp.161--172.

[14] Stoica I, Morris R, Karger D -\it et al}. Chord: A scalable peer-to-peer lookup service for Internet applications. In -\it Proc. SIGCOMM}, San Diego, CA, 2001, pp.161--172.

[15] Rowstron A, Druschel P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In -\it Proc. ACM Middleware}, Heidelberg, Germany, 2001, pp.329--350.

[16] Zhao B Y, Kubiatowicz J D, Joseph A D -\it et al}. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report CSD-01-1141, UC Berkeley, 2001.

[17] Manku G S, Bawa M, Raghavan P. Symphony: Distributed hashing in a small world. In -\it Proc. USITS}, Seattle, USA, 2003, pp.127--140.

[18] Gnutella. http://www.gnutella.wego.com/.

[19] Clarke I, Sandberg O, Wiley B -\it et al}. Freenet: A distributed anonymous information storage and retrieval system. In -\it Proc. International Workshop on Design Issues in Anonymity and Unobservability}, Berkeley, CA, 2001, pp.161--172.

[20] Jovanovic M, Annexstein F, Berman K. Modeling peer-to-peer network topologies through small-world models and power laws. In -\it Proc. Telecommunications Forum}, Belgrade, Yugoslavia, 2001, pp.161--172.

[21] Zhang H, Goel A, Govindan R. Using the small-world model to improve freenet performance. In -\it Proc. INFOCOM}, New York, USA, 2002, pp.1228--1237.

[22] Manku G S, Naor M, Wieder U. Know thy neighbor's neighbor: The power of lookahead in randomized P2P networks. In -\it Proc. STOC}, Chicago, USA, Jun. 2004, pp.54$\sim$63.

[23] Zhou L, Zhang L, McSherry F -\it et al}. A first look at peer-to-peer worms: Threats and defenses. In -\it Proc. IPTPS}, Ithaca, NY, 2005, pp.24--35.

[24] Chothia T, Chatzikokolakis K. A Survey of Anonymous Peer-to-Peer File-Sharing. In -\it Proc. NCUS}, Nagasaki, Japan, 2005, pp.744--755.

[25] Dezso Z, Barab\'asi A-L. Halting viruses in scale-free networks. -\it Phys. Rev. E.}, 2002, 65: 055103.

[26] Cohen R, Havlin S, Daniel ben-A. Efficient immunization strategies for computer networks and populations. -\it Phys. Rev. Lett.}, 2003, 91: 247901.

[27] Madar N, Kalisky T, Cohen R -\it et al}. Immunization and epidemics dynamics in complex networks. -\it Eur. Phys. J. B}, 2004, 38: 269--276.

[28] Echenique P, G\'omez-Gardenes J, Moreno Y -\it et al}. Distance-$d$ covering problem in scale-free networks with degree correlations. -\it Phys. Rev. E.}, 2005, 71: 035102.

[29] G\'omez-Gardenes J, Echenique P, Moreno Y. Immunization of real complex networks. -\it Eur. Phys. J. B}, 2006, 49: 259--264.

[30] Holme P. Efficient local strategies for vaccination and network attack. -\it Europhys. Lett.}, 2004, 68: 908--914.

[31] Moreno Y, Pastor-Satorras R, Vespignani A. Epidemic outbreaks in complex heterogeneous networks. -\it Eur. Phys. J. B}, 2002, 26: 521--529.

[32] Saroiu S, Gummadi P K, Gribble S D. A measurement study of peer-to-peer file sharing systems. In -\it Proc. MMCN}, San Jose, CA, 2002, pp.156$\sim$170.

[33] Adar E, Huberman B. Free Riding on Gnutella. Technical Report, Xerox PARC, Aug. 2000.

[34] Motter A E, Nishikawa T, Lai Y C. Range-based attack on links in scale-free networks: Are long-range links responsible for the small-world phenomenon. -\it Phys. Rev. E.}, 2002, 66: 065103.

[35] Holme P, Kim B J, Yoon C N -\it et al}. Attack vulnerability of complex networks. -\it Phys. Rev. E.}, 2002, 65: 056109.

[36] Newman M. Scientific collaboration networks, II: Shortest paths, weighted networks, and centrality. -\it Phys. Rev. E.}, 2001, 64: 016132.

[37] Goh K-I, Kahng B, Kim D. Universal behavior of load distribution in scale-free networks. -\it Phys. Rev. Lett.}, 2001, 87: 278701.

[38] Holme P. Congestion and centrality in traffic flow on complex networks. -\it Advances in Complex Systems}, 2003, 6: 163--176.

[39] Zhou S, Mondragon R J. Accurately modeling the Internet topology. -\it Phys. Rev. E.}, 2004, 70: 066108.

[40] Maslov S, Sneppen K, Zaliznyak A. Pattern detection in complex networks: Correlation profile of the Internet. -\it Physica A}, 2004, 333: 529--540.

[41] Newman M. Assortative mixing in networks. -\it Phys. Rev. Lett.}, 2002, 89: 208701.

[42] Clip2 Distributed Search Solutions. http://www.clip2.com.

[43] Crespo A, Molina H G. Semantic overlay networks for P2P systems. Technical Report, Stanford University, 2003.

[44] Jon Kleinberg. The small-world phenomenon: An algorithmic perspective. Technical Report TR99-1776, Cornell University, 1999.

[45] Williamson M. Throttling Viruses: Restricting propagation to defeat malicious mobile code. Technical Report HPL2002-172, HP Lab, 2002.

[46] Hethcote H W. Three basic epidemiological models. -\it Biomathematics}, 1989, 18: 119--144.

[47] Palmer C R, Steffan J G. Generating network topologies that obey power laws. In -\it Proc. GLOBECOM}, Pittsburgh, PA, 2000, pp.434--438.

[48] Xu J, Wang X F. Cascading failures in coupled map lattices. -\it Physica A}, 2005, 369: 685--692.
[1] Geun Yong Kim, Joon-Young Paik, Yeongcheol Kim, and Eun-Sun Cho. Byte Frequency Based Indicators for Crypto-Ransomware Detection from Empirical Analysis [J]. Journal of Computer Science and Technology, 2022, 37(2): 423-442.
[2] Ying-Jie Wang, Liang-Ze Yin, Wei Dong. AMCheX: Accurate Analysis of Missing-Check Bugs for Linux Kernel [J]. Journal of Computer Science and Technology, 2021, 36(6): 1325-1341.
[3] Gen Zhang, Peng-Fei Wang, Tai Yue, Xu Zhou, Kai Lu. MEBS: Uncovering Memory Life-Cycle Bugs in Operating System Kernels [J]. Journal of Computer Science and Technology, 2021, 36(6): 1248-1268.
[4] Jingwen Xu, Yanhong Huang, Jianqi Shi, Shengchao Qin. A Multi-Agent Spatial Logic for Scenario-Based Decision Modeling and Verification in Platoon Systems [J]. Journal of Computer Science and Technology, 2021, 36(6): 1231-1247.
[5] Yi Zhong, Jian-Hua Feng, Xiao-Xin Cui, Xiao-Le Cui. Machine Learning Aided Key-Guessing Attack Paradigm Against Logic Block Encryption [J]. Journal of Computer Science and Technology, 2021, 36(5): 1102-1117.
[6] Einollah Pira. Using Markov Chain Based Estimation of Distribution Algorithm for Model-Based Safety Analysis of Graph Transformation [J]. Journal of Computer Science and Technology, 2021, 36(4): 839-855.
[7] Yuan Li, Xing-Chen Wang, Lin Huang, Yun-Lei Zhao. Order-Revealing Encryption: File-Injection Attack and Forward Security [J]. Journal of Computer Science and Technology, 2021, 36(4): 877-895.
[8] Zhao-Yang Wang, Bei-Hong Jin, Tingjian Ge, Tao-Feng Xue. Detecting Anomalous Bus-Driving Behaviors from Trajectories [J]. Journal of Computer Science and Technology, 2020, 35(5): 1047-1063.
[9] Zachary P. Languell, Qijun Gu. A Multi-Point Distance-Bounding Protocol for Securing Automatic Dependent Surveillance-Broadcast in Unmanned Aerial Vehicle Applications [J]. Journal of Computer Science and Technology, 2020, 35(4): 825-842.
[10] Lie-Huang Zhu, Bao-Kun Zheng, Meng Shen, Feng Gao, Hong-Yu Li, Ke-Xin Shi. Data Security and Privacy in Bitcoin System: A Survey [J]. Journal of Computer Science and Technology, 2020, 35(4): 843-862.
[11] Ge Wu, Jian-Chang Lai, Fu-Chun Guo, Willy Susilo, Fu-Tai Zhang. Tightly Secure Public-Key Cryptographic Schemes from One-More Assumptions [J]. Journal of Computer Science and Technology, 2019, 34(6): 1366-1379.
[12] Chong Wang, Nasro Min-Allah, Bei Guan, Yu-Qi Lin, Jing-Zheng Wu, Yong-Ji Wang. An Efficient Approach for Mitigating Covert Storage Channel Attacks in Virtual Machines by the Anti-Detection Criterion [J]. Journal of Computer Science and Technology, 2019, 34(6): 1351-1365.
[13] Jie Xiao, Zhan-Hui Shi, Jian-Hui Jiang, Xu-Hua Yang, Yu-Jiao Huang, Hai-Gen Hu. A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm [J]. Journal of Computer Science and Technology, 2019, 34(5): 1136-1151.
[14] Jianjun Zheng, Akbar Siami Namin. A Survey on the Moving Target Defense Strategies: An Architectural Perspective [J]. Journal of Computer Science and Technology, 2019, 34(1): 207-233.
[15] Ping Zhang, Hong-Gang Hu. Generalized Tweakable Even-Mansour Cipher and Its Applications [J]. Journal of Computer Science and Technology, 2018, 33(6): 1261-1277.
Full text



No Suggested Reading articles found!

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved