A DoS-resilient information system for dynamic data management

ABSTRACT

Denial of service (DoS) attacks are arguably one of the most cumbersome problems in the Internet. This paper presents a distributed information system (over a set of completely connected servers) called Chameleon which is robust to DoS attacks on the nodes as well as the operations of the system. In particular, it allows nodes to efficiently look up and insert data items at any time, despite a powerful "past-insider adversary" which has complete knowledge of the system up to some time point t₀ and can use that knowledge in order to block a constant fraction of the nodes and inject lookup and insert requests to selected data. This is achieved with a smart randomized replication policy requiring a polylogarithmic overhead only and the interplay of a permanent and a temporary distributed hash table. All requests in Chameleon can be processed in polylogarithmic time and work at every node.

REFERENCES

• 1: Baruch Awerbuch , Christian Scheideler, Towards a scalable and robust DHT, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148163]
• 2: B. Awerbuch and C. Scheideler. A Denial-of-Service Resistant DHT. In Proc. 21st International Symposium on Distributed Computing (DISC), 2007.
• 3: D. Bernstein. SYN Cookies. In http://cr.yp.to/syncookies.html, 2008.
• 4: Ankur Bhargava , Kishore Kothapalli , Chris Riley , Christian Scheideler , Mark Thober, Pagoda: a dynamic overlay network for routing, data management, and multicasting, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007938]
• 5: Jelena Mirkovic , Sven Dietrich , David Dittrich , Peter Reiher, Internet Denial of Service: Attack and Defense Mechanisms (Radia Perlman Computer Networking and Security), Prentice Hall PTR, Upper Saddle River, NJ, 2004
• 6: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 7: Nicholas J. A. Harvey , Michael B. Jones , Stefan Saroiu , Marvin Theimer , Alec Wolman, SkipNet: a scalable overlay network with practical locality properties, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.9-9, March 26-28, 2003, Seattle, WA
• 8: J. Ioannidis and S. M. Bellovin. Implementing Pushback: Router-Based Defense Against DDoS Attacks. In Proc. Network and Distributed System Security Symposium (NDSS), 2002.
• 9: Srikanth Kandula , Dina Katabi , Matthias Jacob , Arthur Berger, Botz-4-sale: surviving organized DDoS attacks that mimic flash crowds, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.287-300, May 02-04, 2005
• 10: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 11: Frank Kargl , Joern Maier , Michael Weber, Protecting web servers from distributed denial of service attacks, Proceedings of the 10th international conference on World Wide Web, p.514-524, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372148]
• 12: Angelos D. Keromytis , Vishal Misra , Dan Rubenstein, SOS: secure overlay services, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 13: George Lawton, Stronger Domain Name System Thwarts Root-Server Attacks, Computer, v.40 n.5, p.14-17, May 2007 [doi>10.1109/MC.2007.184]
• 14: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 15: Mazu Networks Inc. http://mazunetworks.com. 2008.
• 16: McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 195--247. Springer Verlag, Berlin, 1998.
• 17: Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
• 18: Jelena Mirkovic , Peter Reiher, A taxonomy of DDoS attack and DDoS defense mechanisms, ACM SIGCOMM Computer Communication Review, v.34 n.2, April 2004 [doi>10.1145/997150.997156]
• 19: William G. Morein , Angelos Stavrou , Debra L. Cook , Angelos D. Keromytis , Vishal Misra , Dan Rubenstein, Using graphic turing tests to counter automated DDoS attacks against web servers, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948114]
• 20: Moni Naor , Udi Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Transactions on Algorithms (TALG), v.3 n.3, p.34-es, August 2007 [doi>10.1145/1273340.1273350]
• 21: George Oikonomou , Jelena Mirkovic , Peter Reiher , Max Robinson, A Framework for a Collaborative DDoS Defense, Proceedings of the 22nd Annual Computer Security Applications Conference, p.33-42, December 11-15, 2006 [doi>10.1109/ACSAC.2006.5]
• 22: Venkata N. Padmanabhan , Kunwadee Sripanidkulchai, The Case for Cooperative Networking, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.178-190, March 07-08, 2002
• 23: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 24: E. Ratliff. The Zombie Hunters. In The New Yorker, 2005.
• 25: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 26: C. Scheideler. Probabilistic Methods for Coordination Problems. HNI-Verlagsschriftenreihe 78, University of Paderborn, 2000.
• 27: Tyron Stading , Petros Maniatis , Mary Baker, Peer-to-Peer Caching Schemes to Address Flash Crowds, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.203-213, March 07-08, 2002
• 28: Angelos Stavrou , Dan Rubenstein , Sambit Sahu, A Lightweight, Robust P2P System to Handle Flash Crowds, Proceedings of the 10th IEEE International Conference on Network Protocols, p.226-235, November 12-15, 2002
• 29: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 30: I. Stoica, R. Morris, D. Liben-Nowell, D. Karger, M. F. Kaashoek, F. Dabek, and H. Kalakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Technical Report MIT, 2002.
• 31: M. Walfish, H. Balakrishnan, D. Karger, and S. Shenker. DoS: Fighting Fire with Fire. In Proc. Workshop on Hot Topics in Networks (HotNets), 2005.
• 32: Michael Walfish , Mythili Vutukuru , Hari Balakrishnan , David Karger , Scott Shenker, DDoS defense by offense, ACM SIGCOMM Computer Communication Review, v.36 n.4, October 2006
• 33: Xiaowei Yang , David Wetherall , Thomas Anderson, A DoS-limiting network architecture, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Theory

Keywords:
DHTS, denial of service attacks, peer-to-peer systems, replication