DATE:Monday, June 2, 2008
TIME:1:00pm – 2:00pm
PLACE: Intel Research Pittsburgh, 4720 Forbes Avenue, CIC Building 4th Floor, Suite 410


Haifeng Yu
National University of Singapore

Defending against Sybil Attacks via Social Networks

Peer-to-peer and other decentralized, distributed systems are known to be particularly vulnerable to sybil attacks where a malicious user pretends to have multiple (fake) identities. By controlling a large fraction of the identities in the system, the single malicious user is able to "out vote" the honest users in a wide scope of collaborative tasks.

In this talk, I will present SybilLimit, a novel protocol for limiting the corruptive influences of sybil attacks. SybilLimit is based on the social network among user identities, where edges correspond to human-established trust relationship. Malicious users can create many identities but disproportionally-few trust relationships. SybilLimit exploits this observation to bound the number of fake identities, providing strong and provable end guarantees. I will further show that SybilLimit's guarantee is at most a log(n) factor away from the optimal. Finally, I will present experimental results from real-world social networks to validate SybilLimit's approach.

This talk is based on two papers in [SIGCOMM'06] and [IEEE S&P'08]. Both are available at

Haifeng Yu is currently an Assistant Professor at Department of Computer Science, National University of Singapore. Previously he was a Researcher at Intel Research Pittsburgh and an Adjunct Assistant Professor at Department of Computer Science, Carnegie Mellon University. Haifeng received his Ph.D. (2002) from Duke University. Haifeng's research interests cover the general area of distributed systems, as well as related fields such as fault-tolerance, large-scale peer-to-peer systems, distributed computing, and distributed systems security. More information is available at

For Further Seminar Info:

Coordinator: Shellee Lank,

, or visit