More Web Proxy on the site http://driver.im/

research-article

Free access

Strength in Numbers: Robust Tamper Detection in Crowd Computations

Authors:

Bimal Viswanath,

Muhammad Ahmad Bashir,

Muhammad Bilal Zafar,

Krishna P. Gummadi,

Alan MisloveAuthors Info & Claims

COSN '15: Proceedings of the 2015 ACM on Conference on Online Social Networks

Pages 113 - 124

https://doi.org/10.1145/2817946.2817964

Published: 02 November 2015 Publication History

Abstract

Popular social and e-commerce sites increasingly rely on crowd computing to rate and rank content, users, products and businesses. Today, attackers who create fake (Sybil) identities can easily tamper with these computations. Existing defenses that largely focus on detecting individual Sybil identities have a fundamental limitation: Adaptive attackers can create hard-to-detect Sybil identities to tamper arbitrary crowd computations.

In this paper, we propose Stamper, an approach for detecting tampered crowd computations that significantly raises the bar for evasion by adaptive attackers. Stamper design is based on two key insights: First, Sybil attack detection gains strength in numbers: we propose statistical analysis techniques that can determine if a large crowd computation has been tampered by Sybils, even when it is fundamentally hard to infer which of the participating identities are Sybil. Second, Sybil identities cannot forge the timestamps of their activities as they are recorded by system operators; Stamper analyzes these unforgeable timestamps to foil adaptive attackers. We applied Stamper to detect tampered computations in Yelp and Twitter. We not only detected previously known tampered computations with high accuracy, but also uncovered tens of thousands of previously unknown tampered computations in these systems.

References

[1]

http://en.wikipedia.org/wiki/Statistical_distance.

[2]

http://tinyurl.com/guardian-cf-p.

[3]

http://tinyurl.com/nyt-haggl.

[4]

http://tinyurl.com/nyt-tw-sale.

[5]

http://tinyurl.com/twitter-inactive.

[6]

http://tinyurl.com/yelp-bought.

[7]

http://tinyurl.com/yelp-consumer-alert.

[8]

http://tinyurl.com/yelp-filter.

[9]

http://tinyurl.com/yelp-filter-explained.

[10]

http://tinyurl.com/yelp-halt.

[11]

http://tinyurl.com/yelp-suspend.

[12]

F. Benevenuto, G. Magno, T. Rodrigues, and V. Almeida. Detecting spammers on twitter. In Proceedings of the 7th Annual Collaboration, Electronic messaging, Anti-Abuse and Spam Conference (CEAS), 2010.

[13]

A. Beutel, W. Xu, V. Guruswami, C. Palow, and C. Faloutsos. Copycatch: stopping group attacks by spotting lockstep behavior in social networks. In Proceedings of the 22nd international conference on World Wide Web (WWW), 2013.

Digital Library

[14]

NIST/SEMATECH e-Handbook of Statistical Methods. http://www.itl.nist.gov/div898/handbook/.

[15]

Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro. Aiding the detection of fake accounts in large scale social online services. In Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation (NSDI), 2012.

Digital Library

[16]

Q. Cao, X. Yang, J. Yu, and C. Palow. Uncovering large groups of active malicious accounts in online social networks. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2014.

Digital Library

[17]

R. T. Clemen and R. L. Winkler. Combining probability distributions from experts in risk analysis. Risk analysis, 19(2):187--203, 1999.

[18]

J. Douceur. The Sybil Attack. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.

Digital Library

[19]

S. Feng, L. Xing, A. Gogar, and Y. Choi. Distributional footprints of deceptive product reviews. In Proceedings of the the 6th International AAAI Conference on Weblogs and Social Media (ICWSM), 2012.

[20]

M. Gabielkov and A. Legout. The complete picture of the twitter social graph. In Proceedings of the 2012 ACM conference on CoNEXT student workshop, 2012.

Digital Library

[21]

S. Ghosh, B. Viswanath, F. Kooti, N. K. Sharma, G. Korlam, F. Benevenuto, N. Ganguly, and K. P. Gummadi. Understanding and combating link farming in the twitter social network. In Proceedings of the 21st International Conference on World Wide Web (WWW), 2012.

Digital Library

[22]

V. J. Hodge and J. Austin. A survey of outlier detection methodologies. Artificial Intelligence Review, 22(2):85--126, 2004.

Digital Library

[23]

A. M. Kakhki, C. Kliman-Silver, and A. Mislove. Iolaus: Securing online content rating systems. In Proceedings of the 22nd International World Wide Web Conference (WWW), 2013.

Digital Library

[24]

S. Kullback and R. A. Leibler. On information and sufficiency. The Annals of Mathematical Statistics, 22(1):79--86, 1951.

[25]

A. Lakhina, M. Crovella, and C. Diot. Diagnosing Network-wide Traffic Anomalies. In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication (SIGCOMM, 2004.

Digital Library

[26]

E.-P. Lim, V.-A. Nguyen, N. Jindal, B. Liu, and H. W. Lauw. Detecting product review spammers using rating behaviors. In Proceedings of the 19th ACM international conference on Information and knowledge management (CIKM), 2010.

Digital Library

[27]

M. Motoyama, D. McCoy, K. Levchenko, S. Savage, and G. M. Voelker. Dirty jobs: The role of freelance labor in web service abuse. In Proceedings of the 20th USENIX conference on Security (Usenix Security), 2011.

Digital Library

[28]

J. X. Parreira, D. Donato, C. Castillo, and G. Weikum. Computing trusted authority scores in peer-to-peer web search networks. In Proceedings of the 3rd International workshop on Adversarial information retrieval on the web, 2007.

Digital Library

[29]

B. C. Roy. The Birth of a Word. PhD thesis, MIT Media Lab, Feb 2013. http://web.media.mit.edu/bcroy/papers/bcroy-thesis_FINAL-sm.pdf.

Digital Library

[30]

R. R. Sillito and R. B. Fisher. Semi-supervised learning for anomalous trajectory detection. In Proceedings of the British Machine Vision Conference 2008 (BMVC), 2008.

[31]

G. Stringhini, M. Egele, C. Kruegel, and G. Vigna. Poultry markets: on the underground economy of twitter followers. In Proceedings of the 2012 ACM workshop on Workshop on Online Social Networks, 2012.

Digital Library

[32]

G. Stringhini, G. Wang, M. Egele, C. Kruegel, G. Vigna, H. Zheng, and B. Y. Zhao. Follow the green: growth and dynamics in twitter follower markets. In Proceedings of the 2013 conference on Internet measurement conference (IMC), 2013.

Digital Library

[33]

K. Thomas, D. McCoy, C. Grier, A. Kolcz, and V. Paxson. Trafficking fraudulent accounts: The role of the underground market in twitter spam and abuse. In Proceedings of the 22nd USENIX Security Symposium (USENIX Security), 2013.

Digital Library

[34]

N. Tran, B. Min, J. Li, and L. Subramanian. Sybil-resilient online content voting. In Proceedings of the 6th Symposium on Networked Systems Design and Implementation (NSDI), 2009.

Digital Library

[35]

B. Viswanath, M. A. Bashir, M. Crovella, S. Guha, K. P. Gummadi, B. Krishnamurthy, and A. Mislove. Towards Detecting Anomalous User Behavior in Online Social Networks. In Proceedings of the 23rd USENIX Security Symposium (Usenix Security).

Digital Library

[36]

B. Viswanath, M. Mondal, A. Clement, P. Druschel, K. P. Gummadi, A. Mislove, and A. Post. Exploring the design space of social network-based Sybil defense. In Proceedings of the 4th International Conference on Communication Systems and Network (COMSNETS), 2012.

[37]

G. Wang, T. Konolige, C. Wilson, X. Wang, H. Zheng, and B. Y. Zhao. You Are How You Click: Clickstream Analysis for Sybil Detection. In Proceedings of the 22nd USENIX Security Symposium (Usenix Security), 2013.

Digital Library

[38]

G. Wang, T. Wang, H. Zheng, and B. Y. Zhao. Man vs. machine: Practical adversarial detection of malicious crowdsourcing workers. In Proceedings of the 23rd USENIX Security Symposium (Usenix Security), 2014.

Digital Library

[39]

G. Wang, C. Wilson, X. Zhao, Y. Zhu, M. Mohanlal, H. Zheng, and B. Y. Zhao. Serf and turf: crowdturfing for fun and profit. In Proceedings of the 21st International conference on World Wide Web (WWW), 2012.

Digital Library

[40]

G. Wu, D. Greene, B. Smyth, and P. Cunningham. Distortion as a validation criterion in the identification of suspicious reviews. In Proceedings of the First Workshop on Social Media Analytics, 2010.

Digital Library

[41]

Z. Yang, C. Wilson, X. Wang, T. Gao, B. Y. Zhao, and Y. Dai. Uncovering social network Sybils in the wild. In Proceedings of the 11th ACM/USENIX Internet Measurement Conference (IMC), 2011.

Digital Library

[42]

H. Yu, C. Shi, M. Kaminsky, P. B. Gibbons, and F. Xiao. DSybil: Optimal sybil-resistance for recommendation systems. In Proceedings of the 2009 30th IEEE Symposium on Security and Privacy (IEEE S&P), 2009.

Digital Library

Cited By

Pratelli MPetrocchi MSaracco FDe Nicola R(2023)Swinging in the States: Does disinformation on Twitter mirror the US presidential election system?Companion Proceedings of the ACM Web Conference 202310.1145/3543873.3587638(1395-1403)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543873.3587638
Yadav UGupta BPeraković DPeñalvo FCvitić I(2022)Security and Privacy of Cloud-Based Online Online Social Media: A SurveySustainable Management of Manufacturing Systems in Industry 4.010.1007/978-3-030-90462-3_14(213-236)Online publication date: 1-Feb-2022
https://doi.org/10.1007/978-3-030-90462-3_14
Fazzolari MBuccafurri FLax GPetrocchi M(2021)ExperienceJournal of Data and Information Quality10.1145/343930713:1(1-16)Online publication date: 13-Jan-2021
https://dl.acm.org/doi/10.1145/3439307
Show More Cited By

Index Terms

Strength in Numbers: Robust Tamper Detection in Crowd Computations

Recommendations

An analysis of social network-based Sybil defenses
SIGCOMM '10

Recently, there has been much excitement in the research community over using social networks to mitigate multiple identity, or Sybil, attacks. A number of schemes have been proposed, but they differ greatly in the algorithms they use and in the ...
An analysis of social network-based Sybil defenses
SIGCOMM '10: Proceedings of the ACM SIGCOMM 2010 conference

Recently, there has been much excitement in the research community over using social networks to mitigate multiple identity, or Sybil, attacks. A number of schemes have been proposed, but they differ greatly in the algorithms they use and in the ...
Exploiting Temporal Dynamics in Sybil Defenses
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security

Sybil attacks present a significant threat to many Internet systems and applications, in which a single adversary inserts multiple colluding identities in the system to compromise its security and privacy. Recent work has advocated the use of social-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

COSN '15: Proceedings of the 2015 ACM on Conference on Online Social Networks

November 2015

280 pages

ISBN:9781450339513

DOI:10.1145/2817946

General Chair:
Aneesh Sharma
Twitter, USA
,
Program Chairs:
Rakesh Agrawal
Data Insights Laboratories, USA
,
Matthias Grossglauser
EPFL, Switzerland

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 November 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

COSN'15

Sponsor:

ACM

COSN'15: Conference on Online Social Networks

November 2 - 3, 2015

California, Palo Alto, USA

Acceptance Rates

COSN '15 Paper Acceptance Rate 22 of 82 submissions, 27%;

Overall Acceptance Rate 69 of 307 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
584
Total Downloads

Downloads (Last 12 months)116
Downloads (Last 6 weeks)21

Reflects downloads up to 25 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pratelli MPetrocchi MSaracco FDe Nicola R(2023)Swinging in the States: Does disinformation on Twitter mirror the US presidential election system?Companion Proceedings of the ACM Web Conference 202310.1145/3543873.3587638(1395-1403)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543873.3587638
Yadav UGupta BPeraković DPeñalvo FCvitić I(2022)Security and Privacy of Cloud-Based Online Online Social Media: A SurveySustainable Management of Manufacturing Systems in Industry 4.010.1007/978-3-030-90462-3_14(213-236)Online publication date: 1-Feb-2022
https://doi.org/10.1007/978-3-030-90462-3_14
Fazzolari MBuccafurri FLax GPetrocchi M(2021)ExperienceJournal of Data and Information Quality10.1145/343930713:1(1-16)Online publication date: 13-Jan-2021
https://dl.acm.org/doi/10.1145/3439307
Liu RLiu RPugliese ASubrahmanian V(2020)STARSACM Transactions on Intelligent Systems and Technology10.1145/339746311:5(1-25)Online publication date: 24-Jul-2020
https://dl.acm.org/doi/10.1145/3397463
Fazzolari MPratelli MMartinelli FPetrocchi M(2020)Emotions and Interests of Evolving Twitter Bots2020 IEEE Conference on Evolving and Adaptive Intelligent Systems (EAIS)10.1109/EAIS48028.2020.9122703(1-8)Online publication date: May-2020
https://doi.org/10.1109/EAIS48028.2020.9122703
Spognardi APetrocchi M(2020)On the Robustness of Rating Aggregators Against Injection AttacksDisinformation in Open Online Media10.1007/978-3-030-61841-4_14(205-217)Online publication date: 19-Oct-2020
https://doi.org/10.1007/978-3-030-61841-4_14
Tardelli SAvvenuti MTesconi MCresci S(2020)Characterizing Social Bots Spreading Financial DisinformationSocial Computing and Social Media. Design, Ethics, User Behavior, and Social Network Analysis10.1007/978-3-030-49570-1_26(376-392)Online publication date: 10-Jul-2020
https://doi.org/10.1007/978-3-030-49570-1_26
Cresci SLillo FRegoli DTardelli STesconi M(2019)Cashtag PiggybackingACM Transactions on the Web10.1145/331318413:2(1-27)Online publication date: 3-Apr-2019
https://dl.acm.org/doi/10.1145/3313184
Cresci SPetrocchi MSpognardi ATognazzi SBoldi PWelles BKinder-Kurlanda KWilson CPeters IMeira W(2019)Better Safe Than SorryProceedings of the 10th ACM Conference on Web Science10.1145/3292522.3326030(47-56)Online publication date: 26-Jun-2019
https://dl.acm.org/doi/10.1145/3292522.3326030
Tai XSoska KChristin NTeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Adversarial Matching of Dark Net Market Vendor AccountsProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330763(1871-1880)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330763
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten