SybilBelief: A Semi-Supervised Learning Approach for Structure-Based Sybil Detection

By Neil Zhenqiang Gong, Mario Frank, Prateek Mittal. 2013

188 citations recorded by the source corpus.

Sybil attacks are a fundamental threat to the security of distributed systems. Recently, there has been a growing interest in leveraging social networks to mitigate Sybil attacks. However, the existing approaches suffer from one or more drawbacks, including bootstrapping from either only known benign or known Sybil nodes, failing to tolerate noise in their prior knowledge about known benign or Sybil nodes, and not being scalable. In this paper, we aim to overcome these drawbacks. Toward this goal, we introduce SybilBelief, a semi-supervised learning framework, to detect Sybil nodes. SybilBelief takes a social network of the nodes in the system, a small set of known benign nodes, and, optionally, a small set of known Sybils as input. Then, SybilBelief propagates the label information from the known benign and/or Sybil nodes to the remaining nodes in the system. We evaluate SybilBelief using both synthetic and real-world social network topologies. We show that SybilBelief is able to accurately identify Sybil nodes with low false positive rates and low false negative rates. SybilBelief is resilient to noise in our prior knowledge about known benign and Sybil nodes. Moreover, SybilBelief performs orders of magnitudes better than existing Sybil classification mechanisms and significantly better than existing Sybil ranking mechanisms.

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

Attacking Graph-based Classification via Manipulating the Graph Structure (2019, methodology): “…can also transfer to other collective classiﬁcation methods including random walk based meth-ods [34], Loopy Belief Propagation based methods [23], and recent Joint Weight Learning and Propagation method [63] that learns edge weights, as well as graph neural network methods including Graph…”
Poisoning Attacks to Graph-Based Recommender Systems (2018, methodology): “ion in social networks. Many methods have been developed for Sybil detection. „ese methods leverage IP addresses (e.g., [28]), user behavior (e.g., [32]), or social relationships between users (e.g., [8, 30, 31]). Since we do not have access to IP addresses nor social relationships of users, we expl”
Fake Co-visitation Injection Attacks to Recommender Systems (2017, background): “For instance, when social relationships between accounts are available, we can leverage SybilBelief [32] to detect fake accounts.”
Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation (2018, methodology): “LBP-based methods [18], [19], [20] suffer from three major limitations: 1) they cannot guarantee convergence on real-world social networks; 2) they are not scalable; and 3) they do not have theoretically guaranteed performance.”
GANG: Detecting Fraudulent Users in Online Social Networks via Guilt-by-Association on Directed Graphs (2017, methodology): “Therefore, for the Twitter dataset, we obtained the AUC results in Table III for SSL, SybilBelief, SybilSCAR, and GANG using the sampled balanced training dataset; and we obtained the results in Figure 2 using the original unbalanced training dataset.”
Graph-based Security and Privacy Analytics via Collective Classification with Joint Weight Learning and Propagation (2018, methodology): “State-of-the-art collective classiﬁcation methods [2], [5], [6], [11], [13]–[15], [17]–[20], [22]–[29] have three key steps.”
SybilBlind: Detecting Fake Users in Online Social Networks without Manual Labels (2018, methodology): “3) SybilBlind outperforms SybilRank and is comparable with SybilBelief, even if SybilRank and SybilBelief use a labeled training dataset.”
SybilSCAR: Sybil detection in online social networks via local rule based propagation (2017, methodology): “Most structurebased methods [9], [10], [11], [12], [8], [13], [14], [15] can be grouped into two categories: Random Walk (RW)-based methods and Loop Belief Propagation (LBP)-based methods.”
Random Walk Based Fake Account Detection in Online Social Networks (2017, methodology): “Then, SybilBelief models the joint probability distribution of all these binary random variables as a pairwise Markov Random Field.”
SybilFuse: Combining Local Attributes with Global Structure to Perform Robust Sybil Detection (2018, methodology): “Sybil ranking performance: Following the established convention [14], [16], [17], [19], we evaluate the ranking performance of the compared approaches by ranking all nodes in an ascending order of their ﬁnal scores.”