Sybil defenses via social networks: a tutorial and survey

Abstract

The sybil attack in distributed systems refers to individual malicious users joining the system multiple times under multiple fake identities. Sybil attacks can easily invalidate the overarching prerequisite of many fault-tolerant designs which assume that the fraction of malicious nodes is not too large. This article presents a tutorial and survey on effective sybil defenses leveraging social networks. Since this approach of sybil defenses via social networks was introduced 5 years ago, it has attracted much more attention from the research community than many other alternatives. We will first explain the intuitions and insights behind this approach, and then survey a number of specific sybil defense mechanisms based on this approach, including SybilGuard, SybilLimit, SybilInfer, Gatekeeper, SumUp, Whanau, and Ostra. We will also discuss some practical implications and deployment considerations of this approach.

References

1. R. Bazzi and G. Konjevod. On the establishment of distinct identities in overlay networks. In ACM PODC, 2005.
2. L. Bilge, T. Strufe, D. Balzarotti, and E. Kirda. All your contacts are belong to us: Automated identity theft attacks on social networks. In WWW, Apr. 2009.
3. E. Bortnikov, M. Gurevich, I. Keidar, G. Kliot, and A. Shraer. Brahms: Byzantine Resilient Random Membership Sampling. Computer Networks, 53(13), 2009.
4. S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: Design, analysis and applications. In IEEE INFOCOM, 2005.
5. A. Cheng and E. Friedman. Sybilproof reputation mechanisms. In ACM P2PEcon, 2005.
6. A. Cheng and E. Friedman. Manipulability of PageRank under Sybil Strategies. In Proceedings of the First Workshop of Networked Systems, 2006.
7. G. Danezis, C. Lesniewski-Laas, M. F. Kaashoek, and R. Anderson. Sybil-resistant DHT routing. In ESORICS, 2005. Springer-Verlag LNCS 3679.
8. G. Danezis and P. Mittal. SybilInfer: Detecting Sybil Nodes using Social Networks. In NDSS, 2009.
9. J. Douceur. The Sybil attack. In IPTPS, 2002.
10. M. Feldman, K. Lai, I. Stoica, and J. Chuang. Robust incentive techniques for peer-to-peer networks. In ACM Electronic Commerce, 2004.
11. A. Flaxman. Expansion and Lack Thereof in Randomly Perturbed Graphs. In International Workshop on Algorithms and Models for the Web-Graph, 2006.
12. S. Fortunato. Community detection in graphs. Physics Reports, 486(3-5), 2010.
13. M. Gurevich and I. Keidar. Correctness of Gossip-Based Membership under Message Loss. SIAM Journal on Computing, 39(8), 2010.
14. J. Kleinberg. The small-world phenomenon: An algorithmic perspective. In ACM STOC, 2000.
15. J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Statistical properties of community structure in large social and information networks. In WWW, 2008.
16. C. Lesniewski-Laas and M. F. Kaashoek. Whanau: A Sybil-proof Distributed Hash Table. In NSDI, Apr. 2010.
17. Q. Lian, Z. Zhang, M. Yang, B. Y. Zhao, Y. Dai, and X. Li. An empirical study of collusion behavior in the Maze P2P file-sharing system. In IEEE ICDCS, 2007.
18. A. Mislove, A. Post, P. Druschel, and K. Gummadi. Ostra: Leveraging trust to thwart unwanted communication. In NSDI, 2008.
19. A. Mohaisen, A. Yun, and Y. Kim. Measuring the mixing time of social graphs. In IMC, 2010.
20. J. Newsome, E. Shi, D. Song, and A. Perrig. The Sybil attack in sensor networks: Analysis & defenses. In ACM/IEEE IPSN, 2004.
21. B. Parno, A. Perrig, and V. Gligor. Distributed detection of node replication attacks in sensor networks. In IEEE S & P, 2005.
22. C. Scheideler. How to spread adversarial nodes? Rotate! In STOC, 2005.
23. N. Tran, J. Li, L. Subramanian, and S. Chow. Optimal Sybil-resilient Node Admission Control. In INFOCOM, Apr. 2011.
24. N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In NSDI, 2009.
25. B. Viswanath, A. Post, K. Gummadi, and A. Mislove. An Analysis of Social Network-based Sybil Defenses. In SIGCOMM, August 2010.
26. M. Yang, Z. Zhang, X. Li, and Y. Dai. An empirical study of free-riding behavior in the Maze P2P file-sharing system. In IPTPS, 2005.
27. H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao. SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks. Technical Report TRA2/08, National University of Singapore, School of Computing, March 2008. http://www.comp.nus.edu.sg/¿yuhf/sybillimit-tr.pdf.
28. H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao. SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks. IEEE/ACM Transactions on Networking, June 2010. Preliminary version appeared in IEEE Symposium on Security and Privacy 2008.
29. H. Yu, P. B. Gibbons, and C. Shi. Brief Announcement: Sustaining Collaboration in Multicast despite Rational Collusion. In PODC, 2011.
30. H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman. SybilGuard: Defending Against Sybil Attacks via Social Networks. IEEE/ACM Transactions on Networking, June 2008. Preliminary version appeared in ACM SIGCOMM Conference 2006.
31. H. Yu, C. Shi, M. Kaminsky, P. B. Gibbons, and F. Xiao. DSybil: Optimal Sybil-Resistance for Recommendation Systems. In IEEE Symposium on Security and Privacy, May 2009.

Index Terms

• General and reference

  • Document types

    • Surveys and overviews

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Web-based interaction

• Information systems

  • Information retrieval

  • Information storage systems