A Software Architecture to Support Misuse Intrusion Detection.”
`
`Sandeep Kumar
`
`Eugene H. Spafford
`
`The COASTProject
`Department of Computer Sciences
`Purdue University
`West Lafayette, IN 47907-1398
`{kumar,spaf}@cs.purdue.edu
`
`Keywords:intrusion detection, misuse, anomaly.
`
`June 16, 1995
`
`Abstract
`
`Misuse intrusion detection has traditionally been understood in theliterature as the detection of
`specific, precisely representable techniques of computer system abuse. Pattern matching is well
`disposed to the representation and detection of such abuse. Each specific method of abuse can
`be represented as a pattern and several such patterns can be matched simultaneously against
`the audit logs generated by the operating systern kernel. Usingrelatively high level patterns to
`specify computer system abuse relieves the pattern writer from having to understand and encode
`the intricacies of pattern matching into a misuse detector. Patterns represent a declarative way
`of specifying what needs to be detected, instead of specifying how it should be detected. We
`have devised a model of matching based on Colored Petri Nets specifically targeted for misuse
`intrusion detection. In this paper we present a software architecture for structuring a pattern
`matching solution to misuse intrusion detection. In the context of an object oriented language
`used for the prototype implementation we describe the abstract classes encapsulating generic
`functionality and the interrelationships between the classes.
`
`1
`
`Introduction
`
`Intrusion detection is an important monitoring technique in computer security aimed at the detec-
`tion of security breaches that cannot be easily prevented by access and information flow control
`techniques. These breaches can be a result of software bugs, failure of the authentication module,
`improper computer system administration, etc.
`Intrusion detection has historically been studied
`as two sub-topics: anomaly detection and misuse detection. Anomaly detection is based on the
`premise that many intrusions appear as anomalies on ordinary or specially devised computer sys-
`tem performance metrics such as I/O activity, CPU usage, etc. By maintaining profiles of these
`metrics for different subject classes, for example individual users, groups of users, or programs
`and monitoring for large variations on them, many intrusions can be detected. Misuse intrusion
`detection has traditionally been understood in the literature as the detection of specific, precisely
`representable techniques of computer system abuse. For example, the detection of the Internet
`worm attack by monitoring for its exploitation of the fingerd and sendmail bugs [Spa89] would
`fall under misuse detection.
`Several approaches to misuse detection have been tried in the past. They include language
`based approaches to represent and detect intrusions, such as ASAX [HCMM92]; developing an
`
`“This work was funded by the Division of INFOSEC Computer Science, Department of Defense.
`
`(cid:38)(cid:54)(cid:16)(cid:20)(cid:19)(cid:21)(cid:24)
`CS-1025
`(cid:38)(cid:76)(cid:86)(cid:70)(cid:82)(cid:3)(cid:54)(cid:92)(cid:86)(cid:87)(cid:72)(cid:80)(cid:86)(cid:15)(cid:3)(cid:44)(cid:81)(cid:70)(cid:17)(cid:3)(cid:89)(cid:17)(cid:3)(cid:41)(cid:76)(cid:81)(cid:77)(cid:68)(cid:81)(cid:15)(cid:3)(cid:44)(cid:81)(cid:70)(cid:17)(cid:3)
`Cisco Systems, Inc. v. Finjan, Inc.
`
`
`194
`
`

`

`
`
`APT! for the same purpose, such as in Stalker [Sma95]; using expert systems to encode intrusions
`such as in MIDAS [SSHW88], Haystack [Sma88], and NIDX [BK88]; andhigh level state machines
`to encode and matchsignatures” such as STAT [PK92] and USTAT[Ilg92]. We proposed using
`a pattern matching approach to the representation and detection of intrusion signatures [KS94b]. °
`This approach resulted from a study of a large number of common intrusions with the aim of
`representing them as patterns to be matched against the audit trail [KS94a]. The signatures were
`also classified into categories based on their theoretical tractability of detection [Kum95]. We
`consider the following to be advantages unique to our modelof pattern represention and matching.
`«» Sequencing and other ordering constraints on events can be represented in a direct manner.
`Systems that use expert system rules to encode misuse activity specify ordering constraints
`by directly specifying temporal relationships between facts in rule antecedents. This makes
`the Rete match procedure [For82] of determining the eligible production rules for firing,
`inefficient. STAT [PK92] and USTAT [Ilg92] permit the specification of state transition
`diagrams to represent misuse activity but their transition events may be high level actions
`that need not corresponddirectly to system generated events. ASAX [HCMM92]is the closest
`to our approach butit is less declarative. In specifying patterns in their rule based language
`RUSSELL, one must explicitly encode the order of rules that are triggered at every step.
`While ASAX tends to be a mechanism for general purpose audit trail analysis, our effort is a
`combination of mechanism and policy. The features provided in our work are closely tied to
`the intrusion characteristics we are trying to detect.
`Our model provides for a fine grained specification of a successful match, The use of pattern
`invariants (to be explained later) allows the pattern writer to encode patterns that do not
`need to rely on primitives built into the matching procedure to manage the matching, for
`example to clean up partial matches once it is determined that they will never match. This
`frees the matching subsystem from having to provide a complete set of such primitives and,
`in the process, couple the semantics of pattern matching with the semantics of the primitives.
`Our method also has the following benefits but these are not necessarily a consequence of our
`approach.
`Portability. Intrusion signatures can be moved across sites without rewriting them to accom-
`modate fine differences in each vendor’s implementation of the audit trail. Because pattern
`specifications are declarative, a standardized representation of patterns enables them to be
`exchanged between users running variants of the same flavor of operating system, with syn-
`tactically differing audit trail formats.
`Declarative Specification. Patterns representing intrusion signatures can be specified by defin-
`ing what needs to be matched, not howit is matched. That is, the:patternis not encoded by
`the signature writer as code that explicity performs the matching. This cleanly separates the
`matching from the specification of what needs to be matched.
`.
`In this paper we describe our implementation of the model that was presented in [KS94b]. We
`have used C++ [Str91] as the programming languagefor the implementation of the prototype. The
`prototype runs underthe Solaris 2.3 operating system and uses the Sun BSM [Sun93] audit trail as
`its input to detect intrusions. The programming techniques and languagefeatures we have used for
`the implementation are applicable to other programming languages as well. Our implementation
`is directed at providing a set of integrated classes that can be used in an application program to
`implement a generic misuse intrusion detector. The implementation also suggests a possible way
`of structuring classes encapsulating generic functionality and the interrelationships between the
`classes to design any misuse detector. The paper also describes that structure.
`‘Application Programming Interface, i.e., a set of library function calls employed for representing and detecting
`intrusions.
`,
`"We use the terms intrusion signature and intrusion pattern synonymously.
`£35
`
`

`

`
`
`Our choice of the language was dictated by the free availability of quality implementations of
`C++, our familiarity with it and the linguistic support provided in it to write modular programs.
`Theset of integrated classes we have developed can be programmed in many other object oriented
`languages as well because no properties specific to C++ have been assumed or used. We only
`exploit the language’s encapsulation and data abstraction properties. We use the word class in a
`generic sense and the corresponding notion from many other languages can be substituted here.
`
`2 Our Approach
`The model of pattern representation and detection on which the implementation is based was
`described in [KS94b]. Briefly, each intrusion signature is represented as a specialized graph in this
`model. These graphs are an adaptation of Colored Petri Nets described by Jensen [Jen92] with
`guards defining the context in which signatures are considered matched. Vertices in the graph
`represent system states. The pattern represents the relationship among events and their context
`that forms the crux of a successful intrusion or its attempt. Patterns may have pre-conditions and
`post-actions associated with them. A pattern pre-conditionis a logical expression that is evaluated
`at the time the pattern springs into existence. It can also be used to set up state that may be used
`later by the pattern. Post-actions are performed whenever the pattern is matched successfully. For
`example, it might be desirable to raise the audit level of a user if he fails a certain number of login
`attempts within a specified time duration. This can be expressed as a post-action. Patterns may
`also include invariants to specify that another pattern cannot appear in the input stream whileit
`is being matched. If a pattern is regarded as a set of event sequences P that it matches, and an
`invariant is regarded as another set of event sequences J that it matches, then a pattern with an
`invariant specification corresponds to the set P A J. A pattern can have more than one invariant.
`That corresponds to P AX; A«::A In.
`invariants are needed to specify cases when it is no
`longer useful to continue a pattern match. For example, a pattern that matches process startups
`and recordsall file accesses by the process may require an invariant that specifies that matching
`be discontinued once the process has exited. From the practical viewpoint of specifying intrusion
`patterns, invariants usually result in more efficient matching rather than adding alia to
`the pattern specification.
`As a concrete exampleof a pattern, consider the monitoring of Clarke-Wilson [CW89] integrity
`triples in a computer system using the system generated audit trail. Clarke-Wilson triples are
`devised to ensure the integrity of important data and specify that only authorized programs running
`as specific user ids are permitted to write to files whose integrity must be preserved. This is similar
`to the maintenance of the integrity of the password file on UNIX systems by allowing only some
`programs, like chfn® to alterit.
`Onepattern that might be used for this purpose is formed by a sequence of two sub-signatures:
`(1) that matches the creation of a process and (2) that matches any process writing to a file. By
`appropriately specifying that the created process is the same as the one that writes, and retrieving
`the user id, the program name, and thefile name from the context of the match, Clarke-Wilson
`integrity triples can be monitored. See figure 1 for a pictorial representation of the signature.
`The implementation of this model can be broken down into the following sub-problems:
`1. The external representation of signatures. That is, how does the signature writer encode
`signatures for use in matching.
`2. The interface to the event source. In our example it would be the interface to the C2 audit
`trail.
`3. Dispatching the events (audit records) to the signatures and the matching algorithms used
`for matching.
`
`?chfn is used to change information about users which is stored in a well-known file, /etc/passwd.
`
`
`
`196
`
`

`

`
`
`
`A PROGRAM STARTS UP|}A PROCESS WRITES TO A FILE
`
`F = this file’s name
`PR = this program's name
`PID! = this process’s pid
`PID = this process’s pid
`Context: PID = PID'A Clarke-Wilson access triples do not permit PR run-
`ning as user id PID to write to file F.
`
`Figure 1; Monitoring Clarke-Wilson triples as a pattern match.
`
`In addition to solving these requirements, our
`These issues ate discussed in the next section.
`implementation is designed to simplify the incorporation of the following:
`» The ability to create signatures and to destroy them dynamically, as matching proceeds.
`« The ability to partition and distribute signatures across different machines for improving
`performance.
`» The ability to prioritize matching of some patterns over others.
`« Theability to handle multiple event streams within the same detector without the need to
`coalesce the event streams into a single event stream.
`We describe our design in the next section and show how the library ¢classes implement the
`
`design.
`
`3 Overall Architecture
`The library consists of several classes, each encapsulating a logically different functionality. An
`application program that uses the library includes appropriate header files and links in the library.
`The external representation of signatures (sub-problem 1) is done using a straightforward rep-
`resentation syntax that directly reflects the structure of their graph. These specifications can be
`stored in a file or maintained as program strings. When a signatureis instantiated in an application,
`a library provided routine (a Server class member function) is called that compiles the signature
`description to generate code that realizes the signature. This code is then dynamically linked to
`the application program and pattern matchingfor that signature is initiated. The application also"
`instantiates a server for each type of event stream used for matching. Events are totally encapsu-
`lated inside the server object (sub-problem 2) and are only used inside signature descriptions. As
`signature descriptions are compiled they are added to the server queue. The server accesses and
`dispatches events to the patterns on its queue in some policy specifiable order (sub-problem 3).
`The application structure is explained below which gives an overall view of the application.
`Section 3.2 looks at the structure of events. Section 3.3 explains the structure of the server itself
`in detail and its relationship to the patterns that are instantiated by the application.
`
`3.1 Application Structure
`As an example application structure, consider matching the pattern described in figure 1. This
`may look as shown below.
`//file application.¢
`#include "C2_Server.h"
`
`int main()
`{
`
`C2_Server §;
`C2_Pattern *pi = S.parse_file("CW"); //read signature from "CW"
`
`197
`
`AIanorwhe
`
`

`

`
`
`
`
`8
`9
`10
`
`/* duplicate a thread of control if necessary. run() doesn’t return */
`S.run();
`
`11
`12
`
`return(1);
`
`}
`The application program makes use of a C2_Server object. The server object understands the
`layout of events and the event types that can belegally used in a signature definition. C2_Server
`also knows how to access events,
`in this case from. the audit trail, and how to dispatch them to
`the signatures that are registered with it. The server is also responsible for parsing signature
`descriptions and can check it for correctness because it understands the data format of the events.
`The call to the server member function parse_file reads, compiles, and registers a new pattern
`with the server object. When the server object member function $.run() is called, it starts reading
`events and dispatching them. This consumes one thread of control as S.run() never returns.
`The server is responsible for implementing concurrency control among its member functions to
`ensure that concurrent calls to its public member functions do not corrupt its internal state. Our
`implementation uses the idea of monitors [Hoa74] to ensure this. The pattern description contained
`in file CW looks as shownin listing 1 below. The pattern is written to match against the Sun BSM
`[Sun93] audit trail.
`//file patterns-ip
`1
`pattern CW "Clarke Wilson Monitoring Triples" priority 10
`2
`int PID, EVID;
`/* token local variables. may be initialized. */
`3
`str PROG, FILE;
`PROGis a token local variable that stores the program name corresponding to the process id PID,
`FILE stores the file name that PROGopens for writing. EUID stores the effective user id of PROG.
`4
`state start, after_exec, violation;
`5
`post_action{
`6
`printf("CW violated for file 4s, PID %d, EUID %d\n", FILE, PID, EUID);
`7
`}
`The post action is code that is executed when the pattern is successfully matched.
`8
`neg invariant first_inv
`9
`state start_inv, final;
`10
`‘
`
`trans exit (EXIT)
`il
`<- start_inv;
`12
`,
`-> final;
`13
`|_ { PID = this[PID];
`14
`end exit;
`15
`end first_inv;
`16
`The invariant specifies the removal of partial matches once a process has exited. What follows
`is the pattern description. The pattern matches all EXECVE records to monitor the creation ofall
`processes in the system. Once a process creation is matched, the pattern further attempts to match
`all possible ways in which the process could modify a file. These could be:
`
`}
`
`e Opena file to read and createit if it doesn’t exist. Or, open a file to read and truncate it if
`it exists......and so on for all the other valid audit record types involving an open that might
`change the file. These are handled in transition mod1.
`
`e Delete a file. This is handled in transition modi2.
`
`17
`
`trans exec(EXECVE) /* EXECVE is the event type of the transition */
`198
`
`
`
`

`

`18
`19
`20
`21
`22
`23
`24
`25
`26
`27
`28
`29
`30
`31
`32
`33
`34
`35
`36
`37
`
`38
`
`<- start;
`-> after_exec;
`|_ { this[ERR] = 0 && PID = this[PID] && PROG = this[PROG] &&
`EUID = this[EUID]; }
`end exec;
`
`trans modi (OPEN_RC|OPEN_RTC|OPEN_RT|OPEN_RW|OPEN_RWC|
`OPEN_RWTC|OPEN_RWT|OPEN_W|OPEN_WC | OPEN_WTC | OPEN_WT)
`<- after_exec;
`-> violation;
`|. { this[ERR] = 0 && PID = this[PID] && FILE = this[0BJ] &&
`disallowed(EUID, PROG, FILE); }
`end modt;
`
`‘trans mod12(UNLINK)
`<- after_exec;
`-> violation;
`|_ { this[ERR] = 0 && PID = this[PID] && FILE = this[OBJ] &&
`disallowed(EUID, PROG, FILE); }
`end modi2;
`
`end CW;
`
`Listing 1: A Sample Pattern Description
`If an application needed to match patterns against IP datagrams, it might have used an IP_Server
`instead of C2_Server or concurrently with it within the same application program.
`
`3.2 Event Structure
`Each event in the event stream is converted to an instance of an event class. For handling a C2
`audit trail this class might be named C2_Event. This class encapsulates all the attributes common
`to C2 audit records. Derived classes of C2_Event can be usedfor specifying more specialized types
`of audit records. For example, C2Event_EXECVE and C2Event_LINK can be derived to represent
`audit records generated by the execve and link system calls. Each event object can identify its
`type throughits type() member function. This is used by the server to identify an event before
`dispatching it to the appropriate patterns. All the data belonging to the event is made awailable
`through its member functions. This encapsulates the organization of data in the event, which may
`be system dependentin general. The descriptionofall the event classes constitutes the backend of
`the system andis one of the few system dependent layers.
`
`3.3 Server Structure
`For each event, the server looks atits type and consults a dynamically maintained table of patterns
`that have requested events of that type. It then calls the Patproc procedure of each such pattern.
`Patprocis a procedureassociated with every pattern (its member function) that handles events for
`it. This approach to handling eventsis similar to the approach taken in Microsoft Windows[Pet92].
`Events that are referenced in a signature description are explicitly requested by the signatures for
`dispatching when they are instantiated.
`Events can be dispatched to patterns based on their priority. Patterns can be placed in queues
`at the appropriate priority level, and patterns serviced in each queue in a round robin fashion.
`This ordering of patterns by priority assumes that on the average, an event can be dispatched to
`all the patterns requesting it in a time less than the mean time of generation of an event. If this
`requirement is not met, patterns up to a certain level in priority may be perpetually starved. A
`199
`
`

`

`
`
`mechanism to age patterns in which patterns that have not been exercised by any event for a length
`of time have their priority increased, can be added. Pictorially this may looklike:
`
`Gy
`
`events
`
`a
`
`”
`
`Ne
`
`SorkPaOkey
`
`unueuwuo
`ao
`
`a 22
`
`BwySoS
`
`ROUND ROBIN
`
`Highest Priorlty Patlerns
`
`a
`
`ROUND ROBIN
`
`Lowest Priority Patterns
`
`Our prototype does not currently implementthepriority structure of dispatching events to patterns.
`It treats every pattern to be of the samepriority.
`
`3.4 Summary
`The use of an event stream with the detector requires the creation of two classes. One event
`class that is the root class of all events provided in the event stream; the other, a server class
`that parses pattern descriptions, instantiates them and manages them onits data structures. The
`server class interacts with the event class by converting raw events into objects of this class and
`dispatching them to patterns. The interrelationship between the various classes is shownin figure 2.
`It shows how two event streams, namely IP datagrams and C2 audit records can be used together.
`IP_EVENTSis the root class from which all the events corresponding to IP datagrams can be derived.
`Similarly, C2_EVENTS is theroot class for deriving C2 audit record objects. Signatures written to
`match against IP datagrams are queued in an instance of IP_SERVER, while signatures that match
`against the audit trail are queued in an instance of C2_SERVER. Class names bounded by dotted —
`boxes are abstract classes. The functions identified within these boxes are the pure virtual functions
`of these classes.
`:
`
`5m
`
`pees
`
`|E Seeiee
`
`|
`
`\P_PATTERN
`
`OR...
`IP_SERVER|
`
`'
`4
`
`Roamer
`
`14
`
`_
`.
`| c2_SERVER|
`ba
`
`C2_PATTERN
`
` BR i
`
`| EVENT
`|
`int type()
`eos oi a.
`| ipevents |
`|.c2_EVENTS |
`
`jEvent_TCP Event_UDP| C2event_EXEC C2event_CHMOD|
`a
`albre
`PATTERN ©
`|
`| void PatProc(Event*)
`
`i
`i
`
`:
`
`. P. mt
`|IP_PATTERN| [c2_PATTEi
`
`_ Figure 2: Interrelationship between the various classes in the detector.
`
`4 Design Choices
`By far the most significant consideration guiding the design was the run-timeefficiency ofthe
`detector. For misuse detection using a O2 generated audit trail, one might reasonably expect
`;
`200
`
`
`
`

`

`to process events (audit records) at the rate of 50K-500K/user/day [Sma95]. Furthermore, any
`computer resource required for matching signatures reduces the availability of these resources for
`general use. We therefore decided not to interpret the pattern automata by using table lookups to
`determine the pattern structure, but instead to compile the pattern description into an automaton.
`This also has the benefit of compile time optimizations of guard expressions present in the pattern.
`As the generated coderealizing the automaton did not need to be “user friendly,” we tried to make
`it more efficient by using functions as little as possible to avoid function call overhead in cases
`where functions could not be inlined. This often meant that data structures manipulated by the
`various pieces of the generated automaton were not encapsulated and were manipulated directly
`by these pieces. This has not proved to be a problem as the routines that generate this “program”
`are structured and the generated program logic can be deciphered by following the structure and
`logic of the generating routine.
`The overriding constraint of efficiency combined with the requirement to dynamically create
`and destroy patterns meant that automaton descriptions be compiled and dynamically linked for
`the purpose of matching. An additional benefit of the dynamic creation of patterns is that new
`patterns can be created within an executing program basedon the logic and execution flow of the
`program. For example, it might be desirable to instantiate specific patterns for matching based on
`the type and degree of observed suspicious activity. Such patterns may depend on the particular
`user and other specifics of the suspicious activity.
`:
`Ourdesign, which is based on the modelof dispatching events to patterns lends itself naturally
`for distribution.
`In a distributed design, the event sources (audit trails) may be generated on
`different machines and their processing on another machine. Thatis, the patterns, the server and
`the event sources may all reside on physically different machines. The server can then retrieve
`events by using any of several well known techniques [BN84, Par90] and dispatch them to patterns.
`Although our current implementation is single host based, a distributed implementation should be
`straightforward.
`
`5 Performance
`The experiments described below were done on a Sun SPARCstation 5 with 32MB of memory
`running Solaris 2.3 underlight load. The audit file was generated separately by turning on auditing
`and simulating exploitations by hand and under program control. Auditing was configured with
`the default configuration which logs all events, both successful and failed. The pattern descriptions
`were translated into C++ code and compiled separately. The running times shown in the graphs
`below represent the reading of the audit file, conversion of each audit record into an object, and
`dispatching the event to all the patterns that request that event.
`It does not include the time
`for the matcher to load and begin execution, nor does it include the time to dynamically link the
`patterns.
`/
`Signatures were written for vulnerability data drawn from COPS [FS91], CERT advisories
`[CER] and the bugtraq and 8lgm‘*electronic mailinglists.
`Figure 1 shows how much time it took to match each signature against an audit file of ap-
`proximate size 400KB°. Each sample point in the figure is the mean value of 200 runs. The small
`horizontal lines on either side of each point represents the standard deviation of the value over the
`runs. The audit file contained 2514 events. The sample point (0, 5.17) in the figure represents that
`the detector took 5.17s to create all the event objects and destroy them. The point (1,5.45) means
`that pattern numbered 1 (numberedarbitrarily) took 5.45s when exercised by the 2514 events.
`*Roth lists discuss computer
`security vulnerabilities,
`their exploitation and steps
`for prevention and
`detection.
`Bugtraq is
`issued from bugtraq@crimelab.com and 8lgm advisories can be retrieved from
`fileserv@bagpuss.demon.co.uk.
`5k in this section means 1000.
`
`201
`
`

`

`
`
`
`
`Some patterns take very little time, just a little over what it took to run with no patterns. The
`reason for this is that the type of events used in the pattern occurred so infrequently in the event
`stream that the cost of exercising the pattern on those events was negligible when compared with
`the creation anddeletion of all the events in the audit trail. The mean time for the creation and
`deletion of an audit trail event is then 5.17/2514 = 2.1ms. This is the fixed cost per event for the
`
`6
`
`5.8
`
`|
`|
`
`Time 6
`(usr+sys)
`in secs BA
`
`5.2
`
`5
`
` system.
`
`6
`
`5.8
`
`5.6
`
`Time
`(usr-+sys)
`in secs 54
`
`5.2
`
`5
`
`0
`5
`10
`15
`20
`Figure 2: Time for matching multiple
`patterns for a 400K auditfile.
`
`Figure 1: Time for matching each pattern for
`a 400K audit file.
`
`Figure 2 shows the time taken when more than one pattern was matched simultaneously in the
`detector. The event stream and the pattern numbers are the same as in the previous simulation.
`In the figure, the data point (3,5.74) shows that it took 5.74 to exercise the three patterns 1,2,3
`together in the system. The fixed overhead cost of reading the audit file and converting each audit
`record into an object: is the same as above, the varying cost that takes the multiplicity of patterns
`into accountis:
`
`variable cost/event/pattern ~ (5.91 — 5.17) /(2514 * 19) = ldys
`
`This calculation uses the data point (19,5.91) which indicates that the detector took 5.91s to
`exercise 19 patterns together against an audit trail that consisted of 2514 events.
`Consider the extrapolation of these results to estimate the performance of the detector in a
`more realistic setting, When running a set of programs in sequence that saturated the CPU, the
`- Sun auditing subsystem generated about 1MB every 10 minutes on the single user SPARCstation.
`This translates to about 6MBper hour. This is about 2514 x 6/.4 ~ 38K events per hour. Consider
`that there are 100 patterns in the detector. Then, for one hour of intense CPU activity, the detector
`requires the following time to process the generated audit data:
`Fixed overhead
`= 5.17/2514 x 38000s = 78.15s
`Variable overhead = 15s x 100 x 38000 = 57s
`Total time
`=
`= 135,15s
`
`the detector requires + 135s to match about 100
`Thus, for every hour of intense activity,
`patterns. This fraction is 135/3600 x 100 = 3.75% ~ 4% of the hourly activity. These results
`correspond to an unoptimized version of the detector.
`202
`
`—
`
`
`
`

`

`6 Summary
`This paper described a possible architecture for structuring a misuse intrusion detector based on
`pattern matching. The structure is client-server based in which the server obtains events and
`dispatches them to clients (patterns) which implement the matching procedure specific to their
`structure. Implementingthis structure as a library permits embedding this type of matching within
`application programs. Our prototype allows the dynamic creation of patterns. These patterns are
`translated from a description language into C++ code that realizes the pattern and dynamically
`links that code into the application. The overhead: of matching 100 signatures simultaneously
`against an audit trail that was generated at the rate of 6MB per hour on a Sun SPARCstation 5
`was calculated to be under 5%.
`
`7 Acknowledgements
`We wouldlike to thank all members of the COAST laboratory for their valuable comments onthis
`paper, in particular Christoph Schuba for his extra effort and help with an earlier draft of this
`paper.
`'This work was supported, in part, by a gift from Sun Microsystems, and by DoD contract
`MDA904-93-C-4081:
`this support is gratefully acknowledged.
`
`References
`[BK88] David S. Bauer and Michael E. Koblentz. NIDX - An Expert System for Real-Time
`Network Intrusion Detection. In Proceedings - Computer Networking Symposium, pages
`98-106. IEEE, New York, NY, April 1988.
`
`[BN84] Andrew D. Birrell and Bruce Jay Nelson. Implementing Remote Procedure Calls. ACM
`Transactions on Computer Systems, 2(1):39-59, February 1984.
`
`[CER] CERT Advisories. Available by anonymous ftp from cert.sei.cmu.edu:/pub/cert_advi-
`sories,
`
`[CW89] David D. Clark and David A. Wilson. Evolution of a Modelfor Computer Integrity.
`Report of the Invitational Workshop on Data Integrity, September 1989.
`
`[For82] Charles L. Forgy. RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern
`Match Problem. In Artificial Intelligence, volume 19. 1982.
`
`[FS91] Daniel Farmer and Eugene Spafford. The COPS Security Checker System. Technical
`Report CSD-TR-993, Purdue University, Department of Computer Sciences, Septem-
`ber 1991.
`
`[HCMM92] Naji Habra, B. Le Charlier, A. Mounji, and I. Mathieu. ASAX: Software Architec-
`ture and Rule-based Language for Universal Audit Trail Analysis. In Proceedings of
`ESORICS 92, Toulouse, France, November 1992.
`
`[Hoa74] C. A. R. Hoare. Monitors: An Operating System Structuring Concept. Communica-
`tions of the ACM, 17(10):549-557, 1974.
`
`[flg92] Koral gun. USTAT: A Real-Time Intrusion Detection System for UNIX. Master’s
`thesis, Computer Science Department, University of California, Santa Barbara, July
`1992.
`°
`,
`
`[Jen92] Kurt Jensen. Coloured Petri Nets - Basic Concepts I. Springer Verlag, 1992.
`
`203
`
`

`

`
`
`[KS94a] Sandeep Kumar and Eugene Spafford. A Taxonomy of Common Computer Security
`Vulnerabilities based on their Method of Detection. (unpublished), June 1994.
`
`([KS894b] Sandeep Kumar and Eugene H. Spafford. A Pattern Matching Model for Misuse In-
`trusion Detection. In Proceedings of the 17th National Computer Security Conference,
`. pages 11-21, October 1994.
`
`[Kum95] Sandeep Kumar. Classification and Detection of Computer Intrusions. PhD thesis,
`Purdue University, Department of Computer Sciences, (to appear) 1995.
`
`[Par90] Graham D. Parrington. Reliable Distributed Programming in C++: The Arjuna Ap-
`proach. In USENIX 1990 C++ Conference Proceedings, pages 37-50, 1990.
`
`[Pet92] Charles Petzold. Programming Windows 3.1. Microsoft Press, 1992.
`
`([PK92] Phillip A. Porras and Richard A. Kemmerer. Penetration State Transition Analysis —
`A Rule-Based Intrusion Detection Approach. In Fighth Annual Computer Security Ap-
`plications Conference, pages 220-229. IEEE Computer Society press, IEEE Computer
`Society press, November 30 — December 4 1992.
`
`[Sma88] Stephen E. Smaha. Haystack: An Intrusion Detection System. In Fourth Aerospace
`