Abstract
Intrusion detection and alert correlation are valuable and complementary techniques for identifying security threats in complex networks. Intrusion detection systems monitor network traffic for suspicious behavior, and trigger security alerts. Alert correlation methods can aggregate such alerts into multi-step attacks scenarios. However, both methods rely on models encoding a priori knowledge of either normal or malicious behavior. As a result, these methods are incapable of quantifying how well the underlying models explain what is observed on the network. To overcome this limitation, we present a framework for evaluating the probability that a sequence of events is not explained by a given a set of models. We leverage important properties of this framework to estimate such probabilities efficiently, and design fast algorithms for identifying sequences of events that are unexplained with a probability above a given threshold. Our framework can operate both at the intrusion detection level and at the alert correlation level. Experiments on a prototype implementation of the framework show that our approach scales well and provides accurate results.