A Declarative Framework for Intrusion AnalysisMatt FredriksonComputer Sciences DepartmentUniversity of Wisconsin – MadisonAbstractIn this paper we consider the problems of computer intru-sion analysis, understanding, and recovery. More specif-ically, we identify the various difficulties associated withthese problems, and propose a solution based on systemevents and the dependencies between them for simplifyingour motivating problems. We then present a tool we havedesigned called SLog that presents a system administratorwith all of the facilities required to analyze the event infor-mation present in system logs, and present only the eventinformation pertinent to an intrusion in a vastly simplifiedmanner. We discuss the ways in which the major designgoals of SLog – simplicity, extensibility, and scalability– are important when dealing with intrusions in realisticscenarios. Finally, we demonstrate the ability of SLog toaccurately return a simplified view of the relevant eventsin a realistic intrusion case study.1 IntroductionIntrusionson computer systems remain a formidable men-ace to the substantial infrastructure present in today’s pub-lic and private networks. The CERT coordination centerhas remained active in the task of following events re-lated 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 au-tomated attacks, increasing sophistication in attack tools,faster discovery of important system vulnerabilities, andan increasing focus on infrastructure attacks [5]. Thesefindings indicate that we can expect intrusions to becomemore frequent and more sophisticated.This poses several challenges for network administra-tors charged with the task of preventing attacks from oc-curing in the first place, as well as detecting and recov-ering from the attacks that will inevitably occur. Thereis a sizeable body of literature, as well as an active re-search community, that focuses on the first two problemsof prevention and detection. Prevention measures includetimely patch updates to vulnerable software, security-conscious operating system design [1, 6, 10], and networkperimiter security devices such as firewalls. Detectoinmeasures are diverse and numerous, ranging from manualanalysis [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 com-munity. This is certainly not for lack of interesting or sub-stantive problems in the area. An administrator is facedwith two important problems after an intrusion. First, hemust determine the cause of the intrusion, which in mostcases means discovering which process on the system al-lowed the intruder an undesired level of access. This stepof the recoveryis essential, as without it, the administratormust expect a similar intrusion at some point in the future.Next, a prudent administrator must discover all entities onthe system that may have been compromised or affectedin some way by the intrusion. Without this step, no guar-antees can be made regarding the integrity of the system’scontents.Having underscored the importance of proper intrusionrecovery, we now focus our attention on some of the dif-ficulties involved with recovery on a real system. We ob-serve that in a typical network setting, an administratormay have numerous sources of relevant information avail-able, including application logs, intrusion detector logs atboth the host and network level, as well as the entire stateof the persistent store. Furthermore, each of these sourcescan potentially contain an overwhelming amount of infor-mation. In an enterprise setting, it is not unreasonable toexpect log files with gigabytes of data. Clearly, culling therelevant information from these sources is a difficult, timeconsuming, and error-prone process.The fundamental problem here is that while thesesources may contain all of the information that is requiredto successfully recover from an intrusion, this informationis effectively drowned out by the high degree of opera-tional noise generated by everyday, legitimate use of thesystem. The task assigned to our hypothetical system ad-ministrator would be made much simpler if there were away for him to automatically filter the irrelevant informa-tion that corresponds to legitimate activity, and focus onlyon those details that pertain to the intrusion at hand. Thisis the problem that we will address in this work.1This paper describes a tool called SLog that attempts tofilter out the irrelevant portions of an event history, leavingonly those portions that provide information that may bevaluable when attempting to understand and recover froma specific intrusion. SLog does this by reasoning aboutthe system in terms of the events that are reported to haveoccurred on it, as well as the dependencies between theseevents. The primary goal of SLog is to provide a simpli-fied view of the objects and events that have been affectedin some way by the intrusion. However, it is crucial thatthis task is performed without over-simplifying the analy-sis in such a way that relevant events are discarded fromthe final report, leaving the administrator without a fullpicture of the effects of the intrusion. In an attempt to re-alize these conflicting goals, SLog provides facilities forviewing and reasoning about events at different concep-tual granularities.The rest of the paper will proceed as follows. Section2 gives an overview of the foundational principles, goals,and design decisions that were made while constructingSLog. Section 3 describes in some detail the various lan-guage constructs used in SLog to implement our designdecisions, as well as their syntax and semantics. Section4 presents a case study involving a realistic intrusion sce-nario to which we applied SLog, as well as a discussionof the results we collected from this case study. Section5 discusses some important related work, and Section 6concludes the paper and hints at some directions for fu-ture work.2 DesignHaving 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 thegoals we hope to achieve with such a system, continueby describing the high-level operational workflow of thesystem, and conclude by enumerating the specific compo-nents that we implemented to realize this workflow.2.1 Design