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

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

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