On Resilience and Connectivity of Secure Wireless Sensor Networks Under Node Capture Attacks

Jun Zhao

TL;DR

This paper provides a rigorous analysis of the resilience and connectivity of secure wireless sensor networks (WSNs) using the q-composite key predistribution scheme, particularly under node capture attacks. It addresses limitations in prior work by offering precise analytical models and deriving optimal parameters for network security and connectivity, even considering real-world transmission constraints.

What Problem Does This Paper Address?

Wireless sensor networks (WSNs) are increasingly deployed in environments where physical security is a concern, making them vulnerable to node capture attacks. When a node is captured, an adversary gains access to all its secret keys, potentially compromising communications. While various key predistribution schemes exist, many lack formal analyses of their resilience to such attacks, especially under realistic conditions. Existing research often suffers from incorrect probability calculations for link compromise and overlooks practical limitations like sensor transmission range. This paper aims to fill this gap by providing a precise, analytical framework to understand and optimize the resilience and connectivity of the q-composite key predistribution scheme against node capture and replication attacks, while also considering network connectivity under realistic transmission constraints.

Methods

The authors employ a combination of theoretical analysis and mathematical modeling. They derive analytical expressions for the probability of link compromise under node capture attacks, building upon and correcting previous work. A key contribution is the development of a tractable asymptotic analysis for these probabilities, which allows for the identification of optimal scheme parameters (like the key pool size $P_n$, key ring size $K_n$, and the q-composite parameter $q$) to achieve desired levels of resilience against different adversary capabilities.

Furthermore, the paper models the network topology as an intersection of a random intersection graph (representing key sharing) and a random geometric graph (representing communication range under the disk model). This allows for the analysis of network connectivity under realistic transmission constraints, both in the absence and presence of node capture. They also analyze node replication attacks by modeling the adversary's strategy to maximize replication success under resource constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation-based experiments to validate its findings, rather than using pre-existing datasets.

Key Insights and Ideas

  • Correcting Prior Work: The paper identifies and corrects an incorrect computation of link compromise probability that was prevalent in earlier studies on the q-composite scheme.
  • Optimal Parameter Tuning: It provides a method to derive optimal parameters ($K_n$, $P_n$, $q$) for the q-composite scheme to maximize resilience against node capture for a given adversary strength.
  • Connectivity Under Constraints: The analysis of network connectivity explicitly incorporates realistic transmission range limitations (disk model), which is often overlooked.
  • Sharp Connectivity Thresholds: The paper establishes sharp "zero-one laws" for network connectivity, meaning that a small change in a critical parameter can drastically shift the network from connected to disconnected.
  • Node Replication Strategy: It offers insights into the optimal strategy for an adversary performing node replication attacks, suggesting a trade-off between the number of replicas and the keys stored on each replica.

Key Results

  • Resilience Analysis: The paper provides a tractable asymptotic expression for the probability of link compromise ($P_{compromised}$) under node capture. It shows that $P_{compromised}$ is minimized when $q$ is chosen optimally as $q^* = \max(\lfloor K_n \rfloor, 1)$ (with a slight variation if $K_n$ is an integer).
  • Connectivity Results: For connectivity in the absence of node capture, a critical threshold for the edge probability is derived as $\frac{\ln n}{n}$. In the presence of $m$ captured nodes, the threshold becomes $\frac{\ln(n-m)}{n-m}$.
  • Node Replication: The analysis suggests that for a resource-constrained adversary, it's often optimal to deploy fewer, higher-cost replicas (more keys per replica) rather than many low-cost ones, especially when the adversary's cost function parameters favor this strategy.
  • Experimental Validation: The theoretical findings are supported by extensive experimental results presented in figures, demonstrating the accuracy of the derived formulas and the behavior of the system under various parameter settings.

Limitations and Future Work

  • Assumptions: The analysis relies on certain assumptions, such as the adversary capturing nodes randomly and the use of the disk model for communication. Real-world scenarios might involve more sophisticated adversary strategies or different communication models.
  • Complexity of Optimal q: While Corollary 3 provides a method to find the optimal $q$ for maximizing node capture, the derivation is noted as difficult and often requires empirical methods (like Table I and Figure 1).
  • Future Work: The paper implicitly suggests future work in exploring more complex adversary models, different network topologies, and potentially more efficient key management schemes that offer enhanced resilience and connectivity. The authors also mention that their full results, including detailed proofs and additional analysis, are available in a separate technical report.

Summary updated

Abstract

Despite much research on probabilistic key predistribution schemes for wireless sensor networks over the past decade, few formal analyses exist that define schemes' resilience to node-capture attacks precisely and under realistic conditions. In this paper, we analyze the resilience of the q-composite key predistribution scheme, which mitigates the node capture vulnerability of the Eschenauer-Gligor scheme in the neighbor discovery phase. We derive scheme parameters to have a desired level of resiliency, and obtain optimal parameters that defend against different adversaries as much as possible. We also show that this scheme can be easily enhanced to achieve the same “perfect resilience" property as in the random pairwise key predistribution for attacks launched after neighbor discovery. Despite considerable attention to this scheme, much prior work explicitly or implicitly uses an incorrect computation for the probability of link compromise under node-capture attacks and ignores the real-world transmission constraints of sensor nodes. Moreover, we derive the critical network parameters to ensure connectivity in both the absence and presence of node-capture attacks. We also investigate node replication attacks by analyzing the adversary's optimal strategy.
BibTeX
@article{zhao2017resilience,
  author = {Jun Zhao},
  title = {{On Resilience and Connectivity of Secure Wireless Sensor Networks Under Node Capture Attacks}},
  journal = {IEEE Trans. Inf. Forensics Secur.},
  year = {2017},
  url = {https://openreview.net/forum?id=SkQmCsnbeO},
}
Figure