Visible to the public Sybil Detection Using Latent Network Structure

TitleSybil Detection Using Latent Network Structure
Publication TypeConference Paper
Year of Publication2016
AuthorsSchoenebeck, Grant, Snook, Aaron, Yu, Fang-Yi
Conference NameProceedings of the 2016 ACM Conference on Economics and Computation
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-3936-0
Keywordscomplex contagion, composability, edge detection, latent social network, Metrics, network accountability, provable security, pubcrawl, Resiliency, security, Sybil attack, sybil attacks

Sybil attacks, in which an adversary creates a large number of identities, present a formidable problem for the robustness of recommendation systems. One promising method of sybil detection is to use data from social network ties to implicitly infer trust. Previous work along this dimension typically a) assumes that it is difficult/costly for an adversary to create edges to honest nodes in the network; and b) limits the amount of damage done per such edge, using conductance-based methods. However, these methods fail to detect a simple class of sybil attacks which have been identified in online systems. Indeed, conductance-based methods seem inherently unable to do so, as they are based on the assumption that creating many edges to honest nodes is difficult, which seems to fail in real-world settings. We create a sybil defense system that accounts for the adversary's ability to launch such attacks yet provably withstands them by: Notassuminganyrestrictiononthenumberofedgesanadversarycanform,butinsteadmakingamuch weaker assumption that creating edges from sybils to most honest nodes is difficult, yet allowing that the remaining nodes can be freely connected to. Relaxing the goal from classifying all nodes as honest or sybil to the goal of classifying the "core" nodes of the network as honest; and classifying no sybil nodes as honest. Exploiting a new, for sybil detection, social network property, namely, that nodes can be embedded in low-dimensional spaces.

Citation Keyschoenebeck_sybil_2016