Creating and Maintaining a Good Intrusion Detection Hierarchy in Dynamic Ad Hoc Networks

Many insider attacks, such as certain forms of packet dropping, malicious routing updates, and wormholes, can only be detected using distributed and cooperative algorithms. One promising approach for applying these algorithms is using an intrusion detection (ID) hierarchy enabling data aggregation and local decision making whenever possible. A key challenge to this problem is the selection and maintenance of a scalable and robust hierarchy optimizing detection performance (e.g., latency, coverage, and false alarm rate) while incurring minimal cost (e.g., bandwidth and processing). Existing approaches (i.e. flooding for forming a Breadth First Search Tree) to constructing such a hierarchy are simple and distributed; however, their performance and cost can be undesirable. Moreover, mobility can produce constant large scale changes in the hierarchy that degrade performance and increase cost. The main contributions of this paper are to: a) model the performance and costs of ID hierarchies and represent them in formal objective functions and constraints, b) modify an existing versatile, multi-objective hierarchy generation and maintenance tool to create trees, c) give simulation results on the quality and stability of ID hierarchies in a 100-node mobile network