一種快速的防火墻規(guī)則沖突檢測算法

摘要：針對目前常用的沖突檢測算法效率低下這一實際情況，提出了一種高效的沖突檢測算法FRCD。該算法為每一維規(guī)則分量構(gòu)造兩棵二叉樹，使得檢測速度大大加快。實驗表明，其檢測速度快于常見算法。

關(guān)鍵詞：防火墻; 規(guī)則沖突； 沖突檢測

中圖分類號：TP393．08文獻標志碼：A

文章編號：1001－3695(2008)01－0266－02

近年來，防火墻規(guī)則數(shù)目不斷增多，大型企業(yè)級防火墻通常包含有幾百條甚至上千條規(guī)則。面對如此數(shù)量眾多的規(guī)則，管理員即使只完成一些最基本的任務(wù)，諸如弄清每條規(guī)則的含義以及規(guī)則間的關(guān)系，也不是一件輕松的事情。當(dāng)添加規(guī)則時，新規(guī)則往往會與某些已有規(guī)則相沖突。而這種沖突可能會造成潛在的安全漏洞。下面以一個例子加以說明。

假設(shè)規(guī)則集中包含有一條規(guī)則R，允許IP地址在192.168.*.*中的節(jié)點訪問FTP服務(wù)器?，F(xiàn)在需要添加一條規(guī)則，禁止IP地址在192.168.10.*中的節(jié)點訪問FTP服務(wù)器。由于規(guī)則數(shù)目眾多，管理員沒有察覺到這兩條規(guī)則是相沖突的，錯誤地給新規(guī)則賦予了一個較低的優(yōu)先級，造成IP地址在192.168.10.*中的節(jié)點依然可以訪問FTP服務(wù)器。從這個例子可以看出，漏洞產(chǎn)生的原因是管理員給新規(guī)則賦予了一個不恰當(dāng)?shù)膬?yōu)先級。而這又是由于管理員忽視了那些與新規(guī)則相沖突的規(guī)則所造成的。在大規(guī)模規(guī)則集中，這種情況更為突出。要避免此類漏洞的出現(xiàn)，在添加規(guī)則時需要找出與新規(guī)則相沖突的所有規(guī)則，即進行沖突檢測。

雖然防火墻技術(shù)受到了廣泛的關(guān)注，但是人們將大量的精力投入到了諸如包過濾、狀態(tài)包檢測、深度包檢測、分

布式防火墻以及防火墻吞吐率等方面的研究上。目前，只有少量的研究針對規(guī)則集沖突檢測。

文獻[1]提出了一種沖突檢測算法。該檢測算法主要針對二維規(guī)則，且規(guī)則分量以前綴形式表示，其算法時間復(fù)雜度為O(w2)（w為域長）。對于高維規(guī)則而言，算法對某些規(guī)則分量進行了限制，如端口號被限制為一個確定值或通配符。顯然，這種處理方式并不通用。

文獻[2]提出了一種快速的沖突檢測算法SBV（s bit vector）。該算法能處理高維規(guī)則，但規(guī)則分量要求以前綴形式表示。SBV利用文獻[3]介紹的位向量技術(shù)，為每一維規(guī)則分量構(gòu)建了一棵二叉樹。在每一維分量的處理過程中需要進行多次位向量運算。

文獻[4~6]研究了規(guī)則沖突的幾種形式，并對沖突進行了詳細的分類，介紹了一種十分簡單的沖突檢測算法。

通過分析現(xiàn)有的沖突檢測算法，以及筆者統(tǒng)計的24個企業(yè)級防火墻和95個個人防火墻規(guī)則集，提出了一種高效的沖突檢測算法FRCD(firewall rules conflicts detecting)。FRCD同文獻[2]提出的沖突檢測算法SBV，均采用了文獻[3]介紹的位向量技術(shù)。所不同的是，在每一維分量的處理過程中，F(xiàn)RCD只需要進行一次位向量交集運算，而SBV需要進行多次位向量并集運算。另外，SBV只能處理以前綴形式表示的規(guī)則分量，而FRCD能處理以范圍表示的規(guī)則分量。雖然范圍表示可以轉(zhuǎn)換為前綴表示，但這會大量增加規(guī)則數(shù)目。FRCD算法時間復(fù)雜度為O(log n+n/f)。其中：n為規(guī)則數(shù)目； f為機器字長。實驗表明其檢測速度快于SBV算法。

1沖突的定義

1．1規(guī)則間的關(guān)系

對于規(guī)則數(shù)小于100條的規(guī)則集，SBV比文獻[4]算法快5~10倍，F(xiàn)RCD比文獻[4]算法快6~12倍，F(xiàn)RCD略快于SBV；規(guī)則數(shù)多于100條的規(guī)則集，SBV比文獻[4]算法快20倍左右，F(xiàn)RCD比文獻[4]算法快60~80倍，F(xiàn)RCD比SBV快3~4倍，并且隨著規(guī)則數(shù)目增多，F(xiàn)RCD算法優(yōu)勢更為明顯。在內(nèi)存消耗方面，F(xiàn)RCD使用量最大，但對于包含有500條規(guī)則的規(guī)則集，實際使用內(nèi)存800 KB左右。顯然，對于一般的個人計算機而言也是微不足道的。

4結(jié)束語

本文通過分析規(guī)則沖突可能帶來的安全漏洞，以及現(xiàn)有的沖突檢測算法，提出了一種規(guī)則集沖突檢測算法

FRCD。FRCD采用分治思想，在每一維處理過程中，只需進行一次位向量交集運算，使得檢測速度大大加快。當(dāng)然，在規(guī)則集沖突檢測方面，還有許多方面需要繼續(xù)研究，諸如分布式防火墻規(guī)則集沖突檢測、化解，規(guī)則沖突在入侵檢測與防火墻聯(lián)動系統(tǒng)中的化解等。

參考文獻：

［1]HARI A， SURI S，PARUIKAR G. Detecting and resolving packet filter conflicts[C]//Proc of Policy 2001 Workshop.Tel Aviv:IEEE Press， 2000：1203 1212.

［2]BABOESCU F，VARGHESE G.Fast and scalable conflict detection for packet classifiers[J].Computer Networks，2003，42(6):717－735.

［3]BABOESCU F，VARGHESE G.Scalable packetclassification [C]//Proc of ACM SIGCOMM.New York:ACM Press， 2001:199－210.

［4]Al SHARE E， HAMED H.Design andimplementation of firewall policy advisor tools， CTI techrep0801[R]. [S.l.]:School of Computer Science Telecommunications and Information Systems， DePaul University，2002.

［5]Al SHARE E，HAMED H.Firewallpolicy advisorfor anomaly detection and rule editing[J]. IEEE/IFIP Integrated Management， 2003，41(8):17－30.

［6]Al SHARE E，HAMED H.Taxonomyofconflictsin network security policies[J]. IEEE Communications Magazine， 2006，44(3):134 141.

［7]GUPTA P， McKEOWN N. Algorithmsforpacket classification[J]. IEEE Network， 2001，15(2):24－32.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”