In the design of distributed systems, defending against Sybil attack is an important issue. Recently, OSN (Online Social Network)-based Sybil defending approaches, which use the fast mixing property of a social network graph with sufficient length of random walks and provide Sybil-resistant trust values, have been proposed. However, because of the probabilistic property of the previous approaches, some honest (non-Sybil) identities obtain low trust value and they are mistakenly considered as Sybil identities. A simple solution of boosting the trust value of honest identities is using longer random walks, but this direct boosting method also increases trust values of Sybil identities significantly. In this paper, a two-step boosting method is proposed to increase the Sybil-resistant trust value of honest identities reasonably and to prevent Sybil identities from having high trust values. The proposed boosting method is composed of two steps: initializing the trust value with a reasonably long random walks and boosting the trust value by using much longer random walks than the first step. The proposed method is evaluated by using sampled social network graphs of Facebook, and it is observed that the proposed method reduces the portion of honest identities mistakenly considered as Sybil identities substantially (from 30% to 1.3%) and keeps the low trust values of Sybil identities.

The social network model has been regarded as a promising mechanism to defend against Sybil attack. This model assumes that honest peers and Sybil peers are connected by only a small number of attack edges. Detection of the attack edges plays a key role in restraining the power of Sybil peers. In this paper, an attack-resisting, distributed algorithm, named Random walk and Social network model-based clustering (RSC), is proposed to detect the attack edges. In RSC, peers disseminate random walk packets to each other. For each edge, the number of times that the packets pass this edge reflects the betweenness of this edge. RSC observes that the betweennesses of attack edges are higher than those of the non-attack edges. In this way, the attack edges can be identified. To show the effectiveness of RSC, RSC is integrated into an existing social network model-based algorithm called SOHL. The results of simulations with real world social network datasets show that RSC remarkably improves the performance of SOHL.