Intrusion Detection: Techniques and Approaches


Mikhail Gordeev


Abstract. Intrusion detection plays one of the key roles in computer system security techniques. This paper is dedicated to this topic. It describes major approaches to intrusion detection and focuses on methods used by intrusion detection systems. We do not describe in this paper details of existing intrusion detection system. Instead, we concentrate on underlying principles and methods. This paper can be considered as an introduction to intrusion detection topic.



1 Introduction *

2 Anomaly and misuse detection *

2.1 Anomaly detection *

2.2 Misuse detection *

3 Classification *

4 Methods *

4.1 Rule-based expert systems *

4.2 State transition analysis *

4.3 Bayesian alarm networks *

5 Conclusion *



1. Introduction

The complexity, as well as the importance, of distributed computer systems and their information resources is rapidly growing. Due to this fact, computers and computer networks become a target of computer crime more and more often. Large theoretical and practical efforts are concentrated today on this problem. Nevertheless, a perfectly secure system is still a myth. Many modern computer system still lack in properly implemented security services (if there are any at all), contain a variety of vulnerabilities exploited by threats, and therefore, are vulnerable to compromise.

Very often, a set of attempts to compromise a computer or a computer network resource security is regarded as an intrusion. In addition to security services (e.g. data confidentiality, integrity, authentication, etc.), intrusion detection (ID) techniques are used to strengthen the system security and increase its resistance to internal and external attacks. These techniques are implemented by an intrusion detection system (IDS). Speaking generally, IDS main task is to detect an intrusion and, if necessary or possible, to undertake some measures eliminating it.

There are two general approaches to intrusion detection: anomaly detection and misuse detection. Methods of the first group deal with profiling user behaviour. In other words, they define a certain model of a user normal activity. Any deviation from this model is regarded as anomalous. Methods of the second group operate with priori prepared patterns, also called signatures, of known attacks that are used to detect intrusions by pattern matching on audit information. We shall pay more detail attention at methods belonging to these groups later.

Historically, IDS grew from the system audit information analysis. A strong need in them emerged due to the fact that on one hand, system audit information, like system log files, has reached not processable by a human or a basic routines amounts, on another hand, complexity and variety of intrusions dramatically increased. Modern IDS implement quite advanced and intelligent mechanisms that are capable of handling intrusions complexity and huge amounts of audit data. Very often, they use already pre-processed raw audit information.

Sommer defines the following tasks that IDS can accomplish [1]:

In order to be able to fulfil its tasks, IDS must follow some requirements. On another hand, these requirements could be regarded as IDS efficiency evaluation criteria. A systematic overview of these requirements is given in [2]:

Apart from the functional requirements, IDS must satisfy a number of economical requirements, in particular case, costs. The following costs categories are playing an essential role for IDS [1]:

An importance of these requirements is obvious. On one hand, IDS should be available not only to large enterprises, but also to medium and small size enterprises, as well as to private persons. On another hand, overall costs of IDS must worth costs of resources it protects.


2. Anomaly and misuse detection

As we already said above, the are in general two approaches to intrusion detection: anomaly and misuse detection. In this section of the paper, we shall make a more detail look at both these approaches and figure their main principles out.

First of all, we must identify main categories of parties that could attack a computer system and compromise its security. Earliest works on intrusion detection defined three major groups of such parties [3]:


- masqueraders. They either steal an identity of other users or pretend to be them.

- clandestine users. They either evade or disable the system auditing mechanism.

These are just general groups. No doubts, an intruder in reality can belong to a number of them. Lets give an example. An external penetrator gains an access to a computer system. First of all, he tries to leave no signs of his intrusion in the system audit information. Then he steals an identity of the system legitimate user. Then he is ready to exploit the user’s privileges. That was just one example. We could image a variety of different intrusion scenarios. This demonstrates that intrusion detection seems to be not a really trivial task.


2.1 Anomaly detection

The first well known approach deals with detection of a certain anomaly in a user behaviour. Lets explain it in more detail. Each user of a computer system is capable of performing some tasks. In other words, each user has a certain functionality within the system. Usually this functionality is observable and does not change a lot in time. For example, a secretary due to her or his job speciality usually deals with a limited number of tasks like typing various documents, reading and sending mail, etc. A system administrator accesses system configuration areas, run statistic, audit, and monitoring applications. A programmer’s tasks is obvious - write a program, compile, and debug. This means that it is possible to define a set of actions usually performed by an user. Very often, this set is also called a user profile that describes user’s normal behaviour. Table 1 gives a rather general and intuitive example of a number of common user profiles.

This is of course a rather general example. Real profiles deal with more precise categories (sometimes up to system calls) and are more flexible in constrains of a user normal behaviour (e.g. boss could sometimes send mail and browse Internet).

After such profiles are defined, it is already manageable to trace current user behaviour and to search for some deviations from it. Such deviations are called anomaly and indicate in most cases an intrusion. An intuitive example could be, when a secretary logs in at 9:00 pm, accesses management software and, finally, tries to get system administrator privileges. Table 2 provides a number of examples of anomalies, which indication is based on profiles given in Table 1.




Normal behaviour

System administrator

Logs in as a root, accesses system’s passwords database, edits users’ access permissions, runs system configuration and monitoring tools.


Logs in from time to time, reads mail once per week and never sends it.


Is logged in locally during company working hours, uses text preparation software, permanently reads and sends mails


Is logged in from early morning till late evening, permanently uses management tools and Internet browser, permanently reads and sends mails


Is logged in from late morning till late night, runs software development tools, browsers Internet more often on the late evening than during a day time.

Table 1: User profiles

Usage of this approach intends in a need in learning a normal user behaviour. In other words, it means that IDS must have a knowledge about the user behaviour priori its normal operation.



Anomaly in user behaviour

System administrator

Becomes a programmer, and accesses software development tools, and software sources belonging to some project


Logs in at midnight and start intensively sending mail, accesses confidential information


Logs in form a remote host, becomes a manager


Tries to become a system administrator, changes users access permissions


Becomes a secretary, accesses personnel database

Table 2: Anomaly in user behaviour

Anomaly detection systems are trained on huge amounts of system audit information in order gain sufficient knowledge about user behaviour. Usually, this involves various intelligent techniques like rules generation, machine learning, neural networks, etc. More detail look at these techniques will be done in further sections of this paper.


2.2 Misuse detection

Almost any intrusion can be described in terms of its indications and signs. This is the basic principle used by misuse detection systems. First of all, patterns (sometimes called signatures) of all known attacks must be described in some abstract form and given to IDS. This patterns are used later by IDS to identify an intrusion. This is done by means of studying the system audit information in order to find some patterns matching to patterns of known to the system intrusions.

A good example to demonstrate this approach could be a well known SYN flood denial of service attack. Its goal is to prevent the target host from accepting new connections on a given IP port. The implementation of this attack utilises a three-step handshake schema of a TCP/IP connection establishment and usually exploits a resource exhaustion vulnerability that is common for many TCP/IP implementations. The basic idea is the following. When a client opens a TCP/IP connection, it sends a SYN packet to the server, server receives it and allocates an entry in a connection queue. Such connection is referred as being half-open. Then the server sends a SYN-ACK packet to the client that must be acknowledged by a ACK packet sent by the client to the server. After receiving the acknowledgement, the server releases the corresponding entry in the queue. This procedure can be exploited by an intruder that sends series of SYN packets to the server and does not acknowledge them. This will result in the following: a finite connections queue of the server will get filled up and will be not emptied until timeout periods will not expire. The result is – the server is not able to accept connections on the attacked port any more.

This attack is characterised in general by the following indications:

In order to recognise this attack, IDS must study information on TCP/IP traffic and try to find these indications in it. If the attack is detected, IDS should react. This reaction could be done in a form of signalling an alarm, removing corresponding entries from the connections queue, etc.

In a similar manner indications of other attacks can be figured out. They are represented in a certain form and coded to IDS. There is a number of methods for intrusions representation and their further recognition. Two of the most widely methods are state transition analysis and rule-based expert system. We shall talk about them in further sections of this paper.



3. Classification

Classification of intrusion detection systems is a rather hard topic. The main reason is that many of them are based on more than just one approach and could implement a number of methods. Some systems could use different techniques on different levels of information processing. They could also run in different operation modes under different configuration parameters. The author of this paper thinks that it is more correct to talk about classification of IDS functional and operational characteristics, rather than about classification of IDS itself.

The following figure summarises classifications that could be found in information sources on intrusion detection. Classifications given in [2] and [4] seem to be complete each other quite well.

Figure 1: IDS characteristics classification

Lets give a brief explanation of characteristics shown in the figure. As we already said before, IDS could be based on one of two previously described approaches: misuse detection or anomaly detection.

IDS can react to detected intrusion in two ways. When it takes some actions (like closing holes, shutting services down, logging an intruder) as a reaction to the intrusion, such IDS is called active. If it just generates some alarms or notifications, it is called passive.

Another characteristic is a target of analysis. Application-based IDS collect information and detect intrusions at the application level. For instance, it could be a Web- or e-commerce server. Host-based IDS (sometimes called agents or sensors) collect and analyse information on activity on a certain host in the system. Network-based IDS operate on the network level and analyse the network traffic.

Audit information analysis can be done generally in two modes. Intrusion detection process can run continuously, also called in real-time. The term "real-time" indicates not more than a fact that IDS reacts to an intrusion "quick enough". Intrusion detection process also can be run periodically.

Another quite interesting characteristic of IDS is its architecture. Tendencies of intrusion detection systems development follow the same way as computer systems development. Traditional IDS are centralised. It means that they are implemented either as a one monolithic module or a number interacting ones, which inherit the overall IDS functionality. Now it is said more and more often about fully distributed IDS that consist of entities, which are distributed over a system and each of them carries its own task. One of the promising approaches in this area is based on autonomous agents and involves genetic programming techniques or Bayesian networks [5]. It is very important to point once again out, that we are talking here not about the physical distribution of IDS components, but about its functionality distribution.


4. Methods

Now it is the right time to talk about methods used by intrusion detection systems to represent knowledge on a system and analyse an audit information in order to detect an intrusion. We shell concentrate on the most well known ones like rule-based expert systems, state transition analysis, and Bayesian alarm networks.


4.1 Rule-based expert systems

Rule-based expert system are used very often as a core of an intrusion detection system. The remarkable thing about this approach is that it is used in both anomaly detection systems and misuse detection systems. In such systems, like in any other expert system, declarative knowledge related to intrusions is separated from an inference engine performing a reasoning about the fact base. In other words, it means that, in general, three main components can be distinguished:

Inference engine searches the facts space for those that match what is expected by a rule. If any match is found, the rule is activated and its consequent is fired. We shall demonstrate this process by a simple example. Lets build up a small rule describing a well known buffer overflow attack. This attack exploit a buffer overflow vulnerability of programs running under privileged accounts (e.g. root). An attacker calls a victim program with a long and carefully prepared argument that overflows program memory buffers and alters its execution. As a result, an attacker gets super-user privileges on the target host. This attack can be described by an heuristic rule based on the following facts[6]:

This can be formalised using Prolog-like syntax in the following way:

buffer_overflow_attack :-

audit_typ(X, "exec"),

audit_uid(X, UID1, UID2),

audit_params(X, Length,_,_),



This rule checks bindings for facts (they also could be not just facts but rules deriving underlying information from the audit information) representing a certain audit record X. When all pre-conditions for the rule are satisfied, this rule is fired and could set pre-conditions of some other rules to true.

A rule-based misuse detection expert system toolset P-BEST is based on a described above principle [6] and is used in a number of intrusion detection environments, for instance EMERALD [10].

Expert systems are also used for anomaly detection. As we already wrote in the previous sections of the paper, this approach intends some kind of learning of normal user behaviour and anomalies in it. That is actually the basic difference in using rule-based expert systems for anomaly and misuse detection. In the first case, the rules are generated using some other techniques. In the second case, the rules are given to the system in advance.

There is a number of methods used to obtain rules describing user behaviour. One of the known methods is data mining [8]. This method extracts descriptive models from huge stores of data. In general, it uses three groups of algorithms originating from a variety of fields like statistic, pattern recognition, and machine learning:

Some other methods like frequency based and Hidden Markov Models are explained and compared in regard of normal and abnormal behaviour representation in [9].


4.2 State transition analysis

State transition analysis was developed few years ago by the Reliable Software Group at University of California, Santa Barbara [7]. This method is used for representing a sequence of actions that an intrude performs to break into a system. These actions and requirements to them are represented by a state transition diagram. It is based on a premise that all intrusions have the following two common features: an intruder gets an access to a target system in one or another way, and intrusion results in gaining by the intruder some abilities that he did not have before. Therefore an intrusion is seen as sequences of an intruder actions that bring a system from an initial state to a compromised state through a number of intermediate states. The initial state identifies a system state before the intrusion, the compromised state reflects the system state after the intrusion success. The steps that the intruder makes are represented by sate transitions.

Apart from the states, signature actions are identified. Signature actions mean a minimal set of actions needed to complete the intrusion. If at least one of them is omitted, the intrusion will be not completed.

Finally, the states, transitions and signature actions are represented graphically in a form of a state transition diagram. A good feature of this approach is that the threat scenario is represented in a visual form and very easy to read.

Lets demonstrate this approach by a small example. A number of security mailing lists have announced in January 2000 a vulnerability in a authentication schema of Intel InBusiness E-mail station, a small office application server. It lets remote users to connect to the server and perform some commands without any authentication. This could lead to giving an attacker a system command prompt under super-user privileges. This attack involves the following steps:

This attack scenario can be represented by the following state transition diagram:

Figure 2: An example of a state transition diagram


Real system do not operate with the graphical diagrams. Instead, they use some special languages for states and transition descriptions. Very often, state transition analysis is used as basis for rule-based expert system. A good example could be the USTAT [7].


4.3 Bayesian alarm networks

This is a rather new and promising approach. Very often, it is used in combination with autonomous agents [5].

Bayesian probabilities and networks are an alternative to classical probability theory. In contrast to it, Bayesian probabilities represent not an event property (a probability of its occurrence) but a degree of believe in a fact that the event will occur. An important difference between a Bayesian probability and a classical probability is that to measure the first one no repeated trails are needed. Instead, a probability of the next event in a trial sequence is defined.

Bayesian network is a directed acyclic graph that represents joint probability distribution for a large set of stochastic variables. Arcs of this graph describe stochastic parent-child dependencies between its two nodes. Nodes represent stochastic variables, which values identify either normal or abnormal state of the variable. This idea fits pretty will to intrusion detection environment that must deal with a big number of interdependent variables and significantly simplifies intrusion scenarios representation.

This method requires that probabilities for root nodes (having no parents) as well as conditional probabilities for connected nodes are priory defined. This seems to be a not really trivial task because huge amounts of information must be processed and analysed.

Computation technique is rather simple. When values of some stochastic variables become known (parent node), conditional values of dependant variables (the node’s children) are calculated. An intrusion is identified as detected, if a corresponding to it stochastic variable gets a relevant value.

The following figure shows a simple Bayesian alarm network and is a part of the network described in [5]:

Figure 3: Bayesian alarm network modelling a general intrusion


The author thinks that Bayesian network approach is quite interesting and promising despite looking rather complicated.


5. Conclusion

This paper is dedicated to a relatively new topic in computer security. However, the experience of last years demonstrated that there is a strong demand on intrusion detection systems. Very often, a need in them is expressed on a state level. For instance, the USA government has announced in January 2000 that a global intrusion detection system covering the governmental computer network will be created. A lot of enterprises of different size already use these system for ensuring their business security. The author believes that R&D activities in this area will bring a lot of solutions that are needed today and will be needed tomorrow.



[1] P. Sommer, "Intrusion detection systems as evidence", Computer Networks, No. 31, 1999

[2] H. Debar, M. Dacier, A. Wespi, "Towards a taxonomy of intrusion-detection systems", Computer Networks, No. 31, 1999

[3] A. Mounji, "Rule-based distributed intrusion detection", PhD thesis, University of Namur, Belgium, 1997

[4] "An introduction to intrusion detection assessment for system and network security management", ICSA Inc, 1999, available on-line at

[5] D. Bulatovic, D. Valesevic, "A distributed intrusion detection system based on Bayesian alarm networks", In Proceedings of the Secure Networking – CQRE [Secure]’99 Conference, Düsseldorf, November/December, 1999

[6] U. Lindqvist, P. Porras, "Detecting computer and network misuse through the production-based expert system toolset (P-BEST)", In Proceedings of the 1999 IEEE Symposium on Security and Privacy, California, May, 1999

[7] K. Ilgun, R. Kemmerer, P. Porras, "State transition analysis: a rule-based intrusion detection approach", IEEE Transactions on Software Engineering, Vol. 21, No. 3, March, 1995

[8] W. Lee, S. Stolfo, "Data mining approaches for intrusion detection", In Proceedings of the 7th USENIX Security Symposium (SECURITY-98), January, 1998

[9] C. Warrender, S. Forrest, B. Pearlmutter, "Detecting intrusions using system calls: alternative data models", In Proceedings of the 1999 IEEE Symposium on Security and Privacy, California, May, 1999

[10] P. Neumann, P. Porras, "Experience with EMERALD to date", In Proceedings of the 1st USENIX Workshop on Intrusion Detection and Network Monitoring, California, April, 1999