Virtual coordinate systems provide an accurate and efficient service that allows hosts on the Internet to determine the latency between arbitrary hosts without using active monitoring of all nodes in the network. Many of the proposed virtual coordinate systems were designed with the assumption that all of the nodes in the system are cooperative. However, this assumption may be violated by compromised nodes acting maliciously to degrade the accuracy of the virtual coordinate systems.

In this work, we demonstrate the vulnerability of decentralized virtual coordinate systems to insider (or Byzantine) attacks. We propose techniques to decrease the number of incorrect coordinate changes, thereby making coordinate assignment and maintenance robust to malicious attackers. We demonstrate the attacks and mitigation techniques in the context of a well-known distributed virtual coordinate system using simulations based on a representative, real-world data set of Internet latencies.