程玉柱　易月娥

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

?

基于RPC模型的訪問(wèn)控制策略壓縮算法

程玉柱易月娥

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

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

關(guān)鍵詞訪問(wè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引言

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

1理論基礎(chǔ)

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

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

(1) M2是一個(gè)二維矩陣，各維坐標(biāo)用Fi表示，相應(yīng)坐標(biāo)區(qū)間為[0, D(Fi)], 1≤i≤2。

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

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

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

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

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

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

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

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

2基于RPC問(wèn)題模型的ACL壓縮算法

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

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

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

將規(guī)則ri映射到二維矩陣M2的詳細(xì)算法可參考文獻(xiàn)[8]，圖2為該算法過(guò)程示例。設(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的決策為拒絕。因?yàn)閞1的決策是拒絕且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維上進(jìn)行切分為三部分:{[(4,2)(2,2)], [(4,4)(2,3)], [(4,7)(2,2)]}，因?yàn)閇(4,4)(2,3)]與r1的規(guī)則空間一樣，將其移除，從而得到最終的四個(gè)單元空間{[(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為輸入，通過(guò)映射過(guò)程，可以得到六個(gè)單元空間格，最后的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求獨(dú)立子集

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

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

Begin

Steps:

1. 對(duì)單元空間集坐標(biāo)遞增順序進(jìn)行排序(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坐標(biāo)小于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è)獨(dú)立單元空間集正好可以構(gòu)成一個(gè)直線多邊形，從幾何學(xué)觀點(diǎn)看，此時(shí)ACL壓縮問(wèn)題等價(jià)于RPC問(wèn)題?？紤]一般情況，該直線多邊形可能含有“洞”。

根據(jù)算法2，對(duì)獨(dú)立子集S1和S2分別進(jìn)行處理，得覆蓋S1的矩形{[(0,4)(3,4)],[(2,2)(2,3)]},覆蓋S2的矩形{[(5,5)(5,3)],[(7,2)(2,8)]}。最后根據(jù)文獻(xiàn)[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兩個(gè)在空間上互為獨(dú)立的單元空間，其所對(duì)應(yīng)的規(guī)則集也互為獨(dú)立。即求整個(gè)單元空間的最少矩形覆蓋等價(jià)于求各獨(dú)立單元空間集的最少矩形覆蓋的組合。

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

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

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

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

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

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

圖5　RPC與FDM方法壓縮比較

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

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

4結(jié)語(yǔ)

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

參考文獻(xiàn)

[1] 曾曠怡,楊家海.訪問(wèn)控制列表的優(yōu)化問(wèn)題[J].軟件學(xué)報(bào),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.

中圖分類號(hào)TP393.08

文獻(xiàn)標(biāo)識(shí)碼A

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

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