Department of Electrical and Computer Engineering University of Arizona 
Loukas Lazos
Home Students Research Publications Teaching Prof. Activities Vitae    

Ad Hoc Networks

Misbehavior detection
Mitigation of control-channel jamming attacks
Modeling network vulnerabilities
Resource-efficient key management for group communications

Cognitive Radio Networks

Spectrum-opportunity based control channel assignment

Wireless Sensor Networks

Secure localization
Stochastic coverage in sensor networks
Probabilistic detection of mobile targets

Misbehavior Detection in Wireless Ad Hoc Networks

Figure 1
Figure 1. Node n5 is misbehaving by dropping packets

Ad hoc networks rely on nodes working in a collaborative manner to forward packets. However, compromised or misbehaving nodes may refuse to forward the packets of other nodes to conserve energy (selfishness) or degrade network performance (maliciousness). Our research focuses on identifying these misbehaving nodes in an ad hoc network.

As an example, consider Figure 1. The source S is sending packets to the destination D via a multi-hop path. Each node in the path is responsible for forwarding the packets to D. Node 5 misbehaves by dropping all packets. We have proposed REAct (Resource-Efficient ACcounTability), a reactive misbehavior identification scheme, to identify such misbehavior. REAct requires nodes to commit to behavioral proofs of the packets they forward via an auditing mechanism. The audits represent a commitment to the packets the node claims to have forwarded. We employ Bloom filters for the construction of audits which allow for space-efficient representation of the set of packet forwarded. Audits are combined by the source to identify misbehaving nodes, while also preventing false accusations.

We are currently working on extending REAct to be collusion-resistant. We investigate the mapping of the misbehavior identification problem to Reyni-Ulam games.pdf

The Java-based misbehavior decection simulator can be found here

Back to top

Mitigation of Control-channel Jamming Attacks

Multi-channel wireless networks utilize several orthogonal frequency bands to eliminate interference between parallel transmissions and hence, improve the network capacity. Due to their increased performance compared to single-channel networks, they are being integrated into various network architectures, such as mobile ad hoc, vehicular, sensor, wireless local area, mesh, and cognitive radio networks.

The increased capacity of multi-channel networks can be translated into actual throughput only if critical network functions such as channel allocation and routing are efficiently coordinated. These functions are collaboratively coordinated by exchanging messages on a broadcast channel known as the control channel. From a security point of view, convergence on a pre-assigned control channel constitutes a single point of failure. An adversary can severely degrade the network performance by launching a Denial of Service (DoS) attack on the control channel, thus negating any gain due to the availability of multiple data channels. A sophisticated adversary can intelligently utilize jamming to attack higher-layer functionalities and deny network availability at a very small energy cost.

We consider the problem of control-channel jamming in multi-channel wireless ad hoc networks. We assume a sophisticated adversary who exploits knowledge of protocol mechanics along with cryptographic quantities extracted from compromised nodes to maximize the impact of his attack in higher layers.

Figure 2     Figure 3
Figure 2. A single frequency band design. Figure 3. A clustered approach.

To mitigate the impact of jamming, we adopt a dynamic control-channel allocation strategy. The network is organized into clusters, whereby each cluster establishes and maintains its own control channel. In Figure 2, we show the implementation of the control channel using a single frequency. All nodes within the range of the jammer are denied access to the control channel. In Figure 2, a single frequency band is allocated for the control channel. The adversary blocks all control messages within Rmax by jamming the control channel located. In Figure 3, a long range jamming transmission on a single frequency band can affect the control channel only to those clusters using that particular band.

Suppose that the current control channel is jammed in a particular cluster. The main idea behind our scheme is to have each node of the cluster hop between channels in a pseudo-noise (PN) fashion, following a unique hopping sequence not known to other nodes. This way if the jammer captures the hopping sequence of a compromised node, this node can be uniquely identified. Once the compromised node has been identified, the node can be removed from the network and the PN sequence within the cluster is updated.

Figure 4
Figure 4: Generation of unique hopping seuqences

By design, the hopping sequences assigned to various nodes overlap only in a pre-defined number of slots, thus implementing the broadcast control channel in the cluster. In order to protect the secrecy of the control channel, the hopping sequences must satisfy the following properties: (a) knowledge of previous hops does not reveal any information about future ones, (b) knowledge of one sequence does not reveal any information regarding another, (c) when interpreted as codewords, the sequences should have a high Hamming distance so that a compromised node can be uniquely identified. In Figure 4, we show the generation of hopping sequences for three nodes.pdf

Back to top

Modeling Network Vulnerabilities

Ad hoc networks are susceptible to a series of attacks due to the absence of a global view of the network. One severe type of attack is the wormhole attack in which an adversary establishes a low-latency link between two points in the network. The adversary eavesdrops on messages at one end of the link, referred to as the origin point, tunnels them through the wormhole ink, and replays them at the other end of the link, referred to as the destination point.

In a wormhole attack, the devices and wormhole links deployed by the adversary do not become part of the network. Hence, they do not need to hold any valid network Ids and cryptographic quantities to perform the attack. The lack of key compromise makes the wormhole attack invisible to the upper layers of the network

Figure 5     Figure 6
Figure 5. A wormhole attck against a distance-vector routing protocol. Figure 6. A wormhole attack against an on-demand routing protocol

As an example, the impact of a wormhole attack on routing protocols is illustrated in Figures 5,6. In Figure 5, then adversary establishes a wormhole link between nodes s9 and s2, using a low-latency link. When node s9 broadcasts its routing table as in distance vector routing protocols, node s2 hears the broadcast via the wormhole and assumes is one hop away from s2. Similarly, the neighbors of s2 adjust their own routing tables and route via s2 to reach any of the nodes s9, s10 s11, and s12. In Figure 6, we consider an on-demand routing protocol. Node s9 wants to send data to node s2. The adversary forwards the route request broadcasted from node s9 via the wormhole link to node s2 which replies with a route reply via the wormhole link. Nodes s2 and s9 establish a route via the wormhole link, as if they were one hop neighbors.

We provided a graph theoretic characterization of the wormhole attack and stated the necessary and sufficient conditions for any candidate solution to prevent the wormhole attack. We also proposed a new method for preventing wormholes that does not rely on tight synchronization among the networks nodes. pdf

Back to top

Resource-efficient Key Distribution for Group Communications

Wireless nodes equipped with omnidirectional antennae can deliver an identical message to any receiver within their communication range by a single transmission. Protocols employing Group communications can benefit from the broadcast nature of the wireless medium, and reduce the energy required for communication. Access control policies are necessary in order to restrict access to the contents of broadcast transmissions to valid members of a Multicast Group. A bandwidth and computationally efficient solution to this problem uses a single symmetric cryptographic key, called the Session Encryption Key (SEK), that is shared by the multicast source and all members of MG. Using the SEK, the sender needs to perform only one encryption and one transmission to send data to MG, while MG members need only perform a single decryption to receive the data.

In the case where the multicast group MG is dynamic, the valid members of MG need to be updated with a new SEK after every membership change so that new members do not access past data (backward secrecy), and departing members do not access future transmissions (forward secrecy). In order to update the SEK, additional keys called Key Encryption Keys (KEKs) are used by the entity managing the cryptographic keys, known as the Group Controller (GC). Hence, the problem of controlling access to the multicast data reduces to the problem of managing and distributing the SEK and KEKs to the members of MG. This problem is known as the key management problem or key distribution problem (KDP).

Figure 7     Figure 8
Figure 7. Grouping of 8 nodes according to the network topology     Figure 8. Corresponding key distribution tree.

We examined the KDP under the metrics of: (a) member key storage, (b) GC transmissions, (c) number of messages sent by the network to update the SEK and related KEKs, and (d) the energy expended by the network for delivering the update messages to valid members after a member deletion. We showed the computational difficulty of each problem and propose a heuristic called VP3, that uses broadcast route and energy expenditure information, to build an energy and bandwidth efficient key assignment structure. The main idea behind our heuristic is to place members sharing similar routing paths to the GC, adjacent in the key assignment tree. Hence, key updates will reach MG members with fewer transmissions and less energy. In Figure 7, we show a MG of 9 nodes and the corresponding network topology. Nodes are grouped according to the routes toward the GC. The corresponding key assignment is depicted in Figure 8.pdf

Back to top

Spectrum-opportunity based control channel assignment

Cognitive radio networks (CRNs) collaboratively implement critical network functions, such as cooperative sensing and channel assignment. These functions require a broadcast control channel for local coordination. For example, nodes may use a predefined control channel to negotiate the data channel assignment and to reserve the medium for future transmissions. However, in a CRN, a channel common to all CRs may not exist due the temporal and spatial variations of the spectrum availability. CRs sense different sets of idle channels depending on their relative locations to PRs and hence, may not be able to communicate over a predefined and globally common channel.

To cope with the time- and space-varying nature of channel availability in CRNs, we considered a cluster-based assignment of the control channel. To locally assign the control channel in the absence of a current one, we developed a neighbor discovery and coordination mechanism suitable for CRNs.

Figure 9
Figure 9. Universal schedule using a time-slotted system

In Figure 9, we show our neighbor discovery protocol. Each CR user determines the list of idle channels (represented by different colors). Each channel corresponds to a different time slot, in a time-slotted system. CR users broadcast their list of idle channels only on the time slots corresponding to idle channels. CR users sensing the same channel as idle will be able to communicate on the corresponding time slot.

To provide a clustering based on spectrum opportunities, we formulated the clustering problem as a maximum edge biclique graph problem and showed a graceful tradeoff between the cluster size and the set of common idle channels within each cluster. We developed a distributed clustering algorithm called Spectrum Opportunity-based Clustering (SOC), which groups neighboring CRs with similar channel availability in the same cluster.

Figure 10 Figure 11 Figure 12
  Figure 10.CRN of 8 CR users organized into clusters Figure 11. The bipartite graph for CR user A. Figure 12. The maximum edge biclique graph for CR user A.

In SOC, each CR node builds a bipartite graph with the neighboring nodes as the one vertex set and the set of idle channels as the opposite vertex set. An edge between two vertices i, j exists if CR node i senses channel j as idle. Figure 11 shows the bipartite graph of CR node A built from the CRN topology of Figure 10. CR nodes compute the complete subgraph of the bipartite graph (biclique) with the maximum number of edges. Such a design provides a balance between the cluster size and the number of channels within a cluster. By exchanging their biclique information, the CRs independently agree on cluster memberships. Hence, the control channel can be migrated in case primary radio (PR) activity appears on the current one. Availability of multiple channels within each cluster limits frequent re-clustering due to PR activity. We also proposed mechanisms for: (a) dynamic migration of the control channel within each cluster based on PR activity, and (b) inter-cluster coordination.

Back to top




Home Students Research Publications Teaching Prof. Activities Vitae    
             
          Valid CSS! Valid HTML 4.01 Transitional