George Dean Bissias
Brian Neil Levine
ABSTRACT
Client-server networks are pervasive, fundamental, and include such key networks as the Internet, power grids, and road networks. In a client-server network, clients obtain a service by connecting to one of a redundant set of servers. These networks are vulnerable to node and link failures, causing some clients to become disconnected from the servers. We develop algorithms that quantify and bound the inherent vulnerability of a clientserver network using semidefinite programming (SDP) and branch-and-cut techniques. Further, we develop a divide-and-conquer algorithm that solves the problem for large graphs. We use these techniques to show that: for the Philippine Power Grid removing just over 6% of the transmission lines will disconnect at least 20% but not more than 50% of the substations from all generators; on a large wireless mesh network disrupting 5% of wireless links between relays removes Internet access for half the relays; even after any 16% of Tier 2 ASes are removed, more than 50% of the remaining Tier 2 ASes will be connected to the Tier 1 backbone; when 300 roadblocks are erected in Michigan, it's possible to disconnect 28--43% of the population from all airports.
- http://sedac.ciesin.columbia.edu.Google Scholar
- http://www-cta.ornl.gov/transnet/Highways.html.Google Scholar
- http://www.haciendacdc.org.Google Scholar
- http://www.ngcp.ph/gridmap/2k6gridmap.pdf.Google Scholar
- http://www.socrata.com.Google Scholar
- M. Amin. Security challenges for the electricity infrastructure. IEEE Computer, 35(4):8--10, Aug 2002. Google ScholarDigital Library
- M. Amin. North America's electricity infrastructure: are we ready for more perfect storms? IEEE Security & Privacy, 1(5):19--25, 2003. Google ScholarDigital Library
- S. Aref and B. Miller. Damage Information and Reporting Tool. Technical report, Common Ground Alliance, 2005.Google Scholar
- C. Berrick, S. Morris, and G. Malavenda. Federal highway report. Technical report, USGAO, 2009.Google Scholar
- G. D. Bissias, B. N. Levine, and R. K. Sitaraman. Finding Weak Points in Networks. Technical Report UM-CS-2010-037, UMass Amherst, 2010.Google Scholar
- T. Bui and C. Jones. Finding good approximate vertex and edge partitions is NP-hard. Info. Proc. Lett., 42(3), 1992. Google ScholarDigital Library
- R. Cohen, K. Erez, D. ben Avraham, and S. Havlin. Breakdown of the Internet under Intentional Attack. Phys. Rev. Lett., 86(16):3682--3685, Apr 2001.Google ScholarCross Ref
- X. Dimitropoulos, D. Krioukov, G. Riley, and K. Claffy. Revealing the Autonomous System Taxonomy. In Proc. PAM Conference, March 2006.Google Scholar
- C. Ding, X. He, and H. Zha. A spectral method to separate disconnected and nearly-disconnected web graph components. In Proc. ACM SIGKDD, pages 275--280, 2001. Google ScholarDigital Library
- A. Flaxman, A. Frieze, and J. Vera. Adversarial deletion in a scale free random graph process. In Proc. ACM-SIAM SODA, pages 287--292, 2005. Google ScholarDigital Library
- S. Gorman, L. Schintler, R. Kulkarni, and R. Stough. The revenge of distance. Jrnl Cont. and Crisis Mgmt., 12(2):48--63, 2004.Google ScholarCross Ref
- J.-L. Guillaume, M. Latapy, and C. Magnien. Comparison of Failures and Attacks on Random and Scale-Free Networks. In Proc. OPODIS, pages 186--196, Dec 2004. Google ScholarDigital Library
- C. Helmberg. Semidefinite programming. European Journal of Operational Research, 3(137):461--482, 2002.Google ScholarCross Ref
- A. Hickson. Terrorist Threat to U.S. Highway System. Technical report, U.S. DHS, June 2006.Google Scholar
- S. Kent, C. Lynn, J. Mikkelson, and K. Seo. Secure Border Gateway Protocol (S-BGP). In Proc. ISOC NDSS, Feb 2000.Google ScholarDigital Library
- Y. Law et al. Energy-efficient link-layer jamming attacks against wireless sensor network MAC protocols. In Proc. ACM SASN, pages 76--88, 2005. Google ScholarDigital Library
- D. Magoni. Tearing down the Internet. IEEE JSAC, 21(6):949--960, 2003. Google ScholarDigital Library
- S. Murphy. BGP Security Vulnerabilities Analysis. Technical report, IETF draft, February 2002.Google Scholar
- A. Perrig, J. Stankovic, and D. Wagner. Security in wireless sensor networks. Commun. ACM, 47(6):53--57, 2004. Google ScholarDigital Library
- K. Poulsen. The Backhoe: A Real Cyberthreat. Wired magazine, Jan 2006.Google Scholar
- P. Pourbeik, P. Kundur, and C. Taylor. The anatomy of a power grid blockout. IEEE Power & Energy Magazine, 4(5):22--29, 2006.Google ScholarCross Ref
- A. Rosenberg and L. Heath. Graph Separators with Applications. Springer, 2001. Google ScholarDigital Library
- B. Smith and J. J. Garcia. Securing the Border Gateway Routing Protocol. In Proc. Global Internet, Nov. 1996.Google ScholarCross Ref
- D. Watts. Security and vulnerability in electric power systems. In Proc. North American Power Symp, pages 559--566, Oct 2003.Google Scholar
- H. Wolkowicz and Q. Zhao. Semidefinite Programming Relaxations for the Graph Partitioning Problem. Discrete Applied Mathematics, 96--97:461--479, 1999. Google ScholarDigital Library
- W. Xu, W. Trappe, Y. Zhang, and T. Wood. The Feasibility of Launching and Detecting Jamming Attacks in Wireless Networks. In Proc. ACM Mobihoc, pages 46--57, May 2005. Google ScholarDigital Library
- H. Yang, H. Luo, F. Ye, S. Lu, and L. Zhang. Security in mobile ad hoc networks: challenges and solutions. Wireless Communications, IEEE, 11(1):38--47, Feb. 2004. Google ScholarDigital Library
- S. Zhou and R. Mondragon. Redundancy and robustness of AS-level Internet topology and its models. Electronics Letters, 40(2):151--152, 2004.Google ScholarCross Ref
Index Terms
- Assessing the vulnerability of replicated network services
Recommendations
A paracasting model for concurrent access to replicated Internet content
In this paper, we develop a model to study how to effectively download a document from a set of replicated servers. We propose a generalized application-layer anycasting protocol, known as paracasting, to advocate concurrent access of a subset of ...
Client-Access Protocols for Replicated Services
This paper addresses the problem of replicated service provision in distributed systems. Existing systems that follow the State Machine approach concentrate on the synchronization of the server replicas and do not consider the problem of client ...
Client--Access Protocols for Replicated Services
ICECCS '97: Proceedings of the Third IEEE International Conference on Engineering of Complex Computer SystemsThe paper addresses the problem of client--service interaction in the case of replicated service provision. Existing systems that follow the State Machine approach concentrate on the synchronization of the server replicas and do not consider the problem ...
Comments