Technical Reports


Click here for full text: PDF

An Empirical Approach to Modeling Uncertainty in Intrusion Analysis

Ou, Xinming; Rajagopalan, Siva Raj; Sakthivelmurugan, Sakthiyuvaraja
HP Laboratories


Keyword(s): intrusion detection; uncertainty; logic

Abstract: Uncertainty is an innate feature of intrusion analysis due to the limited views provided by system monitoring tools, intrusion detection systems (IDS), and various types of logs. Attackers are essentially invisible in cyber space and monitoring tools can only observe the symptoms or effects of malicious activities. When mingled with similar effects from normal or non- malicious activities they lead intrusion analysis to conclusions of varying confidence and high false positive/negative rates. This paper presents an empirical approach to the problem of uncertainty where the inferred security implications of low-level observations are captured in a simple logical language augmented with certainty tags. We have designed an automated reasoning process that enables us to combine multiple sources of system monitoring data and extract highly-confident attack traces from the numerous possible interpretations of low-level observations. We have developed our model empirically: the starting point was a true intrusion that happened on a campus network that we studied to capture the essence of the human reasoning process that led to conclusions about the attack. We then used a Datalog-like language to encode the model and a Prolog system to carry out the reasoning process. Our model and reasoning system reached the same conclusions as the human administrator on the question of which machines were certainly compromised. We then automatically generated the reasoning model needed for handling Snort alerts from the natural-language descriptions in the Snort rule repository, and developed a Snort add-on to analyze Snort alerts. Keeping the reasoning model unchanged, we applied our reasoning system to two third-party data sets and one production network. Our results showed that the reasoning model is effective on these data sets as well. We believe such an empirical approach has the potential of codifying the seemingly ad-hoc human reasoning of uncertain events, and can yield useful tools for automated intrusion analysis.

10 Pages

Additional Publication Information: To be published and presented at 2009 Annual Computer Security Applications Conference, Honolulu, December 9-11, 2009.

External Posting Date: October 6, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: October 6, 2009 [Fulltext]

Back to Index