Related work -- Intrusion detection

In the previous discussion on what to monitor in Section 4, some possible techniques and some differences regarding what is sensible to monitor were mentioned. In this section these issues are discussed in more depth and some of the encountered approaches and their respective merits and drawbacks are discussed.

What are intrusion Detection Systems?

This discussion is based on the classifications of [27,42].

In [42], Sundaram gives a compelling list of arguments to why the hope to design a completely secure system is not feasible in practice:

• Bugs in operating systems and common programs indicate that it is impossible in practice, and even if possible extremely difficult and expensive,to write a completely secure system.
• Transition to such a system for use in the entire world would be an equally difficult task.
• Cryptographic methods can be compromised if the passwords and keys are stolen.
• No matter how secure a system is, it is vulnerable to insiders who abuse their privileges.
• There is an inverse relationship between the level of access control and efficiency. More access controls make a system less user-friendly and more likely of not being used.

To this list should be added the new risks occurring if the programs used on the computer cannot be completely trusted, which was the main incentive for this paper. A secure system would require certified ways for new programs to be added to the system and in an Internet-setting this would require a vast bureaucracy, reduce the speed of which new programs can be introduced and would be expensive.

The conclusion that has to be drawn is that the computers will have to operate in a world where executing a program involves a certain risk. The role of an Intrusion Detection system is to operate in such an ``imperfect'' world and to give guidance and indicate where things might have gone wrong. An Intrusion Detection system is a program (or set of programs) that analyzes what happens or has happened during an execution and tries to find indications that the computer has been misused.

Most Intrusion Detection systems to date have focused mainly on detecting break-ins, attempted break-ins and other ways of subverting the host's security policy. The niche for the security assistant is to monitor programs on the computer, even programs operating within their restrictions. The rationale for this is that it is in practice impossible to grant a program any (or the correct minimal set of) privileges without to some extent having to trust that it will not misuse its privileges. The security assistant is a tool for managing this risk by giving the user a way to detect if the trust has been misused by the program.

A main performance criteria of a runtime-monitoring system is that it shows graceful degradation, i.e it must never be completely subverted even if parts of it can be circumvented. An example of non-graceful degradation is when someone gains root-privileges in Unix. If someone gains root-privileges all access-restrictions are by-passed, and even the traces of the activities can be erased, if it is known what activities are traced. In this perspective, there are at least two arguments for redundant monitoring. If what is monitored constantly changes and is continuously updated it is very hard to cover the tracks of the malicious activity. This is the security by obscurity argument. Secondly, it will also be very hard and hence cost-inefficient to develop a program that covertly misuses the computer. This low-incentive argument holds that there will be fewer malicious programs since the cost of creating them is higher than the cost of accessing the services in the proper way.

The idea of Intrusion Detection systems is in itself not a new one [3]. However, it is still an active field of research with many open questions. Some of the key issues are:

• What to measure. When the behavior of the program is to be explained, what are the most appropriate measures/categories to measure. See e.g [27] for a list of some possible aspects of what to monitor.

• Setting and updating thresholds of when to signal. How to automatically learn and update these thresholds. Some approaches are [9,37].

• How to reduce the need to store the vast amounts of data generated, and how too quickly find patterns or indications of misuse in this data. [14,29].

• How to combine the output of the several different sources of information into a manageable, consistent picture of the activities.

Approaches to Intrusion Detection Systems

The techniques for Intrusion Detection can be divided into two main categories; Anomaly Detection and Misuse Detection. These techniques correspond to detecting deviations from a known behavior and detecting known attacks in the current behavior, respectively. The premise of anomaly detection is that intrusive activity is a subset of anomalous activity [23]. Thus, since this relationship is a conjecture, when trying to detect anomalies there is always a risk that either non-intrusive behavior is classified as intrusive (false positives) or that intrusive but non-anomalous behavior is not detected. If misuse is the target for detection, its is supposed that the possible types of attacks are all known or can be detected, hence the problem is how to discover previously unknown attacks.

There are many conceivable ways to analyze the gathered data. In principle they can be rule-based, focusing on certain patterns or chains of events, or use statistical change detection measures, here taken to include all methods where frequencies, intensities and distributions of events or probabilistic estimates of whether a pattern is contained in the data are considered relevant for detection malicious activities.

Approaches to Statistical Change Detection

Statistical Change Detection measures are compiled using data of previous behavior. Since they base their warnings on actual use patterns they can adapt to behaviors, and thus create their own rules for use-patterns not easily discerned by a human. E.g if someone never uses a word-processor to read plain ASCII text files, this would be noted and enforced by a statistical component. Note that doing this is a perfectly legal action, however the fact that the user in practice never does this is taken advantage of to constrain the accepted behavior. The avoidance of specific rules help in making the security more site-specific since the thresholds for what is allowed will vary between sites.

Whenever a component is trained, the training data has to be free from malicious activity or this will be included as proper behavior. If the system adapts its thresholds to the users activities it is also susceptible to programs that slowly change their behavior. The issue of what aspects of a program's (or a user's) behavior to measure is still an open research question. In many approaches, the correlation or ordering of events is not taken into account,

Some of the suggested approaches to analyze the behavior with statistical change detection measures are:

• The intensity or count of a certain activity can be taken as a measure of malicious activity. E.g can a rapid number of connections be taken as an indication that a port-walking attack is underway. Another example is that an abnormally high count for CPU-cycles or memory used can indicate a denial-of-service attack [9]. A coarse measure such as the number of events not accounted for by any other sensor would be a counting measure.

• The relative distribution of events shows if the program uses more of a certain category of resources than others [20]. An example could be a complier that usually just accesses files in the current directory, but occasionally accesses header-files in other directories. If the proportion of what files are accessed changes it might indicate malicious behavior.

• Predictive pattern generation calculates the probabilities of what will be the program's next action in the light of the program's recent behavior. If the next action is one with a low-probability estimate, this indicates that that the program's behavior has changed from what was expected. Some approaches are using Bayesian networks [45], Markov-chain models [37] or sequence matching [13]. The requirement that the system has to be trained is in some cases to strong. If the monitored programs are mobile agents, the short interaction with the program makes it infeasible to gather historical data about it. However, for applications such as Netscape-plugins, these measures are probably useful.

Rules

Statistical Change Detection methods fail to give more precise information about how a program misbehaved and can only tell whether something changed. Rules have to be pre-specified but can then give explicit feedback to the user what rule was broken and how. E.g if a rule states that an application must only access files with certain names, then the rule can easily communicate to the user what caused the rule to be broken. Rules can use pattern matching techniques to find exact matches of a certain behavior or use approximative methods to find the most likely candidate to explain an observed behavior. Some of the suggested approaches to analyzing/constraining the behavior with rules are:

• Ko et. al [22] create an abstract program description of what a program is supposed to do. The abstract program contains conditions that have to be fulfilled for the program to be allowed to execute.
• Levitt et. al [25] extend the AFS so that programs, as well as users, can get access restrictions. In addition to files, restrictions can also be set on file system operations, such as mkdir, rm etc.

• Kephart [21] suggests (amongst other things) that decoy programs and files can be put into the file system to attract misfeasors or viruses. Only monitoring for activity regarding these files is much less resource-consuming.

• MCF [26] analyzes the program for known patterns of malicious behavior. The program is analyzed for code-parts that are independent of the user's activities, e.g logic-bombs or covert-communication. MCF is a tool for a security analyst that helps visualizing relevant parts of a program and not a stand-alone supervisor-program.

• Occurrences of known misuse patterns can be estimated with statistical measures. GASSATA [29] uses genetic algorithms to detect whether a large data set contains the events necessary for executing a particular attack.

Related Projects

Examining programs using Intrusion Detection techniques has been done by other researchers. Their approaches have been somewhat different and not always useful from the Security Assistant perspective. Below is given a short description some related projects and a discussion on their relevance for a Security Assistant.

Crosbie

Crosbie [9] describes an envisioned Intrusion Detection system in which genetic programming and is used to set the appropriate alarm levels on a set of ``agents'' (sensors analyzing the audit data stream). Crosbie's main contribution is the emphasis on a modifiable sensor-set, and the approach to automatic threshold configuration. The paper discusses Intrusion Detection for users and not problems with untrusted code and is as such not relevant for the Security Assistant. The design approach with semi-autonomous sensors inspired and influenced the design considerations in Section 2.4. There are no experimental results yet, but a paper discussing how to structure the programs to make them more apt for mutation is available [10].

Instead of using genetic programming we believe that communication and negotiation using speech-act based protocols offers greater versatility when extracting and refining new categories of information. Also, if programs will be changed often, it is less interesting to learn their behavior.

NIDES

NIDES [1] is a comprehensive Intrusion Detection system. It uses both an expert system for enforcing special rules, and a statistical component for change detection. Anderson et al. [2] have conducted an experiment where the statistical component is used to detect programs masquerading as another program. Historical data about the programs' previous behaviors was gathered and the programs were compared to the other programs' profiles.

One of the results is that programs getting high similarity score do not show any special relation regarding their functionality. E.g were cat, cp and rm considered similar, whereas cat, fmt, less, man, more and sort were not.

Since we would like to use functionality similarities between programs to allow the user to easily select a proper category the above results seem discouraging. However, all the measures were focused on low-level measures not capturing the way the programs were similar. The only measures not concerning CPU-usage and memory usage were the amount of character I/O (in bytes) during execution, the number of opened files and the time-of-day the program was run. This result suggests that the sensors have to be more abstract, and certainly more relevant to what they try to monitor, than the statistical measures in this experiment.

GASSATA

GASSATA [29] is a tool for efficiently finding, among all possible (known) attacks, the subset that is the most likely to have occurred in a set of audit data. Since there can be many possible attack-types, and finding the optimal subset is very expensive to compute, genetic algorithms are used to search efficiently. The population to be evolved consists of vectors with bits set for each attack that is comprised in the data set. Mutation and crossover converges the population to the most probable candidates. GASSATA creates a histogram of the events in each attack an does hence lose the ordering between the events. Also, it is not possible to consider absence of events, and too varied activity will make all attacks probable. GASSATA is an example of a rather autonomous component that, if part of a larger framework, could be a useful first glance a the possibilities.

Forrest

Forrest et. al [13] use the immune system as an inspiration for statistical change detection. By making table of what sequences of system calls of finite length a program generates when it is run they hope to create a system-specific fingerprint that is hard to forge. Since the fingerprint is built of data from actual executions it should be difficult for e.g a virus to modify the program and create a new fingerprint.

This approach concerns only modifications or altered behavior of known programs and cannot give any information about the essence of the intrusion. The key feature of this design (detecting change in a specific implementation of a program) makes it unsuitable to use as a sensor since functional similarities cannot be detected.

Ko-fink

Ko et. al [22] describe the expected behavior of known suid-programs with abstract programs. Their approach is similar to that of the prolog-prototype (Appendix A.3) in that they use a prolog-like language with predicates describing a file system to constrain what is allowed e.g who the user must be and what programs this program is allowed to run. For example can the consented behavior of the so often misused mailer-daemon be described with the following simple program:

verbatim

The main difference between our approaches is the the idea of what the programs should describe. Preferably, for the security assistant, the abstract descriptions describe some abstract behavior or category of programs. Also, rather than explicability of intrusions and exchangeability of descriptions, minimizing what has to be monitored is the main focus here.

Finjan

Recently, Finjan Software [35] released a product called Java Surfing Board. This product is in scope similar to the Java-Prototype (in Section A.1). It is based on an extension of the security manager but can also get some general information by adding auditing at the operating system level. Their security analysis [36] bears much resemblance to the discussion in Section 2.1. The product is an interesting example of what a security assistant could help with but is prone to most of the inherent problems in the Java environment (discussed in Section 3.1 and Section A.1. The information given is basically that which can be straightforwardly extracted from the SecurityManager e.g amount of memory in use, number of applets, number of security exceptions, total number graphics images.

There is in the current version of this product no provisions for applying functional models of what the programs do and the only information available will be that a certain (somewhat arbitrary) threshold has been superseded.

There is also a database of the location of known malicious applets. It does not appear that information about suspicious applets can be distributed to other users.