Local Connectivity Tests to Identify Wormholes in Wireless Networks

A wormhole attack places two radio transceivers connected by a high capacity link and retransmits wireless signals from one antenna at the other. This creates a set of shortcut paths in the network, and may attract a lot of traffic to the wormhole link. The link thus gains control of a large fraction of network traffic which opens the door for more dangerous attacks afterwards. In this paper we introduce a wormhole detection and removal algorithm based on local connectivity tests. The basic idea is that the neighborhood of a wormhole contains two sets of nodes corresponding to two sides of the wormhole. The distance between these two sets is small when using paths that pass through the wormhole link, but is large when only regular network paths are considered. Thus we remove a small neighborhood that will contain potential wormhole links and check if a slightly larger neighborhood falls apart to multiple connected components. To accommodate spatial and temporal unpredictability of wireless communication links we abstract the network connectivity as an arbitrary graph so that the method does not assume any idealistic models (such as unit disk graph model). The algorithm uses purely local connectivity information, handles multiple wormhole attacks and generalizes to wireless networks deployed in 3D. It does not suffer from typical limitations in previous work such as the requirements of special hardware, communication models, synchronization, node density etc. In simulations, our method is seen to beat the state of the art solutions, in particular for cases where previous solutions experience poor performance.