Wireless sensor networks (WSNs) pose unique security challenges due to the fact that their nodes operate in an unattended manner in potentially hostile environments. A particularly difficult problem not addressed to date is the handling of node capture by an adversary. A key goal for solving this problem is that of limiting the damage caused by captured nodes. This is important since node capture cannot be prevented: by definition, there is no practical physical mechanism that could keep an adversary from physically accessing a sensor node discovered in an unattended area. Hence, the presence of the adversary within a WSN must be detected, and of course, the earlier the better. Adversary detection is predicated on the fact that access to a captured node's internal state, which includes secrets such as cryptographic keys, incurs a nonzero time delay. This suggests that adversary detection be divided into two phases: (i) in-capture detection, namely detection before the adversary completes the capture process and gets a chance to access a node's internal state and do any network damage, and (ii) post-capture detection, namely detection after the adversary already accessed and possibly used a node's internal state and secrets. Since the adversary is already active in the network in the latter case, it is important to determine the overall network resiliency; i.e., the ability of the network to operate in the presence of an active adversary. In this work we focus on the former case in which we try to identify the presence of the adversary prior to completion of a node capture.

To address the problem of in-capture adversary detection, we propose two probabilistic schemes called the pairwise pinging scheme and quorum pinging scheme, whereby the network continuously monitors itself in a distributed and self-organizing manner. We investigate the trade-offs between the network cost-performance and security of these schemes via a Markov Chain model, and present analytical solutions which allow us to choose appropriate performance parameters, such as the expected residual time-to-false-alarm, and security, such as the probability of a missed detection. We show that the quorum pinging is superior to pairwise pinging in terms of both cost-performance and security. Furthermore, we will show that both schemes are scalable with network size and their complexities are linearly proportional to the average node degree of the network.

We also analyze the optimum strategy for an adversary to deploy its agents over a sensor network; i.e., the strategy that enables the adversary to achieve the maximum capture ratio with fixed number of agents. The order of node capture, distribution, and location of agents are investigated and an analytical model is provided that describes the optimum path for deploying of agents to target nodes. Numerical data are presented to compare different scenarios for deploying agents and the corresponding performance of each deployment strategy. The proposed optimum strategy validates the physical interpretation under practical scenarios and demonstrates the feasibility of our capture strategy in practice. Finally, the resiliency of the underlying quorum pinging scheme for detecting adversary agents is investigated despite collusion among agents via optimum capture strategy.