Defending against Sybil Attacks

Speaker:	Dr. Haifeng YU
		Department of Computer Science
		National University of Singapore

Title:		"Defending against Sybil Attacks"

Date:		Wednesday, 12 May 2010

Time:		11:00 am - 12 noon

Venue:		Room 3405 (via lift 17/18), HKUST

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.


*******************
Biography:

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 \url{http://www.comp.nus.edu.sg/~yuhf}.