A sybil defense Mechanism that leverages the network topologies

Distributed systems are vulnerable to sybil attacks , in which an adversary creates many bogus identities, called Sybil identities, and compromises the running of the system or pollutes the system with fake information. The sybil identities can “suppress” the honest identities in a variety of tasks, including online content ranking, DHT routing, file sharing, reputation systems, and Byzantine failure defenses. There are some similar attacks in ad hc and sensor networks . Sybil attacks can be mitigated by assuming the existence of a trusted authority, which can rate-limit the introduction of fake identities by requiring the users to provide some credentials, like social security number, or by requiring payment. However, such requirements will prevent users from accepting these systems, as they impose additional burdens on users. Recently, there has been an increasing interest in defending against sybil attacks in social networks. In a social network, two user identities share a link if a relationship is established between them. Each identity is represented as a node in the social graph. To prevent the adversary from creating many sybil identities, all the previous sybil defense schemes are built upon the assumption that the number of links between the sybil nodes and the honest nodes, also known as attack edges, is limited. Although an adversary can create many sybil nodes and link them in an arbitrary way, there will be a small cut between the honest region and the sybil region. The small cut consists of all the attack edges and its removal disconnects the sybil nodes from the rest of the graph, which is leveraged by previous schemes to identify the sybil nodes. Note that the solution to this problem is non-trivial, because finding small cuts in a graph is an NP hard problem. To limit the number of attack edges, previous schemes assume that all the relationships in social networks are trusted and they reflect the trust relationships among those users in the real world, and thus an adversary cannot establish many relationships with the honest users. It has been shown that this assumption does not hold in some real-world social networks.