Theory Talk
October 28, 2009
4:00 p.m., AKW 500

Sign up to meet with speaker.

Speaker: Haifeng Yu, National University of Singapore
Title: Defending against Sybil Attacks

Abstract: Many distributed systems today are known to be particularly vulnerable to sybil attacks where a malicious user creates numerous or even unlimited number of fake identities. By controlling a large fraction of the identities in the system, the single malicious user is able to "out vote" all the honest users in a wide scope of collaborative tasks.

This talk will first 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. Exploiting this observation, SybilLimit providing strong, provable, and near-optimal (within log(n) factor) end guarantees. I will also briefly present experimental results from real-world social networks to validate SybilLimit's approach.

SybilLimit's social network based approach provides sufficiently strong guarantee for most applications except for recommendation systems, which are significantly more vulnerable to sybil identities than other systems. Thus I will further present DSybil, a novel sybil defense mechanism particularly designed for recommendation systems. DSybil uses feedback information in recommendation systems, and provides strong, provable, and optimal guarantees. It exploits the heavy-tail distribution of the typical voting behavior of the honest identities. Our evaluation shows that DSybil would continue to provide high-quality recommendations even with potential sybil attacks from a million-node botnet.

Bio: 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/algorithms, with particular emphasis on distributed systems security and availability. More information is available at http://www.comp.nus.edu.sg/~yuhf .