Analytical Study of Adversarial Strategies in Cluster-based Overlays

Emmanuelle Anceaume (1) , Romaric Ludinard (1) , Frédéric Tronel (2) , F. Brasiliero (3) , Bruno Sericola (4)

1 ADEPT - Algorithms for Dynamic Dependable Systems
2 SUPELEC-Campus Rennes
3 LSD - Laboratório de Sistemas Distribuídos
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS

Scheideler has shown that peer-to-peer overlays networks can only survive Byzantine attacks if malicious nodes are not able to predict what is going to be the topology of the network for a given sequence of join and leave operations. In this paper we investigate adversarial strategies by following specific games. Our analysis demonstrates first that an adversary can very quickly subvert DHT-based overlays by simply never triggering leave operations. We then show that when all nodes (honest and malicious ones) are imposed on a limited lifetime, the system eventually reaches a stationary regime where the ratio of polluted clusters is bounded, independently from the initial amount of corruption in the system.

Mots clés: Byzantine attack

Domaines: Informatique et théorie des jeux [cs.GT]

Emmanuelle Anceaume, Romaric Ludinard, Frédéric Tronel, F. Brasiliero, Bruno Sericola. Analytical Study of Adversarial Strategies in Cluster-based Overlays. 2nd International Workshop on Reliability, Availability, and Security, 2009, Hiroshima, Japan. pp.12, ⟨10.1109/PDCAT.2009.62⟩. ⟨hal-00408871⟩