一種基於隱馬爾可夫模型的IDS異常檢測新方法
摘 要：提出一種新的基於隱馬爾可夫模型的異常檢測方法，主要用於以shell命令或系統呼叫為審計資料的入侵檢測系統。此方法對使用者（或程式）行為建立特殊的隱馬爾可夫模型，根據行為模式所對應的序列長度對其進行分類，將行為模式型別同隱馬爾可夫模型的狀態聯絡在一起，並引入一個附加狀態。由於模型中各狀態對應的觀測值集合互不相交，模型訓練中採用了運算量較小的的序列匹配方法，與傳統的Baum-Welch演算法相比，大大減小了訓練時間。根據模型中狀態的實際含義，採用了基於狀態序列出現概率的判決準則。利用Unix平臺上使用者shell命令資料進行的實驗表明，此方法具有很高的檢測準確性，其可操作性也優於同類方法。
關鍵詞：入侵檢測；隱馬爾可夫模型；異常檢測；序列匹配
中圖分類號：TP18；TP393.08 文獻標識碼：A
A New Anomaly Detection Method Based on Hidden Markov Models for IDS
Abstract： A new anomaly detection method based on hidden Markov models is presented for Intrusion Detection Systems with shell commands or system calls as audit data. The method constructs specific hidden Markov models to represent the behavior profiles of users or programs, and associates the classes of behavior patterns with the states of the models. Because the collections of observations corresponding to different states are mutually disjoint, the parameters of the models can be estimated by a sequence matching algorithm which is much simpler than the classical Baum-Welch algorithm. This reduces the computational complexity to a great extent. A decision rule based on the probabilities of short state sequences is adopted while the particularity of the states is taken into account. The performance of the method is tested by computer simulation with Unix users’ shell command data. The results show it maintains higher detection accuracy and practicability than other alternative approaches.
Key words： intrusion detection； hidden Markov model； anomaly detection； sequence matching
1 引言
網路入侵檢測技術主要有兩種型別，即誤用檢測和異常檢測。異常檢測是目前IDS（入侵檢測系統）研究的主要方向，其優點是不需要過多關於系統缺陷的知識，具有較強的適應性，並且能夠檢測出未知入侵，但它存在虛警概率高的缺點。異常檢測的關鍵問題是如何建立系統或使用者的正常行為模式（庫）以及如何利用該模式（庫）對當前行為進行比較和判斷。
國內外已經開展了神經網路、資料探勘、機器學習等技術在異常檢測中的應用研究，研究目標主要是提高檢測系統的準確性、實時性、高效性以及自適應性。本文提出一種新的基於隱馬爾可夫模型（HMM）的異常檢測方法，它在建模、HMM訓練以及判決準則的選取等方面與現有的HMM方法均有較大不同。實驗表明，此方法具有很高的檢測準確率和較強的可操作性。
2 現有的兩種HMM方法
IDS的輸入資料主要有兩類，分別是主機資料和網路資料。在基於系統呼叫和shell命令等主機資料的異常檢測研究中，HMM方法是一個重要的研究方向。新墨西哥大學的Warrender C等人
基於系統呼叫資料，進行了針對程式行為的異常檢測[2]。其方法是對每種程式（如sendmail、login）的正常行為建立一個HMM，將程式所用的互不相同的系統呼叫個數作為HMM的狀態數，採用Baum-Welch演算法訓練模型，並利用先驗知識對模型引數進行初始化；檢測時對資料流中的每個系統呼叫分別作一次判決。普渡大學的Lane T則基於Unix平臺上的shell命令資料，進行了針對使用者行為的異常檢測研究和實驗[1]。其方法是用單個HMM代表一個合法使用者的行為輪廓，通過反覆實驗來確定HMM的最佳狀態個數；模型的訓練中同樣採用了Baum-Welch演算法。檢測時，利用近似的前向後向演算法並根據貝葉斯準則對使用者行為進行判別。
以上兩種方法是HMM在分類問題中較為的典型用法，在訓練資料充足的情況下能夠獲得比較高的檢測準確率，但是，模型的訓練和工作中所需要的計算量很大（特別是對於程式行為異常檢測），檢測的實時性不高，這在很大程度上限制了它們的應用。
3 一種新的基於HMM的異常檢測方法
3.1 HMM概念及基本問題的描述
HMM是雙重隨機過程，其中一個是隱含的有限狀態馬爾可夫鏈，它描述狀態的轉移；另一個隨機過程描述狀態與觀測值之間的統計對應關係。HMM一般有三個假設：當前狀態只同上一狀態相關；狀態之間的轉移概率同狀態所處的具體時間無關；觀測值只與當前狀態有關。這三個假設大大降低了模型的複雜度。設觀測值序列為，相應的狀態序列為，其中,，和分別表示觀測值集合和狀態集合。HMM通常用五元組來表示，為狀態轉移概率矩陣，,其中
（1）
為觀測值概率矩陣，，其中
， （2）
為初始狀態概率向量，，其中
（3）
訓練、解碼和評估是HMM的三個基本問題。訓練是指給定觀測值序列，確定模型引數，使得最大；解碼是對於給定的和，求使最大的狀態序列；評估則是指給定模型引數，求觀測值序列的出現概率。HMM訓練、解碼和評估的.經典演算法分別是Baum-Welch演算法、Viterbi演算法和前向後向演算法。應當指出，HMM的訓練，或稱引數估計問題，是HMM在異常檢測中應用的關鍵問題；Baum-Welch演算法只是解決這一問題的經典方法，但並不是唯一的，也不是最完善的方法[3]。
3.2 基於HMM的異常檢測新方法
我們提出一種基於HMM的異常檢測新方法，主要用於Unix和Linux平臺上以shell命令為審計資料的使用者行為異常檢測，也可用於以系統呼叫為審計資料的程式行為異常檢測。下面以使用者行為異常檢測為例，按照建模、訓練、檢測的順序對這一方法進行介紹。
（1）建立兩個HMM，其中一個HMM用於描述一個或一組合法使用者的正常行為，另一個HMM用於描述（入侵者或合法使用者的）異常行為。（在對異常行為缺乏瞭解的情況下，可以只建立一個HMM來描述合法使用者的正常行為。）兩個HMM的狀態集合以及各狀態對應的觀測值集合相同，其狀態對應於合法使用者的行為模式型別。按照行為模式所對應的shell命令序列的長度對其進行分類，並根據合法使用者的正常訓練資料（歷史上的正常行為）確定每個狀態對應的觀測值集合。
入侵檢測中行為模式是指使用者操作或程式執行過程中體現出的某種規律性。在以shell命令為審計資料的使用者行為異常檢測中，使用者的行為模式通常用shell命令序列來表示[2]。（根據Lane T的實驗結論[1]，長度在1到15之間的shell命令序列能夠表示一般的使用者行為模式。）這裡，我們將shell命令序列的長度作為行為模式分類的依據，把長度相同的shell命令序列所表示的行為模式劃為同一種類。建模的首要問題是確定合法使用者正常行為模式的種類個數，以及相應的shell命令序列長度集合，其中表示第類正常行為模式對應的shell命令序列的長度，且。和對檢測效能有直接影響，在選擇它們時，需充分考慮合法使用者的行為特點，同時還要考慮模型的複雜度及檢測效率（和越大，檢測系統的儲存量和工作中的運算量也會越大）。我們將HMM的狀態個數設為，狀態集合設為，其中前個狀態同合法使用者的類正常行為模式一一對應，第個狀態為附加狀態，它對應於合法使用者的正常歷史行為（正常訓練資料）中未出現過的行為模式（型別），並規定這類行為模式對應的命令序列長度。
和確定之後，需根據合法使用者的正常訓練資料確定HMM各狀態對應的觀測值集合，其中為狀態對應的觀測值集合，即第類行為模式對應的命令序列集合，它包含若干個長度為的命令序列；這裡，HMM狀態所對應的觀測值（或稱觀測事件）是命令序列。設一個合法使用者的正常訓練資料為，它是該使用者在正常操作時所執行的長度為的shell命令流，其中表示按時間順序排列的第個shell命令；對應的長度為（）的命令序列流可表示為，其中命令序列。我們設定一個概率門限，將（）中出現概率大於的命令序列視為合法使用者的（正常）行為模式，即由這些命令序列組成（一個序列的出現概率是指此序列在相應序列流中的出現次數與該序列流中的序列總數之比）。附加狀態對應的觀測值集合包括兩部分，一部分是由正常訓練資料中未出現過的命令組成的長度為1的序列，另一部分則有所區別，當時(此時)，它是中出現概率小於或等於的序列，當時，它是中的所有序列。當時（），，即不同狀態對應的觀測值集合是不相交的，這和一般的HMM不同，也是此方法的一個主要特點。需要指出，合法使用者可以只有一個，也可以有多個；當有多個合法使用者時，可將這些使用者的正常訓練資料組合在一起構成總的訓練資料。
（2）利用序列匹配方法計算兩個HMM的引數。
設描述合法使用者正常行為的HMM引數為，其中和的計算方法如下：
第一步：根據得到（）。設定，，，，。
第二步：如果,將與進行比較；否則，,跳至第五步。
第三步：如果，且，則，，，返回執行第二步；如果，且，則，，，，，，，返回執行第二步；如果，則。
第四步：如果，返回執行第二步；如果(此時)，且，則，，，返回執行第二步；如果，且，則，，，，，，，返回執行第二步。
第五步：對於，。對於，。
上述的計算過程是採用序列匹配的方法，按照時間順序逐個找出中的行為模式及其對應的狀態，同時對每個狀態的出現次數和狀態之間的轉移次數進行統計，從而得到狀態轉移概率矩陣和初始狀態概率向量。引數計算時假設了HMM中個狀態的隱含馬爾可夫鏈是一個各態歷經過程。由於檢測時不需要用到觀測值概率矩陣，其計算方法不再贅述。
設描述異常行為的HMM引數為，異常訓練資料為，它是入侵者（非法使用者）或合法使用者在非法操作或誤操作時所執行的shell命令流，和可根據同樣採用以上的序列匹配方法進行計算。在缺乏異常訓練資料時，可不用計算此HMM的引數。
（3）檢測時，利用計算出的HMM引數，基於狀態序列出現概率對被監測使用者的行為進行判決。
設被監測使用者在被監測時間內所執行的shell命令流為。檢測時要利用前面引數計算中的序列匹配方法，由得到狀態序列及其對應的觀測值序列，其中為中的狀態總數，，表示按時間順序排列的第個狀態，表示與對應的觀測值(命令序列)，的長度為（）。
為了實時監測使用者的行為，我們用滑動窗在中擷取短序列，以短序列為資料單元進行分析。設短序列為，其中表示短序列的長度（），。相應的狀態短序列為。和對應的短序列流可分別表示為和。
按照傳統準則，應根據對被監測使用者行為進行判決，其計算公式為：
（4）
這裡，我們沒有采用傳統準則，而是將作為判決依據：
（5）
其中表示引數為（的取值為1或2）的HMM所描述的行為的出現概率。
我們之所以用而不用作為判決依據，主要基於以下考慮：一、觀測值集合與狀態集合之間有明確的對映（滿射）關係，每個狀態所對應的觀測值集合是根據合法使用者的正常訓練資料（正常歷史行為）確定的，因而狀態本身以及狀態之間的轉移能夠反映正常行為與異常行為之間的行為差別。二、的計算量比小，它只用到了HMM引數中的初始狀態概率向量和狀態轉移概率矩陣。三、在（4）式中，對的計算假設了觀測值之間是相互獨立的，即觀測值只與當前狀態有關，根據我們的實驗和分析，這一假設並不是很符合使用者的實際情況，因而，根據（4）式得到的不宜作為判決依據。
考慮到使用者在短時間內的行為可能會偏離其歷史行為，檢測中我們並不直接利用對被監測使用者的行為進行判決，而是對其做了如下的加窗平滑處理：
（6）
此外，在沒有異常訓練資料，無法得到引數和的情況下（此時只建立描述合法使用者正常行為的HMM），可以只對進行變換和加窗處理，得到如下判決值：
（7）
（6）、（7）兩式中，表示狀態序列對應時刻的判決值，，為窗長度（中第個狀態短序列及其後面的每個短序列所對應的時間點上都有一個判決值輸出）。對設定一個門限，若它大於這個門限，將被監測使用者的當前行為判為正常行為（或將此使用者判為合法使用者），否則，將其判為異常行為（或將此使用者判為非法使用者）。是一個重要引數，它決定了從被監測使用者行為發生到檢測系統對其行為做出判斷的最短時間（即檢測時間）。在不考慮計算時間的情況下，檢測時間為個狀態持續時間。
3.3 特點分析
以上基於HMM的使用者行為異常檢測方法主要有以下幾個特點：
（1）它是一種異常檢測方法，這主要體現在描述正常行為和異常行為的HMM狀態以及各狀態對應的觀測值集合都是根據合法使用者的正常訓練資料確定的，描述正常行為的HMM引數也是根據此訓練資料計算得到的。在計算描述異常行為的HMM引數時，需要用到異常訓練資料；但是，當採用（7）式計算判決值時，無需考慮該HMM的引數。
（2）在Lane T的方法中，HMM狀態對應的觀測值是使用者的shell命令，最佳狀態個數是通過反覆實驗確定的。而此方法中，HMM狀態對應的觀測值（或稱觀測事件）不是shell命令，而是長度可變的shell命令序列，狀態本身具有明確的含義。模型中，狀態的“隱含”是指觀測資料（使用者shell命令流）中的狀態不是直接可見的，而是需要通過序列匹配得到。
（3）根據HMM狀態的特點及實際含義，採用了基於狀態序列出現概率的判決準則，減小了判決中的計算量，提高了檢測的實時性。
（4）HMM的訓練和解碼均採用了序列匹配方法，同Lane T的傳統方法相比，較大程度地減小了計算量，縮短了訓練和解碼的時間。
4 實驗設計及結果分析
實驗中，我們採用了普渡大學Lane T網上公佈的shell命令實驗資料[1]，其資料庫包含八個Unix使用者在兩年時間內的活動記錄。每個使用者的資料檔案中均濾除了使用者名稱、主機名、網址等標識資訊，僅保留了shell命令的名稱及引數；使用者命令流中的命令按照在shell會話中的出現次序進行排列，不同的shell會話按照時間順序進行連線，每個會話開始和結束的時間點上插入了識別符號；實驗資料的詳細說明可參見文獻[1]。
我們利用四個使用者的資料對以上方法的效能進行了驗證，其中user1、user2、user3設為非法使用者（其行為設為異常行為），user4設為合法使用者（其行為設為正常行為）。每個使用者各有15000個命令，user4的前10000個命令作為正常訓練資料用於兩個HMM狀態和觀測值集合的確定以及描述正常行為的HMM引數的計算，user1、user2、user3的前10000個命令組合在一起作為異常訓練資料用於計算描述異常行為的HMM引數，每個使用者的後5000個命令用作測試資料。實驗的引數設定為，，，，，並假設（即正常行為和異常行為的出現概率相等）。
檢測時，在user4的後5000個命令中共出現1748個狀態，狀態對應的命令序列（觀測值）的平均長度為2.9；在user1、user2、user3的後5000個命令中，分別出現3497、3436、2943個狀態（其中相當一部分為附加狀態），狀態對應的命令序列的平均長度為1.5，這表明長度為5和3的命令序列所表示的合法使用者的正常行為模式在三個非法使用者的測試資料中較少出現。圖1給出了由（6）式計算的user4和user1的判決值曲線，圖2給出了根據（7）式計算的兩條判決值曲線（為繪圖方便，對橫座標做了平移）。由兩圖可見，合法使用者（user4）和非法使用者（user1）的判決值曲線具有良好的可分性。
圖1 （6）式對應的判決值曲線 圖2 （7）式對應的判決值曲線
實驗中，通過調整判決門限可以得到不同虛警概率條件下對三個非法使用者的異常行為（或使用者類別）的平均檢測概率。表1給出了（6）式和（7）式兩種判決值計算方法對應的實驗結果。
表1 兩種判決值計算方法對應的實驗結果
虛警概率 0 0.001 0.005 0.010 0.050
（6）式對應的
平均檢測概率 0.929 0.932 0.939 0.944 0.996
（7）式對應的
平均檢測概率 0.933 0.938 0.953 0.960 0.992
根據實驗結果，當虛警概率為0時，兩種判決值計算方法對應的平均檢測概率均可達到90%以上。而且，在虛警概率較低的區間，（7）式對應的平均檢測概率與（6）式非常接近，這說明僅利用描述正常行為的HMM引數即可獲得良好的檢測效能。因而，在無法得到異常訓練資料及相應HMM引數的情況下，我們可以只建立一個描述合法使用者正常行為的HMM來進行異常檢測。
5 結束語
本文提出一種新的基於HMM的IDS異常檢測方法。實驗表明，此方法具有很高的檢測準確率和較強的可操作性。根據實驗結果，當引數（特別是W和C）設定不同時，檢測效能會有一定的變化，因而，根據具體使用者的行為特點選擇合適的引數是實際應用中提高檢測效能的重要途徑。此外，本文的方法還適用於以系統呼叫為審計資料的程式行為異常檢測，但是，同用戶行為相比，程式行為具有一些不同的特點，所以具體的操作方式及檢測效能還有待分析和驗證。
參考文獻
[1] Lane T. Machine learning techniques for the computer security domain of anomaly detection [D]ue University，2000.
[2] Warrender C，Forrest S，Pearlmutter B. Detecting intrusions using system calls: alternativedata models[A]. Proceedings of the 1999 IEEE Symposium on Security and Privacy[C]. Berkely，California，USA：IEEE Computer Society，1999：133-145.
[3] Rabiner L R，Juang B H. An introduction to hidden Markov models[J]. IEEE ASSP Magazine，1986(1)：4-16.
[4] Kosoresow A P，Hofmeyr S A. A shape of self for UNIX processes[J]. IEEE Software，1997，14(5)：35-42.