An analysis of social network-based Sybil defenses

By Bimal Viswanath, Ansley Post, Krishna P. Gummadi, Alan Mislove. 2010

421 citations recorded by the source corpus.

Recently, there has been much excitement in the research community over using social networks to mitigate multiple identity, or Sybil, attacks. A number of schemes have been proposed, but they differ greatly in the algorithms they use and in the networks upon which they are evaluated. As a result, the research community lacks a clear understanding of how these schemes compare against each other, how well they would work on real-world social networks with different structural properties, or whether there exist other (potentially better) ways of Sybil defense. In this paper, we show that, despite their considerable differences, existing Sybil defense schemes work by detecting local communities (i.e., clusters of nodes more tightly knit than the rest of the graph) around a trusted node. Our finding has important implications for both existing and future designs of Sybil defense schemes. First, we show that there is an opportunity to leverage the substantial amount of prior work on general community detection algorithms in order to defend against Sybils. Second, our analysis reveals the fundamental limits of current social network-based Sybil defenses: We demonstrate that networks with well-defined community structure are inherently more vulnerable to Sybil attacks, and that, in such networks, Sybils can carefully target their links in order make their attacks more effective.

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

In Information Systems

In Signal Processing

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.”
Understanding user behavior in online social networks: a survey (2013, background): “Viswanath et al. [19] develop a deep understanding of these approaches.”
Local search of communities in large graphs (2014, methodology): “Their basic idea is that local community around a trusted node is also trustworthy [31].”
Finding and Characterizing Information Warfare Campaigns (2020, background): “This was applied to both Facebook data and the Enron email data (not to Twitter).”
The socialbot network: when bots socialize for fame and money (2011, methodology): “Now, in order to detect Sybil nodes in the P2P network, the following assumption is often made [41]: a Sybil node cannot have many connections with non-Sybil nodes in the social network.”
CrowdTarget: Target-based Detection of Crowdturfing in Online Social Networks (2015, background): “Second, graph-based methods [9, 10, 13, 30, 36, 37] detect malicious accounts by using the observation that malicious accounts usually have few connections with normal accounts.”
Uncovering social network sybils in the wild (2011, background): “2009], prior work demonstrates that these Sybil detectors generalize to community detection [Viswanath et al. 2010].”
SybilFuse: Combining Local Attributes with Global Structure to Perform Robust Sybil Detection (2018, methodology): “Second, benign users tend to form multiple small communities [18] driven by different purposes (e.g., geographical location, education, and career), which introduces a longer mixing time than the theoretical anticipated value [31].”
SoK: The Evolution of Sybil Defense via Social Networks (2013, methodology): “[39] ob− serve that, despite their peculiarities, sybil defense schemes are based on the same fundamental principle—community detection—and produce highly correlated results.”
Combating Attacks and Abuse in Large Online Communities (2016, methodology): “In the context of online social networks, most Sybil detection systems rely on social graphs [247, 246, 217, 221, 69, 58].”
Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation (2018, methodology): “[47] demonstrated that Sybil detection methods can be treated as ranking mechanisms, and they can be evaluated using Area Under the Receiver Operating Characteristic Curve (AUC).”
Aiding the Detection of Fake Accounts in Large Scale Social Online Services (2012, methodology): “Our evaluation is based on a framework [54] that reduces defense schemes to a general model: producing a trust-based node ranking.”
Exploiting Temporal Dynamics in Sybil Defenses (2015, background): “Second, the social network is a strong trust network, where the number of attack edges is relatively small [29].”
The rise of social bots (2014, background): “One common strategy is to adopt off-the-shelf community detection methods to reveal such tightly knit local communities; however, the choice of the community detection algorithm has proven to crucially affect the performance of the detection algorithms.(34) A wise attacker may counterfeit the connec”
Graph-based Security and Privacy Analytics via Collective Classification with Joint Weight Learning and Propagation (2018, methodology): “Like previous studies [2], [5], [10], [11], [13]–[15], [17], [20], we adopt the following metrics to evaluate a collective classiﬁcation method for graph-based security and privacy analytics.”
Sybil Attacks and Their Defenses in the Internet of Things (2014, background): “The possibility of using social community detection algorithms to detect SA-1 is validated in [68].”
Defending against Sybil Devices in Crowdsourced Mapping Services (2015, methodology): “Graph-based Sybil detectors [53, 52, 47, 14, 10] were originally proposed in social networks.”