We first give an overview of computer security and the development of misuse detection systems. This is followed by a discussion on the processes in misuse detection model together with the approaches and techniques employed. A survey of existing misuse detection systems is conducted. Finally, a conjecture of how future generation of misuse detection systems should focus is given which motivates us to conduct research in misuse detection in database systems.

A secure computer system should provide confidentiality, integrity and availability of service. These system properties can be specified explicitly by security policies - what actions a subject can or cannot perform on objects under specified conditions. Subjects are active components of the system, such as legitimate users or processes running on behalf of the users. Objects are passive components and are typically entities to protect, such as files, memory blocks. The security policies are enforced by security mechanisms. Compromising the security mechanisms is intrusion. The set of events specified by security policies seldom equals the set allowed by the security mechanisms. Insider abuse occurs if legitimate users violate the security policies without compromising the security mechanisms. Misuse includes both intrusion and insider abuse.

The increased connectivity between computer systems has opened up many possibilities of attacks. Examples of intrusive attacks are: attempted break-in (unauthorized users try to gain access to the system, typically associated with a high rate of login failures), tempered executables (Trojan horses or viruses, associated with atypical CPU and I/O activity, frequency of executables rewritten), denial of service (other users are denied access to certain services, associated with atypical usage pattern of system resources), leakage ( attacker tries to leak information (e.g. covert channel), associated with atypical use of system resources), masquerade attack (an intruder tries to masquerade as a legitimate user, associated with, for instance, abnormal login time, location, connection type, different types of processes executed), malicious use (Legitimate users exploit their privileges, such as inference, aggregation, penetration, associated with excessive protection violation, directories browsing).

Although it is desirable to prevent these intrusive activities, building a totally secure system is difficult, if not impossible. This would require complete knowledge of possible attacks, system components and their interactions. Known security flaws may not be fixed and insecure systems may not be replaced because of economical and practical reasons. The audit records are too volumous to be analyzed manually by security officers (SSO) - which is typically a group of system administrators responsible for specifying and enforcing the security policies of the organization. Further, the cost of prevention is high and prevention limits users' access to the system. Therefore instead of focusing on prevention, attention has been given to misuse detection systems (MDSs). (Intrusion Detection System IDS is often used instead of MDS. However, the term IDS is confusing under the author's definition of intrusion and misuse. Since most systems detect both intrusion and insider abuses, we will adopt the terminology MDS.)

The study of misuse detection systems began with Jim Anderson's work in 1980s on categorizing threats. Anderson analyzed audit trail and classified threats into several categories: external penetrators (who are not authorized to use the computer), internal penetrators (who are authorized to use the computer, but not certain data) and misfeasors (who are authorized to use both the computer and data, but abuse their privileges). He proceeded to suggest ways to detect these threats by associating the threats with abnormal and known suspicious patterns in the audit trail. This is based on the assumptions that misuse behavior exhibits distinguishable patterns from normal usage behavior and that these patterns are reflected in the audit trail.

These assumptions were soon verified by the Sytek work which tested the discriminating ability of interesting audit record fields between normal sessions and sessions with simulated intrusions. Values of features that are good indicators are significantly different between normal sessions and sessions with intrusions. They include password changed, subject identity queried, access to system dictionary, device on which the accessed file resides, file size, oversized file associated with the command, group id and user id of the owner of the accessed file, time and day of use, subject program CPU time and maximum total memory use.

The processes in a typical MDS are (1) data collection, (2) data pre-processing, (3) misuse detection and (4) response. A MDS may iterate over the processes.

In data collection, the necessary information is collected and stored in the audit logs. The key issue is what to audit which in turn depends on what we want to detect. Inference in database systems requires auditing at record level whereas auditing at file level suffices for denial of service attacks. The level of auditing (e.g. at user command level or system calls level) needs to be decided as well. We also need to determine what features are relevant to misuse detection. Contrary to intuition, more features are not better. For one thing, it is neither space nor computation efficient. For the other, irrelevant features add noise to the data, which makes it more difficult to distinguish between normal and abnormal behavior. More features add complexity to anomaly detection approaches that are based on machine learning, which requires more samples for the same degree of accuracy. An interesting direction to pursue would be to dynamically select what to monitor based on some preliminary analysis or history of the subject behavior. Another question that needs to be addressed is when to collect the data. If data are collected before the process terminates, we can collect information for both successful and unsuccessful attempts and possibly react to intrusive attacks before it is too late. If data are collected after the process terminates, it is possible to measure the usage patterns of the process, such as resource utilization, exception conditions generated. Most systems collect the data before and after the process terminates. A challenge in this process is to manage the huge amount of audit data. This can be achieved by aggregating the data, such as using some statistical model to represent past records and only keep detailed information for the most current sequence of events.

The second process is data pre-processing. Upon receiving the audit records, a component of the MDS pre-processes them into a format that is understandable to other components of the system. This includes handling noisy and missing data, data type mapping, condensing representation. A challenge here is to map numerical features to categorical features or vice versa if the detection engine only support data of one type. Numerical features can be clustered into categories whereas binary categorical features can be assigned to the values 0 or 1. Auditing has to be done on the target system, but MDS can be as a separate system from the target system or can reside on the target system. This opens up the possibility of how much autonomy the auditing system should have. In the former case, MDS has no control over the auditing system and hence the audit records may not contain all the information needed by the MDS. The MDS has to perform mapping of the audit records to its own format, yet most auditing systems provide little or no descriptive information about the format of their audit logs. Since MDS is separate from the target system, compromising the target system does not affect the MDS. The latter approach has the advantage that MDS can have control of what to audit and knows what is audited. In both cases, it is assumed that the audit logs are not tampered, which is a weaker assumption to make in the latter case as the MDS and target system are tightly coupled.

The next step is to characterize what is normal and what is abnormal. In profile based approaches, the profiles characterize normal subject behavior. A profile, specified in a language, states what operations the subject typically take or does not take on the objects and under what conditions. It should be noted that profiles can never be complete. Profiles can be generated with respect to a single subject, a user group or classes of audit records with the same values of certain parameters. In signature based approaches, the database of signatures for known intrusive events is created. To detect intrusive events, new audit records are compared against the profiles or signatures. If the features in the audit records deviate from the profiles or the audit records match the known signatures in the database, alarm is raised. In specification based approaches, misuse is detected if the system deviates from its specified expected behavior. Effectiveness of the detection depends on how well the profiles are derived, and on the accuracy and completeness of the domain knowledge of the SSO in formalizing the database of signatures and descriptions of system components. The following session provides more detailed discussion on the approaches in this process.

When intrusive events are suspected, the MDS can respond in several ways. A type of responds are passive responds. This includes informing the SSO. MDS can aid the SSO by generating summary reports so that the SSO do not need to analyze huge amount of audit data. The MDS can also provide an explanation for the likely cause of the intrusive events. The data MDS generates can be fed to other systems for, say, visualization. When suspicious activities are raised, the MDS can also respond by focusing on the suspicious user by refining the level of auditing. Another type of responds are active responds. An aggressive MDS can react to the malicious users by terminating his/her account, revoking his/her privileges, giving noisy query results or even silently inject tampered programs to the malicious user's account. What type of response to take depends on the specifications by SSO.

We need to evaluate the MDSs. Several criteria to evaluate an MDS have been proposed. These include soundness (Does the MDS really detect intrusive events?), effectiveness (Can it distinguish between anomalies due to intrusion/misuse and other factors? What is the false alarm rate?), completeness (Can it detect all intrusive events?), timeliness (Can it detect fast enough to take appropriate action?), social implication (How does it affect the user community (psychological and legal aspects)?) and cost (What is the effect on the system performance on the target system?).

Dorothy Denning suggests a generic and system independent model for MDS. Many MDSs developed since are based on this model. These systems basically employ three approaches, namely profile based, signature based and specification based. Each approach has its pros and cons and hence most MDSs use a hybrid-approach.

In profile based approaches, it is assumed that the set of intrusive events equals the set of anomalous events. Profiles for subjects are derived and maintained to characterize the normal subject behavior. If too many audit records deviate from the profiles, alarm is raised. It is worth mentioning that when an anomaly detector detects abnormal patterns, it may not indicate the system is compromised, but that the subject exhibits a sudden change in his/her behavior. Also, a user may not have distinguishable patterns or may change his/her behavior frequently. Certain features that give high true positive rate also give high false positive rate. Security officers need to determine a threshold level above which the behavior is flagged abnormal. If the threshold is set too low for good detection ability, high false positive rate results. The challenge is to balance the sensitivity to intrusive events and the false alarm rates. Designers of anomaly detectors need to face certain technical challenges such as how to initialize the parameters when the system just starts up or when a new user is added. A solution is to initialize the subject profile from a generic profile of his/her user group. System parameters can be adjusted to lower sensitivity initially and gradually tightened as more data are collected. It takes some time for the system to stabilize. Malicious user can gradually change his/her behavior or perform malicious tasks little by little so that the anomaly is not detected. A database of past user sessions needs to be maintained by the system and more weight can be assigned to recent audit records to detect such gradual change.

In signature based approaches, it is assumed that intrusive events exhibit certain distinguishing patterns from normal events. These patterns give the signatures for the intrusive events. The signatures can be based on observed activities. For example, the way to exploit a known system hole may consist of a sequence of particular commands. If a user executes commands that are from another type of operating system, it is likely that the user is an intruder. The signatures can also be based on physical characteristics of legitimate users, such as the timing between keystrokes or common mistakes made by legitimate users. Though not realized, the signatures can serve as an intruder profile, much like criminal profiles for different types of criminals. An example is that a paranoid intruder often checks if other system administrators are logged on right after he/she has gained access to the system. A severe limitation of signature based approaches is that they can only detect known attacks but fail to recognize new attacks. The patterns for some intrusive attacks may be too difficult to formalize. The patterns selected for a class of intrusive attacks have to be present in most of the intrusive attacks and they have to be distinguishing from normal events. The completeness and accuracy of the database of known misuse patterns very much depend on the knowledge of the SSO who define those patterns. In specification-based approaches, the expected system behavior is specified. Data about system activities are collected to detect any deviation from the expected system behavior. For example, temporal reasoning systems predict the next event given a sequence of events. The input is a sequence of events (episodes). The system generates temporal patterns of typical usage pattern. They are rules of the form E1 -> E2 -> (E3=0.95, E4=0.05). This means given E2 occurs after E1, there is a 95% chance the next event is E3 and 5% chance of being E4. An event in an episode that does not match predicted events of the episode in the rule is caught as deviation from normal usage. An episode that does not match any rules is caught as unrecognized activity which can, in turn, be treated by default as normal (may result high false negatives) or abnormal (may result in high false positives). UCDavis designed a program policy specification language based on predicate logic and regular expressions to describe the expected restricted behavior of privileged programs. The program policies are surprisingly concise and clear. Misuse is detected by deviation from the program specification. For specification based approaches to work, the objects under consideration have to exhibit well-defined behavior.

There are two classes of techniques that are widely used by MDSs.

The first class of technique uses statistical models. Past audit records are used to compute the values of the parameters in a statistical model. When a new audit record is received, it is compared with the parameters which represent past subject behavior. If large deviation is observed, the record is anomalous. The complexity of the models can range from operational model, mean and standard deviation model, multivariate model, Markov process model to time series model. Deciding which model to use depends on the intrusive events to detect. An operational model is suitable for monitoring attempted break-ins by recording the number of login failures. A Markov process model and time series model are desirable when sequence of the records should be taken into account. A problem with statistical technique is that it requires a prior knowledge of the probability distribution of certain features. Independence between features is often assumed which is not the case in reality. Unfortunately, covariance between features are often computationally expensive to incorporate into the system. Audit data are often categorical in nature. Transformation from categorical data into numerical data are necessary before statistical techniques can be applied. Interpretation of the statistics is not intuitive and it is difficult to incorporate domain knowledge into the algorithms. Statistical approaches are not sensitive to gradual change in subject behavior. A solution is to assign more weights to recent records.

The second class of techniques borrows methods from artificial intelligence and machine learning. An example is expert systems which are often used in MDSs. In the learning phase, the system generates profiles which are stored in a rule base from a set of training samples. The rules can be generated from some templates specified by SSO. The templates give heuristics to guide the system to generate rules. In some systems, the rules can be generated automatically from historical data by inductive concept learning. Then the rule base is used to detect anomalies. New audit records are matched against the rule base. If a record matches the conditions of a rule but violates the conclusion, the record is anomalous. Alarm is raised if there are too many anomalous records or a record is highly anomalous based on some score to measure its degree of anomaly. The rule base technique can also be applied to detect known attack patterns. In this case, the rules specify the signatures of known intrusive events. They can also be used to specify the security policies of the organization or what actions the MDS should take upon certain changes in system states. An advantage of expert systems is that domain knowledge is easily incorporated. Technical challenges are how to assign confidence levels to the rules. Rules with less noise, occur more often frequently, more specific and are based on clear observations should carry more weights. Other issues are how to handle inconsistent rules and how to keep the size of the rule base manageable. Yet the completeness and accuracy of the rules very much depends on the knowledge of the SSO. Clustering, classification and neural networks are also used in some MDSs. A problem with these techniques is that, unlike the statistical techniques, they assume noise free data sets. Extensions to some of the algorithms are derived to handle noisy data. Machine learning techniques do not scale well with respect to the size of the data and the number of features though extensions are being designed to improve their scalability. The success of the techniques depends on how much domain knowledge is input to the system.

MDSs can be categorized as active or inactive. In response to misuse, active MDSs take action to change the system, such as counter-attack or revoking the rights of malicious users, while passive MDSs only respond passively, such as generating reports. Another axis is how MDSs interact with target systems. MDSs can be tightly coupled with target systems in which case autonomy of target systems is reduced. For example, MDSs can give feedback to target systems as what to audit. Loosely coupled MDSs do not interfere with the operations of target systems.

MDSs can be categorized according to their source of audit data. Host based MDSs analyze audit data from single hosts while network based MDSs analyze audit data from a collection of hosts in a network. The first generation of MDSs developed in the '80s are host based systems which monitor single target systems. A host based MDS has only information about the target system and data collected is at the operating system or network level. Examples are IDES (later NIDES), Haystack, MIDAS and Wisdom and Sense. Host based MDSs only have information about the single hosts. Nevertheless, the proliferation of heterogeneous computer networks has increased the connectivity of computer systems and hence has given greater access to outsiders to a computer system. Audit trail from a single host alone is not as effective as aggregating information across the network in detecting intrusion. This advocates the second generation of MDS which is based on a heterogeneous collection of network hosts. The MDS monitors the traffic of the network and hence has information about the connected systems. The aggregated information gives them more capability to detect intrusion attacks across the network. MDSs of this generation gear towards a distributed architecture - not only is data collection distributed, but also the analysis of the audit trail - and scalability with respect to the number of network nodes is an important goal. The second generation MDSs are still under development and not all these goals have been achieved. Examples of second generation MDSs are NSM, NADIR, DMDS and GrIDS.

Intrusion Detection Expert System (IDES, later NIDES) was developed by SRI in 1980's. It receives operating system audit trails from a single host via a network. Certain system-wide parameters are monitored, including categorical features (such as names of accessed files, terminal IDs, names of remote hosts used), ordinal features (such as CPU time, I/O amount, failed login attempts), intensity features (which track the number of audit records occurring in different time intervals to reflect bursts of activities) and distribution features (which track all activity types that have been generated in the recent past to detect the distribution of activity types). These audit data are put into a generic audit record format for system independence.

It has an expert system that contains rules describing suspicious behavior and known system vulnerabilities which are independent of the past behavior of the subjects. Audit data are matched against this database for known misuse patterns.

IDES also has a statistical anomaly detector that compares the present short-term behavior of a subject with his/her past long-term behavior. Subject profiles are kept for the subjects which describe their expected behavior with respect to the features monitored. The profiles are updated daily and aged by exponential decay with half life of 30 days. The monitored features form a N-space. Anomaly is detected if the corresponding point of the new audit record in the N-space is significantly far from the point defined by the expected subject behavior in the profile. Degree of abnormality is measured by a single test statistic value T^2. Critical values for different levels of concern are selected so that the SSO are informed if T^2 exceeds the critical value. Different versions of the test statistics are defined and the choice depends on the type of subject behavior, the type of system and the type of subject activity. Calculation of T^2 statistics for intense features requires knowledge of their historical distribution.

Haystack is a offline MDS developed for US Air Force computer systems in 1988. It is designed for military systems which have explicit security policies. The data are unclassified but sensitive and the primary threats are aggregation, privacy and modification of data. It uses statistical techniques to detect abnormal behavior by comparing against a set of known computer abuses such as attempted break-ins, masquerade attacks, penetration of security perimeters, leakage, denial of service, malicious use, and the creation and propagation of viruses. The only data type supported is counting features such as amount of I/O, amount of CPU, number of files accessed. Based on some observed values of the features, Haystack defines a range of values that are considered normal for each feature. It considers a set of six generic types of computer abuses, each associated with a set of features and their corresponding weight to that type of abuse. If during a session, a feature falls outside the normal range, the score for the subject is raised. Assuming the features are independent, the probability distribution of the scores is calculated. Alarm is raised if the score is too large. Haystack also has a anomaly detector component which performs simple statistical test to detect changes in median values of the features.

Haystack is an early design of MDS using statistical techniques and therefore it is not surprising that the techniques used are not sophisticated. One problem with Haystack is that the weights of different features towards different types of computer abuses are chosen by the SSO. No test has been conducted to test its sensitivity to different intrusion patterns and no reason has been given as to how the weights are assigned. The assumption that the features are statistically independent often does not hold in reality. The only data type supported is counting feature, which is very limited.

MIDAS is an expert system developed for US National Computer Security Center Multics-based networked environment at 1988. MIDAS encodes a prior rules that define known intrusive patterns. Immediate rules do not depend on subject behavior. They are used to detect events that are considered suspicious in isolation from any other consideration. Sensitive path rules encode command sequences similar to known attacks. MIDAS also uses statistical approach to derive the subject profiles which are stored as rules. The features monitored are user commands, usual access times, location of the subject and expected typing rate of the subject. The profile is updated at the end of each session. It also keeps a system-wide profile to characterize what is normal for the system globally. Data is collected from a command monitor and the auditing system at user command line level. When an audit data are inserted into the fact base, some rules are fired. If the current audit record falls outside the normal values defined by the rules fired, anomaly is detected. MIDAS is real time and is capable of detecting attempted break-ins, masquerade, penetration, malicious use, Trojan horses and viruses.

Wisdom and Sense (W&S) is any anomaly detection expert system which was developed at Los Alamos National Laboratory LANL in 1984. The audit data are periodically received from the target system. Wisdom and Sense supports categorical features such as login location, terminal type. Numerical features are clustered into ranges with equal number of data points (bucket). Normal buckets (those with high density) then define the legal values for the features. For categorical data, the least frequent ones are tagged anomalous. The normal range of values of the features give the profiles for the subjects which are stored in a rule forest. When a subject executes a sequence of n events (a event is a low level feature such as login location), the first n-1 events are used to match rules in the rule forest. A score is raised if the nth event does not match the RHS of the rule. Anomaly is detected if the score is too high. W&S tends to conclude a audit record is anomalous if the first n-1 events do not match any rule in the rule base.

Profiles are generated automatically. Rule are pruned discarding rules with low grades (specific rules based on clear observations are given higher grades), or with many different acceptable values. Conflicts in rules are resolved by weighting and scaling or reconciled by SSO. The rule base is very large and highly redundant, but can be generated within an hour and can be searched in less than 0.05 second, making W&S capable of real time misuse detection.

NADIR is designed for Los Alamos National Laboratory's Integrated Computing Network (ICN). NADIR receives audit record from the Network Security Controller (which provides user authentication and access control), Common File System (which stores data) and Security Assurance Machine (which authenticates and records attempts to degrade the security level of data). It aggregates the audit data for individual users into weekly summaries which are compared against a set of built-in expert rules. The rules are obtained from audit trail analysis and interviews with SSO which state known misuse patterns and security policies. Each rule is assigned a level-of-interest. If the sum of the level-of-interest of the rules triggered by a user is too high, alarm is raised.

Network Security Monitor was developed at the University of California, Davis. The network topology NSM monitors is a hierarchically-structured Interconnected Computing Environment. Unlike other MDS, the data NSM analyzes is network traffic data. It cannot monitor network traffic from dial-up line or encrypted network traffic. The network traffic data are organized into 6 layers of abstractions. The packet l