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

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

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