Graph-based Sybil Detection in social and information systems

Yazan Boshmaf; Konstantin Beznosov; Matei Ripeanu

doi:10.1145/2492517.2492568

Graph-based Sybil Detection in social and information systems

Yazan Boshmaf
, Konstantin Beznosov
, Matei Ripeanu

University of British Columbia

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

33 Citations (Scopus)

Abstract

Sybil attacks in social and information systems have serious security implications. Out of many defence schemes, Graph-based Sybil Detection (GSD) had the greatest attention by both academia and industry. Even though many GSD algorithms exist, there is no analytical framework to reason about their design, especially as they make different assumptions about the used adversary and graph models. In this paper, we bridge this knowledge gap and present a unified framework for systematic evaluation of GSD algorithms. We used this framework to show that GSD algorithms should be designed to find local community structures around known non-Sybil identities, while incrementally tracking changes in the graph as it evolves over time.

Original language	English
Title of host publication	Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
Publisher	Association for Computing Machinery
Pages	466-473
Number of pages	8
ISBN (Print)	9781450322409
DOIs	https://doi.org/10.1145/2492517.2492568
Publication status	Published - 2013
Externally published	Yes
Event	2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013 - Niagara Falls, ON, Canada Duration: 25 Aug 2013 → 28 Aug 2013

Publication series

Name	Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

Conference

Conference	2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
Country/Territory	Canada
City	Niagara Falls, ON
Period	25/08/13 → 28/08/13

Access to Document

10.1145/2492517.2492568

Cite this

Boshmaf, Y., Beznosov, K., & Ripeanu, M. (2013). Graph-based Sybil Detection in social and information systems. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013 (pp. 466-473). (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013). Association for Computing Machinery. https://doi.org/10.1145/2492517.2492568

Boshmaf, Yazan ; Beznosov, Konstantin ; Ripeanu, Matei. / Graph-based Sybil Detection in social and information systems. Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013. Association for Computing Machinery, 2013. pp. 466-473 (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013).

@inproceedings{15e0012b12d848bbb3d066597fda65cb,

title = "Graph-based Sybil Detection in social and information systems",

abstract = "Sybil attacks in social and information systems have serious security implications. Out of many defence schemes, Graph-based Sybil Detection (GSD) had the greatest attention by both academia and industry. Even though many GSD algorithms exist, there is no analytical framework to reason about their design, especially as they make different assumptions about the used adversary and graph models. In this paper, we bridge this knowledge gap and present a unified framework for systematic evaluation of GSD algorithms. We used this framework to show that GSD algorithms should be designed to find local community structures around known non-Sybil identities, while incrementally tracking changes in the graph as it evolves over time.",

author = "Yazan Boshmaf and Konstantin Beznosov and Matei Ripeanu",

year = "2013",

doi = "10.1145/2492517.2492568",

language = "English",

isbn = "9781450322409",

series = "Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013",

publisher = "Association for Computing Machinery",

pages = "466--473",

booktitle = "Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013",

address = "United States",

note = "2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013 ; Conference date: 25-08-2013 Through 28-08-2013",

}

Boshmaf, Y, Beznosov, K & Ripeanu, M 2013, Graph-based Sybil Detection in social and information systems. in Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013. Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013, Association for Computing Machinery, pp. 466-473, 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013, Niagara Falls, ON, Canada, 25/08/13. https://doi.org/10.1145/2492517.2492568

Graph-based Sybil Detection in social and information systems. / Boshmaf, Yazan; Beznosov, Konstantin; Ripeanu, Matei.
Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013. Association for Computing Machinery, 2013. p. 466-473 (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Graph-based Sybil Detection in social and information systems

AU - Boshmaf, Yazan

AU - Beznosov, Konstantin

AU - Ripeanu, Matei

PY - 2013

Y1 - 2013

N2 - Sybil attacks in social and information systems have serious security implications. Out of many defence schemes, Graph-based Sybil Detection (GSD) had the greatest attention by both academia and industry. Even though many GSD algorithms exist, there is no analytical framework to reason about their design, especially as they make different assumptions about the used adversary and graph models. In this paper, we bridge this knowledge gap and present a unified framework for systematic evaluation of GSD algorithms. We used this framework to show that GSD algorithms should be designed to find local community structures around known non-Sybil identities, while incrementally tracking changes in the graph as it evolves over time.

AB - Sybil attacks in social and information systems have serious security implications. Out of many defence schemes, Graph-based Sybil Detection (GSD) had the greatest attention by both academia and industry. Even though many GSD algorithms exist, there is no analytical framework to reason about their design, especially as they make different assumptions about the used adversary and graph models. In this paper, we bridge this knowledge gap and present a unified framework for systematic evaluation of GSD algorithms. We used this framework to show that GSD algorithms should be designed to find local community structures around known non-Sybil identities, while incrementally tracking changes in the graph as it evolves over time.

UR - https://www.scopus.com/pages/publications/84893231662

U2 - 10.1145/2492517.2492568

DO - 10.1145/2492517.2492568

M3 - Conference contribution

AN - SCOPUS:84893231662

SN - 9781450322409

T3 - Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

SP - 466

EP - 473

BT - Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

PB - Association for Computing Machinery

T2 - 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

Y2 - 25 August 2013 through 28 August 2013

ER -

Boshmaf Y, Beznosov K, Ripeanu M. Graph-based Sybil Detection in social and information systems. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013. Association for Computing Machinery. 2013. p. 466-473. (Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013). doi: 10.1145/2492517.2492568

Graph-based Sybil Detection in social and information systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this