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.