1、基于關(guān)系數(shù)據(jù)流模型的網(wǎng)絡(luò)入侵檢測系統(tǒng)譚建龍 沈星星 王映摘要：數(shù)據(jù)流管理系統(tǒng)（data stream management system DSMS）是處理動(dòng)態(tài)數(shù)據(jù)集合的一種數(shù)據(jù)管理技術(shù)，采用數(shù)據(jù)流模型對網(wǎng)絡(luò)入侵檢測系統(tǒng)(Network Intrusion Detection System-NIDS)進(jìn)行設(shè)計(jì)，可以利用數(shù)據(jù)流中多持續(xù)查詢優(yōu)化的技術(shù)，提高網(wǎng)絡(luò)入侵檢測系統(tǒng)的性能。同時(shí)使用關(guān)系數(shù)據(jù)流模型可以讓入侵檢測系統(tǒng)結(jié)構(gòu)更加清晰，擴(kuò)展性更好。文章描述網(wǎng)絡(luò)數(shù)據(jù)的關(guān)系結(jié)構(gòu)化，入侵檢測特征的關(guān)系查詢表示以及過濾型多持續(xù)查詢優(yōu)化技術(shù)。這個(gè)系統(tǒng)可以認(rèn)為是數(shù)據(jù)流管理系統(tǒng)的一個(gè)應(yīng)用系統(tǒng)，體現(xiàn)了一些數(shù)據(jù)流管理的概

2、念和核心技術(shù)，對設(shè)計(jì)和實(shí)現(xiàn)通用的數(shù)據(jù)流管理系統(tǒng)具有一定借鑒意義。本文將重點(diǎn)圍繞數(shù)據(jù)流查詢（continue query）的編譯優(yōu)化、數(shù)據(jù)流管理技術(shù)和網(wǎng)絡(luò)安全應(yīng)用的關(guān)系進(jìn)行分析。1. 數(shù)據(jù)流管理系統(tǒng)的功能數(shù)據(jù)流管理技術(shù)是處理相對固定不變的大量查詢和源源不斷的流動(dòng)數(shù)據(jù)的技術(shù)。而網(wǎng)絡(luò)信息安全是解決對網(wǎng)絡(luò)信息的分發(fā)、通訊、管理的問題。由于網(wǎng)絡(luò)信息是典型的源源不斷的數(shù)據(jù)流，同時(shí)有很多網(wǎng)絡(luò)信息安全應(yīng)用系統(tǒng)是采用大量查詢方式，對這些網(wǎng)絡(luò)數(shù)據(jù)流進(jìn)行處理。所以網(wǎng)絡(luò)信息安全是數(shù)據(jù)流管理研究的一個(gè)很好的典型應(yīng)用。這個(gè)安全應(yīng)用必須不間斷無延遲地處理在線、持續(xù)的高速網(wǎng)絡(luò)數(shù)據(jù)流，且網(wǎng)絡(luò)數(shù)據(jù)不可能全都保存在外部存儲器中。我

3、們的研究就是基于持續(xù)查詢概念，采用數(shù)據(jù)流管理系統(tǒng)作為流數(shù)據(jù)處理平臺，將其應(yīng)用到網(wǎng)絡(luò)安全監(jiān)控系統(tǒng)中去。我們實(shí)現(xiàn)了一個(gè)基于數(shù)據(jù)流處理模型的網(wǎng)絡(luò)安全事件監(jiān)控系統(tǒng)IceNetwork。在這個(gè)系統(tǒng)中，數(shù)據(jù)流管理平臺通過優(yōu)化執(zhí)行注冊于系統(tǒng)中的大量持續(xù)查詢，對連續(xù)網(wǎng)絡(luò)流進(jìn)行過濾等操作，完成各種安全事件的監(jiān)測與報(bào)警，從而有效地支持了監(jiān)控系統(tǒng)的實(shí)時(shí)性，準(zhǔn)確性與靈活性要求。本文以建立一個(gè)網(wǎng)絡(luò)入侵檢測技術(shù)系統(tǒng)為案例，采用基于數(shù)據(jù)流管理技術(shù)的思想，來開展數(shù)據(jù)流核心技術(shù)的研究。希望能把工程中的核心問題，轉(zhuǎn)換為數(shù)據(jù)流管理研究領(lǐng)域的通用問題。1.1. 數(shù)據(jù)流管理系統(tǒng)的功能數(shù)據(jù)流管理系統(tǒng)1是為流動(dòng)數(shù)據(jù)管理建立的統(tǒng)一平臺。在數(shù)

4、據(jù)庫管理中，數(shù)據(jù)是相對靜態(tài)的，查詢是動(dòng)態(tài)的；而在數(shù)據(jù)流管理中，查詢是相對靜態(tài)的，數(shù)據(jù)是動(dòng)態(tài)的。也就是說數(shù)據(jù)庫技術(shù)主要研究對數(shù)據(jù)在外存（磁盤）上的存儲索引和一次查詢的執(zhí)行技術(shù)，而數(shù)據(jù)流管理技術(shù)主要研究數(shù)據(jù)在內(nèi)存中的存儲索引和多個(gè)執(zhí)行查詢（continue query）2的執(zhí)行技術(shù)。數(shù)據(jù)庫管理的一個(gè)核心問題是為了高效的查詢，如何建立數(shù)據(jù)對象的索引，而數(shù)據(jù)流管理技術(shù)的核心問題是如何管理這些檢索條件和操縱程序，研究如何為實(shí)現(xiàn)高效的大量查詢進(jìn)行編譯的技術(shù)。 1.2. 網(wǎng)絡(luò)入侵檢測系統(tǒng)為了防范計(jì)算機(jī)被入侵，入侵檢測系統(tǒng)應(yīng)運(yùn)而生。所謂入侵檢測，就是通過從計(jì)算機(jī)網(wǎng)絡(luò)或計(jì)算機(jī)系統(tǒng)中的若干關(guān)鍵點(diǎn)收集信息并對其進(jìn)行

5、分析，發(fā)現(xiàn)網(wǎng)絡(luò)或系統(tǒng)中是否有違反安全策略的行為和遭到襲擊的跡象，并對此做出適當(dāng)反應(yīng)的過程。根據(jù)入侵檢測系統(tǒng)部署的位置以及網(wǎng)絡(luò)數(shù)據(jù)的來源，入侵檢測系統(tǒng)可以分為兩類：主機(jī)入侵檢測系統(tǒng)(HIDS Host Intrusion Detection System)和網(wǎng)絡(luò)入侵檢測系統(tǒng)(NIDS)。其中HIDS部署于單個(gè)主機(jī)，收集所有進(jìn)入本主機(jī)的數(shù)據(jù)，加以分析檢測。而NIDS部署于一個(gè)子網(wǎng)的出入口，以進(jìn)出子網(wǎng)的網(wǎng)絡(luò)包做為分析數(shù)據(jù)源。通常利用一個(gè)工作在混雜模式下的網(wǎng)卡來實(shí)時(shí)監(jiān)視并分析通過網(wǎng)絡(luò)的數(shù)據(jù)流。其分析模塊通常使用模式匹配、統(tǒng)計(jì)分析等技術(shù)來識別攻擊行為。一旦檢測到了攻擊行為，NIDS的響應(yīng)模塊就作出適當(dāng)?shù)?/p>

6、響應(yīng)，比如報(bào)警、切斷相關(guān)用戶的網(wǎng)絡(luò)連接等。由于NIDS采用在關(guān)鍵節(jié)點(diǎn)集中監(jiān)測的方式，能夠監(jiān)控整個(gè)子網(wǎng)，并且對于子網(wǎng)內(nèi)單個(gè)主機(jī)來說是透明的，因此部署起來比HIDS方便得多。隨著越來越多的單位和企業(yè)采用以太網(wǎng)的局域網(wǎng)組網(wǎng)方式，NIDS得到了廣泛的應(yīng)用。NIDS的主要檢測手段是模式匹配，這里說的“模式”是指，網(wǎng)絡(luò)數(shù)據(jù)包的頭部信息或者載荷中的數(shù)據(jù)滿足的特定條件，網(wǎng)絡(luò)安全領(lǐng)域把能夠判定一個(gè)入侵的一組特征條件叫做“特征(Signature)”。Snort3是一個(gè)成熟的、被廣泛使用的、開放源代碼網(wǎng)絡(luò)入侵檢測系統(tǒng)，它的有效性已經(jīng)得到時(shí)間的驗(yàn)證。它具有一個(gè)可配置的特征庫(因?yàn)樗拿恳粋€(gè)特征對應(yīng)于一條規(guī)則，我們也

7、把它的特征庫稱為規(guī)則庫)，最新版本的Snort規(guī)則庫包含了約2300條常見網(wǎng)絡(luò)入侵的檢測規(guī)則。圖1為Snort2.0中檢測引擎的工作流程圖。圖1 snort2.0 包數(shù)據(jù)和特征(處理圖)典型情況是包通過且僅通過多特征過濾引擎一次，所以設(shè)計(jì)高效的多特征過濾引擎是入侵檢測系統(tǒng)的核心問題之一。對于一個(gè)在監(jiān)控整個(gè)子網(wǎng)的入侵檢測系統(tǒng)來說，網(wǎng)絡(luò)數(shù)據(jù)捕獲，TCP組包、應(yīng)用協(xié)議分析、特征設(shè)計(jì)方、多特征過濾引擎是決定效率的主要方面，也是研究的重點(diǎn)內(nèi)容。2. 關(guān)系數(shù)據(jù)數(shù)據(jù)流模型的網(wǎng)絡(luò)入侵檢測系統(tǒng)一個(gè)采用數(shù)據(jù)流管理系統(tǒng)作為處理引擎的NIDS的結(jié)構(gòu)如圖2所示。查詢提交捕包前端網(wǎng)絡(luò)數(shù)據(jù)入侵檢測引擎DSMS引擎檢測結(jié)果處

8、理模塊檢測條件圖2 基于DSMS的NIDS結(jié)構(gòu)圖其中捕包前端負(fù)責(zé)將以太網(wǎng)數(shù)據(jù)幀捕獲，并轉(zhuǎn)換為預(yù)定義的結(jié)構(gòu)化數(shù)據(jù)，提交給入侵檢測引擎。入侵檢測引擎的核心是DSMS引擎，其中預(yù)先注冊了大量以數(shù)據(jù)流查詢語言表示的入侵檢測條件。當(dāng)格式化的描述網(wǎng)絡(luò)數(shù)據(jù)包的關(guān)系元組到達(dá)時(shí)，計(jì)算注冊查詢。檢測結(jié)果被傳給檢測結(jié)果處理模塊，以對入侵進(jìn)行報(bào)警等后續(xù)處理。2.1. 網(wǎng)絡(luò)入侵檢測系統(tǒng)和數(shù)據(jù)流管理技術(shù)的關(guān)系如果我們把網(wǎng)絡(luò)入侵檢測系統(tǒng)看作數(shù)據(jù)流管理系統(tǒng)的一個(gè)應(yīng)用，數(shù)據(jù)流管理系統(tǒng)為入侵檢測系統(tǒng)提供一個(gè)基礎(chǔ)的平臺，那么數(shù)據(jù)流管理平臺就需要為入侵檢測系統(tǒng)提供一些核心技術(shù)的支持。下表說明網(wǎng)絡(luò)入侵檢測系統(tǒng)和數(shù)據(jù)流管理技術(shù)的關(guān)系。從

9、對照比中我們可以看出入侵檢測系統(tǒng)需要使用到大量的數(shù)據(jù)流管理的核心技術(shù)。把數(shù)據(jù)流管理研究的技術(shù)應(yīng)用到入侵檢測系統(tǒng)中，將為入侵檢測系統(tǒng)提供良好的性能和擴(kuò)展性。網(wǎng)絡(luò)入侵檢測系統(tǒng)數(shù)據(jù)流管理系統(tǒng)聯(lián)系應(yīng)用系統(tǒng)基礎(chǔ)平臺網(wǎng)絡(luò)入侵檢測系統(tǒng)是基于數(shù)據(jù)流管理系統(tǒng)的應(yīng)用系統(tǒng)。網(wǎng)絡(luò)數(shù)據(jù)捕獲：將網(wǎng)絡(luò)的數(shù)據(jù)保存到內(nèi)存中。難點(diǎn)主要是如何在內(nèi)存中存儲大量的數(shù)據(jù)，同時(shí)及時(shí)將處理后的數(shù)據(jù)丟棄。內(nèi)存數(shù)據(jù)存儲：解決海量關(guān)系數(shù)據(jù)的存儲問題。主要是處理數(shù)據(jù)滑動(dòng)出處理窗口后，如何高效地丟棄掉。由于數(shù)據(jù)流管理系統(tǒng)只能處理關(guān)系化的數(shù)據(jù)，所以如何把網(wǎng)絡(luò)數(shù)據(jù)包變化為關(guān)系數(shù)據(jù)，將是這部分需要完成的工作。TCP組包：將網(wǎng)絡(luò)上的單個(gè)IP包，拼裝為一個(gè)完整

10、的TCP流。主要解決IP后序包先到，和存在碎片包的問題。要保證應(yīng)用層可以看到連續(xù)的網(wǎng)絡(luò)數(shù)據(jù)流。內(nèi)存數(shù)據(jù)索引：解決在內(nèi)存數(shù)據(jù)中，如何通過鍵(key)找到數(shù)據(jù)記錄的問題和如何對數(shù)據(jù)建立鍵索引(index)的問題核心問題是如何通過IP包的地址信息找到以前的數(shù)據(jù)包。也就是對已經(jīng)存在的數(shù)據(jù)包按IP地址對建立好索引，將來新數(shù)據(jù)包到來的時(shí)候，通過這個(gè)索引找到對應(yīng)的TCP流。應(yīng)用協(xié)議分析：協(xié)議分析包括協(xié)議解碼、協(xié)議狀態(tài)識別、協(xié)議內(nèi)容分析等工作多流連接：如果多個(gè)數(shù)據(jù)流存在一定的關(guān)系，需要將這多個(gè)數(shù)據(jù)流窗口內(nèi)的表進(jìn)行多表連接計(jì)算，形成一個(gè)表關(guān)系后再進(jìn)行持續(xù)查詢的過濾。核心問題是協(xié)議分析可能需要關(guān)注其他流的信息，例

11、如ftp命令流的結(jié)果，可能對當(dāng)前文件傳輸流的分析是有用的。所以需要連接這兩個(gè)流，才能進(jìn)行判斷和計(jì)算。特征設(shè)計(jì)方案：特征設(shè)計(jì)的時(shí)候需要考慮特征對入侵描述的簡潔性和高效實(shí)現(xiàn)擴(kuò)展的可能性。使用關(guān)系查詢語句來定義查詢的條件和過濾的操作。每個(gè)網(wǎng)絡(luò)入侵檢測產(chǎn)品使用單獨(dú)的入侵特征，不利用入侵檢測系統(tǒng)之間的信息交流。多特征過濾引擎：多特征過濾引擎一般包括協(xié)議域搜索、一般內(nèi)容搜索、包頭異常檢測。單流多持續(xù)查詢執(zhí)行引擎：對關(guān)系數(shù)據(jù)流中的字段屬性，一般分為字符串字段、整數(shù)字段、實(shí)數(shù)字段、時(shí)間日期等字段。針對不同的字段類型，可以設(shè)計(jì)不同的多持續(xù)查詢優(yōu)化策略。同時(shí)各個(gè)字段間的判斷次序也是一個(gè)需要考慮的問題。入侵檢測系統(tǒng)

12、中，IP地址可以看作整數(shù)字段；包內(nèi)容可以看做字符串字段；IP頭的字段一般是整數(shù)字段。所以入侵檢測系統(tǒng)中需要設(shè)計(jì)的是整數(shù)字段和字符串字段的單流多持續(xù)查詢優(yōu)化。從上表可以看出，基于關(guān)系數(shù)據(jù)流模型的入侵檢測系統(tǒng)，需要解決網(wǎng)絡(luò)數(shù)據(jù)關(guān)系化存儲（網(wǎng)絡(luò)數(shù)據(jù)捕獲）、整數(shù)字段索引（TCP組包）、特征設(shè)計(jì)方案、整數(shù)字段持續(xù)查詢編譯、字符串字段持續(xù)查詢編譯（多特征過濾引擎）等問題。還應(yīng)包括多流連接查詢、字段判斷次序、實(shí)數(shù)字段的持續(xù)查詢編譯等問題。2.2. 網(wǎng)絡(luò)數(shù)據(jù)關(guān)系化我們利用改進(jìn)的輕量級捕包程序winpcap進(jìn)行捕包，對于每一個(gè)IP包，首先對載荷部分進(jìn)行統(tǒng)一的關(guān)鍵詞掃描。如果沒有命中的關(guān)鍵詞則將其拋棄；否則，將其

13、拼到相應(yīng)的TCP流，提取包內(nèi)各個(gè)字段信息，分別生成兩個(gè)流：TCPLink 與Packet。TCPLink包括一個(gè)連接的四元組信息，表示了一個(gè)包所屬的TCP連接，兩個(gè)流格式如下：TCPLinkID PRIMARY KEYSourceIPDestIP,SourcePortDestPort.PacketID PRIMARY KEYTcpID Foreign KEYFragOffset; /IP頭信息TTL, Buff varchar(64,000).其中，TCPLink是主流，每一個(gè)元組對應(yīng)一個(gè)連接；Packet是輔流，記錄主流中每個(gè)元組對應(yīng)的每一個(gè)包的各個(gè)字段的具體值。主流與輔流之間是一對多的關(guān)系

14、。通過對網(wǎng)絡(luò)包的預(yù)處理，形成兩條流，完成了網(wǎng)絡(luò)數(shù)據(jù)的關(guān)系化，從而可以在其上進(jìn)行關(guān)系操作。2.3. 入侵檢測特征的關(guān)系查詢表示數(shù)據(jù)流管理系統(tǒng)只接受SQL語句表示的查詢，因此我們必須將Snort的特征轉(zhuǎn)換為SQL表示，這需要解析Snort規(guī)則。我們實(shí)現(xiàn)了一個(gè)規(guī)則轉(zhuǎn)換程序RulesParser，讀入標(biāo)準(zhǔn)snort規(guī)則，生成數(shù)據(jù)流管理系統(tǒng)NIDS的SQL查詢。一條典型的Snort規(guī)則如下：alert tcp any any -> any 6666:7000 (msg:"EXPLOIT CHAT IRC Ettercap parse overflow attempt" flow

15、:to_server,established; content:"PRIVMSG" nocase; content:"nickserv" nocase; content:"IDENTIFY" nocase; isdataat:100,relative; pcre:"/PRIVMSGs+nickservs+IDENTIFYsn100/smi" reference:url,/dev/GOBBLES-12.txt; classtype:misc-attack; sid:1382; rev:9

16、;)這條規(guī)則表達(dá)的含義是：一個(gè)TCP數(shù)據(jù)報(bào)，無論來自哪個(gè)IP地址的哪個(gè)端口，只要是6666:7000 端口，并且含有二進(jìn)制串” PRIVMSG”，“nickserv”，“IDENTIFY ”等則觸發(fā)報(bào)警，報(bào)警信息為” EXPLOIT CHAT IRC Ettercap parse overflow attempt”。 轉(zhuǎn)換成關(guān)系數(shù)據(jù)上的查詢SELECT * FROM packet WHERE packet.ip_proto=6 AND (packet.DestinationPort>=6666 AND packet.DestinationPort<=7000) AND (packe

17、t.flowflag&18)=18 AND packet.ruleid=110 AND substr(content,”PRIVMSG”) ANDsubstr(content,” nickserv”) AND substr(content,” IDENTIFY”) AND bytetest(content,100)3. 過濾型多持續(xù)查詢優(yōu)化網(wǎng)絡(luò)入侵檢測系統(tǒng)所注冊的持續(xù)查詢基本上均為過濾型查詢（Filter），即對由網(wǎng)絡(luò)包生成的關(guān)系表中某些字段的選擇操作。這些字段類型包括字符型、整型等。我們分別針對不同字段類型設(shè)計(jì)過濾型多持續(xù)查詢優(yōu)化算法。3.1. 字符字段的多串匹配優(yōu)化字符串匹配是包的

18、規(guī)則檢測中最耗時(shí)的一個(gè)操作，很大程度上決定了檢測引擎的性能。snort2.0中采用改進(jìn)的Wu-Manber4和AhoCorasick4多串匹配算法，比以前的算法性能有了大幅提高。在我們的系統(tǒng)中，采用了一種新的高效多串匹配算法SBOM6，試驗(yàn)表明，這種算法同樣能取得較高的性能。3.2. 整數(shù)字段的模式匹配優(yōu)化Snort規(guī)則中，除了content選項(xiàng)是對網(wǎng)絡(luò)包載荷部分進(jìn)行關(guān)鍵詞模式匹配，還有相當(dāng)數(shù)量的包頭協(xié)議字段的數(shù)值匹配。如源、目的端口、ttl值等。一種直觀而簡單的處理方式是對每一個(gè)到來的數(shù)據(jù)包，先順次執(zhí)行一條規(guī)則中各個(gè)字段的數(shù)值比較，再順次執(zhí)行多條規(guī)則。這種處理方式有幾個(gè)弊端：n 時(shí)間復(fù)雜度是

19、O(n)，n為總規(guī)則數(shù)目，即比較次數(shù)與規(guī)則條數(shù)成正比。處理時(shí)間隨著規(guī)則數(shù)目的增加而線性增長。當(dāng)前的snort包含2300多條規(guī)則，其中不含content字段的包異常檢測有相當(dāng)數(shù)量。日益增多的網(wǎng)絡(luò)攻擊使得規(guī)則數(shù)目仍在增長。如此大量的規(guī)則數(shù)導(dǎo)致的匹配引擎性能下降已經(jīng)是一個(gè)不得不考慮的問題。n 針對各個(gè)屬性域上的判斷，規(guī)則與規(guī)則之間存在冗余。考慮下面兩條規(guī)則片斷：Rule1: SourcePort=200; DestPort=23;ttl=3;Rule2: 80<=SourcePort<6000; DestPort!=8080;ttl=5;Rule3: SourcePort=80;Des

20、tPort=23;ttl=3;若某個(gè)包的SourcePort字段為60，如果第一條規(guī)則不滿足必然不滿足第二條規(guī)則，因此不用再進(jìn)行第二次比較。可見順次執(zhí)行各條規(guī)則的判斷導(dǎo)致產(chǎn)生多余的比較。所以，針對上述兩個(gè)弊端，我們提出新的數(shù)值型模式匹配算法，充分利用大量注冊查詢能夠事先知道的優(yōu)勢，將其進(jìn)行預(yù)編譯，形成有效的內(nèi)部數(shù)據(jù)結(jié)構(gòu)（一個(gè)DFA Deterministic finite automaton，或者說是一棵匹配樹），使得匹配時(shí)間不由規(guī)則數(shù)目線性決定，并減少不必要的比較，從而緩解規(guī)則數(shù)目大，網(wǎng)絡(luò)流速高，導(dǎo)致檢測引擎效率降低的困難。3.2.1. 問題形式化給定一個(gè)關(guān)系，關(guān)系是一個(gè)屬性的（attrib

21、ute）集合：a1, a2an.每一個(gè)這個(gè)關(guān)系上的元組都由各個(gè)屬性域上的值組成。每一個(gè)屬性有它特定的值域范圍aj Dj.每一個(gè)規(guī)則是一系列謂詞的合取范式，每一個(gè)謂詞對應(yīng)于一個(gè)屬性的判斷。" " i Î 1,2 ××× m : Ri = 其中，Pij有如下形式 Pij :Dj ® Boolean如果某個(gè)規(guī)則中對于某個(gè)屬性域沒有限制，則認(rèn)為這條規(guī)則對于這個(gè)屬性域的取值限制是此屬性域上的所有值。首先任意確定一個(gè)屬性順序a1,a2an，則每一個(gè)元組就成為此順序的屬性值域上的序列，且序列的長度是n。每條規(guī)則都可以轉(zhuǎn)化成一個(gè)順次對每個(gè)屬

22、性值判斷的謂詞的合取范式，可以看成一個(gè)非確定有限自動(dòng)機(jī)（NFSA）。我們對每一條規(guī)則都進(jìn)行形式化規(guī)范，這樣使其精確地由n個(gè)條件序列組成。其中的第i個(gè)條件就是作用于第i個(gè)屬性域上的謂詞。如果對第i個(gè)屬性域沒有限制，則認(rèn)為它可以取所在值域上的所有值，在自動(dòng)機(jī)中以TRUE代替。從而，每條規(guī)則都轉(zhuǎn)化為一條匹配路徑，如圖4。同樣的處理辦法，對于每一條規(guī)則都進(jìn)行規(guī)范化，都成為n個(gè)比較步驟。將所有的規(guī)則首尾并列連接起來，就形成一個(gè)對應(yīng)于所有規(guī)則的非確定自動(dòng)機(jī)。如果將其轉(zhuǎn)化為一個(gè)確定性自動(dòng)機(jī)，則對于每一個(gè)元組，走一遍自動(dòng)機(jī)，順次對每一個(gè)屬性域上的值進(jìn)行比較，走完n步之后，可以找出這條屬性滿足的所有規(guī)則。這種算

23、法的關(guān)鍵是將這個(gè)NSFA轉(zhuǎn)化為DSFA。傳統(tǒng)的字符串匹配中的自動(dòng)機(jī)轉(zhuǎn)化方法不能直接應(yīng)用到此情況中。首先，每個(gè)屬性的值域是不確定的，而且可能不是有限域，如值域?yàn)檎麄€(gè)整數(shù)域。而字符串匹配中自動(dòng)機(jī)的值域就是26個(gè)字母，是確定的有限的。另外，不同屬性的值域可能不同，不像字符串自動(dòng)機(jī)中，每一步匹配的值域都是字母集合域。所以，針對規(guī)則匹配的自動(dòng)機(jī)轉(zhuǎn)化，需要解決的問題是對于每個(gè)不同的屬性，如何確定每個(gè)屬性域上的值域，以及如何將原始值轉(zhuǎn)化為新的屬性域上的新值。當(dāng)前我們僅考慮所有字段都是整數(shù)域的情況（對于非整數(shù)域數(shù)值，我們經(jīng)過預(yù)轉(zhuǎn)換將其映射到整數(shù)域）。對于整數(shù)域上所有值不可窮盡枚舉的問題，我們通過生成新字母表的

24、方法解決。下面講述具體算法。 P1 P2 TRUE Pn圖3匹配路徑3.2.2. 算法概述n 生成新值域?qū)?yīng)于某一個(gè)屬性，通過下面所述的轉(zhuǎn)換方式，根據(jù)所有規(guī)則在此屬性上的取值，為此屬性域構(gòu)造新的值域。這個(gè)值域是一個(gè)整數(shù)集合，它的勢是有限的。這樣我們就為每一個(gè)屬性分別構(gòu)造了類似于字符集合的有限的屬性域，從而可以運(yùn)用自動(dòng)機(jī)思想來進(jìn)行匹配。設(shè)有m條規(guī)則，對應(yīng)于某個(gè)屬性i的值域構(gòu)造方法如下：對于整數(shù)域上的每一個(gè)取值范圍，都可以統(tǒng)一用左關(guān)右開的值域來表示。設(shè)置最大值MaxNum與最小值MinNum，這個(gè)值取得足夠大（小）從而所有元組的真實(shí)取值都不會超過這個(gè)范圍。如對于端口號，設(shè)置MinNum=0,Max

25、Num=65535。則對于a1=m，可以表示為a1m,m+1）；對于a1<m,可以表示為a1MinNum,m）； 對于a1>m，可以表示為a1m+1,MaxNum）； 對于n<a1<m，可以表示為a1n+1,m）；類似的，可以這種統(tǒng)一的方式表示出a1在整數(shù)域上的所有范圍。讀入所有規(guī)則中相應(yīng)屬性上的所有取值。設(shè)有m+1個(gè)不同的取值，這樣，整個(gè)整數(shù)軸在最大值與最小值范圍內(nèi)分成m段。如圖4所示。如果為每一個(gè)劃分出的值分別賦予新的字母，則產(chǎn)生了一個(gè)有有限個(gè)數(shù)的值域。每一個(gè)取值必然落在數(shù)軸上的某一段內(nèi)，從而屬于某一個(gè)字母。對于每一個(gè)數(shù)，我們都可以通過二分查找，在(log (m)的

26、時(shí)間內(nèi)得出這個(gè)數(shù)在新值域下的取值。將每一條規(guī)則在新值域下進(jìn)行轉(zhuǎn)換，則所有規(guī)則就轉(zhuǎn)換為新值域下的表示了。考慮到規(guī)則中有Any的情況，也就是對此屬性域上的值不作限制，則將其表示為新值域上所有值的集合。Minnumn1n3n2Maxnumabcd圖4 分段整數(shù)軸，構(gòu)造新的值域n 生成自動(dòng)機(jī)假定有n個(gè)屬性域，共有m條規(guī)則。則自動(dòng)機(jī)樹是一個(gè)n層的樹，每一層代表對一個(gè)屬性值的判斷。樹的每一個(gè)節(jié)點(diǎn)是一個(gè)向量。向量的每一個(gè)元組是一個(gè)結(jié)構(gòu)，包含指向下一個(gè)樹節(jié)點(diǎn)（nextnode）的指針以及當(dāng)前樹節(jié)點(diǎn)所匹配的規(guī)則集合（ruleset）。非葉子節(jié)點(diǎn)的Ruleset均為空，因?yàn)榇藭r(shí)沒有匹配成功的規(guī)則。如果某個(gè)節(jié)點(diǎn)的n

27、extnode域?yàn)榭罩羔槪瑒t表示由當(dāng)前規(guī)則集在這一層所表示的屬性上的相應(yīng)值有匹配狀態(tài)，指針指向下一個(gè)狀態(tài)節(jié)點(diǎn)。而如果某個(gè)節(jié)點(diǎn)的nextnode域?yàn)榭罩羔槪f明匹配樹到此狀態(tài)為止已經(jīng)停止，沒有進(jìn)一步的狀態(tài)。向量的大小對應(yīng)于此節(jié)點(diǎn)包含的規(guī)則集在所屬屬性域上劃分出的新值域的個(gè)數(shù)。向量的下標(biāo)值對應(yīng)于新值域上的相應(yīng)取值。向量在每一個(gè)下標(biāo)下的值是一個(gè)指向節(jié)點(diǎn)的指針，表示當(dāng)前狀態(tài)節(jié)點(diǎn)在對應(yīng)取值下的狀態(tài)轉(zhuǎn)換。圖5 規(guī)則樹結(jié)構(gòu)圖上圖為由Rule1,Rule2,Rule3生成的匹配樹自動(dòng)機(jī)。匹配樹自動(dòng)機(jī)從左至右共三層，每層對應(yīng)一個(gè)屬性字段的匹配，在這里為SourcePort、DestPort、ttl。每個(gè)節(jié)點(diǎn)對應(yīng)

28、一個(gè)臨時(shí)規(guī)則集，表示匹配到這個(gè)節(jié)點(diǎn)時(shí)剩余可能最終匹配成功的所有規(guī)則。根節(jié)點(diǎn)對應(yīng)的規(guī)則集為原始規(guī)則集，包括全部規(guī)則數(shù)。每個(gè)節(jié)點(diǎn)根據(jù)對應(yīng)的臨時(shí)規(guī)則集在相應(yīng)屬性上的劃分，生成當(dāng)前節(jié)點(diǎn)的新值域。接著根據(jù)當(dāng)前規(guī)則集的各條規(guī)則分別生成各個(gè)新值域上的后繼狀態(tài)節(jié)點(diǎn)。葉子節(jié)點(diǎn)的規(guī)則集指針指向全部屬性匹配結(jié)束后最終匹配的規(guī)則集合。如上所示，全部規(guī)則經(jīng)過預(yù)處理，整體編譯成一棵自動(dòng)機(jī)匹配樹的內(nèi)部表示形式，從而支持高效的多查詢執(zhí)行。n 運(yùn)行自動(dòng)機(jī)對于每一個(gè)到來的元組，判斷哪些規(guī)則滿足的過程就是將元組的各個(gè)屬性上的值在生成于內(nèi)存中的自動(dòng)機(jī)上跑一遍的過程。由根節(jié)點(diǎn)開始，按自動(dòng)機(jī)屬性順序進(jìn)行每一層的匹配。如果在中間的某一層，

29、下一節(jié)點(diǎn)指針為空，說明沒有匹配規(guī)則。如果匹配到最后一層，則相應(yīng)規(guī)則集代表此元組所觸發(fā)的所有規(guī)則集。3.2.3. 復(fù)雜度分析n 時(shí)間復(fù)雜度：設(shè)|Q|=m,表示規(guī)則個(gè)數(shù)；|T|=n，表示規(guī)則的屬性共有n個(gè)。Qj (Ti) =true Qj (Ti)表示對第j條規(guī)則的第i個(gè)屬性域字段進(jìn)行匹配的布爾函數(shù)。則一條查詢規(guī)則j的執(zhí)行，表現(xiàn)為對待匹配數(shù)據(jù)的相應(yīng)字段i執(zhí)行匹配布爾函數(shù)Qj (Ti) =true，并將所有結(jié)果相與，取合取值。普通查詢算法中最差算法復(fù)雜度 O（規(guī)則個(gè)數(shù)m´字段個(gè)數(shù)n）。平均最優(yōu)判斷復(fù)雜度O（規(guī)則個(gè)數(shù)m´p）P為一個(gè)小于1的概率，由規(guī)則的分布與待匹配元組的分布決定。

30、多持續(xù)查詢優(yōu)化算法中速度和配置檢測規(guī)則個(gè)數(shù)m無關(guān)。對于匹配成功的元組，匹配時(shí)間是確定的，為log（pi)。pi為屬性i的新值域上的勢。匹配過程中，需要將原始值轉(zhuǎn)化為新值域上的值，通過二分查找，可以在log（pi)的時(shí)間內(nèi)完成。對于匹配不成功的元組，匹配過程會在自動(dòng)機(jī)的某一層打住，則可定義平均匹配復(fù)雜度為O(t)= O (j×(1 kt) 其中，kt為自動(dòng)機(jī)中第t層的過濾度，即均勻分布的元組值，經(jīng)過第t層的過濾后，剩下的元組數(shù)目占總數(shù)目的百分比。n 空間復(fù)雜度對于普通查詢算法，所有查詢只需在內(nèi)存中存儲一次，而順次執(zhí)行導(dǎo)致比較次數(shù)有冗余。優(yōu)化查詢算法存在規(guī)則的重復(fù)存儲，而比較次數(shù)卻大大減

31、少，相當(dāng)于是用空間換時(shí)間。優(yōu)化算法在自動(dòng)機(jī)轉(zhuǎn)化過程中，存在狀態(tài)數(shù)目指數(shù)增長的問題。為了防止空間復(fù)雜度過大，我們可以采取將規(guī)則分組，分別生成多棵匹配樹，從而使每棵樹的大小可控；還可以讓相同狀態(tài)共用指針，而不是以在內(nèi)存中再存儲一個(gè)拷貝的方式，來解決空間復(fù)雜度過大的問題。3.2.4. 優(yōu)化算法的改進(jìn)一旦規(guī)則集給定，屬性順序給定，生成的匹配自動(dòng)機(jī)就是確定的。到來的元組跑一遍自動(dòng)機(jī)，或者在中間的某層打住，表示沒有任何規(guī)則匹配，或者在最末一層停止，相應(yīng)的規(guī)則集表示匹配規(guī)則。元組所匹配的步數(shù)代表了自動(dòng)機(jī)的效率。匹配步數(shù)由到來的元組的分布情況以及匹配自動(dòng)機(jī)的形狀共同決定。假設(shè)到來的元組是均勻分布的，不考慮由元

32、組分布造成的對匹配效率的影響，則匹配自動(dòng)機(jī)的形狀就是決定效率的因素了。我們希望找到效率最高，即平均匹配步數(shù)最少的自動(dòng)機(jī)生成方法。已有研究顯示，達(dá)到全局最優(yōu)是NP hard（多項(xiàng)式時(shí)間難解）的問題7。我們只能通過一些啟發(fā)式方法，進(jìn)行局部優(yōu)化，改進(jìn)效率。我們從以下兩個(gè)方面考慮：n 屬性選擇度為了到來元組在匹配過程中能盡早打住，從而減少平均總比較次數(shù)，應(yīng)該將過濾度（Ki）高的屬性排在自動(dòng)機(jī)的前部。過濾度的度量沒有一個(gè)確定的算法，我們提出以下幾種可行的度量方法。a. 值域范圍百分比。Ki1（dij / di）/m，dij表示第j條規(guī)則中屬性i在新值域上的定義范圍， m表示規(guī)則總數(shù)目。di表示屬性i的新

33、值域范圍。1（dij / di）/m的值越大，表示經(jīng)過過濾后可能被排除的范圍越大，即過濾度越高。這里通過值域范圍反映過濾度大小。b. 信息熵。我們借鑒優(yōu)化決策樹生成理論，引入機(jī)器學(xué)習(xí)中的聚類（clustering）算法。算法從一個(gè)分類的有不同屬性的數(shù)據(jù)集合中生成決策樹。生成過程利用信息增益（information gain）的概念。數(shù)據(jù)的某個(gè)屬性的信息增益是將一個(gè)數(shù)據(jù)集劃分后熵（混亂，無序）的減少量。劃分后數(shù)據(jù)集的熵的度量是將每一個(gè)劃分集大小相對于原始數(shù)據(jù)集大小的比例作為權(quán)重累加。一個(gè)規(guī)則集合S的熵E通過如下公式計(jì)算 Es=-1/n log2(1/n)=log2(n)則一個(gè)規(guī)則集S在屬性A上的

34、信息增益通過如下公式計(jì)算 G(s,f)=Es-|Sv|/|S|*Esv= log2(|S|)-|Sv|/|S|* log2 (|Sv|)Sv代表對于規(guī)則集S,在屬性A上劃分之后生成的各個(gè)規(guī)則集合。|Sv|，|S|代表集合的數(shù)目。我們對原始規(guī)則集以及劃分后生成的多個(gè)規(guī)則集，計(jì)算各個(gè)屬性上的信息增益,選擇大的作為先匹配的屬性。這里通過信息增益來反映過濾度，實(shí)際上是認(rèn)為，劃分后分布越均勻的屬性有更大的區(qū)分度。c. 經(jīng)驗(yàn)判斷在實(shí)際的網(wǎng)絡(luò)安全監(jiān)控系統(tǒng)中，利用經(jīng)驗(yàn)來判定區(qū)分度與優(yōu)先順序是可行的。在包過濾步驟中，源、目的端口有較強(qiáng)的區(qū)分度，對這個(gè)屬性的過濾能較均勻地將規(guī)則集分類，應(yīng)該放在前面匹配。而ttl值

35、這個(gè)屬性的區(qū)分度相對較弱，應(yīng)該放在靠后的位置。我們可以根據(jù)經(jīng)驗(yàn)將各個(gè)屬性區(qū)分度排序，從而確定一個(gè)較優(yōu)的匹配順序。n 規(guī)則集分類將規(guī)則集預(yù)分類，相同類型的規(guī)則作為一個(gè)初始規(guī)則集。如TCP規(guī)則集，UDP User Datagram Protocol（用戶數(shù)據(jù)報(bào)協(xié)議）規(guī)則集，ICMP Internet Control Message Protocol（Internet控制信息協(xié)議）規(guī)則集等。這樣有兩個(gè)好處。一是每一個(gè)自動(dòng)機(jī)匹配樹的規(guī)則集不會太大，狀態(tài)數(shù)目可控，并且多棵樹可以并行運(yùn)行。二是相同類型的規(guī)則有類似的屬性字段，有些字段是某種規(guī)則集特有的，如ICMP的itype字段，在TCP規(guī)則集中就不需要考

36、慮。所以針對每一種類型的規(guī)則集生成相應(yīng)的自動(dòng)機(jī)，能夠減少自動(dòng)機(jī)匹配樹的層數(shù)，從而提高匹配效率。4. 性能測試為檢驗(yàn)IceNetwork處理引擎的功能與性能，我們設(shè)計(jì)如下測試方案測試環(huán)境：千兆交換機(jī)器網(wǎng)絡(luò)發(fā)包機(jī)：AMD Opterontm1421。60Ghz 64bit入侵檢測服務(wù)器Xeon（tm) 2*CPU 2.0GHz 3.87G內(nèi)存圖6 測試網(wǎng)絡(luò)結(jié)構(gòu)圖測試說明：入侵檢測系統(tǒng)包括Snort 和IceNetwork;發(fā)包機(jī)器，可以按照指定的速度發(fā)送全部是攻擊數(shù)據(jù)的網(wǎng)絡(luò)數(shù)據(jù)包。發(fā)送包間隔中插入特定Sleep(0)進(jìn)行時(shí)間延時(shí)。攻擊包的構(gòu)造是通過依照Snort規(guī)則構(gòu)造的。 測試丟包率結(jié)果如下：在純攻擊包流量壓力較小時(shí)，兩者均有較好的處理效率。當(dāng)流量壓力加大時(shí)，Snort丟包率明顯增大，而IceNetwork顯示出較好的檢測引擎執(zhí)行效率與抗壓能力。實(shí)驗(yàn)表明，這種基于數(shù)據(jù)流管理平臺進(jìn)行網(wǎng)絡(luò)安全事件監(jiān)控的設(shè)計(jì)思路是正確可行的。系統(tǒng)能夠完成設(shè)計(jì)功能，并獲得了較好的性能。圖7 丟包率對比圖5. 結(jié)論和展望本文將數(shù)據(jù)流模型引入系統(tǒng)