SybilBelief: A Semi-Supervised Learning Approach for Structure-Based Sybil Detection
Open accessThe DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Abstract
Sybil attacks are a fundamental threat to the security of distributed systems. Recently, there has been a growing interest in leveraging social networks to mitigate Sybil attacks. However, the existing approaches suffer from one or more drawbacks, including bootstrapping from either only known benign or known Sybil nodes, failing to tolerate noise in their prior knowledge about known benign or Sybil nodes, and not being scalable. In this paper, we aim to overcome these drawbacks. Toward this goal, we introduce SybilBelief, a semi-supervised learning framework, to detect Sybil nodes. SybilBelief takes a social network of the nodes in the system, a small set of known benign nodes, and, optionally, a small set of known Sybils as input. Then, SybilBelief propagates the label information from the known benign and/or Sybil nodes to the remaining nodes in the system. We evaluate SybilBelief using both synthetic and real-world social network topologies. We show that SybilBelief is able to accurately identify Sybil nodes with low false positive rates and low false negative rates. SybilBelief is resilient to noise in our prior knowledge about known benign and Sybil nodes. Moreover, SybilBelief performs orders of magnitudes better than existing Sybil classification mechanisms and significantly better than existing Sybil ranking mechanisms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
(1988) · Cited by 16,582
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004 · cited 1×
“these approaches are variants of the PageRank algorithm [40].”
MethodFoundations of statistical natural language processing
Manning, C. D., & Schütze, H. (1999) · Cited by 9,816
Power-Law Distributions in Empirical Data
Clauset, A., Shalizi, C. R., & Newman, M. E. J. (2009) · SIAM Review · doi:10.1137/070710111 · Cited by 8,019 · cited 1×
“, power-law degree distribution [33] and lognormal degree distribution [26]), in which most nodes have very small degrees.”
BackgroundPower-law distributions in empirical data
Clauset, A. J., Shalizi, C. R., & Newman, M. E. J. (2018) · Figshare · doi:10.1184/r1/6586835.v1 · Cited by 6,504
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Douceur, J. R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45748-8_24 · Cited by 4,419 · cited 1×
“SYBIL attacks, where a single entity emulates the behavior of multiple users, form a fundamental threat to the security of distributed systems [1].”
BackgroundThe EigenTrust algorithm for reputation management in P2P networks
Kamvar, S. D., Schlosser, M. T., & Garcia-Molina, H. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775242 · Cited by 3,362 · cited 1×
“Interesting avenues for future work include evaluating SybilBelief and previous approaches with datasets containing real Sybils and applying our SybilBelief framework to other security and privacy problems such as graph based Botnet detection [44], reputation systems [37], and private information inference [45].”
MethodMeasurement and analysis of online social networks
Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P., & Bhattacharjee, B. (2007) · Proceedings of the 7th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1298306.1298311 · Cited by 3,057 · cited 1×
“Note that social networks are often sparse graphs [25], [26].”
BackgroundGraphs over time: densification laws, shrinking diameters and possible explanations
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081893 · Cited by 2,281 · cited 1×
“The Email network was generated using email data from a large European research institution [32].”
MethodA Simple Generalisation of the Area Under the ROC Curve for Multiple Class Classification Problems
Hand, D. J., & Till, R. J. (2001) · Machine Learning · doi:10.1023/a:1010920819831 · Cited by 2,276 · cited 1×
“We compute the AUC in the manner described in [34].”
MethodThe computational complexity of probabilistic inference using bayesian belief networks
Cooper, G. F. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90060-d · Cited by 1,937 · cited 1×
“shown that this problem is NP-hard on general graphs [43].”
BackgroundPropagation of trust and distrust
Guha, R., Kumar, R., Raghavan, P., & Tomkins, A. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988727 · Cited by 1,464 · cited 1×
“Several approaches have been proposed to propagate trust scores or reputation scores in file-sharing networks or auction platforms (e.g., [37]– [39]).”
BackgroundOn the evolution of user interaction in facebook
Viswanath, B., Mislove, A., Cha, M., & Gummadi, K. P. (2009) · Proceedings of the 2nd ACM workshop on Online social networks · doi:10.1145/1592665.1592675 · Cited by 1,461 · cited 1×
“Facebook is an interaction graph from the New Orleans regional network [31].”
BackgroundMarkov Random Field Texture Models
Cross, G. R., & Jain, A. K. (1983) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1983.4767341 · Cited by 1,414 · cited 1×
“The Markov Random Fields (MRF) has many applications in electrical engineering and computer science such as computer vision [41] and natural language processing [42].”
BackgroundLoopy Belief Propagation for Approximate Inference: An Empirical Study
Murphy, K. P., Weiss, Y., & Jordan, M. I. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6725 · Cited by 1,397 · cited 3×
“graphs has often been used in practical applications and has demonstrated satisfying approximate performance [24].”
Predicting tie strength with social media
Gilbert, E., & Karahalios, K. (2009) · Proceedings of the SIGCHI Conference on Human Factors in Computing Systems · doi:10.1145/1518701.1518736 · Cited by 1,382 · cited 1×
“One method is to approximate trust relationships between users through looking into user interactions [20], inferring tie strengths [21], and asking users to rate their social contacts [22].”
MethodThe Eigentrust algorithm for reputation management in P2P networks
Kamvar, S. D., Schlosser, M. T., & Garcia-Molina, H. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775240.775242 · Cited by 1,365
Trust Management for the Semantic Web
Richardson, M., Agrawal, R., & Domingos, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-39718-2_23 · Cited by 982
User interactions in social networks and their implications
Wilson, C., Boe, B., Sala, A., Puttaswamy, K. P. N., & Zhao, B. Y. (2009) · Proceedings of the 4th ACM European conference on Computer systems · doi:10.1145/1519065.1519089 · Cited by 879 · cited 1×
“One method is to approximate trust relationships between users through looking into user interactions [20], inferring tie strengths [21], and asking users to rate their social contacts [22].”
MethodSybilGuard: defending against sybil attacks via social networks
Yu, H., Kaminsky, M., Gibbons, P. B., & Flaxman, A. (2006) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1151659.1159945 · Cited by 725
You are who you know: inferring user profiles in online social networks
Mislove, A., Viswanath, B., Gummadi, K. P., & Druschel, P. (2010) · Proceedings of the third ACM international conference on Web search and data mining · doi:10.1145/1718487.1718519 · Cited by 668 · cited 1×
“[35] had equivalent results to using state-ofthe-art Sybil detection approaches.”
ResultSybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks
Yu, H., Gibbons, P. B., Kaminsky, M., & Xiao, F. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.13 · Cited by 563
Aiding the detection of fake accounts in large scale social online services
Cao, Q., Sirivianos, M., Yang, X., & Pregueiro, T. (2012) · Networked Systems Design and Implementation · Cited by 560
All your contacts are belong to us: automated identity theft attacks on social networks
Bilge, L., Strufe, T., Balzarotti, D., & Kirda, E. (2009) · Proceedings of the 18th international conference on World wide web · doi:10.1145/1526709.1526784 · Cited by 545 · cited 1×
“activities such as spreading spam or malware [3], stealing other users’ private information [4], [5], and manipulating web search results via “+1” or “like” clicks [6].”
BackgroundSybilInfer: Detecting Sybil Nodes using Social Networks.
Danezis, G., & Mittal, P. (2009) · UCL Discovery (University College London) · Cited by 481
Self-citationDesign and Evaluation of a Real-Time URL Spam Filtering Service
Thomas, K., Grier, C., Ma, J., Paxson, V., & Song, D. (2011) · 2011 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2011.25 · Cited by 468
An analysis of social network-based Sybil defenses
Viswanath, B., Post, A., Gummadi, K. P., & Mislove, A. (2010) · Proceedings of the ACM SIGCOMM 2010 conference · doi:10.1145/1851182.1851226 · Cited by 304
Sybil-resilient online content voting
Tran, N. H. K., Min, B., Li, J., & Subramanian, L. (2009) · Networked Systems Design and Implementation · Cited by 304
Yang, C., Harkreader, R., Zhang, J., Shin, S., & Gu, G. (2012) · Proceedings of the 21st international conference on World Wide Web · doi:10.1145/2187836.2187847 · Cited by 299 · cited 6×
“, SybilRank [13] and Criminal account Inference Algorithm [14].”
BackgroundMethodInfluentialCOMPA: Detecting Compromised Accounts on Social Networks.
Egele, M., Stringhini, G., Krügel, C., & Vigna, G. (2013) · UCL Discovery (University College London) · Cited by 293
Uncovering social network Sybils in the wild
Yang, Z., Wilson, C., Wang, X., Gao, T., Zhao, B. Y., & Dai, Y. (2014) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/2556609 · Cited by 290
BotGrep: finding P2P bots with structured graph analysis
Nagaraja, S., Mittal, P., Hong, C.-Y., Caesar, M., & Borisov, N. (2010) · University of Birmingham Research Portal (University of Birmingham) · Cited by 283
Self-citationSybillimit: a near-optimal social network defense against sybil attacks
Yu, H., Gibbons, P. B., Kaminsky, M., & Xiao, F. (2010) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2009.2034047 · Cited by 246
Measuring the mixing time of social graphs
Mohaisen, A., Yun, A., & Kim, Y. (2010) · Proceedings of the 10th ACM SIGCOMM conference on Internet measurement · doi:10.1145/1879141.1879191 · Cited by 189 · cited 3×
“Mohaisen et al. [30] found that such preprocessing will prune a large portion of nodes.”
BackgroundInfluentialSoK: The Evolution of Sybil Defense via Social Networks
Alvisi, L., Clement, A., Epasto, A., Lattanzi, S., & Panconesi, A. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.33 · Cited by 173 · cited 6×
“[15] showed that some simple detectors might enforce the social networks to be suitable for structure-based Sybil defenses if the attack edges are established randomly [15].”
BackgroundMethodInfluentialEvolution of social-attribute networks: measurements, modeling, and implications using google+
Gong, N. Z., Xu, W., Huang, L., Mittal, P., Stefanov, E., Sekar, V., & Song, D. (2012) · Proceedings of the 2012 Internet Measurement Conference · doi:10.1145/2398776.2398792 · Cited by 170 · cited 1×
“For SB-B, we randomly sample 100 nodes from the entire network including both benign and Sybil regions and treat them as Sybil labels.”
MethodSelf-citationUncovering social network sybils in the wild
Yang, Z., Wilson, C., Wang, X., Gao, T., Zhao, B. Y., & Dai, Y. (2011) · Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference · doi:10.1145/2068816.2068841 · Cited by 164 · cited 1×
“[19] showed that the friendship network in RenRen, the largest online social networking site in China, does not satisfy this assumption, and thus structure-based approaches should not be applied to such friendship networks.”
BackgroundSocial Turing Tests: Crowdsourcing Sybil Detection
Wang, G., Mohanlal, M., Wilson, C., Wang, X., Metzger, M. J., Zheng, H.-T., & Zhao, B. Y. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.3856 · Cited by 164 · cited 2×
“For example, labels got from crowdsourcing could have noise up to 35% [29].”
BackgroundAn analysis of social network-based Sybil defenses
Viswanath, B., Post, A., Gummadi, K. P., & Mislove, A. (2010) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1851275.1851226 · Cited by 161
Optimal Sybil-resilient node admission control
Tran, N. H. K., Li, J., Subramanian, L., & Chow, S. S. M. (2011) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2011.5935171 · Cited by 151 · cited 3×
“keeper [12] and SybilDefender [22] also leverage random walks.”
BackgroundMethodSybilDefender: Defend against sybil attacks in large social networks
Wei, W., Xu, F., Tan, C. C., & Li, Q. (2012) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2012.6195572 · Cited by 145 · cited 3×
“One method is to approximate trust relationships between users through looking into user interactions [20], inferring tie strengths [21], and asking users to rate their social contacts [22].”
BackgroundMethodKeep your friends close: Incorporating trust into social network-based Sybil defenses
Mohaisen, A., Hopper, N., & Kim, Y. (2011) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infcom.2011.5934998 · Cited by 123 · cited 1×
“In an ideal setting, G represents a weighted network of trust relationships between users, where the edge weights represent the levels of trust between users [17].”
BackgroundSybil Guard: Defending Against Sybil Attacks via Social Networks
Vasudevan, S. K., Sivaraman, R., & Karthick, M. R. (2010) · International Journal of Computer Applications · doi:10.5120/896-1270 · Cited by 80
An Analysis of Social Network-Based Sybil Defenses
Inaba, K., & Xiao, X. (2013) · Cited by 55
Predicting Links and Inferring Attributes using a Social-Attribute Network (SAN)Preprint
Gong, N. Z., Talwalkar, A., Mackey, L. W., Huang, L., Shin, E. C. R., Shin, R., & Stefanov, E. (2011) · arXiv (Cornell University) · Cited by 54
Self-citationSocial Turing Tests: Crowdsourcing Sybil Detection
Wang, G., Mohanlal, M., Wilson, C., Wang, X., Metzger, M. J., Zheng, H.-T., & Zhao, B. Y. (2012) · VTechWorks (Virginia Tech) · Cited by 51
Preventing Sybil Attacks by Privilege Attenuation: A Design Principle for Social Network Systems
Fong, P. W. L. (2011) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2011.16 · Cited by 50
Evolution of Social-Attribute Networks: Measurements, Modeling, and Implications using Google+Preprint
Gong, N. Z., Xu, W., Huang, L., Mittal, P., Stefanov, E., Sekar, V., & Song, D. X. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1209.0835 · Cited by 45 · cited 1×
“For SB-B, we randomly sample 100 nodes from the entire network including both benign and Sybil regions and treat them as Sybil labels.”
MethodSelf-citationPoisonedwater: An improved approach for accurate reputation ranking in P2P networks
Wang, Y., & Nakao, A. (2009) · Future Generation Computer Systems · doi:10.1016/j.future.2009.05.001 · Cited by 43 · cited 2×
“, front peers) [18], [23], which decreases the number of attack edges and increases the homophily.”
BackgroundJointly Predicting Links and Inferring Attributes using a Social-Attribute Network (SAN)Preprint
Gong, N. Z., Talwalkar, A., Mackey, L. W., Huang, L., Shin, E. C. R., Stefanov, E., Elaine, Shi, & Song, D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.3265 · Cited by 33 · cited 1×
“…for future work include evaluating Sybil-Belief and previous approaches with datasets containing real Sybils and applying our SybilBelief framework to other security and privacy problems such as graph based Botnet detection [44], reputation systems [37], and private information inference [45].”
MethodSelf-citationThe Latent Community Model for Detecting Sybils in Social Networks.
Cai, Z., & Jermaine, C. (2012) · Network and Distributed System Security Symposium · Cited by 31
Uncovering Social Network Sybils in the WildPreprint
Yang, Z. C., Wilson, C., Wang, X., Gao, T., Zhao, B. Y., & Dai, Y. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1106.5321 · Cited by 16 · cited 1×
“[19] showed that the friendship network in RenRen, the largest online social networking site in China, does not satisfy this assumption, and thus structure-based approaches should not be applied to such friendship networks.”
BackgroundTrust Management for Semantic Web
Tahajod, M., Iranmehr, A., & Khozooyi, N. (2009) · International Conference on Computer and Electrical Engineering · doi:10.1109/iccee.2009.241 · Cited by 16 · cited 1×
“ed to Sybil detection, is the trust propagation problem. Several approaches have been proposed to propagate trust scores or reputation scores in file-sharing networks or auction platforms (e.g., [32], [35], [36]). Similar to SybilRank [13] and CIA [14], these approaches are variants of the PageRank algorithm [37]. In p…”
Method
Cited by
Torky, M., & Hassanein, A. E. (2020) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2020.105476 · Cited by 390
Backdoor Attacks to Graph Neural Networks
Zhang, Z., Jia, J., Wang, B., & Gong, N. Z. (2021) · Proceedings of the 26th ACM Symposium on Access Control Models and Technologies · doi:10.1145/3450569.3463560 · Cited by 220
Self-citationPoisoning Attacks to Graph-Based Recommender Systems
Fang, M., Yang, G., Gong, N. Z., & Liu, J. (2018) · Proceedings of the 34th Annual Computer Security Applications Conference · doi:10.1145/3274694.3274706 · Cited by 204
“ion in social networks. Many methods have been developed for Sybil detection. „ese methods leverage IP addresses (e.g., [28]), user behavior (e.g., [32]), or social relationships between users (e.g., [8, 30, 31]). Since we do not have access to IP addresses nor social relationships of users, we explore a behavior base…”
BackgroundMethodSelf-citationDetection of malicious social bots: A survey and a refined taxonomy
Latah, M. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113383 · Cited by 94
(2017) · doi:10.1145/3038912.3052695 · Cited by 78
Self-citation
Metadata
- Authors
- Gong, N. Z., Frank, M., & Mittal, P.
- Venue
- IEEE Transactions on Information Forensics and Security
- Published
- 2014-06
- Volume
- 9
- Issue
- 6
- Pages
- 976-987
- ISSN
- 1556-6013 (ISSN-L)
- 1556-6021
- OpenAlex
- W2016707451
- Cited by
- 180
- References
- 55
- FWCI
- 28.66
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.