SybilGuard: Defending Against Sybil Attacks via Social Networks

By Haifeng Yu, Michael Kaminsky, Phillip B. Gibbons, Abraham D. Flaxman. 2006

1,222 citations recorded by the source corpus.

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 ldquoout voterdquo 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 ldquosocial networkrdquo 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 ldquocutrdquo 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.

Subfields: Computer Networks and Communications, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

Citations in the corpus

Mitigating Sybils in Federated Learning Poisoning (2018, background): “To mitigate malicious clients in federated learning, existing solutions assume either costly third party user verification control [10], [37] or use explicit parameterization of the expected number of sybils [9].”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “Standard defenses [3, 114, 124, 125] against Sybil attacks [52] would apply here.”
Proactively Accountable Anonymous Messaging in Verdict (2012, background): “Dynamic group management schemes could leverage existing Sybil prevention techniques [47, 53, 54], but we do not consider such approaches herein.”
EVILCOHORT: Detecting Communities of Malicious Accounts on Online Services (2015, background): “On the other hand, E VIL C OHORT can detect an account (or an IP address) as malicious even if the account does not post any content on the online service.”
User interactions in social networks and their implications (2009, background): “While these applications often cite social network connectivity statistics to support their designs, researchers in psychology and sociology have repeatedly cast doubt on the practice of inferring meaningful relationships from social network connections alone.”
Trafficking Fraudulent Accounts: The Role of the Underground Market in Twitter Spam and Abuse (2013, background): “With no central operation of the underground market, we resort to investigating common haunts: advertisements via search engines, blackhat forums such as blackhat-world.com , and freelance labor pages including Fiverr and Freelancer [20, 21].”
Random Walk Based Fake Account Detection in Online Social Networks (2017, methodology): “, social network based Sybil defense in peer-to-peer and distributed systems [6], and social network based anonymous communications [30].”
An analysis of social network-based Sybil defenses (2010, methodology): “A number of schemes have been proposed that attempt to defend against Sybils in a social network by using properties of the social network’s structure [7,29,32,33].”
Sybil Attacks and Their Defenses in the Internet of Things (2014, methodology): “Sybil identification can detect whether a node is Sybil or not, similar to the existing SNSD schemes.”
SybilInfer: Detecting Sybil Nodes using Social Networks (2009, background): “In our case the random walk is performed over a slightly modified version of the social graph, where the transition probability attached to each link ij is: Pij = { min( 1di , 1 dj ) if i→ j is an edge in G 0 otherwise , which guarantees that the stationary distribution is uniform over all nodes…”
SybilBlind: Detecting Fake Users in Online Social Networks without Manual Labels (2018, methodology): “This assumption is required by all previous structurebased methods [39,38,8,26,7,36,6,14,30,33] except Íntegro [6].”
Adversarial Attacks on Node Embeddings via Graph Poisoning (2018, background): “Manipulating the network structure (the graph) is a common scenario with link spam farms (Gyöngyi & Garcia-Molina, 2005) and Sybil attacks (Yu et al., 2006) as typical examples.”
An inquiry into the nature and causes of the wealth of internet miscreants (2007, background): “One approach would be to detect anomalous recommendation topologies [21], but this would require a sophisticated system for tracking interactions o ver time.”
A SURVEY ON TRUST MANAGEMENT FOR MOBILE AD HOC NETWORKS (2010, methodology): “[24] used social networks to evaluate the overall trust value of a node.”
Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation (2018, methodology): “SybilGuard [9] Oðg ffiffiffiffiffiffi jV j p log jV jÞ”