›› 2015, Vol. 30 ›› Issue (6): 1344-1357.doi: 10.1007/s11390-015-1602-6

Special Issue: Theory and Algorithms

• Theory and Algorithms • Previous Articles     Next Articles

Understanding Sybil Groups in the Wild

Jing Jiang1,2(蒋竞), Member, CCF, Zi-Fei Shan2(单子非), Xiao Wang2(王潇), Li Zhang1*(张莉), Senior Member, CCF, Ya-Fei Dai2(代亚非), Distinguished Member, CCF   

  1. 1 State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China;
    2 Department of Computer Science and Technology, Peking University, Beijing 100871, China
  • Received:2014-04-25 Revised:2015-01-09 Online:2015-11-05 Published:2015-11-05
  • About author:Jing Jiang received her B.S. and Ph.D. degrees in computer science from Peking University in 2007 and 2012, respectively. She is now an assistant professor in the State Key Laboratory of Software Development Environment of Beihang University, Beijing. Her research interests include social network, data mining, human factors and social aspects of software engineering.
  • Supported by:

    This work is supported by the National Basic Research 973 Program of China under Grant No. 2011CB302305, the National Natural Science Foundation of China under Grant No. 61300006, and the Project of the State Key Laboratory of Software Development Environment under Grant No. SKLSDE-2013ZX-26.

Sybil attacks are one kind of well-known and powerful attacks against online social networks (OSNs). In a sybil attack, a malicious attacker generates a sybil group consisting of multiple sybil users, and controls them to attack the system. However, data confidentiality policies of major social network providers have severely limited researchers' access to large-scale datasets of sybil groups. A deep understanding of sybil groups can provide important insights into the characteristics of malicious behavior, as well as numerous practical implications on the design of security mechanisms. In this paper, we present an initial study to measure sybil groups in a large-scale OSN, Renren. We analyze sybil groups at different levels, including individual information, social relationships, and malicious activities. Our main observations are: 1) user information in sybil groups is usually incomplete and in poor quality; 2) sybil groups have special evolution patterns in connectivity structure, including bursty actions to add nodes, and a monotonous merging pattern that lacks non-singleton mergings; 3) several sybil groups have strong relationships with each other and compose sybil communities, and these communities cover a large number of users and pose great potential threats; 4) some sybil users are not banned until a long time after registration in some sybil groups. The characteristics of sybil groups can be leveraged to improve the security mechanisms in OSNs to defend against sybil attacks. Specifically, we suggest that OSNs should 1) check information completeness and quality, 2) learn from dynamics of community connectivity structure to detect sybil groups, 3) monitor sybil communities and inspect them carefully to prevent collusion, and 4) inspect sybil groups that behave normally even for a long time to prevent potential malicious behaviors.

[1] Jin L, Chen Y, Wang T, Hui P, Vasilakos A V. Understanding user behavior in online social networks: A survey. IEEE Communications Magazine, 2013, 51(9): 144-150.

[2] Nazir A, Raza S, Chuah C N, Schipper B. Ghostbusting facebook: Detecting and characterizing phantom profiles in online social gaming applications. In Proc. the 3rd Workshop on Online Social Networks, June 2010.

[3] Bhat S Y, Abulaish M. Community-based features for identifying spammers in online social networks. In Proc. ASONAM, August 2013, pp.100-107.

[4] Dai H, Zhu F, Lim E P, Pang H. Mining coherent anomaly collections on web data. In Proc. the 21st CIKM, October 29-November 2, 2012, pp.1557-1561.

[5] Gao H, Hu J, Wilson C, Li Z, Chen Y, Zhao B Y. Detecting and characterizing social spam campaigns. In Proc. the 10th ACM SIGCOMM Internet Measurement Conference, November 2010, pp.35-47.

[6] Hu X, Tang J, Zhang Y, Liu H. Social spammer detection in microblogging. In Proc. the 23rd IJCAI, August 2013, pp.2633-2639.

[7] Irani D, SteveWebb, Pu C. Study of static classification of social spam profiles in MySpace. In Proc. the 4th ICWSM, May 2010, pp.82-89.

[8] Lumezanu C, Feamster N. Observing common spam in Tweets and email. In Proc. the 12th ACM SIGCOMM IMC, November 2012, pp.461-466.

[9] Miller Z, Dickinson B, Deitrick W, Hua W, Wang A H. Twitter spammer detection using data stream clustering. Information Sciences, 2014, 260: 64-73.

[10] Stringhini G, Kruegel C, Vigna G. Detecting spammers on social networks. In Proc. the 26th Annual Computer Security Applications Conference, December 2010, pp.1-9.

[11] Thomas K, Grier C, Paxson V, Song D. Suspended accounts in retrospect: An analysis of Twitter spam. In Proc. the 11th ACM SIGCOMM Internet Measurement Conference, November 2011, pp.243-258.

[12] Wang G, Wilson C, Zhao X, Zhu Y, Mohanlal M, Zheng H, Zhao B Y. Serf and turf: Crowdturfing for fun and profits. In Proc. the 21st WWW, April 2012, pp.679-688.

[13] Danezis G, Mittal P. SybilInfer: Detecting sybil nodes using social networks. In Proc. NDSS, February 2009.

[14] Tran N, Min B, Li J, Subramanian L. Sybil-resilient online content voting. In Proc. the 6th NSDI, April 2009, pp.15-28.

[15] Wei W, Xu F, Tan C C, Li Q. SybilDefender: A defense mechanism for sybil attacks in large social networks. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(12): 2492-2502.

[16] Yu H, Gibbons P B, Kaminsky M, Xiao F. SybilLimit: A near-optimal social network defense against sybil attacks. In Proc. IEEE Symposium on Security and Privacy, May 2008, pp.3-17.

[17] Yu H, Kaminsky M, Gibbons P B, Flaxman A D. Sybil- Guard: Defending against sybil attacks via social networks. IEEE/ACM Transactions on Networking, 2008, 16(3): 576- 589.

[18] Chu Z, Gianvecchio S, Wang H, Jajodia S. Who is tweeting on Twitter: Human, bot, or cyborg? In Proc. the 26th Annual Computer Security Applications Conference, December 2010, pp.21-30.

[19] Lee K, Caverlee J, Webb S. Uncovering social spammers: Social honeypots + machine learning. In Proc. the 33rd SIGIR, July 2010, pp.435-442.

[20] Webb S, Caverlee J, Pu C. Social honeypots: Making friends with a spammer near you. In Proc. the 5th CEAS, August 2008.

[21] Benevenuto F, Rodrigues T, Almeida V, Almeida J, Gonglves M. Detecting spammers and content promoters in online video social networks. In Proc. the 32nd SIGIR, July 2009, pp.620-627.

[22] Benevenuto F, Magno G, Rodrigues T, Almeida V. Detecting spammers on Twitter. In Proc. CEAS, July 2010.

[23] Liu J Y, Zhao Y H, Zhang Z X, Wang Y H, Yuan X M, Hu L, Dong Z J. Spam short messages detection via mining social networks. Journal of Computer Science and Technology, 2012, 27(3): 506-514.

[24] Yang Z, Wilson C, Wang X, Gao T, Zhao B Y, Dai Y. Uncovering social network sybils in the wild. In Proc. the 11th ACM SIGCOMM Internet Measurement Conference, November 2011, pp.259-268.

[25] Yardi S, Romero D, Schoenebeck G, Boyd D. Detecting spam in a Twitter network. First Monday, 2010, 15(1).

[26] Jiang J, Shan Z, Sha W, Wang X, Dai Y. Detecting and validating sybil groups in the wild. In Proc. the 32nd ICDCS Workshops, June 2012, pp.127-132.

[27] Jiang J, Wilson C, Wang X, Huang P, Sha W, Dai Y, Zhao B Y. Understanding latent interactions in online social networks. In Proc. the 10th ACM Internet Measurement Conference, November 2010, pp.369-382.

[28] Mann H B, Whitney D R. On a test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics, 1947, 18(1): 50-60.

[29] Palla G, Barabási A L, Vicsek T. Quantifying social group evolution. Nature, 2007, 446(7136): 664-667.

[30] Viswanath B, Post A, Gummadi K P, Mislove A. An analysis of social network-based sybil defenses. In Proc. SIGCOMM, August 30-September 3, 2010, pp.363-374.

[31] Kumar R, Novak J, Tomkins A. Structure and evolution of online social networks. In Proc. the 12th KDD, August 2006, pp.611-617.

[32] Li Z, Chen G, Qiu T. Partition nodes: Topologically-critical nodes of unstructured peer-to-peer networks. Journal of Software, 2008, 19(9): 2376-2388. (in Chinese)

[33] Gong M G, Zhang L J, Ma J J, Jiao L C. Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of Computer Science and Technology, 2012, 27(3): 455-467.

[34] Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.

[35] Bastian M, Heymann S, Jacomy M. Gephi: An open source software for exploring and manipulating networks. In Proc. the 3rd International AAAI Conference on Weblogs and Social Media, May 2009, pp.361-362.

[36] Xue J, Yang Z, Yang X,Wang X, Chen L, Dai Y. VoteTrust: Leveraging friend invitation graph to defend against social network sybils. In Proc. INFOCOM, April 2013, pp.2400- 2408.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved