Sensor networks allow to deploy large self-organized and adaptable sets of sensors for many applications such as monitoring, detection, tracking etc. Unfortunately, the simplicity and low-cost of the sensors eases replication of nodes by attackers. Node replication attacks are the entry point to a large span of insidious attacks. Using replicas it is possible to capture, alter or suppress traffic and to disrupt protocols through misbehavior. In 2005 Parno et al. proposed a passive protocol [1] for distributed detection of node replication attacks in sensor networks based on location claims. For an n node network, the detection protocol results in O(root n) message transmissions per node where the trivial approach would result in O(n) messages per node. It is the ?rst non-centralized protocol providing the emerging property of node replication detection and provides a performance leap from a communication point of view when compared to the trivial approach. On the other hand, each node needs to store O(root n) signed location claims which is an important limiting factor as sensor memory is quickly saturated. In this paper we propose a new distributed protocol in which each node veri?es at random a few other nodes in the network. Our protocol results in the same communication complexity than the protocol of Parno et al. but no storage is done on the nodes.

Active Detection, Node Replication Attacks