基于RPC模型的訪問控制策略壓縮算法

程玉柱　易月娥

(長沙民政職業技術學院軟件學院　湖南 長沙 410004)

?

基于RPC模型的訪問控制策略壓縮算法

程玉柱易月娥

(長沙民政職業技術學院軟件學院湖南 長沙 410004)

摘要訪問控制列表(ACL)提供了對網絡設備接口的一種基本訪問控制，是維護網絡系統安全的重要手段之一。隨著網絡應用的日益增多，ACL條目也隨之增加，使得管理ACL更加困難，降低了網絡設備的轉發性能。因此對ACL進行壓縮顯得尤為重要，但該問題已被證明是NP難。針對ACL壓縮問題，提出基于矩陣映射和構建獨立單元空間集的方法，將其轉換為直線多邊形的矩形覆蓋問題。分析表明該問題的求解近似度可以突破O(logn)，為ACL壓縮問題的求解提供了新的思路。

關鍵詞訪問控制列表網絡安全規則壓縮RPC矩形覆蓋

AN ALGORITHM OF ACCESS CONTROL POLICY COMPRESSION BASED ON RPC MODEL

Cheng YuzhuYi Yuee

(Software Department,Changsha Social Work College,Changsha 410004,Hunan,China)

AbstractAccess control list (ACL) provides a basic access control on network device interfaces, and is one of the important means to maintain the security of network systems. However, ACL items have been growing along with the increase of network applications, while increasing the difficulty in ACL management, this also degrades the forwarding performance of network devices as well. Therefore to compress ACL is particularly important, but this problem has been proved to be NP-hard. Aiming at ACL compression problem, the paper proposes an approach based on mapping matrix and constructing independent unit space set to transform the problem into a problem of rectilinear polygon rectangle cover. Analysis shows that the approximation degree of the solution to the problem can break O (logn), this offers a new thought for solving ACL compression problem.

KeywordsACLNetwork securityRule compressionRectilinear polygon cover (RPC)Rectangle cover

0引言

隨著人們對網絡依賴程度的日益增強，網絡安全性愈發重要，路由器作為網絡傳輸過程中的重要設備，對報文安全、正確和快速的轉發起著關鍵作用。在路由器上配置訪問控制列表ACL[1]，通過訪問規則控制和過濾經過路由器的數據流，防止外部用戶對內部網絡不安全的訪問。訪問控制列表由源地址、目的地址、端口號等一系列特定指示條件組成，其采用自上而下的執行順序，當數據包到達時，路由器會遍歷ACL內所有規則，直至找到第一條匹配數據包的規則，并執行該規則所定義的操作(拒絕或允許)。在高速網絡環境中，會引入一種特殊的硬件機制(TCAMs)[2]來對遍歷并行處理以加快數據包轉發速度，但TCAM內存受限且價格昂貴，因此需要考慮如何盡可能地壓縮ACL內規則條數以優化TCAM的存儲結構[3]。此外，當ACL內規則條數達到一定數量時，對ACL進行編輯和管理會變得非常繁瑣而且容易出錯，甚至由此帶來災難性的后果[6]。因此，有必要在保持ACL語義不變的前提下，對ACL進行盡可能的壓縮。不失一般性，本文研究只包含源地址和目標地址的二維ACL壓縮問題。

1理論基礎

一般而言，ACL內任意規則可以表示為形如“F1∈D(F1)(F2∈D(F2)→decision”的形式，這里Fi(1≤i≤2)分別表示源地址和目標地址，D(Fi)表示對應的域值區間，decision表示規則的決策(接受或拒絕)。根據文獻[8]中規則空間的定義，可進一步將ACL規則表示為R[(l1,l2)(d1,d2):0] (如果 =discard)) 或者R[(l1,l2)(d1,d2):1] (如果 =accept), 這里 li是 D(Fi)的下界，而di代表D(Fi)的大小。下面正式給出本文算法所涉及的一些概念定義。

定義1針對域(F1,F2)的映射矩陣M2滿足以下幾點要求：

(1) M2是一個二維矩陣，各維坐標用Fi表示，相應坐標區間為[0, D(Fi)], 1≤i≤2。

(2) M2由一系列單元矩陣組成，每個單元矩陣可用其下界坐標及相應坐標區間表示:[(l1,l2)(d1,d2)]。

(3) 任一具有形如→的ACL規則可在M2中表示，即每一條規則的前綴可以用M2中的一個單元矩陣來表示，而單元矩陣的值則可以用來表示規則的決策:value=0 (如 =discard ),或value =1 (如=accept)。

(4) 一個包含有m個互為獨立的單元矩陣的二維矩陣M2可以形式化描述為:

這m個獨立單元矩陣在M2內互不相交，我們把這些獨立單元矩陣稱作單元空間。

定理1任意原始ACL規則，采用FDM構建算法[8]，在矩陣M2內按逆序依次映射后，可得到一串語義與原始ACL規則完全相同的單元空間。

證明：因為ACL規則遵循首次匹配優先原則，即數據包會執行最先匹配規則的決策。根據算法過程，原始規則按逆序逐條映射到二維矩陣之中，并根據規則各維域值范圍及對應決策對相應單元空間進行賦值。因為自后而前的映射過程保證了規則的首次優先匹配，同時單元空間與規則域值范圍保證了完全一致。因此，可知原始ACL規則采用FDM構建算法在二維矩陣內映射后，規則語義保持不變。得證。

定理2任意兩個單元空間Ui和Uj在某一個維度上的坐標關系R(Ui,Uj)=r有且只屬于{左相鄰、右相鄰、左相交、右相交、分離、覆蓋、包含、相等}之一，分別表示為{╜,╙ ,┤,├,║,>,<,≡}。本定理證明略。

我們定義兩個單元空間的空間關系為各個維度上的坐標關系的組合。當兩個單元空間的空間關系中，有一個“║”或者同時有兩個“╜或╙”，則定義對應的兩個單元空間的空間關系為“分離”。我們可以把任一單元空間看作無向連通圖中的一個點，兩單元空間不互為分離則表示其對應圖中的兩點之間有邊相連，類似求獨立連通子圖，我們把映射后得到的單元空間劃分為若干獨立的單元空間集。每個獨立單元空間集正好可以構成一個二維直線多邊形，由定義1可知多邊形內各單元空間的值均為1，若幾個單元空間圍成一個圈，而圈內區域值為0，則把這些值為0的區域稱作“洞”[4]。

2基于RPC問題模型的ACL壓縮算法

我們首先用FDM構建算法[8]將原始ACL規則映射成一系列單元空間，然后基于各單元空間的空間關系將它們劃分為若干獨立單元空間集，每個獨立單元空間集正好可以構成一個直線多邊形。從幾何學觀點看，此時ACL壓縮問題等價于如何用最少的矩形去覆蓋該直線多邊形，即RPC問題。下面，我們舉一個例子來詳細說明方法步驟。設原始ACL包含9條規則，如圖1所示。

圖1　原始ACL規則示例

步驟1將ACL規則映射到二維矩陣M2

將規則ri映射到二維矩陣M2的詳細算法可參考文獻[8]，圖2為該算法過程示例。設有兩條規則r1: F1∈[4,5]∧F2∈[4,6]→discard, r2: F1∈[1,7]∧F2∈[2,8]→accept，圖2(a)為規則r2映射后的結果。這里(1,r2)表示規則r2的決策為接受，類似地，圖2(b)內(0,r1)表示規則r1的決策為拒絕。因為r1的決策是拒絕且r1的規則空間被包含在r2映射后的單元空間內，首先將單元空間 [(1,2)(7,7)]在F1維上切分成三部分，{[(1,2)(3,7)], [(4,2)(2,7)], [(6,2)(2,7)]}，而在F2維上保持不變，然后繼續將 [(4,2)(2,7)]在F2維上進行切分為三部分:{[(4,2)(2,2)], [(4,4)(2,3)], [(4,7)(2,2)]}，因為[(4,4)(2,3)]與r1的規則空間一樣，將其移除，從而得到最終的四個單元空間{[(1,2)(3,7)],[(4,2)(2,2)], [(4,7)(2,2)], [(6,2)(2,7)]}。

圖2　映射示例:r1:F1∈[4,5]∧F2∈[4,6]→discard, r2: F1∈[1,7]∧F2∈[2,8] →accept

以圖1所示的原始ACL為輸入，通過映射過程，可以得到六個單元空間格，最后的FDM為{[(0,4)(3,4)],[(2,2)(1,2)],[(3,2)(1,3)],[(5,5)(2,3)],[(7,2)(2,8)],[(9,5) (1,3)]}，如圖3所示。

圖3　規則映射后結果示例

步驟2求獨立子集

該方法第一步需要判斷任意兩單元空間之間的空間關系(具體判定過程見算法1)，可得到對應的空間關系矩陣M，圖4展示了圖3各單元空間之間的空間關系矩陣。對M內每一個矩陣元素，當存在一個“║”或有兩個“╜或╙”時，對應的兩單元空間可以定義為“分離”。我們把任一單元空間看作無向連通圖中的一個點，兩單元空間不互為分離則表示其對應圖中的兩點之間有邊相連，類似求獨立連通子圖方法[12]，可以容易地求得獨立單元空間集S1和S2：

S1={[(0,4)(3,4)],[(2,2)(1,2)],[(3,2)(2,3)]}

S2={[(5,5)(2,3)],[(7,2)(2,8)],[(9,5)(1,3)]}

圖4　空間關系矩陣示例

算法1構建空間關系矩陣

輸入:包含n個單元空間的單元空間集UNs

輸出:空間關系矩陣M，矩陣元素為任意兩單元空間的空間關系

Begin

Steps:

1. 對單元空間集坐標遞增順序進行排序(U1~ Un);

2. for i:=1 to n

for j:=1 to n do

if i==j then do M[i][j]=?;

else do M[i][j]=Relation(Ui,Uj);

End

Relation(Ui,Uj){

/*設Ui=(l1(i),l2(i))(d1(i),d2(i)),Uj=(l1(j),l2(j))(d1(j),d2(j)), t代表維度，在任一維，如Ui坐標小于Uj, 且兩者相鄰或相交，則稱兩單元空間在該維度上為左相鄰或左相交。反之類似定義*/

for t:=1 to 2 do

if (lt(i)+dt(i)lt(j)+dt(j)) then R[t][i][j]=║;

if (lt(i)+dt(i)=lt(j)‖lt(i)=lt(j)+dt(j))

then R[t][i][j]=╜‖R[t][i][j]=╙;

if (lt(i)

then R[t][i][j]=┤‖├;

if (lt(j)

then R[t][i][j]=<‖> ;

if (lt(i)=lt(j)&dt(i)=dt(j)) then R[t][i][j]=≡;

} // End of Relation(Ui,Uj)

步驟3直線多邊形的矩形覆蓋

每個獨立單元空間集正好可以構成一個直線多邊形，從幾何學觀點看，此時ACL壓縮問題等價于RPC問題?？紤]一般情況，該直線多邊形可能含有“洞”。

根據算法2，對獨立子集S1和S2分別進行處理，得覆蓋S1的矩形{[(0,4)(3,4)],[(2,2)(2,3)]},覆蓋S2的矩形{[(5,5)(5,3)],[(7,2)(2,8)]}。最后根據文獻[8]內的規則生成算法，可得壓縮后的ACL規則為：

r1:F1∈[7,8]∧F2∈[2,9]→accept

r2:F1∈[5,9]∧F2∈[5,7]→accept

r3:F1∈[0,2]∧F2∈[4,7]→accept

r4:F1∈[2,3]∧F2∈[2,4]→accept

r5:F1∈[0,9]∧F2∈[0,9]→discard

算法2Covering Rectilinear Polygons with Rectangles

Input: A 2-dimensional rectilinear polygon P with n vertices

Output: m rectangles which can cover the whole P

Begin

Steps:

1. A sequence of consecutive vertically aligned non-hole cells bounded by a hole on the top and the bottom constitutes a strip;

2. For each strip, put the unique associated rectangle whose height just covers the strip and whose width is as large as possible;

End

3理論分析與仿真結果

定理3兩個在空間上互為獨立的單元空間，其所對應的規則集也互為獨立。即求整個單元空間的最少矩形覆蓋等價于求各獨立單元空間集的最少矩形覆蓋的組合。

證明：采用反證法，設兩個獨立的單元空間集，所對應的規則集不互為獨立，即存在兩條規則(記為ra和rb)分別屬于不同的單元空間集，但兩規則互為包含或者相交，即等價于存在某個區間，同時屬于ra和rb，但根據我們的FDM構建算法，此即意味著存在某個單元空間，同時屬于兩個不同的單元空間集，這與兩單元空間集互為獨立相矛盾。得證。

定理4二維ACL規則通過矩陣映射[8]后的壓縮問題求解近似度可以突破O(logn)。

1) 基于各單元空間相互之間的空間關系，可以將全部的單元空間劃分到各獨立單元空間子集。

2) 各單元空間子集內值為1的單元空間通過鄰接關系連在一起，可以構成一個多邊形，該多邊形內部可能有值為0的單元空間，其可以看作多邊形的洞。

3) 如果能用最少的矩形覆蓋該多邊形，即相當于對這些單元空間進行最大程度地壓縮，問題模型與RPC相同。故得證。

實驗分別選取實際ACL規則和合成規則進行測試，我們選取了一個53條規則的實際ACL，此外用Classbench[13]自動生成了十個合成規則，規則條數分別從14至200條。任意ACL規則前綴均有且只包含源和目標IP地址兩個域。采用文獻[8]中的FDM方法和本文提出的RPC方法分別對各規則進行壓縮，得到的壓縮結果如圖5所示。

圖5　RPC與FDM方法壓縮比較

可以看到，RPC方法相比FDM方法而言，在壓縮率上更優，這個結果不難理解，因為FDM方法相當于圖6(a)所示的MNC問題(Minimal Nonoverlapping Cover)而RPC方法相當于圖6(b)所示的MOC(Minimal Overlapping Cover)問題[11]。

圖6　直線多邊形的矩形覆蓋示意圖

4結語

隨著網絡的飛速發展，ACL在網絡安全、網絡優化等方面得到越來越多的應用。但二維及以上的區間ACL壓縮問題已被證明是NP難。本文基于矩陣映射方法基礎，提出將ACL壓縮問題轉化成RPC問題，突破了目前已知的最好近似度O(min(n1/3,OPT1/2))。仿真實驗表明其比傳統ACL壓縮方法具有更高的壓縮比。下一步工作研究如何將該方法應用到多維防火墻規則壓縮之上。

參考文獻

[1] 曾曠怡,楊家海.訪問控制列表的優化問題[J].軟件學報,2007,18(4):978-986.

[2] Rottenstreich O,Cohen R,Raz D,et al.Exact worst case TCAM rule expansion[J].IEEE Transactions on Computers,2013,62(6):1127-1140.

[3] Meiners C R,Liu A X,Torng E.Bit Weaving:A non-prefix approach to compressing packet classifiers in TCAMs[J].IEEE Trans on Networking,2012,20(2):488-500.

[4] Applegate D A,Calinescu G,Johnson D S,et al.Compressing rectilinear pictures and minimizing access control lists[C]//Proc.of the eighteenth annual ACM-SIAM symposium on Discrete algorithms,2007:1066-1075.

[5] Suri S,Sandholm T,Warkhede P.Compressing two-dimensional routing tables[J].Algorithmica,2003,35(4):287-300.

[6] Liu A X,Torng E,Meiners C.Firewall Compressor:An algorithm for minimizing firewall policies[C]//Proc.of the IEEE INFOCOM,April 2008.Phoenix,AZ,2008:176-180.

[7] Daly J,Liu A X,Torng E.A difference resolution approach to compressing access control lists[C]//Proc.of the IEEE INFOCOM,April 2013:2040-2048.

[8] Cheng Y,Wang W,Min G,et al.A new approach to designing firewall based on multidimensional matrix[J].Concurrency and Computation:Practice and Experience,2013,11(27):1-14.

[9] Hu H,Ahn G J,Kulkarni K.Detecting and resolving firewall policy anomalies[J].IEEE Transactions on Dependable and Secure Computing,2012,9(3):318-331.

[10] O’rourke J,Supowit K.Some NP-hard polygon decomposition problems[J].IEEE Transactions on Information Theory,1983,29(2):181-190.

[11] Anil Kumar V S,Ramesh H.Covering rectilinear polygons with axis-parallel rectangles[C]//Proc.of the thirty-first annual ACM symposium on Theory of computing.ACM,1999:445-454.

[12] Richard M K,Avi W.A fast parallel algorithm for the maximal independent set problem[J].Journal of the Association for Computing Machinery,1985,32(4):762-773.

[13] Taylor D E,Turner J S.ClassBench:A packet classification benchmark[J].IEEE Transactions on Networking,2007,15(3):499-511.

中圖分類號TP393.08

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.077

收稿日期：2014-05-08。湖南省教育廳科技項目(13C1049)。程玉柱，講師，主研領域：網絡信息安全。易月娥，副教授。