Cet article a fait l'objet d'une traduction automatique.

Série de tests

Systèmes immunitaires artificiels pour détecter les intrus

James McCaffrey

Télécharger l'exemple de code

Un système immunitaire artificiel (AIS) pour la détection d'intrusion est un logiciel qui modélise certaines parties du comportement du système immunitaire humain pour protéger les réseaux informatiques contre les virus et les cyber-attaques similaires. L'idée essentielle est que le système immunitaire humain — qui est un système complexe composé de lymphocytes (globules blancs), anticorps et beaucoup d'autres composants — a évolué au fil du temps pour fournir une protection puissante contre les toxines nocives et d'autres pathogènes. Ainsi, la modélisation du comportement du système immunitaire humain peut fournir une architecture efficace contre les cyberattaques.

Dans cet article, j'ai décrit certains des principes des systèmes immunitaires artificiels et présenter un programme pour illustrer ces principes. Travaux sur la protection de l'AIS est encore relativement nouveau et, à mon avis, aucune des implémentations commerciales ne sont tout à fait prêtes pour prime time. Le code présenté dans cet article pas directement vous permettra de créer un système de réseau-intrusion réaliste, mais il y a au moins quatre raisons pourquoi vous pouvez trouver cet article mérite d'être lu. Tout d'abord, le code vous donnera un point de départ pour l'expérimentation pratique avec un simple système AIS. Deuxièmement, les principes expliqués vont vous surmonter l'obstacle initial plutôt difficile pour ce secteur et permettent de comprendre des documents de recherche sur l'AIS. En troisième lieu, plusieurs des techniques de programmation utilisés dans cet article, en particulier r-morceaux bit correspondant et une sélection négative, peuvent être utiles dans d'autres scénarios de programmation. Et Quatrièmement, vous pouvez juste trouver l'idée de la modélisation d'un système de logiciel basé sur le comportement du système immunitaire humain intéressant à part entière.

La meilleure façon d'avoir une idée d'où je veux en venir est de jeter un oeil à la capture d'écran d'une démo exécution, montre Figure 1. Le programme de démonstration commence par créer un ensemble de six modèles normaux (modèles connus ne pas faire partie d'une cyber-attaque) qui représentent TCP/IP réseau paquets sous forme binaire. Cela s'appelle l'auto-établis dans la terminologie de l'AIS. Bien sûr, dans un véritable système AIS, l'auto-établis probablement contient des dizaines ou des centaines de milliers de modèles, et chaque modèle serait beaucoup plus grande (en général 48-256 bits) que les 12 bits utilisées ici. Ensuite, le programme de démonstration crée trois lymphocytes artificiels. Chaque lymphocyte a un anticorps simulé qui présente quatre bits (encore une fois, artificiellement petit), un âge et un champ de stimulation. Le champ de l'anticorps est essentiellement un détecteur. Comme vous le verrez bientôt, les lymphocytes sont créés afin qu'aucun d'eux ne détecte les modèles dans l'auto-établis. Pour l'instant, observer que chaque lymphocyte a trois 0 consécutifs s ou 1 s, mais aucun des modèles dans l'auto-établis a trois valeurs de bit égaux consécutifs.

Figure 1 démonstration de système immunitaire artificiel

Après que le système a été initialisé, le programme de démonstration commence une petite simulation avec six modèles d'entrée. La première entrée est détectée par lelymphocyte 1, mais parce que chaque lymphocyte a un seuil d'activation, les lymphocytes ne déclenchent pas d'alarme. Au temps t = 3, lymphocyte 1 détecte une autreentrée suspecte mais, encore une fois, est pas encore sur le seuil. Mais au temps t = 5, lymphocyte 1 détecte un troisième paquet d'entrée suspect et une simulation alerteest déclenchée.

Dans les sections qui suivent, j'expliquerai tout d'abord les concepts clés du système immunitaire humain qui sont utilisés pour modéliser un AIS. Alors je vais vous guiderdans le code qui a produit la capture d'écran de Figure 1. Je conclurai en vous donnant quelques références supplémentaires et quelques opinions sur SIA. Cet articlesuppose que vous disposez au moins de niveau intermédiaire de compétences en programmation avec un langage de programmation modern. J'ai utiliser le langage c# pour leprogramme de démonstration, mais je vais vous expliquer où vous devez apporter des modifications si vous souhaitez refactor mon code dans une autre langue, tels que VisualBasic .NET ou Python. Je vous présente tout le code qui a généré la capture d'écran de Figure 1; le code est également disponible àarchive.msdn.microsoft.com/mag201301TestRun.

Le système immunitaire humain

Les éléments clés d'un système immunitaire très simplifié sont illustrés dans la Figure 2. Éléments dangereux sont des protéines appelées antigènes. Dans Figure 2 lesantigènes sont de couleur rouge et ont des angles aigus. Aussi, le corps humain contient de nombreux antigènes non dangereux appelés auto-antigènes, ou self-items. Ellessont naturellement des protéines et en Figure 2 sont de couleur verte et côtés arrondis.

Figure 2 principaux éléments d'un système immunitaire simplifiée

Antigènes sont détectés par les lymphocytes. Chaque lymphocyte a plusieurs anticorps, ce qui peuvent être considérés comme détecteurs. Chaque anticorps est spécifique à un antigène particulier. En général, parce que les anticorps-antigène correspondant est seulement approximative, un lymphocyte pas déclenchera une réaction lorsqu'un seul anticorps détecte un seul antigène. Seulement après que plusieurs anticorps détecte les antigènes correspondants un lymphocyte deviendra stimulé et déclencher une sorte de réaction défensive.

Ne remarquez qu'aucun lymphocyte anticorps détectant un self-item. Anticorps réels générés par le système immunitaire dans le thymus, mais n'importe quel anticorps détectant les self-items sont détruits avant d'être libéré dans la circulation sanguine, un processus appelé apoptose.

En ce qui concerne un système de détection d'intrusion, les antigènes correspondent aux paquets de réseau TCP/IP dont le contenu contient une sorte de données dangereux, comme un virus informatique. Auto-antigènes correspondent aux paquets réseau normal, non nocif. Un anticorps correspond à un modèle binaire qui correspond à environ un paquet réseau inconnus et potentiellement dangereux. Un lymphocyte représente deux ou plusieurs anti­corps/détecteurs. L'apoptose est modélisée en utilisant une technique appelée sélection négative.

Structure générale du programme

Le programme de démonstration montré Figure 1 est une simple application de console c# nommée ArtificialImmuneSystem. J'ai utilisé Visual Studio 2010, mais n'importe quelle version de Visual Studio dans laquelle Microsoft .NET Framework 2.0 ou version ultérieur devrait fonctionner. J'ai renommé le fichier modèle généré par Visual Studio nommé Program.cs pour l'ArtificialImmuneSystemProgram.cs plus descriptive et renommé de la classe correspondante. La structure globale du programme est répertoriée dans Figure 3.

Figure 3 Structure de programme pour le système immunitaire artificiel

using System;
using System.Collections.Generic;
using System.Collections; // for BitArray
namespace ArtificialImmuneSystem
{
  class ArtificialImmuneSystemProgram
  {
    static Random random;
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin Artificial Immune System for Intrusion" +
        " Detection demo\n");
      random = new Random(1);
      int numPatternBits = 12;
      int numAntibodyBits = 4;
      int numLymphocytes = 3;
      int stimulationThreshold = 3;
      Console.WriteLine("Loading self-antigen set ('normal' historical patterns)");
      List<BitArray> selfSet = LoadSelfSet(null);
      ShowSelfSet(selfSet);
      Console.WriteLine("\nCreating lymphocyte set using negative selection" +
        " and r-chunks detection");
      List<Lymphocyte> lymphocyteSet = CreateLymphocyteSet(selfSet, numAntibodyBits,
        numLymphocytes);
      ShowLymphocyteSet(lymphocyteSet);
      Console.WriteLine("\nBegin AIS intrusion detection simulation\n");
      int time = 0;
      int maxTime = 6;
      while (time < maxTime)
      {
        Console.WriteLine("============================================");
        BitArray incoming = RandomBitArray(numPatternBits);
        Console.WriteLine("Incoming pattern = " +
          BitArrayAsString(incoming) + "\n");
        for (int i = 0; i < lymphocyteSet.Count; ++i)
        {
          if (lymphocyteSet[i].Detects(incoming) == true)
          {
            Console.WriteLine("Incoming pattern detected by lymphocyte " + i);
            ++lymphocyteSet[i].stimulation;
            if (lymphocyteSet[i].stimulation >= 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("============================================");
      } // Simulation loop
        Console.WriteLine("\nEnd AIS IDS demo\n");
        Console.ReadLine();
    } // Main
    public static List<BitArray> LoadSelfSet(string dataSource) {..}
    public static void ShowSelfSet(List<BitArray> selfSet) {..}
    public static string BitArrayAsString(BitArray ba) {..}
    public static List<Lymphocyte> CreateLymphocyteSet(List<BitArray> selfSet,
      int numAntibodyBits, int numLymphocytes) {..}
    private static bool DetectsAny(List<BitArray>
      selfSet, Lymphocyte lymphocyte) {..}
    public static void ShowLymphocyteSet(List<Lymphocyte> lymphocyteySet) {..}
    public static BitArray RandomBitArray(int numBits) {..}
  } // Program
  public class Lymphocyte
  {
    public BitArray antibody;  // detector
    public int[] searchTable;  // for fast detection
    public int age;            // not used; could determine death
    public int stimulation;    // controls triggering
    public Lymphocyte(BitArray antibody) {..}
    private int[] BuildTable() {..}
    public bool Detects(BitArray pattern) {..}
    public override int GetHashCode() {..}
    public override string ToString() {..}
  }
} // ns

J'ai supprimé tout le modèle généré utilisant des déclarations, à l'exception des références aux espaces de noms System et System.Collections.Generic. J'ai ajouté une référence à l'espace de noms System.Collections, donc je pourrais avoir accès à la classe BitArray. Après un message de démarrage, j'ai instancié un objet Random statique à l'aide d'une valeur de départ arbitraire de 1.

Si vous comparez le code dans la méthode Main dans Figure 3 avec la capture d'écran de Figure 1, vous ne devriez pas avoir trop de mal à comprendre la logique du programme. La clé de la démo de l'AIS est la définition de la classe des lymphocytes. Notez que pour que la taille du code démo petite et dégager les idées maîtresses, j'ai enlevé tous les normales vérification des erreurs que vous comprendrait probablement pendant l'expérimentation.

La classe de lymphocytes

La classe de lymphocytes a quatre champs de données :

public BitArray antibody;  // Detector
public int[] searchTable;  // For fast detection
public int age;            // Not used; could determine death
public int stimulation;    // Controls triggering

Je déclare tous les champs avec une portée publique pour plus de simplicité. Le champ de l'anticorps est un BitArray. Si vous n'êtes pas familier avec BitArray, l'idée est qu'à l'aide d'un tableau normal d'int pour représenter une collection de bits est très inefficace car chaque int requiert 32 bits de stockage. Un tableau de bits condense 32 bits d'information dans un entier unique de stockage, ainsi que certains frais généraux pour la classe. Langages de programmation qui n'est pas une classe BitArray ressemblant vous obliger à faire la manipulation de bas niveau bit avec le masque de bits et les opérations de bits.

Le champ searchTable est un tableau qui est utilisé par la méthode détecte à augmenter considérablement les performances. Le champ n'est pas utilisé dans mon programme de démonstration ; beaucoup de systèmes AIS suivre l'âge d'un lymphocyte simulé et probabiliste tuer et générer de nouveaux lymphocytes fondées sur l'âge. Le domaine de la stimulation est un compteur qui permet de suivre combien de fois un objet de lymphocytes a détecté une menace potentielle. Dans cette démo, lorsqu'une valeur de stimulation lymphocytaire est supérieure à la valeur de stimulationThreshold de 3, une alerte est déclenchée.

Le constructeur de lymphocytes est :

public Lymphocyte(BitArray antibody)
{
  this.antibody = new BitArray(antibody);
  this.searchTable = BuildTable();
  this.age = 0;
  this.stimulation = 0;
}

Le constructeur accepte un seul paramètre de BitArray qui représente un antigène/détecteur. Le tableau searchTable est instancié à l'aide d'une méthode d'assistance privée nommée BuildTable, qui je présenterai sous peu.

Parmi les éléments clés de tout système AIS est la routine qui détermine si un antigène détecte un modèle. Nécessitant une correspondance exacte n'est pas possible (et n'imitent le comportement réel de l'antigène). Les premiers travaux sur l'AIS utilisé une technique appelée bits contigus r correspondant, dans lequel un antigène et un modèle d'entrée ont le même nombre de bits et de détection se produit lorsque l'antigène et le modèle correspondent en bits consécutifs r. Des recherches ultérieures a indiqué qu'un meilleur algorithme de détection est r-morceaux bit correspondant. La correspondance de bits r-morceaux ressemble à bits contigus r correspondant sauf que le détecteur de l'antigène est plus petit que le modèle à vérifier, et détection se produit lorsque le sous-ensemble de New York du modèle correspond à l'antigène. Par exemple, si un antigène est 110 et un patron est 000110111, l'antigène détecte le modèle commençant à l'index 3.

Si vous pensez à r-morceaux correspondant à un moment, tu te rendras compte que c'est presque identique à une fonction substring de chaîne. La seule différence est que r-morceaux correspondant bits de correspondances et de sous-chaîne correspond aux caractères.

Dans l'exemple précédent, les r-morceaux correspondant à une approche simple consisterait à examiner le modèle commençant à l'index 0, puis à l'index 1, puis 2 et ainsi de suite. Toutefois, cette approche est très lente dans la plupart des situations. Il existe plusieurs algorithmes sophistiqués de sous-chaîne prétraitement la plus petite chaîne de détecteur pour créer un tableau (généralement appelé table). Cette table de recherche peut servir à sauter en avant lorsqu'un déséquilibre est détecté et améliorer considérablement les performances. Dans les situations où la plus petite chaîne de détecteur sert à plusieurs reprises pour vérifier les différents modèles, comme dans la détection des intrusions AIS — le temps et la mémoire nécessaire pour créer la table de recherche est un petit prix à payer pour améliorer considérablement les performances.

La méthode détecte de lymphocytes classe utilise l'algorithme de sous-chaîne de Knuth-Morris-Pratt appliqué à un BitArray. La méthode détecte accepte un modèle d'entrée tels que 000110111 et retourne la valeur true si l'antigène de l'objet en cours, tels que 110, correspond au modèle. Le code pour la méthode détecte est répertorié dans Figure 4.

Figure 4 la méthode de détecte

public bool Detects(BitArray pattern)  // Adapted KMP algorithm
{
  int m = 0;
  int i = 0;
  while (m + i < 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] > -1)
        i = searchTable[i];
      else
        i = 0;
    }
  }
  return false;  // Not found
}

La méthode détecte suppose l'existence de la table de recherche. Rappelons que le constructeur de lymphocytes appelle une méthode d'assistance BuildTable pour créer le champ searchTable. Le code pour BuildTable est répertorié dans Figure 5.

Figure 5 la méthode de BuildTable

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

La classe de lymphocytes définit merthods GetHashCode et ToString substituée. La méthode GetHashCode sert à éviter que des objets dupliqués de lymphocytes et est :

public override int GetHashCode()
{
  int[] singleInt = new int[1];
  antibody.CopyTo(singleInt, 0);
  return singleInt[0];
}

Cette implémentation suppose que le domaine d'anticorps de BitArray est 32 bits ou moins. Dans des situations réalistes dont le champ de l'anticorps a plus de 32 bits, traitant des objets dupliqués de lymphocytes n'est pas si simple. Une approche consisterait à définir une méthode de code de hachage personnalisé qui retourne un type BigInteger (disponibles dans le .NET Framework 4 et versions ultérieures).

La méthode ToString de lymphocytes dans le programme de démonstration est :

public override string ToString()
{
  string s = "antibody = ";
  for (int i = 0; i < antibody.Length; ++i)
    s += (antibody[i] == true) ? "
1 " : "0 ";
  s += " age = " + age;
  s += "  stimulation = " + stimulation;
  return s;
}

Création de l'auto-établis

Vous connaissez certainement standard (non-AIS) logiciel de détection des virus informatiques, tels que Microsoft Security Essentials. Ces systèmes fonctionnent en stockant une base de données locale de définitions de virus informatique connu. Lorsqu'un modèle de virus connus est détecté, une alerte immédiate est déclenchée. Ces systèmes antivirus ont mal en variations sur les virus existants et ne pas entièrement dans la plupart des situations face à un tout nouveau virus. Détection d'intrusion AIS fonctionne dans le sens inverse en maintenant un ensemble de modèles d'entrée qui sont connus pour être nocif et ensuite déclencher une alerte lorsqu'un motif inconnu est détecté. Cela permet à des systèmes de détection d'intrusion AIS — en principe, au moins, pour détecter les nouveaux virus. Toutefois, traitant des faux positifs — c'est-à-dire, déclenchant une alerte sur un modèle d'entrée de non-nocive — constitue un défi majeur pour les systèmes AIS.

Un système de détection d'intrusion réels AIS recueillerait des milliers de modèles d'entrée normales au cours des jours ou des semaines. Ces structures auto-établis normales seraient stockés sur un hôte local ou un serveur. En outre, un véritable système AIS mettrait à jour continuellement l'auto-établis (et l'ensemble induit des lymphocytes) de structure normale pour tenir compte des changements normaux du trafic réseau au fil du temps. Le programme de démonstration dans cet article crée un artificiel, statique self-set à l'aide de la méthode LoadSelfSet :

public static List<BitArray> LoadSelfSet(string dataSource)
{
  List<BitArray> result = new List<BitArray>();
  bool[] self0 = new bool[] { true, false, false, true, false, true,
                              true, false, true, false, false, true };
  // Etc.
bool[] self5 = new bool[] { false, false, true, false, true, false,
                              true, false, false, true, false, false };
  result.Add(new BitArray(self0));
  // Etc.
result.Add(new BitArray(self5));
  return result;
}

La méthode accepte un paramètre de factice-n'utilise pas de source de données pour suggérer que, dans un scénario réaliste, les données auto-établis ne serait pas codé en dur. Le constructeur de BitArray, étonnamment, accepte un tableau de valeurs Boolean où true représente un bit 1 et false représente un bit 0. Observer que j'ai généré les données auto-établis de telle sorte que self-item n'a plus deux 0 consécutifs s ou 1 s.

Le programme de démonstration utilise la méthode utilitaire ShowSelfSet, qui appelle la méthode d'assistance BitArrayAsString, pour afficher l'auto-établis :

public static void ShowSelfSet(List<BitArray> selfSet)
{
  for (int i = 0; i < selfSet.Count; ++i)
    Console.WriteLine(i + ": " + BitArrayAsString(selfSet[i]));
}
public static string BitArrayAsString(BitArray ba)
{
  string s = "";
  for (int i = 0; i < ba.Length; ++i)
    s += (ba[i] == true) ? "
1 " : "0 ";
  return s;
}

Création de l'ensemble des lymphocytes

Si vous revenez à l'explication du fonctionnement du système immunitaire humain, vous remarquerez que le jeu de lymphocytes doit contenir uniquement les objets de lymphocytes qui ne détectent pas tous les motifs dans l'auto-établis. Méthode CreateLymphocyteSet est répertorié dans Figure 6.

La figure 6 de la méthode CreateLymphocyteSet

public static List<Lymphocyte> CreateLymphocyteSet(List<BitArray> selfSet,
  int numAntibodyBits, int numLymphocytes)
{
  List<Lymphocyte> result = new List<Lymphocyte>();
  Dictionary<int, bool> contents = new Dictionary<int, bool>();
  while (result.Count < numLymphocytes)
  {
    BitArray antibody = RandomBitArray(numAntibodyBits);
    Lymphocyte lymphocyte = new Lymphocyte(antibody);
    int hash = lymphocyte.GetHashCode();
    if (DetectsAny(selfSet, lymphocyte) == false &&
      contents.ContainsKey(hash) == false)
    {
      result.Add(lymphocyte);
      contents.Add(hash, true);
    }
  }
  return result;
}

Dans la terminologie de l'AIS, la méthode CreateLymphocyteSet utilise une sélection négative. Un Lymphocyte aléatoire objet est généré et ensuite testé pour voir s'il ne détecte pas tous les motifs dans l'auto-établis et aussi que les lymphocytes pas déjà dans le résultat défini. Cette approche est plutôt grossière, et il existe d'autres approches plus efficaces. J'utilise une collection de dictionnaires avec une valeur bool factice pour suivre les objets existants de lymphocytes ; la classe HashSet dans le .NET Framework 4.5 ou version ultérieure est une solution plus efficace.

Un objet au hasard des lymphocytes est créé en générant un BitArray aléatoire :

public static BitArray RandomBitArray(int numBits)
{
  bool[] bools = new bool[numBits];
  for (int i = 0; i < numBits; ++i)
  {
    int b = random.Next(0, 2);  // between [0,1] inclusive
    bools[i] = (b == 0) ?
false : true;
  }
  return new BitArray(bools);
}

Méthode d'assistance DetectsAny accepte un auto-établis et un lymphocyte analyse un auto-établis et retourne la valeur true si n'importe quel motif dans l'auto-établis est détecté par l'antigène dans les lymphocytes :

private static bool DetectsAny(List<BitArray> selfSet,
  Lymphocyte lymphocyte)
{
  for (int i = 0; i < selfSet.Count; ++i)
    if (lymphocyte.Detects(selfSet[i]) == true) return true;
  return false;
}

Le programme de démonstration utilise une méthode utilitaire ShowLymphocyteSet pour afficher les objets générés de lymphocytes :

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

Pour résumer

Le code et les explications que j'ai présentée dans cet article devraient vous donner une base solide pour l'expérimentation pratique avec l'AIS. Les chercheurs ont suggéré plusieurs options. Par exemple, le programme de démonstration dans cet article déclenche une alerte lorsqu'un lymphocyte unique détecte des modèles d'entrée inconnus plus que certains nombre de fois. L'idée ici est que les vrais agents pathogènes émettent d'antigènes. Une autre possibilité est le système AIS déclencher une alerte uniquement après que plusieurs lymphocytes différents détecter le même modèle inconnu.

Il est important de souligner que l'AIS n'est pas destiné à être une solution unique pour la détection d'intrusion. Au contraire, c'est censé faire partie d'une défense multicouche qui inclut les logiciels antivirus traditionnels. En outre, parce que le travail avec l'AIS est encore relativement jeune, il y a beaucoup de questions sans réponse. Si vous souhaitez examiner les recherches sur l'AIS, je recommande la recherche en ligne pour les articles écrits par des auteurs S. Forrest, P. Williams et U. Aickelin.

Dr.  James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Microsoft Redmond, Wash., campus. Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. James McCaffrey est l'auteur de « .NET Test Automation Recipes » (en anglais) (Apress, 2006). Il peut être contacté à jammc@microsoft.com.

Merci à l'expert technique suivant d'avoir relu cet article : Dan Liebling