Pp. 63–78 of the Proceedings

Synthesizing Fast Intrusion Prevention/Detection Systems from High-Level Specifications¹

R. Sekar P. Uppuluri
State University of New York at Stony Brook, NY 11794.
{sekar,prem}@cs.sunysb.edu

Introduction

Our increasing reliance on networked information systems to support critical infrastructures (e.g, telecommunication, commerce and banking, power distribution, and transportation) has prompted interest in making the information systems survivable, so that they continue to perform their primary functions even in the face of coordinated attacks. In order to build survivable systems, it is necessary to detect and isolate attacks before they impact system performance or functionality. Thus a number of recent research efforts have focussed on the problem of intrusion prevention [GWTB96,SBS99,CPMWBBGWZ98,MLO97,FBF99].

Many known approaches for intrusion prevention (including the one described in this paper) are based on the following observation about attacks: regardless of the nature of an attack, damage can ultimately be caused only via system calls made by processes running on the attacked host. It is hence possible to prevent damage due to attacks if we can monitor every system call made by every process, and prevent damage-causing calls from being executed. Actions to contain or respond to the attack could be launched at this point, e.g., terminating the process. Some of the central problems in the context of these approaches are:

• efficient interception of system calls
• pattern languages to characterize normal/abnormal system call sequences for any given program/process
• efficient matching of actual system calls made by a process against such patterns
  

   
Summary of Results

• In Section 2 we present a new and expressive language for capturing patterns of normal or abnormal behaviors of processes in terms of sequences of system calls and their arguments. As compared to the language described in [SCS98,SBS99], this paper focuses on a core language that we call regular expressions for events (REE). REEs extend regular expressions to model system calls that are characterized by a name as well as argument values. Response actions can be associated with patterns, and these will be launched automatically when our system observes a match for the pattern.
• In Section 3 we illustrate our language with several simple examples. We then detail the process of developing a complete specification for the ftpd server. This example, together with similar specifications for httpd and telnetd forms the basis of our experimental results in later sections.
• REE have much higher expressive power than regular expressions. The presence of variables makes them comparable to attribute grammars in terms of expressive power. The examples in Section 3 illustrate that in practice, REE language provides the capabilities needed to describe program behavior as needed for intrusion detection or prevention.
• In Section 4 we present our runtime model for fast pattern-matching, based on extended finite-state machines (EFSA). Just as REE's extend the power of regular expressions to permit variables, EFSA extend traditional finite-state automata to be able to assign or examine values of a finite set of variables. As in the case of regular expressions, every REE can be matched by a non-deterministic EFSA (NEFA) whose size is linear in the size of REE. But simulation of a NEFA at runtime can be very inefficient. We then examine the properties of deterministic EFSA (DEFA) which can be simulated efficiently. However, we show that the size of deterministic EFSA can be far too large (super-exponential in the size of NEFA) for the approach of using DEFA to be viable.
• Ideally, we would like an approach that achieves a balance between the space explosion implied by DEFA with the runtime inefficiency imposed by NEFA. We propose an algorithm to accomplish this in Section 5. Given an REE of size N, our algorithm produces an EFSA with a worst-case size that is O(2^N). We show that this EFSA is deterministic for a subclass of REE's called REE(0) patterns.
• We present an implementation of our techniques in Section 6 and report its performance. In practice, our algorithm uses much less than exponential amount of space. This means that we can perform intrusion prevention/detection in essentially constant time per system call for most patterns. Our current implementation introduces about 1 to 2% overhead due to the pattern-matching operations.

   
Approach Overview

  

Figure 1: System Model

Our intrusion detection/prevention system consists of an offline and a runtime component. The offline system generates detection engines from specifications, while the runtime system provides the execution environment for these engines. The input to the offline component is a specification S_P for each program P to be defended². The offline component translates S_P into a C++ class definition C_P. This C++ class simulates an extended finite state machine for matching the patterns in S_P and initiating appropriate responses to intrusion attempts. This code is compiled and then linked with a runtime infrastructure to produce a detection engine.

Figure 1 shows the runtime operation of our system. When Pexecutes as process P_j, it is monitored using the detection engine M_j, which incorporates an instance of C_P. System calls made by P_jare intercepted by the system call interceptor just before, and just after the system call's kernel level functionality is executed, and the system call information is passed to M_j. If M_j matches a pattern, it invokes the action associated in S_P with that pattern. This action would typically utilize the support functions provided by the runtime system to modify the just-initiated system call execution so as to prevent it from causing damage.

The fork system call is given special treatment. When process P_jexecutes a fork system call, it results in two processes P_j and P_j'. At this point, the detection engine monitoring P_j also clones itself, with one instance monitoring P_j and another monitoring P_j'. If one of these processes, say P_j', executes another program using the execve system call, we may switch to monitoring the new program with respect to a new specification as described later.

Frequently, security specifications for a process are completely independent of the actions of other processes. However, some specifications concern interactions among multiple processes. To monitor the behavior of concurrent processes, we use a coordinating monitor that communicates with the monitors for different processes to identify deviant behaviors. We express specification of process interaction using a language construct called an atomic sequence, described later. The coordinating monitor is used to detect violations of atomic sequences. While we describe the atomic sequence construct and discuss a possible implementation to support it, we have not yet implemented it. As such, we do not provide experimental results regarding this construct.

Specification Language

Event Patterns

We define a special event begin which precedes any system call made by any process, and the event pattern any that stands for any event.

Sequencing operators are similar to those used in regular expressions, but operate on events with arguments. We refer to our pattern language as regular expressions over events (REE) to indicate this relationship. Elementary patterns in our language are of the form e(x₁,..., x_n)| cond, where cond is a boolean-valued expression on the event arguments x₁,..., x_n, any temporary variables that may appear earlier in a pattern, and state variables. The condition component can make use of standard arithmetic, comparison and logical operations and several support functions. The support functions allowed in a pattern correspond to ``read'' operations that do not modify the state of the monitored process. An example of such a function is realpath() which translates a file name into a canonical form that does not contain ``.'', ``..'', or symbolic links.

The meaning of event patterns and the sequencing operators is best explained by the following definition of what it means for an event history to match a pattern:

• event occurrence: e(x₁,..., x_n)| cond is satisfied by the event history e(v₁,..., v_n) if cond evaluates to true when variables x₁,..., x_n are replaced by the values v₁,..., v_n.
• event nonoccurrence: !e(x₁,..., x_n)| cond is matched by H if it does not match e(x₁,..., x_n)| cond.
• sequencing: pat₁;pat₂ is satisfied by an event history H of the form H₁H₂ provided H₁ satisfies pat₁ and H₂ satisfies pat₂.
• alternation: pat₁|| pat₂ is satisfied by an event history H if either pat₁ or pat₂ is satisfied by H.
• repetition: pat* is satisfied by an event history H₁H₂ ^... H_n iff H_i satisfies pat,  1in.
• realtime constraints: is satisfied by an event history H₁ if H₁ satisfies pat and the time interval between the first and last events in H₁ is less than or equal to t.
• atomicity: nonatomic d in pat denotes that accesses to data d be atomic in pat, i.e., without any intervening operations by other processes that could modify this data.

We relax the definition of the sequencing operators to minimize the need to include both entry and exit events in a pattern. For instance, when two system call entry events occur in sequence, we implicitly insert an exit event in the middle, e.g., (open| C₁);(close| C₂)is treated as equivalent to (open| C₁);open;(close| C₂). If the first event is an entry event while the second is an exit event for a different system call, then an exit event for the first call and the entry event for the second call are implicitly added, e.g., (open| C₁);(close| C₂) is treated as equivalent to (open| C₁);open;close;(close| C₂).

The value of a temporary variable should be defined before its first use via a binding that takes the form tvar = expr. Note that binding differs from assignment in that there can be at most one binding to any temporary variable, as subsequent conditions of the form tvar = expr are treated as comparisons.

Response Actions

A typical response is to prevent a system call from executing and/or return a fake return value. This is accomplished using a support function fail, which takes an argument that corresponds to the value to which the variable errno should be set to. Sometimes, it is necessary (or just convenient) to switch to a new specification using the support function switch(f ), where f is the name of the new specification.

If multiple patterns match at the same time, all of the associated actions are launched. This leads to a problem when some of these actions conflict with each other. It is possible to address such interactions by (a) defining a notion of conflict among operations contained in the reaction components of rules, whether they be assignments to variables or invocation of support functions provided by the runtime system, and (b) by stipulating that there must not exist two patterns with conflicting operations such that for some sequence of system calls, they can match at the same point. Potential conflicts can be identified by the automaton construction algorithms developed in this paper -- if there is any state in the automaton that corresponds to a final state for two such patterns, then there is a potential conflict. However, we have not implemented this approach yet, instead relying on the specification writer to deal with such conflicts.

    
Example Specifications

Simple Examples

execve|| connect|| chmod|| chown||
creat|| truncate|| sendto|| mkdir
fail (EINVAL)

We may also wish to restrict the files accessed for reading or writing. For a program such as fingerd, we may use the following rule to prevent the program from writing any file, and reading any files other than those mentioned in admFiles defined below.

admFiles = {"/etc/utmp",
 *0.5in"/etc/passwd", datadir/*}
open(f, mode)|(realpath(f ) admFiles
||  (modeO)
fail (EPERM);

To illustrate the use of sequencing operators, consider the following pattern that asserts that a program never opens and closes a file without reading or writing into it. Before defining the pattern, we define abstract events that denote the occurrence of one of many events. Occurrence of an abstract event in a pattern is replaced by its definition, after substitution of parameter names, and renaming of variables that occur only on the right-hand side of the abstract event definition so that the names are unique.

openExit(fd ): : =
open(f, fl, m, fd )|| creat(f, m, fd )
rwOp(fd ): : = read (fd )|| readdir(fd )|| write(fd )
openExit(fd );(!rwOp(fd ))*;close(fd ) ^...

Although regular expressions are not expressive enough to capture balanced parenthesis, the presence of variables in REE enables us capture the close system call matching an open. This issue of expressive power is discussed again later.

The example below illustrates the use of atomic sequence patterns. A popular attack uses race conditions in setuid programs as follows. Since the setuid process runs with effective user root, any open operation by the process will always succeed. If the process is running on behalf of a user, and wishes to open a file with the permissions of this user (i.e., with privileges corresponding to the real userid), it may do so by first using the access system call which determines if the real user has access to a file, and if so, it goes ahead and opens the file. The attacker exploits the time window between the access and open system calls as follows. The attacker uses a symbolic link as the name of the file in question, and changes the target of the link between the access and open system calls. To prevent this attack, we ensure that the object referred by the access and open system calls is accessed atomically:

nonatomic(f.target) in
(access(f );(!open(f ))*;open(f ))
fail (EACCES);

Case Study: Specification for ftpd

  

Figure 2: A specification for ftpd.

Our starting point in developing a specification of ftpd is the documentation provided in its manual pages. Specifically, we identified the following properties for wu-ftpd by examining its manual page and based on our knowledge of UNIX. These properties are captured in our specification language in Figure 2. Although it is possible to turn the English descriptions directly into specifications in our language, it is usually necessary to cross-check (or ``debug'') the specifications by monitoring ftpd under typical conditions. We have therefore used a hybrid approach, where we first manually inspected system call traces produced by ftpd, and used it to further narrow down the actions/behaviors that the ftpd server may exhibit. In most cases, we have not attempted a sophisticated response, instead opting for a simple action such as terminating the process using a support function named term().

• ftpd attempts to authenticate a client host before proceeding to user authentication phase. Precisely identifying the sequence of system calls that correspond to client authentication is hard, as it involves a large number of steps that may vary from installation to installation. As such, we treat getpeername as a marker that indicates host authentication related processing. Similarly, we treat opening of /etc/passwd as a marker for user authentication related processing. Rule 13 captures this English description by stipulating that an open of the password file should never happen before invocation of getpeername.
• users need to be first logged in before most files can be accessed. Rule 14 uses setreuid as an indicator for completion of user login process.
• after user authentication is completed, ftpd sets the userid to that of the user that just logged in. We remember this userid for later use (rule 11).
• prior to user authentication, only files beginning with names identified in the set ftpAdmFilePrefixes can be accessed (rule 15).
• certain system calls are never used before user login, and certain others are never used after login process (rules 16, 17). Let ftpInitBadCall denote a pattern that matches system calls not used prior to user login. Similarly, let ftpAccessBadCall match system calls that are not used after login⁴.
• for anonymous login, the userid FTPUSERID is used; moreover, the chroot system call is used to restrict access only to the subtree of the filesystem rooted at ~ftp (rule 18).
• ftpd resets its effective userid to root in order to bind certain sockets to ports numbered below 1024. The userid is reverted back to that of the logged in user immediately afterwards (rule 20).
• to eliminate possible security loopholes, ftpd must execute a setuid system call to change its real, effective and saved userid permanently to that of the logged in user before executing any other program; otherwise, the executed process may be able to revert its effective userid back to that of superuser (rule 19). In addition, we make sure that any file that is opened with superuser privilege is closed before exec (rule 21).
• finally, we model certain site-specific policies that override any access policies configured into ftpd. These policies are captured by rules 22 through 25.

Discussion

• In order to reduce clutter, we have deliberately abbreviated some of the lists (e.g., ftpInvalidUsers), while leaving out definitions of some abstract events (e.g., wrOpen) in the specification for ftpd.
• Typical specifications need not be as comprehensive as for ftpd - we have made it comprehensive in order to better illustrate what sorts of properties can be captured in our language.
• The specification was developed using the principle of least privilege, without really paying attention to known vulnerabilities. Nevertheless, it does address most known ftp vulnerabilities (many of which have since been fixed) such as FTP bounce (rule 25), race conditions in signal handling (rules 20, 19) and site-exec (rule 24) [CERT].
• Availability of fast matching algorithms described in the subsequent sections enables us to focus on developing these rules independent of each other, as opposed to worrying about how they may be modified to enable more optimal checking, e.g., rules 11, 15, 16, and 23 have prefixes in their pattern component that are similar, and we can in fact combine them into a single rule. But this will lead to a specification that is much less clear, so we avoid this. Since the matching algorithms give us the benefit of such combination for free, there is no cost to pay for the clarity of specifications.
• We can develop a more concise language that gives us the ability to specify dependencies among events e₁ and e₂ more directly, rather than using a pattern such as begin();(!e₁)*;e₂. However, the focus here is on a core language that has the necessary expressive power.
• The examples illustrate that the expressive power of REE is far beyond that of regular expressions. For instance, rules 20 and 21 capture associations among events that are beyond what can be captured even by context-free grammars. (The associations are similar to checking that a variable is defined before use, and can be captured by attribute grammars.)

   
Runtime Model

An EFSA is normally nondeterministic. The notion of acceptance by a nondeterministic EFSA (abbreviated as NEFA) is similar to that of an NFA: a NEFA accepts an event history e₁e₂ ^... e_n if there is a sequence of states s₀, s₁,...s_n such that s₀ is the start state, s_n is a final state, and  1 i n, there exists a transition from s_{i - 1} to s_i that can be taken on e_i. A deterministic EFSA (DEFA for short) is an EFSA in which at most one of the transitions is enabled in any state of the EFSA. A NEFA for the pattern a(x);b*;b(x) is shown in Figure 3. The equivalent DEFA is also shown in the same figure.

  

Figure 3: A NEFA and its equivalent DEFA

• there exists a NEFA of size N corresponding to the REE and it uses state variables X₁,..., X_k
• this NEFA can be simulated with at most O(N*n₁*n₂* ^... *n_k) cost per event at runtime
• every NEFA can be transformed into an equivalent DEFA with the same set of state variables
• in the worst-case, the smallest DEFA for the above REE will have 2^{N*n₁*n₂* ... *n_k} states

The algorithm uses a hash table to store all of the possible states in which the NEFA could be in. On receipt of an event, we compute the new states of the NEFA by making a transition from each of the current states. A state of the NEFA is represented by a tuple (c, v₁,..., v_n) where c denotes the control state of the NEFA and v₁,..., v_n denote the values of the state variables. The algorithm uses a function epsilon to compute the set of states reachable from a state S while only following -transitions.

We remark that our NEFA model has some similarities with the colored Petrinet model used in [Kumar95]. In particular, the notion of a token in their Petrinet corresponds to our notion of a NEFA state. Their semantics of matching differs from ours in some ways, and as a result, their algorithm for simulating a nondeterministic Petrinet results in cloning of tokens at each step of the simulation algorithm. This can result in unbounded increase in the number of tokens, whereas the number of distinct states of the NEFA is bounded as discussed above.

   
Translation of REE to NEFA

Translation Algorithm

• strip the leading begin from patterns; if a pattern does not start with a begin, prefix any*, so that the augmented pattern will match an event history iff the original pattern matched a suffix of the history.
• introduce an end-marker # to every pattern, and then combine them into one pattern using ||.
• express realtime or atomicity using *,;,|| and constraints on argument values
• rename event arguments so that ith argument to any event is named $i. For arguments that need to be remembered for later, we assign their values to state variables using notation /t_j = $i. A pattern that does not use a state variable after this step is known as an REE(0) pattern.
• number the positions in the REE from left to right, indicating the positions as superscripts

(a¹|$1 = $2)/t₁ : = $1;(a²| b³)*;b⁴/$1 = t₁;#⁵    || (a⁶|$2 = 3|| c⁷)/t₂ : = $1;(a⁸|| c⁹)*;c¹⁰|$1 = t₂;#¹¹

The purpose of numbering the REE positions is similar to that of earlier algorithms for constructing DFA from regular expressions [Aho90,MY60]. Each state S in the NEFA is associated with a subset P_S of positions in the REE as follows: a position p P_S iff there is a path from the start state of the NEFA to S that matches the prefix of the REE up to position p. Intuitively, P_Sdenotes that set of positions in the REE up to which we may have matched an input event history that took the NEFA from its start state to the state S.

The construction of the NEFA for an REE R begins with the start state S₀. The positions P_S0 associated with the start state is defined as first(R), where first is the function defined below.

first(e| C)	=	{pos(e| C)}
first(A;B)	=	first(A) first(B) *.1in if empty(A)
first(A;B)	=	first(A) *0.78in otherwise
first(A| B)	=	first(A) first(B)
first(A*)	=	first(A)

The next step in construction is to identify the distinct events e₁,..., e_m that occur at one of the positions in P_S. We create m transitions from S to dummy states as shown with dotted lines in Figure 4. The set of positions P_Siassociated with each of these dummy states is given by:

P_Si = {j P_S| e_i occurs at j in R}

  

Figure 4: Partially constructed NEFA

  

Figure 5: NEFA (also a DEFA) for the example patterns

P_Si1 = {j P_Si| C_j C_kfalse}
P_Si2 = {j P_Si| C_j C_kfalse}

When we reach a dummy state S_d where all conditions have been tested, we are ready to create new (non-dummy) states. Let A₁,..., A_r be the distinct assignment actions among the positions P_Sd. Then we create a total of r states S'₁,..., S'_r, with -transitions from S_d to S'_k labeled with assignment actions A_n, for 1 n r. P_S'k is determined as follows. Let P_k denote the subset of P_Sd where assignment actions A_k appear. Then P_S'k = follow(p), where follow is defined by:

follow(p) 
first(Q), if p is rightmost for 
										a subexpression Q* in R  


follow(p) 
first(Q), if p is rightmost
										within Q' where Q';Q is in R  


follow(p) 
follow(q), if p and q are rightmost
										 in Q and Q', where Q|| Q' is in R,
										 or Q;Q' is in R and empty(Q')  

After the above algorithm, a post-processing phase merges sequences of dummy transitions into a single one, eliminating the dummy states in the process. It also marks any state that includes an end-marker position as a final state for the corresponding pattern. The NEFA constructed by the algorithm for our example is shown in Figure 5.

Properties of NEFA

Matching REE(0) Patterns

Size

To get an idea of the size of the NEFA, one has to consider the states as well as the space required for storing the transitions. If maxp denotes the maximum number of positions where the same event occurs in an REE, then we can show that the total space requirements for the states and transitions is bounded by O(2^{n + maxp}).

We note that as in the case of the DFA construction algorithm from [Aho90], the worst case space requirements do not reflect the space usage in practice. Often, as in the case of the above example and in the examples studied Section 6.3, we end up with an automaton whose size is much smaller than the exponential upper bound.

   
Implementation and Performance

Compiler

The front-end of the compiler is responsible for parsing a specification. Its implementation is routine, based on standard compiler construction tools Flex and Bison. Type-checking is performed subsequently, and then we translate the pattern components of our specifications into a NEFA using the algorithm described in the previous section. The reaction components of the rules are attached to those states that accept the pattern corresponding to the respective rules.

The NEFA is then translated into a C++ class NEFA as follows. At runtime, the state of the NEFA is maintained in a structure called FSM, which stores the control state as well as the state variables. To support nondeterminism, multiple instances of an FSM can be created using a clone function that makes identical copies of an FSM. At any point during runtime, zero, one or more copies of the FSM may be active.

The transitions of the NEFA are captured in the C++ code as follows. A system call sc is delivered to the NEFA class by invocation of a member function on the NEFA class with the name sc. The code for this class sequences through the list of FSM's that are currently active. For each FSM, its state is updated to reflect a transition that it would have made on the event sc and its arguments. If multiple transitions are possible, suitable number of copies of the FSM are made and each copy follows one of the transitions.

Runtime System

The output code produced by the compiler is linked with a runtime support system that provides the infrastructure for intercepting and delivering system calls to the detection engine. Events are delivered by invoking the corresponding member functions on the NEFA class described above. The runtime system also provides the functions needed by the detection engine to alter the behavior of system calls. With regard to data access, it provides support functions to access system call argument values.

The runtime system has been implemented by modifying the system call interface within the operating system. We do not provide a detailed explanation of the runtime system here, as our focus in this paper is on efficient runtime matching operations. Our results indicate that the overhead for interception is more or less constant per system call, and adds about 30% overhead to the cost of a system call [Bow99]. However, since system calls account for only a small fraction of the CPU time used by an application, the increase in CPU time (counted as the sum of user and system time on UNIX) is in the range of 2% to 30%. Most applications, especially those that are CPU-intensive, impose overheads at the bottom of this range, while I/O intensive applications such as tar and ftp lead to higher overheads. [FBF99], which employs an interception mechanism similar to ours, reports overheads in the range of 2% to 4% for a different set of applications, namely, gcc and httpd.

We remark that the overheads for system call interception are nontrivial. In fact, our fast matching algorithm reduces the checking time to the point where system call interception accounts for the the dominant portion of the total overhead imposed by our approach. In particular, this implies that there is no penalty to be paid due to the use of sophisticated pattern-matching based approach such as ours over a method that uses simpler rules that are triggered on individual system calls.

   
Performance Results

Timing Results

  

Figure: Overhead due to system call pattern matching. Results taken on 350MHz Pentium II Linux PC with 128MB memory and 8GB EIDE disk.

Figure 6 summarizes our experimental results. They show that in fact, the overheads due to the monitoring are almost imperceptible for all three applications. The runtime data storage requirements for the FSM are too small to be measured.

Figure 7 shows the overhead for matching each system call, averaged across the three programs. The graph indicates a slight increase with increase in number of system calls, which is to be expected due to the presence of non-REE(0) rules. However, the rate of increase is extremely small, at about 5% when the number of system calls has increased by about 2000%. Thus, it is meaningful to talk about overhead as a percentage of the total runtime, as was done in Table 6. To obtain the results in the table and the figure, we exercised the three programs with a random combinations of valid commands of different lengths.

  

Figure 7: Matching time per system call (in microseconds).

  

Figure 8: Increase in automaton size with specification size.

Automaton Size

Although the worst-case size is exponential in the size of REE, we find that in practice, the size increases more or less linearly with the total REE size. Although it is not readily apparent from the graph, the rate of increase in number of states tended to decrease after a while in our examples. The reason for this is that existing patterns had already created many states that could already represent some of the stages of matching the new pattern, and thus only fewer additional states were required. However, we must exercise caution in generalizing from these three programs, as the relationship between pattern size and automaton size can vary greatly from one set of patterns to another.

   
Related Work

Intrusion Detection

Among misuse-based approaches, a state-transition diagram based approach is used in [PK92] to capture signatures of intrusions. [Kumar95] uses colored petri nets to specify intrusive activity. This language is more expressive than ours in some ways (e.g., ability to capture occurrence of two concurrent sequences of actions), and less expressive in some other ways (e.g., ability to capture atomic sequences or the occurrence of one event immediately following another). Nevertheless, most intrusion signatures expressed in [Kumar95] can be easily captured in our language as well and hence our compilation techniques are applicable to their approach.

Among anomaly detection approaches, one of the first works based on program behaviors (as opposed to user behaviors) was that of [FHS97]. Recently, these results have been improved by [GSS99] using a neural network based approach that produces very accurate anomaly detectors. All these approaches deal only with system call names, not with arguments. This simplifies the problem of learning normal behaviors of processes, which is the main focus of their work. However, for intrusion prevention or confinement, argument values are indeed important, e.g., we cannot otherwise distinguish an action to write a log file from one to modify the /etc/passwd file. Thus a language like REE is more appropriate in this context.

A specification-based approach achieves the accuracy of misuse detection, while addressing one of its deficiencies, namely, the inability to deal with unknown intrusions. It was first proposed in [Ko96]. They use a pattern language based on context-free grammars extended with variables, and formulate the intrusion detection problem as one of parsing the audit logs with respect to these grammars. In contrast, our language is based on an extension of regular languages with variables. While context-free languages are more expressive than regular languages, this is not necessarily true when variables have been added to these languages. On the other hand, a regular language based formulation lends itself more readily to an automaton based pattern-matching approach that can be implemented efficiently.

Preventive Approaches

Some of the preventive approaches are based on protecting systems against underlying software errors that are exploited by attackers. For instance, malicious code detection techniques [BD96,GM96,LLO95] employ program analysis techniques to detect security-related errors in the source code. Similarly, [CPMWBBGWZ98] developed compilation techniques that add additional checks into the code generated to identify (and prevent) attacks that exploit buffer overflows to overwrite the return addresses stored on a process stack.

Interception of system calls, followed by interposition of arbitrary code at this point, has been proposed by many researchers as a way to confine applications. The Janus system [GWTB96] incorporates a user-level implementation of system call interception. It is aimed at confining helper applications (such as those launched by web-browsers) so that they are restricted in their use of system calls. Their language is tailored to restrict individual system calls without any regard for the context in which they appear. This approach is well-suited for fine-grained access control and sandboxing. The kernel hypervisor [MLO97] approach is similar to the Janus approach, but is implemented within an operating system kernel using loadable modules. A more comprehensive set of system call interposition capabilities was developed in [GPRA98]. Their approach is geared for a broad range of applications aimed at augmenting software functionality in areas such as security and fault-tolerance. [FBF99] focuses on the related problem of developing languages customized for writing interposition code (also known as wrapper code), and runtime infrastructure for their installation and management. Unlike the preceding approaches, their language can more easily capture sequencing relationships among system calls. But they do not focus on pattern-based techniques for intrusion detection. Moreover, computational issues in efficient matching of system call sequences are not addressed.

Other Work

Regular languages and -regular languages, together with their automata-equivalents, have been used widely in formal specification and verification of concurrent systems [Kurshan94]. In the related area of program analysis, [OO90] develops an approach for expressing sequencing constraints as regular expressions, and compile-time checking of these constraints using dataflow analysis. [Schneider98] proposes to use Buchi automata for monitoring security properties of programs. The main difference between these works and ours is that they operate on regular or -regular languages, while our language is REE. Another difference is that in the context of verification, we are often interested in properties of infinite sequences, while our interest is in behaviors that manifest themselves in finite sequences.

Describing properties of event sequences is an important problem in building, prototyping, debugging and monitoring distributed systems. Languages such as CSP [Hoare78], LOTOS [BB89] and Esterel [BCG87] support very simple patterns, permitting no sequencing or closure operators. The task sequencing language developed in [LHMBH87] and its successor Rapide [LV95] support an expressive pattern language that is significantly more expressive than ours. Moreover, they support a partially ordered set model of event histories, whereas our current model is a linear sequence. However, it is not clear whether this language is amenable to efficient pattern matching at runtime, as they do not address the problem of automata-based techniques for efficient matching of these patterns.

   
Conclusions

One of the main challenges in making our approach practical is the ability to perform runtime prevention/detection that is fast enough to be included as part of processing every system call made by every process. We proposed a solution to this problem in this paper by developing an algorithm that compiles patterns in our specification language into an extended finite state automaton (EFSA). Our implementation results demonstrate that detection can be performed very fast (1 to 2% overhead to program execution time) using our approach. A key benefit of our approach (supported by theory as well as performance experiments) is that the detection time is insensitive to the complexity or number of patterns used in the specification. In most cases, our algorithm takes a constant time per system call intercepted, and uses a constant amount of storage. These advantages make our algorithm attractive for any other approach that performs intrusion detection by some form of pattern-matching.

We showed that for a class of patterns (specifically, REE(0) patterns) the automata constructed by our algorithm are deterministic. A more precise characterization is desirable, since in practice, our algorithm builds deterministic automata for a much larger class of patterns. Such a characterization may also enable us to restrict the specification language so that patterns that can lead to very large overheads (associated with simulating a large number of NEFA instances at runtime) can be avoided. Another area of future research is the application of techniques presented in this paper to the larger problems of distributed system monitoring and software debugging.

Bibliography

Aho90

A.V. Aho, Algorithms for Finding Patterns in Strings, Handbook of Theoretical Computer Science Vol A, Elsevier Science Publishers B.V., 1990.

AWK88

A.V. Aho, B.W. Kernighan, and P.J. Weinberger, The AWK Programming Language, Addison-Wesley, Reading, MA, 1988.

ALJTV95

D. Anderson, T. Lunt, H. Javitz, A. Tamaru, and A. Valdes, Next-generation Intrusion Detection Expert System (NIDES): A Summary, SRI-CSL-95-07, SRI International, 1995.

BCG87

G. Berry, P. Couronne and G. Gonthier, Synchronous Programming of Reactive Systems: An Introduction to Esterel, Technical Report 647, INRIA, Paris, 1987.

BD96

M. Bishop, M. Dilger, Checking for Race Conditions in File Access. Computing Systems 9(2), 1996, pp. 131-152.

BB89

T. Bolognesi and E. Brinksma, Introduction to the ISO Specification Language LOTOS, The Formal Description Technique LOTOS. Amsterdam: North-Holland, 1989.

Bow99

T. Bowen et al, Operating System Support for Application-Specific Security, under review for Symposium on Operating Systems Principles, 1999.

CERT

CERT Coordination Center Advisories 1988-1998, https://www.cert.org/advisories/index.html.

CPMWBBGWZ98

C. Cowan, C. Pu, D. Maier, J. Walpole, P. Bakke, S. Beattie, A. Grier, P. Wagle and Q. Zhang, StackGuard: Automatic Adaptive Detection and Prevention of Buffer-Overflow Attacks, 7th USENIX Security Symposium, 1998.

Denning87

D. Denning, An Intrusion Detection Model, IEEE Trans. on Software Engineering, Feb 1987.

FHS97

S. Forrest, S. Hofmeyr and A. Somayaji, Computer Immunology, Comm. of ACM 40(10), 1997.

FHRS90

K. Fox, R. Henning, J. Reed and R. Simonian, A Neural Network Approach Towards Intrusion Detection, National Computer Security Conference, 1990.

FBF99

T. Fraser, L. Badger, M. Feldman, Hardening COTS software with Generic Software Wrappers, IEEE Symposium on Security and Privacy, 1999.

GPRA98

D. Ghormley, D. Petrou, S. Rodrigues, and T. Anderson, SLIC: An Extensibility System for Commodity Operating Systems, USENIX Annual Technical Conference, 1998.

GM96

B. Guha and B. Mukherjee, Network Security via Reverse Engineering of TCP Code: Vulnerability Analysis and Proposed Solutions, Proc. of the IEEE Infocom, March 1996.

GSS99

A.K. Ghosh, A. Schwartzbard and M. Schatz, Learning Program Behavior Profiles for Intrusion Detection, 1st USENIX Workshop on Intrusion Detection and Network Monitoring, 1999.

GWTB96

I. Goldberg, D. Wagner, R. Thomas, and E. Brewer, A Secure Environment for Untrusted Helper Applications, USENIX Security Symposium, 1996.

Hoare78

C. Hoare, Communicating Sequential Processes, Comm. of the ACM, 21(8), 1978.

Jones93

M. Jones, Interposition Agents: Transparently Interposing User Code at the System Interface, 14th ACM Symposium on Operating Systems Principles, December 1993

Ko96

C. Ko, Execution Monitoring of Security-Critical Programs in a Distributed System: A Specification-Based Approach, Ph.D. Thesis, Dept. Computer Science, University of California at Davis, 1996.

Kumar95

S.Kumar, Classification and Detection of Computer Intrusions, Ph.D Dissertation, Department of Computer Science, Purdue University, 1995.

Kurshan94

R. Kurshan, Computer Aided Verification of Coordinating Processes: The Automata-Theoretic Approach, Princeton University Press, Princeton, NJ, 1994.

LLO95

R.W. Lo, K.N. Levitt, R.A. Olsson, MCF: a Malicious Code Filter, Computers and Security, Vol.14, No.6, 1995.

LV95

D. Luckham and J. Vera, An Event-Based Architecture Definition Language, IEEE Transactions on Software Engineering, 21(9), 1995.

LHMBH87

D. Luckham, D. Helmbold, S. Meldal, D. Bryan, and M. Haberler, Task Sequencing Language for Specifying Distributed Ada Systems: TSL-1, PARLE: Conf. on Parallel Architectures and Languages, LNCS 259-2, 1987.

Lunt92

T. Lunt et al, A Real-Time Intrusion Detection Expert System (IDES) - Final Report, SRI-CSL-92-05, SRI International, 1992.

MY60

R. McNaughton and H. Yamada, Regular expressions and state graphs for automata, IRE Trans. on Electronic Comput., EC-9(1), 1960.

MLO97

T. Mitchem, R. Lu, R. O'Brien, Using Kernel Hypervisors to Secure Applications, Annual Computer Security Application Conference, December 1997.

OO90

K. Olender and L. Osterweil, Cecil: A Sequencing Constraint Language for Automatic Static Analysis Generation, IEEE Transactions on Software Engineering, 16(3), 1990.

PK92

P. Porras and R. Kemmerer, Penetration State Transition Analysis:A Rule based Intrusion Detection Approach, Eighth Annual Computer Security Applications Conference, 1992.

Schneider98

F. Schneider, Enforceable Security Policies, TR 98-1664, Department of Computer Science, Cornell University, Ithaca, NY, 1998.

SCS98

R. Sekar, Y. Cai and M. Segal, A Specification-Based Approach for Building Survivable Systems, NISSC, October 1998.

SBS99

R. Sekar, T. Bowen and M. Segal, On Preventing Intrusions by Process Behavior Monitoring, USENIX Intrusion Detection Workshop, 1999.

SU99

R. Sekar and P. Uppuluri, Synthesizing Fast Intrusion Prevention/Detection Systems from High-Level Specifications, Technical Report 99-03, Department of Computer Science, Iowa State University, Ames, IA 50014.

About this document ...

This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -no_reuse -no_math -html_version 3.2,math main.tex.

The translation was initiated by R. Sekar on 1999-07-12

Footnotes

... Specifications¹

This research is supported in part by Defense Advanced Research Agency's Information Technology Office (DARPA-ITO) under the Information System Survivability program, under contract number F30602-97-C-0244.

... defended²

This specification may be developed based on known information about P, obtainable from such sources as manual pages, security advisories etc.

... system³

Knowledge about these support functions are not integrated into the specification language, but are declared in header files that can be included in the specification. Due to space constraints, we do not treat these declarations in detail.

... login⁴

We note that it may be hard to obtain a complete list of the system calls in either of these cases.