« first  « prev  » next  » last 

Jump to:

Artificial Immune Systems and Negative Selection

1. Architecture of an Artificial Immune System

The building blocks we need to create an artificial immune system are listed here. This section details the basic structure of the system, to clarify the link between the biological inspiration and the implemented system. The next section gives code listings and other implementation specific details for the Delphi component set. For any system, be it a computer system, manufacturing process or real time control application, we can define a pattern of normal behaviour. For example, a bridge will vibrate only within a given frequency and amplitude range and we can safely assume that if the vibration of the bridge leaves this normal range we are heading towards a potentially dangerous situation. Similarly, the behaviour of users and processes within a computer system will generally fall within an acceptable range of values for CPU, memory, network and resource usage. We are probably safe in assuming that if a process leaves this range there is something bad happening. Maybe that process has crashed or a user is attempting to do something untoward. Artificial Immune Systems are an ideal tool for detecting these sorts of incidents. We know from the previous section that the human immune system is able to differentiate between "self" and "non-self" and we can use this ability in a computer system to detect when things go wrong. We define "self" to be the normal operation of the system. For the bridge example above, "self" is the normal range of vibrations, loads and suchlike. For the computer security example, "self" is the normal range of process behaviour. "Non-self" in both examples is any measurement we make that is outside these ranges.

Normal behaviour of a system
Figure 1: Normal behaviour of a system

Figure 4 shows an example measurement for a system which is functioning normally. It could be a vibration measurement of our bridge as somebody walks across it. (Actually I just used Matlab to add a couple of sine waves together to give a sensible example). Figure 5 shows another example measurement for the same system, but this time there is a noise signal there which represents a fault. Perhaps the wind is making our bridge unstable? We need out bridge's immune system to be able to sense this change in behaviour and raise an alarm so we can investigate the problem.

Abnormal behaviour of a system
Figure 2: Abnormal behaviour of a system

The first thing we need to define is a Self Set. The self set is a set of patterns which represent normal operation of the system. These patterns will be used by the negative selection process to ensure that our artificial lymphocytes (T cells) do not detect "self" (i.e. to ensure that they don't raise an alarm under normal operation). Our self set will be simply a set of symbol sequences. Our lymphocytes will also be a set of symbol sequences. Matching will be measured simply by comparing symbols. The symbols we'll use here are positive integers. Different problems will need a different number of symbols, some, such as comparing binary strings, will need only two (1 and 0), while others will require more. Figure 6 shows how we would convert a continuous sensor reading into a series of symbols.

Normal behaviour of a system - restricted to 10 symbols (0 - 9)
Figure 3: Normal behaviour of a system - restricted to 10 symbols (0 - 9)

Next we create a library of "self" patterns by chopping the above into a set of shorter sequences. The self set for the above might look something like listing 1.

  Pattern 1:  5     6     6     7     8     8     9
  Pattern 2:  9     9     9     9     9     9     9
  Pattern 3:  8     8     7     7     6     6     5
  Pattern 4:  5     5     4     4     4     4     4

Once we have our self set we are ready to start creating the lymphocytes which will monitor the system. New lymphocytes must be presented to self patterns to see if they "match" or not. Listing 2 is an example of how the negative selection algorithm will compare new lymphocytes to self patterns. Remember that any lymphocyte that matches any self pattern will be destroyed. The length of the lymphocytes and the self patterns must be the same and it, in this example, 7.

Exact match - delete lymphocyte

  Self pattern:  1 6 7 3 6 2 2
    Lymphocyte:  1 6 7 3 6 2 2

Partial match (with threshold of 4) - delete lymphocyte

  Self pattern:  1 6 7 3 6 2 2
    Lymphocyte:  4 6 7 3 6 3 9

No match (with threshold of 4) - keep lymphocyte

  Self pattern:  1 6 7 3 6 2 2
    Lymphocyte:  1 6 1 3 6 1 2

We will use the algorithm in listing 3 to create a set of lymphocytes known as the Detector Set.

    create a new lymphocyte pattern at random
    add lymphocyte to detector set
    for each pattern in the self set
      if lymphocyte matches self set pattern
        delete lymphocyte from detector set
  until size limit reached

Once we have generated our detector set we are ready to start looking for abnormal system behaviour. We do this by discreetising new data from our system using the rules above, ensuring that we use the same symbol set, pattern size and suchlike. We can then watch for errors/ faults by continually applying every artificial lymphocyte in our detector set to the new data. Because our detector set is self tolerant (i.e. will never match normal data) we can be sure that if any detector matches our new data then that data is indicative of abnormal behaviour. To put it another way: If a detector matches we have a fault.

To summarise, the following is a list of the components of an artificial immune system:

  • Symbols: We must be able to decompose measurements of our systems into a small set of symbols (the smaller the better). For the sake of this article, symbols are positive integers and could be simply [0, 1] for binary, [0 .. 35] for numbers and letters (a..z, 0..9) or some other appropriate range.
  • Pattern: A pattern is a simple structure for storing a list of symbols. The self set and detector set are simply lists of patterns.
  • Self Set: A set of patterns, constructed from past data, which represents normal operation of our system
  • Detector Set: A set of lymphocyte patterns, generated using the negative selection algorithm (above)

« first  « prev  » next  » last 

Jump to: