A graph theoretic framework for preventing the wormhole attack in wireless ad hoc networks

Radha Poovendran, Loukas Lazos

Research output: Contribution to journalArticlepeer-review

159 Scopus citations


Wireless ad hoc networks are envisioned to be randomly deployed in versatile and potentially hostile environments. Hence, providing secure and uninterrupted communication between the un-tethered network nodes becomes a critical problem. In this paper, we investigate the wormhole attack in wireless ad hoc networks, an attack that can disrupt vital network functions such as routing. In the wormhole attack, the adversary establishes a low-latency unidirectional or bi-directional link, such as a wired or long-range wireless link, between two points in the network that are not within communication range of each other. The attacker then records one or more messages at one end of the link, tunnels them via the link to the other end, and replays them into the network in a timely manner. The wormhole attack is easily implemented and particularly challenging to detect, since it does not require breach of the authenticity and confidentiality of communication, or the compromise of any host. We present a graph theoretic framework for modeling wormhole links and derive the necessary and sufficient conditions for detecting and defending against wormhole attacks. Based on our framework, we show that any candidate solution preventing wormholes should construct a communication graph that is a subgraph of the geometric graph defined by the radio range of the network nodes. Making use of our framework, we propose a cryptographic mechanism based on local broadcast keys in order to prevent wormholes. Our solution does not need time synchronization or time measurement, requires only a small fraction of the nodes to know their location, and is decentralized. Hence, it is suitable for networks with the most stringent constraints such as sensor networks. Finally, we believe our work is the first to provide an analytical evaluation in terms of probabilities of the extent to which a method prevents wormholes.

Original languageEnglish (US)
Pages (from-to)27-59
Number of pages33
JournalWireless Networks
Issue number1
StatePublished - Jan 2007


  • Geometric random graphs
  • Security
  • Wireless ad hoc networks
  • Wormhole attack

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'A graph theoretic framework for preventing the wormhole attack in wireless ad hoc networks'. Together they form a unique fingerprint.

Cite this