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

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

關鍵詞：防火墻; 規則沖突； 沖突檢測

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

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

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

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

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

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

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

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

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

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

1沖突的定義

1．1規則間的關系

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

4結束語

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

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

參考文獻：

［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.

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