Structure-Based Sybil Detection in Social Networks via Local Rule-Based Propagation

By Binghui Wang, Jinyuan Jia, Le Zhang, Neil Zhenqiang Gong. 2018

59 citations recorded by the source corpus.

Social networks are known to be vulnerable to the so-called Sybil attack, in which an attacker maintains massive Sybils and uses them to perform various malicious activities. Therefore, Sybil detection in social networks is a basic security research problem. Structure-based methods have been shown to be promising at detecting Sybils. Existing structure-based methods can be classified into two categories: Random Walk (RW)-based methods and Loop Belief Propagation (LBP)-based methods. RW-based methods cannot leverage labeled Sybils and labeled benign users simultaneously, which limits their detection accuracy, and/or they are not robust to noisy labels. LBP-based methods are not scalable, and they cannot guarantee convergence. In this work, we propose SybilSCAR, a novel structure-based method to detect Sybils in social networks. SybilSCAR is Scalable, Convergent, Accurate, and Robust to label noise. We first propose a framework to unify RW-based and LBP-based methods. Under our framework, these methods can be viewed as iteratively applying a (different) local rule to every user, which propagates label information among a social graph. Second, we design a new local rule, which SybilSCAR iteratively applies to every user to detect Sybils. We compare SybilSCAR with state-of-the-art RW-based methods and LBP-based methods both theoretically and empirically. Theoretically, we show that, with proper parameter settings, SybilSCAR has a tighter asymptotical bound on the number of Sybils that are falsely accepted into a social network than existing structure-based methods. Empirically, we perform evaluation using both social networks with synthesized Sybils and a large-scale Twitter dataset (41.7M nodes and 1.2B edges) with real Sybils, and our results show that 1) SybilSCAR is substantially more accurate and more robust to label noise than state-of-the-art RW-based methods; and 2) SybilSCAR is more accurate and one order of magnitude more scalable than state-of-the-art LBP-based methods.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

  1. Neil Zhenqiang Gong
  2. Binghui Wang
  3. Jinyuan Jia
  4. Le Zhang
  5. Yang Zhang
  6. Hao Fu
  7. Michael Backes
  8. Ahmed Salem

In Computer Networks and Communications

  1. Binghui Wang
  2. Neil Zhenqiang Gong
  3. Jinyuan Jia
  4. Le Zhang
  5. Hao Fu

In Information Systems

  1. Neil Zhenqiang Gong
  2. Binghui Wang
  3. Jinyuan Jia
  4. Le Zhang
  5. Hao Fu

Citations in the corpus