SybilGuard: defending against sybil attacks via social networks

ABSTRACT

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks. In a sybil attack, a malicious user obtains multiple fake identities and pretends to be multiple, distinct nodes in the system. By controlling a large fraction of the nodes in the system, the malicious user is able to "out vote" the honest users in collaborative tasks such as Byzantine failure defenses. This paper presents SybilGuard, a novel protocol for limiting the corruptive influences of sybil attacks. Our protocol is based on the "social network" among user identities, where an edge between two identities indicates a human-established trust relationship. Malicious users can create many identities but few trust relationships. Thus, there is a disproportionately small "cut" in the graph between the sybil nodes and the honest nodes. SybilGuard exploits this property to bound the number of identities a malicious user can create. We show the effectiveness of SybilGuard both analytically and experimentally.

REFERENCES

• 1: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 2: Anirudh Ramachandran , Nick Feamster, Understanding the network-level behavior of spammers, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 3: L. von Ahn, M. Blum, N. J. Hopper, and J. Langford, "CAPTCHA: Using hard AI problems for security," in Proc. Eurocrypt 2003, Warsaw, Poland, May 2003, pp. 294-311.
• 4: Rida A. Bazzi , Goran Konjevod, On the establishment of distinct identities in overlay networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073873]
• 5: T. S. E. Ng and H. Zhang, "Predicting Internet network distance with coordinates-based approaches," in Proc. IEEE INFOCOM 2002, New York, NY, Jun. 2002, pp. 170-179.
• 6: Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham Flaxman, SybilGuard: defending against sybil attacks via social networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 7: H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao, "SybilLimit: A near-optimal social network defense against sybil attacks," in Proc. 2008 IEEE Symp. Security and Privacy, Oakland, CA, May 2008, pp. 3-17.
• 8: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 9: M. Mitzenmacher and E. Upfal, Probability and Computing. Cambridge, U.K.: Cambridge Univ. Press, 2005.
• 10: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Gossip algorithms: Design, analysis and applications," in Proc. IEEE INFOCOM 2005, Miami, FL, Mar. 2005, pp. 1653-1664.
• 11: A. Flaxman, "Expansion and lack thereof in randomly perturbed graphs," Microsoft Research, Redmond, WA, Tech. Rep. MSR-TR-2006-118, Aug. 2006 [Online]. Available: ftp://ftp.research.microsoft.com/pub/tr/TR-2006-118.pdf
• 12: Ittai Abraham , Dahlia Malkhi, Probabilistic quorums for dynamic systems, Distributed Computing, v.18 n.2, p.113-124, December 2005 [doi>10.1007/s00446-005-0139-2]
• 13: Ruggero Morselli , Bobby Bhattacharjee , Aravind Srinivasan , Michael A. Marsh, Efficient lookup on unstructured topologies, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073828]
• 14: H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman, "SybilGuard: Defending against sybil attacks via social networks," Intel Research Pittsburgh, Pittsburgh, PA, Tech. Rep. IRP-TR-06-01, Jun. 2006 [On-line]. Available: http://www.comp.nus.edu.sg/~yuhf/sybilguard-tr.pdf
• 15: William J. Bolosky , John R. Douceur , David Ely , Marvin Theimer, Feasibility of a serverless distributed file system deployed on an existing set of desktop PCs, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.34-43, June 18-21, 2000, Santa Clara, California, United States
• 16: International Network for Social Network Analysis. 2006 [Online]. Available: http://www.insna.org/INSNA/data_inf.htm
• 17: Center for Computational Analysis of Social and Organizational Systems (CASOS). 2006 [Online]. Available: http://www.casos.cs.cmu. edu/computational_tools/data.php
• 18: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 19: D. J. Watts and S. H. Strogatz, "Collective dynamics of "small-world" networks," Nature, vol. 393, no. 6684, 1998.
• 20: Naveen Sastry , Umesh Shankar , David Wagner, Secure verification of location claims, Proceedings of the 2nd ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941313]
• 21: G. Danezis, C. Lesniewski-Laas, M. F. Kaashoek, and R. Anderson, "Sybil-resistant DHT routing," in Proc. European Symp. Research in Computer Security (ESORICS 2005), Milan, Italy, Sep. 2005, pp. 305-318.
• 22: James Newsome , Elaine Shi , Dawn Song , Adrian Perrig, The sybil attack in sensor networks: analysis & defenses, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984660]
• 23: Bryan Parno , Adrian Perrig , Virgil Gligor, Distributed Detection of Node Replication Attacks in Sensor Networks, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.49-63, May 08-11, 2005 [doi>10.1109/SP.2005.8]
• 24: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080202]
• 25: Michal Feldman , Kevin Lai , Ion Stoica , John Chuang, Robust incentive techniques for peer-to-peer networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988788]
• 26: M. Richardson, R. Agrawal, and P. Domingos, "Trust management for the semantic web," in Proc. 2nd Int. Semantic Web Conf. (ISWC2003), Sanibel Island, FL, Oct. 2003, pp. 351-368.
• 27: Kevin Walsh , Emin Gün Sirer, Experience with an object reputation system for peer-to-peer filesharing, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.1-1, May 08-10, 2006, San Jose, CA
• 28: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 29: A. Mislove, A. Post, K. Gummadi, and P. Druschel, "Ostra: Leveraging trust to thwart unwanted communication," in Proc. 5th USENIX Symp. Networked Systems Design and Implementation (NSDI 2008), San Francisco, CA, Apr. 2008, pp. 15-30.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring; Network management

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

Keywords:
SybilGuard, social networks, sybil attack, sybil identity