Fireflies: scalable support for intrusion-tolerant network overlays

ABSTRACT

This paper describes and evaluates Fireflies, a scalable protocol for supporting intrusion-tolerant network overlays. While such a protocol cannot distinguish Byzantine nodes from correct nodes in general, Fireflies provides correct nodes with a reasonably current view of which nodes are live, as well as a pseudo-random mesh for communication. The amount of data sent by correct nodes grows linearly with the aggregate rate of failures and recoveries, even if provoked by Byzantine nodes. The set of correct nodes form a connected submesh; correct nodes cannot be eclipsed by Byzantine nodes. Fireflies is deployed and evaluated on PlanetLab.

References

1. A. Adya, W. J. Bolosky, M. Castro, G. Cermak, R. Chaiken, J. R. Douceur, J. Howell, J. R. Lorch, M. Theimer, and R. P. Wattenhofer. FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment. In Proc. of the 5th Symp. on Operating Systems Design and Implementation, Boston, MA, December 2002. USENIX.
2. T. Anker, G. V. Chockler, D. Dolev, and I. Keidar. Scalable group membership services for novel applications. In M. Mavronicolas, M. Merritt, and N. Shavit, editors, Proc. of the Workshop on Networks in Distributed Computing, pages 23--42. DIMACS, 1998.
3. G. Badishi, I. Keidar, and A. Sasson. Exposing and eliminating vulnerabilities to Denial of Service attacks in secure gossip-based multicast. In Proc. of the International Conference on Dependable Systems and Networks (DSN), pages 201--210, June - July 2004.
4. M. Castro, P. Druschel, A. Ganesh, A. Rowstron, and D. S. Wallach. Secure routing for structured peer-to-peer overlay networks. In Proc. of the 5th Usenix Symposium on Operation System Design and Implementation (OSDI), Boston, MA, December 2002.
5. F. Chung and L. Lu. The diameter of random sparse graphs. Advances in Applied Math, 26(4):257--279, May 2001.
6. M. Costa, J. Crowcroft, M. Castro, A. Rowstron, L. Zhou, L. Zhang, and P. Barham. Vigilante: End-to-end containment of Internet worms. In Proc. of the 20th ACM Symp. on Operating Systems Principles, Brighton, UK, October 2005.
7. A. Das, I. Gupta, and A. Motivala. SWIM: Scalable Weakly-consistent Infection-style process group Membership. In Proc. of the Int. Conf. on Dependable Systems and Networks DSN 02, pages 303--312, Washington, DC, June 2002.
8. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proc. of the 6th ACM Symp. on Principles of Distributed Computing, pages 1--12, Vancouver, BC, August 1987.
9. J. Douceur. The Sybil attack. In Proc. of the 1st Int. Workshop on Peer-to-Peer Systems, Cambridge, MA, March 2002.
10. J. R. Douceur and J. Howell. Byzantine fault isolation in the Farsite distributed file system. In Proc. of the 5th Int. Workshop on Peer-To-Peer Systems, Santa Barbara, CA, February 2006.
11. P. Erdös and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Közl, 5(17):17--61, 1960.
12. M. J. Freedman, I. Stoica, D. Mazières, and S. Shenker. Group therapy for systems: Using link attestations to manage failures. In Proc. of the 5th Int. Workshop on Peer-To-Peer Systems, Santa Barbara, CA, February 2006.
13. A. J. Ganesh, A.-M. Kermarrec, and L. Massoulié. SCAMP: Peer-to-peer lightweight membership service for large-scale group communication. In Proc. of the 3rd International Workshop on Networked Group Communication, London, UK, November 2001.
14. A. Gupta, B. Liskov, and R. Rodrigues. One hop lookups for peer-to-peer overlays. In Proc. of the 9th Workshop on Hot Topics in Operating Systems (HotOS-IX), pages 7--12, Lihue, HI, May 2003.
15. A. Gupta, B. Liskov, and R. Rodrigues. Efficient routing for peer-to-peer overlays. In Proc. of the 1st Symp. on Networked Systems Design and Implementation, San Francisco, CA, March 2004.
16. F. Harary. The maximum connectivity of a graph. In Proc. of the National Academy of Sciences, volume 48, pages 1142--1146, 1962.
17. A.-M. Kermarrec, L. Massoulié, and A. J. Ganesh. Probabilistic reliable dissemination in large-scale systems. IEEE Transactions on Parallel and Distributed Systems, 14(3), March 2003.
18. J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for global-scale persistent storage. In Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, November 2000.
19. C. S. Lewis and L. Saia. Scalable byzantine agreement. Technical report, CS Dept., University of New Mexico, 2004.
20. M.-J. Lin, K. Marzullo, and S. Masini. Gossip versus deterministically constrained flooding on small networks. In Proc. of the 14th Int. Conf. on Distributed Computing, volume 1914 of Lecture Notes in Computer Science, pages 253--267. Springer, 2000.
21. D. Malkhi, Y. Mansour, and M. K. Reiter. On diffusing updates in a Byzantine environment. In Symposium on Reliable Distributed Systems, pages 134--143, Lausanne, Switzerland, October 1999.
22. Y. Minsky, A. Trachtenberg, and R. Zippel. Set reconciliation with nearly optimal communication complexity. IEEE Transactions on Information Theory, 49(9):2212--2218, September 2003.
23. V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, and A. E. Mohr. Chainsaw: Eliminating trees from overlay multicast. In Proc. of the 4th Int. Workshop on Peer-To-Peer Systems, Ithaca, NY, February 2005.
24. L. Peterson, S. Shenker, and J. Turner. Overcoming the Internet impasse through virtualization. In Third Workshop on Hot Topics in Networking (HotNets-III), San Diego, CA, November 2004.
25. P. Pietzuch, J. Shneidman, J. Ledlie, M. Welsh, M. Seltzer, and M. Roussopoulos. Evaluating DHT-based service placement for stream-based overlays. In Proc. of the 4th Int. Workshop on Peer-To-Peer Systems, Ithaca, NY, February 2005.
26. K. Potter Kihlstrom, L. E. Moser, and P. M. Melliar-Smith. The SecureRing protocols for securing group communication. In Proc. of the the 31st Hawaii Int. Conf. on System Sciences, volume 3, pages 317--326, Kona, HI, January 1998.
27. M. K. Reiter. A secure group membership protocol. IEEE Transactions on Software Engineering, 22(1):31--42, January 1996.
28. R. Rodrigues and C. Blake. When multi-hop peer-to-peer routing matters. In Proc. of the 3rd Int. Workshop on Peer-to-Peer Systems, La Jolla, CA, February 2004.
29. A. Singh, M. Castro, P. Druschel, and A. Rowstron. Defending against Eclipse attacks on overlay networks. In Proc. of the 11th European SIGOPS Workshop, Leuven, Belgium, September 2004. ACM.
30. E. Sit and R. T. Morris. Security considerations for peer-to-peer distributed hash tables. In Proc. of the 1st Int. Workshop on Peer-To-Peer Systems, Cambridge, MA, March 2002.
31. R. van Renesse, Y. Minsky, and M. Hayden. A gossip-style failure detection service. In Proc. of Middleware. 98, pages 55--70, The Lake District, UK, September 1998. IFIP.
32. S. Voulgaris, D. Gavidia, and M. van Steen. CYCLON: Inexpensive membership management for unstructured P2P overlays. Journal of Network and Systems Management, 13(2), June 2005. Special issue on Self-Managing Systems and Networks.
33. L. Zhou and R. van Renesse. P6P: A peer-to-peer approach to Internet infrastructure. In Proc. of the 3rd Int. Workshop on Peer-To-Peer Systems, San Diego, CA, February 2004.