MODELING A SENSOR NETWORK DESIGN TO SECURE A NETWORK AGAINST ATTACK

• US 20080144835A1
• Filed: 12/13/2006
• Published: 06/19/2008
• Est. Priority Date: 12/13/2006
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Mukhopadhyay, Debaprivay, Roy, Suman S.R., PS, Chandrashekhara Thejaswi
• Granted Patent: US 7,804,962 B2
• Time in Patent Office: Days
• US Class Current: 380/278
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/1433 Vulnerability analysis
• CPC Class Codes: H04L 63/1466 Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks
• CPC Class Codes: H04L 63/1475 Passive attacks, e.g. eavesdropping or listening without modification of the traffic monitored
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/0471 Key exchange
• CPC Class Codes: H04W 12/122 Counter-measures against attacks; Protection against rogue devices
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A wireless sensor network may be designed by modeling the network as a function of at least one design parameter and/or at least one threat parameter ε, by assessing the model by varying the at least one design parameter to determine an effect on the at least one threat parameter ε, and by choosing a value for the at least one design parameter based on the assessment that produces an acceptably low value for the at least one threat parameter ε.

Claims

1. A method for designing a wireless sensor network comprising:

assessing a degree of security of the wireless sensor network against a security threat to the wireless sensor network; and

,

estimating network design parameters for the wireless sensor network as a function of the degree of security.

2. The method of claim 1 wherein the assessing of a degree of security further comprises assessing a tolerance to the security threat as a function of a degree of authenticity of the nodes in the wireless sensor network.

3. The method of claim 2 further comprising distributing the nodes in accordance with the design parameters.

4. The method of claim 2 further comprising:

pre-distributing keys amongst the nodes of the wireless sensor network;

estimating a key distribution shared between a pair of the nodes; and

,

verifying the shared key distribution mutually by the pair of nodes to establish the degree of authenticity.

5. The method of claim 4 further comprising distributing the nodes in accordance with the design parameters.

6. The method of claim 1 wherein the design parameters comprise at least one of N and d, wherein N is a number of nodes, and wherein d is based on a reach of each node in the network.

7. The method of claim 6 further comprising distributing the nodes in accordance with the design parameters.

8. The method of claim 6 wherein the assessing of a degree of security further comprises assessing a tolerance to the security threat, wherein the tolerance is denoted as ε

, wherein the design parameters are arbitrated according to the following function;

$f<br><br>\left(N,d,\mathrm{\varepsilon <br><br>}\right)<br><br>\mathrm{•<br><br>}<br><br>{\frac{p_{d_0}}{\left(1-p_{d_0}\right)}<br><br>\left[\frac{1}{2<br><br>\left(N-1\right)}<br><br>\left(1-p_{d_0}\right)<br><br>\left(1-p\right)<br><br>\left(1+{p^d<br><br>\left(2-p\right)}^d\right)\right]}^{\mathrm{\kappa <br><br>}}-\mathrm{\varepsilon <br><br>}=0$

wherein κ

is a polynomial in N, wherein M is a number of authentication tags used by the nodes during identity authentication, wherein P_do=1/M, wherein p is the probability that two of the nodes in the network do not share a common key and is given by the following equation;

$\hspace{1em}<br><br>\begin{array}{c}p=<br><br>\frac{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}\times <br><br>\frac{\left(\begin{array}{c}s-s^{\mathrm{\prime <br><br>}}\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}=\frac{{\left(\left(s-s^{\mathrm{\prime <br><br>}}\right)!\right)}^2}{\left(s-2<br><br>s^{\mathrm{\prime <br><br>}}\right)!<br><br>s!}\\ =<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-1}\right)<br><br><br><br>\mathrm{\cdots <br><br>}<br><br><br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-s^{\mathrm{\prime <br><br>}}+1}\right)\end{array}$

wherein s is a number of keys in a pool from which keys to be assigned to each of the nodes are chosen, and wherein s′

is a number of keys assigned to each of the nodes.

9. The method of claim 8 further comprising distributing the nodes in accordance with the design parameters.

10. The method of claim 1 further comprising distributing the nodes in accordance with the design parameters.

11. The method of claim 1 wherein the design parameters comprise at least one of N_c/N and t, wherein N_c/N is a fraction of compromised nodes N_c to a total number of nodes N in the network, and wherein t is a maximum number of nodes that can be compromised without an attacker discovering keys used by the nodes.

12. The method of claim 11 wherein the assessing of a degree of security further comprises assessing a tolerance to the security threat, wherein the tolerance is denoted as ε

, and wherein the design parameters are arbitrated according to the following function;

f(N_c/N,t,ε

)P_secure^κ

P_insecure−

ε

=0

wherein P_secure is given by the following equation;

$P_{\mathrm{secure}}=\left(1-P_{\mathrm{cd}}\right)<br><br>\left(1-{\mathrm{Pd}}_q\right)<br><br>\left[p+\left(1-p\right)<br><br>\left(1-\frac{N_c}{N}\right)<br><br>\left(1-P_{\mathrm{cd}}\right)\right]$

wherein P_insecure is given by the following equation;

P_insecure=1−

P_secure.

wherein P_cd is given by the following equation;

$P_{\mathrm{cd}}=1-\underset{i-0}{\overset{t}{\sum <br><br>}}<br><br>P<br><br>\left[i<br><br><br><br>\mathrm{comprised}<br><br><br><br>\mathrm{shares}\right].$

wherein P[i comprises shares] is given by the following equation;

$P<br><br>\left[i<br><br><br><br>\mathrm{compromised}<br><br><br><br>\mathrm{shares}\right]=\frac{N_c!}{\left(N_c-i\right)!<br><br>i!}<br><br>{\left(\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)}^i<br><br>{\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)}^{\left(N_c-i\right)}$

wherein κ

is a polynomial in N, wherein N_C/N is the at least one design parameter, wherein pd_q is a maximum value of ε

such that the adversary is an (ε

,q) forger, wherein p is the probability that two of the nodes in the network do not share a common key and is given by the following equation;

$\hspace{1em}<br><br>\begin{array}{c}p=<br><br>\frac{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}\times <br><br>\frac{\left(\begin{array}{c}s-s^{\mathrm{\prime <br><br>}}\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}=\frac{{\left(\left(s-s^{\mathrm{\prime <br><br>}}\right)!\right)}^2}{\left(s-2<br><br>s^{\mathrm{\prime <br><br>}}\right)!<br><br>s!}\\ =<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-1}\right)<br><br><br><br>\mathrm{\cdots <br><br>}<br><br><br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-s^{\mathrm{\prime <br><br>}}+1}\right)\end{array}$

wherein s is a number of keys in a pool from which keys to be assigned to each of the nodes are chosen, and wherein s′

is a number of keys assigned to each of the nodes.

13. The method of claim 12 further comprising distributing the nodes in accordance with the design parameters.

14. A method for designing a wireless sensor network comprising:

modeling the network as a function of at least one design parameter and at least one threat parameter ε

;

assessing the model by varying at least one design parameter to determine an effect on the threat parameter ε

; and

,

choosing a value for the design parameter based on the assessment that produces an acceptably low value for the threat parameter ε

.

15. The method of claim 14 wherein the modeling of the network comprises modeling the network based on a probabilistic key sharing automaton.

16. The method of claim 15 further comprising distributing the nodes in accordance with the at least one design parameter.

17. The method of claim 15 wherein the modeling of the network based on a probabilistic key sharing automaton comprises modeling the network based on the following function:

$f<br><br>\left(N,d,\mathrm{\varepsilon <br><br>}\right)<br><br>\mathrm{•<br><br>}<br><br>{\frac{p_{d_0}}{\left(1-p_{d_0}\right)}<br><br>\left[\frac{1}{2<br><br>\left(N-1\right)}<br><br>\left(1-p_{d_0}\right)<br><br>\left(1-p\right)<br><br>\left(1+{p^d<br><br>\left(2-p\right)}^d\right)\right]}^{\mathrm{\kappa <br><br>}}-\mathrm{\varepsilon <br><br>}=0$

wherein N is the at least design parameter and is the total number of nodes in the network, wherein κ

is a polynomial in N, wherein M is a number of authentication tags used by the nodes during identity authentication, wherein pd₀=1/M, wherein p is the probability that two of the nodes in the network do not share a common key and is given by the following equation;

$\hspace{1em}<br><br>\begin{array}{c}p=<br><br>\frac{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}\times <br><br>\frac{\left(\begin{array}{c}s-s^{\mathrm{\prime <br><br>}}\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}=\frac{{\left(\left(s-s^{\mathrm{\prime <br><br>}}\right)!\right)}^2}{\left(s-2<br><br>s^{\mathrm{\prime <br><br>}}\right)!<br><br>s!}\\ =<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-1}\right)<br><br><br><br>\mathrm{\cdots <br><br>}<br><br><br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-s^{\mathrm{\prime <br><br>}}+1}\right)\end{array}$

wherein s is a number of keys in a pool from which keys to be assigned to each of the nodes are chosen, wherein s′

is a number of keys assigned to each of the nodes, and wherein d is another design parameter and is dependent on a number of nodes within a transmission range of any given node in the network.

18. The method of claim 17 further comprising distributing the nodes in accordance with the design parameters.

19. The method of claim 14 wherein the modeling of the network comprises modeling the network based on a polynomial pool based key pre-distribution probabilistic automaton.

20. The method of claim 19 further comprising distributing the nodes in accordance with the at least one design parameter.

21. The method of claim 19 wherein the modeling of the network based on a polynomial pool based to key pre-distribution probabilistic automaton comprises modeling the network based on the following function:

f(N_c/N,t,ε

)P_secure^κ

P_insecure−

ε

=0

wherein P_secure is given by the following equation;

$P_{\mathrm{secure}}=\left(1-P_{\mathrm{cd}}\right)<br><br>\left(1-{\mathrm{Pd}}_q\right)<br><br>\left[p+\left(1-p\right)<br><br>\left(1-\frac{N_c}{N}\right)<br><br>\left(1-P_{\mathrm{cd}}\right)\right]$

wherein P_insecure is given by the following equation;

P_insecure=1−

P_secure.

wherein P_cd is given by the following equation;

$P_{\mathrm{cd}}=1-\underset{i-0}{\overset{t}{\sum <br><br>}}<br><br>P<br><br>\left[i<br><br><br><br>\mathrm{comprised}<br><br><br><br>\mathrm{shares}\right].$

wherein P[i comprises shares] is given by the following equation;

$P<br><br>\left[i<br><br><br><br>\mathrm{compromised}<br><br><br><br>\mathrm{shares}\right]=\frac{N_c!}{\left(N_c-i\right)!<br><br>i!}<br><br>{\left(\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)}^i<br><br>{\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)}^{\left(N_c-i\right)}$

wherein N is the total number of nodes in the network, wherein κ

is a polynomial in N, wherein N_C is an assumed number of sensor nodes that are compromised by an adversary, wherein N_C/N is the at least one design parameter, wherein t is another design parameter and is a number of nodes that an adversary must compromise in order to determine non-compromised keys, wherein pd_q is a maximum value of ε

such that the adversary is an (ε

,q) forger, wherein p is the probability that two of the nodes in the network do not share a common key and is given by the following equation;

$\hspace{1em}<br><br>\begin{array}{c}p=<br><br>\frac{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}\times <br><br>\frac{\left(\begin{array}{c}s-s^{\mathrm{\prime <br><br>}}\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}{\left(\begin{array}{c}s\\ s^{\mathrm{\prime <br><br>}}\end{array}\right)}=\frac{{\left(\left(s-s^{\mathrm{\prime <br><br>}}\right)!\right)}^2}{\left(s-2<br><br>s^{\mathrm{\prime <br><br>}}\right)!<br><br>s!}\\ =<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s}\right)<br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-1}\right)<br><br><br><br>\mathrm{\cdots <br><br>}<br><br><br><br>\left(1-\frac{s^{\mathrm{\prime <br><br>}}}{s-s^{\mathrm{\prime <br><br>}}+1}\right)\end{array}$

wherein s is a number of keys in a pool from which keys to be assigned to each of the nodes are chosen, and wherein s′

is a number of keys assigned to each of the nodes.

22. The method of claim 21 further comprising distributing the nodes in accordance with the design parameters.

23. The method of claim 14 further comprising distributing the nodes in accordance with the at least one design parameter and the at least one threat parameter.