Enhancing Sybil Detection via Social-Activity Networks: A Random Walk Approach
Xiaoying Zhang, Hong Xie, Pei Yi, John C. S. Lui
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">social and activity network</i> (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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">“matrix perturbation theory”</i> 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. Lastly, we present two extensions of Sybil_SAN to further improve its accuracy.