本文章是由機器翻譯。

測試回合

用於入侵偵測的人工免疫系統

James McCaffrey

下載代碼示例

James McCaffrey
入侵偵測人工免疫系統 (AIS) 是一個軟體系統,模特的人體的免疫系統,以保護電腦網路免受病毒和類似的網路攻擊行為的某些部分。基本想法是人體免疫系統 — — 這是淋巴細胞 (白血細胞)、 抗體和許多其他元件組成的一個複雜系統 — — 由來已久,提供強大的保護,防止有害的毒素和其他病原體的時間。因此,建模行為的人體免疫系統可能提供有效的架構,對網路攻擊。

在這篇文章我描述的一些人工免疫系統的原則,並提出一個程式來演示這些原則。關於認可機構保護工作是仍然相對較新,在我看來,沒有商業的實現都是相當準備就緒。本文仲介紹的代碼將不直接使您能夠創建一種切合實際的網路入侵系統,但至少四個理由為什麼您可能會發現這篇文章值得一讀。首先,代碼會給你一個起點的動手實驗,用一個簡單的 AIS 系統。第二,解釋的原則將把你送是相當困難的初始跨欄到這一領域,並允許您瞭解對認可機構的研究論文。第三,在本文中,在特定的 r 塊位匹配和陰性選擇,使用的程式設計技術的幾個可以在其他程式設計方案中很有用。第四,您可能會發現基於行為本身就有趣的人體免疫系統的軟體系統建模的想法。

最好的感受我是來看一看的螢幕擷取畫面演示的運行,所示圖 1。該演示程式開始通過創建一組六個正常模式 (已知不是一些網路攻擊的一部分的模式) 代表 TCP/IP 網路資料包中的二進位形式。認可機構術語中,這被稱為 self 集。當然,在實際的 AIS 系統,自設將可能包含數萬或數十萬的模式,並且每個模式會大得多 (通常 48 256 位) 比在這裡使用的 12 位。接下來,該演示程式創建三個人工淋巴細胞。每個淋巴細胞已有四位 (再次,人工小) 的類比的抗體、 年齡和刺激的欄位。該抗體欄位是本質上是一種探測器。如您很快就會看到,淋巴細胞創建,以便他們都不檢測中自設的任何模式。現在,觀察每個淋巴細胞有三個連續的 0 或 1s,但中自設的模式沒有三個連續相同的位值。

Artificial Immune System Demo
圖 1 人工免疫系統演示

已初始化系統後,該演示程式開始微小模擬與六個輸入模式。第一個輸入檢測淋巴細胞 1,但由於每個淋巴細胞有啟動閾值,淋巴細胞不會觸發報警。在時間 t = 3,淋巴細胞 1 檢測到另一個可疑輸入但,再次,尚不超過閾值。但在時間 t = 5,淋巴細胞 1 檢測到第三個可疑的輸入的資料包和類比觸發。

在下面的章節中,我將首先解釋人體免疫系統,用於建模的認可機構的關鍵概念。然後我陪你走的截圖中的代碼通過圖 1。最後,我會給你一些其他的參考資料和有關認可機構的幾點意見。本文假定您有至少中間級與現代程式設計語言的程式設計技巧。我使用 C# 的演示程式,但我會解釋的你需要更改如果你想要我的代碼重構到另一種語言 (如 Visual Basic.NET 或 Python。我目前生成的螢幕擷取畫面中的所有代碼圖 1; 代碼也是可用在 archive.msdn.microsoft.com/mag201301TestRun

人體免疫系統

一個高度簡化的免疫系統的關鍵要素所示圖 2。有害的專案是稱為抗原的蛋白質。在圖 2 抗原的紅色,和有尖角。人體還包含許多非有害的抗原稱為自我-抗原,或 self-items。這些自然產生的蛋白質和在圖 2 將標記為綠色和有圓角的邊。

Key Elements of a Simplified Immune System
圖 2 的一個簡化的免疫系統的關鍵要素

淋巴細胞檢測抗原。每個淋巴細胞有幾個的抗體,可以被認為是探測器。每個抗體是特定于特定的抗原。通常情況下,因為抗體抗原匹配只是近似的淋巴細胞不會觸發反應單抗體檢測單一抗原時。只有幾個抗體檢測其相應抗原後將淋巴細胞成為刺激和觸發某種形式的防禦性反應。

注意沒有淋巴細胞檢測 self-item 的抗體。真正的抗體生成的胸腺中的免疫系統,但任何檢測到的抗體 self-items 被摧毀之前被釋放到血液流中,一個稱為細胞凋亡的過程。

入侵偵測系統,在抗原對應其內容包含某種有害資料例如,電腦病毒的 TCP/IP 網路資料包。自我抗原對應于正常、 無有害網路資料包。抗體對應于大約與匹配一個未知的、 可能有害的網路資料包的位模式。淋巴細胞表示兩個或更多的反­機構和檢測器。細胞凋亡是使用一種稱為陰性選擇技術建模的。

程式的總體結構

在所示的演示程式圖 1 是一個 C# 主控台應用程式命名為 ArtificialImmuneSystem。我使用 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

我刪除了所有的範本生成使用除引用系統和 System.Collections.Generic 的命名空間聲明。 所以我可以有訪問 BitArray 類添加到 System.Collections 命名空間的引用。 啟動消息之後, 我具現化靜態隨機物件使用任意種子值為 1。

如果您比較中的 Main 方法中的代碼圖 3 的截圖中與圖 1,您不應該有太多理解程式邏輯的麻煩。 認可機構演示的關鍵是淋巴細胞類的定義。 請注意,以保持較小的演示代碼的大小和清除的主要思路,我刪除了所有正常的錯誤並檢查您很可能將包括在試驗期間。

淋巴細胞類

淋巴細胞類有四個資料欄位:

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 的使用一個普通陣列表示的位的集合是 int 的效率非常低,因為每個 int 需要存儲的 32 位。 位陣列凝結成單個 int 存儲,再加上一些開銷為該類資訊的 32 位。 別有樣 BitArray 類的程式設計語言需要您做低級位操作位掩蔽與位操作。

SearchTable 欄位是一個陣列,它的檢測方法用於極大地提高性能。 年齡欄位不用在我的演示程式 ; 許多 AIS 系統跟蹤類比淋巴細胞的年齡和近親殺死並生成基於年齡的新淋巴細胞。 刺激欄位是一個計數器,用於跟蹤多少次淋巴細胞物件已檢測到可能的威脅。 在此演示中,淋巴細胞刺激值超過 3,stimulationThreshold 值時,會觸發警報。

淋巴細胞建構函式是:

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

建構函式接受一個 BitArray 參數,表示一種抗原/檢測器。 SearchTable 陣列是使用一個名為 BuildTable,我會于短期內提交的私有的 helper 方法具現化的。

任何認可機構系統的關鍵區段之一是該常式,用於確定是否一種抗原檢測模式。 要求精確匹配不是可行 (和不模仿真實抗原行為)。 早期工作對認可機構使用一種稱為 r-連續位匹配,其中抗原和輸入的模式都有相同的比特數和抗原和模式匹配中 r 個連續位時發生檢測技術。 後來的研究表明一種更好的檢測演算法是 r 塊位匹配。 R 塊位匹配就是類似于 r-連續位匹配只不過抗原檢測儀是小於的模式要檢查,和檢測時發生抗原匹配模式的 ny 子集。 例如,如果在抗原是 110,一種模式是 000110111 抗原檢測起始索引 3 處的模式。

如果你想想 r 塊匹配了一會兒,你就會知道它是一個字串的子字串函數幾乎相同。 唯一的區別該 r 塊匹配的匹配項雙邊投資條約和匹配的子字串的字元。

在前面的示例中,r 塊匹配到一個簡單的方法將檢查模式起始索引為 0,然後在索引為 1,然後 2,等等。 然而,這種方法是在大多數情況下十分緩慢。 有幾個尖端的子串演算法,預處理的較小的探測器字串來創建陣列 (通常稱為表)。 可以使用此搜索表,向前跳,遇到不匹配時,並極大地提高性能。 在較小的探測器字串反復用於檢查不同模式的情況下 — — 如認可機構入侵偵測 — — 的時間和創建搜索表所需的記憶體是小的代價,以大大提高性能。

淋巴細胞類檢測方法使用應用於 BitArray Knuth-莫里斯-普拉特子串演算法。 檢測方法接受 000110111 等輸入的模式,並返回 true,如果當前物件的抗原,如 110,與模式匹配。 檢測方法的代碼中列出圖 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
}

檢測方法假定搜索表的存在。 記得淋巴細胞建構函式調用 BuildTable 創建的 searchTable 欄位的説明器方法。 中列出的代碼 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 位的現實情況下,處理重複的淋巴細胞物件不是那麼簡單的。 一種辦法將定義一個自訂雜湊代碼方法返回 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;
}

創建自設

您當然熟悉與標準 (非認可機構) 的電腦病毒檢測軟體,如 Microsoft 安全要點。 這些系統通過存儲的已知的電腦病毒定義的本機資料庫的工作。 當檢測已知的病毒模式時,立即警報觸發。 這種防病毒系統上現有的病毒,有麻煩處理變動和完全在大多數情況下,面對一種全新的病毒時失敗。 認可機構入侵偵測工程以相反的方式通過維護一組已知為非有害的輸入模式,然後觸發警報時檢測到未知的模式。 這使得 AIS 入侵偵測系統 — — 在原則上,至少 — — 來檢測新病毒。 然而,處理誤報 — — 也就是說,觸發警報上非有害的輸入模式 — — 是 AIS 系統的重大挑戰。

真正的 AIS 入侵偵測系統會收集數以千計的正常輸入模式過去一天或幾周。 本地主機或伺服器上,將存儲這些正常的自設的模式。 此外,實際的 AIS 系統會不斷更新自設 (和誘導的淋巴細胞集) 的正常模式,以便隨著時間的推移核算的網路交通正常變化。 在這篇文章的演示程式創建人工、 靜態自訂使用 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;
}

該方法接受一個道具不使用資料來源參數表明現實情景中自設的資料不會硬編碼。 BitArray 建構函式,有點令人驚訝的是,接受 bool 值,其中 true 表示 1 的位,false 表示 0 位的陣列。 觀察我以這種方式生成的 self 集的資料沒有 self-item 有兩個以上連續 0 或 1s。

該演示程式使用實用程式方法,其中要求説明器方法,BitArrayAsString,ShowSelfSet 顯示 self 集:

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

在認可機構術語中,CreateLymphocyteSet 方法使用不利的選擇。 物件是生成的然後進行測試,查看它不檢測任何模式中自設,,而且,如果隨機淋巴細胞淋巴細胞不已經在結果集中。 這種做法是相當粗糙,並有其他更有效的方法。 我使用字典集合道具 bool 值來跟蹤淋巴細胞的現有物件 ; 在.NET 框架 4.5 及更高版本的 HashSet 是更為有效的替代。

通過生成隨機 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 系統需要多個不同淋巴細胞檢測同一未知的模式後,才會觸發警報。

它是重要的是要指出的是認可機構,並不是用於入侵偵測單個解決方案。 相反,它意味著一種多層防禦,其中包括傳統的防毒軟體的一部分。 此外,因為與認可機構的工作仍然相對年輕,還有很多懸而未決的問題。 如果您想要檢查一些對認可機構的研究,我推薦連線搜索文章的作者 S. 福雷斯體育 威廉斯和美國 Aickelin。

Dr. James McCaffrey 為伏資訊科學 Inc.,他在管理工作在微軟雷德蒙德,華盛頓州,校園的軟體工程師的技術培訓工作。他曾經參與過多項 Microsoft 產品的研發,包括 Internet Explorer 和 MSN Search。麥卡弗裡是作者的".NET 測試自動化食譜"(Apress,2006年)。他可以在達成 jammc@microsoft.com

由於以下的技術專家對本文的審閱: Dan Liebling