入侵檢測基本概念檢測算法基礎(chǔ)

1、入侵檢測基本概念與檢測算法基礎(chǔ)本文主要分為幾個部分1.入侵檢測基本概念2.入侵檢測算法的理論研究發(fā)展3.入侵檢測算法的一種實(shí)現(xiàn)嘗試1.入侵檢測基本概念入侵檢測是一種通過收集和分析被保護(hù)系統(tǒng)的信息，從而發(fā)現(xiàn)入侵的技術(shù)。它的主要 功能是對網(wǎng)絡(luò)和計算機(jī)系統(tǒng)進(jìn)行實(shí)時監(jiān)控，發(fā)現(xiàn)和識別系統(tǒng)中的入侵行為或企圖，給出入 侵警報入侵檢測攻防對抗的觀點(diǎn)1.要想完全避免安全事件的發(fā)生并不太現(xiàn)實(shí)，網(wǎng)絡(luò)安全人員需要做的是盡力發(fā)現(xiàn)和察 覺入侵及入侵企圖(即具有高度的異常敏感性，從長遠(yuǎn)的角度來看，安全的問題本來就是 一個互相攻防對抗的過程。1安全的攻防對抗沒有一招解決所有問題的技術(shù)2好的攻防思路是部署一種盡可能敏感的攻擊事

2、件捕獲機(jī)制，當(dāng)發(fā)生了已知、或者 未知的攻擊的事件時，我們能第一時間獲取到關(guān)于本次攻擊的盡可能多的元數(shù)據(jù)(強(qiáng)大的入侵檢測機(jī)制3針對發(fā)生的攻擊，采取針對性的防御，針對性地防御是最有效的方法漏洞進(jìn)行針對性的代碼修復(fù)、為系統(tǒng)的某個cve漏洞打上補(bǔ)丁(對cms的4在針對性防御的基礎(chǔ)上，我們對一些解決方案進(jìn)行歸納、總結(jié)，試圖找到一種底 層性的、歸類性的安全解決方案(回想歷史上微軟的dep、aslr、safeseh技術(shù)2.采取有效的措施來堵塞漏洞和修復(fù)系統(tǒng)入侵檢測的定義及分類1.定義:1將入侵企圖或威脅定義為未經(jīng)授權(quán)蓄意嘗試訪問信息(sql注入、橫向/縱向越權(quán) 訪問、非法下載數(shù)據(jù)庫/日志信息、竄改信息(掛黑

3、鏈、sql注入，使系統(tǒng)不可靠或不能 使用(種植后門木馬、webshell2入侵是指有關(guān)試圖破壞資源的完整性、機(jī)密性及可用性的活動集合定義(安全的三大3從分類角度指出入侵包括:3.1嘗試性闖入(掃描行為3.2偽裝攻擊(代理、跳板攻擊3.3安全控制系統(tǒng)滲透3.4泄漏3.5拒絕服務(wù)(ddos3.6惡意使用(僵尸網(wǎng)絡(luò)、rootkit后門2.分類:入侵檢測技術(shù)主要分成兩大類型1異常入侵檢測能夠根據(jù)異常行為和使用計算機(jī)資源情況檢測出來的入侵，異常入侵檢測試圖用定量方式描述可接受的行為特征，以區(qū)分非正常的、潛在的入侵性行。整個流程基本如下:1.1建立威脅模型，包括:1.1.1確定一個算法1.1.2監(jiān)控哪些事

4、件的發(fā)生1.1.3需要獲取哪些數(shù)據(jù)1.1.4對獲取到的數(shù)據(jù)進(jìn)行怎樣的計算1.1.5計算的結(jié)果的上線閾值是多少1.1.6當(dāng)超過這個閾值的時候，需要采取什么操作，是直接報警、還是采取權(quán)重打分 的機(jī)制1.2進(jìn)行行為監(jiān)控，并捕獲數(shù)據(jù)1.3對捕獲的數(shù)據(jù)進(jìn)行異步、或?qū)崟r計算1.4根據(jù)計算的結(jié)果采取相應(yīng)的預(yù)設(shè)動作2誤用入侵檢測誤用檢測是指:根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過判斷這此特征是否出 現(xiàn)來完成檢測任務(wù)。誤用檢測中使用的檢測技術(shù)主要有：模式匹配、專家系統(tǒng)、狀態(tài)轉(zhuǎn)移 等，其中模式匹配原理簡單，可擴(kuò)展性好，而且最為常用。據(jù)統(tǒng)計，現(xiàn)在大約的入侵檢測95%的入侵檢測都是特征匹配3. 異常入侵檢測和誤用

5、入侵檢測的異同點(diǎn)1誤用入侵檢測根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過判斷這此特征是否 出現(xiàn)來完成檢測任務(wù)2異常入侵檢測是檢查出與正常行為相違背的行為，異常入侵檢測的核心就是對合 法的行為和可疑的行為進(jìn)行二值邏輯區(qū)分我個人覺得誤用入侵檢測更多的是一種針對性防御，根據(jù)已知的對性的匹配規(guī)則，例如:poc、exp攻擊特征，指定針1 waf對web漏洞的url特征建立的阻斷規(guī)則庫2網(wǎng)絡(luò)防火墻對ddos等攻擊的流量模式建立規(guī)則庫3殺軟對已知病毒、shellcode的二進(jìn)制特征、api調(diào)用特征建立規(guī)則庫而異常入侵檢測更側(cè)重于對已知、未知的異常行為進(jìn)行捕獲、判斷，本文重點(diǎn)學(xué)習(xí)異常入侵檢測異常入侵檢測方法異

6、常入侵檢測的主要前提條件是將入侵性活動作為異?；顒拥淖蛹＠硐霠顩r是異?；顒蛹c入侵性活動集等同，這樣，若能檢測所有的異常活動，則可檢測所有的入侵 性活動。但是，入侵性 活動并不總是與異常活動相符合，它們之間存在以下幾種關(guān)系1異常且入侵性(黑客攻擊2異常但非入侵(誤報3非異常但入侵(漏報4非異常且非入侵(正常業(yè)務(wù)操作，選擇忽略異常入侵要解決的問題就是構(gòu)造異?；顒蛹闹邪l(fā)現(xiàn)入侵性活動子集 異常入侵檢測方法依賴于異常模型的建立，不同模型構(gòu)成不同的檢測方法。異常檢測 就是通過觀測到的一組測量值偏離度來預(yù)測用戶行為的變化，然后作出決策判斷的檢測技術(shù)，對此，學(xué)術(shù)界和企業(yè)界都提出了很多優(yōu)秀的異常模型，

7、在不同的場景下不同的異 常模型的效果是打不相同的我認(rèn)為本質(zhì)上來說，這也就一個誤報、漏報的問題1我們可以通過文件行為監(jiān)控，捕獲所有的磁盤文件操作行為(windows、；linux都 提供了相應(yīng)的callback回調(diào)api2通過逆向機(jī)器學(xué)習(xí)、行為建模、閾值判斷從所有的行為中過濾出:2.1用戶正常操作2.1.1文件新建管理員通過ftp、ssh、rdp登錄后在web根目錄下進(jìn)行單個文件的新建管理員在進(jìn)行文件單個、批量復(fù)制(復(fù)制文件從操作系統(tǒng)的層面上來看還是一 個文件新建的行為 rar壓縮包解壓(rar壓縮包解壓只是一種軟件機(jī)制，在操作系統(tǒng)層面還是在 進(jìn)行文件的

8、新建2.1.2文件修改管理員通過ftp、ssh、rdp登錄后在web根目錄下進(jìn)行單個文件的編輯并 修改(注意:從操作系統(tǒng)層面來看，只有打開文件并編輯保存之后才能算文件修改，否則只 是單純的文件訪問行為2.2網(wǎng)站正常運(yùn)行行為2.2.1文件創(chuàng)建網(wǎng)站的web系統(tǒng)在正常的運(yùn)行過程中會有一些文件創(chuàng)建的行為產(chǎn)生 cache臨時緩存文件預(yù)編譯模板高速緩存網(wǎng)站配置信息settings高速緩存 log日志文件、error_log出錯日志文件文件上傳控件(fck、kindeditor導(dǎo)致的圖片、rar附件上傳 web

9、系統(tǒng)為了并發(fā)串行訪問的需求生成臨時鎖文件(.lock2.2.2文件修改網(wǎng)站配置信息sett ings高速緩存的修改管理員進(jìn)行網(wǎng)站模板編輯2.3黑客在嘗試進(jìn)行攻擊2.3.1文件創(chuàng)建黑客通過注入拿到了網(wǎng)站后臺，通過后臺可以上傳文件的地方進(jìn)行上傳(本質(zhì)上是文件創(chuàng)建行為黑 客 通 過web漏 洞 的 代 碼 執(zhí) 行 直 接 生 成 文 件(。?黑客通過注入拿到了網(wǎng)站后臺，通過webshellsql執(zhí)行接口進(jìn)行文件寫入(selectshell.shell into outfile path黑客已經(jīng)拿到了rdp、ssh、f

10、tp登錄口令，以正常管理員的身份進(jìn)行登錄， 并寫webshell黑客通過老的webshell上傳新的webshell2.3.2文件修改黑客通過注入拿到了網(wǎng)站后臺，對模板文件、配置文件進(jìn)行修改，在其中插 入webshell(這類文件一般都是.php黑客通過老的webshell對網(wǎng)站的正常文件進(jìn)行編輯標(biāo)準(zhǔn)的入侵檢測測試數(shù)據(jù)集kdd99 data set，kdd測試數(shù)據(jù)集的這種思路我覺得非 常好，有時候，通過這種集中式的數(shù)據(jù)觀察、對數(shù)據(jù)進(jìn)行聚類、分段，能得到很多對入侵 行為、入侵模式新的觀點(diǎn)。 我們需要建立一套磁盤文件行為的規(guī)范化表示，并捕獲一段時 間內(nèi)的記

11、錄，建立一個測試數(shù)據(jù)集，為我們之后作訓(xùn)練作準(zhǔn)備2.入侵檢測算法的理論研究發(fā)展我們前面提到一個關(guān)鍵概念:異常入侵檢測方法依賴于異常模型的建立，不同模型構(gòu)成不同的檢測方法。異常 檢測就是通過觀測到的一組測量值偏離度來預(yù)測用戶行為的變化，然后作出決策判斷 的檢測技術(shù)，下面我們逐步學(xué)習(xí)幾種在學(xué)術(shù)界提出的關(guān)于異常模型的思想概念0 x1:基于特征選擇異常檢測方法基于特征選擇異常檢測方法是通過從一組度量（例如文件創(chuàng)建時間、文件大小、時間/事件孤立度、是否包含敏感關(guān)鍵字中挑選能檢測出入侵的度量構(gòu)成向量（或者子集來準(zhǔn)確 地預(yù)測（或分類已檢測到的異常行為。這種技術(shù)的難點(diǎn)有以下幾個:1 異?；顒雍腿肭只顒又g難于作

12、出判斷（回想之前我們提到的入侵性活動和異?；顒拥年P(guān)系2進(jìn)行二值分類的特征值（閾值的選取是否合理、符合實(shí)際、達(dá)到準(zhǔn)確效果 為此，一個度量集（特征向量對各種各樣的入侵類型不可能是足夠的。 在文獻(xiàn)（網(wǎng)絡(luò)安全入侵檢測研究綜述.pdf中提到使用學(xué)習(xí)分類器方案生成遺傳交叉算 子和基因突變算子，除去降低預(yù)測入侵的度量子集，而采用遺傳算子產(chǎn)生更強(qiáng)的度量自己 取代。這里小瀚個人覺得對于可疑磁盤文件操作行為的入侵分類，我們需要著重考慮的問題 有兩個1度量子集的選取:和遺傳優(yōu)化算法相比，更加利于項(xiàng)目實(shí)踐、更貼近實(shí)際的做法是將安全研究員的經(jīng) 驗(yàn)進(jìn)行固化，安全人員根據(jù)服務(wù)器滲透、入侵、cms漏洞的實(shí)際研究經(jīng)驗(yàn)，選擇在正

13、常業(yè) 務(wù)操作、和黑客攻擊中所表現(xiàn)出的所有度量維度。以此來建立入侵檢測度量子集。2測量值偏移度（異常閾值的確定:比起度量子集的選擇，測量值偏移度的計算則更加棘手，即使采用安全人員的安全 知識來進(jìn)行確定也具有很大的主觀性、隨機(jī)性的制約。很難保證確定的閾值的正確性，因 為在不同的業(yè)務(wù)場景（web系統(tǒng)下，超過怎樣的值算作入侵，不是很容易用經(jīng)驗(yàn)進(jìn)行確定，在這方面。在這個 問題上，可以考慮引入例如機(jī)器學(xué)習(xí)、遺傳算法這類的反饋機(jī)制，不斷通過，通過一些學(xué) 習(xí)的過程來確定最好的閾值（所以提到引入kdd的這種思想，建立一個文件操作行為的kdd數(shù)據(jù)集，進(jìn)行數(shù)據(jù)分析0 x2:基于貝葉斯推理的異常檢測方法 基于貝葉斯推

14、理的異常檢測方法是通過在任意給定的時刻測量值，推理判斷系統(tǒng)是否有入侵事件發(fā)生。其中每個變量表示系統(tǒng)不同方面的特征:a1,a2,a3.an變量1如磁盤i/0的活動數(shù)量2或者系統(tǒng)中頁面出錯的數(shù)量下面是數(shù)學(xué)的模型定義:1假定ai變量有兩個值: 1表示異常、0表示正常2 i表示系統(tǒng)當(dāng)前遭受入侵攻擊。每個異常變量ai的異?？煽啃员硎緸?p(ai=1/l和敏感性”表示為：和p(ai=1/q因此，根據(jù)各種異常測量的值、入侵的先驗(yàn)概率及入侵發(fā)生時每種測量到的異常概 率，能夠檢測判斷入侵的概率。但是，為了檢測的準(zhǔn)確性，還必須考慮各個測量ai之間的獨(dú)立性。一種方法是通過相 關(guān)性分析，確定各個異常變量與入侵的關(guān)系0

15、 x3：基于模式預(yù)測的異常檢測方法基于模式預(yù)測的異常檢測方法的假設(shè)條件是事件序列不是隨機(jī)的而是遵循可辨別的 模式。這種檢測方法的特點(diǎn)是：1考慮了事件的序列2考慮了事件之間的相互聯(lián)系teng和chen給出了基于時間的推理方法，利用時間規(guī)則來識別用戶行為正常模式 的特征。classfication and detection of computer intrusions通過歸納學(xué)習(xí)產(chǎn)生這些規(guī)則集，并能動態(tài)地修改系統(tǒng)中這些規(guī)則，使之具有較高效的 預(yù)測性、準(zhǔn)確性、和可信度，如果規(guī)則大部分時間是正確的，并能夠成功地運(yùn)用預(yù)測所觀 察到的數(shù)據(jù)，那么規(guī)則就 具有高可信度，tlm給出了一條產(chǎn)生規(guī)則：(e1-e2

16、-e3-(e4=95%、e5=5%其中e1e5表示安全事件 這條規(guī)則表明：如果前面觀測到事件e1-e2-e3這樣一個事件鏈模式，則后面觀測到e4事件的概率 是95%，而e5事件的概率是5%根據(jù)觀察到的用戶行為、或者機(jī)器行為歸納出一套規(guī)則規(guī)則集來構(gòu)成用戶的輪廓 框架。1如果觀察到的事件序列匹配規(guī)則的左邊，而后續(xù)事件顯著偏離規(guī)則預(yù)測到的事 件，那么系統(tǒng)就可以檢測出這種偏離，這就表明用戶操作是異常的，否則相反這種技術(shù)的優(yōu)點(diǎn)有：1能較好地處理變化多樣的用戶行為，并具有很強(qiáng)的時序模式2能夠集中考察少數(shù)幾個相關(guān)的安全事件，而不是關(guān)注可疑的整個會話過程3對發(fā)現(xiàn)檢測系統(tǒng)遭受攻擊，具有良好的靈敏度4根據(jù)規(guī)則的蘊(yùn)

17、含語義，在系統(tǒng)學(xué)習(xí)階段，能夠更容易地辨別出欺騙著訓(xùn)練系統(tǒng)的 企圖0 x4：基于數(shù)據(jù)采掘的異常檢測方法 除了依靠安全人員的經(jīng)驗(yàn)固化來建立規(guī)則、模式。還有一種思路是將數(shù)據(jù)挖掘技術(shù)應(yīng) 用到入侵檢測研究領(lǐng)域中，從審計數(shù)據(jù)或數(shù)據(jù)流中提取感興趣的知識，這些知識是：1隱含的2事先未知的3潛在的有用信息 提取的知識表示為：1概念2規(guī)則3規(guī)律4模式等形式 并可用這些知識去檢測異常入侵和已知的入侵。基于數(shù)據(jù)挖掘的異常檢測方法目前已 有現(xiàn)成的kdd算法可疑借用，這種方法的優(yōu)點(diǎn)是可適應(yīng)處理大量數(shù)據(jù)的情況0 x5:適合于入侵檢測的分步特征選擇算法 入侵檢測是一種通過收集和分析被保護(hù)系統(tǒng)的信息，從而發(fā)現(xiàn)入侵的技術(shù)。它的主

18、要 功能是對網(wǎng)絡(luò)和計算機(jī)系統(tǒng)進(jìn)行實(shí)時監(jiān)控，發(fā)現(xiàn)和識別系統(tǒng)中的入侵行為或企圖，給出入 侵警報。我們知道，入侵行為的特征是由特征來刻畫的，一般情況下，只有特征向量中包含 足夠多的類別信息，才能通過分類器實(shí)現(xiàn)正確分類:識別正常、或入侵。而問題就在于:怎么證明特征向量中是否包含足夠的類別信息是很難確定的，為此，為 了提高識別率，系統(tǒng)總是最大限度地提取特征信息，使得特征維數(shù)增大。但是，維數(shù)的增 大、數(shù)據(jù)量的提高必然導(dǎo)致入侵檢測系統(tǒng)處理的速度下降，計算資源消耗增大。同時還有另一方面，不同的特征對檢測的有效性貢獻(xiàn)也不同（即它們的權(quán)值不同，如 果對它們相同對待就會導(dǎo)致算法效率下降，因此，根據(jù)特征的貢獻(xiàn)度權(quán)值分

19、配不同的資源 對入侵檢測算法來說是一個值得考慮的方面因此，特征選擇算法的任務(wù)主要是刪除兩類特征:1無用特征2冗余特征 傳統(tǒng)入侵檢測的特征選擇算法是以對一組測試數(shù)據(jù)檢測的正確性、或時間作為度量準(zhǔn) 則，這種方法有一定的局限性:即使測試數(shù)據(jù)的統(tǒng)計特性與實(shí)際特性相同，它也是針對特定 的檢測方法，缺乏普遍性拋開檢測算法，從數(shù)據(jù)統(tǒng)計特性出發(fā)，文獻(xiàn)提出了一種基于互信息的分步特征選擇算法，首先刪除無用特征，然后再刪除冗余特征，減少了刪除冗余特征的計算量0 x6:模式匹配算法在入侵檢測中的應(yīng)用我們知道，入侵檢測分為誤用檢測和異常檢測，之前學(xué)習(xí)的都是異常檢測，接下來繼續(xù)學(xué)習(xí)誤用檢測，而誤用檢測中使用的檢測技術(shù)中占

20、大多數(shù)的主要是模式匹配是所謂的正則匹配（也就模式匹配算法性能的好壞直接影響到入侵檢測系統(tǒng)的效率。隨著網(wǎng)絡(luò)傳輸速度的大幅 度提高，入侵檢測系統(tǒng)需要處理的數(shù)據(jù)量越來越大，如果模式匹配算法來不及處理這些實(shí) 時的大量的數(shù)據(jù)包，必然 會丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息，從而造成漏報我們接下來學(xué)習(xí)幾種用于入侵檢測的模式匹配算法，包括:1單模式匹配算法模式匹配：是指在給定長度為n的目標(biāo)串t=t1t2tn中查找長度為m的模式串p=p1p2pm的首次出現(xiàn)或多次出現(xiàn)的過程。這里ti（1isnpj（1，若1次 或 多 次 ，1次只能對1個模式串進(jìn)p在行匹配的算法t中 出 現(xiàn)則稱匹配成功，

21、否則稱匹配失敗。單模式匹配算法：在目標(biāo)串中2多模式匹配算法在目標(biāo)串中可同時對多個模式串進(jìn)行匹配的算法（即多模正則匹配單模匹配算法、多模匹配算法是一種思想，它們有很多具體的算法實(shí)現(xiàn)，下面逐一學(xué)1.單模匹配算法1.1bruteforce算法（bf算法在bf算法的目標(biāo)串和模式串的字符比較中，只要有1個字符不相等，而不管前面已 有多少個字符相等，就需要把目標(biāo)串t回退，下次比較時目標(biāo)串t只后移1個字符。雖然 算法簡單，但效率低下從這個缺點(diǎn)出發(fā)，可以明白匹配算法的優(yōu)化方向 高效的模式匹配算法都是設(shè)法增大不匹配時目標(biāo)串t或模式串p之間的偏移量，以減 少總的比較次數(shù)(即減小時間復(fù)雜度1.2 kmp算法1970

22、年，sacook從理論上證明了一維模式匹配問題可以在o(m+2時間內(nèi)解決。d.e.knuth,v.r.pratt和t.h.morris在bf算法的基礎(chǔ)上提出了一種快速模式 匹配算法，稱為kmp算法，該算法消除了bf算法的目標(biāo)串指針在相當(dāng)多個字符比較相等 后，只要有1個字符比較不等便需要回溯的缺點(diǎn)，使算法的效率得到了大幅度提高，時間 復(fù)雜度達(dá)到最理想的o(m+n，空間復(fù)雜度是o(m1.3 bm算法相對于bf算法，kmp算法雖然消除了主串指針的回溯，在不匹配時能使模式串右滑 若干位，但由上述next函數(shù)可知：右滑的最大距離不會超過1趟匹配操作所進(jìn)了的比較次 數(shù)j，原因在于kmp算法的匹配操作是從左

23、到右進(jìn)行的。受到rsboyer和jsmoore提出一種新的快速字符串匹配算法一1.4 rk算法kmp算法的啟發(fā)，bm算法。karp和rabin在1981年提出來的rk算法利用了hash方法和素數(shù)理論。rk算法的思想是:1首先定義一個hash函數(shù)，用該函數(shù)計算出模式串p的hash函數(shù)值2再計算出目標(biāo)串t中所有長度為m的子串的hash函數(shù)值3然后用相應(yīng)的hash函數(shù)值進(jìn)行比較。當(dāng)出現(xiàn)hash沖突時，再進(jìn)行相應(yīng)字符串的 比較4當(dāng)構(gòu)造hash函數(shù)的素數(shù)選擇得合理，hash沖突出現(xiàn)的概率就可以做到很小。rk算法的時間復(fù)雜度是0(mn。在實(shí)際應(yīng)用中，可設(shè)法取kr算法的如果hash沖突不發(fā)生，即不再需要額外

24、的字符匹配，0(m+n;若考慮字符匹配，則rk算法的時間復(fù)雜度是適當(dāng)大的素數(shù)q,使得mod q仍可執(zhí)行并且hash沖突又幾乎不發(fā)生，從而使得實(shí)際運(yùn)行時間只需0(m+n。rk算法采用了與kmp和bf算法不同的思路,盡量減少字符之間的比較次數(shù),從而 達(dá)到提高效率的目的2.多模式匹配算法 與單模式匹配算法相比,多模式匹配算法的優(yōu)勢在于一趟遍歷可以對多個模式進(jìn)行匹 配,從而大大提高了匹配效率。對于單模式匹配算法,如果要匹配多個模式,那么有幾個 模式就需要幾趟遍歷。當(dāng)然多模式匹配算法也適用于單模式的情況。下面學(xué)習(xí)一下多模匹配的相關(guān)算法2.1 ahocorasick(ac算法ac算法1975年產(chǎn)生于貝爾實(shí)

25、驗(yàn)室,最早用于圖書館的書目查詢程序中。該算法基于 有限狀態(tài)自動機(jī)(fsa,在進(jìn)行匹配之前先對模式串集合sp進(jìn)行預(yù)處理,形成模式樹(樹 形fsa，然后只需對目標(biāo)串t掃描一次就可以找出所有與其匹配的模式串p。模式樹k的構(gòu)成如下:ac算法模式匹配的時間復(fù)雜度是的長度無關(guān)。無論模式串中，所以無論是最好情況還是最壞情況，0（n，并且與模式集中模式串的個數(shù)和每個模式串a(chǎn)c算法模式匹配的時間復(fù)雜度都是0（n，包括p是否出現(xiàn)在目標(biāo)串t中，t中的每個字符都必須輸入狀態(tài)機(jī)預(yù)處理時間在內(nèi)，ac算法總時間復(fù)雜度是o（m+n，其中m為所有模式串的長度總和22 acbm算法對多模式串的匹配而言，雖然ac算法比bm算法高效

26、得多，但ac算法必須逐一查bm算法則能夠利用 右滑”ac算法中，則可大大提高commentzwalter最先將snort就是采用commentzwalter算法；baezayates結(jié)合bmp看目標(biāo)串的每個字符，即必須按順序輸入，不能實(shí)現(xiàn)跳躍，而應(yīng)用到多模式匹配算法的效率。許多人據(jù)此給出了各種改進(jìn)的算法。跳 過 目 標(biāo) 串 中 的 大 段 字 符， 從 而 提高搜索速度。如果將bm算法的這種啟發(fā)式搜索技術(shù)bm算法和ac算法結(jié)合在一起給出了ac-bm的優(yōu)化算法算法和ac算法也給出了多模式匹配改進(jìn)算法。據(jù)說著名的入侵檢測系統(tǒng)3.入侵檢測算法的一種實(shí)現(xiàn)嘗試目前對漏報的問題基本沒遇到問題，但是對誤報的

27、問題很嚴(yán)重，從特征子集（規(guī)則的角度、和偏移度（閾值這兩個角度應(yīng)該還有很多需要改進(jìn)、優(yōu)化的地方/*算法目的：對磁盤文件的正常操作、異常操作進(jìn)行二值區(qū)分，起到入侵檢測的作用事件特征向量維度：向量0 x1:可疑文件創(chuàng)建行為（on_fileadded1相鄰兩次文件創(chuàng)建時間的間距2相鄰兩次文件創(chuàng)建時間的間距的閾值（判斷是否為密集文件操作3密集文件創(chuàng)建事件連續(xù)發(fā)生的次數(shù)密集文件創(chuàng)建事件（在間距閾值之內(nèi)發(fā)生一次文件創(chuàng)建算作一次4文件的擴(kuò)展名后綴5新建文件所在目錄的其他文件創(chuàng)建時間的平均值6新建文件所在的目錄是否為新建目錄向量0 x2:可疑文件修改行為(on_filemodified1相鄰兩次文件修改時間的間

28、距2相鄰兩次文件修改時間的間距的閾值(判斷是否為密集文件操作3密集文件修改事件連續(xù)發(fā)生的次數(shù)密集文件創(chuàng)建事件(在間距閾值之內(nèi)發(fā)生一次文件修改算作一次4文件的擴(kuò)展名后綴5文件的修改時間和創(chuàng)建時間的差值(表明是否是老文件被修改/頭文件#include /變量聲明unsigned long file_create_time_last。/記錄上一次文件創(chuàng)建的unix時間unsignedlong file_create_time_count。/記錄本次文件創(chuàng)建的unix時間unsigned longfile_modify_time_last。/記錄上一次文件被重寫、修改的unsigned long fi

29、le_modify_time_count。件被重寫、修改的unix時間/記錄本次文unix時間/*當(dāng)有文件的創(chuàng)建操作時觸發(fā)這個回調(diào)函數(shù)parameter:const cstring & strfilename:捕獲到的磁盤文件操作的完整路徑return value:1:入侵事件0:正常操作*/int on_fileadded(const cstring & strfilename/*說明:在進(jìn)行實(shí)際的入侵行為判斷前，先進(jìn)行一次密集文件創(chuàng)建狀態(tài)判斷，因?yàn)橛幸韵聨追N行為可能導(dǎo)致短時間內(nèi)出現(xiàn)大量的文件創(chuàng)建操作被捕獲1管理員通過ftp、ssh、rdp登錄后在web根目錄下進(jìn)行單個文件的

30、新建2管理員在進(jìn)行文件單個、批量復(fù)制一個文件新建的行為(復(fù)制文件從操作系統(tǒng)的層面上來看還是3 rar壓縮包解壓(rar壓縮包解壓只是一種軟件機(jī)制，在操作系統(tǒng)層面還是 在進(jìn)行文件的新建4 cache臨時緩存文件5預(yù)編譯模板高速緩存6網(wǎng)站配置信息settings高速緩存7 log日志文件、error_log出錯日志文件8文件上傳控件(fck、kindeditor導(dǎo)致的圖片、rar附件上傳9 web系統(tǒng)為了并發(fā)串行訪問的需求生成臨時鎖文件(.lock在入侵檢測前排除掉這部分的報告，可以減少一些誤報 參數(shù)說明:兩次創(chuàng)建事件時間間隔閾值(小于則說明在進(jìn)行密集文件創(chuàng)建密集文件創(chuàng)建事件連續(xù)發(fā)生的次數(shù)內(nèi)則說明

31、當(dāng)前處于密集文件復(fù)制狀態(tài): 5次: 10ms(如果連續(xù)5次的文件創(chuàng)建時間間隔都在閾值之*/if (intensive_file_creation_detection(strfilename, 10, 5 = 1/處于文件創(chuàng)建密集狀態(tài)，即正常操作return 0。else/并非文件創(chuàng)建密集狀態(tài)，繼續(xù)判斷邏輯/參數(shù)說明: strfilename為捕獲到的磁盤文件操作的完整路徑if (createtime_detection(strfilename = 1/入侵事件return 1。else/正常操作return 0。/*判斷是否處于文件密集創(chuàng)建狀態(tài)中parameter:const cstring

32、& strfilename:捕獲到的磁盤文件操作的完整路徑int threshold:兩次創(chuàng)建事件時間間隔閾值(小于則說明在進(jìn)行密集文件創(chuàng)建int times:密集文件創(chuàng)建事件連續(xù)發(fā)生的次數(shù)(在間距閾值之內(nèi)發(fā)生一次文件創(chuàng)建算作一次密集文件創(chuàng)建事件return:0:并非在進(jìn)行密集文件創(chuàng)建操作1:正在進(jìn)行密集文件創(chuàng)建操作*/int intensive_file_creation_detection(const cstring & strfilename, intthreshold, int timesunsigned long file_create_time_current =

33、0。/新增的當(dāng)前文件的創(chuàng)建時間long handle。/保存指定文件的文件屬性結(jié)構(gòu)體的變量struct _finddata_t fileinfo。handle=_findfirst(strfilename, &fileinfo。if(-1 = handlereturn 0。file_create_time_current = fileinfo.time_create。if ( (file_create_time_current - file_create_time_last file_create_time_count+。/開始計數(shù)file_create_time_last = fil

34、e_create_time_current。else /if( (file_create_time_current - file_create_time_last 60 file_create_time_count=0。/只要有一次不滿足，則計數(shù)器清零file_create_time_last = file_create_time_current。if( file_create_time_count times return 1。else return 0。/*可疑文件創(chuàng)建行為的入侵檢測判斷parameter:const cstring & strfilename:捕獲到的磁盤文件操作

35、的完整路徑 return:1:入侵事件0:正常操作*/int createtime_detection(const cstring & strfilenamechar * pch。char *ext = *.*。long handle。/用來保存路徑中最后一個的位置的指針/需要檢測的文件擴(kuò)展名/保存指定文件的文件屬性結(jié)構(gòu)體的變量char pathbuf128 = 0。/保存路徑信息的緩沖區(qū)struct _finddata_t fileinfo。char createtimebuffer50。/保存文件創(chuàng)建時間(用于顯示之用unsigned long curfilecreatetime。

36、/新增的當(dāng)前文件的創(chuàng)建時間unsigned longavgfilecreatetime = 0。/保存當(dāng)前目錄下所有文件的創(chuàng)建時間的平均 值int i = 0。static int num_file = 0。static int num_bad_file = 0。/只檢測.php、.html文件if(ignore_ext(strfilename = 1 return 0。 /*1.獲取當(dāng)前新增文件的創(chuàng)建時間，為了之后的比較之用*/ handle=_findfirst(strfilename, &fileinfo。if(-1=handlereturn 0。curfilecreatetim

37、e = fileinfo.time_create。/*2.計算當(dāng)前新增文件所在目錄的所有文件的創(chuàng)建時間的平均值1獲取路徑中最后一個的位置2截取從路徑開始到最后一個之前的路徑字符串3拼接通配符4遍歷新增的文件當(dāng)前目錄下的所有文件，知道找不到其他的為止*/ pch =strrchr(strfilename,。strncpy ( pathbuf, strfilename, (pch - strfilename + 1 。strncat (pathbuf,ext, 3。handle=_findfirst(pathbuf, &fileinfo。_findnext(handle,&file

38、info。if(-1=handlereturn 0。while(!_findnext(handle,&fileinfoi+。/*1.當(dāng)前目錄下的所有文件個數(shù)已經(jīng)統(tǒng)計完畢2.開始遍歷新增的文件當(dāng)前目錄下的所有文件，知道找不到其他的為止3. avgfilecreatetime最終的計算結(jié)果就已經(jīng)是平均值了*/handle=_findfirst(pathbuf, &fileinfo。_findnext(handle,&fileinfo。if(-1=handlereturn 0。while(!_findnext(handle,&fileinfoavgfilecreate

39、time += (fileinfo.time_create / i。/*1.根據(jù)一個時間閾值進(jìn)行可疑性判斷2.注意:如果avgfilecreatetime為0，則說明是新創(chuàng)建的文件夾，php的寫磁盤不允許直接創(chuàng)建新目錄的同時寫文件，所以如果是往新的文件夾下復(fù)制文件，一定是合法的行為，要排除這種情況*/if (avgfilecreatetime != 0if (curfilecreatetime - avgfilecreatetime 1000000/m_listbox.addstring( _t(一 個 可 疑 文 件 的 創(chuàng) 建 行 為 被 檢 測 到 + strfilename。retur

40、n 1。elsereturn 0。elsereturn 0。_findclose(handle。/*過濾指定擴(kuò)展名后綴的文件parameter:const cstring & strfilename:捕獲到的磁盤文件操作的完整路徑return:1:這個文件應(yīng)該忽略0:這個文件不能忽略，需要繼續(xù)執(zhí)行檢測邏輯*/int ignore_ext(const cstring & strfilenamechar * pch。/用來保存路徑中最后一個.的位置的指針char extbuf20。/保存需要捕獲文件后綴名char ext_php12 = .php。char ext_html12 =

41、 .html。pch = strrchr(strfilename,.。/獲取路徑中最后一個.的位置strcpy(extbuf, pch。if ( (strcmp(ext_php, extbuf != 0 & (strcmp(ext_html, extbuf != 0/既不是.php、也不是.html，應(yīng)該忽略return 1。:elsereturn 0。/*當(dāng)有文件的修改操作時觸發(fā)這個回調(diào)函數(shù)parameter:const cstring & strfilename:捕獲到的磁盤文件操作的完整路徑 return value:1:入侵事件0:正常操作*/int on_filemo

42、dified(const cstring & strfilename/*說明:在進(jìn)行實(shí)際的入侵行為判斷前，先進(jìn)行一次密集文件修改狀態(tài)判斷，因?yàn)橛幸韵聨追N行為可能導(dǎo)致短時間內(nèi)出現(xiàn)大量的文件修改操作被捕獲1管理員通過ftp、ssh、rdp登錄后在web根目錄下進(jìn)行單個文件的編輯 并修改(注意:從操作系統(tǒng)層面來看，只有打開文件并編輯保存之后才能算文件修改，否則 只是單純的文件訪問行為2網(wǎng)站配置信息settings高速緩存的修改3管理員進(jìn)行網(wǎng)站模板編輯 在入侵檢測前排除掉這部分的報告，可以減少一些誤報 參數(shù)說明:兩次創(chuàng)建事件時間間隔閾值(小于則說明在進(jìn)行密集文件創(chuàng)建: 10000ms密集文件創(chuàng)

43、建事件連續(xù)發(fā)生的次數(shù)(如果連續(xù)5次的文件創(chuàng)建時間間隔都在閾值之 內(nèi)則說明當(dāng)前處于密集文件復(fù)制狀態(tài): 1次*/if (intensive_file_modify_detection(strfilename, 10000, 1 = 1/處于文件修改密集狀態(tài)，即正常操作return 0。else/并非文件修改密集狀態(tài)，繼續(xù)判斷邏輯/參數(shù)說明: strfilename為捕獲到的磁盤文件操作的完整路徑if (modifytime_detection(strfilename = 1/入侵事件return 1。else/正常操作return 0。/*判斷是否處于文件密集修改狀態(tài)中parameter:const cstring & strfilename:捕獲到的磁盤文件操作的完整路徑int threshold:兩次創(chuàng)建事件時間間隔閾值（小于則說明在進(jìn)行密集文件創(chuàng)建int times:密集文件創(chuàng)建事件連續(xù)發(fā)生的次數(shù)（在間距閾值之內(nèi)發(fā)生一次文件創(chuàng)建算作一次密集文件創(chuàng)建事件retu