It had been quite a long time since I looked at artificial immune systems for intrusion detection, so I figured I’d revisit the topic. An artificial immune system (AIS) loosely models biological immune systems to identify incoming data, usually network packets, that are suspicious.

In biology, in highly simplified terms, an antigen is something that can be benign or malicious. An antibody is a kind of detector. Each antibody can detect a specific kind of bad antigen. Antibodies are hosted by lymphocytes.

When a antibody detects a bad antigen, the host lymphocyte does not immediately trigger an alert. Instead the host lymphocyte maintains a stimulation value. Each detection increases the stimulation value and an alert id triggered only when the lymphocyte stimulation value exceeds a specified threshold. This mechanism limits the number of false alarms.

I put together a demo simulation using the C# language. The ideas are best explained by looking at the output of a demo run and then working backward.

The demo program begins by loading a set of six normal data patterns:

Loading antigen self-set ('normal' patterns)
0: 100101101001
1: 110010101100
2: 101100110101
3: 001101011011
4: 010101001101
5: 001010100100

These patterns represent normal, non-threat incoming TCP/IP network packets in binary form. This is called the self-set in AIS terminology. Of course, in a real AIS system, the self-set would likely contain tens or hundreds of thousands of patterns and each pattern would be much larger (typically 48-256 bits) than the 12 bits used in the demo.

Next the demo creates three artificial lymphocytes:

Creating lymphocyte set
0: antibody = 1111 age = 0  stimulation = 0
1: antibody = 1000 age = 0  stimulation = 0
2: antibody = 1110 age = 0  stimulation = 0

Each lymphocyte has a simulated antibody that has four bits (again artificially small), and an age and a stimulation field. The antibody is essentially a detector of patterns that are suspicious. The lymphocytes are created so that none of them detect any of the patterns in the self-set. For example, lymphocyte [0] has antibody = 1111 but none of the six items in the self-set has four consecutive 1s.

After the system has been initialized, the demo program begins a tiny simulation with four incoming patterns. The first incoming pattern is:

Incoming pattern = 111011111000

Detected by lymphocyte 0 new stimulation = 1
Lymphocyte 0 not over stimulation threshold
Detected by lymphocyte 1 new stimulation = 1
Lymphocyte 1 not over stimulation threshold
Detected by lymphocyte 2 new stimulation = 1
Lymphocyte 2 not over stimulation threshold

The incoming pattern is detected by the antibody in lymphocyte [0] because the incoming pattern has “1111”. The incoming pattern is also detected by lymphocyte [1] (“1000”) and lymphocyte [2] (“1110”). A single detection does not trigger an alert by a lymphocyte. Instead, each lymphocyte has a threshold number of detections that must be reached before an alert is triggered. The demo lymphocytes all have a threshold of 3.

The second incoming pattern is:

Incoming pattern = 011100011100

Incoming pattern not detected by lymphocyte 0
Detected by lymphocyte 1 new stimulation = 2
Lymphocyte 1 not over stimulation threshold
Detected by lymphocyte 2 new stimulation = 2
Lymphocyte 2 not over stimulation threshold

The incoming pattern is not detected by lymphocyte [0] so its stimulation value stays at 1. The incoming pattern is detected by lymphocytes [1] and [2] so both of their stimulation values increment to 2.

The third incoming pattern is:

Incoming pattern = 110000011001

Incoming pattern not detected by lymphocyte 0
Detected by lymphocyte 1 new stimulation = 3
Lymphocyte 1 stimulated! Check incoming as possible intrusion!
Incoming pattern not detected by lymphocyte 2

The incoming pattern is detected by lymphocyte [1] so its stimulation value is incremented to 3 and an alert is triggered that the incoming pattern is suspicious and should be examined.

The final, fourth incoming pattern is:

Incoming pattern = 111110110101

Detected by lymphocyte 0 new stimulation = 2
Lymphocyte 0 not over stimulation threshold
Incoming pattern not detected by lymphocyte 1
Detected by lymphocyte 2 new stimulation = 3
Lymphocyte 2 stimulated! Check incoming as possible intrusion!

The incoming pattern is detected by lymphocyte [2], so its stimulation reaches the threshold value of 3, and an alert is triggered.

In a non-demo artificial immune system, the length of the incoming bit patterns can be very large, and the length of simulated antigens can be large too. Therefore, it’s important to use an efficient algorithm to determine if the simulated antigen pattern, such as “1000”, is contained in an incoming pattern such as “111011111000”.

The demo implements a Detects() method in a Lymphocyte class that uses the Knuth-Morris-Pratt pattern matching algorithm. This requires a search table that is constructed from the antibody pattern. There are other efficient pattern matching algorithms that can be used, depending on how the bit patterns are stored. The demo uses arrays of type char which is simple, but not particularly efficient.

The first artificial immune systems were studied over 20 years ago. Those early AIS systems turned out to be not practical. But there is renewed interest in AIS systems, using modern machine learning techniques.

Real biological antigens and lymphocytes, and their behaviors, are vastly more complex than the simplified model that is the basis for artificial immune system intrusion detection.

Demo program. Replace “lt” (less than), “gt”, “lte”, “gte”, “and” with Boolean operator symbols (my blog editor frequently chokes on symbols).

using System;
using System.Collections.Generic;

namespace ArtificialImmuneSystem
{
  class ArtificialImmuneSystemProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin Artificial Immune System" +
        " for Intrusion Detection demo\n");

      Random rnd = new Random(0);

      int numPatternBits = 12;
      int numAntibodyBits = 4;
      int numLymphocytes = 3;
      int stimulationThreshold = 3;
      int time = 0;
      int maxTime = 4;

      Console.WriteLine("Loading antigen self-set" +
        " ('normal' historical patterns)");
      List"lt"char[]"gt" selfSet = LoadSelfSet(null);
      ShowSelfSet(selfSet);

      Console.WriteLine("\nCreating lymphocyte set using" +
        " negative selection" +
        " and r-chunks detection");
      List"lt"Lymphocyte"gt" lymphocyteSet = 
        CreateLymphocyteSet(selfSet, numAntibodyBits,
        numLymphocytes, rnd);
      ShowLymphocyteSet(lymphocyteSet);

      Console.WriteLine("\nBegin AIS intrusion detection" +
        " simulation");
      Console.WriteLine("Stimulation threshold: " +
        stimulationThreshold + "\n");

      while (time "lt" maxTime)
      {
        Console.WriteLine("===============================");
        //Console.WriteLine("time = "+ time);
        char[] incoming = 
          RandomCharArray(numPatternBits, rnd);
        Console.WriteLine("Incoming pattern = " + 
          new String(incoming) + "\n");

        for (int i = 0; i "lt" lymphocyteSet.Count; ++i)
        {
          if (lymphocyteSet[i].Detects(incoming) == true)
          {
            Console.Write("Detected" +
              " by lymphocyte " + i);
            ++lymphocyteSet[i].stimulation;
            Console.WriteLine(" new stimulation = " +
              lymphocyteSet[i].stimulation);
            if (lymphocyteSet[i].stimulation "gte" 
              stimulationThreshold)
              Console.WriteLine("Lymphocyte " + i + 
                " stimulated!" +
                " Check incoming as possible intrusion!");
            else
              Console.WriteLine("Lymphocyte " + i +
                " not over stimulation threshold");
          }
          else
            Console.WriteLine("Incoming pattern not" +
              " detected by lymphocyte " + i);
        }
        ++time;
        Console.WriteLine("===============================");

      }  // while

      Console.WriteLine("\nEnd artificial immune" +
        " system demo");
      Console.ReadLine();
    }  // Main

    public static List"lt"char[]"gt"
      LoadSelfSet(string dataSource)
    {
      // normal patterns
      List"lt"char[]"gt" result = 
        new List"lt"char[]"gt"();
      result.Add("100101101001".ToCharArray());
      result.Add("110010101100".ToCharArray());
      result.Add("101100110101".ToCharArray());
      result.Add("001101011011".ToCharArray());
      result.Add("010101001101".ToCharArray());
      result.Add("001010100100".ToCharArray());
      return result;
    }

    public static void ShowSelfSet(List"lt"char[]"gt" selfSet)
    {
      for (int i = 0; i "lt" selfSet.Count; ++i)
        Console.WriteLine(i + ": " +
          new String(selfSet[i]));
    }

    public static List"lt"Lymphocyte"gt" 
      CreateLymphocyteSet(List"lt"char[]"gt" selfSet,
      int numAntibodyBits, int numLymphocytes, Random rnd)
    {
      // create a List of Lymphocytes that do not detect
      // any patterns in selfSet
      List"lt"Lymphocyte"gt" result = 
        new List"lt"Lymphocyte"gt"();
      Dictionary"lt"int, bool"gt" contents = 
        new Dictionary"lt"int, bool"gt"();  // prevent dups

      while (result.Count "lt" numLymphocytes)
      {
        char[] antibody = 
          RandomCharArray(numAntibodyBits, rnd);
        Lymphocyte lymphocyte = new Lymphocyte(antibody);
        int hash = lymphocyte.GetHashCode();

        if (DetectsAny(selfSet, lymphocyte) == false "and"
          contents.ContainsKey(hash) == false)
        {
          result.Add(lymphocyte);
          contents.Add(hash, true);
        }
      }
      return result;
    }

    private static bool DetectsAny(List"lt"char[]"gt" selfSet,
      Lymphocyte lymphocyte)  // helper
    {
      // does lymphocyte detect any pattern in selfSet?
      // used to create the self-set
      for (int i = 0; i "lt" selfSet.Count; ++i)
      {
        if (lymphocyte.Detects(selfSet[i]) == true)
          return true;
      }
      return false;
    }

    public static void 
      ShowLymphocyteSet(List"lt"Lymphocyte"gt" lymphocyteySet)
    {
      for (int i = 0; i "lt" lymphocyteySet.Count; ++i)
        Console.WriteLine(i + ": " + 
          lymphocyteySet[i].ToString());
    }

    public static char[] RandomCharArray(int numBits,
      Random rnd)
    {
      char[] result = new char[numBits];
      for (int i = 0; i "lt" numBits; ++i)
      {
        int b = rnd.Next(0, 2);
        if (b == 0) result[i] = '0';
        else result[i] = '1';
      }
      return result;
    }

  }  // class ArtificialImmuneSystemProgram

  public class Lymphocyte
  {
    public char[] antibody;  // detector, one per lymphocyte
    public int[] searchTable;  // fast detection
    public int age;            // not used; determine death
    public int stimulation;    // controls triggering

    public Lymphocyte(char[] antibody)
    {
      this.antibody = new char[antibody.Length]; // len "gte" 2
      for (int i = 0; i "lt" antibody.Length; ++i)
        this.antibody[i] = antibody[i];
      this.searchTable = BuildTable();        // call helper
      this.age = 0;
      this.stimulation = 0;
    }

    private int[] BuildTable()
    {
      int[] result = new int[this.antibody.Length];
      int pos = 2;
      int cnd = 0;
      result[0] = -1;
      result[1] = 0;
      while (pos "lt" this.antibody.Length)
      {
        if (this.antibody[pos - 1] == this.antibody[cnd])
        {
          ++cnd; result[pos] = cnd; ++pos;
        }
        else if (cnd "gt" 0)
          cnd = result[cnd];
        else
        {
          result[pos] = 0; ++pos;
        }
      }
      return result;
    }

    public bool Detects(char[] pattern)
    {
      // does the this.antibody detector detect pattern?
      // Knuth-Morris-Pratt algorithm aka r-chunks
      int m = 0;
      int i = 0;
      while (m + i "lt" pattern.Length)
      {
        if (this.antibody[i] == pattern[m + i])
        {
          if (i == antibody.Length - 1)
            return true;
          ++i;
        }
        else
        {
          m = m + i - this.searchTable[i];
          if (searchTable[i] "gt" -1)
            i = searchTable[i];
          else
            i = 0;
        }
      }
      return false;  // not found
    }

    public override int GetHashCode()
    {
      return new String(this.antibody).GetHashCode();
    }

    public override string ToString()
    {
      string s = "antibody = ";
      for (int i = 0; i "lt" antibody.Length; ++i)
        s += this.antibody[i].ToString();
      s += " age = " + age;
      s += "  stimulation = " + stimulation;
      return s;
    }

  }  // class Lymphocyte

}  // ns