Visible to the public Sybil Detection in Social-Activity Networks: Modeling, Algorithms and Evaluations

TitleSybil Detection in Social-Activity Networks: Modeling, Algorithms and Evaluations
Publication TypeConference Paper
Year of Publication2018
AuthorsZhang, X., Xie, H., Lui, J. C. S.
Conference Name2018 IEEE 26th International Conference on Network Protocols (ICNP)
Keywordsactivity 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.

URLhttps://ieeexplore.ieee.org/document/8526803
DOI10.1109/ICNP.2018.00015
Citation Keyzhang_sybil_2018