SoK: The Evolution of Sybil Defense via Social Networks

By Lorenzo Alvisi, Allen Clement, Alessandro Epasto, Silvio Lattanzi, Alessandro Panconesi. 2013

192 citations recorded by the source corpus.

Sybil attacks in which an adversary forges a potentially unbounded number of identities are a danger to distributed systems and online social networks. The goal of sybil defense is to accurately identify sybil identities. This paper surveys the evolution of sybil defense protocols that leverage the structural properties of the social graph underlying a distributed system to identify sybil identities. We make two main contributions. First, we clarify the deep connection between sybil defense and the theory of random walks. This leads us to identify a community detection algorithm that, for the first time, offers provable guarantees in the context of sybil defense. Second, we advocate a new goal for sybil defense that addresses the more limited, but practically useful, goal of securely white-listing a local region of the graph.

Subfields: Computer Networks and Communications, Information Systems, Signal Processing

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

1. Binghui Wang
2. Neil Zhenqiang Gong
3. Le Zhang
4. Jinyuan Jia
5. Prateek Mittal
6. Rongxing Lu
7. Henry Corrigan-Gibbs
8. Dan Boneh

In Information Systems

1. Neil Zhenqiang Gong
2. Binghui Wang
3. Jinyuan Jia
4. Le Zhang
5. Emilio Ferrara
6. Filippo Menczer
7. Onur Varol
8. Alessandro Flammini

In Signal Processing

1. Emilio Ferrara
2. Filippo Menczer
3. Onur Varol
4. Alessandro Flammini
5. Jinyuan Jia
6. Clayton A. Davis
7. Henry Corrigan-Gibbs
8. Prateek Mittal

Citations in the corpus

• Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “Standard defenses [3, 114, 124, 125] against Sybil attacks [52] would apply here.”
• Attacking Graph-based Classification via Manipulating the Graph Structure (2019, neutral): “uctural differences between negative nodes and positive nodes, we replicate the negative nodes and their edges as positive nodes and edges in each of the three graph datasets, as prior studies (e.g., [2,65]) on graph-based security analytics did. Moreover, we assume an attacker has already inserted ”
• SybilBlind: Detecting Fake Users in Online Social Networks without Manual Labels (2018, methodology): “[2] demonstrated a vulnerability of the local community detection algorithm adopted by Viswanath et al.”
• Integro: Leveraging Victim Prediction for Robust Fake Account Detection in OSNs (2015, background): “showed that this local community detection technique can be easily circumvented if the fakes establish sparse connectivity among themselves [9].”
• Online Human-Bot Interactions: Detection, Estimation, and Characterization (2017, background): “surveyed the evolution of sybil defense protocols that leverage the structural properties of the social graph (Alvisi et al. 2013).”
• The rise of social bots (2014, background): “Combining Multiple Approaches Alvisi et al.(3) recognized first the need of adopting complementary detec-”
• Deep Neural Networks for Bot Detection (2018, background): “vice providers with full access to data and systems. Some of them published studies showing the effectiveness of some implementations, e.g., SybilRank [8], the Facebook Immune System [52], and others [3]. To obviate the limitation of unlimited data access, other techniques have been designed to requ”
• Sybil Attacks and Their Defenses in the Internet of Things (2014, background): “To resist the strong Sybil attacks, in [54], an SoK defense scheme is proposed exploiting conductance to enable honest users to build a white-list which contains a set of nodes ranked associated with their trustworthiness.”
• IoT security: Review, blockchain solutions, and open challenges (2017, methodology): “The countermeasures using social graphs make it possible for legitimate nodes to detect Sybil nodes by traversing the graph through random walks or using the community detection algorithms [46, 86, 87, 88].”
• SybilBelief: A Semi-Supervised Learning Approach for Structure-Based Sybil Detection (2013, methodology): “[15] showed that some simple detectors might enforce the social networks to be suitable for structure-based Sybil defenses if the attack edges are established randomly [15].”
• Advanced social engineering attacks (2015, background): “The analysis also showed that attackers tend to use well-known instead of zero-day vulnerabilities.”
• SybilSCAR: Sybil detection in online social networks via local rule based propagation (2017, methodology): “[36] showed that if the attack edges are established randomly, simple feature-based classifiers are sufficient to enforce Sybils to be suitable for structure-based Sybil detection.”
• Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation (2018, methodology): “[40] showed that if the attack edges are established randomly, simple feature-based classifiers are sufficient to enforce Sybils to be suitable for structurebased Sybil detection.”
• SoK: Consensus in the Age of Blockchains (2017, background): “the analysis of social networks and trust graphs [6], but those have”