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

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

(1. 南開大學(xué) 信息技術(shù)科學(xué)學(xué)院，天津 300071；2. 國家計(jì)算機(jī)病毒應(yīng)急處理中心，天津 300457)

1 引言

入侵檢測是計(jì)算機(jī)信息系統(tǒng)安全保障的關(guān)鍵技術(shù)之一，是位于防火墻和訪問控制之后重要的安全防護(hù)措施。Forrest[1,2]等人將人工免疫的思想引入到入侵檢測技術(shù)中，構(gòu)造計(jì)算機(jī)系統(tǒng)的正常行為模式庫，并通過比對系統(tǒng)運(yùn)行時(shí)的模式與正常行為模式庫的方法來判斷系統(tǒng)是否異常或被入侵。

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

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

2 變長語義模式的提取

根據(jù)操作系統(tǒng)中函數(shù)調(diào)用的原理，在向操作系統(tǒng)內(nèi)核發(fā)起系統(tǒng)調(diào)用請求時(shí)，所有與之相關(guān)聯(lián)的函數(shù)調(diào)用的返回地址均存放在進(jìn)程堆棧中，通過解析進(jìn)程堆棧可以獲取與系統(tǒng)調(diào)用相關(guān)聯(lián)的函數(shù)返回地址。本文使用函數(shù)返回地址來表示對應(yīng)的函數(shù)調(diào)用，從而得到系統(tǒng)調(diào)用序列的函數(shù)返回地址鏈。

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

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

圖1 函數(shù)返回地址樹形結(jié)構(gòu)

3 基于HHMM的入侵檢測模型

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

3.1 HHMM模型簡介

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

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

∑：表示有限符號集。

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

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

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

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

圖2 HHMM的抽象描述圖

3.2 HHMM序列概率計(jì)算與參數(shù)估計(jì)算法

HHMM是一種具有層次結(jié)構(gòu)的HMM。可以使用動(dòng)態(tài)規(guī)劃Baum-Welch算法來計(jì)算序列產(chǎn)生的概率。定義“前向”概率為

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

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

為了能夠?qū)HMM的參數(shù)進(jìn)行估計(jì)，需要添加與垂直方向狀態(tài)轉(zhuǎn)移過程相對應(yīng)的路徑變量。定義以下變量：

和

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

基于這些關(guān)于路徑的變量定義，可以得到如下參數(shù)重估算法：

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

3.3 HHMM入侵檢測模型

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

該HHMM模型分為2個(gè)階段：訓(xùn)練階段和檢測階段。

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

下面以一個(gè)簡單的程序?yàn)槔f明該模型樹形結(jié)構(gòu)的構(gòu)造方法。程序代碼如下：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);}

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

在生成模型的樹形結(jié)構(gòu)后，再采用上文給出的推廣的Baum-Welch算法對HHMM進(jìn)行參數(shù)估計(jì)。

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

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)介紹

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

圖3 根據(jù)函數(shù)調(diào)用地址鏈構(gòu)造的HHMM樹形結(jié)構(gòu)實(shí)例

表1 實(shí)驗(yàn)數(shù)據(jù)源描述

4.2 實(shí)驗(yàn)結(jié)果

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

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

圖4 HHMM與HMM針對ftpd守護(hù)進(jìn)程的測試結(jié)果比較

圖5 HHMM與HMM針對sendmail守護(hù)進(jìn)程的測試結(jié)果比較

5 結(jié)束語

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

[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] 徐偉,賈春福. 擴(kuò)充Linux系統(tǒng)功能的LKM技術(shù)[J]. 計(jì)算機(jī)應(yīng)用研究, 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.