Exploiting Trust and Distrust Information to Combat Sybil Attack in Online Social Networks

Huanhuan Zhang, Chang Xu, Jie ZhangIFIPTM 2014 · OpenReview

Abstract

Due to open and anonymous nature, online social networks are particularly vulnerable to the Sybil attack, in which a malicious user can fabricate many dummy identities to attack the systems. Recently, there is a flurry of interests to leverage social network structure for Sybil defense. However, most of graph-based approaches pay little attention to the distrust information, which is an important factor for uncovering more Sybils. In this paper, we propose an unified ranking mechanism by leveraging trust and distrust in social networks against such kind of attacks based on a variant of the PageRank-like model. Specifically, we first use existing topological anti-Sybil algorithms as a subroutine to produce reliable Sybil seeds. To enhance the robustness of these approaches against target attacks, we then also introduce an effective similarity-based graph pruning technique utilizing local structure similarity. Experiments show that our approach outperforms existing competitive methods for Sybil detection in social networks.

Introduction

Online Social Networks (OSNs) like Facebook and Twitter are increasingly targeted by Sybil attacks, where a single adversary creates numerous fake identities to manipulate social influence, spread spam, or rig voting systems. Traditional defenses rely on the "social graph" structure, assuming that while Sybils can easily link to each other, they struggle to form many links with honest users—a property known as a "small cut."

However, these methods face two significant challenges: targeted attacks, where attackers successfully link to highly trusted nodes to evade detection, and the "fast mixing" myth, where real-world social data often fails to meet the mathematical assumptions required for standard random-walk algorithms to be effective.

The Unified Ranking Mechanism

To address these vulnerabilities, this paper introduces a three-stage unified ranking mechanism that incorporates both trust and distrust signals.

1. Similarity-Based Graph Pruning

To neutralize targeted attacks, the system employs a pruning technique based on local neighborhood similarity. By calculating the number of common friends between connected nodes, the algorithm removes edges that lack sufficient social support. This leverages the "link dependency" property: while an attacker can trick an individual into a connection, it is significantly harder to infiltrate an entire social circle.

2. Sybil Seed Selection and Network Topology

Unlike traditional models that only utilize honest seeds, this approach identifies "Sybil seeds" to serve as negative anchors in the ranking process.

Conceptual model of a social network under Sybil attack, illustrating the Non-Sybil and Sybil regions, attack edges, and the placement of trusted and Sybil seeds.

As illustrated in the figure above, the network is conceptually divided into a Non-Sybil region and a Sybil region, connected by "Attack Edges." By identifying both a "Trusted Identity" and a "Sybil Seed," the system can propagate scores from both ends of the spectrum to more accurately delineate the boundary between honest and malicious nodes.

3. Unified Ranking Algorithm

The core of the system is a variant of Personalized PageRank (PPR) that propagates two distinct scores through the network:

  • Trust scores (TR): Positive scores originating from honest seeds.
  • Distrust scores (DTR): Negative scores originating from identified Sybil seeds.

The final trustworthiness of a node $v_i$ is determined by a weighted sum: $Total(v_i) = a \cdot TR(v_i) + (1-a) \cdot DTR(v_i)$.

Experimental Evaluation

The researchers evaluated the approach using real-world social graph datasets from the SNAP repository, including Facebook, AstroPh (Astrophysics citations), and HepTh (High Energy Physics Theory citations). Synthetic Sybil regions were added using both Random Graph (ER) and Scale-Free (PA) models to simulate various attack scenarios.

Key Results

  • Pruning Effectiveness: Under targeted attacks, applying the pruning technique (specifically with a diameter $T_p=2$) restored the Area Under the Curve (AUC) for detection to near-perfect levels, whereas standard models saw significant performance drops.
  • Lower Error Rates: In small-scale attack simulations, the Unified Ranking (UR) consistently produced fewer misclassified nodes than the popular SybilRank + Node Ranking (SR+NR) baseline.
  • Resilience of Distrust Signals: The model proved remarkably stable; even when relying heavily on distrust information, it outperformed traditional trust-only models by preventing trust "leakage" into malicious regions.

Conclusion

By leveraging distrust as an underutilized asset and implementing local structural pruning, the proposed unified ranking mechanism provides a robust defense against sophisticated Sybil attacks. While the system currently relies on a human "Oracle" for final Sybil seed confirmation, it represents a significant step toward more resilient and accurate social network security.

Summary updated

Abstract

Due to open and anonymous nature, online social networks are particularly vulnerable to the Sybil attack, in which a malicious user can fabricate many dummy identities to attack the systems. Recently, there is a flurry of interests to leverage social network structure for Sybil defense. However, most of graph-based approaches pay little attention to the distrust information, which is an important factor for uncovering more Sybils. In this paper, we propose an unified ranking mechanism by leveraging trust and distrust in social networks against such kind of attacks based on a variant of the PageRank-like model. Specifically, we first use existing topological anti-Sybil algorithms as a subroutine to produce reliable Sybil seeds. To enhance the robustness of these approaches against target attacks, we then also introduce an effective similarity-based graph pruning technique utilizing local structure similarity. Experiments show that our approach outperforms existing competitive methods for Sybil detection in social networks.
BibTeX
@inproceedings{zhang2014exploiting,
  author = {Huanhuan Zhang and Chang Xu and Jie Zhang},
  title = {{Exploiting Trust and Distrust Information to Combat Sybil Attack in Online Social Networks}},
  booktitle = {IFIPTM},
  year = {2014},
  url = {https://openreview.net/forum?id=I1Hk9_YXW0M},
}
Figure