Overview
Summary
Ad hoc wireless networks are vulnerable to a wide range of security attacks. An adversary can physically capture ad hoc nodes and tamper with them. This is because ad hoc nodes are often deployed in insecure locations, as the case for mesh routers deployed on rooftops or attached to streetlights, and for nodes deployed in a hostile environment (e.g., a battlefield). Further, the nodes often lack strong hardware protection. Once nodes are compromised, the adversary can launch a variety of attacks exploiting the cooperative nature of these networks. For example, the adversary can disrupt the network services by letting compromised nodes deny the network protocol such as the back-off rule at the MAC layer or the packet-relaying duty at the Network layer. Also, the compromised nodes can inject malicious traffic into the network (e.g., worm traffic into a sensor network).
An approach widely used to detect this class of attacks is behavior-based detection. In this, nodes overhear communications in their neighborhood exploiting the open nature of wireless medium, and determine if the behaviors of their neighbors are legitimate. For instance, to detect the MAC-layer misbehavior, a node can verify if the back-off times of its neighbors follow a legitimate pattern. Also, to detect malicious traffic, a node can analyze the overheard packets to check if they contain any malicious data. Upon detection, a remediation action can be taken, such as an isolation of the misbehavior node by neighboring nodes.
We are interested in ad hoc multi-channel wireless networks, where an ad hoc node can tune its radio to one from a given set of wireless channels. We first consider stationary networks, where ad hoc nodes do not move and their channel assignment is fixed. The problem that we address in this work is how to strategically deploy a given number of monitoring nodes in the network, and also which channels to tune their radios to. Here, we assume that a finite set of possible places (e.g., grid points) where the monitoring nodes will be deployed is given. Our goal is to maximize the number of nodes (or more generally, the amount of traffic) to be monitored by judiciously placing the monitoring nodes and assigning channels to them. We mathematically formulate this problem, and show that the problem is NP-hard. We then find approximate solution to the problem. Our algorithm development takes the following path: we first formulate the problem as an integer linear program; we then relax the integer constraints and solve the resulting linear program (LP) relaxation, which takes polynomial time; Lastly, we adopt LP rounding techniques to obtain feasible solution to our problem, which satisfies the integer constraints.
Next, we develop distributed online solutions for large-scale and dynamic networks. In such networks, the network has frequent configuration changes, such as channel-usage changes of ad hoc nodes and network topology changes due to mobility of ad hoc nodes and arrivals/departures of monitoring nodes. In this work, we address how to optimally assign channels to a set of monitoring nodes that are already deployed in the network. This problem, even without determining the placement of them, is still NP-hard. To solve this problem, we develop distributed algorithm based on our prior (centralized) algorithm for stationary networks.
Further, we allow for imperfect detection schemes, where monitoring nodes may generate false negatives and/or false positives. But, we would like to still maintain the accuracy of the network diagnoses above a certain level. Our approach to attain the desired accuracy level is to provide multiple detection cover for ad hoc nodes, i.e., let each node be monitored by multiple monitoring nodes. The problem that we address in this work is how to energy-effectively monitor the network while maintaining the accuracy of network diagnoses above a desired level.
Achieved Technical Goals
In the first work, our major contribution is to develop the best approximation algorithm that one can achieve for our problem. That is, our algorithm always achieves a factor of the optimal performance, i.e., the maximum detection coverage, and the approximation ratio is the best achievable for our problem among all polynomial-time algorithms. Our algorithm is based on LP rounding technique, where we first formulate the problem as an integer linear program, then relax the integer constraints and solve the resulting linear program (LP) relaxation, which takes polynomial time, and finally round the optimal LP solution, which contains fractional values in general, to an integer value, either 0 or 1. We present two rounding schemes—randomized and deterministic. The probabilistic rounding scheme achieves the best approximation ratio probabilistically (i.e., on average) while the deterministic rounding scheme attains it deterministically (i.e., each time it runs).
In the second work, our main contribution in this work is to develop a distributed algorithm that preserves the same approximation ratio as our prior (centralized) algorithm while providing a distributed solution that is amenable to online implementation. Further, our algorithm is cost-effective in terms of communication and computational overheads. Also, we present two operational modes of our algorithm for two types of networks that have different rates of network changes—a proactive mode for fast varying networks and a reactive mode for slowly varying networks. The design milestone of our distributed algorithm is the proximal optimization algorithm and the duality theory. They enable us to decompose the given global optimization problem into sub-problems that can be solved in a distributed manner requiring only local communication among neighboring nodes.
In the third work, which is on going, our goal is to minimize the number of monitoring nodes being activated while meeting a given detection accuracy level for all ad hoc nodes by judiciously selecting a set of monitoring nodes to be activated and assigning channels to the selected monitoring nodes. We show that finding any feasible solution to the problem is NP-hard. That is, it is NP-hard to even find any solution that activates all monitoring nodes and gives a channel assignment that meets the desired accuracy level of the network diagnoses. Alternatively, we consider a problem where we find a channel assignment that maximizes the detection coverage, in terms of the number of ad hoc nodes, subject to meeting the desired detection accuracy. We are developing algorithms to solve this alternative problem.
Students
- DongHoon Shin, shin39 AT purdue DOT edu
- Matthew Tan Creti, mtancret AT purdue DOT edu