DSybil: Optimal Sybil-Resistance for Recommendation Systems
Published 1 May 2009Open access
Haifeng Yu, Chenwei Shi, Michael Kaminsky, Phillip B. Gibbons, Feng Xiao
Citations113
SJR quartileQ4
SJR score0.11
SNIP0.06
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
DSybil provides strong provable guarantees that hold even under the worst-case attack and are optimal, and would continue to provide high-quality recommendations even when a million-node botnet uses an optimal strategy to launch a sybil attack.
Abstract
10.1109/SP.2009.26
Keywords
Computer ScienceDecision SciencesBusiness, Management and Accounting
Lecture notes in computer scienceThe Sybil Attack
4,328 Citations2002John R. Douceur
It is shown that, without a logically centralized authority, Sybil attacks are always possible except under extreme and unrealistic assumptions of resource parity and coordination among entities.
The Eigentrust algorithm for reputation management in P2P networks
3,353 Citations2003Sepandar Kamvar, Mario Schlösser +1 more
An algorithm to decrease the number of downloads of inauthentic files in a peer-to-peer file-sharing network that assigns each peer a unique global trust value, based on the peer's history of uploads is described.
Cambridge University Press eBooksPrediction, Learning, and Games
3,258 Citations2006Nicolò Cesa‐Bianchi, Gábor Lugosi
This chapter discusses prediction with expert advice, efficient forecasters for large classes of experts, and randomized prediction for specific losses.
SIAM Journal on ComputingThe Nonstochastic Multiarmed Bandit Problem
2,213 Citations2002Peter Auer, Nicolò Cesa‐Bianchi +2 more
A solution to the bandit problem in which an adversary, rather than a well-behaved stochastic process, has complete control over the payoffs.
Cambridge University Press eBooksProbability and Computing
1,708 Citations2005Michael Mitzenmacher, Eli Upfal
Lecture notes in computer scienceTrust Management for the Semantic Web
992 Citations2003Matthew Richardson, Rakesh Agrawal +1 more
A web of trust is employed, in which each user maintains trusts in a small number of other users, and these trusts are composed into trust values for all other users.
Communications of the ACMTelling humans and computers apart automatically
906 Citations2004Luis von Ahn, Manuel Blum +1 more
ACM Transactions on Sensor NetworksReputation-based framework for high integrity sensor networks
800 Citations2008Saurabh Ganeriwal, Laura Balzano +1 more
A Bayesian formulation, specifically a beta reputation system, is employed for the algorithm steps of reputation representation, updates, integration and trust evolution in sensor networks to allow the sensor nodes to develop a community of trust.
ACM Computing SurveysA survey of attack and defense techniques for reputation systems
773 Citations2009Kevin Hoffman, David Zage +1 more
This work contributes to understanding which design components of reputation systems are most vulnerable, what are the most appropriate defense mechanisms and how these defense mechanisms can be integrated into existing or future reputation systems to make them resilient to attacks.
ACM SIGOPS Operating Systems ReviewSecure routing for structured peer-to-peer overlay networks
752 Citations2002Miguel Castro, Peter Druschel +3 more
This paper studies attacks aimed at preventing correct message delivery in structured peer-to-peer overlays and presents defenses to these attacks, and describes and evaluates techniques that allow nodes to join the overlay, to maintain routing state, and to forward messages securely in the presence of malicious nodes.
Shilling recommender systems for fun and profit
643 Citations2004Shyong K. Lam, John Riedl
Four open questions are explored that may affect the effectiveness of shilling attacks on recommender systems: which recommender algorithm is being used, whether the application is producing recommendations or predictions, how detectable the attacks are by the operator of the system, and what the properties are of the items being attacked.
A reputation-based approach for choosing reliable resources in peer-to-peer networks
610 Citations2002Ernesto Damiani, De Capitani di Vimercati +3 more
This work proposes a self-regulating system where the P2P network is used to implement a robust reputation mechanism, and a distributed polling algorithm by which resource requestors can assess the reliability of a resource offered by a participant before initiating the download.
Proceedings - IEEE Symposium on Security and Privacy/Proceedings of the ... IEEE Symposium on Security and PrivacySybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks
570 Citations2008Haifeng Yu, Phillip B. Gibbons +2 more
Robust incentive techniques for peer-to-peer networks
567 Citations2004Michal Feldman, Kevin Lai +2 more
This work model the P2P system using the Generalized Prisoner's Dilemma, and proposes the Reciprocative decision function as the basis of a family of incentives techniques that can drive a system of strategic users to nearly optimal levels of cooperation.
ACM Transactions on Internet TechnologyToward trustworthy recommender systems
465 Citations2007Bamshad Mobasher, Robin Burke +2 more
This study shows that both user-based and item-based algorithms are highly vulnerable to specific attack models, but that hybrid algorithms may provide a higher degree of robustness.
An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms
399 Citations1988T. Leighton, S. Rao
The main result is an algorithm for performing the task provided that the capacity of each cut exceeds the demand across the cut by a Theta (log n) factor.
IEEE/ACM Transactions on NetworkingSybilGuard: Defending Against Sybil Attacks via Social Networks
388 Citations2008Haifeng Yu, Michael Kaminsky +2 more
This paper presents SybilGuard, a novel protocol for limiting the corruptive influences of sybil attacks, based on the "social network" among user identities, where an edge between two identities indicates a human-established trust relationship.
Secure routing for structured peer-to-peer overlay networks
328 Citations2002Miguel Castro, Peter Druschel +3 more
ACM Transactions on Internet TechnologyCollaborative recommendation
327 Citations2004Michael P. O’Mahony, Neil Hurley +2 more
This work analyzes the robustness of collaborative recommendation: the ability to make recommendations despite (possibly intentional) noisy product ratings, and formalizes recommendation accuracy in machine learning terms and develops theoretically justified models of accuracy.
Preventing shilling attacks in online recommender systems
310 Citations2005Paul‐Alexandru Chirita, Wolfgang Nejdl +1 more
Several metrics for analyzing rating patterns of malicious users are proposed and an algorithm for protecting recommender systems against shilling attacks is evaluated that can be employed for monitoring user ratings and removing shilling attacker profiles from the process of computing recommendations, thus maintaining the high quality of the recommendations.
Pollution in P2P file sharing systems
303 Citations2005Jian Liang, R. Senthil Kumar +2 more
A measurement study of the nature and magnitude of pollution in the FastTrack P2P network, currently the most popular P1P file sharing system, and an automated procedure to detect whether a given version is polluted or not.
Sybilproof reputation mechanisms
273 Citations2005Alice Cheng, Eric Friedman
This work uses a static graph formulation of reputation to give a general asymmetric reputation function based on flow and give conditions for sybilproofness, and shows that there is no symmetric sybilProof reputation function.
Sybil-resilient online content voting
261 Citations2009Nguyen H. Tran, Bonan Min +2 more
SumUp is presented, a Sybilresilient vote aggregation system that leverages the trust network among users to defend against Sybil attacks and uses the technique of adaptive vote flow aggregation to limit the number of bogus votes cast by adversaries to no more than theNumber of attack edges in the Trust network.
IEEE/ACM Transactions on NetworkingSybilLimit: A Near-Optimal Social Network Defense Against Sybil Attacks
244 Citations2009Haifeng Yu, Phillip B. Gibbons +2 more
The novel SybilLimit protocol is presented, which leverages the same insight as SybilGuard, but offers dramatically improved and near-optimal guarantees, and provides the first evidence that real-world social networks are indeed fast-mixing.
A reputation-based approach for choosing reliable resources in peer-to-peer networks
240 Citations2002Ernesto Damiani, De Capitani di Vimercati +3 more
Using and combining predictors that specialize
239 Citations1997Yoav Freund, Robert E. Schapire +2 more
It is shown how to transform algorithms that assume that all experts are always awake to algorithms that do not require this assumption, and how to derive corresponding loss bounds.
Conference on Workshop on Hot Topics in Understanding BotnetsMy botnet is bigger than yours (maybe, better than yours): why size estimates remain challenging
222 Citations2007Moheeb Abu Rajab, Jay Zarfoss +2 more
It is shown how several issues, including cloning, temporary migration, and hidden structures significantly increase the difficulty of determining botnet size with any accuracy.
Experience with an object reputation system for peer-to-peer filesharing
217 Citations2006Kevin Walsh, Emin Gün Sirer
Data from the live deployment shows that Credence's flow-based trust computation enables users to avoid undesirable content, and results from a long-term study of the trust network built by users are reported.
Machine LearningEmpirical Support for Winnow and Weighted-Majority Algorithms: Results on a Calendar Scheduling Domain
191 Citations1997Avrim Blum
A new variant on the Winnow algorithm is created that is especially suited to conditions with string-valued classifications, and an analysis of a policy for discarding predictors in Weighted-Majority that allows it to speed up as it learns.
Machine LearningRegret bounds for sleeping experts and bandits
175 Citations2010Robert Kleinberg, Alexandru Niculescu-Mizil +1 more
This work compares algorithms against the payoff obtained by the best ordering of the actions, which is a natural benchmark for this type of problem and gives algorithms achieving information-theoretically optimal regret bounds with respect to the best-ordering benchmark.
Computational Puzzles as Sybil Defenses
158 Citations2006Nikita Borisov
This work considers the problem of defending against Sybil attacks using computational puzzles by continually distributing locally generated challenges that are then incorporated into the puzzle solutions, and proposes a fully decentralized scheme to enforce this.
Ostra: leveraging trust to thwart unwanted communication
154 Citations2008Alan Mislove, Ansley Post +2 more
The system, Ostra, bounds the total amount of unwanted communication a user can produce based on the number of trust relationships the user has, and relies on the fact that it is difficult for a user to create arbitrarily many trust relationships to thwart unwanted communication.
Competitive recommendation systems
130 Citations2002Petros Drineas, Iordanis Kerenidis +1 more
This paper presents a notion of competitive recommendation systems, and presents a matrix reconstruction scheme that is competitive: it requires a small overhead in the number of users and products to be sampled, delivering in the process a net utility that closely approximates the best possible with full knowledge of all user-product preferences.
DSybil: Optimal Sybil-Resistance for Recommendation Systems
113 Citations2009Haifeng Yu, Chenwei Shi +3 more
DSybil provides strong provable guarantees that hold even under the worst-case attack and are optimal, and would continue to provide high-quality recommendations even when a million-node botnet uses an optimal strategy to launch a sybil attack.
Limiting Sybil Attacks in Structured P2P Networks
110 Citations2007Hosam Rowaihy, William Enck +2 more
An admission control system that mitigates Sybil attacks by adaptively constructing a hierarchy of cooperative peers and can place a ceiling on the number of IDs any adversary may obtain by requiring periodic reassertion of the IDs continued validity.
Lecture notes in computer scienceMaking Chord Robust to Byzantine Attacks
106 Citations2005Amos Fiat, Jared Saia +1 more
A variant of Chord is given which is robust with high probability for any time period during which there are always at least z total peers in the network for some integer z and the number of peer insertion and deletion events is no more than zk for some tunable parameter k.
Theory of Computing SystemsTowards a Scalable and Robust DHT
103 Citations2008Baruch Awerbuch, Christian Scheideler
It is shown that both of these threats can be handled in a scalable manner, even if a constant fraction of the peers in the system is adversarial, demonstrating that open systems for scalable distributed data storage that are robust against even massive adversarial behavior are feasible.
Recommendation systems: a probabilistic analysis
102 Citations2002Ravi Kumar, Prabhakar Raghavan +2 more
A simple analytical framework for recommendation systems is introduced, including a basis for defining the utility of such a system, and probabilistic analyses of algorithmic methods within this framework yield insights into how much utility can be derived from the memory of past actions.
The influence limiter
88 Citations2007Paul Resnick, Rahul Sami
An influence-limiting algorithm that can turn existing recommender systems into manipulation-resistant systems is described and both the influence limits and the information loss incurred due to those limits are described in terms of information-theoretic concepts of loss functions and entropies.
On the establishment of distinct identities in overlay networks
78 Citations2005Rida A. Bazzi, Goran Konjevod
Phalanx: withstanding multimillion-node botnets
75 Citations2008Colin Dixon, Thomas E. Anderson +1 more
The goal is to define a system that could be deployed in the next few years to address the danger from present-day massive botnets, called Phalanx, which leverages the power of swarms to combat DoS.
Journal of Machine Learning ResearchFrom External to Internal Regret
75 Citations2007BlumAvrim, MansourYishay
This paper gives a simple generic reduction that, given an algorithms for the external regret problem, converts it to an efficient online algorithm for the internal regret problem and derives a quantitative regret bound for a very general setting of regret.
Towards a scalable and robust DHT
71 Citations2006Baruch Awerbuch, Christian Scheideler
Improved recommendation systems
52 Citations2005Baruch Awerbuch, Boaz Patt-Shamir +2 more
The paper presents an O(m + n) time centralized algorithm and a distributed algorithm that can be implemented in a peer-to-peer model even in the presence of adaptively colluding malicious players, with only logarithmic over-head.
Journal of Computer and System SciencesCompetitive collaborative learning
47 Citations2007Baruch Awerbuch, Robert Kleinberg
This work develops algorithms for a multi-user online learning problem in which each user makes a sequence of decisions about selecting products or resources, and presents an algorithm whose expected regret per user is linear in the number of groups and only logarithmic in thenumber of resources.
Journal of Computer and System SciencesRecommendation Systems: A Probabilistic Analysis
41 Citations2001Ravi Kumar, Prabhakar Raghavan +2 more
The information cost of manipulation-resistance in recommender systems
41 Citations2008Paul Resnick, Rahul Sami
It is proved that any robust recommender system must also discard Ω(log (n/c)) units of useful information from each genuine rater, and used an information-theoretic framework to exhibit a fundamental tradeoff between manipulation-resistance and optimal use of genuine ratings in recommender systems.
Lecture notes in computer scienceManipulation-Resistant Reputations Using Hitting Time
27 Citations2007John E. Hopcroft, Daniel Sheldon
SOFIA: Social Filtering for Robust Recommendations
24 Citations2008Matteo Dell’Amico, Licia Capra
It is argued that, in order to be trusted, users must be both well-intentioned and competent, and so SOFIA, an algorithm realising this approach, is described and validated, in terms of accuracy and robustness, on two real large-scale datasets.
Collaboration of untrusting peers with changing interests
24 Citations2004Baruch Awerbuch, Boaz Patt-Shamir +2 more
This paper introduces a framework for optimizing reputation systems for objects in an asynchronous setting, and in the context of restricted access to the objects, where access may be restricted in time and inspace.
Collaborate with strangers to find own preferences
20 Citations2005Baruch Awerbuch, Yossi Azar +3 more
Internet MathematicsManipulation-Resistant Reputations Using Hitting Time
18 Citations2008John E. Hopcroft, Daniel Sheldon
A reputation system based on hitting time is developed and it is shown that it resists tampering by individuals or groups who strategically place outlinks; conventional algorithms do not scale adequately.
Lecture notes in computer sciencePervasive Random Beacon in the Internet for Covert Coordination
16 Citations2005Hui Huang Lee, Ee‐Chien Chang +1 more
This paper discusses the desirable properties of a pervasive random beacon which can be used for covert coordination, and describes how such a beacon can be found in the Internet based on major stock market indices closing values.
Theory of Computing SystemsTell Me Who I Am: An Interactive Recommendation System
15 Citations2008Noga Alon, Baruch Awerbuch +2 more
A distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player’s real preference vector after a polylogarithmic number of rounds.
Online collaborative filtering with nearly optimal dynamic regret
8 Citations2007Baruch Awerbuch, Thomas P. Hayes
An algorithm is presented whose expected dynamic regret per honest player is optimal up to a multiplicative constant and an additive polylogarithmic term, assuming the number of options is bounded.
Adaptive Collaboration in Peer-to-Peer Systems
7 Citations2005Baruch Awerbuch, Boaz Patt-Shamir +2 more
It is proven that no algorithm could guarantee individual cost of less than Omega(1/alpha), which is essentially constant if there are enough honest players, and the main result is a new algorithm that achieves O(1) individual cost when there are many honestPlayers, and achieves individual cost O((1/ alpha)(log n/ log log n)) even when there is not.
Theory of Computing SystemsCollaborate with Strangers to Find Own Preferences
6 Citations2007Baruch Awerbuch, Yossi Azar +3 more
A sequential and a parallel algorithm is presented to solve the problem with logarithmic cost overhead of a model with n players and m objects, and considers players whose preference vectors are popular, i.e., players whose preferences are common to many other players.
Lecture notes in computer scienceAsynchronous Active Recommendation Systems
4 Citations2007Baruch Awerbuch, Aviv Nisgav +1 more
This paper presents the first low-overhead algorithms that can provably reconstruct the preferences of players under asynchronous scheduling, and presents algorithms in this model for exact and approximate preference reconstruction.
Learning specialist decision lists
1 Citations1999Atsuyoshi Nakamura
Preliminary experiments verify that SWML and SFixed-Loss-Update outperform S-L Loss-Update not only when outcomes are generated by an SDL, but also when good performing specialists sometimes suffer big losses.