One promising way to defend against sybil attacks in social networks is to leverage the social network topologies. Decentralized algorithms, SybilGuard and SybilLimit to determine whether a suspect node is Sybil or not. SybilGuard and SybilLimit both rely on the assumption that social networks are fast mixing (explained later), and the number of attack edges is limited. To identify sybil nodes, the schemes make use of random routes, a special kind of random walks in which each node uses a pre-computed random permutation as a one-to-one mapping from incoming edges to outgoing edges. SybilGurad suffers from high false negatives, as each attack edge may introduce O(√n log n) sybil nodes without being detected. The improved version of SybilGuard, SybilLimit, reduces this value to O(log n), which is still larger than the proved lower bound by a log n factor. Moreover, to detect the sybil region with SybilGuard or SybilLimit, all the suspect nodes in the social graph need to be tested. By contrast, with our sybil community detection algorithm, the sybil community around a sybil node can be detected in one run of the algorithm. GateKeeper is another decentralized sybil defense scheme that heavily relies on the assumption that the social networks are random expander. This is a strong assumption which has not been validated by previous research. Our evaluation shows that GateKeeper suffers from high false positive and negative rates and cannot effectively identify sybil nodes on the real-world asymmetric social topologies.
You are here: Home / ieee projects 2013-2014 / Sybil defender Is Efficient and Scalable To Large Social Networks