利用Ｗｉｎｄｏｗｓ Ｎａｔｉｖｅ ＡＰＩ調用序列和基于決策樹算法的主機異常檢測

摘要：主要研究Windows平臺下的異常檢測方法，提出一種利用Windows Native API調用序列和基于決策樹算法的主機服務進程模式抽取算法，并通過在模式中引入通配符而大大縮減了模式集的規模。進一步引入了表征模式間關系的轉移概率，建立了模式序列的全局馬爾可夫鏈模型，并給出了相應的異常檢測算法。實驗結果表明：該算法可以抽取一個規模較小且泛化能力較強的模式集，相應的檢測算法可以有效地檢測異常。

關鍵詞：主機異常檢測; Windows Native API;決策樹;間斷模式

中圖法分類號：TP393．08文獻標識碼：A

文章編號：1001－3695(2007)01－0258－03

主機異常檢測是利用進程的相關信息對其正常行為進行建模，從而在一定程度上描述程序的內部結構與邏輯。在建模時，可將進程看作一個黑箱[1， 3， 6， 7]，僅利用進程行為的外部表現信息(主要是類UNIX平臺下的日志、系統調用等)。這些建模算法多是從正常進程中提取只反映定長或變長局部時間窗之內行為模式，并用生成的模式集匹配待檢測序列。為得到較好檢測效果，這些算法試圖對程序的正常行為空間盡可能完全地覆蓋，往往會造成對訓練數據過擬合。這種過擬合導致模式集規模過大，其中包含了大量頻率很低的模式，使算法很難在檢測能力與計算效率之間取得很好的權衡。另外，局部模式反應的可能是一個函數調用或循環的一次執行所產生的局部信息，因此只考慮這種局部信息，難免要影響對程序全局結構與邏輯的正確描述。文獻[2，3]討論了模式間的關系，并建立了程序全局模型，但是其檢測算法沒有充分利用各模式間轉移特性。

本文主要研究Windows平臺下的異常檢測方法。對關鍵進程采集了Windows Native API序列數據，通過抽取其間斷模式避免了對訓練數據的過擬合，并用轉移概率描述了模式間的關系，從而更有效地利用了各個模式間的轉移特性，建立了全局模型。

1序列訓練算法

1．1數據預處理

將采集到的一個關鍵進程的數據按不同線程分成幾個獨立部分。用滑動窗n切割，并整理為C4.5可以處理的格式。對定長模式方法，n=6被認為是檢測能力與效率的最佳權衡[5]。但本文不僅考慮了定長序列內部信息，還考慮了序列間信息，故選n<6的滑動窗試驗，且當n=4時仍可得到較好結果，而當n<4時檢測能力則顯得不足，所以我們取n=4的滑動窗。這樣便可以在不影響檢測能力的情況下，大大減少模式數量，從而提高檢測效率。 

類屬性的選擇是基于對程序的系統調用和Native API的以下認知：離屬性Y(Y∈{A，B，C

1．2間斷模式抽取

未修剪的決策樹對訓練數據的覆蓋率會非常高，模式也比較多，因此第二步的修剪是必要的。C4.5中常用的修剪算法有REP(Reduced Error Prune)和EBP(Error Based Prune)。 EBP算法在較少模式和較高準確性之間有很好的權衡，并且對數據集有很強的穩定性和泛化能力[4]，因此本文選擇EBP算法。

表 1修剪方法比較

定義2所有出現次數≥1的候選模式構成了模式庫Φ={cp(t)|t∈ΩT′，n(t)≠0}。其中ΩT表示T′的葉節點集。

這一步生成了間斷模式集Φ。由表1可知，其模式數量處于一個較低的水平。

1．3模式間轉移關系建模

應用程序的執行路徑通常并不是不同模式的任意組合，而也是服從著一些特定的順序關系。所以還要考慮模式間的轉移關系，進而建立全局模型。已有一些文獻中[8，9]用MCM對系統調用序列信息直接進行建模，但效果并不理想。本文應用馬爾可夫模型來考慮模式之間的順序特性。

1．3．1模式序列的馬爾可夫鏈模型(MCM)

用得到的間斷模式對Native API序列進行匹配，可以得到一條模式序列，它是模式間關系的研究對象。

定義3pseq(k)k=1，2，…，是一正常關鍵進程產生的模式序列，若它服從馬爾可夫假設，則可將其稱為一個馬爾可夫模式鏈，

1．3．2轉移概率的估計

馬爾可夫鏈模型的轉移概率矩陣和初始概率分布是用長度為2的定長窗切割pseq序列，得到一組值對，將其中包含0的值對除去，然后按下式計算正常模式間的轉移概率：

2異常檢測算法

讀入當前的Native API號s(k)，與之前三個Native API共同構成當前待檢測模式ptn0。首先與Φpseq(k-4)中模式對比，如果沒有匹配，再用ptn0與模式集Φ中的模式匹配。與第i個模式匹配則pseq(k-3)=i，如不匹配pseq(k-3)=0。這里要注意的是若模式p第m(1≤m≤4)位間斷，ptn0與其匹配時應保證第m位∈∑才算正確匹配。這樣就產生了模式序列pseq，然后根據模式間的轉移關系和模式匹配信息得到異常度序列aseq。

要特別注意轉移關系中存在模式0時aseq的取值。對于這種情況，若當前模式是0則把aseq值取為1．5，作為懲罰；若當前模式pseq(k)非0，而前一模式是0，則aseq(k)=1-qk。用這種方法對模式序列pseq進行匹配后，得到了模式轉移關系序列aseq，并有0≤aseq(k)≤1．5。最終得到了異常度矩陣PA：

異常檢測根據每一連續20個轉移概率序列aseq值的和，即采用LFC方法進行。算法綜合考慮了模式的發生特性、頻率特性和順序(轉移)特性。得到的值越大(越接近30)序列異常度就越大。

3試驗

3．1異常檢測

本文在Windows 2000下采集了幾種關鍵進程的Native API數據。包括系統關鍵進程(Svchost)和提供網絡服務的進程(IIS)，如圖2所示，可以看到檢測算法很好地區分了正常和異常的進程。

圖2中的異常數據是用流光掃描了以下幾個可能漏洞：Unicode編碼漏洞、FrontPage擴展、嘗試獲取SAM文件、嘗試獲取PcAnyWhere密碼文件和CGI漏洞掃描所得到的數據。

圖3中的異常數據是利用微軟在MS03026公布的RPC接口緩沖區溢出漏洞進行攻擊所得到的數據。

3．2檢測算法時間復雜度

Forrest方法檢測算法的時間復雜度為O(|s|(RA|Φ|+1))[6]，其中RA為序列中異常出現的比率。本文的方法在正常情況下，k時刻經過與Φpseq(k-4)匹配，并從PA中讀取異常度可得到當前模式和轉移異常度，所以檢測算法時間復雜度也為O(|s|(RA|Φ|+1))。其中|Φ|要比Forrest算法小得多，因此時間復雜度在異常較多的情況下會有一些優勢，適合在線檢測。

4結論

本文用C4.5算法抽取了Windows Native API序列的局部間斷模式，并根據表征模式間關系的轉移概率建立了模式序列的全局馬爾可夫鏈模型，獲得了一個較小規模較強檢測能力的模式集，更有效地利用了模式間的順序(轉移)特性。算法的檢測時間復雜度較低，適合在線檢測。

參考文獻：

［1］Forrest S， et al. A Sense of Self for UNIX Processes[C]. Oakland，California: IEEE Symposium on Security and Privacy， 1996. 120128.

［2］Ning Jiang， Kien A Hua， Simon Sheu. Considering Both Intrapattern and Interpattern Anomalies for Intrusion Detection[C]. Maebashi City: IEEE International Conf. on Data Mining， 2002. 637640.

［3］Kosoresow A P， Hofmeyer S A. Intrusion Detection via System Call Traces[J]. IEEE Software， 1997，14(5):3542.

［4］Floriana Esposito， et al. A Comparative Analysis of Methods for Pru￣ning Decision Trees[J]. IEEE Transactions on Pattern Analysis and Machine Intellegence，1997，19(5):476491.

［5］Tan K， Maxion R. Why 6? Defining the Operational Limits of Stide[C]. Oakland， California: IEEE Symposium on Security Privacy， 2002. 188201.

［6］S A Hofmeyr， S Forrest， A Somayaji. Intrusion Detect Using Sequences of System Calls[J]. Journal of Computer Security， 1998，6(3):151180.

［7］Debin Gao， Michael K Reiter， Dawn Song. On Graybox Program Tracking for Anomaly Detection[C]. San Diego: The 13th USENIX Security Symposium，20-04.103118.

［8］Nong Ye， et al. Probabilistic Techniques for Intrusion Detection Based on Computer Audit Data[J]. IEEE Trans. on Systems， Man， and CyberneticsPart A:Systems and Humans，2001，31(4):266274.

［9］譚小彬，王衛平，等. 系統調用序列的Markov模型及其在異常檢測中的應用[J]. 計算機工程，2002，28(12):189265.

作者簡介：

李乃捷(1981)，男，山西大同人，碩士研究生，主要研究方向為基于序列信息的主機入侵檢測系統;

彭勤科(1962），男，教授，主要研究方向為實時并行信息處理與控制系統、集群服務器、計算機網絡信息安全。

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