We focus on detecting intrusions in ad hoc networks using the misuse detection technique. We allow for detection modules that periodically fail to detect attacks and also generate false positives. Combining theories of hypothesis testing and approximation algorithms, we develop a framework to counter different threats while minimizing the resource consumption. We obtain computationally simple optimal rules for aggregating and thereby minimizing the errors in the decisions of the nodes executing the intrusion detection software (IDS) modules. But, we show that the selection of the optimal set of nodes for executing the IDS is an NP-hard problem. We describe a polynomial complexity, distributed selection algorithm, "Maximum Unsatisfied Neighbors in Extended Neighborhood" (MUNEN) that attains the best possible approximation ratio. The aggregation rules and MUNEN can be executed by mobile nodes with limited processing power. The overall framework provides a good balance between complexity and performance for attaining robust intrusion detection in ad hoc networks.

We consider ad hoc networks with multiple, mobile intruders. We investigate the placement of the intrusion detection modules for misuse-based detection strategy. Our goal is to maximize the detection rate subject to limited availability of communication and computational resources. We mathematically formulate this problem, and show that computing the optimal solution is NP-hard. Thereafter, we propose two approximation algorithms that approximate the optimal solution within a constant factor, and prove that they attain the best possible approximation ratios. The approximation algorithms though require recomputation every time the topology changes. Thereafter, we modify these algorithms to adapt seamlessly to topological changes. We obtain analytical expressions to quantify the resource consumption versus detection rate tradeoffs for different algorithms. Using analysis and simulation, we evaluate these algorithms, and identify the appropriate algorithms for different detection rate and resource consumption tradeoffs.

We focus on detecting intrusions in ad hoc networks using the misuse detection technique. We allow for detection modules that periodically stop functioning due to operational failure or compromise by intruders. Combining theories of stochastic coverage processes and approximation algorithms, we develop a framework to counter failure of detection modules, while minimizing the resource consumption. We show that the selection of the optimal set of nodes for executing the detection modules is an NP-hard problem. We present a distributed polynomial complexity selection algorithm that attains the best possible approximation ratio. We next consider a simple heuristic selection strategy that allows for seamless operation in time varying topologies. We obtain analytical expressions to quantify the tradeoffs between the resource consumption and detection rates attained by these algorithms. Using analysis and simulation, we identify the appropriate algorithms for different failure rates, resource limitation, and required detection rates.

Sensor networks have increasingly become the subject of intense scientific interest over the past few years. In this work, we focus on intrusion detection in sensor networks. The intrusion detection community has been focusing mainly on wired networks. But techniques geared towards wire line networks would not suffice for a sensor environment because of the constraints associated with such networks. In this paper, we consider the arbitrary sized sensor networks and propose algorithms to improve the detection rates by intelligently enabling the intrusion detection functionality on particular sensor nodes. The proposed algorithms, based on the concepts of minimum cut-set and minimum dominating set, allow for a distributed implementation. The performance of the algorithms in identifying intrusions using signature based detection techniques is studied via simulations.

We consider ad hoc networks with multiple, mobile colluding intruders. We investigate the placement of the intrusion detection modules for misuse intrusion detection. Our goal is to maximize the detection performance subject to limitation in the computational resources. We mathematically formulate different detection objectives, and show that computing the optimal solution is NP-hard in each case. Thereafter, we propose a family of algorithms that approximate the optimal solution, and prove that some of these algorithms have guaranteeable approximation ratios. The algorithms that have analytically guaranteeable performance require re-computation every time the topology changes due to mobility. We next modify the computation strategy so as to seamlessly adapt to topological changes due to mobility. Using simulation we evaluate these algorithms, and identify the appropriate algorithms for different detection performance and resource consumption tradeoffs.