鑒于模型推理的入侵檢測方法，需要在龐大的審計記錄空間中搜索巨量的攻擊腳本子集中的最優(yōu)值，對于這一NP類完全問題，提出了應用模擬退火算法。并建立了攻擊檢測的優(yōu)化問題模型，給出了攻擊檢測實驗中的解空間、目標函數(shù)、新解的產(chǎn)生和接受準則，得到了一個合理的冷卻進度表，并對實驗中的模擬退火算法進行了并行化研究。實驗證明，與傳統(tǒng)的貪心算法相比，應用模擬退火算法提高了進化速度和全局尋優(yōu)能力，較好地解決了搜索效率問題。
關 鍵 詞 模擬退火算法; 模型推理; 入侵檢測; 網(wǎng)絡安全

1 基于模型推理的入侵檢測方法
入侵是指任何試圖對資源的完整性、保密性或可用性產(chǎn)生危害的行為。入侵檢測是對這些行為的識別。由于入侵模式的多樣性，入侵檢測策略和模型也具有多種不同的類型[1,2]。基于模型推理(Model-Based Reasoning)的入侵檢測方法通過為入侵行為建立特定的模型，結(jié)合攻擊腳本推理出入侵行為是否出現(xiàn)。入侵檢測利用的信息很大一部分是來自系統(tǒng)的日志和審計信息。入侵者經(jīng)常在系統(tǒng)日志中留下他們的蹤跡，因此充分利用系統(tǒng)的日志文件和審計信息是檢測入侵的必要手段。日志中包含發(fā)生在系統(tǒng)和網(wǎng)絡上的不尋常和不期望活動的證據(jù)，通過分析日志文件和審計信息，能夠發(fā)現(xiàn)成功的入侵或入侵企圖。

在Unix操作系統(tǒng)中帶有許多審計機制，并且還可以再配置審計工具，因此能夠產(chǎn)生大量的審計數(shù)據(jù)。為從龐大的信息中提取出與安全相關的信息，以產(chǎn)生攻擊腳本，首先對歷史審計文件進行預處理，產(chǎn)生用戶會話矢量。用戶會話包括login和logout之間的所有事件。會話矢量A=描述單一會話過程中用戶進行的各種事件數(shù)量。會話開始于login，終止于logout，login和logout次數(shù)也作為會話矢量的一部分。可以監(jiān)視20多種事件，如：登錄的時間、登錄失敗數(shù)、寫文件數(shù)、讀文件數(shù)等。
然后將產(chǎn)生的用戶會話矢量提交給分析模塊，分析模塊可以采用統(tǒng)計、專家系統(tǒng)等方法建立用于入侵檢測的攻擊腳本，存入攻擊腳本庫中。腳本庫是一個m×n維的事件矩陣，一個列向量表示一種攻擊所對應的會話矢量。
檢測時先將這些攻擊腳本的子集假設為系統(tǒng)正面臨的攻擊，然后通過一個預測器程序模塊，根據(jù)當前行為模式產(chǎn)生需要驗證的攻擊腳本子集，并將它傳給決策器，決策器收到信息后，根據(jù)這些假設的攻擊行為在審計記錄中的可能出現(xiàn)方式，將它們翻譯成與特定系統(tǒng)匹配的審計記錄格式，在審計記錄中尋找相應信息來判定該攻擊是否發(fā)生。
基于模型推理的入侵檢測的實質(zhì)是在審計記錄中搜索可能出現(xiàn)的攻擊子集。在實際應用中，發(fā)現(xiàn)通常系統(tǒng)的審計記錄數(shù)據(jù)量龐大：一個典型的C2級審計機制，在一個多用戶系統(tǒng)，不到1 h時便會產(chǎn)生1 GB的數(shù)據(jù)量；一臺4CPU SPARC SUN系統(tǒng)需要用兩個CPU和所有磁盤通道來記錄其它兩個CPU的活動；在網(wǎng)絡環(huán)境中，數(shù)據(jù)量將更加膨脹。同時，攻擊腳本子集的數(shù)量也很巨大，假設攻擊腳本中與入侵潛在相關的度量有n個，則這n個度量所構成的子集數(shù)便達到2n個。可以將在審計記錄中尋找相應信息來確認或否認這些攻擊的問題看作類似于一個非確定型多項式類(Nondterministic Polynomial, NP)完全問題，即在復雜而龐大的搜索空間中尋找最優(yōu)解或準優(yōu)解。在求解此類問題時，若不能利用問題的固有知識來縮小搜索空間則會產(chǎn)生搜索的組合爆炸。
因此本文在模型推理方法已有成果的基礎上，提出了將模擬退火(Simulated Annealing，SA)算法運用在基于模型推理的入侵檢測中。論述了模擬退火算法4要素：解空間、目標函數(shù)、新解的產(chǎn)生、接受準則在攻擊檢測中的選用，給出了實驗的主要SA算法代碼，并對用于攻擊檢測的SA算法進行了并行化研究。
2 SA算法
求NP完全問題的最優(yōu)解有多種方法，如線性規(guī)劃、貪心算法等，但這些算法往往由于計算時間的限制不具有可行性。而入侵檢測一個重要的特征就是要具有實時性，因此上述算法不適合應用于模型推理的入侵檢測[3,4]。
模擬退火算法是一種解大規(guī)模組合優(yōu)化問題[5]，特別是NP完全問題的有效近似算法。它源于對固體退火過程的模擬，采用Metropolis接受準則，并用一組稱為冷卻進度表的參數(shù)控制算法進程，使算法在多項式時間里給出一個近似最優(yōu)解。
模擬退火算法的主要特點是高效、健壯、通用和靈活。盡管該算法本身在理論和應用方法上仍有許多待進一步研究的問題，但實踐證明，模擬退火算法對于組合優(yōu)化中的NP完全問題非常有效。
3 SA應用研究
3.1 問題的描述
本文目標是：根據(jù)審計跟蹤記錄中的事件確定在所有可能攻擊子集中哪一個對系統(tǒng)最具威脅性，即對于一個特定的攻擊子集，統(tǒng)計所有攻擊產(chǎn)生的每類事件的個數(shù)，如這一數(shù)量少于或等于那種被記錄事件的數(shù)量，“該攻擊子集存在”的假設是成立的。為了用數(shù)學形式更精確地描述該問題.