Pattern-Oriented Intrusion-Detection System and Method

1. Technical Field

The present invention relates generally to intrusion detection for a computer-based system and, more particularly, to a pattern-oriented, intrusion-detection system and method that can be used to analyze privilege and data flows in secure computer systems to detect operational security problems.

2. Background Art

Computer system intrusion typically occurs as a result of either system penetration or operational security problems caused by misuse of access authorization. In principle, access control and authentication mechanisms can provide the penetration resistance necessary to prevent illegitimate access by unauthorized users. However, intrusion resulting from operational security problems can be prevented by neither authentication nor access control since unauthorized access need not be attempted. Instead, this type of intrusion must be detected by after-the-fact analysis of audit trails, that is, by intrusion detection.

Most intrusion-detection methods proposed to date define intrusion patterns as statistical deviations from an activity profile that characterizes the "typical" access behavior of a given subject (i.e., user or process) or group of subjects with respect to a given object (e.g., a file or a directory) or group of objects (see Clyde, A. R., Insider Threat Identification Systems. Proc. of the 10th Ntl. Comp. Sec. Conf., pp. 343-356, Baltimore, Md. (October 1987); Denning, D. E. An Intrusion Detection Model, IEEE Trans. on Software Eng., Vol 13-2, pp. 222-226 (Feb. 1987), Lunt et al., A Protection Real Time Intrusion Detection Expert System. Proc. of the 1988 IEEE Symposium on Sec. and Priv., pp. 59-66 Oakland, Calif. (April 1988); Lunt, T. F., Automated Audit Trail Analysis and Intrusion Detection, Proc. of the 11th Ntl. Comp. Sec. Conf., pp. 65-73, Baltimore, Md. (Oct. 1988); Smaha, S. E., An Intrusion Detection System, Proc. of the 4th Aerospace Comp. Sec. Appln. Conf., pp. 37-44, Orlando, Fla. (December 1988); and Vaccaro, et al., Detection of Anomalous Computer Session Activity Proc. of the 1989 IEEE Symp. on Sec. and Privacy, pp. 280-289, Oakland, Calif. (May 1-3 1989)). Activity profiles attempt to capture statistically the normal access activity of subjects during a given period of system operation. A key advantage of these methods is that intrusion patterns need not be defined explicitly, thereby enabling detection of new, unanticipated intrusion patterns. However, these methods are generally unable to adapt easily to changes of subject behavior; for example, changes legitimately caused by the use of new applications.

A method that adapts intrusion detection to subject behavior is presented in Teng, et al., Adaptive Real-time Anomaly Detection Using Inductively Generated Sequential Patterns, Proc. of the 1990 IEEE Symp. on Res. in Sec. and Privacy pp. 278-284, Oakland, Calif. (May 6-9, 1990). This method uses sequential rules that are dynamically generated and modified by a time-based, inductive engine to define expected user-activity profiles. However, its effectiveness is somewhat limited whenever the intrusion patterns include sequences of events in which both the size of the subject and object sets and the length of the sequence itself vary in time. Both this method and those based on statistical definitions of intrusion patterns are rather insensitive to occurrences of context-dependent intrusions, such as those characterizing covert-channel use or virus propagation. Insensitivity to context-dependent intrusion may lead to failure to detect some intrusion instances and may cause false alarms to be raised. This limitation is shared by all intrusion-detection methods that ignore the meaning and significance of event sequences in defining intrusion patterns.

The present invention provides a pattern-oriented intrusion detection system and method that defines patterns of intrusion based on object privilege and information flow in secure computer systems to detect actual intrusion occurrences. This approach has the advantage of detecting context-dependent intrusions such as those caused by inadvertent execution of foreign programs containing viruses or Trojan Horses and also those caused by unintended use of foreign input data. The present invention can track both information and privilege flows within a system, and has the ability to uniformly define various types of intrusion patterns. Operational security problems can lead to intrusion in secure computer systems. With this approach, explicitly defined types of intrusion patterns due to operational security problems can be detected.

In particular, the present invention provides a system and method for detecting intrusion patterns in a secure computer-based system having a Central Processing Unit and a data storage memory. The present invention has means for inputting access operations and a protection graph into an intrusion detection system. The protection graph includes direct and indirect relations between subjects and objects. Means are provided for generating a new protection graph by applying a set of model rules and generating exception conditions based on a comparison of the new protection graph and a set of intrusion patterns.

The foregoing and other features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings, in which:

FIG. 1 illustrates an environment in which the preferred embodiment of the present invention operates;

FIG. 2 shows a high level block diagram of the pattern-oriented intrusion-detection system of the present invention;

FIG. 3 illustrates a graphical representation of a direct reads/read relation;

FIG. 4 illustrates a graphical representation of a direct write/wrote relation;

FIG. 5 illustrates a graphical representation of a direct is/was controlled-by relation;

FIG. 6 illustrates a graphical representation of a direct drives/drove relation;

FIG. 7 illustrates a graphical representation of an indirect reads/read;

FIG. 8 illustrates a graphical representation of an indirect read given a first sequence of relations;

FIG. 9 illustrates a graphical representation of an indirect read given a second sequence of relations;

FIG. 10 illustrates a graphical representation of an indirect write/wrote;

FIG. 11 illustrates a graphical representation of an indirect write given a first sequence of relations;

FIG. 12 illustrates a graphical representation of an indirect write given a second sequence of relations;

FIG. 13 illustrates a graphical representation of when a subject is/was indirectly controlled by an object;

FIG. 14 illustrates a graphical representation of an indirect is-controlled-by relation given a first sequence of relations;

FIG. 15 illustrates a graphical representation of an indirect is-controlled-by relation given a second sequence of relations;

FIG. 16 illustrates a graphical representation of an indirect drives/drove;

FIG. 17 illustrates a graphical representation of an indirect drives given a first sequence of relations;

FIG. 18 illustrates a graphical representation of an indirect drives given a second sequence of relations;

FIG. 19 illustrates a graphical representation of an indirect drives given a third sequence of relations;

FIG. 20 illustrates a graphical representation of an indirect drives given a fourth sequence of relations;

FIG. 21 illustrates a graphical representation of the addition of a new vertex;

FIG. 22 illustrates a graphical representation of the deactivation of a vertex;

FIG. 23 illustrates a graphical representation of the addition of a new edge;

FIG. 24 illustrates a graphical representation of the deactivation of an edge;

FIG. 25, which consists of FIGS. 25(a) through 25(d), shows an example of detecting the unintended use of a foreign program;

FIG. 26 illustrates a graphical representation of a virus-free set;

FIG. 27 illustrates a graphical representation of a virus-confinement set;

FIG. 28 illustrates a graphical representation of a virus-free next state; and

FIG. 29 illustrates a graphical representation of a virus-confined next state.

FIG. 1 illustrates an environment in which a preferred embodiment of the present invention operates. The preferred embodiment of the present invention operates on a computer platform 104. The computer platform 104 includes certain hardware units 112, including one or more central processing units (CPUs) 116, a random access memory (RAM) 114, and an input/output interface 118. The computer platform 104 includes an operating system 108, and may include microinstruction code 110. An intrusion detection system 105, configured and operated in accordance with the present invention, is operated concurrently with operating system 108. For a general discussion of data security see Denning, Cryptography and Data Security, Addison-Wesley Publishing Co. (1982).

One or more application programs 102 can be executed by computer platform 104. Various peripheral components may be connected to the computer platform 104, such as a terminal 126, a data storage device 130, and a printing device 134.

In a preferred embodiment of the present invention, the computer platform 104 is an International Business Machines AT personal computer. The IBM personal computer is equipped with Secure Xenix.RTM.. Secure Xenix.RTM.includes an audit detection mechanism which was modified with the pattern-intrusion detection model of the present invention.

The intrusion detection system and method of the present invention can best be explained with reference to a pattern-oriented, intrusion-detection "model". Below is a discussion of some of the model's salient properties, and an illustration of two of its applications (detection of unintended use of foreign programs and detection of virus propagation). (Other applications, which help distinguish the use of this model from that of others, includes that of auditing covert storage-channel use (see Shieh, et al., Auditing the Use of Covert Storage Channels in Secure Systems, Proc. of the 1990 IEEE Symp. on Res. in Sec. and Privacy, pp. 285-295, Oakland, Calif. (May 6-9, 1990).

The model presented here is inspired by the use of the Take-Grant model (see Bishop, M., Theft of Information in the Take-Grant Protection Model, Proc. of the Comp. Sec. Fndtn. Workshop, pp. 194-218, Franconia, N.H. (June 1988); Jones et al., A Linear Time Algorithm for Deciding Security, Proc. of the 17th An. Symp. on the Fndtns. of Comp. Sci. (1976); Snyder, L., Formal Models of Capability-Based Protection Systems, IEEE Trans. on Comps., Vol. C-30(3), pp. 172-181 (March 1981); and Snyder, L., Theft and Conspiracy in the Take-Grant protection Model, J. Comp. and System Sci., Vol 23, pp. 333-347 (Dec. 1981)) and the U-KUANG rule-based tool (see Baldwin, R. W., Rule Based Analysis of Computer Security, Technical Report, Mass. Inst. of Tech., (March 1988)) for static analysis of system protection states; e.g., for the static determination of whether a subject can potentially acquire object privileges or data. However, in contrast to the Take-Grant model and the U-KUANG tool, the model of the present invention captures the dynamic flow of object privileges and data, thereby enabling the definition and discovery of specific intrusion patterns in audit trails.

In particular, the present invention helps define patterns of object privilege and data flows that characterize operational security problems in otherwise secure systems. These problems include those caused by (1) the unintended use of foreign programs, (2) the unintended use of foreign input data, (3) the imprudent choice of default privileges, and (4) the use of weak protection mechanisms. However, as is the case with any model that requires explicit definition of intrusion patterns, the present invention detects only intrusions that can be anticipated prior to their occurrence. In general, pattern-oriented intrusion detection is intended to complement, not replace, statistical approaches for intrusion detection.

Operational security problems, such as those caused by imprudent use of object privileges, inadequate setting of name-resolution variables, or execution of foreign programs that may contain Trojan Horse or virus codes, can be eliminated neither by use of access control and authentication mechanisms nor by administrative measures. These problems affect both systems employing discretionary and non-discretionary access controls, and may be caused by both privileged, administrative users and unprivileged, casual users. Four of the many types of operational problems leading to context-dependent intrusions, and which suggest the use of pattern-oriented approach to intrusion detection are described below. The problems are described with reference to the Unix.RTM. operating system. The Unix.RTM. operating system is used only for illustrative purposes, and it should be noted that, similar examples could have been described with reference to other operating systems.

Unintended use of foreign programs is a common operational problem in many Unix.RTM. systems. This problem can be caused by failures to set and reset the environment variables (see Bishop M., Security Problems with the Unix.RTM. Operating System, Tech. Rpt., Dept. of Comp. Sci., Purdue Univ., West Lafayette, Ind., pp.1-28 (1983); Bishop, M., How to Write a Setuid Program, Proc. of the 1987 Winter USENIX, vol. 12, No. 1, pp. 5-11 (1987); and Discolo, A. V., 4.2BSD Unix Security, Tech. Rpt , Dpt. Compt. Sci., U. of Cal. at Santa Barbara, pp. 1-16 (1985)) For example, whenever the Bourne shell sh is used, an environment variable IFS is used to define a list of characters representing word separators for commands. If IFS is set to `o,` then the shell command show (which prints mail messages on the screen) is treated as the command sh with one argument w (since the `o` is treated as a blank). Thus, whenever an unsuspecting user fails to set or reset IFS, another user may set up a file w, which can include command programs under the control of the latter user. Similar problems appear if other environment variables, such as PATII, are not carefully set or reset by users.

Misuse of the environment variables that cause unintended use of foreign programs in example (1) can also cause unintended use of foreign input data. However, more subtle instances of unintended use of foreign data also appear in Unix.RTM. systems. For example, a miscreant user may exploit the fact that directories tmp and /usr/tmp, provide a writable repository for the creation of temporary files by system programs like cc(1). Since these directories must be readable and writable by everyone, a miscreant user is free to remove any or all files saved there and replace them with his own files. cc(1) may take these intermediate files as unintended input and generate (unintended) executable files. The resulting operational problem is that an unsuspecting user may end up using bogus input data and programs with the same effects as those of example (1).

Operating systems, such as Unix.RTM., allow users to define default object privileges. For example, a user may set his default-privilege mask to allow: (1) all privileges for the owner, (2) read-write privileges for a specified group of users, and (3) read privilege for all other users whenever he creates an object. Object privileges can be subsequently modified to accommodate the needs of different sharing patterns. The user editing a sensitive document stored in a file may modify the file's privileges to allow read-only privileges for the group and no-privileges for other users. Suppose, however, that an editor, running with the user identity, creates a new temporary file (which has the default privileges set by the user mask), copies the contents of the original file in it, edits it, destroys the original file, and renames the temporary file with the name of the original file. The unsuspecting user appears now to have granted read access to all other users, perhaps contrary to the wishes of the group members; also, the group members gain inadvertently write access to the document file, perhaps contrary to the unsuspecting user's wishes. In this context, subsequent read access to the document file exercised by other users and write access exercised by the group represents an intrusion. The use of unsafe object-privilege defaults is a very common operational security problem in most (secure) systems.

Compatibility with existing system interfaces requires retention of protection mechanisms visible at a system interface even when these mechanisms are demonstrably weak or unsafe. The setuid/setgid system calls of Unix.RTM. systems, which are intended to help implement protected subsystems (Saltzer, et al., The Protection of Information in Computer Systems. Proc. of the IEEE 63(9):1278-1308 (Sept. 1975)), represent a good example of this requirement. Hypothetically, a secure system would not use such mechanisms within its trusted base but, nevertheless, would retain them for discretionary use by various applications. In such a system, a user may (un)intentionally call a foreign program that creates a setuid file with the user's identity, unbeknownst to the user. The effect of this seemingly innocuous create-file call is that the owner of the foreign program, which would be granted read and write privileges on the file, could copy to, and run programs from, that file under the user's identity. The resulting operational problem, namely the ability of a user to masquerade as another user, cannot be avoided easily because casual users often lack the ability or permission necessary to discover the potential use of setuid like calls by untrusted application code. (Trusted Xenix is the only Unix.RTM.-like system which corrects the above problem by placing the setuid/setgid commands in the trusted path and by allowing only the owner of a file to execute setuid/setgid commands on that file (see Gligor, et al., Design and Implementation of Secure XENIX, IEEE Transactions on Software Engineering, vol. SE-13, No. 2, pp. 208-221 (February 1987); Hecht et al., Unix without the Superuser, 1987 Summer USENIX Conf., Phoenix, Ariz. (Summer 1987)). Additional operational problems caused by the use of the setuid mechanism are described in Bishop, M., "Security Problems with the Unix.RTM. Operating System," Tech. Rpt., Dept. of Comp. Sci., Purdue Univ., West Lafayette, Ind. pp. 1-28 (1983); and Bishop, M., Proc. of the 1987 Winter USENIX 12(1):5-11 (1987).

The above examples show that seemingly innocuous access patterns may, in fact, represent intrusion patterns whenever they appear in the context of specific sets of subjects and objects.

In this section the access patterns that need to be analyzed for intrusion-detection purposes in terms of basic relations and sequences of relations among subjects and objects are characterized. In addition, the notion of access context that helps discriminate between an intrusion and an innocuous access is defined.

The basic subject accesses to objects can be defined as a set of direct and indirect relations among subjects and objects, and divided into two classes of access depending on whether the accesses cause a flow of object data or of privileges. Read and write relations are introduced to capture the flow of an object data. A subject has a direct read relation with every object it reads; at the same time, the subject has an indirect read relation with all subjects and objects that provided input to the write operation on that object. Similarly, a subject has a direct write relation with every object it writes; at the same time, the subject has an indirect write relation with all objects that will be written by other subjects that take input from the subject. Note that, to capture data flow dependencies among subjects and objects, both indirect read and write relations must include specific sequencing of direct read and write relations. For example, if process 1 writes a file before process 2 reads it, process 1 has an indirect write relation with any object written by process 2 and, conversely, process 2 has an indirect read relation with process 1. However, if process 1 writes the file after process 2 reads it, no indirect relation can be established between the two processes. Other indirect write relations exist and are described in Section C.

Two other basic relations, namely controlled-by and drive, are introduced to capture the flow of object privileges. A subject is directly controlled by an object if the subject executes the object, or if the subject receives input from the object. For example, whenever a process executes a Unix.RTM. shell command such as sh and csh, it creates a child process to execute commands read from the objects such as .login and .cshrc. Therefore, this process is controlled by sh or csh and by .login or .cshrc, depending upon which shell it executes and which file it reads. A subject directly drives another subject whenever the former provides a command to the latter. The drive relation differs from the controlled-by relation because the controlled-by relation provides a subject with a sequence of instructions for execution and usually lasts for a period of time, whereas the drive relation is an instantaneous operation that only provides a subject with the command or program to be executed.

A subject is indirectly controlled (1) by another subject, if the latter directly or indirectly wrote the object which directly controls the former, or (2) by another object, if that object provided input to a write operation on the object which directly controls the subject. A given subject is indirectly driven (1) by another subject, if the latter directly or indirectly controls a subject which directly drives the former, or (2) by another object, if that object directly or indirectly controls a subject which directly drives the given subject.

Access contexts are defined in terms of (1) protection sets and (2) their core subsets. A protection set defines the set of all subjects and objects that require protection from intrusion by outside subjects. Object data and privileges are allowed to flow freely within a protection set. The selection of the size of a protection set is left to the latitude of users and administrators, and reflects the intrusion detection requirements of specific applications. For example, an auditor may select a collection of all subjects and objects owned by a user at a given security level, a collection of a group of cooperative processes, or a collection of subjects and objects owned by a group of users working on the same project for a protection set. A core subset is the subset of a protection set in which elements should be always protected from intrusion by subjects from outside the protection set. We distinguish four types of core subsets:

objects, (2) the core (1) the core subset of non-writable subset of non-readable objects and subjects, (3) the core subset of non-controllable subjects, and (4) the core subset of non-drivable subjects. Unless otherwise specified, the elements of the core subsets cannot be directly or indirectly written, read, controlled, and driven by subjects outside of a protection set. If any element of a core subset is accessed by a subject or an object outside of its protection set and the access violates the given restriction (e.g. non-writable) of the core subset, an intrusion occurs.

Protection sets help define the targets of intrusion detection. Core subsets are particularly useful in distinguishing between legitimate activities and intrusions. Sensitive files of Unix.RTM., such as .login, .cshrc, .profile, a user's login directory, system commands, and setuid files, should be included in their owners' core subsets of non-writable objects. Sensitive or privileged subjects, such as superuser's processes, users' login shells, etc., should be included in their owners' core subsets of non-controllable subjects. In addition, all subjects and objects of protected subsystems should be protected from other users (see Saltzer, et al., The Protection of Information in Computer Systems, Proc. of the IEEE, vol 63, No. 9, pp. 1278-1308 (September 1975)). Therefore, all subjects and objects in a protected subsystem should be included in its core subset.

In this section, a succinct definition of the intrusion detection model is provided by formally defining system states, state transitions, direct relations, and rules that establish indirect relations between subjects and objects.

The system states captured in audit trails can be represented by a protection graph. A protection graph has two distinct types of vertices: subjects and objects. Subjects are the active vertices, and can represent processes and users; they can initiate operations and pass information and privileges. Objects, on the other hand, are completely passive; they can represent files, directories, etc., and cannot initiate operations.

A system state Gi is an element of G, where G is the set of protection graphs (PGs): G=V.times.E.times.C.times.K

where V is the set of vertices: V={v1, v2, v3, . . . }=S.orgate.0; E is the set of labeled edges: E={e1 e2, e3, . . . }; C={C1, C2, C3, . . . } and C.sub.i is a protection set, C.sub.i V; K=(K1, K2, K3, . . . } and K.sub.i is a core subset, K.sub.i C.sub.i ; S is the set of subjects, and a subject s, s .epsilon. S, is represented by .largecircle. in a protection graph. .largecircle. is the set of objects, and an object o, o .epsilon. .largecircle., is represented by .quadrature. in a protection graph. A vertex v.sub.i, vi .epsilon. V, that can be a subject or an object is represented by . Each edge e connects elements of an ordered pair of vertices {u, v}, and is labeled with subsets of a finite relation set R, where R={r, w, cb, d, Ir, Iw, Icb, Id, r*, w*, cb*, d*, Ir*, Iw*, Icb*, Id*}. Symbols r, w, d, and cb represent present read, write, drive, and is-controlled-by relations, respectively; and Ir, Iw, Id, Icb represent indirect relations which are originally derived from direct relations such as r, w, d, and cb. Symbol * is the past unary operator. For example, w(a, b) represents a writes b and w*(a, b) represents a wrote b.

Intrusion detection is concerned with the distinction between two epochs: the past and the present. The present epoch begins at the start of the particular operation under consideration. All operations performed before this time are considered to be in the past. The execution of any operation takes time and cannot finish instantaneously. However, if all operations are executed sequentially, that is, if no operations are interleaved and all operations are always completed without any interruption, then these operations can be treated as instantaneous operations. For example, operations read, write, and drive can be treated as instantaneous direct relations. In contrast to direct relations, an indirect relation cannot be treated as an instantaneous relation because it consists of a sequence of direct relations that are usually interleaved. In addition, present direct controlled-by is the only type of present direct operation that can occur simultaneously with other types of present direct operations.

To represent access patterns, we define three types of sequencing operators in the model: (1) an ordering operator, (2) a concurrent execution operator, and (3) a next-state temporal operator. The ordering operator, denoted by <, is used between two relations to mean that the relation on its left occurs before the relation on its right. For example, indirect relation L1<L2 indicates that L1 finishes before L2 starts. That is, every single direct relation of L1 occurs before L2 starts. The ordering operator is important for sequencing indirect relations. The concurrent-execution operator, denoted by .parallel., indicates that two access relations take place simultaneously. The next-state operator, denoted by 0, is the next-state operator in Temporal Logic, see Kroger, Fred, Temporal Logic of Programs, Springer-Verlag (1987). .largecircle.P represents "P holds at the time point immediately after the reference point."

Core subsets are denoted by Ki and protection sets by C.sub.i. The four types of core subsets defined in Section B are denoted as Kow (the core subset of non-writable objects), Kor and Ksr (the core subsets of non-readable objects and subjects, respectively), Ksc (the core subset of non-controllable subjects), and Ksd (the core subset of non-drivable subjects). A protection set Ci includes a subset of subjects, Csi, and a subset of objects, Coi, where C.sub.i =Csi .orgate. Coi; a core subset K.sub.i includes subsets of subjects, Ksci, Ksdi and Ksri, and subsets of objects, Kori and Kowi, where Ki=Ksci .orgate.Ksdi .orgate.Ksri .orgate.Kori .orgate.Kowi. Note that Csi .andgate.Coi=.phi., Ksi Csi and Koi Coi. The set of vertices connecting to vertex v with `e` edges entering v is represented by v.sub.-- set(in, e, v), and .vertline.v.sub.-- set(in, e, v).vertline. is the total number of vertices in v.sub.-- set(in, e, v). The set of protection sets that have at least one element connecting to vertex v with `e` edge leaving v is represented by C.sub.-- set(out, e, v), and .vertline.C.sub.-- set(out, e, v).vertline. is the total number of protection sets in C.sub.-- set(out, e, v).

Referring to FIG. 2, the state of a computer system changes as a result of present access operations. Thus, the present access operations 210 and the present protection graph 205 (present system state) must be input to the intrusion detection system 215 to detect intrusion patterns. Using this input, the intrusion detection system 215 generates a new protection graph 220 and exception-conditions 230, if any, by applying a set of model rules 225. The exception conditions 230 tell the operating system (not shown) that there is a problem (i.e., there has been an intrusion) in the audit trail. In other words, a pattern in the protection graph 205 has been detected by the intrusion detection system 210 that matches a set of pre-determined intrusion patterns.

After all the rules 225 have been applied and all the new edges have been derived, the new protection graph 220 defines the next state. As shown in FIG. 2, G.sub.t is the protection graph at time t before any rules are applied; G.sub.t.sup.' is the protection graph at time t after all the applicable rules have been applied. Note that G.sub.t =G.sub.t-1.sup.'.

The state transition of a system is formally defined as follows:

where c is the set of present access relations and c=V.times.A.times.V, A={r, w, cb, d) and D is the set of exception-condition results. In the graphic definition of the state-transition rules, the symbol is used to represent that the graph following this is produced by the graph-rewriting rules on the graph preceding it.

The definition of read and write relations are made with regard to information flow operations and the definition of controlled-by and drive relations are made with regard to privilege flow operations. The definitions of four direct relations, (a) read, (b) write, (c) controlled-by, and (d) drive, are as follows:

(a) A subject s.sub.i reads/read an object o.sub.m : represented by relation r{s.sub.i, o.sub.m }/r* (s.sub.i, o.sub.m); FIG. 3 shows a graphical representation of this relation;

(b) A subject s.sub.m writes/wrote an object o.sub.n : represented by relation w(s.sub.m, o.sub.n)/w (s.sub.m, o.sub.n); FIG. 4 shows a graphical representation of this relation;

(c) A subject s.sub.i is/was controlled by an object o.sub.m : represented by relation cb(s.sub.i, o.sub.m)/cb*(s.sub.i, o.sub.m); FIG. 5 shows a graphical representation of this relation; and

(d) A subject s.sub.m drives/drove a subject s.sub.i if s.sub.m, provides/provided the next command (or program) to be executed by s.sub.i. This is represented by relation d(s.sub.m, s.sub.i)/d*(s.sub.m, s.sub.i); FIG. 6 shows a graphical representation of this relation.

All of the indirect relations are generated from interaction between subjects and objects and their corresponding direct relations. Each of the four model rules defining indirect relations includes two other relations. At least one of these other relations is a present direct relation. Rules 1 to 4 illustrate how indirect relations can be derived from the invocation of present direct relations. For example, r(s.sub.n, o.sub.i) in Rule 1, w(s.sub.i, o.sub.n) in Rule 2, cb(s.sub.n, o.sub.i) in Rule 3, and d(s.sub.i, s.sub.n) in Rule 4 are present direct relations.

Indirect read is represented by the relation Ir/Ir*(s.sub.i, v.sub.m), if a subject s.sub.i indirectly reads/read an object (or a subject) v.sub.m. FIG. 7 shows a graphical representation of this relation. Indirect read is achieved through the following sequences of relations:

Rule 1-1. w*/Iw*(s.sub.m, o.sub.i) A r(s.sub.n, o.sub.i).fwdarw.Ir(s.sub.n, s.sub.m); FIG. 8 shows a graphical representation of this relation.

Rule 1-2. Iw*(o.sub.m, o.sub.i).LAMBDA.A r(s.sub.n, o.sub.i).fwdarw.Ir(s.sub.n, o.sub.m); FIG. 9 shows a graphical representation of this relation.

Indirect write is represented by the relation Iw/Iw*(v.sub.m, o.sub.n), if a subject (or object) v.sub.m indirectly writes/wrote an object o.sub.n. FIG. 10 shows a graphical representation of this relation. Indirect write is achieved through the following sequences of relations:

Rule 2-1. r*/Ir*/cb/Icb(s.sub.i, o.sub.m) A w(s.sub.i, o.sub.n)=Iw(o.sub.m, o.sub.n); FIG. 11 shows a graphical representation of this relation.

Rule 2-2. Ir*/Icb(s.sub.i, s.sub.m) A w(s.sub.i, o.sub.n)=Iw(s.sub.m, o.sub.n); FIG. 12 shows a graphical representation of this relation.

Indirect controlled-by is represented by the relation Icb/Icb*(s.sub.i, v.sub.m), if a subject s.sub.i is/was indirectly controlled by an object (or subject) v.sub.m. FIG. 13 shows a graphical representation of this relation. Indirect controlled-by is achieved through the following sequences of relations:

Rule 3-1. w*/Iw*(s.sub.m, o.sub.i) A cb(s.sub.n, o.sub.i).fwdarw.Icb(s.sub.n, s.sub.m); FIG. 14 shows a graphical representation of this relation.

Rule 3-2. Iw*(o.sub.m, o.sub.i).fwdarw.cb(s.sub.n, o.sub.i)=Icb(s.sub.n, o.sub.m); FIG. 15 shows a graphical representation of this relation.

Indirect drive is represented by the relation Id/Id*(v.sub.m, s.sub.i), if a subject (or object) v.sub.m indirectly drives/drove a subject s.sub.i, that is, if v.sub.m provides the next command to be executed by s.sub.i. FIG. 16 shows a graphical representation of this relation. Indirect drive is achieved through the following sequences of relations:

Rule 4-1 cb/Icb(s.sub.i, o.sub.m).LAMBDA.(s.sub.i, s.sub.n).fwdarw.Id(o.sub.m, s.sub.n); FIG. 17 shows a graphical representation of this relation.

Rule 4-2. Icb(s.sub.i, s.sub.m).LAMBDA.d(s.sub.i, s.sub.n).fwdarw.. Id(s.sub.m, s.sub.n); FIG. 18 shows a graphical representation of this relation.

Rule 4-3. d*/Id*(s.sub.m, s.sub.i).LAMBDA.d(s.sub.i, s.sub.n).fwdarw.Id(s.sub.m, s.sub.n); FIG. 19 shows a graphical representation of this relation.

Rule 4-4. Id*(o.sub.m, s.sub.i).LAMBDA.d(s.sub.i, s.sub.n).fwdarw.Id(o.sub.m, s.sub.n); FIG. 20 shows a graphical representation of this relation.

The distinction between a solid edge and a dotted edge, as used in Rule 8 (described below), is that dotted-edge relations have no effect on the current activities of the vertices adjacent to them. This means that Rule 1 to 4 cannot apply to dotted-edge relations. The distinction between solid vertices and dotted-vertices is that dotted vertices cannot initiate or accept any direct operations. Let .alpha., .beta., .delta. R, .alpha. .beta. and .lambda. represent a null vertex. We have the following rules:

Rule 5 (Add vertex) .lambda..fwdarw.v.sub.m. FIG. 21 shows a graphical representation of this rule.

Rule 6 (Deactivate vertex) .beta.'(s.sub.i, v.sub.m).LAMBDA.(v.sub.m, v.sub.j).fwdarw..beta.'(v.sub.i, [v.sub.m ]).LAMBDA..beta."([v.sub.m], v.sub.j) FIG. 22 shows a graphical representation of this rule.

Rule 7 (Add edges) .beta.(s.sub.i, v.sub.m).fwdarw..beta.+.delta.(s.sub.i, v.sub.m) FIG. 23 shows a graphical representation of this rule.

Rule 8 (Deactivate edges) .beta.(v.sub.i, v.sub.m).fwdarw..beta.-.alpha.(v.sub.i, v.sub.m) FIG. 24 shows a graphical representation of this rule.

The first three rules above are self-explanatory. We use two Unix.RTM. system-call examples, namely exece() and creat(), to illustrate the use of Rules 4 to 8. The exece() system call invokes another program, overlaying the memory space of the process with a copy of the executable file. When a subject invokes exece(), the subject is directly self-driven. Applying Rule 4, this subject is indirectly driven by those subjects or objects which directly or indirectly control it. After the successful return of exece(), the subject is controlled by a new object. All adjacent relations with outgoing label cb*/Icb* from the subject are deactivated (ref. Rule 8, deactivated edges) because this subject is no longer controlled by those subjects or objects. (The past execution code is removed from memory space and replaced by the code of that new object.)

The second system-call example is provided by the invocation of creat(). When a subject invokes creat() on an existing object, the length of the object is truncated to zero. That is, all stored data is removed. Therefore, all the relations labeled w*/Iw from other vertices to that object are deactivated (Rule 8). When creat() is invoked on a new file in a directory, a new vertex is added (Rule 5) and the directory is directly written (a new edge is added by Rule 7). When an object in a directory is removed, the vertex is deactivated (Rule 6) and the directory is written.

Two relations are called adjacent if they share a graph vertex. Note that Rules 1 to 4 discussed above only apply to a present direct relation and its adjacent relations. The "present relation" is provided by the access operation under current consideration. The "present relation" can be interpreted as the latest event read from the audit trail. All access operations performed before the present access operations are past operations. All the present operation on a protection graph must be carried out before the next event is read in the audit trails. Otherwise, an indirect relation may be missed.

Equations (1) to (6) (provided below) characterize all types of present indirect operations which are derived from a present direct relation and its adjacent relations. These equations show that the only event order which needs to be maintained is that which distinguishes past operations from present direct operations. Therefore, the updates of the protection graph need not track the order of all operations. Thus, if all past direct and indirect relations are shown in a protection graph, the application of rules 1 to 4 to those relations adjacent to present direct relations is sufficient to discover all new indirect relations.

Equations (1) through (6) are as follows:

Note that, if the present protection graph only contains direct relations, that is, all past indirect relations are missing, then applying Rules 1 to 4 to those direct relations adjacent to present direct relations is insufficient to discover all new indirect relations.

In this section, the detection of (1) unintended use of a foreign program, and (2) virus propagation by using the model presented in Section C is illustrated.

The unintended use of foreign programs can be caused by the inadequate setting of the user's command search paths in Unix.RTM. systems. Two types of problems may arise: (1) a user may execute an intruder's version of a system command instead of the intended system command whenever the user's command search paths start from the current directory; (2) a user may execute a system command instead of the intended user program if the user's search paths start from a system command directory. These two problems cannot be easily resolved because: (1) it is undesirable to require users to type full path names for every program execution, and (2) it is unrealistic to expect all users to understand the effects of the search-path setting on their executed programs. The following example illustrates the effect of the execution of an intruder's version of a system command, instead of the intended system command, by an unsuspecting user.

In UNIX.RTM., user applications often access the /tmp directory, which can be read, written and executed by every user in the system. This implies that, for example, a user (identified below as the Intruder) may deliberately leave an executable file named ls in directory /tmp and then change the owner of /tmp/ls (to anther identity denoted by ssp below) such that his real identity cannot be discovered later. Subsequently, an unsuspecting user (identified below as the Victim) may change his current directory to /tmp and attempt to list current directory contents by using (what he believes to be the system-provided command) ls. If the Victim's first search path is set to the current directory, then the bogus version of ls gets executed instead of the system command ls. Thus, the bogus ls can acquire all the Victim's privileges, thereby controlling all his activities and allowing the Intruder to (albeit indirectly) write over the unsuspecting user's sensitive objects; e.g., setup files .login and .cshrc. In this context, these seemingly normal actions of the bogus ls program represent intrusions.

The Intruder's actions may be summarized as follows:

$ cp I.sub.-- write /tmp/ls

$ chmod 0111 /tmp/ls

$ chown ssp /tmp/ls

The Victim's actions may be summarized as follows:

$ cd /tmp

$ ls

The contents of the /tmp/ls file created by the Intruder is shown below.

The Command "set path=(. $HOME/bin /bin /usr/bin /usr/security/bin /etc)" is a typical command found in users' .cshrc files on UNIX.RTM.-like system to set up a user's command search paths. After the execution of program /tmp/ls, the Victim's command search paths in his $HOME/.cshrc is changed to "set path=(/tmp . $HOME/bin /bin usr/bin /usr/ security/bin /etc)" and a new line "/tmp/ls" is appended to the end of $HOME.login. Thus, both .cshrc and .login files of the Victim can be affected by the Intruder.

As the consequence of the commands invoked by Intruder and Victim, the following events can be selected from audit trails:

This sequence of events is interpreted by our model as the sequence of protection graphs shown below. At time 10:01, process 111 (owner Intruder) writes into /tmp/ls, as shown in the graph illustrated in FIG. 25a.

At time 11:01, process 222 (owner Victim) starts being controlled by /tmp/ls. For simplicity, the previous object executed by process 222 is not shown in the graph. The direct-write relation between process 111 and /tmp/ls is a past relation because the operation occurred in the past. A new indirect controlled-by relation between processes 111 and 222 can be derived from the direct controlled-by relation between process 222 and /tmp/ls, as illustrated in FIG. 25b.

At time 11:02, process 222 writes data into $HOME/.login. A new indirect-write relation between process 111 and $HOME/.login and a new indirect-write relation between tmp/ls and $HOME/.login can be derived, as illustrated in FIG. 25c.

At time 11:03, process 222 writes data into $HOME/.cshrc. A new indirect-write relation between process and $HOME/.cshrc and a new indirect-write relation between tmp/ls and $HOME/.cshrc can be derived, as illustrated in FIG. 25d.

The fact that there are two indirect writes into a object that is located in a core-subset indicates that there has been an intrusion.

Access relations between vertices can be recorded in Access Logging Lists (ALLs). An ALL, which can be associated with a subject or object, contains entries that record relations between vertices. The ALL of a subject or object contains the names of all subjects and objects that accessed that subject or object. Thus, if a relation exists between two vertices in a protection graph, it can be represented by two entries, one in each ALL.

The ALLs corresponding to the subjects and objects of the protection set selected for our example are shown below.

The structure of an ALL can be simplified by reducing the number of its entries and by removing irrelevant or redundant information. In our example, process 222, Victim/.chsrc and Victim/.login belongs to Victim's protection set. Although /tmp/ls has been created by the Intruder, /tmp/ls belongs to ssp's protection set after its owner was changed to ssp by the Intruder. Thus, subjects in a vertex's ALL can be replaced by their owner's name. Entries of indirectly-written-by relations with other objects listed in an ALL cannot be replaced by their owners' names because (1) these objects' owners may not write them, and (2) these objects may actually represent covert-channel variables. In case (1) the objects do not contain their owners' data, and in case (2) the objects may not have owners. Furthermore, unless auditors decide to retain them to track data and privilege flow paths, entries of indirectly-written-by relations with other objects listed in an ALL can be removed. This is the case because objects are not the active elements (that is, they cannot be intruders) and only provide input to write operations on the object associated with the ALL. Thus, the ALL associated with Victim/.cshrc's in the example above can be simplified as shown below.

A further simplification results from the deletion redundant past relations; i.e., multiple past relations of the same type. Maintaining multiple past relations of the same type between two vertices cannot provide any additional useful information. However, indirect-write relations with other object identities cannot be removed from ALLs, because these entries are essential to the detection of covert-channel use and virus propagation. Similar simplification of other entries in ALLs is possible.

The intrusion-detection model presented in the previous section can be used to detect potential propagation of typical viruses. The most frequently used method for virus propagation requires an infected process to write a piece of code into another file while running a virus program. This action can be represented in the model as [cb(s.sub.1 virus .parallel. W(s.sub.1, o.sub.2)]. Thus, by Rule 3-1, [cb(s.sub.1, virus w(s.sub.1, o.sub.2)].fwdarw.Iw(virus, o.sub.2). Three typical approaches to Virus propagation (see Cohen, F., Computer Viruses: Theory and Experiments, Proceedings of the 7th National Computer Security Conference, pp. 240-263 (1984)) can be used to illustrate the use of the intrusion detection model in this area. The first approach is simply to copy the disk file containing the virus after reading it. The direct copying of the disk file containing the virus can be represented in the model as: [cb*(s.sub.1, virus) .parallel. r*(s.sub.1, virus)] [cb(s.sub.1, virus) .parallel. w(s.sub.i, o.sub.2)].fwdarw.Iw(virus, o.sub.2). If the process attempting to propagate the virus has only execute access to the file but, nevertheless, has read access to executable-code segments, it can read its code segments as well as its data segments, convert them to the disk-file format, and write them onto another disk file copy. This way the infected process does not need to read the original disk-file in order to make a copy.

The second approach to virus propagation requires that the process s.sub.1 forks a child process s.sub.2 and has the child process execute system command cp (copy) to make copies of the virus program. This can be described formally using Rules 4-1, 2-1 as [cb (s.sub.1, virus) .parallel. d*(s.sub.1 , s.sub.2 )] [cb*(s.sub.2, c.sub.p) .parallel. r*(s.sub.2 , virus)] [cb(s.sub.2 , c.sub.p) .parallel. w(s.sub.2 , o.sub.3)].fwdarw.Id*(virus, s.sub.2 ).LAMBDA.Iw(virus, o.sub.3). In this type of virus propagation, a process always makes copies of the file which "indirectly drove" it.

The third approach to virus propagation requires that an infected process writes a piece of code, which has a similar function as cp, into a second file o.sub.2 then forks a child process s.sub.2 to run o.sub.2 . The child process copies the virus to a third file o.sub.3 By Rules 4-1, 2-1, 3-2, this sequence of operations can be formalized as [cb*(s.sub.1, virus .parallel. w*(s.sub.1, o.sub.2)] [cb (s.sub.1 , virus) .parallel. d*(s;, s.sub.2 )] [cb*(s.sub.2 , o.sub.2) .parallel. r*(s.sub.2 , virus)] [cb(s.sub.2 , o.sub.2) .parallel. w(s.sub.2 , o.sub.3 )].fwdarw.Id.(virus, s.sub.2 ) .LAMBDA.Icb(s.sub.2 , virus).LAMBDA.Iw(virus, o.sub.3 ). In this type of virus propagation, a process always makes copies of the file which "indirectly drove" and "indirectly controlled" it.

From the application of the model rules to the direct relations shown in the three approaches to virus propagation presented above, it can be concluded that a virus must indirectly write other files to propagate itself, that is Iw(virus, o.sub.i). Consequently, after the virus propagation proceeds for a period of time, the original virus will have the highest frequency of indirect write to other files.

The indirect-write pattern of virus propagation, namely Iw(virus, o.sub.i), may appear individually or simultaneously and can be detected by the model of the present invention using the following conditions: (1) .vertline.v.sub.-- set(out, Iw/Iw*, virus).vertline.>threshold and a large portion of elements are executable files; (2) .vertline.C.sub.-- set(out, Iw/Iw*, virus).vertline.>threshold; (3) .vertline.v.sub.-- set(in, cb/cb*/Icb/Icb*, virus).vertline.>threshold; (4) .vertline.C.sub.-- set(in, cb/cb*/Icb/Icb*, virus).vertline.>threshold; (5) v.sub.-- set(out, Id/Id*, virus).vertline.>threshold; (6) .vertline.C.sub.-- set(out, Id/Id*, virus).vertline.>threshold. The used here are parameters defining limits to determine abnormal process behavior. If the occurrences of a pattern exceeds the threshold, an abnormality occurs.

The present invention can be used to detect the existence of viruses by detecting virus-propagation patterns. In particular, it can help discover whether a protection set can be infected by a virus originating outside of the protection set, and whether a virus could propagate outside of its originating protection set. We define the virus-free protection set and a virus-confinement protection set as follows:

A protection set C.sub.i is a virus-free set if all objects of C.sub.i have not been written (directly/indirectly) by other protection sets. Formally, w*/IW (v.sub.g, o.sub.i), where o.sub.i .epsilon.C.sub.i, v.sub.g C.sub.i .revreaction.P.sub.i. Predicate P.sub.i denotes that protection set C.sub.i is a virus-free set. FIG. 26 shows a graphical representation of a virus-free set.

A protection set C.sub.i is a virus-confinement set if subject of C.sub.i have not (directly/indirectly) written objects of other sets. Formally, w*/Iw*(v.sub.i, o.sub.g), where v.sub.i e C.sub.i, o.sub.g C.sub.i .revreaction.Q.sub.i. Predicate Q.sub.i denotes that protection set C.sub.i is a virus-confinement set. FIG. 27 shows a graphical representation of a virus-confinement set.

The present invention can detect if present direct operations can lead to the infection of a presently virus-free protection set at the next state. Thus, if a protection set C.sub.i is virus-free and present direct relations do not lead to direct write or indirect write relations from outside vertices to any objects of C.sub.i, then C.sub.i will be virus-free in the next state. Consequently, if a protection set was not infected when the system was initialized, then the protection of objects in the set can be ensured by applying this principle. Formally, S.sub.in, o.sub.in .epsilon. C.sub.i, S.sub.gk, o.sub.gk C.sub.i, P.sub.i .LAMBDA. w(s.sub.gk, o.sub.in) .LAMBDA. r*/cb(s.sub.in, o.sub.gk) .LAMBDA. w(s.sub.in, o.sub.in)].fwdarw..circle.P.sub.i. FIG. 28 shows a graphical representation of this principle.

The present invention can detect if any present operations can propagate a virus at the next stage. Thus, if C.sub.i is a virus-confined set and present direct operations do not lead to direct write or indirect write relations to any objects outside C.sub.i, then C.sub.i will be virus-confined in the next state. Thus, if a protection set remain virus-confined after the system is initialized, then the virus confinement property of this protection set can be maintained by applying this principle. Formally, s.sub.ik, o.sub.ik .epsilon.Ci, s.sub.gk, o.sub.gk Ci, Qi .LAMBDA. w(s.sub.in, o.sub.gk).LAMBDA. r*/cb(s.sub.gk, o.sub.in) w(s.sub.gk, o.sub.gk))].fwdarw.OQ.sub.i , FIG. 29 shows a graphical representation of this principle.

The following procedure derives all the new indirect write relations when a present direct write relation occurs. The protection graph PG.sub.B contains all the past direct and indirect access relations, and protection graph PG.sub.A contains all the indirect relations derived by application of the model rules.

In the procedure above, the protection graph PG.sub.B is updated whenever a direct write access relation is found. Other algorithms that help derive all instances of indirect read, indirect controlled-by, indirect drive relations are omitted because of their similarity to the above algorithm.

The complexity of this algorithm is in O(n), where n is the total number of vertices in a protection graph PG.sub.B. The maximum number of vertices that directly or indirectly write a vertex is n in the worst case.

A pattern-oriented intrusion detection model is defined here. The key advantage of this model is its ability to characterize context-dependent patterns of intrusion, such as those present in covert-channel use and in virus propagation. As with any pattern-oriented model of intrusion detection, the present invention requires the explicit definition of individual intrusion patterns prior to analysis of audit trails. It is contemplated that future intrusion-detection systems will rely on both the pattern-oriented and the statistical approaches, thereby combining the advantages of both.

Finally, the present invention can be easily adapted to other applications beyond those mentioned above. For example, the detection of internet worms, the information and privilege flows within a distributed ATM banking system, and the improvement of reliability and consistency of distributed data bases.

While the invention has been particularly shown and described with reference to a preferred embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention.