SA算法在基于模型推理入侵檢測中的應(yīng)用

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

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

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