TY - GEN
T1 - SybilControl
T2 - 7th ACM Workshop on Scalable Trusted Computing, STC 2012
AU - Li, Frank
AU - Mittal, Prateek
AU - Caesar, Matthew
AU - Borisov, Nikita
PY - 2012
Y1 - 2012
N2 - Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present Sybil-Control, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that Sybil-Control can be practically deployed.
AB - Many distributed systems are subject to the Sybil attack, where an adversary subverts system operation by emulating the behavior of multiple distinct nodes. Most recent works addressing this problem leverage social networks to establish trust relationships between users. However, social networks are not appropriate in all systems. They can be subverted by social engineering techniques, require nodes to maintain and be aware of social network information, and may require overly optimistic assumptions about the fast-mixing nature of social links. This paper explores an alternate approach. We present Sybil-Control, a novel decentralized scheme for controlling the extent of Sybil attacks. It is an admission and retainment control scheme for nodes in a distributed system that requires them to periodically solve computational puzzles. SybilControl consists of a distributed protocol to allow nodes to collectively verify the computational work of other nodes, and mechanisms to prevent the malicious influence of misbehaving nodes that do not perform the computational work. We investigate the practical issues involved with deploying SybilControl into existing DHTs, particularly with handling churn. SybilControl is shown to provide strict bounds on the size of Sybil attacks, given adversaries with finite resources. We also show through simulations that the performance overhead of enabling SybilControl is manageable using commonplace DHT churn-handling techniques. This provides strong evidence that Sybil-Control can be practically deployed.
KW - Computational puzzles
KW - Distributed systems
KW - Sybil attack
UR - http://www.scopus.com/inward/record.url?scp=84869457691&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84869457691&partnerID=8YFLogxK
U2 - 10.1145/2382536.2382548
DO - 10.1145/2382536.2382548
M3 - Conference contribution
AN - SCOPUS:84869457691
SN - 9781450316620
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 67
EP - 78
BT - STC'12 - Proceedings of the Workshop on Scalable Trusted Computing
Y2 - 15 October 2012 through 15 October 2012
ER -