基于兩層隱馬爾可夫模型的入侵檢測方法

摘要：在基于系統調用的入侵檢測研究中，如何提取系統調用序列模式是一個重要問題。提出一種利用進程堆棧中的函數返回地址鏈信息來提取不定長模式的方法。同王福宏的不定長模式提取方法相比，該方法可以取得更完備的模式集。在此基礎上，基于系統調用序列及其對應的不定長模式序列構建了一個兩層隱馬爾可夫模型來檢測異常行為，與僅利用系統調用序列信息的經典隱馬爾可夫方法相比，該方法可以取得更低的誤報率和漏報率。

關鍵詞：入侵檢測； 系統調用； 進程堆棧； 函數返回地址； 不定長序列模式； 兩層隱馬爾可夫模型

中圖分類號：TP393.08文獻標志碼：A

文章編號：1001－3695(2008)03－0911－04

通過分析系統調用信息實現對入侵行為的檢測，是基于主機入侵檢測中的一個重要方面，許多研究者在這方面做了很多工作。Forrest等人在1996年首先提出以進程正常運行時產生的一定長度的系統調用短序列為模型來刻畫進程正常運行狀態[1]。Lee等人繼Forrest的工作，用RIPPER從系統調用序列中挖掘正常和異常的模式[2]，以規則的形式來描述系統的運行狀態，建立了一個更簡潔有效的系統正常模型。但是利用定長模式方法的主要局限性在于很難合理地選擇短序列長度。程序具有結構特性，并且結構之間存在顯著的差異，因此利用不定長序列模式來描述程序的正常行為比定長模式更為合理。Kosoresow等人通過一些啟發式的腳本和人工方式來提取不定長模式[3]。Wespi等人采用了生物學中挖掘模式的Teiresias算法來提取進程的不定長模式[4]。國內方面，王福宏等人根據同一模式中不存在重復系統調用號的原則提取不定長模式[5]。然而，這些方法基本上都是借鑒了生物學中一些算法來提取模式，方法本身缺乏一個合理有效的依據。由于在產生系統調用時可以通過解析進程堆棧來獲取與系統調用關聯的函數返回地址[6]，本文提出了一種利用進程堆棧中的函數返回地址鏈信息來構造不定長模式的方法。同王福宏的不定長模式提取方法相比，本文方法可以取得規模更小的模式集。

隱馬爾可夫模型（hidden Markov model， HMM）在基于主機數據的入侵檢測研究中具有重要意義。美國新墨西哥大學的Warrender等人首次提出將HMM應用于基于系統調用的入侵檢測中[7]。2002年，Yan等人提出用HMM對系統調用序列進行建模，利用TIDE方法劃分狀態序列的短序列，建立正常數據的狀態短序列庫來進行檢測[8]。2003年，Cho等人提出用HMM對關鍵的系統調用序列進行建模[9]。Yeung等人用HMM對系統調用和命令序列進行建模，也取得了較好的檢測效果[10]。本文基于系統調用序列及其對應的不定長模式序列構建了一個兩層隱馬爾可夫模型來檢測異常行為。實驗結果表明，同Warrender等人僅利用系統調用序列信息的HMM方法相比，本文方法融合了系統調用和函數返回地址鏈兩個信息源，因此更能發現進程中的異常執行軌跡。

1不定長模式的提取

1．1函數返回地址鏈

根據操作系統中函數調用的原理，在向內核發起系統調用請求時，所有與之關聯的函數調用的返回地址均存放在進程堆棧中，通過解析進程堆?？梢垣@取與系統調用關聯的函數返回地址。本文使用函數調用的返回地址來表示對應的函數調用，從而得到一組對應系統調用的函數返回地址。筆者稱之為函數返回地址鏈，如圖1所示。

系統調用返回地址→函數1返回地址→函數2返回地址→…→函數n返回地址

理論上來說，對于一個進程，其系統調用序列對應的函數返回地址鏈均有相同的鏈尾，即main函數的返回地址。相鄰的一段系統調用，如果它們均是由某一個上層函數調用衍生，則它們對應的地址鏈的后幾個節點相同。本文根據地址鏈信息之間的關聯關系，對所有系統調用的函數返回地址鏈進行關聯。以地址鏈的尾節點為起始端，對所有的地址鏈信息進行歸并，得到一個與進程對應的樹型結構的函數地址結構。圖2是進程執行的一個簡單例子。A~F代表函數調用的返回地址；S1~S9代表依次執行的系統調用。

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

1．2基本定義

1)∑程序所有可能執行的系統調用號的集合。

2)Ω程序所有可能執行的函數返回地址的集合。

3)Ω程序所有可能的函數返回地址鏈的集合，Ω={R1，R2，R3，…}。其中：Ri為定義在Ω上的一條函數返回地址鏈。

對于相鄰的兩個系統調用ti和tj(ti，tj∈∑)及其對應的函數返回地址鏈Ri=(ri，1，ri，2，…，ri，m)和Rj=(rj，1，rj，2，…，rj，n)(Ri，Rj∈Ω，ri，x∈Ω，rj，y∈Ω，1≤x≤m，1≤y≤n)，一定存在k和l(1≤k≤m，1≤l≤n，m-k=n-l)，使得對于任何的p(0≤p≤m-k)，均有ri，k+p=rj，l+p。尤其當k取其最小值時，ri，k表示了ti和tj在函數返回地址樹中具有最大深度的共同父節點。本文將此時ri，k的深度記為maxDepthi， j。如圖2中，S1和S2最大深度的共同父節點為B；S3和S4最大深度的共同父節點為E。

1．3模式提取算法

定義一個可以同時存儲三個系統調用及其對應的函數返回地址鏈的隊列Q。進程實時地產生一個系統調用，即將該系統調用及其對應的函數返回地址鏈插入到隊列Q中。隊列Q的特點是先入先出。從進程產生第三個系統調用開始，每次隊列操作后均執行如下操作：

最后，輸出不定長模式（S1，S2）、（S3，S4）、（S5，S6，S7）。需要說明兩點：a)不定長系統調用序列模式的提取可以在線完成；b)每一個不定長模式實際上代表了程序中某個函數f()執行時的調用序列，即每一個不定長模式均與某個函數f()的返回地址相對應，而且該返回地址是不定長模式中所有系統調用在函數返回地址樹中具有最大深度的共同父節點。所以，一條系統調用序列惟一地對應著一條不定長模式序列，同時也惟一地對應著一條函數返回地址序列。本文在今后一律用函數返回地址序列來表示不定長模式序列。例如，將不定長模式序列（（S1，S2），（S3，S4），（S5，S6，S7））記做（B，E，F）。

2基于不定長模式的兩層隱馬爾可夫模型

2．1模型的建立

HMM是一個雙重隨機過程，即一個雙重的內含不可見（隱藏）的從屬隨機過程的隨機過程。其中：不可見從屬隨機過程只能通過另一套產生觀察序列的隨機過程間接觀察到[11]。對于一個給定的觀察值序列O={O1，O2，…，OT}及O所對應的隱狀態序列Q={q1，q2，…，qT}（T為序列長度），一個HMM可記為λ=(N，M，π，A，B)。其中：N是隱狀態個數，定義隱狀態的有限集合S={S1，S2，…，SN}；M為觀察值個數，定義觀察值有限集合V={v1，v2，…，vM}；初始狀態分布π={πi}，其中πi=P(q1=Si)(1≤i≤N)；狀態轉移概率A={aij}，其中aij=P(qi+1=Si|qt=Si)，表示在t時刻處于狀態Si而在t+1時刻處于狀態Sj的概率，也就是從狀態Si轉移到Sj的概率（如果aij=0，則說明Si到Sj不存在轉移關系）；輸出概率B={bj(k)}，其中bj(k)=P(Ot=vk|qt=Sj)，表示在t時刻處于狀態Sj并輸出觀察值vk的概率。

根據上一節所述，進程產生的一條系統調用序列可以看做由若干個不定長模式拼成。由此，本文提出了一種基于系統調用序列及其對應的不定長模式序列的兩層隱馬爾可夫模型。將基于系統調用序列的HMM記為下層隱馬爾可夫模型，將基于不定長模式序列（用函數返回地址序列來表示）的HMM記為上層隱馬爾可夫模型。在下層隱馬爾可夫模型中，將程序運行時的系統調用序列定義為觀察值序列，將不同類型系統調用的個數定義為隱狀態數；在上層隱馬爾可夫模型中，將不定長模式序列定義為觀察值序列，隱狀態數在由人工指定，在本文中設置為30。最后，本文利用BaumWelch算法分別對上下兩層隱馬爾可夫模型進行訓練，BaumWelch算法是一種迭代算法，它利用前向后向概率來解決參數估計問題。本文將上下兩層隱馬爾可夫模型訓練得到的參數記為λ1=(N1，M1，π1，A1，B1)和λ

2．2檢測算法

基于正常程序行為的兩層隱馬爾可夫模型訓練完成以后，即可用于實際的入侵檢測。利用一個長度為L的滑動窗對進程產生的系統調用序列及其對應的不定長模式序列進行切割，滑動窗口每次向后滑動一步。假設某個進程產生的系統調用序列長度為T，對應的不定長模式序列長度為K，則滑動窗口可以切割出T-L+1個系統調用短序列Xi(1≤i≤T-L+1)和K-L+1個不定長模式短序列Yj(1≤j≤K-L+1)。

根據隱馬爾可夫模型的前向后向算法可以得出，系統調用短序列Xi和不定長模式短序列Yj的輸出概率為P(Xi|λ1)和P(Yj|λ2)。由上一節所述，不定長模式短序列Yj對應著L個連續的不定長模式，即對應著系統調用序列中的一個子序列。記該子序列中的第一個和最后一個系統調用在進程系統調用序列中的出現位置為m和n，則利用P（Yj|λ2)對每一個P(Xi|λ1)（m≤i≤n）作如下修正：

P(Xi|λ1)=P(Xi|λ1)+k×P(Yj|λ2)(m≤i≤n)。其中：k為修正系數，在本文中取1/L。

對一給定的測試進程，將進程修正后的每個P（Xi|λ1)的值與一個給定的輸出概率閾值ε進行比較，并將小于此閾值的短序列標定為不匹配；然后計算出此進程中不匹配的短序列數與該進程中包含的總短序列數的比值。這里定義此比值為該進程的異常度：

δ=不匹配短序列數/測試進程中的總短序列數

3實驗結果

3．1實驗數據

實驗中，通過修改系統內核的方法來動態獲取進程的系統調用信息和堆棧信息，主要跟蹤了Ftpd和Samba等服務程序。實驗數據分為兩部分，即訓練數據和測試數據。正常數據中的一部分數據組成訓練數據，剩余的正常數據和異常數據組成測試數據。正常數據的搜集是在一個封閉的環境中，通過模擬用戶的各種正常行為獲得；異常數據是利用Internet搜集的一些攻擊腳本和工具對監控進程進行模擬攻擊得到。表1給出了實驗數據的情況。其中：對于Ftpd和Samba進程，正常數據中分別包含1 627 306和286 452個系統調用。

3．2模式集規模與覆蓋率比較

本文在1.3節中給出了一種獲取不定長系統調用序列模式的方法。模式集規模的大小是衡量一個入侵檢測系統性能的指標。模式集規模越小，則占用的內存空間越少。覆蓋率的定義是指用給定的模式集去覆蓋一條完整的系統調用序列，序列中被準確覆蓋的位置占整個序列長度的百分比。通過計算已有的模式集對未知正常序列的覆蓋率，可以體現該模式集表征程序正常行為的完備程度。覆蓋率越高，說明算法提取的模式集越能準確地描述程序的正常行為。本文從模式集規模和覆蓋率兩個角度同王福宏在文獻[5]中的方法進行比較，結果如表2所示?？梢?，本文方法得到的不定長模式集規模更小，覆蓋率更高。

表3為本文方法同文獻[7]中的方法得到的Ftpd和Samba測試進程的平均異常度的比較結果?？梢钥闯觯疚牡膬蓪与[馬爾可夫模型方法對進程中的異常行為更為敏感，對異常的捕捉能力要優于文獻[7]中的方法。若在異常度上設立一個閾值來檢測入侵，本文方法可以提供更大的選擇空間。

3．4誤報率和漏報率

漏報率和誤報率是評價入侵檢測方法有效性的兩個重要指標。前者表示入侵行為沒有被檢測出來的概率，后者表示將正常序列標定為異常的概率。實驗中，將本文的兩層隱馬爾可夫模型方法同文獻[7]中的方法進行了比較。兩種方法的漏報率和誤報率如表4所示。

本文方法與文獻[7]中的方法均能夠檢測出所有的異常進程，兩種方法對于測試數據的漏報率相同。在誤報率方面，本文方法要比文獻[7]中的方法略好?？梢姡疚姆椒梢员３衷谝粋€較低誤報率的情況下，有效且準確地檢測出針對系統的攻擊行為。

4結束語

基于程序的結構性特征，本文提出了一種利用進程堆棧中的信息來提取不定長系統調用序列模式的方法。實驗結果表明，同國內王福宏的不定長模式提取方法相比，本文方法能夠獲取更完備的模式集。在此基礎上，本文基于系統調用序列及其對應的不定長模式序列構建了一個兩層隱馬爾可夫模型來檢測異常行為。本文方法融合了系統調用和函數返回地址鏈兩個信息源，因此較Warrender方法更能發現進程中的異常執行軌跡，取得更低的誤報率和漏報率。在今后的研究中，可以考慮采用更符合語義的不定長系統調用序列模式的提取算法，以望獲得更高的檢測性能。

參考文獻：

[1]FORREST S， HOFMEYR S A， SOMAYAJI A， et al. A sense of self for UNIX processes[C]//Proc of IEEE Symposium on Security and Privacy. Los Alamos， California:[s.n]， 1996: 120128.

[2]LEE W， STOLFO S J. Data mining approaches for intrusion detection[C]//Proc of the 7th USENIX Security Symposium. San Antonio， Texas:[s.n.]， 1998:79－94.

[3]KOSORESOW A P， HOFMEYR S A. Intrusion detection via system call traces[J]. IEEE Software， 1997， 14(5):35－42.

[4]WESPI A， DACIER M， DEBAR H. Intrusion detection using variablelength audit trail patterns[C]//Proc of the 3rd International Workshop on the Recent Advances in Intrusion Detection(RAID 2000). Toulouse:[s.n.]， 2000:110129.

[5]王福宏，彭勤科，李乃捷.基于不定長系統調用序列模式的入侵檢測方法[J] .計算機工程，2006，32(20):143146. [6]FENG H， KOLESNIKOV O， FOGLA P， et al. Anomaly detection using call stack information[C]//Proc of IEEE Symposium on Security and Privacy. Berkeley， California:[s.n.]， 2003:62－75.

[7]WARRENDER C， FORREST S， PEARLMUTTER B. Detecting intrusions using system calls: alternative data models[C]//Proc of IEEE Symposium on Security and Privacy. Oakland， California:[s.n.]，1999: 133145.

[8]YAN Qiao， XIE Wiexin， YANG Bin， et al. An anomaly intrusion detection method based on HMM[J]. Electronics Letters， 2002，38(13):663－664.

[9]CHO S B， PARK H J. Efficient anomaly detection by modeling privilege flows using hidden Markov model[J]. Computers Security， 2003，22(1):45－55

[10]YEUNG D Y， DING Y. Hostbased intrusion detection using dynamic and static behavioral models[J]. Pattern Recognition， 2003，36(1):229－243.

[11]RABINER L R. A tutorial on hidden Markov models and selected applications in speech recognition[J].Proc of the IEEE，1989， 77(2): 257－286.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”