Sybil Detection in Social-Activity Networks: Modeling, Algorithms and Evaluations
Title | Sybil Detection in Social-Activity Networks: Modeling, Algorithms and Evaluations |
Publication Type | Conference Paper |
Year of Publication | 2018 |
Authors | Zhang, X., Xie, H., Lui, J. C. S. |
Conference Name | 2018 IEEE 26th International Conference on Network Protocols (ICNP) |
Keywords | activity attacks, Algorithms, composability, Computational modeling, convergence, detection algorithms, detection metric, Facebook, fake accounts, friendship attacks, graph theory, graph-based sybil detection, Image edge detection, iterative algorithm, Iterative methods, low detection accuracy, malicious activities, matrix algebra, matrix perturbation theory, Metrics, online social networks, perturbation theory, pubcrawl, security of data, social activity network, social networking (online), social-activity networks, sybil attacks, sybil defenses, sybil detection, Sybil SAN, Twitter |
Abstract | Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users' activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop the social and activity network (SAN), a two-layer hyper-graph that unifies users' friendships and their activities, to fully utilize users' activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil SAN, and derive the number of rounds needed to guarantee the convergence. We use "matrix perturbation theory" to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy. |
URL | https://ieeexplore.ieee.org/document/8526803 |
DOI | 10.1109/ICNP.2018.00015 |
Citation Key | zhang_sybil_2018 |
- malicious activities
- Sybil SAN
- sybil detection
- sybil defenses
- sybil attacks
- social-activity networks
- social networking (online)
- social activity network
- security of data
- pubcrawl
- perturbation theory
- online social networks
- Metrics
- matrix perturbation theory
- matrix algebra
- activity attacks
- low detection accuracy
- Iterative methods
- iterative algorithm
- Image edge detection
- graph-based sybil detection
- graph theory
- friendship attacks
- fake accounts
- detection metric
- detection algorithms
- convergence
- Computational modeling
- composability
- Algorithms