Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> We investigate the problem of modeling node capture attacks in heterogeneous wireless ad hoc and mesh networks. Classical adversarial models such as the Dolev-Yao model are known to be unsuitable for describing node capture attacks. By defining the amortized initialization overhead cost as well as the cost of capturing a node, we show that finding the node capture attack yielding the minimum cost can be formulated as an integer-programming minimization problem. Hence, there is no polynomial solution to find the minimum cost node capture attack. We show that depending on the adversary's knowledge of the constraint matrix in the integer-programming problem, different greedy heuristics can be developed for node capture attacks. We also show under what conditions privacy-preserving key establishment protocols can help to prevent minimum cost node capture attacks. Individual node storage randomization is investigated as a technique to mitigate the effect of attacks which are not prevented by the use of privacy-preserving protocols. It is shown that probabilistic heuristic attacks can be performed effectively even under storage randomization. <s> BIB001 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> We formalize a model for node capture attacks in which an adversary collects information about the network via eavesdropping on the wireless medium and captures nodes based on the learned information. We show that attacks in this adversary model correspond to NP-hard optimization problems and discuss the behavior of a reasonable heuristic algorithm. We show that the goals of node capture attacks can be decomposed into a collection of primitive events, the impact of which can be evaluated and recombined to yield an overall evaluation of the attack. We demonstrate the use of the attack decomposition model for derivation of attack metrics and discuss the potential use of this decomposition technique for the purposes of defense against node capture attacks. <s> BIB002 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> Joint analysis of security and routing protocols in wireless networks reveals vulnerabilities of secure network traffic that remain undetected when security and routing protocols are analyzed independently. We formulate a class of continuous metrics to evaluate the vulnerability of network traffic as a function of security and routing protocols used in wireless networks. We develop two complementary vulnerability definitions using set theoretic and circuit theoretic interpretations of the security of network traffic, allowing a network analyst or an adversary to determine weaknesses in the secure network. We formalize node capture attacks using the vulnerability metric as a nonlinear integer programming minimization problem and propose the GNAVE algorithm, a Greedy Node capture Approximation using Vulnerability Evaluation. We discuss the availability of security parameters to the adversary and show that unknown parameters can be estimated using probabilistic analysis. We demonstrate vulnerability evaluation using the proposed metrics and node capture attacks using the GNAVE algorithm through detailed examples and simulation. <s> BIB003 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> Motivated by recently surfacing viruses that can spread over the air interfaces, in this article, we investigate the potentially disastrous threat of node compromise spreading in wireless sensor networks. We assume such a compromise originating from a single infected node, can propagate to other sensor nodes via communication and pre-established mutual trust. We focus on the possible epidemic breakout of such propagations where the whole network may fall victim to the attack. Using epidemic theory, we model and analyze this spreading process and identify key factors determining potential outbreaks. In particular, we perform our study on random graphs precisely constructed according to the parameters of the network, such as distance, key sharing constrained communication and node recovery, thereby reflecting the true characteristics therein. Moreover, a comparative study of the epidemic propagation is performed based on the effects of two types of sensor deployment strategies, viz., uniform random and group-based deployment. The analytical results provide deep insights in designing potential defense strategies against this threat. Furthermore, through extensive simulations, we validate the model and perform investigations on the system dynamics. Our analysis and simulation results indicate that the uniform random deployment is more vulnerable to an epidemic outbreak than the group based deployment strategy. <s> BIB004 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> In this paper we address the problem of physical node capture attacks in wireless sensor networks and provide a control theoretic framework to model physical node capture, cloned node detection and revocation of compromised nodes. By combining probabilistic analysis of logical key graphs and linear control theory, we derive a dynamical model that efficiently describes network behavior under attack. Using LQR and LQG optimal control theory tools, we develop a network response strategy, which guarantees secure network connectivity and stability under attack. Detailed simulations are presented to validate the methodology. <s> BIB005 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> Node capture attack is considered to be one of the most serious attack in WSN. An adversary physically captures a node so that she can steal all the confidential information stored in it and can launch further attacks by deploying clones of a captured node. To achieve this she needs to gather useful information regarding the network before capturing a node. Hence, a node capture by an adversary depends on how quickly she is able to gather the information regarding the network and about the target node. In this paper we have proposed a model for the process of gathering information by an adversary. We have also found the expected amount of information an adversary have at an arbitrary time t. Using the above information we proposed the expected time of a node capture based on the strength of an adversary and the dynamicity of the network. <s> BIB006 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> Wireless sensor networks are often deployed in hostile and unattended environment that are very prone to node capture attack. In node capture attack, information such as key, data on captured nodes, can all be extracted by the adversary. Node capture attack in wireless sensor networks suffers from low efficiency and high resource expenditure. To enhance the efficiency of node capture attack, we propose here a high efficiency node capture attack algorithm that is based on route minimum key set, namely greedy node captured based on route minimum key set (GNRMK). To obtain the route minimum key set, the sensor network is mapped as a flow network. The route minimum key set can be calculated by the maximum flow of the flow network. Then, an overlapping value is assigned to each node on the basis of route minimum key set. The node with maximum overlapping value will be captured in every round of attack. Simulation results indicate that, compared with other node capture attack schemes, GNRMK can compromise the network by capturing fewer nodes. Moreover, the fraction of traffic compromised is much higher. Copyright © 2012 John Wiley & Sons, Ltd. <s> BIB007 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> In the node capture attack, the adversary intelligently captures nodes and extracts the cryptographic keys from their memories to destroy the security, reliability and confidentiality of the wireless sensor networks. However, it suffers from low attacking efficiency and high resource expenditure. In this paper, we approach this attack from an adversarial view and develop a matrix-based method to model the process of the node capture attack. We establish a matrix to indicate the compromising relationship between the nodes and the paths. We propose a Matrix-based node capture attack Algorithm (MA in short), which can maximize the destructiveness while consuming the minimum resource expenditure. We conduct several experiments to show the performance of MA. Experimental results manifest that MA can reduce the attacking round, shorten the execution time, enhance the attacking efficiency and conserve the energy cost. <s> BIB008 </s> Optimized and Executive Survey of Physical Node Capture Attack in Wireless Sensor Network <s> III. SURVEY OF MODELING OF NODE CAPTURE ATTACK USING DIFFERENT SCHEMES <s> In the node compromise attack, the adversary physically captures nodes and extracts the cryptographic keys from the memories, which destroys the security, reliability and confidentiality of the networks. Due to the dynamical network topology, designing an efficient node compromise attack algorithm is challenging, because it is difficult to model the attack or to enhance the attacking efficiency. In this paper, a general algorithm for modeling the node compromise attack in VANET is proposed, which promotes the attacking efficiency by destroying the network backbone. The backbone is constructed using the connected dominating set of the network, which has relevant to the intermeeting time between the vehicles. Then two attacking algorithms are proposed based on the general model, which destroy the network in a centralized and distributed version while maximizing the destructiveness. Simulations are conducted to show the advantages of our scheme. Simulation results reveal that our scheme enhances the attacking efficiency in different mobility models and different applications, which is suitable for modeling the node compromise attack in VANET. At last, discussions are presented to the illustrate the influences of the characteristics to the attacking efficiency with respect to vehicle speed, communication range and key sharing probability. <s> BIB009
Tague et al. presented a mathematical model for node capture attacks on key establishment protocols in heterogeneous wireless ad hoc and mesh networks. This mathematical model relates the information brought by an attacker to the sets Sn assigned to nodes in N. By defining the amortized initialization overhead cost as well as the cost of capturing each node and the contribution of each node to the attack success, node capture attacks are formulated using an integer programming minimization problem. They identified problem that there is no polynomial solution that can determine the node capture attack with minimum cost for heterogeneous or homogeneous networks. An efficient heuristic algorithm for node capture attacks was thus presented using a known heuristic for the integer-programming minimization problem. They shown that, by the use of privacy-preserving key establishment protocol, the attack can be prevented using a subset coverage strategy. They also investigated storage randomization as a technique to mitigate set coverage attacks. They also shown, even in the presence of storage randomization, the adversary can perform a probabilistic heuristic via statistical analysis at an increased cost. They observed that the probabilistic heuristic outperforms the random capture of nodes BIB001 . Tague et al. BIB002 also formalized a model for node capture attack in which an attacker collects information about the network by eavesdropping on the wireless medium and captures nodes based on the learned information. Use of open, shared wireless medium allows any nearby device to overhear message transmission, interference with or block message reception, insert messages within the network. Even if the message payload is encrypted, the exchange of messages and the presence of message headers potentially allow an eavesdropper to learn about the network operation and the protocol state. In addition to passive learning, the attacker can actively participate in network protocols, probing the network for information and maliciously injecting the information into the network. Once sufficient amount of information is achieved by the adversary, he can physically capture nodes. The gathered information is used by the adversary in order to optimize the performance of the attack. The author showed that the goal of node capture attack can be decomposed into a collection of primitive events, the influence of which can be estimated and recollected to yield an overall of the attack. They considered the attack correspond to NP-hard optimization problems and discussed the behavior of a reasonable heuristic algorithm. They used the event based attack decomposition model for the development of suitable performance metrics for node capture attack. They also discussed the potential use of event based decomposition and evaluation metrics for the purpose of defend against node capture attack. Tague et al. also given that when security and routing protocols are analyzed independently, the vulnerabilities of secure network traffic remain undetected. In this work BIB003 , the authors took into consideration joint analysis of security and routing protocols in wireless networks to reveal vulnerabilities. The authors investigate a class of continuous metrics to evaluate the vulnerability of network traffic and isolate weakly secured connections. They devised two complementary vulnerability definitions by using set theoretic and circuit theoretic interpretations. These definitions of vulnerability allow an adversary to determine weakness or vulnerable point in the secure network. They also formulated the node capture attack as a nonlinear integer programming minimization problem. Due to the NP hardness of minimization problem, they presented the GNAVE algorithm, a Greedy Node Capture Approximation using Vulnerability Evaluation using a greedy heuristic to approximate the minimum cost attack. The use of greedy heuristics allows it to iteratively add nodes to the set of compromised nodes to maximize the increase in route vulnerability at each step. To increase the route vulnerability with minimum resource expenditure, it is Copyright © 2014 MECS I.J. Computer Network and Information Security, 2014, 11, 26-34 beneficial for an attacker to attempt to increase the vulnerability which results from the capture of each individual node through the information recovered from previously captured nodes. To enhance the cost effectiveness of the node capture attack at each step, an attacker chooses to compromise the node with maximum incremental value per unit cost. GNAVE can enhance attacking efficiency in terms of fewer compromised nodes and higher fraction of compromised traffic, but it did not include the execution time to compromise the network. De et al. proposed in BIB004 proposed the spreading process of node compromise in large-scale sensor networks. To study the results and effects of node capture attack, the author expressed the spread process to compromise the node by using epidemic theory. They started from a single most vulnerable point, and then assumed that the neighboring nodes can be compromised by an adversary via wireless communication and thus can threaten the complete network. As a result of security schemes used by the sensor networks, they assumed that communication can only be established when neighboring nodes can establish mutual trust by sharing a common key. Therefore, they shown that node compromise is not solely determined by the deployment of sensor nodes that successively affects node density, but also determined by the pair wise key scheme used in that. By taking these factors of the networks, they proposed an epidemiological model to identify the probability of a breakout (compromise of the whole network) and if not, the sizes of the components that are affected. Moreover, they analyzed the result of node recovery in an active infection state of the network and got vital values for these parameters that resulted in an outbreak. They targeted their analysis on two specific kinds of node deployment scenarios, namely uniform random deployment and group based deployment of nodes. Their results showed that a uniform random deployment was more insecure to epidemic propagation than a groupbased deployment model and leak key parameters of the network in defensive and containing potential epidemics. In the case of the node recovery, the result provided benchmark time period for the network to recover a node so as to defend against the epidemic spreading and also vital values of the key sharing probability which characterize the transition from a non epidemic to an outbreak state of the network compromise. However, the authors neglected to think about that an attacker can capture more than one node within the network to compromise the network. Therefore, modeling process of the node capture attack as a spread process is not suitable. Bonaci et al. proposed a control-theoretic framework to model physical node capture attacks in WSN by mapping the network security problem into a control theory problem. They also taken detection of cloned nodes and recovery of compromised node, followed by key distribution to valid nodes into consideration. By using probabilistic analysis of logical key graphs with linear control theory, they proposed a dynamical model that efficiently describes network behavior under attack. Using control theory methods, they showed that the network response under node capture attacks can be characterized using a proportional controller. They devised two network response strategies based on optimal control theory and showed the optimization problem can be formulated explicitly in terms of the network as well as logical key graph parameters. Using optimal control theory, they obtained the minimal revocation rate as a control parameter, which guarantees secure network connectivity and hence stability under the attack. The practical implications of these are: it enables (a) analysis of the network's stability and resilience against the physical node capture attack, (b) characterization of adversarial behavior and strategies and (c) computation of the optimal revocation rates, in terms of network parameters and cryptographic quantities, to maintain secure network connectivity in the presence of the attack. In this model, the authors provide consideration for the behavior of the attacker, while the effects of the node capture attack are not fully considered BIB005 . Mishra et al. proposed probabilistic model to capture a node in WSN by an adversary. An Adversary physically captures a node to steal all the secure information which is stored into the node's memory to lunch further attacks by deploying clones of a compromised node. To achieve this goal, an adversary needs to gather information for the network to capture a node. So they identified, to capture a node it is necessary for an adversary how quickly he/she is able to gather information regarding the network and for the target node. In this work, they modeled the information gathering process by an adversary to capture a node as a birth and death process. They shown that the time varies to gather information for different attackers based on their strength and configuration. So they also proposed the expected time of node capture based on the strength of an adversary and dynamicity of the network using a stochastic process. They also calculated expected amount of information that will be available to an adversary at an arbitrary time t BIB006 . In this paper BIB007 , a high efficiency node capture attack algorithm based on route minimum key set, namely GNRMK, is presented. In GNRMK, the wireless sensor network is mapped as a flow network and therefore the link key set cardinal is formalized as the capacity of the corresponding edge in flow network to get its route minimum key set that shows the vulnerability of the route in the network. The route minimum key set can be achieved by computing the max flow of the flow network using labeling and adjustment procedure on the basis of Ford-Fulkerson. In the label procedure, an augment path is found using breadth-first search. Then, they have the adjustment value, which can be found within the last searched node. In the adjustment procedure, if the edge is pointing toward the destination node, the flow value of each edge on the augment path is updated by adding the adjustment value in it otherwise subtracting the adjustment value if the edge is pointing toward the source node. The max flow is estimated through finding augment paths regularly. Then, a node overlapping value (NOV) metric is estimated through the route minimum key sets. A node with maximum overlapping value is targeted as the node to be compromised. Also, when a node is compromised, the topology of the network is dynamically modified because of the already compromised links or paths. So, the algorithm needs to traverse all the paths within the sensor network and delete the compromised paths because of the compromised key set estimated by captured node set. In this way, a new sensor network topology is acquired with the paths that are not compromised yet. Every time the network is restructured just after a node compromised and in this way, the complexity of the network is quickly reduced. Thus, the attack times out, and executing time may be reduced effectively. The effect of GNRMK algorithm is shown in different routing environments: the single path routing protocol, the multiple independent path routing protocol, and the multiple dependent path routing protocol. Furthermore, GNRMK is compared with previously related proposed schemes that show that GNRMK provides more efficiency in compromising the network. Chi Lin et al. approached the node capture attack from an attacker's point of view and developed a matrix approach to design the process of node capture attack. The authors proposed Matrix Algorithm (MA) which can produce the maximum destructiveness while taking the minimum resource expenditure (Energy cost). They established a matrix to show the compromising relationship among nodes and the paths BIB008 . To indicate the compromise relationship, first they analyzed the relationship between the paths and key by establishing path-key matrix PK = [pki, j] P×K that clears that whether obtaining a single key can directly lead to compromise of a path. Then they created another keynode matrix KN = [kni, j] K×N for showing the belonging relationship between the keys and the nodes. After that, they derived compromise relationship between nodes and paths by establishing the matrix PN = [pni, j] P×N as PN = PK ×KN. But it may be possible that a link is secured using more than one key. So considering only direct compromise relationship is not enough. To show partial compromise relationship they established another matrix PLN = [plni, j] P×N for representing the ratio of keys which are acquired by the adversary in path pi when node nj is captured. Then they combine the entries of PN and PLN into another matrix M = [mi, j] P×N to represent compromise relationship. The adversary looks for compromising a set of nodes that can compromise the entire network while taking the least energy. Thus, the author combines energy cost of capturing nodes into the matrix MC = [mci, j] P×N. After that, they devised the node capture attack algorithm to enhance the attacking efficiency. They performed the lots of experiments to check the performance of MA. Results show that MA reduced the attacking rounds, shorten the execution time, enhancing the attacking efficiency and conserve the energy cost. They modeled the MA algorithm that is limited to random key pre-distribution scheme. It also paid little attention to the relationship between the attacking efficiency and the attacking cost BIB008 . Design an efficient node capture attack algorithm is challenging for dynamic network topology. In this paper BIB009 , the author proposed a general algorithm to model node compromise attack in VANET. In their method, they defined the destructiveness value SK (i) to show the number of vehicles which are sharing keys with node i. These algorithms enhance the attacking efficiency by destroying the network backbone. The Connected Dominating Set of the network is used to construct the backbone. In VANET, nodes are moving over time so creation of fixed backbone is impossible task. To overcome this difficulty, they construct the virtual backbone. They construct Connected Dominating Set (CDS) as virtual backbone for balancing load and maintaining connectivity using dominating Set. The author proposed two attacking algorithm based on the general model to destroy the network in the centralized and distributed network while maximize the destructiveness. In Centralized attack based on Connected Dominating Set (CCDS), when adversary finds the target node to attack, he calculates the value of SK () for the neighbor nodes of all the captured nodes. Then he finds the node with the maximum value to mount an attack which will cause the maximum destructiveness within the network. In distributed attack based on Connected Dominating Set (DCDS), an adversary can select any node in CDS to attack. In the DCDS, an adversary needs to find the attacking node in each iteration. An adversary initially records the key sharing relationship and computes the value of SK (). Then he finds the vehicle with the maximum SK () and provides the index of the vehicle as the output. They compare DCDS and CCDS with two node compromise attack algorithms: random attack and epidemic attack. Simulation results show that their scheme improves the attacking efficiency in different mobility models and different applications. Regardless of specific key distribution scheme, in their work, the probability that two neighboring nodes share at least one key to establish a secure communication is represented by α. So, when they developed general model to formulize the node compromise attack, there was no need to consider what key pre-distribution protocol was implemented. They only focused on the influence of α to the attacking efficiency. Table 1 represents existing approaches for modeling of node capture attack in the wireless sensor network.