Graphical Inference for Multiple Intrusion Detection

Abstract—In this paper, we consider vulnerabilities of net-worked systems and develop a multiple intrusion detection system (MIDS) which operates by running belief propagation on an appropriately constructed weighted bipartite graph. In this bipartite graph, one set of nodes represents the different types of intrusions that are possible, the other set of nodes represents the set of significant measures that are available, and the (weighted) connections represent the dependence of a certain measure on a particular type of intrusion. We assume that the effect of each active intrusion on a particular significant measure is superim-posed on the normal operation of that measure; thus, we are able to obtain a complete representation of the overall bipartite graph model by superimposing the simpler graphs associated with each individual intrusion. The key ingredient of our MIDS is the development of a modified belief propagation max-product algorithm (MPA) that avoids the exponential complexity of the original MPA by limiting during the iteration process the number of active intrusions that are connected to a particular measure. Our simulation results indicate that the proposed MIDS performs well in detecting both single and multiple intrusions with a very low false alarm rate. Index Terms—Bayesian network, belief propagation algorithm, intrusion detection, multiple intrusion model, naive Bayesian network model. I