Abstract
This paper examines the impact of heavy churn on the robustness of decentralized social network-based Sybil defense (SNSD) schemes. Our analysis reveals that (i) heavy churn disintegrates the social overlay network that is fundamental to these schemes into multiple disconnected components, resulting in poor network connectivity, and (ii) a naive solution that adds links from each node to all its 2-hop neighbors improves network connectivity but comes at a significant cost of poor attack resilience of these schemes.
We propose a new design point in the trade-off between network connectivity and attack resilience of SNSD schemes, where each node adds links to only a selective few of all its 2-hop neighbors based on a minimum expansion contribution (MinEC) heuristic. Extensive evaluation through simulations shows that our approach fares as good as the naive 2-hop solution in terms of network connectivity, while making little compromise on the attack resilience. Moreover, our approach preserves the fast-mixing property that is fundamental to many SNSD schemes even at high levels of churn. This result suggests that existing and potential future SNSD schemes relying on this property can incorporate our approach into their designs with minimal changes.
We propose a new design point in the trade-off between network connectivity and attack resilience of SNSD schemes, where each node adds links to only a selective few of all its 2-hop neighbors based on a minimum expansion contribution (MinEC) heuristic. Extensive evaluation through simulations shows that our approach fares as good as the naive 2-hop solution in terms of network connectivity, while making little compromise on the attack resilience. Moreover, our approach preserves the fast-mixing property that is fundamental to many SNSD schemes even at high levels of churn. This result suggests that existing and potential future SNSD schemes relying on this property can incorporate our approach into their designs with minimal changes.
Original language | English |
---|---|
Title of host publication | ASIA CCS'15 |
Subtitle of host publication | Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security |
Place of Publication | New York, NY |
Publisher | Association for Computing Machinery (ACM) |
Pages | 507-518 |
Number of pages | 12 |
ISBN (Print) | 978-1-4503-3245-3 |
DOIs | |
Publication status | Published - 1 Apr 2015 |
Event | ASIA CCS 2015: The 10th ACM Symposium on Information, Computer and Communications Security - Singapore, Singapore Duration: 14 Apr 2015 → 17 Apr 2015 Conference number: 10th |
Conference
Conference | ASIA CCS 2015 |
---|---|
Country/Territory | Singapore |
City | Singapore |
Period | 14/04/15 → 17/04/15 |
Keywords
- Social overlay network
- Churn
- Sybil attack