基于層次隱馬爾科夫模型和變長語義模式的入侵檢測方法

段雪濤，賈春福,2，劉春波

(1. 南開大學 信息技術科學學院，天津 300071；2. 國家計算機病毒應急處理中心，天津 300457)

1 引言

入侵檢測是計算機信息系統(tǒng)安全保障的關鍵技術之一，是位于防火墻和訪問控制之后重要的安全防護措施。Forrest[1,2]等人將人工免疫的思想引入到入侵檢測技術中，構造計算機系統(tǒng)的正常行為模式庫，并通過比對系統(tǒng)運行時的模式與正常行為模式庫的方法來判斷系統(tǒng)是否異?；虮蝗肭帧?/p>

目前，大多數研究人員通常都利用一組定長的系統(tǒng)調用短序列模式來描述進程的正常運行狀態(tài)。使用定長短序列方法的一個主要局限就是很難合理地選擇短序列的長度。一般來說，定長短序列的長度通常是根據經驗來選擇，序列的長度一般選取為4至8之間。短序列模式越長，入侵檢測系統(tǒng)就越傾向于捕獲更多的異常，但同時模式庫的規(guī)模會越大，算法的執(zhí)行效率也會降低，而且更重要的是誤報率也會增加，對建庫和檢測都會造成困難[3]。而采用短的序列會造成區(qū)分度降低，增大漏報率。這樣使得定長序列的檢測方法難以兩全，很難在存儲空間方面和檢測效率方面都較好地滿足實時檢測的需要。Lee[4]等人利用條件熵模型來求最優(yōu)短序列的長度，然而系統(tǒng)調用序列的局部模式好比進程的基因片斷，這樣的局部模式可以認為是一個功能片段，它代表了一個有特定意圖的操作流程，同時也蘊涵了進程的行為方式。由于文獻[4]的條件熵模型在系統(tǒng)調用序列的收集過程中跨越整個進程的執(zhí)行過程，忽略了進程執(zhí)行語義的階段性以及不同進程執(zhí)行語義的差異性。因此，筆者認為在整個數據集上采用條件熵模型通過構造定長序列模式來描述進程行為并不合理。但是變長模式的抽取算法過于復雜，目前的算法[5～8]復雜度過高。

可以注意到，每個程序都是由很多子函數組成，而程序中的子函數恰如一個個有著特殊意義的語義基因片段，這些片段呈現(xiàn)出明顯的層次特征和語義關系。在本文中，將利用進程堆棧中的函數返回地址鏈來抽取系統(tǒng)調用的變長序列模式，并使用層次隱馬爾科夫模型（HHMM， hierarchical hidden Markov model）來構造一種能夠利用變長模式語義關系的新入侵檢測模型。

2 變長語義模式的提取

根據操作系統(tǒng)中函數調用的原理，在向操作系統(tǒng)內核發(fā)起系統(tǒng)調用請求時，所有與之相關聯(lián)的函數調用的返回地址均存放在進程堆棧中，通過解析進程堆?？梢垣@取與系統(tǒng)調用相關聯(lián)的函數返回地址。本文使用函數返回地址來表示對應的函數調用，從而得到系統(tǒng)調用序列的函數返回地址鏈。

理論上來說，對于一個進程，其系統(tǒng)調用序列對應的函數返回地址鏈均有相同的尾鏈，即 main函數的返回地址。相鄰的一段系統(tǒng)調用，如果它們均是由某一個上層函數調用衍生，則它們對應的地址鏈的后幾個節(jié)點相同。可以根據地址鏈信息之間的關聯(lián)關系，對所有系統(tǒng)調用的函數返回地址鏈進行關聯(lián)。以地址鏈的尾節(jié)點為起始端，對所有的地址鏈信息進行歸并，得到一個與進程對應的樹形函數地址結構。圖1是進程執(zhí)行的一個簡單程序轉化為函數調用樹形結構的例子。其中，A～F代表函數調用的返回地址；S1～S9代表依次執(zhí)行的系統(tǒng)調用。因此，中間葉節(jié)點分支處的系統(tǒng)調用可以構成一條變長系統(tǒng)調用短序列模式。

進程堆棧中的函數返回地址鏈反映了程序內部函數依次調用的關系，從一定程度上反映了程序結構。這種利用函數返回地址鏈來提取變長序列模式方法的基本思想是根據產生系統(tǒng)調用的不同函數來分解系統(tǒng)調用序列從而得到變長模式。與其他尋找變長模式的方法相比，這種方法中的每個模式分別代表了程序按某一路徑執(zhí)行的函數產生的系統(tǒng)調用序列，在功能上表征了某一個程序的函數訪問系統(tǒng)內核資源的情況。

圖1 函數返回地址樹形結構

3 基于HHMM的入侵檢測模型

由于提出的變長系統(tǒng)調用模式提取方法構造出的短序列具有明顯的層次結構和狀態(tài)轉移特性，而這種結構特征恰與統(tǒng)計方法中的HHMM模型相吻合，由此，希望能夠構造出一種適合于入侵檢測的HHMM模型。

3.1 HHMM模型簡介

HHMM是隱馬爾科夫模型[9,10]的一種擴展，是一種結構化的多層次隨機過程[11]。HHMM 并不直接輻射出觀測符號，它擁有一個根狀態(tài)節(jié)點，并且由根狀態(tài)節(jié)點輻射出一系列子狀態(tài)，而這些子狀態(tài)又可以獨立地被看作是一個 HHMM，并且以迭代的方式向下層子節(jié)點輻射。這種迭代的輻射方式最終將終結于一類特殊的狀態(tài)節(jié)點，稱為輸出狀態(tài)，這種輸出狀態(tài)將向外放射出類似于 HMM 的觀測符號。而其他沒有放射出觀測符號的狀態(tài)，稱為抽象狀態(tài)或中間狀態(tài)。定義由中間狀態(tài)傳遞到其子狀態(tài)的過程，稱之為垂直轉移。定義在同一層次的狀態(tài)之間的轉移為水平轉移。因此，整個HHMM可以抽象為一個樹形結構，樹的根節(jié)點就是HHMM的根狀態(tài)，樹的葉節(jié)點就是HHMM的輸出狀態(tài)。

為了描述HHMM，需要定義以下符號或變量：

∑：表示有限符號集。

∑*：表示∑中所有可能出現(xiàn)的組合。表示 ∑*中出現(xiàn)過的一個觀察序列。表示HHMM中的一個狀態(tài)，i表示該狀態(tài)編號，d表示該狀態(tài)的層次編號。根狀態(tài)節(jié)點的層次編號為 1，輸出狀態(tài)的層次編號為D。

|qd|：表示一個中間狀態(tài)所擁有的自狀態(tài)數

i量。在i明確時，可以直接用 qd表示。使用以上符號，HHMM可以定義為

圖2是一個4層的HHMM抽象圖。粗線的箭頭表示垂直狀態(tài)轉移，黑色的箭頭表示水平狀態(tài)轉移，虛線的箭頭表示本層終止狀態(tài)返回上一層父狀態(tài)。為了簡化表示，輸出狀態(tài)在本圖中被省略。

圖2 HHMM的抽象描述圖

3.2 HHMM序列概率計算與參數估計算法

HHMM是一種具有層次結構的HMM?？梢允褂脛討B(tài)規(guī)劃Baum-Welch算法來計算序列產生的概率。定義“前向”概率為

也就是，“前向”概率表示在t時刻由狀態(tài) qd-1產生局部觀測符 ot… ot+k，且在t+k時刻生成 qd的概率。通過計算在d層所有這樣的狀態(tài)概率之和，可以得到：

與此類似，可以得到HHMM的“后向”概率為

為了能夠對HHMM的參數進行估計，需要添加與垂直方向狀態(tài)轉移過程相對應的路徑變量。定義以下變量：

和

其中， ξ (t,qid,qdj ,qd-1)：表示在時刻 t生成觀測符號 ot之后，且生成觀測符號 ot+1之前，由狀態(tài) qid到狀態(tài) qdj的水平狀態(tài)轉移概率。表示在生成觀測符號 ot之前，向狀態(tài) qid的水平狀態(tài)轉移概率。表示在生成觀測符號 ot之后，離開狀態(tài) qid的水平狀態(tài)轉移概率。表示經由狀態(tài) qid在時刻 t生成觀測符號 ot之前，狀態(tài) qd-1的概率。

基于這些關于路徑的變量定義，可以得到如下參數重估算法：

為了能夠找到模型的一組最佳參數，迭代計算χ以及輔助路徑變量，之后利用以上方程來計算新的參數。

3.3 HHMM入侵檢測模型

HHMM適用于多種應用環(huán)境，如文本分類、手寫識別等。在本文提出的基于 HHMM 的入侵檢測方法中，將利用進程堆棧中的函數調用地址鏈構造 HHMM 的狀態(tài)集，并使用變長系統(tǒng)調用序列來構造 HHMM 的觀測符號集。與傳統(tǒng)的HMM 相比，這種模型的構造方法對于描述進程語義結構更加適合，對于變長系統(tǒng)調用短序列的切分也更加合理。

該HHMM模型分為2個階段：訓練階段和檢測階段。

在訓練階段，利用進程堆棧中的函數調用地址鏈信息來切分變長系統(tǒng)調用短序列，定義每條函數調用地址鏈組成HHMM的狀態(tài)，并定義各進程在相應狀態(tài)鏈下產生的系統(tǒng)調用短序列為HHMM的觀測符號，以此來構造HHMM的樹形模型結構。

下面以一個簡單的程序為例，說明該模型樹形結構的構造方法。程序代碼如下：void func1(FILE *fp) {

char str1[20];

memcpy(str1, "cantoluna", 10);

fwrite(str1, 10, 1, fp);

printf("cantoluna is record in the object file! ");

}

void func2(FILE *fp) {

char str2[20];

memcpy(str2, "pastorale", 10);

fwrite(str2, 10, 1, fp)

printf("pastorale is record in the object file! ");

}void main(void) {

FILE *fp = fopen("secret_garden.txt", w+);

int i = getc();

if (i ＞ '0')

func1(fp);else (i ＜= '0')

func2(fp);fclose(fp);}

這段程序包括一個主程序以及2個子程序，實現(xiàn)的功能是根據輸入條件在指定文件中寫入不同的字符串。根據函數調用關系，main函數是根，對應 HHMM 的根狀態(tài)；main函數直接調用的函數fopen、getc、func1、func2和 fclose分別對應 HHMM的第2層狀態(tài)；func1和func2 這2個函數所調用的memcpy等函數則對應HHMM的第3層狀態(tài)。第2層的fopen、getc和fclose以及第3層的memcpy等函數是庫函數，不再調用其他函數，因而對應HHMM 的輸出狀態(tài)。再考慮到同一層函數執(zhí)行時的邏輯順序，并將每條函數調用地址鏈對應的系統(tǒng)調用短序列作為相應輸出狀態(tài)的觀測符號，即可構造出如圖3所示的HHMM樹形結構。

在生成模型的樹形結構后，再采用上文給出的推廣的Baum-Welch算法對HHMM進行參數估計。

在檢測階段，仍然根據進程堆棧中的函數調用地址鏈獲得進程在實際運行環(huán)境中的變長語義模式，并按照上文給出的HHMM序列概率計算方法計算出該模型下變長序列出現(xiàn)的概率。如果計算出的 (|)POλ小于預先設定的閾值，則判定為異常入侵行為；否則，認為是正常進程行為。

4 實驗

4.1 實驗數據介紹

采用 LKM[12]技術來截獲操作系統(tǒng)產生的系統(tǒng)調用以及進程在運行時的堆棧信息。通過模擬用戶的正常行為來收集正常行為模式，通過惡意代碼與入侵腳本的攻擊來收集異常行為模式。在收集系統(tǒng)調用短序列的時候，只記錄與操作系統(tǒng)服務進程相關的行為模式。在實驗過程中，使用80%的正常行為模式來訓練該入侵檢測模型，并使用其余20%的正常數據以及所有的異常數據作為檢測數據。表1給出了ftpd和sendmail守護進程的實驗數據收集情況。

圖3 根據函數調用地址鏈構造的HHMM樹形結構實例

表1 實驗數據源描述

4.2 實驗結果

在實驗中，比較了傳統(tǒng)的HMM模型與HHMM模型的入侵檢測效果，對比結果采用ROC（receiver operating characteristic）圖[13]來描述，如圖4和圖5所示。顯然，不論對 ftpd進程，還是對 sendmail進程，HHMM 模型與傳統(tǒng)的HMM模型相比，都具有更好的檢測效果，在誤報率較低的情況下，能提供更高的檢測率。

通過對實驗結果的分析還發(fā)現(xiàn)，這種HHMM模型不僅狀態(tài)數較少，并且其觀測符號集數量也控制在一定范圍之內。這是由于其觀測值也可以理解為由一段段變長系統(tǒng)調用序列所構成的語義模式片斷。

圖4 HHMM與HMM針對ftpd守護進程的測試結果比較

圖5 HHMM與HMM針對sendmail守護進程的測試結果比較

5 結束語

與定長系統(tǒng)調用短序列方法不同，本文提出了一種使用變長系統(tǒng)調用短序列的入侵檢測思路。這種思路以進程執(zhí)行語義為出發(fā)點，對采集到的系統(tǒng)調用按照語義行為切分短序列。此外，由于變長系統(tǒng)調用短序列之間具有嚴格的層次結構和狀態(tài)轉移關系，因此本文提出了一種基于HHMM的變長模式入侵檢測方法。實驗證明這種方法具有良好的檢測效果。

[1] FORREST S, HOFMEYR S A, SOMAYAJI A, et al. A sense of Unix processes[A]. Proceedings of the 1996 IEEE Symposium on Research in Security and Privacy[C]. 1996.120-128.

[2] FORREST S, PERELSON A S, ALLEN L, et al. Self-nonself discrimination[A]. Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy[C]. 1994. 202-212.

[3] LEE W, STOLFO S J. Data mining approaches for intrusion detec-tion[A]. Proceedings of the 7th USENIX Security Symposium[C]. San Antonio, Texas, 1998.

[4] LEE W, XIANG D. Information theoretic measures for anomaly detection[A]. Proceedings of the 2001 IEEE Symposium on Research in Security and Privacy[C]. Oakland, California, 2001.130-134.

[5] KOSORESOW A P, HOFMEYR S A. Intrusion detection via system call trace[J]. IEEE Software, 1997, 14(5)∶ 35-42.

[6] WESPI A, DACIER M, DEBAR H. Intrusion detection using variable-length audit trace patterns[A]. Proceedings of Workshop on Recent Advances in Intrusion Detection[C]. Toulouse, France, 2000.110-129.

[7] ZHANG X H, LI J W, JIANG Z H, et al. Black-box extraction of functional structures system call traces for intrusion detection[A]. Advanced Intelligent Computing Theories and Applications with Aspects of Contemporary Intelligent Computing Techniques[C]. Springer, Berlin Heidelberg, 2007. 135-144.

[8] WESPI A, DEBAR H, DACIER M, et al. Fiexed vs. variable-length patterns for detecting suspicious process behavior[A]. Proceedings of the 5th European Symposium on Research in Computer Security[C].2004. 1-15.

[9] RABINER L R, JUANG B H. An introduction to hidden Markov models[J]. IEEE ASSP Magazine, 1986, 3(1)∶ 4-16.

[10] ZHONG A M, JIA C F. Study on the application of hidden Markov models to computer intrusion detection[A]. Proceedings of the 5th World Congress on Intelligent Control and Automation[C]. Hangzhou,2004. 4352-4356.

[11] FINE S, SINGER Y, TISHBY N. The hierarchical Markov model∶analysis and application[J]. Machine Learning, 1998, 32(1)∶ 41-62.

[12] 徐偉,賈春福. 擴充Linux系統(tǒng)功能的LKM技術[J]. 計算機應用研究, 2003, 20(4)∶ 100-102.XU W, JIA C F. LKM∶ a technology to enhance functionalities of Linux kernel[J]. Application Research of Computers, 2003, 20(4)∶ 100-102.

[13] FAN J, UPADHYE S, WORSTER A. Understanding receiver operating characteristic (ROC) curves[J]. Canadian Journal of Emergency Medicine, 2006, 8(1)∶ 19-20.