An Analysis of Graph Properties for Detecting Sybil Nodes in Social Networks
DOI:
https://doi.org/10.5614/itbj.ict.res.appl.2018.12.2.6Keywords:
attack graph, graph theory, social graph, social network, Sybil attackAbstract
This research concerns the analysis of social networks using graph theory to find properties that can be used to determine Sybil nodes. This research also investigated the mixing time, which is one of the properties that many existing methods use for detecting Sybil attacks. The results showed that the mixing time does not reflect the difference between honest graphs and Sybil graphs. In addition, the properties of social graphs were studied and it was found that the average node distance is different in graphs containing Sybil nodes than in graphs with only honest nodes. Furthermore, the eigenvector centrality and the degree of Sybil nodes are correlated, while in honest nodes they are not.Downloads
References
Boshmaf, Y., Muslukhov, I., Beznosov, K. & Ripeanu, M., The Socialbot Network: When Bots Socialize for Fame and Money, Proceedings of the 27th Annual Computer Security Applications Conference, pp. 93-102, 2011.
Boshmaf, Y., Muslukhov, I., Beznosov, K. & Ripeanu, M., Design and analysis of a social botnet, Computer Networks, 57(2), pp. 556-578, 2013.
Cao, Q., Sirivianos, M., Yang, X. & Pregueiro, T., Aiding the Detection of Fake Accounts in Large Scale Social Online Services, the Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, p. 15, 2012.
Mohaisen, A., Yun, A. & Kim, Y., Measuring the Mixing Time of Social Graphs, the Proceedings of the 10th ACM SIGCOMM Conference on Internet Measurement, pp. 383-389, 2010.
Yang, Z., Wilson, C., Wang, X., Gao, T., Zhao, B.Y. & Dai, Y., Uncovering Social Network Sybils in the Wild, ACM Transactions on Knowledge Discovery from Data (TKDD), 8(1), p. 2, 2014.
Sommer, R. & Paxson, V., Outside the Closed World: On Using Machine Learning for Network Intrusion Detection, in Security and Privacy (SP), 2010 IEEE Symposium on 2010 May 16, pp. 305-316, 2010.
Cresci, S., Di Pietro, R., Petrocchi, M., Spognardi, A. & Tesconi, M., Fame for Sale: Efficient Detection of fake Twitter Followers, Decision Support Systems, 80, pp. 56-71, 2015.
Yu, H., Kaminsky, M., Gibbons, P.B. & Flaxman, A., Sybil Guard: Defending Against Sybil Attacks via Social Networks, In ACM SIGCOMM Computer Communication Review, 36(1), pp. 267-278, 2006.
Yu, H., Gibbons, P.B., Kaminsky, M. & Xiao, F., Sybillimit: A Near-Optimal Social Network Defense Against Sybil Attacks, presented at the Security and Privacy, 2008. SP 2008. IEEE Symposium on, pp. 3-17, 2008.
Danezis, G. & Mittal, P., SybilInfer: Detecting Sybil Nodes using Social Networks, presented at the NDSS, 2009.
Tran, D.N., Min, B., Li, J. & Subramanian, L., Sybil-Resilient Online Content Voting, presented at the NSDI, 9(1), pp. 15-28, 2009.
Tran, N., Li, J., Subramanian, L. & Chow, S.S., Optimal Sybil-resilient Node Admission Control, presented at the INFOCOM, 2011 Proceedings IEEE, pp. 3218-3226, 2011.
Cai, Z. & Jermaine, C., The Latent Community Model for Detecting Sybil Attacks in Social Networks, InProc. NDSS, 2012.
Boshmaf, Y., Beznosov, K. & Ripeanu, M., Graph-based Sybil Detection in Social and Information Systems, presented at the Advances in Social Networks Analysis & Mining (ASONAM), 2013 IEEE/ACM International Conference on, pp. 466-473, 2013.
Shi, L., Yu, S., Lou, W. & Hou, Y.T., Sybilshield: An Agent-aided Social Network-based Sybil Defense among Multiple Communities" , presented at the INFOCOM, 2013 Proceedings IEEE, pp. 1034-1042, 2013.
Boshmaf, Y., Logothetis, D., Siganos, G., Lera, J., Lorenzo, J., Ripeanu, M. & Beznosov, K., Integro: Leveraging Victim Prediction for Robust Fake Account Detection in OSNs. In NDSS, 15, pp. 8-11, 2015.
Mulamba, D., Ray, I. & Ray, I., SybilRadar: A Graph-Structure Based Framework for Sybil Detection in On-line Social Networks, In IFIP International Information Security and Privacy Conference, Springer, Cham, pp. 179-193, 2016.
Liu, Y., Ji, S. & Mittal, P., SmartWalk: Enhancing Social Network Security via Adaptive Random Walks, In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security), ACM, pp. 492-503, 2016.
Misra, S., Tayeen, A. S. M. & Xu, W., SybilExposer: An Effective Scheme to Detect Sybil Communities in Online Social Networks, In Communications (ICC), 2016 IEEE International Conference on, IEEE, pp. 1-6, 2016.
Jia, J., Wang, B. & Gong, N. Z., Random Walk Based Fake Account Detection in Online Social Networks. In Dependable Systems and Networks (DSN), 2017 47th Annual IEEE/IFIP International Conference on. IEEE, pp. 273-284, 2017.
Wang, B., Jia, J., Zhang, L. & Gong, N. Z., Structure-based Sybil Detection in Social Networks via Local Rule-based Propagation, IEEE Transactions on Network Science and Engineering, 2018.
Wang, B., Zhang, L. & Gong, N. Z., SybilBlind: Detecting Fake Users in Online Social Networks without Manual Labels. arXiv preprint arXiv:1806.04853, 2018.
Douceur, J.R., The Sybil Attack in Peer-to-peer Systems, Springer, pp. 251-260, 2002.
Yu, H., Sybil Defenses via Social Networks: A Tutorial and Survey, ACM SIGACT News, 42(1), pp. 80-101, 2011.
Mohaisen, A., Tran, H., Hopper, N. & Kim, Y., On the Mixing Time of Directed Social Graphs and Security Implications, presented at the Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pp. 36-37, 2012.
Dellamico, M. & Roudier, Y., A Measurement of Mixing Time in Social Networks, IWSTM, 2009.
Gjoka, M., Kurant, M., Butts, C.T. & Markopoulou, A., Walking in Facebook: a Case Study of Unbiased Sampling of OSNs, in Infocom 2010 Proceedings IEEE, pp. 1-9, 2010.
Buccafurri, F., Lax, G., Nocera, A. & Ursino, D., Moving from Social Networks to Social Internetworking Scenarios: The Crawling Perspective, Information Sciences, 256(1), pp. 126-137, 2014.
Bonacich, P., Power and Centrality: A Family of Measures, American Journal of Sociology, 92(5), pp. 1170-1182, 1987.
Bonacich, P. & Lloyd, P., Eigenvector-like Measures of Centrality for asymmetric relations, Social networks, 23(3), pp. 191-201, 2001.
Kas, M., Carley, L.R. & Carley, K.M., Monitoring Social Centrality for Peer-to-peer Network Protection, IEEE Communications Magazine, 51(12), pp. 155-161, 2013.
