15-07-2011, 12:13 PM
Submitted by
M. I. MOHAMED AKRAM
K. SABANAYAGAN
J. SATHAM HUSSAIN
R. SRIBALAJI
[attachment=14477]
ABSTRACT
Open-access distributed systems such as peer-to-peer systems are particularly vulnerable to Sybil attacks, where a malicious user creates multiple fake identities (called Sybil nodes). Without a trusted central authority that can tie identities to real human beings, defending against Sybil attacks is quite challenging.
Among the small number of decentralized approaches, our recent SybilGuard protocol leverages a key insight on social networks to bound the number of Sybil nodes accepted. Despite its promising direction, SybilGuard can allow a large number of Sybil nodes to be accepted. Furthermore, SybilGuard assumes that social networks are fast-mixing, which has never been confirmed in the real world.
This project presents the novel SybilLimit protocol that leverages the same insight as SybilGuard, but offers dramatically improved and near-optimal guarantees. The number of Sybil nodes accepted is reduced by a factor or around 200 times in our experiments for a million-node system. We further prove that SybilLimit’s guarantee is at most a log n factor away from optimal when considering approaches based on fast-mixing social networks. Finally, based on three large-scale real-world social networks, we provide the first evidence that real-world social networks are indeed fast-mixing. This validates the fundamental assumption behind SybilLimit’s and SybilGuard’s approach.
CHAPTER - 1
1. INTRODUCTION
Decentralized distributed systems (such as peer-to-peer systems) are particularly vulnerable to sybil attacks, where a malicious user pretends to have multiple identities(called sybil identities or sybil nodes). In fact, such sybil attacks have already been observed in the real world in the Maze peer-to-peer system. Researchers have also demonstrated that it is surprisingly easy to launch sybil attacks in the widely-used eMule system. When a malicious user’s sybil nodes comprise a large fraction of the nodes in the system, that one user is able to “out vote” the honest users in a wide scope of collaborative tasks. Examples of such collaborative tasks range from Byzantine consensus and voting schemes for email spam to implicit collaboration in redundant routing and data replication in Distributed Hash Tables (DHTs). The exact form of such collaboration and the exact fraction of sybil nodes these collaborative tasks can tolerate may differ from case to case. However, a generic requirement is that the number of sybil nodes (compared to the number of honest users) needs to be properly bounded. To defend against sybil attacks, simply monitoring each node’s historical behavior is often insufficient because sybil nodes can behave nicely initially, and then launch an attack. Although a trusted central authority can thwart such attacks by issuing credentials to actual human beings or requiring payment, finding such a single entity that every user worldwide is willing to trust can be difficult or impossible (especially if that entity requires users to provide sensitive information). Without a trusted central authority, defending against sybil attacks is much harder. Among the small number of approaches, the simplest one perhaps is to bind identities to IP addresses or IP prefixes. Another approach is to require every identity to solve puzzles that require human effort, such as CAPTCHAs. Both approaches can provide only limited protection—the adversary can readily steal IP addresses with different prefixes in today’s Internet, while CAPTCHAs can be re-posted on an adversary’s website to be solved by users seeking access to that site.
1.1 Existing system(The SybilGuard approach)
Sybil-Guard, a protocol for defending against sybil attacks without relying on a trusted central authority. Sybil-Guard leverages a key insight regarding social networks. In a social network, the vertices (nodes) are identities in the distributed system and the (undirected) edges correspond to human-established trust relations in the real world. The edges connecting the honest region (i.e., the region containing all the honest nodes) and the sybil region (i.e., the region containing all the sybil identities created by malicious users) are called attack edges. SybilGuard ensures that the number of attack edges is independent of the number of sybil identities, and is limited by the number of trust relation pairs between malicious users and honest users. SybilGuard observes that if malicious users create too many sybil identities, the graph will have a small quotient cut—i.e., a small set of edges (the attack edges) whose removal disconnects a large number of nodes (all the sybil identities). On the other hand, “fast mixing” social networks do not tend to have such cuts. SybilGuard leverages the small quotient cut to limit the size of sybil attacks. SybilGuard is a completely decentralized protocol and enables any honest node V (called the verifier) to decide whether or not to accept another node S (called the suspect). “Accepting” means that V is willing to do collaborative tasks with S.
1.1.1 Drawbacks
SybilGuard suffers from two major limitations.
1. Although the end guarantees of SybilGuard are stronger than previous decentralized approaches, they are still rather weak in the absolute sense : Each attack edge allows O(√n log n) sybil nodes to be accepted.
The situation can get worse: When the number of attack edges g = (√n/ log n) SybilGuard can no longer bound the number of accepted sybil nodes at all.
2. SybilGuard critically relies on the assumption that social networks are fast mixing, an assumption that had never not been validated in the real world.
