基于LE-Trie的SDN 訪問控制策略研究

李曉強，徐雅斌，2

(1.北京信息科技大學(xué)計算機學(xué)院北京100101;2.北京信息科技大學(xué)網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點實驗室，北京100101)

0 引言

隨著云計算、物聯(lián)網(wǎng)等新興網(wǎng)絡(luò)應(yīng)用的爆發(fā)增長，傳統(tǒng)網(wǎng)絡(luò)架構(gòu)在網(wǎng)絡(luò)承載、控制與業(yè)務(wù)多樣性方面均面臨巨大挑戰(zhàn)。軟件控制和硬件轉(zhuǎn)發(fā)緊密耦合的傳統(tǒng)網(wǎng)絡(luò)設(shè)備越來越難以滿足網(wǎng)絡(luò)快速發(fā)展的需要。為解決上述問題，學(xué)術(shù)界與產(chǎn)業(yè)界針對下一代網(wǎng)絡(luò)架構(gòu)進(jìn)行了大量研究，提出了軟件定義網(wǎng)絡(luò)(software defined networks，SDN)。

SDN的核心思想是將控制與數(shù)據(jù)轉(zhuǎn)發(fā)分離，實現(xiàn)靈活、標(biāo)準(zhǔn)的可編程與自動化網(wǎng)絡(luò)控制。SDN架構(gòu)將網(wǎng)絡(luò)分為數(shù)據(jù)層、控制層和應(yīng)用層。其中數(shù)據(jù)層主要由支持OpenFlow協(xié)議的交換機組成;控制層中的控制器作為一個平臺，向下可以與OpenFlow交換機直接會話，向上可以為應(yīng)用層軟件提供開放接口。應(yīng)用層包括各種應(yīng)用軟件通過restful接口與控制器進(jìn)行交互［1］。

然而，SDN這種邏輯集中、功能分層的網(wǎng)絡(luò)架構(gòu)也存在諸多問題。例如，由于SDN架構(gòu)中轉(zhuǎn)發(fā)設(shè)備的軟硬件實現(xiàn)了解耦合，OpenFlow交換機只負(fù)責(zé)數(shù)據(jù)轉(zhuǎn)發(fā)，導(dǎo)致傳統(tǒng)網(wǎng)絡(luò)中部署在交換機或路由器上的訪問控制功能在SDN架構(gòu)中沒有相應(yīng)的設(shè)備來實現(xiàn)。使得現(xiàn)有SDN架構(gòu)無法實現(xiàn)訪問控制功能，從而降低了SDN的安全性。

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)面臨的安全問題也越來越嚴(yán)重。和傳統(tǒng)網(wǎng)絡(luò)一樣，SDN的網(wǎng)絡(luò)安全性至關(guān)重要。但是，在SDN的架構(gòu)設(shè)計中，對安全性問題考慮不夠，根據(jù)SDN集中控制的思想，傳統(tǒng)的訪問控制列表(access control list，ACL)應(yīng)該部署在控制器上。然而，控制器一般只能接收首包的包頭，無法進(jìn)行檢測。因此，研究和設(shè)計面向SDN的訪問控制策略具有非常重要的理論意義和實際應(yīng)用價值。

1 相關(guān)工作

SDN作為一種新興的網(wǎng)絡(luò)，還處在發(fā)展的初期階段，專門針對SDN網(wǎng)絡(luò)中訪問控制的相關(guān)研究非常少。文獻(xiàn)［2］中提出了一個SDN安全應(yīng)用開發(fā)框架——FRESCO(framework for enabling security controls in openflow netwroks)，F(xiàn)RESCO本質(zhì)上是一個安全控制器，用戶可以在該控制器上進(jìn)行安全應(yīng)用的開發(fā)，F(xiàn)RESCO雖然為安全應(yīng)用開發(fā)者提供了方便，但是FRESCO下發(fā)的安全規(guī)則具有強制執(zhí)行性，由于OpenFlow沒有流表的沖突檢測機制，因而容易導(dǎo)致不同流表的沖突。文獻(xiàn)［3］中提出了在復(fù)雜的SDN網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中設(shè)計一個訪問控制策略傳輸機制，將全局控制策略和SDN網(wǎng)絡(luò)拓?fù)浞謩e導(dǎo)入該策略傳輸機制，由該機制根據(jù)網(wǎng)絡(luò)拓?fù)鋵θ植呗赃M(jìn)行分析，最后將策略下發(fā)到相應(yīng)的交換機上，從而解決了現(xiàn)有SDN只能由人工將高層策略分解成低級規(guī)則的問題。但由于該機制在每次處理時都需要遍歷全部規(guī)則，所以存在效率不高的問題。

盡管SDN架構(gòu)與傳統(tǒng)網(wǎng)絡(luò)架構(gòu)不同，但是傳統(tǒng)網(wǎng)絡(luò)中的訪問控制方法仍然可以借鑒。

傳統(tǒng)網(wǎng)絡(luò)中經(jīng)典的訪問控制模型主要有自主訪問控制模型、強制訪問控制模型和基于角色的訪問控制模型。前2種模型屬于靜態(tài)化的個體資源訪問控制方法，無法適應(yīng)復(fù)雜多變的應(yīng)用系統(tǒng)?，F(xiàn)階段，基于角色的模型被廣泛采用。

文獻(xiàn)［4］中提出了一個基于RBAC(role-based access control)的上下文感知的動態(tài)訪問控制模型，該模型用環(huán)境謂詞描述環(huán)境上下文，通過角色的激活來實現(xiàn)上下文約束條件。模型的不足是上下文信息的動態(tài)變化造成了角色狀態(tài)和關(guān)系的復(fù)雜性，而且模型無法描述普適計算環(huán)境下的模糊不確定上下文信息。

文獻(xiàn)［5］中提出了一個基于信任值的RBAC模型，通過綜合計算信任度和歷史訪問記錄來為用戶分配合理的角色權(quán)限，具有自動決策的功能，但系統(tǒng)訪問控制的復(fù)雜度太高。文獻(xiàn)［6］中提出了一個基于信任的動態(tài)訪問控制模型，在固定的信任域內(nèi)，利用與請求方的歷史交互數(shù)據(jù)和其他用戶的信任信息，計算請求方的信任度，與信任標(biāo)準(zhǔn)比較后授權(quán)，基于信任的模型有效解決了訪問控制的分布式授權(quán)管理問題，但在解決訪問控制安全強度的控制和實現(xiàn)上不夠理想。

文獻(xiàn)［7］將風(fēng)險評估的方法引入控制模型的授權(quán)機制中，提高了使用訪問控制模型的靈活性和安全性。文獻(xiàn)［8］提出了一種分布式計算環(huán)境下訪問控制的實施方案。雖然該模型在分布式、跨域環(huán)境下具有明顯的優(yōu)勢，但是該模型的授權(quán)管理較為復(fù)雜。

文獻(xiàn)［9］提出了一種基于行為的多級安全模型，結(jié)合BLP(bell-la padula)模型和ABAC(attribute-based access control)，通過為主體、課題、行為定義多級安全屬性，實現(xiàn)了基于行為的多級訪問控制。解決了多級安全訪問控制實施中缺乏時空要素的問題，但管理員定義安全級別后，不能伴隨環(huán)境的變化進(jìn)行動態(tài)調(diào)整，靈活性較低。

本文在深入研究SDN架構(gòu)和傳統(tǒng)網(wǎng)絡(luò)訪問控制方法的基礎(chǔ)上，提出了一種集中訪問控制策略。在該策略中，通過訪問控制服務(wù)器實現(xiàn)對SDN網(wǎng)絡(luò)中訪問控制規(guī)則的集中管理。通過分析數(shù)據(jù)流的首包，匹配相應(yīng)的規(guī)則，并將規(guī)則以流表的形式下發(fā)到相應(yīng)的源交換機，從而實現(xiàn)對入網(wǎng)數(shù)據(jù)流的控制。在解決網(wǎng)絡(luò)安全性的同時，降低了SDN網(wǎng)絡(luò)中的無效流量。

2 SDN訪問控制策略的實現(xiàn)方案

在本方案中，將訪問控制作為一個安全應(yīng)用部署到SDN網(wǎng)絡(luò)中，并采用專用的訪問控制服務(wù)器實現(xiàn)訪問控制。訪問控制服務(wù)器主要由檢測模塊、匹配模塊和交互模塊和規(guī)則數(shù)據(jù)庫組成。其中，檢測模塊通過構(gòu)造LE-Trie樹對存入數(shù)據(jù)庫中的規(guī)則進(jìn)行檢測;匹配模塊根據(jù)從數(shù)據(jù)流中提取的信息對數(shù)據(jù)庫中規(guī)則進(jìn)行匹配;交互模塊連接服務(wù)器和控制器;規(guī)則數(shù)據(jù)庫用于存儲訪問控制規(guī)則。

圖1 SDN訪問控制策略Fig.1 SDN Access control policy

SDN訪問控制系統(tǒng)的拓?fù)浣Y(jié)構(gòu)如圖1所示。其工作流程如下。

1)源交換機分析接收到的數(shù)據(jù)流，提取首包中的源地址、目的地址、源端口、目的端口、協(xié)議類型，封裝成OpenFlow數(shù)據(jù)包發(fā)送到SDN控制器中。

2)控制器將OpenFlow數(shù)據(jù)包通過restful接口傳送到訪問控制服務(wù)器。

3)訪問控制服務(wù)器解析該數(shù)據(jù)包，提取五元組信息，服務(wù)器使用五元組與訪問控制策略匹配，并將結(jié)果返回控制器。

4)控制器根據(jù)訪問控制服務(wù)器返回的結(jié)果，將訪問控制策略以流表的形式下發(fā)到源交換機。

5)源交換機根據(jù)下發(fā)的流表決定是否允許該數(shù)據(jù)流的訪問行為。

3 SDN訪問控制規(guī)則檢測

3.1 問題的提出

與傳統(tǒng)網(wǎng)絡(luò)中將訪問控制規(guī)則部署到相應(yīng)的路由器或交換機上不同，本方案將訪問控制規(guī)則集中部署到SDN網(wǎng)絡(luò)中的訪問控制服務(wù)器中，全網(wǎng)規(guī)則的集中管理導(dǎo)致規(guī)則之間會出現(xiàn)各種沖突，如何檢測沖突，規(guī)則就成為本方案首先要解決的問題。文獻(xiàn)［10］中提出了一種分治的異常檢測的方法，大大減小了數(shù)據(jù)包匹配規(guī)則的范圍，但仍然受規(guī)則相關(guān)性的影響。文獻(xiàn)［11］中提出了位向量法檢測異常的方法，雖然提高了時間效率，但對空間要求太高。文獻(xiàn)［12］中提出一種利用遞歸trie樹來檢查異常的grid-of-Tries方法。但是，grid-of-Tries算法只能處理二維交叉沖突問題，無法檢測規(guī)則冗余。

為此，本文在分析OpenFlow數(shù)據(jù)包的基礎(chǔ)上，引入了一種快速沖突檢測和規(guī)則匹配的多區(qū)域LETrie算法(multi-area-domain LE-Trie，MADLT)，該算法在LE-Trie樹的支持下避免了對規(guī)則集進(jìn)行順序匹配，且對規(guī)則條數(shù)的增加不敏感。

3.2 相關(guān)定義

定義1 規(guī)則。形如R={(P1P2…Pn)－＞A|Pi.A{Action Set}，稱R為一條規(guī)則。其中，A是來自Action集合，表示(P1P2…Pn)結(jié)果為True時需要執(zhí)行的業(yè)務(wù)操作;規(guī)則點Pi定義為滿足Pi={(Pi.N=Pi.V)|Pi}，其中，Pi.N是一個變量名，Pi.V是Pi.N對應(yīng)至于的一個具體值，n表示規(guī)則點個數(shù)。

訪問控制規(guī)則一般可以用IF(條件表示公式)THEN(執(zhí)行結(jié)果)的形式來表示，表1為訪問控制規(guī)則表的一個簡單表示形式。表1中，規(guī)則R1表示為:IF(協(xié)議=TCP and源IP=141.192.37.20 and目的端口=80)THEN(執(zhí)行動作=拒絕)。

定義2 規(guī)則沖突。假設(shè)RX和Ry是2條規(guī)則，RX和Ry中的各個相同的規(guī)則點參數(shù)均有交集，且2條規(guī)則的執(zhí)行結(jié)果不同，則稱規(guī)則RX與Ry沖突，記為conf(RX，Ry)。

規(guī)則沖突的類型主要有3類:包含沖突、相交沖突和相離沖突。

定義3 包含關(guān)系。設(shè)Rx和Ry為任意2條規(guī)則，如果對于所有的規(guī)則點Pk(1≤k≤m，m為規(guī)則點總數(shù))，都有P［x，k］.V=P［y，k］.V或者P［x，k］.V=Ω，定義規(guī)則Rx包含規(guī)則Ry，其中，Ω 為P［x，y］的全集。如表2所示。

性質(zhì)1包含沖突性質(zhì)。設(shè)有Rx，Ry任意2條規(guī)則，且Rx包含Ry，當(dāng)Ax不等于Ay時，有conf(Rx，Ry)成立。形如:

IF{?k:P［x，k］.V=P［y，k］.V or P［x，k］.V=Ω)and Ax≠Ay}THEN conf(Rx，Ry)

定義4 相交關(guān)系。設(shè)Rx和Ry為任意2條規(guī)則，如果至少存在一個規(guī)則點Pk(1≤k≤m，m為規(guī)則點總數(shù))，使得P［x，k］.V=P［y，k］.V，同時存在P［x，q］.V=Ω 或者P［y，q］.V=Ω(k≠q)，則定義規(guī)則Rx和規(guī)則Ry相交。如表3所示。

性質(zhì)2相交沖突。設(shè)有任意2條規(guī)則Rx，Ry，且Rx與Ry相交，當(dāng)Ax不等于Ay時，有conf(Rx，Ry)成立。形如:

IF{?k，q:P［x，k］.V=P［y，k］.V and(P［x，q］.V=Ω or P［y，q］.V=Ω))and Ax≠Ay|k≠q}THEN conf(Rx，Ry)

定義5 相離關(guān)系。設(shè)任意2條規(guī)則Rx和Ry，對于任意規(guī)則點Pk(1≤k≤m，m為規(guī)則點數(shù))，如果存在P［x，K］≠Ω 或者P［y，k］≠Ω 時，且對應(yīng)的P［y，K］=Ω 或者P［x，k］=Ω，稱Rx與Ry相離。如表4所示。

表1 訪問控制規(guī)則表Tab.1 Access control list

表2 包含關(guān)系Tab.2 Inclusion relationship

表3 相交關(guān)系Tab.3 Intersection relationship

表4 相離關(guān)系Tab.4 Disjoint relation

性質(zhì)3相離沖突性質(zhì)。設(shè)任意2條規(guī)則Rx，Ry，且Rx與Ry相離，當(dāng)Ax不等于Ay時，有conf(Rx，Ry)。形如:

IF{?k:(P［x，K］≠Ω∩P［y，K］=Ω or P［y，k］≠Ω∩P［x，k］=Ω)and Ax≠Ay}THEN conf(Rx，Ry)

定義6 域。假設(shè)P［*，j］是所有規(guī)則R的第j個規(guī)則點，P［*，j］.N是規(guī)則點上的變量名，則稱P［*，j］.N對應(yīng)的P［*，j］.V的值集合為域Domj;形如

其中，n表示規(guī)則點總數(shù)。

定義7 區(qū)。在域Domk中根據(jù)每個P［*，k］.V值對所有規(guī)則R進(jìn)行分類，所形成的每一個規(guī)則分類集合稱為一個區(qū)Area。形如:

Areax={{Rk}|k:P［i，k］.V=P［j，k］.V，1≤k≤m}

性質(zhì)4同域不沖突性質(zhì)。假設(shè)Domi是規(guī)則表R的一個域，Areax和Areay是該域中任意2個區(qū)，則區(qū)Areax和Areay中規(guī)則號的交集必然為空集。形如:

IF{＜Rm，Rn＞|Areax，Areay∈Domi∩Rm∈Areax∩Rn∈Areay}THEN{Rm∩Rn=?}

分析SDN中的OpenFlow數(shù)據(jù)流可知，數(shù)據(jù)流至少由協(xié)議類型、源IP、目的IP、源端口和目的端口等5個參數(shù)組成。因此，可通過由這5個參數(shù)和動作字段構(gòu)成的訪問控制規(guī)則來對數(shù)據(jù)流進(jìn)行訪問控制。

分析訪問控制規(guī)則可知，規(guī)則中的IP字段和端口字段的類型主要有單點和區(qū)間2類，單點具體到某個IP或端口，而區(qū)間則限制某一段的IP或端口。

根據(jù)OpenFlow數(shù)據(jù)流的訪問控制規(guī)則的特點以及域和區(qū)的概念，將規(guī)則參數(shù)分為5個不同的域，在同域中根據(jù)起止點數(shù)值的二進(jìn)制最大公共前綴劃分成區(qū)，對上述規(guī)則進(jìn)行處理后得到的訪問控制規(guī)則的形式如表5所示。

表5 訪問控制規(guī)則Tab.5 Access control rules

由表1可知，規(guī)則中的參數(shù)劃分為6個域，每個域中根據(jù)參數(shù)值不同劃分為若干不同的區(qū)，相同參數(shù)值的規(guī)則屬于一個區(qū)。

3.3 沖突檢測算法

由上述的規(guī)則沖突定義和沖突類型可知:對于給定的待檢測規(guī)則，分別檢查待檢測規(guī)則與規(guī)則表中已有規(guī)則組成的規(guī)則對的關(guān)系，如果符合3種沖突類型之一，則說明該規(guī)則對沖突。文獻(xiàn)［13］中提到的順序檢測方法需要對所有的規(guī)則逐條進(jìn)行檢測，所以只適用于小規(guī)模規(guī)則集合，處理大規(guī)模規(guī)則集合的效率太低。

為提高大規(guī)模規(guī)則集的沖突檢測效率，本文提出了基于LE-Trie樹結(jié)構(gòu)的快速沖突檢測算法。將對規(guī)則的順序匹配轉(zhuǎn)化為對多個域的處理，在域內(nèi)根據(jù)分區(qū)和規(guī)則構(gòu)建LE-Trie樹。該方法降低了規(guī)則檢測中的匹配規(guī)模，同時對規(guī)則數(shù)量的增加不敏感。

LE-Trie樹的特點如下:

1)Trie樹只有2種情況，一種是樹為空集;另一種樹為有惰性展開特性的二叉樹。

2)可展開的節(jié)點有2個分別指向左右孩子的指針，指向左孩子的路徑是以0開頭的字符串，右孩子是以1開頭的字符串。不限制路徑上字符串的長度，指向父節(jié)點的路徑字符串為2個子節(jié)點的字符串的最大公共前綴。

3)有新規(guī)則加入時，如果節(jié)點中存在與它前綴不同的規(guī)則，這個新規(guī)則的加入將展開這個節(jié)點。

檢測算法建立在已有規(guī)則的LE-Trie樹結(jié)構(gòu)的基礎(chǔ)上，向樹中插入新規(guī)則的過程即為檢測的過程。

構(gòu)造LE-Trie樹時盡量不展開Trie樹的路徑，直到無法在同一節(jié)點中共存2個具有不同前綴規(guī)則時，才按Trie樹路徑建立規(guī)則展開盡可能小的一段路徑。以IP地址為例，構(gòu)建LE-Trie樹的過程如圖2所示。圖2中，IP的前綴分別是a=01*，b=01001*，c=010001*，d=01100*。

構(gòu)建圖2中LE-Trie的過程如下。

1)只有一條數(shù)據(jù)a時，a的第一位為0，則直接從根節(jié)點生成一個左孩子。

圖2 LE-Trie樹構(gòu)建過程Fig.2 Build process of LE-Trie tree

2)向樹中插入數(shù)據(jù)b(01001)，從根節(jié)點開始查找與公共前綴最大的節(jié)點01，b的第3位為0，則從a節(jié)點上生成左孩子001，并保存節(jié)點b。

3)插入數(shù)據(jù)c(010001)，從根節(jié)點開始查找與數(shù)據(jù)c公共前綴最大的節(jié)點發(fā)現(xiàn)，a的左孩子的前2位與c相應(yīng)位置的數(shù)據(jù)匹配，分解b節(jié)點，將00作為節(jié)點，并在該節(jié)點上生成左右孩子01和1，分別保存b和c節(jié)點。

4)插入數(shù)據(jù)d(01100)，d與a有公共節(jié)點01，d的第3位為1，在a節(jié)點生成右孩子100，保存數(shù)據(jù)d。

在Trie樹的構(gòu)建過程中，本算法將單值點視為起止點相同的區(qū)間，以參數(shù)起止點的最大公共前綴作為構(gòu)建樹中節(jié)點的元素，具有相同最大公共前綴的規(guī)則號保存在同一個節(jié)點下，從而解決了參數(shù)的區(qū)間值和單點值在同一樹結(jié)構(gòu)中檢測困難的問題。

本檢測算法如下:

4 SDN訪問控制規(guī)則匹配

檢測算法主要對新加入的規(guī)則進(jìn)行識別，并將符合條件的規(guī)則添加到規(guī)則樹中。規(guī)則匹配算法則是根據(jù)數(shù)據(jù)流的包頭信息在規(guī)則樹中選擇合適的規(guī)則，并通過控制器將規(guī)則下發(fā)到相應(yīng)的交換機上，實現(xiàn)對數(shù)據(jù)流的訪問控制。

如前所述，由于SDN架構(gòu)沒有類似傳統(tǒng)網(wǎng)絡(luò)中路由器或者交換機的硬件承載設(shè)備，本方案采用專門的訪問控制服務(wù)器來實現(xiàn)SDN下的訪問控制功能。該方案中將SDN網(wǎng)絡(luò)的所有訪問控制規(guī)則都集中到訪問控制服務(wù)器存儲，因而可能會使得規(guī)則的數(shù)目變得十分龐大，從而導(dǎo)致匹配時間過長，難以滿足網(wǎng)絡(luò)訪問控制請求的快速響應(yīng)。因此，如何提高訪問控制服務(wù)器的響應(yīng)時間就成為規(guī)則匹配首先要解決的問題。

4.1 基本性質(zhì)

性質(zhì)5規(guī)則點不交叉性。

設(shè)Pi.N和Pj.N表示規(guī)則集中任意一條規(guī)則R的第i和第j個規(guī)則點的屬性名，則Pi.N∩Pj.N=?，其中，i≠j，1≤i，j≤n。

定義7 規(guī)則匹配。

設(shè)X為一條待匹配業(yè)務(wù)數(shù)據(jù)，R為規(guī)則庫中規(guī)則集合。如果存在一條規(guī)則Ri的規(guī)則點P［i，］j.N與Xk.N相同，且P［i，j］.V與Xk.V相同，則稱該規(guī)則Ri的動作值A(chǔ)i為規(guī)則的執(zhí)行動作，求解過程稱為規(guī)則匹配函數(shù)F(X)。形如:

F(x)={{Ai(x)}|?i(P［i，］jN=Xk.N∩P［i，j］.V=Xk.V)→Ai(x)，1≤i≤m，1≤j≤n，1≤k≤q}

其中，m表示規(guī)則數(shù)，n為業(yè)務(wù)數(shù)據(jù)的屬性名數(shù)，q為規(guī)則點個數(shù)。

以表1的規(guī)則集合為例，假定需要匹配的數(shù)據(jù)流的五元組字段為(TCP，141.192.37.*，*，*，80)，如果存在規(guī)則R，使得各對應(yīng)域的屬性名和屬性值均相同，則說明F(X)成立，結(jié)果F(X)=“拒絕”。

性質(zhì)6動作數(shù)性質(zhì)。

設(shè)R為規(guī)則集合，對于任意外部數(shù)據(jù)X，經(jīng)規(guī)則匹配函數(shù)F(X)對X在R上進(jìn)行匹配后，產(chǎn)生的匹配結(jié)果A(X)要么有且僅有一個動作結(jié)果A，即要么|A(X)|=1，要么為空集?:

IF F(X)={{A(X)}，?i:(Ri(x)→Ai(x)|1≤i≤m)}THEN{|A(X)|=1 or{A(X)}=?}

4.2 規(guī)則匹配算法

規(guī)則匹配算法的核心思想是根據(jù)已經(jīng)構(gòu)造出的所有域的LE-Trie樹結(jié)構(gòu)來匹配規(guī)則，根據(jù)規(guī)則匹配的性質(zhì)和LE-Trie樹結(jié)構(gòu)的特點可知，各域的匹配結(jié)果的交集即為該數(shù)據(jù)流要執(zhí)行的規(guī)則。通過LETrie樹可以降低規(guī)則匹配的次數(shù)，提高匹配效率。

具體匹配算法如下:

輸入:一條業(yè)務(wù)數(shù)據(jù)R(x)

輸出:業(yè)務(wù)數(shù)據(jù)R(x)所匹配規(guī)則的Action:A(x)

1)for each Doms［i］//將業(yè)務(wù)數(shù)據(jù)的屬性值送入對應(yīng)的域進(jìn)行匹配

RuleNum［i］=MatchLeTrie(LeTrie(i)，R(x))

end each

2)Rule=RuleNum［1］//獲取匹配的規(guī)則號

for(i=1;i＜=m;i++)

Rule=Rule∩RuleNum［i+1］

A［x］=Rule∩Doms［A］

return A［x］

匹配獲取的規(guī)則動作A［x］，通過交互模塊返回給SDN控制器，控制器將A［x］以流表的形式下發(fā)到相應(yīng)的OpenFlow交換機中，交換機根據(jù)流表對數(shù)據(jù)流進(jìn)行處理。

規(guī)則匹配主要根據(jù)已經(jīng)構(gòu)建好的LE-Trie樹完成，因此，規(guī)則檢測算法的時間復(fù)雜度為O(lb|Domsi|x|Domsi|/2)，其中，|Domsi|為域Doms(i)對應(yīng)的屬性值的個數(shù)。

5 實驗及結(jié)果分析

為驗證算法的有效性和高效性，分別選取順序匹配算法和普通Trie算法與MADLT算法分別在時間和空間效率方面進(jìn)行比較。

在實驗中，采用Class Bench工具生成的不同規(guī)模的訪問控制策略規(guī)則集對檢測和匹配算法的時間性能進(jìn)行測試，采用5次測試后的平均時間作為實驗結(jié)果。

表6為3種算法在不同規(guī)模的規(guī)則集下進(jìn)行沖突檢測時所消耗的時間。

表6 規(guī)則檢測的時間性能對比Tab.6 Time performance comparison of rule detection

圖3為根據(jù)表6生成的3種算法在沖突檢測時的時間變化的對數(shù)曲線。

由表6和圖3可知，使用小規(guī)模規(guī)則集進(jìn)行測試時，順序算法時間最快。隨著規(guī)模變大，Trie算法和MADLT算法在時間性能上優(yōu)勢明顯。除第一組數(shù)據(jù)外，MADLT算法與順序算法相比，效率平均提高了2.97倍;與Trie算法相比，效率平均提高了約30.4%。并且，規(guī)則集越大，MADLT算法的性能優(yōu)勢越明顯。

表7為進(jìn)行規(guī)則匹配時3種算法所消耗的時間。

圖4是根據(jù)表7生成的消耗時間的對數(shù)曲線圖。

由表7和圖4可知，順序算法在小規(guī)模規(guī)則集的匹配上有優(yōu)勢，而普通Trie算法和MADLT算法在處理大規(guī)模規(guī)則集時速度更快，MADLT算法的效率較順序算法平均提高了2.3倍，較普通Trie算法平均提高了16.3%，且規(guī)則集越大，MADLT算法性能提高越多。

表8為3種算法在不同規(guī)模規(guī)則集下消耗的內(nèi)存空間。

圖5為根據(jù)表8得到的消耗內(nèi)存空間的變化曲線。

表7 規(guī)則匹配的時間性能比較Tab.7 Time performance comparison of rule matching

圖3 沖突檢測算法時間性能對數(shù)曲線Fig.3 Time performance logarithmic of curve collision detection algorithm

圖4 規(guī)則匹配算法的時間性能對數(shù)曲線Fig.4 Time performance logarithmic curve of rule matching algorithm

表8 內(nèi)存消耗比較Tab.8 Memory consumption comparison

圖5 內(nèi)存消耗對比曲線Fig.5 Contrast curves of memory consumption

由表8和圖5可知，順序算法消耗內(nèi)存最少，MADLT算法較順序算法空間消耗平均增加了2.14倍，MADLT算法較普通Trie算法的空間消耗平均降低了50.1%。MADLT算法對空間需求明顯高于順序算法，但與普通Trie算法相比，空間消耗明顯降低。

分析實驗數(shù)據(jù)發(fā)現(xiàn)，MADLT算法通過犧牲空間換取時間，在時間效率上可以滿足實際需求。同時，犧牲的空間也在計算機硬件可承受的范圍內(nèi)。對比檢測算法與匹配算法提高的效率可知，匹配算法提高的幅度略小于檢測算法，原因在于匹配算法需要處理動作域獲取規(guī)則動作，并將動作傳回給控制器。

6 結(jié)束語

為解決SDN架構(gòu)中無法對數(shù)據(jù)流進(jìn)行訪問控制的問題，本文提出了以訪問控制服務(wù)器為基礎(chǔ)的集中訪問控制策略，并通過設(shè)計基于LE-Trie樹的規(guī)則檢測和匹配方案，提高了沖突檢測和規(guī)則匹配的效率。

實驗結(jié)果表明，基于LE-Trie的規(guī)則檢測算法較順序檢測提高2.97倍，較普通Trie算法提高了30.4%;基于LE-Trie的規(guī)則匹配算法較順序檢測提高了2.3倍;較普通Trie樹的算法提高了16.3%;在空間消耗上，雖然比順序算法占用空間多，但比普通Trie算法降低了50.1%。通過實驗證明，本文提出的集中訪問控制方案能較好的解決SDN中的訪問控制問題，具有一定的實用性。在下一步的研究工作中，將重點考慮解決進(jìn)入SDN網(wǎng)絡(luò)后的用戶行為安全的感知問題，進(jìn)一步提高SDN網(wǎng)絡(luò)的安全性。

［1］ONF.Software-Defined Networking:the New Norm for Networks［EB/OL］.［2015-05-04］.http://wenku.baidu.com/view/74cbdflac281e53a5802ffa7.html.

［2］SHIN Seungwon，PHIL P，VINOD Y.FRESCO:Modular Composable Security Services for Software-Defined Networks［C］//Proceedings of Network and Distributed Security Symposium.San Diego:Internet Society，2013:135-139.

［3］KANG Nanxi，REXFORD R，WALKER D.Policy Transformation in Software Defined Networks［C］//ACM SIGCOMM Computer Communication Review-Special october issue.New York:ACM Special Interest Group on Data Communication，2012(12):309-310.

［4］YOUNA J，JAMES B D.CRiBAC:Community-centric role interaction based access control model Computers Security［J］.computer＆secturity，2012，31(4):497-523.

［5］鄧文洋，周洲儀，林思明，等.開放式環(huán)境下一種基于信任度的RBAC模型［J］.計算機工程，2013，39(02):112-118.

DENG Wenyang，ZHOU Zhouyi，LIN Siming，et al.An RBAC model based on trust degree in open environment［J］.Computer Engineering，2013，39(02):112-118.

［6］殷曉玲，夏啟壽，王汝傳.Web Services中基于信任的動態(tài)訪問控制［J］.計算機應(yīng)用研究，2011，28(11):4331-4334.

YIN Xiaoling，XIA Qishou，WANG Ruchuan.Trust-based dynamic access control in Web Services［J］.Application Research of Computers，2011，28(11):4331-4334

［7］KRAUTSEVICH L，LAZOUSKI A，MARTINELLI F.Risk-aware Usage Decision Making in Highly Dynamic Systems［C］//The Fifth Internet Monitoring and Protection.Barcelona，Spain:IEEE press，2010:29-34.

［8］初曉博，秦宇.一種基于可信計算的分布式使用控制研究［J］.計算機學(xué)報，2010，33(1):93-101.

CHU Xiaobo，QIN Yu.A Distributed usage control system based on trusted computing［J］.Chinese Journal of Computers，2010，33(1):93-101.

［9］蘇铓，李鳳華.基于行為的多級訪問控制模型［J］.計算機研究與發(fā)展，2014，51(7):1604-1613.

SU Mang，LI Fenghua.Action-based multi-level access control mode［J］.Journal of Computer Research and Development，2014，51(7):1604-1613.

［10］李中，李堯.一種性能優(yōu)化的防火墻規(guī)則匹配算法［J］.計算機應(yīng)用研究，2013，30(4):1205-1207.

LI Zhong，LI Yao.Modified firewall rules matching algorithm［J］.Application Research of Computers，2013，30(4):1205-1207.

［11］徐艷，董濤.一種防火墻規(guī)則沖突快速檢測算法［J］.計算機技術(shù)與發(fā)展，2013(9):128-134.

XU Yan，DONG Tao.A fast algorithm for detecting firewall rule conflict［J］.Computer Technology and Development，2013(9):128-134.

［12］劉軍軍.基于決策樹的防火墻策略算法研究［D］.長沙:中南大學(xué)，2009.

LIU Junjun.Research of algorithm for firewall policy based on policy tree［D］.Changsha:Central South University，2009.

［13］施榮華，莫銳，趙文濤.一種基于沖突檢測的無關(guān)聯(lián)規(guī)則集匹配算法［J］.計算機工程與科學(xué)，2010(10):1-4.

SHI Ronghua，MO Rui，ZHAO Wentao.An irrelative rule set match algorithm based on collision detection［J］.Computer Engineering＆Science，2010(10):1-4.

［14］梁建武，龍曉梅，劉軍軍.基于LE-Trie的防火墻策略檢測算法［J］.計算機工程，2010(22):134-136.

LIANG Jianwu，LONG Xiaomei，LIU Junjun.Detection algorithm for firewall policy based on le-trie［J］.Computer Engineering，2010(22):134-136.

［15］秦拯，厲怡君，歐露.SFDD算法的設(shè)計及其在狀態(tài)防火墻規(guī)則集比對的應(yīng)用［D］.長沙:湖南大學(xué)，2013.

QIN Zheng，LI Yijun，OU Lu.SFDD Construction Algorithm Design and its application in the stateful firewall rule set comparison［D］.Changsha:Hunan University，2013.

［16］郎波.面向分布式系統(tǒng)訪問控制的信任度量化模型［J］.通信學(xué)報，2010，31(12):45-54.

LANG Bo.Access control oriented quantified trust degree representation model for distributed systems［J］.Journal on Communications，2010，31(12):45-54.

［17］王小明，付紅，張立臣.基于屬性的訪問控制研究進(jìn)展［J］.電子學(xué)報，2010，38(7):1660-1667.

WANG Xiaoming，F(xiàn)U Hong，ZHANG Lichen.Research progress on attribute-base access control［J］.Acat Electronica Sinica，2010，38(7):1660-1667.