程玉柱　易月娥

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

?

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

程玉柱易月娥

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

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

關(guān)鍵詞訪問控制列表網(wǎng)絡(luò)安全規(guī)則壓縮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引言

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

1理論基礎(chǔ)

一般而言，ACL內(nèi)任意規(guī)則可以表示為形如“F1∈D(F1)(F2∈D(F2)→decision”的形式，這里Fi(1≤i≤2)分別表示源地址和目標地址，D(Fi)表示對應(yīng)的域值區(qū)間，decision表示規(guī)則的決策(接受或拒絕)。根據(jù)文獻[8]中規(guī)則空間的定義，可進一步將ACL規(guī)則表示為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表示，相應(yīng)坐標區(qū)間為[0, D(Fi)], 1≤i≤2。

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

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

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

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

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

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

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

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

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

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

圖1　原始ACL規(guī)則示例

步驟1將ACL規(guī)則映射到二維矩陣M2

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

步驟2求獨立子集

該方法第一步需要判斷任意兩單元空間之間的空間關(guān)系(具體判定過程見算法1)，可得到對應(yīng)的空間關(guān)系矩陣M，圖4展示了圖3各單元空間之間的空間關(guān)系矩陣。對M內(nèi)每一個矩陣元素，當存在一個“║”或有兩個“╜或╙”時，對應(yīng)的兩單元空間可以定義為“分離”。我們把任一單元空間看作無向連通圖中的一個點，兩單元空間不互為分離則表示其對應(yīng)圖中的兩點之間有邊相連，類似求獨立連通子圖方法[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　空間關(guān)系矩陣示例

算法1構(gòu)建空間關(guān)系矩陣

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

輸出:空間關(guān)系矩陣M，矩陣元素為任意兩單元空間的空間關(guān)系

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){

/*設(shè)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直線多邊形的矩形覆蓋

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

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

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理論分析與仿真結(jié)果

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

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

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

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

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

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

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

圖5　RPC與FDM方法壓縮比較

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

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

4結(jié)語

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

參考文獻

[1] 曾曠怡,楊家海.訪問控制列表的優(yōu)化問題[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)。程玉柱，講師，主研領(lǐng)域：網(wǎng)絡(luò)信息安全。易月娥，副教授。