`
`Sandeep Kumar
`
`Eugene H. Spafford
`
`The COAST Project
`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 the literature 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 system kernel. Using relatively 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 hour 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 1/0 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 [SpaSQ] 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 [HGMMQZ]; 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)
`08-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
`
`
`
`
`
`API1 for the same purpose, such as in Stalker [Sma95]; using expert systems to encode intrusions
`such as in MIDAS [SSHWBS], Haystack [Sma88], and NIDX [BK88]; and high level state machines
`to encode and match signatures2 such as STAT [PK92] and USTAT [lngZ]. We proposed using
`a pattern matching approach to the representation and detection of intrusion signatures [K894b]. '
`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 [K394a]. The signatures were
`also classified into categories based on their theoretical tractability of detection [Knmgfi]. We
`consider the following to be advantages unique to our model of 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 [PKQZ] and USTAT [Ing2] permit .the specification of state transition
`diagrams to represent misuse activity but their transition events may be high level actions
`that need not correspond directly to system generated events. ASAX [HCMM92] is the closest
`to our approach but it 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 purposa 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 defim
`ing what needs to be matched, not how it is matched. That is, the'pattern is 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.
`I
`In this paper We describe our implementation of the model that Was presented in [KSQ4b]. We
`have used C++ [StrQl] as the programming language for the implementation of the prototype. The
`prototype runs under the Solaris 2.3 operating system and uses the Sun BSM [Sun93} audit trail as
`its input to detect intrusions. The programming techniques and language features 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.
`
`1Application Programming Interface, i.e., a set of library function calls employed for representing and detecting
`intrusions.
`_
`
`2We use the terms intrusion signature and intrusion pattern synonymously.
`195
`
`
`
`
`
`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.
`The set of integrated classes we have developed can be programmed in many other object oriented
`languages as well because no properties specific to G++ 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 [K894b]. 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-condition is 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 while it
`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 I that it matches, then a pattern with an
`invariant specification corresponds to the set P A T. A pattern can have more than one invariant.
`That corresponds to P A IT A
`A E;
`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 records all 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 functionality to
`the pattern specification.
`-
`As a concrete example of a pattern, consider the monitoring of ClarkeWilson [CWSQ] 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 chfn3 to alter it.
`One pattern 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 the file name from the context of the match, Clarke—Wilson
`integrity triples can be menitored. 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 CZ audit
`trail.
`
`3. Dispatching the events (audit records) to the signatures and the matching algorithms used
`for matching.
`
`Bel-urn is used to change information about users which is stored in a well-known file, lets/passed.
`
`196
`
`
`
`
`
`
`
`
`A PROGRAM STARTS UP A PROCESS WRITES TO A FILE
`
`PR 2 this program‘s name
`PID = this process’s pid
`
`F = this file’s name
`PID' = this process’s pid
`
`Context: PID = PI13% 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.
`
`These issues are discussed in the next section.
`In addition to solving these requirements, our
`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 prioritizematching of some patterns over others.
`- The ability 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 classes1 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 signature is 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 matching for 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~pr0biem 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 (subproblem 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 . C
`1
`#include ”C2_Server.h"
`
`int main()
`
`«I
`
`C2_Server S;
`
`C2_Pat1:ern #191 = S.parse_fil'e("Clvl"); l/read signature from "CW"
`
`197
`
`2 3
`
`4
`5
`
`6 7
`
`
`
`
`
`
`
`/* duplicate a thread of control if necessary. runO doesn’t return */
`S .runO ;
`
`return(1) ;
`
`}
`
`8
`9
`10
`
`11
`12
`
`The application program makes use of a 02_Server object. The server object understands the
`layout of events and the event types that can be legally 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 S.r1m() 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 [H0374] to ensure this. The pattern description contained
`in file CW looks as shown in listing 1 below. The pattern is written to match against the Sun BSM
`[Sun93] audit trail.
`f/file patterns—ip
`
`1
`2
`3
`
`pattern CW "Clarke Wilson Monitoring Triples" priority 10
`int PID, EUID;
`/* token local variables. may be initialized. */
`Str FROG, FILE;
`'
`
`PRDG is a token local variable that stores the program name corresponding to the process id PID1
`FILE stores the file name that PRUGopens for writing. EUID stores the effective user id of PBUG.
`4
`state start, after_exec, violation:
`5
`post_action- -[
`6
`printf("Cw violated for file is, PID “lid, 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 startninv, final;
`10
`'
`
`11
`
`12
`13
`
`14
`15
`16
`
`trans exit(EXIT)
`
`<- start_inv;
`—'> final;
`
`_
`
`1_ { PID = thisEPID];
`end exit;
`end first_inv;
`
`}
`
`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 of all
`
`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:
`
`a Open a file to read and create it 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 modi.
`
`- Delete a file. This is handled in transition mod12.
`
`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;
`|_ { thisEERR] = 0 && PID = this[PID] es PRGG = thisEPRDG] &&
`EUID = this[EUID]; }
`end exec;
`
`trans modi(UPENHRCIUPEN_RTC|GPEN_RTIDPEN_RWIDPEN_RWC|
`UPEN_RWTCIUPEN#RWTIDPENHWIUPEN‘HCIDPEN_WTCIDPEN_WT)
`<— after_exec;
`~> violation;
`|_ { thisEERR] = 0 es PID = thisEPID] && FILE = thisEDBJ] &&
`disallowed€EUID,
`PRDG, FILE); }
`end modi;
`
`-trans mod12(UNLINK)
`
`<— after_exec;
`a) violation;
`l_ { this[ERR] = D && PID = thisEPIDJ as FILE = thisEUBJ] &&
`disallowed£EUlD, FROG, FILE); }
`end mod12;
`
`end CW;
`
`Listing 1: A Sample Pattern Description
`If an application needed to match patterns against 1? 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 02
`audit trail this class might be named C2_Event. This class encapsulates all the attributes common
`to 02 audit records. Derived classes of CZJJvent can be used for specifying more specialized types
`of audit records. For example, C2EventfiEKECVE and CEEventHLINK can be derived to represent
`audit records generated by the execve and link system calls. Each event object can identify its
`type through its 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 available
`through its member functions. This encapsulates the organization of data in the event, which may
`be system dependent in general. The description of all the event classes constitutes the backend of
`the system and is one of the few system dependent layers.
`
`3.3 Server Structure
`For each event, the server looks at'its 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.
`Patproc is a procedure associated with every pattern (its member function) that handles events for
`it. This approach to handling events is 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 patternsby 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 look like:
`
`ROLI ND'ROEW
`
`Highesl Pflorlty Patlerns
`
`"
`
`RDU ND ROBIN
`
`Lowest Priority Psllsrns
`
`U.
`
`mu'0M'n
`RO
`IJ
`
`Es;WI:D
`
`events
`
`4 .
`
`N
`
`1‘
`
`smurf;Padres;
`
`Our prototype does not currently implement the priority structure of dispatching events to patterns.
`It treats every pattern to be of the same priority.
`
`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 on its 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 shown in figure 2.
`It shows how two event streams, namely IP datagrams and 02 audit records can be used together.
`IP_EVEI~‘ITS is the root class from which all the events corresponding to IP datagrams can be derived.
`Similarly, 02_EVENTS is the root class for deriving C2 audit record objects. Signatures written to
`match against 1? datagrams are queued in an instance of IP_SERVER, while signatures that match '
`against the audit trail are queued in an instance of CZflSERVER. Class names bounded by dotted '
`boxes are abstract classes. The functions identified within these boxes are the pure virtual functions
`of these classes.
`
`EVENT
`int WPBU
`
`!I
`
`I
`I
`~____.__..
`A
`[samurai
`[answers |
`. ..p. _. in
`n.
`A
`,
`items? Steam?! CEevsnLEXEC. czevenLCHMoD |
`l'"
`i
`
`PATTERN I
`void PatProc(Event ')
`
`__
`
`F'
`
`.
`
`IL...
`
`lumen{02 PITE__Nl
`
`I
`
`|
`
`_
`
`
`
`I
`.._..
`..
`_
`SERVER :
`
`I...
`
`|.
`
`-
`
`A. _
`laser—weal
`I
`I
`_i
`
`
`;__...._.._._:
`
`..
`
`|
`
`lPPATTERN
`
`5
`[cinemas [
`l-__I
`
`C2"PATTERN
`
`I
`
`|
`
`. 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-time efficiency of' the
`detector. For misuse detection using a 02 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 cornpile 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 code realizing the automaton did not need to be “user friendly," we tried to make
`it more eificient 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 based on 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.
`Our design, which is based on the model of 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. That is, 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, ParQO] and dispatch them to patterns.
`Although our current implementation is single host based1 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 under light 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 events1 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 [F391], CERT advisories
`[GER] and the bugtraq and Eilgrn4 electronic mailing lists.
`Figure 1 shows how much time it took to match each signature against an audit file of ap-
`proximate size 400KB5. 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.1?) in the figure represents that
`the detector took 5.173 to create all the event objects and destroy them. The point [1, 5.45) means
`that pattern numbered 1 (numbered. arbitrarily) took 5458 when exercised by the 2514 events.
`
`for prevention and
`their exploitation and steps
`security vulnerabilities,
`‘Both lists discuss computer
`detection.
`Bugtraq is
`issued from bugtraqecrimelabmom and Sign:
`advisories can be retrieved from
`fileseerb-agpuss . demon . co .11k.
`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 and deletion 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
`system.
`
`6
`
`5.8
`
`|
`I
`
`Time 56
`(usr+sys)
`111 sees 54
`
`5.2
`
`5
`
`6
`
`5.8
`
`5.6
`
`Time
`(usr-l—sys)
`in secs 5-4
`
`
`
`5.2
`
`5
`
`U
`
`5
`
`10
`
`15
`
`20
`
`Figure 1: Time for matching each pattern for
`a 400K audit file_
`
`Figure 23 Time for matching multiple
`patterns 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 account is:
`
`variable cost/event/pattern m (5.91 —- 5.17)/(25l4 =1: 19} 2 1511s
`
`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.
`Censider 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 6MB per hour. This is about 2514 x 6/.4 2 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:
`II
`Fixed overhead
`Variable overhead
`Total time
`
`5.1172514 x 380003 = 78.155
`15113 x 100 X 33000 = 573
`= 135.155
`
`II
`
`the detector requires m 1353 to match about 100
`Thus, for every hOur of intense activity,
`patterns. This fraction is 135/3600 x 100 : 3.75% m 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; Implementing this 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 190 signaturessimultaneously
`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 Atknowledgements
`
`We would like to thank all members of the COAST laboratory for their valuable comments on this
`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 BOB contract
`MDA904-93—CH4081:
`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. Birreil and Bruce Jay Nelson. Iniplementing Remote Procedure Calls. ACM
`Transactions on Computer Systems, 2(1):39—-59, February 1984.
`
`[GER] CERT Advisories. Available by anonymous ftp from cert.sei.cmu.edu:fpub/cerLadvi-
`sories.
`
`[CWSQ] David D. Clark and David A. Wilson. Evolution of a. Model for Computer Integrity.
`Report of the Invitational Workshop on Data Integrity, September 1989.
`
`[F0182] Charles L. Porgy. RETE: A Fast Algorithm for the Many Pattern/Many Object Pattern
`Match Problem. In Artificiei Inteiligenee, volume 19. 1982.
`'
`
`[F891] Daniel Farmer and Eugene Spafi'ord. 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 ofthe ACM, 17(10):549—557, 1974.
`
`[Ilg92] Koral Ilgun. 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 1'. Springer Verlag, 1992.
`
`203
`
`
`
`
`
`[K894a] Sandeep Kumar and Eugene Spafi'ord. A Taxonomy of Common Computer Security
`Vulnerabilities based on their Method of Detection. (unpublished), June 1994.
`
`[K894b] Sandeep Kumar and Eugene H. Spafforcl. A Pattern Matching Model for Misuse In-
`trusion Detection. In Proceedings of the 17th. Nationat Computer Security Conference,
`. pages 11—21, October 1994.
`
`[KquS] Sandecp 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«
`preach. In USENIX 19.90 C++ Conference Proceedings, pages 37—50, 1990.
`
`[Pct92] Charles Petzold. Programming Windows 3.1. Microsoft Press, 1992.
`
`[PK921 Phillip A. Porras and Richard A. Kemmerer. Penetration State Transition Analysis —
`A Rule-Based Intrusion Detection Approach. In Eighth Annual Computer Secur