2015-08-19

この記事は機械翻訳されたものです。

テストの実行

侵入検知のための人工免疫システム (機械翻訳)

James McCaffrey 侵入検知用人工免疫システム (AIS) は、ウイルスと同様のサイバー攻撃からコンピュータネットワークを保護するために人間の免疫システムの動作の一部をモデル化ソフトウェアシステムです。基本的な考え方は、人間の免疫システムです — リンパ球 (白血球)、抗体と多くの他のコンポーネントから成る複雑なシステムである — 有害な毒素や他の病原体に対する強力な保護を提供するために時間をかけて進化してきた。だから、人間の免疫システムの挙動のモデル化サイバー攻撃に対する効果的なアーキテクチャを提供する可能性があります。

この記事では人工免疫システムの原則のいくつかを説明し、これらの原則を示すためにプログラムを提示します。 AIS の保護の仕事はまだ比較的新しいですし、商用の実装かなりプライムタイムの準備ができて私の意見ではありません。この記事で紹介したコード直接、現実的なネットワーク侵入システムを作成する有効いないが、少なくとも 4 つの理由なぜあなたはこの記事を読む価値がある見つけるかもしれない。まず、コード単純な AIS システムと実践的な実験のための出発点を与えるでしょう。第二に、説明原則でしょうこの領域に、むしろ難しい初期ハードルを取得し、AIS に関する研究論文を理解することができます。第三に、特定の r チャンクビットマッチングと負の淘汰でこの資料で使用されるプログラミングのテクニックのいくつかの他のプログラミングシナリオで役に立ちます。そして第四に、ちょうど人間の免疫システムの独自の権利で興味深いの行動に基づくソフトウェアシステムのモデル化のアイデアを見つけるかもしれない。

示すどこに向かっているの感触を得るための最良の方法実行、それなら、ぜひこのデモのスクリーンショットを取ることです図 1。表す TCP/IP 6 通常パターン (いくつかのサイバー攻撃の一部でないことが知られているパターン) のセットを作成することによって、デモ・プログラムを開始ネットワークのパケットでバイナリ形式。これは自己 AIS の用語で呼ばれます。もちろん、実際の AIS システムで、自己可能性が数十または数十万のパターンの含むだろうし、各パターンははるかに大きくなる (通常 48 256 ビット) 12 ここで使用するビットより。次に、デモプログラムは 3 つの人工リンパ球を作成します。各リンパ球では、4 つのビットが (再度、人工的に小さい) シミュレートされた抗体、年齢刺激フィールドがあります。抗体のフィールドは、本質的に検出器です。後述しますが、それらのどれも、パターンのいずれかの自己検出するリンパ球が作成されます。今のところ、各リンパ球を 3 つの連続した 0 または 1 s がありますが、どれも、自己中のパターンの 3 つの連続する等しいビット値が観察します。

Artificial Immune System Demo
図 1 人工免疫システムのデモ

システムの初期化後は、デモプログラムは六つの入力パターンによる小さなシミュレーションを開始します。最初の入力 1、リンパ球によって検出されますが各リンパ球活性化しきい値があり、リンパ球アラームをトリガーしません。時間 t で = 3、リンパ球 1 を検出する別の疑わしい入力しかし、再び、まだされていませんが、しきい値を超える。しかし、時間 t で = 5、リンパ球 1 第三不審な入力パケットを検出し、シミュレートされたアラートがトリガーされます。

このセクションでは、私は最初は、AIS モデルに使用される人間の免疫システムの主要な概念を説明します。私はあなたのスクリーンショットを生成するコードを介して歩くよし、 図 1。あなたにいくつかの追加の参照と AIS についていくつかの意見を与えることによってと締めくくります。この記事は、少なくとも中級レベルのプログラミングスキル最新のプログラミング言語があると仮定します。私は c# デモプログラムを使用するが、私のコードを Visual Basic .NET または Python など別の言語にリファクタリングする場合を変更する必要がありますを説明します。スクリーンショットで生成されたコードを提示図 1; コードはまた利用で archive.msdn.microsoft.com/mag201301TestRun。

人間の免疫システム

簡素化した免疫システムの重要な要素で示されている図 2。有害な項目は抗原と呼ばれる蛋白質です。 図 2 抗原赤着色され、鋭いコーナーがあります。人間の体は、また自己抗原と呼ばれる多くの非有害な抗原を含むまたは他人します。これらは当然の蛋白質を発生しているとの図 2 グリーンに着色され、両側が丸くなっています。

Key Elements of a Simplified Immune System
図 2 簡易免疫システムの主な要素

抗原によるリンパ球が検出されます。各リンパ球の探知機として考えることができますいくつかの抗体を持っています。各抗体は、特定の抗原に固有です。抗体抗原の一致のみおおよそであるため、単一の抗体は単一の抗原を検出すると通常、リンパ球反応トリガーされません。いくつかの抗体がその対応する抗原検出のみ後されますリンパ球刺激になるし、いくつかの並べ替えの防御反応を引き起こします。

リンパ球は self-item を検出する抗体を持たないことに注意してください。本物の抗体が、胸腺の免疫システムによって生成されますが検出任意抗体他人アポトーシスと呼ばれるプロセス血流にリリースされる前に破棄されます。

侵入検知システムの面では、TCP/IP ネットワークパケットの内容が含まれているいくつかの並べ替えがコンピューターウイルスなどの有害なデータの抗原に対応します。自己抗原は通常、非有害ネットワークパケットに対応しています。抗体は約未知の潜在的に有害のネットワークパケットに一致するビットパターンに対応します。 2 つ以上の抗リンパ球を表す体/検出器。アポトーシスは、負の淘汰と呼ばれる手法を使用してモデル化されます。

全体的なプログラムの構造

示されているデモプログラム図 1 ArtificialImmuneSystem という名前の単一 c# コンソールアプリケーションです。 Visual Studio 2010 を使用が、任意のバージョンの Visual Studio、Microsoft .NET Framework 2.0 以降が動作するはずです。わかりやすい ArtificialImmuneSystemProgram.cs に Program.cs という名前の Visual Studio テンプレート生成ファイルの名前を変更し、同様の対応するクラスの名前を変更します。全体的なプログラム構造に記載されている図 3。

図 3 人工免疫システムプログラムの構造

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

すべての使用テンプレート生成削除ステートメント、システムとその他の名前空間への参照を除いて。 BitArray クラスへのアクセスを持ってできるよう System.Collections 名前空間への参照を追加します。起動時のメッセージの後、任意のシード値が 1 を使用して静的 Random オブジェクトをインスタンス化します。

Main メソッド内のコードを比較するかどうかは図 3 のスクリーンショットと図 1、あまりにも多くのトラブルをプログラムロジックを理解してはなりません。 AIS デモへの鍵は、リンパ球のクラスの定義です。デモコードのサイズを小さく保つために注意してくださいオフに主要なアイデア、私は、通常のエラーを可能性が高い実験中が含まれますをチェック削除されます。

リンパ球クラス

リンパ球クラス 4 つのデータフィールドがあります。

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

シンプルさのパブリックスコープを持つすべてのフィールドを宣言します。抗体フィールド BitArray です。 BitArray と慣れていない場合は、アイデア各 int 32 ビットストレージが必要なためビットのコレクションを表す int 型の通常の配列を使用して非常に効率的なないです。ビット配列は、32 ビットの情報を保管、プラスいくつかのオーバーヘッドのクラスの単一の int に凝縮します。 BitArray のようなクラスを持っていないプログラミング言語では、ビットマスクとビット操作の低レベルのビット操作を行うことが必要です。

SearchTable フィールドは、検出法によるパフォーマンスを大いに向上に使用される配列です。 "年齢"フィールドは、私のデモプログラムで使用されていない; AIS の多くのシステムは、シミュレートされたリンパ球の年齢を追跡確率的殺す、年齢に基づいて新しいリンパ球を生成します。刺激のフィールドは、リンパ球オブジェクトの回数を追跡するカウンターが可能な脅威が検出されましたです。このデモでは、リンパ球刺激値 stimulationThreshold 値が 3 を超えたときに警告を発生します。

リンパ球のコンストラクターです。

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

コンストラクターには、抗原/検出器を表す 1 つの BitArray パラメーターを受け入れます。 SearchTable 配列はまもなく紹介します BuildTable という名前のプライベートヘルパーメソッドを使用してインスタンス化されます。

任意 AIS システムの主要部分の 1 つ抗原、パターンが検出されたかどうかを決定するルーチンです。正確な一致が必要な可能ではない (と本物の抗原の動作を模倣していません)。 AIS で初期の作品は抗原と入力パターンビットの同じ数があるし、抗原とのパターンで r 連続したビットの一致検出が発生するマッチング、r 連続するビットと呼ばれる手法を使用しました。後の研究は良い検出アルゴリズム r - ビットに一致するチャンクであることを示した。ビット r チャンクマッチングは抗原検出器よりもパターンをチェックするには、小さいおよび抗原 ny サブセットのパターンと一致するときの検出ことを除いて一致する r 連続するビットに似ています。たとえば、抗原が 110 パターンが 000110111 の場合は、抗原はインデックス 3 で始まるパターンを検出します。

R チャンクの瞬間をマッチングについて考える場合は、文字列の部分文字列関数とほぼ同じであることを実現します。唯一の違いはその r チャンク一致一致ビットおよび部分文字列の文字に一致します。

上記の例では、r チャンクマッチングへの単純なアプローチなどなどインデックス 0、次にインデックス 1、その 2 で始まるパターンを検討することです。しかし、このアプローチはほとんどの状況で非常に遅いです。 (通常は、テーブルと呼ばれる)、配列を作成する小さい検出器文字列前処理いくつかの洗練されたサブストリングアルゴリズムがあります。不一致が検出されたとき先を省略してパフォーマンスを向上するこの検索表を使用できます。異なるパターンをチェックする小さい検出器文字列を使用繰り返し場合 — AIS 侵入検知のように — 時間と検索テーブルを作成するために必要なメモリは劇的に改善された性能を支払うために小さな価格。

リンパ球クラス検出法は適用する BitArray クヌース-モリス-プラットサブストリングアルゴリズムを使用します。検出メソッドは、入力パターン 000110111 などを受け取り、現在のオブジェクトの抗原、110 など、パターンに一致する場合は true を返します。検出メソッドのコードに記載されている図 4。

図 4 はメソッドを検出しました。

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
}

検出メソッド検索テーブルの存在を前提とします。リコールは、リンパ球のコンストラクターがヘルパーメソッド searchTable フィールドを作成する BuildTable を呼び出します。 BuildTable のコードに記載されている図 5。

図 5 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;
}

リンパ球クラス GetHashCode と ToString のオーバーライドされた merthods を定義します。 GetHashCode メソッドは、リンパ球オブジェクトの重複を防ぐために使用され、です：

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

この実装は、BitArray 抗体フィールドが 32 ビットを持っていること仮定または少ない。現実的な状況では、32 ビット以上の抗体フィールドが重複するリンパ球のオブジェクトを扱うはそう単純ではないです。 1 つのアプローチは、BigInteger 型 (.NET Framework 4 で利用可能とそれ以降) を返すカスタムハッシュコードメソッドを定義することです。

デモプログラムで使用されるリンパ球の ToString メソッドがあります。

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;
}

自己の作成

あなたは確かに標準（非 AIS）精通しているマイクロソフト・セキュリティ主要点などのコンピュータウイルス検出ソフトウェア。これらのシステムは、既知のコンピューターのウイルス定義のローカルデータベースを格納することによって動作します。既知のウイルスパターンが検出されると、直ちに警告がトリガーされます。このようなウイルス対策システムバリエーションにトラブル対処既存のウイルスを有しが完全に新しいウイルスに直面したとき全くほとんどの状況で失敗します。 AIS 侵入検知、逆の方法で非有害であることが知られている入力パターンのセットの維持と未知パターンが検出されたときにアラートをトリガー動作します。これは、AIS の侵入検知システムできます — 原則として、少なくとも — 新しいウイルスを検出します。ただし、偽陽性を扱う — つまり、非有害な入力パターンに関する警告のトリガー — AIS システムのための主要な課題です。

実際の AIS の侵入検知システムに数日または数週間にわたって通常入力パターンの何千も収集します。これらの通常の自己パターンいずれかローカルホストまたはサーバーに格納されます。また、実際の AIS システム、自己（とリンパ球の誘導セット）時間をかけてネットワークトラフィックに通常の変化を考慮して、通常のパターンの継続的に更新する必要と思います。この記事のデモプログラムは人工的なを作成し、静的メソッド LoadSelfSet を使用して self-set:

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;
}

このメソッドは、現実的なシナリオで自己データハードコードされただろうことを示唆するダミー使用しないデータソースパラメーターを受け入れます。 BitArray のコンストラクターは、やや意外にも、true 1 ビットを表し、false はビット 0 を表す bool 値の配列を受け入れます。私はそのような方法で自己のデータを生成観察いいえ self-item 2 つ以上連続した 0 または 1 s いること。

デモプログラムでは、ヘルパーメソッド BitArrayAsString を呼び出して、ShowSelfSet のユーティリティメソッドを使用して、自己表示します。

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;
}

リンパ球のセットを作成します。

戻って人間の免疫システムのしくみの説明を参照するくださいと、リンパ球セット任意パターンの自己検出されないリンパ球オブジェクトのみを含めることがわかります。メソッド CreateLymphocyteSet で記載されて図 6。

図 6 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;
}

AIS の用語では、負の淘汰メソッド CreateLymphocyteSet を使用します。オブジェクトを生成し、その後、それ任意パターン、自己でも検出されない場合を参照してくださいにテストランダムリンパ球リンパ球はない結果ですでに設定されます。このアプローチは、むしろ原油ですより効率的です他のアプローチがあります。リンパ球の既存のオブジェクトを追跡するためにダミーの bool 値をディクショナリコレクション使用する; HashSet .NET フレームワーク 4.5 と後でより効率的な代替手段です。

ランダムなリンパ球オブジェクトランダム BitArray を生成することによって作成します。

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);
}

ヘルパーメソッド DetectsAny は、自己を受け入れ、リンパ球の自己を介してスキャンし任意のパターンを自己が、リンパ球の抗原が検出された場合に true を返します。

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;
}

デモプログラムでは、ユーティリティメソッド ShowLymphocyteSet を使用して生成されたリンパ球のオブジェクトを表示します。

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

まとめ

コードと説明この資料でを紹介した、AIS と実践的な実験のための強固な基盤を与える必要があります。研究者は、多くのオプションを示唆しています。単一リンパ球未知入力パターンよりもいくつか回のしきい値の数を検出するとたとえば、この記事のデモプログラムは警告を発します。ここの考えは実質の病原体が多くの抗原を発するです。別の可能性は、AIS システムのみ複数異なるリンパ球同じ未知パターンを検出した後、アラートをトリガーするためです。

それは、AIS 意図されていないこと侵入検知のための単一のソリューションに指摘することが重要です。むしろ、それは伝統的なウイルス対策ソフトウェアが含まれている多層防御の一部になるというものです。また、ワーク、AIS とはまだ比較的若いので、多くの未解答の質問があります。 AIS の研究のいくつかを検討したい場合は、s. の著者による記事のオンライン検索お勧めフォレスト, p. ウィリアムズと u. Aickelin。

Dr.James McCaffreyボルト情報科学株式会社は、彼はマイクロソフトのレドモンド、ワシントン州でキャンパス働くソフトウェアエンジニアの技術トレーニングを管理するために動作します。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。McCaffrey は、「.NET テストオートメーションレシピ」（Apress、2006年）の著者です。連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビュー、次技術専門家のおかげで：ダン Liebling