Sybil attacks, in which an adversary forges a potentially unbounded number of identities, are a danger to distributed systems and online social networks. The goal of sybil defense is to accurately identify sybil identities. This paper surveys the evolution of sybil defense protocols that leverage the structural properties of the social graph underlying a distributed system to identify sybil identities. We make two main contributions. First, we clarify the deep connection between sybil defense and the theory of random walks. This leads us to identify a community detection algorithm that, for the first time, offers provable guarantees in the context of sybil defense. Second, we advocate a new goal for sybil defense that addresses the more limited, but practically useful, goal of securely white-listing a local region of the graph.

Communities, Random Walks, and Social Sybil Defense / L., Alvisi; A., Clement; Epasto, Alessandro; Lattanzi, Silvio; Panconesi, Alessandro. - In: INTERNET MATHEMATICS. - ISSN 1542-7951. - 10:(2014), pp. 360-420. [10.1080/15427951.2013.865685]

Communities, Random Walks, and Social Sybil Defense

EPASTO, ALESSANDRO;LATTANZI, SILVIO;PANCONESI, Alessandro
2014

Abstract

Sybil attacks, in which an adversary forges a potentially unbounded number of identities, are a danger to distributed systems and online social networks. The goal of sybil defense is to accurately identify sybil identities. This paper surveys the evolution of sybil defense protocols that leverage the structural properties of the social graph underlying a distributed system to identify sybil identities. We make two main contributions. First, we clarify the deep connection between sybil defense and the theory of random walks. This leads us to identify a community detection algorithm that, for the first time, offers provable guarantees in the context of sybil defense. Second, we advocate a new goal for sybil defense that addresses the more limited, but practically useful, goal of securely white-listing a local region of the graph.
01 Pubblicazione su rivista::01a Articolo in rivista
Communities, Random Walks, and Social Sybil Defense / L., Alvisi; A., Clement; Epasto, Alessandro; Lattanzi, Silvio; Panconesi, Alessandro. - In: INTERNET MATHEMATICS. - ISSN 1542-7951. - 10:(2014), pp. 360-420. [10.1080/15427951.2013.865685]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/539416
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact