A Declarative Framework for Intrusion Analysis Matt Fredrikson Computer Sciences Department University of Wisconsin Madison Abstract perimiter security devices such as firewalls Detectoin measures are diverse and numerous ranging from manual analysis 4 to fully automatic intrusion detectors 13 7 The problem of intrusion recovery on the other hand has not been studied as extensively by the academic community This is certainly not for lack of interesting or substantive problems in the area An administrator is faced with two important problems after an intrusion First he must determine the cause of the intrusion which in most cases means discovering which process on the system allowed the intruder an undesired level of access This step of the recovery is essential as without it the administrator must expect a similar intrusion at some point in the future Next a prudent administrator must discover all entities on the system that may have been compromised or affected in some way by the intrusion Without this step no guarantees can be made regarding the integrity of the system s contents Having underscored the importance of proper intrusion recovery we now focus our attention on some of the difficulties involved with recovery on a real system We observe that in a typical network setting an administrator may have numerous sources of relevant information available including application logs intrusion detector logs at both the host and network level as well as the entire state of the persistent store Furthermore each of these sources can potentially contain an overwhelming amount of information In an enterprise setting it is not unreasonable to expect log files with gigabytes of data Clearly culling the relevant information from these sources is a difficult time consuming and error prone process The fundamental problem here is that while these sources may contain all of the information that is required to successfully recover from an intrusion this information is effectively drowned out by the high degree of operational noise generated by everyday legitimate use of the system The task assigned to our hypothetical system administrator would be made much simpler if there were a way for him to automatically filter the irrelevant information that corresponds to legitimate activity and focus only on those details that pertain to the intrusion at hand This is the problem that we will address in this work In this paper we consider the problems of computer intrusion analysis understanding and recovery More specifically we identify the various difficulties associated with these problems and propose a solution based on system events and the dependencies between them for simplifying our motivating problems We then present a tool we have designed called SLog that presents a system administrator with all of the facilities required to analyze the event information present in system logs and present only the event information pertinent to an intrusion in a vastly simplified manner We discuss the ways in which the major design goals of SLog simplicity extensibility and scalability are important when dealing with intrusions in realistic scenarios Finally we demonstrate the ability of SLog to accurately return a simplified view of the relevant events in a realistic intrusion case study 1 Introduction Intrusions on computer systems remain a formidable menace to the substantial infrastructure present in today s public and private networks The CERT coordination center has remained active in the task of following events related to computer intrusions for the past several decades and has compiled a list of observed trends in this domain Among the more alarming trends are an increase in automated attacks increasing sophistication in attack tools faster discovery of important system vulnerabilities and an increasing focus on infrastructure attacks 5 These findings indicate that we can expect intrusions to become more frequent and more sophisticated This poses several challenges for network administrators charged with the task of preventing attacks from occuring in the first place as well as detecting and recovering from the attacks that will inevitably occur There is a sizeable body of literature as well as an active research community that focuses on the first two problems of prevention and detection Prevention measures include timely patch updates to vulnerable software securityconscious operating system design 1 6 10 and network 1 This paper describes a tool called SLog that attempts to filter out the irrelevant portions of an event history leaving only those portions that provide information that may be valuable when attempting to understand and recover from a specific intrusion SLog does this by reasoning about the system in terms of the events that are reported to have occurred on it as well as the dependencies between these events The primary goal of SLog is to provide a simplified view of the objects and events that have been affected in some way by the intrusion However it is crucial that this task is performed without over simplifying the analysis in such a way that relevant events are discarded from the final report leaving the administrator without a full picture of the effects of the intrusion In an attempt to realize these conflicting goals SLog provides facilities for viewing and reasoning about events at different conceptual granularities The rest of the paper will proceed as follows Section 2 gives an overview of the foundational principles goals and design decisions that were made while constructing SLog Section 3 describes in some detail the various language constructs used in SLog to implement our design decisions as well as their syntax and semantics Section 4 presents a case study involving a realistic intrusion scenario to which we applied SLog as well as a discussion of the results we collected from this case study Section 5 discusses some important related work and Section 6 concludes the paper and hints at some directions for future work 2 Design Having motivated the need for a system such as SLog we describe the overall design of our tool in this section We begin by giving a more thorough description of the goals we hope to achieve with such a system continue by describing the high level operational workflow of the system and conclude by enumerating the specific components that we implemented to realize this workflow 2 1 Design Goals The basic functional goal of SLog is to provide a