Title: Method of and system for detecting an anomalous operation of a computer system
Abstract: A real-time approach for detecting aberrant modes of system behavior induced by abnormal and unauthorized system activities that are indicative of an intrusive, undesired access of the system. This detection methodology is based on behavioral information obtained from a suitably instrumented computer program as it is executing. The theoretical foundation for the present invention is founded on a study of the internal behavior of the software system. As a software system is executing, it expresses a set of its many functionalities as sequential events. Each of these functionalities has a characteristic set of modules that is executed to implement the functionality. These module sets execute with clearly defined and measurable execution profiles, which change as the executed functionalities change. Over time, the normal behavior of the system will be defined by the boundary of the profiles. An attempt to violate the security of the system will result in behavior that is outside the normal activity of the system and thus result in a perturbation of the system in a manner outside the scope of the normal profiles. Such violations are detected by an analysis and comparison of the profiles generated from an instrumented software system against a set of known intrusion profiles and a varying criterion level of potential new intrusion events.
Patent Number: 6,963,983 Issued on 11/08/2005 to Munson, et al.
| Inventors:
|
Munson; John C. (Moscow, ID);
Elbaum; Sebastian G. (Moscow, ID)
|
| Assignee:
|
Cylant, Inc. (Lexington, MA)
|
| Appl. No.:
|
755948 |
| Filed:
|
January 13, 2004 |
| Current U.S. Class: |
713/201 |
| Intern'l Class: |
G06F 011/30 |
| Field of Search: |
713/200,201
709/223,224
706/15,16,21,22,50,61,45-48,62
|
References Cited [Referenced By]
U.S. Patent Documents
| 5067073 | Nov., 1991 | Andrews.
| |
| 5278901 | Jan., 1994 | Shieh et al.
| |
| 5313616 | May., 1994 | Cline et al.
| |
| 5355487 | Oct., 1994 | Keller et al.
| |
| 5487131 | Jan., 1996 | Kassatly et al.
| |
| 5499340 | Mar., 1996 | Barritz.
| |
| 5528753 | Jun., 1996 | Fortin.
| |
| 5539907 | Jul., 1996 | Srivastava et al.
| |
| 5557742 | Sep., 1996 | Smaha et al.
| |
| 5581482 | Dec., 1996 | Wiedenman et al.
| |
| 5621889 | Apr., 1997 | Lermuzeaux et al.
| |
| 5675711 | Oct., 1997 | Kephart et al.
| |
| 5732273 | Mar., 1998 | Srivastava et al.
| |
| 5790858 | Aug., 1998 | Vogel.
| |
| 5907834 | May., 1999 | Kephart et al.
| |
| 5987250 | Nov., 1999 | Subrahmanyam.
| |
| 5991881 | Nov., 1999 | Conklin et al.
| |
| 6009514 | Dec., 1999 | Henzinger et al.
| |
| 6026236 | Feb., 2000 | Fortin et al.
| |
| 6094530 | Jul., 2000 | Brandewie.
| |
| 6119236 | Sep., 2000 | Shipley.
| |
| 6266408 | May., 2001 | Sirosh.
| |
| 6282701 | Aug., 2001 | Wygodny et al.
| |
| 6321338 | Nov., 2001 | Porras et al.
| |
| 6347374 | Feb., 2002 | Drake et al.
| |
| 6370648 | Apr., 2002 | Diep.
| |
| 6405318 | Jun., 2002 | Rowland.
| |
| 6681331 | Jan., 2004 | Munson et al.
| |
| 2002/0138753 | Sep., 2002 | Munson.
| |
| 2003/0200462 | Oct., 2003 | Munson.
| |
| 2005/0044406 | Feb., 2005 | Stute.
| |
Other References
Frank, "Artificial Intelligence and Intrusion Detection: Current and Future Directions"
Jun. 9, 1994, Division of Computer Science University of California at Davis, p. 1-12.
"Real -time attach recognition and response: A solution for tightening network
security" 1997, Internet Security Systems, p. 1-13.
Lankiewicz et al, "Real-time Anomaly Detection Using a Nonparametric Pattern
Recognition Approach", 1991, IEEE, p. 80-89.
Cannady, "Artificial Neural Networks for Misuse Detection" Oct. 1998, School
of Computer and Information Sciences Nova Southeastern University, p. 1-14.
Cannady et al, "The Application of Artificial Neural Networks to Misuse Detection:
Initial Results", Mar. 10, 1997, Georgia Tech Research Institute Georgia Institute
of Technology, p. 1-13.
Herringshaw, "Detecting Attacks on Networks" Dec. 1997, Industry Trends, p. 16-17.
Mukherjee et al, "Network Intrusion Detection" May/Jun. 1994, IEEE Network, p. 26-41.
Lane et al, "Sequence Matching and Learning in Anomaly Detection for Computer
Security" 1997, School of Electrical and Computer Engineering Purdue University,
p. 1-7.
Dasgupta, D. et al., "Novelty Detection in Time Series Data Using Ideas from
Immunology," 1995, 6 pages.
D'haeseleer, P. et al., "A Distributed Approach to Anomaly Detection," Aug. 30,
1997, 30 pages.
D'haeseleer, P. et al., "An Immunology Approach to Change Detection: Algorithms,
Analysis and Implications," IEEE Symposium on Security and Privacy, 1996,
10 pages.
Forrest, S. et al., "Computer Immunology," Comm. of the ACM, Mar. 21,
1996, 18 pages.
Forrest, S. et al., "Self-Nonself Discrimination in a Computer," Proceedings
of IEEE Symposium on Research in Security and Privacy, 1994, 11 pages.
Hofmeyr, S.A., "Intrusion Detection Using Sequences of System Calls," Dec. 17,
1997, 41 pages.
Hofmeyr, S.A. et al., "Architecture for an Artificial Immune System," 2000, 31 pages.
Somayaji, A. et al., "Automated Response Using System-Call Delays," Proceedings
of the 9th USENIX Security Simposium, Aug. 14-17, 2000, 13 pages.
Somayaji, A. et al., "Principles of a Computer Immune System," ACM, New Security
Paradigms Workshop, Langdale, Cumbria UK, 1998, 75-82.
Warrender, C. et al., "Detecting Intrusions Using System Calls: Alterative Data
Models," IEEE Computer Society, Symposium on Security and Privacy. 1999, 133-145.
Anderson, D. et al., "Next-generation intrusion detection expert system (NIDES),"
Technical Report, Computer Science Laboratory, SRI International, Menlo Park, CA,
SRI-CSL-95-07, May, 1995, 1-37 (plus 6 additional pages).
Anderson, D. et al., "Detecting Unusual Program Behavior Using the Statistical
Component of the Next-generation Intrusion Detection Expert System (NIDES)," SRI-CSL-95-06,
SRI International, Menlo Park, CA, May, 1995, 1-71, 73-75, 77 (plus 6 additional pages).
Aslam, T. et al., "Use of A Taxonomy of Security Faults," Technical Report TR-96-051,
COAST Lab, Purdue University, presented at 19th National Information Systems Security
Conference, Sep., 1996, 1-10.
Ball, T. et al., "Optimally Profiling and Tracing Programs," Technical Report
#1031, University of Wisconsin, Computer Science Dep., Sep., 1991, 1-27.
Bishop, M., "A Standard Audit Log Format," Proc. of the 18th National Information
Systems Security Conference, 1995, 136-145.
Bishop, M., "Profiling Under UNIX by Patching," Software-Practice and Exp.,
Oct. 1987, 17(10), 729-739.
Crosbie, M. et al., "Defending a Computer System using Autonomous Agents," Technical
Report No. 95-022, COAST Laboratory, Dept. of Computer Sciences, Purdue University,
Mar., 1994, 1-11.
Denning, D., "An Intrusion-Detection Model," IEEE Transactions on Software
Engineering, Feb. 1987, 13(2), 222-232.
Elbaum, S. et al., "Intrusion Detection through Dynamic Software Measurement,"
Proc. Usenix Workshop on Intrusion Detection and Networking Monitoring, Santa
Clara, California, Apr. 9-12, 1999, 1-10.
Graham, S.L. et al., "An Execution Profiler for Modular Programs," Software
Practice and Exp., 1983, 13, 671-685.
Hall, R.J., "Call Path Profiling," Proc. 14th Int'l. Conf.
Soft. Engineering, ACM, 1992, 296-306.
Halme, L. et al., "AINT misbehaving—a Taxonomy of Anti-intrusion Techniques,"
Proc. of the 18th National Information Systems Security Conference, 1995,
13 pages.
Hochberg, J. et al., "NADIR: An Automated System for Detecting Network Intrusion
and Misuse," Computers & Security, 1993, 12(3), 235-248.
Ilgun, K., "USTAT: A Real-time Intrusion Detection System for UNIX," Proc.
of the IEEE Symposium on Research in Security and Privacy, May 24-25, 1993, 16-28.
Javitz, H. et al., "The SRIIDES Statistical Anomaly Detector," Proc. of the
IEEE Symposium on Research in Security and Privacy, May 20-22, 1991, 316-326.
Johnson, "Profiling for Fun and Profit," UNSENIX Winter '90 Conference Proceedings,
1990, 325-330.
Jonsson, E. et al. "A Quantitative Model of the Security Intrusion Process Based
on Attacker Behavior," IEEE Transactions on Software Engineering, Apr.,
1997, 23(4), 235-245.
Kumar, S. et al., "A Pattern Matching Model for Misuse Intrusion Detection,"
Proc. of the 17th National Computer Security Conference, COAST Laboratory,
Dept. of Computer Sciences, Purdue University, Oct. 1994, 11-21.
Kumar, S. et al., "A Software Architecture to Support Misuse Intrusion Detection,"
Proc. 18th National Information Systems Security Conference, COAST Laboratory,
Dept. of Computer Sciences, Purdue University, Mar. 1995, 1-17.
Lankiewicz, L. et al., "Real-Time Anomaly Detection Using a Nonparametric Pattern
Recognition Approach," Seventh Annual Computer Security Applications Conference,
San Antonio, Texas, Dec. 2-6, 1991, 80-89.
Larus, J.R., et al., "Abstract Execution: A Technique for Efficiently Tracing
Programs," Software-Practice and Experience, Dec., 1990, 20(12), 1241-1258.
Larus, J.R. et al., "Rewriting Executable Files to Measure Program Behavior,"
Technical Report #1083, University of Wisconsin, Computer Science Dep., Mar. 25,
1992, 1-17.
Lunt, T., "A Survey of Intrusion Detection Techniques," Computers & Security,
1993, 12, 405-418.
Mukherjee, B. et al., "Network Intrusion Detection," IEEE Network, May/Jun.,
1994, 8(3), 26-41.
Munson, J., "A Functional Approach to Software Reliability Modeling," In Quality
of Numerical Software, Assessment and Enhancement, Boisvert (ed.), Chapman
& Hall, London, 1997, 61-76.
Petersen, K., "IDA—Intrusion Detection Alert," Proc. of the IEEE Annual
International Computer Software and Applications Conference, Chicago, IL, Sep.
21-25, 1992, 306-311.
Porras, P. et al., "Penetration State Transition Analysis—A Rule-Based
Intrusion Detection Approach," Eighth Annual Computer Security Applications
Conference, IEEE Computer Society Press, Nov. 30-Dec. 4, 1992, 220-229.
Power, L.R., "Design and use of a program execution analyzer," IBM Systems
J., 1983, 22(3), 271-294.
Puketza, N. et al., "A Methodology for Testing Intrusion Detection Systems,"
IEEE Transactions on Software Engineering, Oct., 1996, 22(10), 719-729.
Shieh et al., "A Pattern-Oriented Intrusion-Detection Model and Its Applications,"
Proc. of the 1991 IEEE Symposium on Research in Security and Privacy, Oakland,
Calif., May 20-22, 1991, 327-342.
Smaha, S., "Haystack: An Intrusion Detection System," Proceedings of the Fourth
Aerospace Computer Security Applications Conference, Orlando, Florida, IEEE
Computer Society, Dec. 12-16, 1988, 37-44.
Smith, M.D., "Tracing with Pixie," Stanford University Technical Report No. CSL-TR-91-497,
Apr. 4, 1991, 1-29.
Sobirey, M. et al., "The Intrusion Detection System AID. Architecture, and Experiences
in Automated Audit Analysis," Proc. of the International Conference on Communications
and Multimedia Security, Sep. 23-24, 1996, 278-290.
Speer, S.E., "Improving UNIX Kernel Performance Using Profile Based Optimization,"
Winder USENIX, Jan. 17-21, 1994, 181-188.
Teng, H. et al., "Adaptive Real-Time Anomaly Detection Using Inductively Generated
Sequential Patterns," Proc. of the IEEE Symposium on Research in Security and
Privacy, Oakland, CA, May 7-9, 1990, 278-284.
Vaccaro, H. et al., "Detection of Anomalous Computer Session Activity," Proc.
of the IEEE Symposium on Research in Security and Privacy, Oakland, CA, May
1-3, 1989, 280-289.
Wall, D.W., "Global Register Allocation at Link Time," Digital Equipment Corporation,
WRL Research Report 86/3, Oct., 1986 1-20.
|
Primary Examiner: Revak; Christopher
Attorney, Agent or Firm: Judson; David H.
Parent Case Text
RELATED APPLICATION
This application is a continuation of prior co-pending application Ser. No.
09/309,755, filed May 11, 1999, now U.S. Pat. No. 6,681,331.
Claims
1. A method of detecting an anomalous operation of a computer system indicative
of a security violation, the method comprising:
(a) monitoring transitions across defined points within software executing on
the computer system and in response thereto producing given program activity data;
(b) comparing the given program activity data with data indicative of a normal
operation of the computer system to detect an anomalous operation of the computer
system indicative of a security violation; and
(c) as a result of the comparison that detects the anomalous operation, taking
a given action.
2. The method as described in claim 1 wherein the given action includes outputting
a given notification.
3. The method as described in claim 2 wherein the given notification indicates
an anomalous operation of the computer system.
4. The method as described in claim 1 wherein the given action includes updating
data indicative of a normal operation of the software.
5. The method as described in claim 1 wherein the defined points within the software
comprise program module input or output events.
6. The method as described in claim 1 wherein step (b) occurs at a given rate.
7. The method as described in claim 6 further including the step of adjusting
the given rate.
8. The method as described in claim 7 wherein the given rate is increased during
a given period of activity of the computer system.
9. The method as described in claim 7 wherein the given rate is decreased during
a given period of activity of the computer system.
10. The method as described in claim 1 wherein the given action outputs a first
indication if the comparison is indicative of an event that has been previously
observed, and the given action outputs a second indication if the comparison is
indicative of an event that has not been previously observed.
11. The method as described in claim 10 further including the step of forwarding
data about the event that has not been previously observed for subsequent characterization.
12. The method as described in claim 1 further including the step of selectively
displaying the given program activity data.
13. In a computer system comprising given hardware and software, the improvement comprising:
a transducer instrumented within the given hardware or the given software of
the computer system that monitors the computer system as the computer system operates
and in response thereto generates given program activity data;
a comparator that compares the given program activity data with data indicative
of a normal operation of the computer system; and
a device for outputting a given indication based on the comparison between the
given program activity data and the data indicative of the normal operation of
the computer system;
wherein the given indication is indicative of an anomalous behavior resulting
from a security violation in the computer system.
14. In the computer system as described in claim 13 wherein the transducer is
given code that monitors transitions across defined points within the operating
environment of the computer system.
15. In the computer system as described in claim 14 wherein the defined points
within the operating environment of the computer system comprise program module
input or output events.
16. In the computer system as described in claim 13 wherein the transducer obtains
signals indicative of the operating environment of the computer system from a hardware bus.
17. In the computer system as described in claim 13 further including code for
selectively adjusting a rate at which the comparator compares the given program
activity data with data indicative of the normal operation of the computer system.
18. In the computer system as described in claim 13 further including a display
for outputting the given program activity data.
19. In the computer system as described in claim 13 further including code for
updating the data indicative of the normal operation of the computer system.
20. A computer system, comprising:
given hardware;
given software executable on the given hardware;
a transducer instrumented within the given hardware or the given software that
monitors an operating environment of the computer system as the computer system
operates and in response thereto generates given program execution trace data;
a comparator that compares the given program execution trace data with data indicative
of a normal operation of the computer system; and
a device for outputting a given indication based on the comparison between the
given program execution trace data and the data indicative of the normal operation
of the computer system;
wherein the given indication is indicative of an anomalous behavior resulting
from a security violation in the computer system.
21. A method of determining whether an intrusion has occurred at a given computer
system having given hardware and given software, comprising:
instrumenting the given hardware or the given software;
instrumented hardware or software, monitoring an operating environment of the
computer system as the computer system operates and in response thereto generating
given program execution trace data;
comparing the given program execution trace data with data indicative of a normal
operation of the computer system to determine whether an intrusion has occurred;
and
based on the comparison that determines that an intrusion has occurred, taking
a given action.
22. The method as described in claim 21 wherein the monitoring step is performed
remotely from the computer system.
23. The method as described in claim 21 wherein the given action outputs an alarm.
24. The method as described in claim 21 wherein the given action updates the
data indicative of the normal operation of the computer system.
25. The method as described in claim 21 further including the step of adjusting
a rate at which the program execution trace data is compared with the data indicative
of the nominal operation of the computer system as a function of an amount of processing
activity taking place at the given computer system.
26. A method of detecting an anomalous operation of a computer system, indicative
of a security violation, comprising:
establishing a steady state behavior of the computer system based on at least
one execution profile;
comparing internally observable execution behavior of the computer system against
the steady state behavior to detect an anomalous operation of the computer system
indicative of the security violation, the internally observable execution behavior
defined by program activity; and
taking a given action as a result of the comparison that detects the anomalous
operation.
27. The method as described in claim 26 further including the step of adjusting
a given rate of the comparison as a function of an amount of processing activity
occurring in the computer system.
28. The method as described in claim 26 wherein the given action outputs an alarm.
29. The method as described in claim 28 wherein the alarm is indicative of an anomaly.
30. The method as described in claim 26 further including the step of recording
the internally observable execution behavior of the computer system.
31. A method of detecting an anomalous operation of a computer system indicative
of a security violation, comprising the unordered steps:
instrumenting given hardware or software in the computer system;
establishing a steady state behavior of the computer system based on at least
one execution profile;
comparing a first behavior, as determined using program activity data generated
from the instrumented hardware or software, against the steady state behavior to
detect an anomalous operation of the computer system indicative of a security violation;
and
taking a given action as a result of the comparison that indicates the anomalous operation.
Description
FIELD OF THE INVENTION
The present invention generally relates to detecting the use of software, and
more specifically, to the dynamic detection of an intrusive anomalous use of computer software.
BACKGROUND OF THE INVENTION
The literature and media abound with reports of successful violations of computer
system security by both external attackers and internal users. These breaches occur
through physical attacks, social engineering attacks, and attacks on the system
software. In a system software attack, the intruder subverts or bypasses the security
mechanisms of the system in order to gain unauthorized access to the system or
to increase current access privileges. These attacks are successful when the attacker
is able to cause the system software to execute in a manner that is typically inconsistent
with the software specification and thus leads to a breach in security.
Intrusion detection systems monitor some traces of user activity to determine
if an intrusion has occurred. The traces of activity can be collated from audit
trails or logs, network monitoring or a combination of both. Once the data regarding
a relevant aspect of the behavior of the system are collected, the classification
stage starts. Intrusion detection classification techniques can be broadly catalogued
in the two main groups: misuse intrusion detection, and anomaly intrusion detection.
The first type of classification technique searches for occurrences of known attacks
with a particular "signature," and the second type searches for a departure from
normality. Some of the newest intrusion detection tools incorporate both approaches.
One prior art system for detecting an intrusion is the EMERALD™ program.
EMERALD defines the architecture of independent monitors that are distributed about
a network to detect intrusions. Each monitor performs a signature or profile analysis
of a "target event stream" to detect intrusions and communicates such detection
to other monitors on the system. The analysis is performed on event logs, but the
structure of the logs is not prescribed and the timeliness of the analysis and
detection of an intrusion depends on the analyzed system and how it chooses to
provide such log data. By monitoring these logs, EMERALD can thus determine that
at some point in the event stream that was recorded in the log, an intrusion occurred.
However, the detection is generally not implemented in real time, but instead occurs
at some interval of time after the intrusion. Also, this prior art system does
not allow monitoring of all types of software activity, since it is limited to
operating system kernel events.
Accordingly, it would be desirable to provide a real time intrusion
detection paradigm that is applicable to monitoring almost any type of program.
It would be preferable to detect an intrusion based on the measurement of program
activity as control is passed among program modules. As a system executes its customary
activities, the intrusion detection scheme should estimate a nominal system behavior.
Departures from the nominal system profile will likely represent potential invidious
activity on the system. Since unwanted activity may be detected by comparison of
the current system activity to that occurring during previous assaults on the system,
it would be desirable to store profiles for recognizing these activities from historical
data. Historical data, however, cannot be used to recognize new kinds of assaults.
An effective security tool would be one designed to recognize assaults as they
occur through the understanding and comparison of the current behavior against
nominal system activity. Currently, none of the prior art techniques fully achieve
these objectives.
SUMMARY OF THE INVENTION
The present invention represents a new software engineering approach to intrusion
detection using dynamic software measurement to assist in the detection of intruders.
Dynamic software measurement provides a framework to analyze the internal behavior
of a system as it executes and makes transitions among its various modules governed
by the structure of a program call graph. A target system is instrumented so that
measurements can be obtained to profile the module activity on the system in real
time. Essentially, this approach measures from the inside of a software system
to make inferences as to what is occurring outside of the program environment.
In contrast, the more traditional approach of the prior art measures or profiles
system activity from system log files and other such patterns of externally observable behavior.
Program modules are distinctly associated with certain functionalities that
a program is capable of performing. As each functionality is executed, it creates
its own distinct signature of transition events. Since the nominal behavior of
a system is more completely understood while it is executing its customary activities,
this nominal system behavior can be profiled quite accurately. Departures from
a nominal system profile represent potential invidious activity on the system.
New profiles of intrusive behavior can be stored and used to construct an historical
database of intrusion profiles. However, these historical data cannot be used as
a basis for the recognition of new types of assaults. The present invention is
designed to recognize assaults as they occur through the understanding and comparison
of the current behavior against nominal system activity.
BRIEF DESCRIPTION OF THE DRAWING FIGURES
The foregoing aspects and many of the attendant advantages of this invention
will become more readily appreciated as the same becomes better understood by reference
to the following detailed description, when taken in conjunction with the accompanying
drawings, wherein:
FIG. 1 is a block diagram illustrating the relationship between instrumented
program modules and a mapping module that generates a sequence of module streams;
FIG. 2 is a block diagram illustrating the operation of a module sequence transducer
of a first kind;
FIG. 3 is a block diagram illustrating the operation of a module sequence transducer
of a second kind;
FIG. 4 is a block diagram illustrating the operation of a module sequence transducer
of a third kind;
FIG. 5 is a block diagram illustrating the operation of a comparator of a first kind;
FIG. 6 is a block diagram illustrating the operation of a comparator of a second kind;
FIG. 7 is a block diagram illustrating the operation of a comparator of a third kind;
FIG. 8 is a block diagram illustrating an environment in which a preferred embodiment
of the present invention operates;
FIG. 9 is an isometric view of a generally conventional computer system suitable
for implementing the present invention; and
FIG. 10 is block diagram showing internal components of the computer system
of FIG. 9.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Environment of the Present Invention
A system operating in accord with the present invention has three modes of operation.
Each of these modes represents an incremental improvement in the ability of the
system to detect an intrusion or abnormal use of the system or program executing
thereon. However, as the resolving ability of the system increases, there is an
associated penalty in processing overhead. In a first mode, simple execution profiles
indicative of modules that have executed are employed for the evaluation of intrusive
activity. This mode is the most coarse grained level of operation for the detection
of intrusions, but it has the least cost in terms of performance of the three modes.
In the second mode, transitions from one program module to the next are recorded,
providing a much finer grained description of program behavior. This second mode
is capable of detecting more subtle forms of attack and is also more costly to
run in terms of the degradation of performance and consumption of computer memory.
In a third mode, sequences of module transitions are mapped onto specific design
specification elements, or functionalities. This third mode of operation can detect
the most subtle of all intrusions, again at a greater expense of computation time
and memory space. FIG. 1 illustrates the internal program environment of a program
that has been suitably instrumented for anomaly and/or intrusion detection. Each
program module, M
i, of a plurality of program modules
101 will
have calls placed in it at each entry point and before each return. Control is
passed to a mapping module
102 that records any transition into and out
of a program module. The mapping module transmits the module transitions to a module
sequence buffer
103 that buffers these data until they are requested from
the external program environment. All of structures
101-
103 are encapsulated
within the operating environment of a program to which the present invention is
applied to detect anomalous behavior or an intrusion.
FIG. 2 shows the operation of a first profile transducer
202. It is the
purpose of first profile transducer
202 to capture module sequence information
201 from the internally instrumented program environment. At intervals determined
by an externally provided sampling engine
204, first profile transducer
201 interrogates module sequence buffer
103, requesting current profile
information. The profile information obtained from the module sequence buffer is
a list of all modules that have executed since the last interrogation, and the
frequencies of their executions. First profile transducer
202 normalizes
each of the module frequencies by dividing them by the total number of module transitions
that have occurred during the sampling interval. These execution profiles are transmitted
to and retained by an execution profile buffer
203.
FIG. 3 shows the operation of a second profile transducer
302. Second
profile transducer
302 captures module sequence information
301 from
the internal instrumented program environment. At intervals determined by an externally
provided sampling engine
304, which is substantially different than the
interval determined by sampling engine
204, the second profile transducer
interrogates module sequence buffer
103 for current profile information.
The profile information requested from the module sequence buffer is the list of
all modules that have executed since the last interrogation and the frequencies
of their executions. Second profile transducer
302 develops a transition
matrix for the current sampling interval. This transition matrix is an n×n
matrix, where the entry in the i
th row and the j
th column
is the frequency with which module i has transferred control to module j during
the current sampling interval. The transition matrix is transmitted to and retained
by a transition matrix buffer
303.
FIG. 4 shows the operation of the third profile transducer. It is the purpose
of a third profile transducer
402 to capture module sequence information
401 from the internal instrumented program environment. At intervals determined
by an externally provided sampling engine
404, the third profile transducer
interrogates module sequence buffer
103 for current profile information.
The profile information requested from the module sequence buffer is the list of
all modules that have executed since the last interrogation and the frequency with
which each module has executed during that interval. Third profile transducer
402
maps the sequence of module transitions representing subtrees on a program call
graph into function sequences through the mapping of program functionalities to
modules. These functional sequences are transmitted to and retained by a functional
sequences buffer
403.
FIG. 5 shows the operation of an execution profile comparator
502. The
execution profile comparator determines any difference (i.e., a differenced profile)
between a current execution profile
501 most recently obtained from first
profile transducer
202 and a nominal execution profile obtained from nominal
profiles data
506, which represents the steady-state behavior of the software
system with no intrusive activity. The nominal profiles data are initially established
by a calibration process that is implemented by running the program in a calibration
mode in which the program is run through as many of the functions and operations
performed during a nominal operational phase. A nominal activity profile and boundary
conditions for variations during this nominal operational phase are accumulated
during this calibration mode. The nominal profile is subsequently modified by a
user (or administrator), if during normal operation of the program an alarm is
raised, but it is determined that no intrusion has occurred. In a typical software
application, there may be a wide range of behavior that is considered nominal.
The computational result of the comparison between the current execution profile
and the steady state behavior of the system represented by the nominal profile
suite is used in two different subsystems. First, if the total variance in the
steady state profile rises above a pre-established threshold, then the recognition
of an intrusive event becomes difficult. In this case, the comparator will increase
the sampling rate set by the sample rate engine. Similarly, the sampling rate may
be decreased when the system is operating in a more quiescent mode to lessen the
impact of the detection process on the total system operation. Second, the differenced
profile is analyzed to determine if it has crossed a predetermined threshold level
that represents an unacceptable departure from the nominal system behavior. If
so, then there is a potential new behavior on the system and a level
1 alarm
503 is raised. The system then attempts to match the differenced profile
with known intrusion profiles data
505. If a match for the differenced profile
is found in the intrusion profile data, then a level
2 alarm
503
is raised, indicating a certainty of an intrusive attack.
FIG. 6 illustrates operation of a transition matrix comparator
602. The
transition matrix comparator determines any difference (i.e., a "differenced matrix")
between a current transition matrix
601 that was most recently obtained
from second profile transducer
302 and a nominal transition matrix obtained
from nominal transitions data
607 representing the steady-state behavior
of the software system with no intrusive activity. The result of the comparison
between the current transition matrix and the steady state behavior of the system
represented by the nominal transitions suite is used in two different subsystems.
First, if the total variance in the steady state profile rises above a predefined
threshold, the comparator will increase the sample rate determined by a sample
rate engine
606. Similarly, the sampling rate may be decreased when the
system is operating in a more quiescent mode to lessen the impact of the detection
process on the total system operation. Second, the differenced matrix is analyzed
to see whether it has crossed a predetermined threshold level that represents an
unacceptable departure from the nominal system behavior. If so, then there is a
potential new behavior on the system and a level
1 alarm
603 will
be raised. Against this potential intrusive behavior, a static call tree
605
structure is stored in a single transition matrix. Embedded in this static call
tree structure is a set of legitimate module transitions. A potentially new intrusive
behavior may be characterized by abnormal transitions in current transition matrix
601. The system attempts to match the differenced matrix with known intrusion
characteristics stored as sequences of characteristic transition matrix data
604.
If a match for the differenced matrix is found in the intrusion transitions data,
then a level
2 alarm
603 is raised, indicating a certainty of an
intrusive attack.
FIG. 7 shows the operation of a functional profile comparator
702, which
behaves similar to execution profile comparator
502. The fundamental difference
between these two comparators is that functional profile comparator
702
operates on functional profiles as opposed to execution profiles. Functional profile
comparator
702 determines any difference ("a differenced profile") between
a most recent functional sequence
701 obtained from third profile transducer
402 and a nominal functional profile obtained from nominal functional profiles
data
706, which represents the steady-state behavior of the software system
with no intrusive activity. The result of the comparison between the most recent
functional sequences and the steady state behavior of the system represented by
the nominal functional profile suite is again used in two different subsystems.
First, if the total variance in the steady state profile rises above a predefined
threshold, the comparator will increase the sample rate determined by a sample
rate engine
705. Similarly, the sampling rate may be decreased when the
system is operating in a more quiescent mode to lessen the impact of the detection
process on the total system operation. Second, the differenced profile will be
analyzed to see whether it has crossed a predetermined threshold level that represents
an unacceptable departure from the nominal system behavior. In this event, there
is a potential new behavior on the system, and a level
1 alarm
703
will be raised. The system then attempts to match this differenced profile with
a known intrusion profile from known intrusion profiles data
704. If a match
for the differenced profile is found in the intrusion profiles data then a level
2 alarm
703 will be raised, indicating a certainty of an intrusive attack.
FIG. 8 shows the relationship among the various components of the intrusion
detection system. A transducer
802 and a comparator
803 are the essential
functional components of the intrusion detection methodology. The transducer obtains
signals from an instrumented software system
801 and computes activity measures
for these signals. The actual software signals may be obtained either from instrumented
code (software probes) or directly from a hardware address bus (a hardware probe).
The inputs to the transducer are software module entry and exit events that may
be obtained either from software or hardware instrumentation.
Depending on the level of resolution desired, the transducer will produce
from the module transition events a summary profile of the execution transitions
(execution profile), a transition matrix representing the frequency of transition
events from one module to another, or a function sequence of program activity.
The transducer interacts with the software system in real-time. That is, all transition
events are available to the transducer as they occur.
The output of transducer
802 is sent directly to comparator
803
for analysis. The rate at which these data are obtained is controlled by the comparator.
During periods of relatively light computational activity when there is little
likelihood of an intrusion, the sampling interval might be set to be relatively
long. Alternatively, during periods of extensive system activity, the sampling
frequency can be increased to provide increased resolution on system activity.
All sampling activity is measured in system epochs, or module transitions. The
sampling rate
810 is controlled by the sample rate engine (not separately
shown) associated with the comparator.
Each activity measure
808 is obtained from transducer
802 by comparator
803. The comparator makes a formal assessment as to whether the current
system activity is non-threatening (nominal) or otherwise. There are essentially
two types of non-nominal activity. The first occurs as new users or new programs
are being run on the system. This new activity is reviewed by an external decision
maker, such as the system administrator, and if determined to be non-threatening
by that person, is added to the system repertoire of nominal behavior in an intrusion
database
805. However, the observed activity may represent an intrusion
event. There are two types of intrusion events. First, there are existing or known
intrusion events. These have well-known and established intrusion profiles that
are stored in intrusion database
805. Comparator
803 will search
intrusion database
805 for a matching profile, and if it finds a matching
profile, will raise a level
2 alarm
807. A level
2 alarm means
that there is a high level of certainty that an intrusion event is in progress.
If, on the other hand, the intrusion event is not found in intrusion database
805,
comparator
803 will raise a level
1 alarm
807, indicating
that new behavior has been observed on the system. Typically, the level
1
alarm system would be referred to a system administrator and/or an artificial intelligence
(AI) engine for review.
The ability to recognize an actual intrusion event is dependent on the variance
in the profiles of software activity. This variation may be controlled by varying
the sampling rate of the instrumented software. The sampling rate is controlled
by a sensitivity adjustment
804, which can be designed into the software
and/or controlled by input from the system administrator.
To enhance the overall viability of the system to detect new and unobserved intrusion
events, a visualizer
806 may optionally be added to the system. This visualizer
receives a data stream
809 from the comparator and graphically displays
module transition information in a continuous recording strip on a display terminal
(not separately shown). The moving image of system activity closely resembles a
side-scan sonar display. Module (or functionality) frequency data are displayed
to render a visual image of overall system activity. Human pattern recognition
ability currently greatly surpasses that of any available software. The visualizer
provides a real-time image of system activity from which abnormal activity may
be detected by a system administrator using this superior pattern recognition capability.
A Profile-Oriented Anomaly Detection Model
As any software system is being specified, designed and developed, it is constructed
to perform a distinct set of mutually exclusive operations O for the customer.
An example of such an operation might be the activity of adding a new user to a
computer system. At the software level, these operations must be reduced to a well
defined set of functions F. These functions represent the decomposition of operations
into sub-problems that may be implemented on computer systems. The operation of
adding a new user to the system might involve the functional activities of changing
from the current directory to a password file, updating the password file, establishing
user authorizations, and creating a new file for the new user. During the software
design process, the basic functions are mapped by system designers to specific
software program modules that implement the functionality.
From the standpoint of computer security, not all operations are equal. Some
user operations may have little or no impact on computer security considerations.
Other operations, such as system maintenance activities, have a much greater impact
on security. System maintenance activities being performed by system administrators
would be considered nominal system behavior. System maintenance activities being
performed by dial-up users, on the other hand, would not be considered nominal
system behavior. In order to implement this decomposition process, a formal description
of these relationships must be established. To assist in the subsequent discussion
of program functionality, it will be useful to make this description somewhat more
precise by introducing some notation conveniences.
Formal Description of Software Operation
Assume that a software system S was designed to implement a specific set of
mutually exclusive functionalities F. Thus, if the system is executing a function
ƒ∈F, then it cannot be expressing elements of any other functionality
in F. Each of these functions in F was designed to implement a set of software
specifications based on a user's requirements. From a user's perspective, this
software system will implement a specific set of operations O. This mapping from
the set of user perceived operations O to a set of specific program functionalities
is one of the major functions in the software specification process. It is possible,
then, to define a relation IMPLEMENTS over O×F such that IMPLEMENTS(o, ƒ)
is true if functionality ƒ is used in the specification of an operation o.
From a computer security standpoint, operations can be envisioned as the set
of services available to a user (e.g., login, open a file, write to a device),
and functionalities as the set of internal operations that implement a particular
operation (e.g., user-id validation, access control list (ACL) lookup, labeling).
When viewed from this perspective, it is apparent that user operations, which may
appear to be non-security relevant, may actually be implemented with security relevant
functionalities (send mail is a classic example of this, an inoffensive operation
of send mail can be transformed into an attack, if the functionalities that deal
with buffers are thereby overloaded).
The software design process is strictly a matter of assigning functionalities
in F to specific program modules m∈M, the set of program modules of system
S. The design process may be thought of as the process of defining a set of relations
ASSIGNS over F×M, such that ASSIGNS(ƒ, m) is true if functionality ƒ
is expressed in module m. For a given software system S, let M denote the set of
all program modules for that system. For each function ƒ∈F, there
is a relation p over F×M such that p(ƒ, m) is the proportion of execution
events of module m when the system is executing function ƒ.
Each operation that a system may perform for a user may be thought of as having
been implemented in a set of functional specifications. There may be a one-to-one
mapping between the user's notion of an operation and a program function. In most
cases, however, there may be several discrete functions that must be executed to
express the user's concept of an operation. For each operation o that the system
may perform, the range of functionalities ƒ must be well known. Within each
operation, one or more of the system's functionalities will be expressed.
The Software Epoch
When a program is executing a functionality, it apportions its activities among
a set of modules. As such, it transitions from one module to the next on a call
(or return) sequence. Each module called in this call sequence will have an associated
call frequency. When the software is subjected to a series of unique and distinct
functional expressions, there is a different behavior for each of the user's operations,
in that each will implement a different set of functions, which, in turn, invoke
possibly different sets of program modules.
An epoch begins with the onset of execution in a particular module and ends when
control is passed to another module. The measurable event for modeling purposes
is this transition among the program modules. Calls from a module are accumulated,
along with returns to that module, to produce a total count. Each of these transitions
to a different program module from the one currently executing represents an incremental
change in the epoch number. Computer programs executing in their normal mode make
state transitions between program modules rather rapidly. In terms of real clock
time, many epochs may elapse in a relatively short period.
Formal Definitions of Profiles
It can be seen that there is a distinct relationship between any given operation
o and a given set of program modules. That is, if the user performs a particular
operation, then this operation manifests itself in certain modules receiving control.
It is also possible to detect, inversely, which program operations are being executed
by observing the pattern of modules executing, i.e., the module profile. In a sense
then, the mapping of operations to modules and the mapping of modules to operations
is reflexive.
It is a most unfortunate accident of most software design efforts that there
are
really two distinct set of operations. On the one hand, there is a set of explicit
operations O
E. These are the intended operations that appear in the
Software Requirements Specification documents. On the other hand, there is also
a set of implicit operations O
I that represents unadvertised features
of the software, which have been implemented through designer carelessness or ignorance.
These implicit operations are neither documented nor well known except by a group
of knowledgeable and/or patient system specialists, called hackers.
Since the set of implicit operations O
I is not well known for most
systems, most system administrators are obliged to learn about implicit operations
by carefully investigating program behavior, or by experiencing the unfortunate
results of an intrusion by someone who has learned about these operations. Hackers
and other interested citizens will find implicit operations and exploit them. What
is known is the set of operations O
E and the mappings of the operations
onto the set of modules M. For each of the explicit operations there is an associated
module profile. That is, if an explicit operation is executed, then a well-defined
set of modules will execute in a very predictable fashion. This fact may be exploited
to develop a reasonable profile of the system when it is executing operations from
the set of explicit operations. This nominal system behavior serves as a stable
reference against which intrusive activity may be measured. That is, when an observation
is made of module profiles that is not representative of the operations in O
E,
an assumption may be made that the new observation is one or more operations from
the set O
I; in other words, there is an intruder present.
When the process of software requirements specification is complete, a system
consisting of a set of a mutually exclusive operations will have been defined.
Characteristically, each user of a new system will cause each operation to be performed
at a potentially different rate than another user. Each user, then, will induce
a probability distribution on the set O of mutually exclusive operations. This
probability function is a multinomial distribution and constitutes the operational
profile for that user.
The operational profile of a software system is the set of unconditional probabilities
of each of the operations in O being executed by the user. Then, Pr[X=k], k=1,
2, . . . , |O| is the probability that the user is executing program operation
k as specified in the functional requirements of the program and ∥O∥
is the cardinality of the set of operations. A program executing on a serial machine
can only be executing one operation at a time. The distribution of the operational
profile is thus multinomial for programs designed to fulfill more than two distinct operations.
A user performing the various operations on a system causes each operation to
occur
in a series of steps or transitions. The transition from one operation to another
may be described as a stochastic process. In this case, an indexed collection of
random variables {X
t} may be defined, where the index t runs through
a set of non-negative integers t=0, 1, 2, . . . representing the individual transitions
or intervals of the process. At any particular interval, the user is found to be
expressing exactly one of the system's a operations. The fact of the execution
occurring in a particular operation is a state of the user. During any interval,
the user is found performing exactly one of a finite number of mutually exclusive
and exhaustive states that may be labeled 0, 1, 2, . . . a. In this representation
of the system, there is a stochastic process {X
t}, where the random
variables are observed at intervals t=1, 2, . . . and where each random variable
may take on any one of the (a+1) integers, from the state space O={0, 1, 2, . .
. , a}.
Each user may potentially bring his/her own distinct behavior to the system.
Thus, each user will have a unique characteristic operational profile. It is a
characteristic, then, of each user to induce a probability function p
i=Pr[X=i]
on the set of operations O. In that these operations are mutually exclusive, the
induced probability function is a multinomial distribution.
As the system progresses through the steps in the software lifecycle, the user
requirements specifications, the set O must be mapped on a specific set of functionalities
F by systems designers. This set F is in fact the design specifications for the
system. As per the earlier discussion, each operation is implemented by
