針對規則更新操作的測試數據包選取算法

(電子科技大學 計算機科學與工程學院 成都 610054)

摘 要：防火墻規則集中存在的配置錯誤主要來源于規則的添加、刪除等更新操作。因此進行規則更新時，需要使用測試算法判斷更新操作的正確性。現有的測試算法僅從被添加或被刪除規則的頂點選取測試數據包，不能檢測出所有因規則沖突而導致的配置錯誤。基于此，提出了一種針對規則更新操作的測試數據包選取算法PCRU。該算法從兩處選取測試數據包，即被添加或者被刪除的規則的頂點和規則沖突區域。理論分析和仿真實驗表明，與現有測試算法相比，在進行規則更新時，PCRU算法只需使用少量的測試數據包，即可檢測出所有因規則沖突而導致的配置錯誤。

關鍵詞：規則沖突；規則更新操作；測試數據包；防火墻；正確性

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

文章編號：1001-3695(2009)05-1919-03

Test packetchoosing algorithm for rules updating

LI Lin LU Xianliang NIE Xiaowen XU Haimei PU Xun PENG Yongxiang

(School of Computer Science Engineering，University of Electronic Science Technology of China Chengdu 610054 China)

Abstract:The deployment errors in firewall rule sets mainly come from rules updating. And hence test algorithms should be employed to verify the correctness of updating when rules are added or deleted. Current test algorithms only choose test packets from apexes of added or deleted rules which cannot detect deployment errors caused by rule conflicts. This paper proposed a test packetchoosing algorithm for rules updating which was named packet choosing rule updating (PCRU).PCRU chose test packets from the apexes of rules and from conflicting areas. The results of simulations show that PCRU can detect the deployment errors caused by rule conflicts when rule updating at the cost of a small number of test packets.

Key words:rule conflicts; rule updating; test packets; firewall; correctness

0 引言

近年來，隨著防火墻規則數目的不斷增多，有效地管理這些規則變得越來越困難。大型企業級防火墻通常包含有數百條規則，而在這類規則集中，往往都存在不少沖突規則。面對這樣的規則集，管理員即使只完成一些最基本的任務，如弄清每條規則的含義以及規則間的關系，也不是一件輕松的事情。因此在這種情況下，當進行規則添加、刪除等更新操作時，很容易導致規則配置錯誤。下面通過一個例子來加以說明。

假設某二維規則集中包含有一條規則Ri：禁止192.168.2.55~192.168.2.160中的節點訪問192.168.10.97~192.168.10.189中的節點。現在管理員需要添加一條規則Rj，使得192.168.2.10~192.168.2.230中的節點能夠訪問192.168.10.130~192.168.10.150中的節點。在添加規則的過程中，由于規則眾多，管理員沒有注意到Ri和Rj是相沖突的，錯誤地給Rj賦予了一個較低的優先級，從而使得192.168.2.55~192.168.2.160中的節點依然不能訪問192.168.10.130~192.168.10.150中的節點。

從上述例子可以看出，在進行規則更新時，很有可能出現因規則沖突而導致的配置錯誤。因此需要使用測試算法，判斷更新操作的正確性。更新操作的正確性是指規則更新后的規則集，符合管理員的配置意圖。目前，常見的測試方法是：首先按照某種算法選取測試數據包，并由管理員提供，更新操作后的這些數據包的預期處理動作，即放行或者丟棄；進行完更新操作后，再使用報文分類模擬器，對上述測試數據包進行處理，并記錄每個數據包的處理動作；最后將上述記錄結果，與事先由管理員輸入的預期結果進行比對。若發現兩者不一致，即說明存在規則配置錯誤。從上述測試方法可以看出，如何選取測試數據包，即如何設計測試數據包選取算法，是一個關鍵點。而現階段有關更新操作正確性的研究也集中于此。

目前，有關防火墻測試方面的研究，主要集中在功能測試、性能測試、抗攻擊能力測試等方面，只有少量的研究針對規則更新操作正確性測試。

在防火墻測試方面的研究工作中，文獻[1]對各類防火墻測試方法進行了分析比較，指出了各自的應用環境以及優缺點；并給出了一種針對規則更新操作的測試數據包選取算法。該算法僅從被添加或被刪除的規則的頂點選擇數據包。

文獻[2]設計了一種模擬防火墻以及網絡環境的工具。該工具能自動生成針對一系列安全漏洞的測試用例。

文獻[3]設計了一種分析工具來模擬防火墻的行為模式。該工具有利于管理員及早發現配置錯誤，但并不能找出所有因規則沖突而帶來的配置錯誤。

文獻[4]分析了分布式系統中，防火墻安全性與性能之間的關系，并提出了一些防火墻性能測試和安全性測試的方法。

文獻[5]提出了一種基于數據流的防火墻漏洞分析框架。該框架對防火墻漏洞進行了分類，并據此提出了不同的抗攻擊能力測試方法。

文獻[6]提出了一種針對防火墻漏洞的測試方法。該方法使用兩類測試用例，即自動生成和手工添加。

從以上討論可知，在規則更新操作正確性測試方面，以文獻[1]算法為代表的現有測試數據包選取算法，僅從被添加或被刪除的規則的頂點選擇數據包，從而導致其不能檢測出因規則沖突而引起的配置錯誤。由此可見，有必要研究能夠檢測出這類配置錯誤的測試數據包選取算法。

本文從計算幾何的角度對規則、規則沖突進行了分析，然后在此基礎之上，提出了一種針對規則更新操作的測試數據包選取算法PCRU。理論分析和仿真實驗表明，與現有檢測算法相比，在進行規則更新時，PCRU算法只需使用少量的測試數據包，即可檢測出因規則沖突而導致的配置錯誤。

1 規則沖突的定義

本文所討論的規則集，是一個包含有n條規則的m維規則集，記為I。

定義1 規則Ri定義為Ri={Ti1，Ti2，…，Tik，…，Tim}，1≤k≤m。其中：Tik=[TSik，TEik]，即Tik={x|TSik≤x≤TEik，TSik，x，TEik∈N，N為非負整數集。規則優先級定義為pri(Ri)，處理動作定義為act(Ri)。

定義2 一個數據包P，其對應的m維分量為T(P)={tP1，tP2，…，tPk，…，tPm}。其中：tPk∈N，1≤k≤m。Ri，對于j（1≤j≤m），均使得tPj∈Tij，則稱數據包P匹配規則Ri，記為P∈Ri，否則稱P不匹配規則Ri，記為PRi。P的處理動作記為A(P)。

定義3 數據包P和規則Ri、Rj。若P∈Ri，P∈Rj，且act(Ri)≠act(Rj)，則稱Ri和Rj沖突，記為Ri∫Rj。

定義4 數據包P和規則集合match(P)，Rp∈match(P)，均有P∈Rp，而Rqmatch(P)，Rq∈I，均有PRq，則稱match(P)是P的匹配集合。A(P)=act(Rr)，Rr∈match(P)且Rr是match(P)中優先級最高的規則。

從定義1可知，規則分量Tik在數軸上相當于一條線段，規則Ri在m維空間中相當于一個超長方形。下面從計算幾何角度分析規則沖突。

定義5 數軸上兩條線段Tik和Tjk。

若Tik和Tjk不相交，即TEik＜TSjk或TE

2 PCRU算法

PCRU算法的任務是在進行規則更新時，選擇合適的測試數據包，以檢測出因規則沖突而導致的配置錯誤。當需要添加或者刪除規則Ri時，PCRU算法的執行步驟如下：a)從Ri的頂點選取測試數據包；b)進行規則沖突檢測，找出規則集中與Ri相沖突的規則；c)從這些與Ri相沖突的規則中選取測試數據包。下面分別按照這三個步驟進行討論。

首先分析a)，即從Ri的頂點選取測試數據包。在該步驟中，數據包的選取基于單規則映射，即定義9。

定義7 L是數軸上以非負整數為端點的線段組成的集合。l∈L，l=[lS，lE]。其中：lS，lE∈N，lS表示l的左端點；lE表示l的右端點。映射g:L→N定義如下：g(l)=lS；映射h:L→N定義為h(l)=lE。

定義8 Ri，映射gk:I→N定義為gk(Ri)=g(Tik)，映射hk:I→N定義為hk(Ri)=h(Tik)，1≤k≤m。

定義9 單規則映射D:I→2M。其中：M是m維空間中坐標分量均為非負整數的所有點組成的集合，2M是M的冪集。Ri，D(Ri)={mk=1gk(Ri)，mk=1hk(Ri)}。其中：為笛卡兒積，1≤k≤m。

從定義9可知，D(Ri)中包含了兩個數據包，即mk=1gk(Ri)和mk=1hk(Ri)。這兩個數據包實際上是Ri的一條對角線上的兩個頂點。PCRU算法從Ri的頂點選取的數據包就是D(Ri)中的數據包。之所以選擇D(Ri)中的數據包，是為了測試Ri本身是否符合管理員的配置意圖。下面分析選擇D(Ri)中的數據包的正確性，即定理2。

定理2 通過D(Ri)中的數據包，能確定Ri的每個分量值。

證明 根據定義9可設，數據包P1和P2屬于D(Ri)。令T(P1)={g1(Ri)，g2(Ri)，…，gm(Ri)}。所以

T(P1)={g1(Ti1)，g2(Ti2)，…，gm(Tim)}

T(P1)={TSi1，TSi2，…，TSim}

同理，可得T(P2)={TEi1，TEi2，…，TEim}。

顯然，從T(P1)和T(P2)能夠獲得Ri的每個分量值。

命題成立。

從定理2易知，通過測試D(Ri)中的數據包，能夠判斷Ri本身是否符合管理員的配置意圖。下面討論PCRU算法的步驟b)和c)。

當需要添加或刪除規則Ri時，PCRU算法使用最簡單的順序檢測算法，查找與Ri相沖突的所有規則。針對每一個沖突規則對，PCRU算法按照關鍵數據包選取映射，選取測試數據包。下面就討論關鍵數據包選取映射，即定義12。

定義10 映射f:L×L→N。l1，l2∈L，映射f定義如下：

包就是PCRU算法在第三個步驟中需要獲取的測試數據包。通過這個測試數據包，能夠確定沖突規則之間的優先級關系。下面對這一結論進行證明。

定理3 從以上討論易證，不再贅述。

實際上定理3說明了根據K(Ri，Rj)能確定規則的優先級關系，即在添加或刪除規則時，PCRU算法選取的測試數據包考慮了規則沖突，并能找出因規則沖突而導致的配置錯誤。

3 算法分析與測試

從上述定義和定理易知，PCRU算法選取的測試數據包在進行規則更新時，能夠檢測出因規則沖突而導致的配置錯誤，即PCRU算法是正確的。

當添加或刪除規則Ri時，PCRU算法會從D(Ri)和K(Ri，Rj)中選取測試數據包，其中，Rj，Ri∫Rj。從D(Ri)中選取的測試數據包個數為2。從K(Ri，Rj)中選取的測試數據包個數為1。當添加規則時，最壞情況下，新規則會與n條規則沖突，即PCRU算法最多可選取n+2個測試數據包；當刪除規則時，最壞情況下，被刪規則會與n-1條規則沖突，即PCRU算法最多可選取n+1個測試數據包。因此，PCRU算法最壞情況下的空間復雜度為O(n)。測試數據包選取算法都是非在線運行，因此不關心其時間性能。本文略去這方面的討論。下面從PCRU算法正確性，以及測試數據包個數進行測試分析。

測試環境：AMD 1.6 GHz，448 MB內存，Windows XP，使用C++語言實現PCRU算法和文獻[1]算法。測試所用的三個規則集來自于本文統計的商業防火墻。測試項目如下：

a）PCRU算法與文獻[1]算法的對比測試。測試方法：隨機地從規則集中刪除一條規則，或者隨機地生成一條規則添加到規則集中，并使用PCRU算法和文獻[1]算法選取測試數據包；利用報文分類模擬器記錄測試數據包的處理動作，管理員提供測試數據包的預期處理動作。進行測試時，需要使得更新操作后得到的規則集不符合管理員配置意圖，即要求至少有一個測試數據包的處理動作與管理員預期的處理動作不一致。按照上述測試方法，進行10次實驗。

測試結果如下：有六次實驗，文獻[1]算法產生的測試數據包的處理動作，與其預期的處理動作完全一致；沒有一次PCRU算法產生的測試數據包的處理動作，與其預期的處理動作完全一致。即說明，在進行規則更新時，PCRU算法能夠檢測出規則沖突導致的配置錯誤。

b）PCRU算法測試數據包個數。測試方法：隨機地從規則集中刪除一條規則，或者隨機地生成一條規則添加到規則集中，使用PCRU算法選取測試數據包，并記錄其個數。按照上述測試方法進行1 000次實驗，計算測試數據包的平均個數。

從表1可以看出，PCRU算法選取的測試數據包的個數很少，與其理論最大值n+2相差很大。例如，當在Fw2中添加或刪除規則時，其測試數據包的平均個數才為8，而其理論最大值應為n+2=795。造成這種情況的主要原因在于，在實際的規則集中，一條規則通常至多與數條或數十條規則相沖突^[8]。例如，在Fw1中，至多與19條規則相沖突；在Fw2中，至多與15條規則相沖突；在Fw3中，至多與19條規則相沖突。

根據以上討論可知，在進行規則更新時，PCRU算法只需使用少量的測試數據包，即可檢測出因規則沖突而導致的配置錯誤。

4 結束語

本文從計算幾何的角度對規則沖突進行了分析，并在此基礎之上，提出了一種針對規則更新操作的測試數據包選取算法PCRU。該算法不僅從被添加或被刪除的規則的頂點選取測試數據包，而且還從規則沖突區域選取測試數據包。理論分析和仿真實驗表明，與現有檢測算法相比，在進行規則更新時，PCRU算法只需使用少量的測試數據包，即可檢測出因規則沖突而導致的配置錯誤。

參考文獻：

［1］ALLEN J.The CERT guide to system and network security practices[M].New York:AddisonWesley，2001:1200.

[2]JURJENS J，WIMMEL G.Specificationbased testing of firewalls[C]//Proc of the 4th International Conference on Perspectives of System Informatics.Washington DC:IEEE Press，2001:308316.

[3]WOOL A，MAYER A，ZISKIND E.A firewall analysis engine[C]//Proc of IEEE Symposium on Security and Privacy.Chicago:IEEE Press，2000:8597.

[4]LYU M，LAU L.Firewall security:policies，testing and performance evaluation[C]//Proc of International Conference on Computer Systems and Applications.New York:IEEE Press，2000:116121.

[5]SCHULTZ E，FRANTZEN M，KERSCHBAUM F.A framework for understanding vulnerabilities in firewalls using a dataflow model of firewall internals[J].Computers and Security，2001，20(3):263270.

[6]TAWIL K ，KALTHAM I A.Evaluation and testing of Internet firewalls[J].International Journal of Network Management，2002，9(3):135149.

[7]田原，云曉春，朱曉輝.防火墻性能基準測試研究[J].計算機仿真，2003，20（7）：123126.

[8]DVID E T，JONATHAN S T.ClassBench:a packet classification benchmark[J].IEEE Trans on Networking，2007，15(3): 499511.