,,,

(浙江師范大學 數(shù)理與信息工程學院,浙江 金華 321004)

0 概述

訪問控制是保障網(wǎng)絡安全重要的核心技術(shù)之一,它允許被授權(quán)的主體對特定客體的訪問,同時拒絕向非授權(quán)的主體提供服務[1]。安全與可用是訪問控制2個重要需求,也是運用訪問控制技術(shù)保護網(wǎng)絡環(huán)境中信息機密性和完整性的關(guān)鍵所在。訪問控制策略側(cè)重于安全原則,主要是對用戶訪問進行限制以保障系統(tǒng)的安全性需求。職責分離策略將執(zhí)行一項任務的相關(guān)權(quán)限分配給不同的用戶,形成系統(tǒng)內(nèi)部用戶之間的相互牽制,阻止少量用戶擁有過多權(quán)限,以防止系統(tǒng)權(quán)限被濫用,是一種典型的基于安全需求的訪問控制策略[2-4]。相對于被看作為限制訪問的安全性需求而言,可用性需求則可以被看作是對訪問的啟用[5-6]?？捎貌呗砸髤f(xié)作完成某個任務的用戶數(shù)量不能超過某個閾值,因為用戶的數(shù)量上限直接關(guān)系到該任務是否能被順利執(zhí)行,是訪問控制策略基于可用性需求的一個典型實例[7-9]。

訪問控制策略的安全性需求與可用性需求互為彼此補充。如果缺少了可用性需求,可以輕易構(gòu)造出滿足任何安全性需求的訪問控制狀態(tài),例如令該狀態(tài)不包含任何用戶集合能夠擁有完成該任務所需的全部權(quán)限[6]。同樣,如果缺少了安全性需求,也可以輕易構(gòu)造出滿足任何可用性需求的訪問控制狀態(tài),例如給系統(tǒng)中所有用戶均授予所有權(quán)限,使得系統(tǒng)中任何單個用戶都能夠獨立完成該任務[5]?，F(xiàn)有權(quán)限指派約束往往側(cè)重于保障系統(tǒng)的安全性而忽略了可用性。因此,設(shè)計一種兼顧系統(tǒng)安全性與可用性需求的高階權(quán)限指派約束顯得尤為必要。然而,安全性與可用性需求彼此互斥,兩者并存且當訪問控制系統(tǒng)中的主體、客體、權(quán)限又隸屬于不同的約束時,有可能引發(fā)安全沖突[10-15]。

關(guān)于安全沖突消解方面的代表性研究較多,例如文獻[13]將策略看作是一種規(guī)定系統(tǒng)管理行為的方法,研究了策略沖突的離線檢測和解決技術(shù)及其工具支持,主要涉及授權(quán)策略和強制策略。在策略之間建立優(yōu)先級關(guān)系來消除沖突,并給出了4種策略優(yōu)先級:否定策略優(yōu)先,指定策略的優(yōu)先級,基于距離規(guī)定優(yōu)先級,域嵌套優(yōu)先級。文獻[14]從策略角度分析了大規(guī)模分布式系統(tǒng)中元素間的相互關(guān)系,并統(tǒng)一抽象成有向無環(huán)圖模型,從而將抽象的安全策略沖突檢測問題轉(zhuǎn)化為具有成熟算法的有向圖的連通性問題,提出一種檢測策略沖突的定量方法檢測分布式系統(tǒng)中安全策略沖突,包括模態(tài)沖突和內(nèi)外沖突,并得出影響沖突檢測復雜性的主要因素及其程度。文獻[15]使用Prolog實現(xiàn)謂詞規(guī)范以驗證訪問控制元策略。將沖突檢測窗口中的策略集合自動轉(zhuǎn)換為Prolog斷言,并對謂詞加以評估。一個謂詞的全部解決方案就是存在沖突的策略集。安全性需求與可用性需求之間的沖突不能直接按照以上消解方法來進行消解。上述方法適用于求解計算復雜性較低的問題,當問題求解的復雜性為NP-hard級別時,其計算開銷往往呈指數(shù)級增長趨勢,因此,設(shè)計一種針對一致性驗證問題的優(yōu)化求解方法尤為必要。

針對上述問題,本文首先提出一種兼顧系統(tǒng)安全性與可用性需求的高階權(quán)限指派(High-level Permission Assignment,HPA)約束,定義高階權(quán)限指派約束的安全性驗證問題和一致性驗證問題;然后證明安全性驗證問題和一致性驗證問題在一般情形下分別是NP-complete及NPNP問題;最后設(shè)計一種求解一致性驗證問題的優(yōu)化算法,并通過仿真實驗驗證其有效性。

1 高階權(quán)限指派約束的定義

定義1一個高階權(quán)限指派約束防止用戶集{u1,u2,…,un}中任何基數(shù)小于s的用戶子集的權(quán)限并集包含{p1,p2,…,pm},同時保證{u1,u2,…,un}中至少存在一個基數(shù)為t的用戶子集的權(quán)限并集包含{p1,p2,…,pm},形式化描述如下:

hpa〈{p1,…,pm},{u1,…,un},s,t〉

其中,pi(1≤i≤m)表示一個權(quán)限,uj(1≤j≤n)表示一個用戶,s和t都是整數(shù),且1≤s≤t≤min(m,n),min(m,n)返回m和n兩者之中較小的一個數(shù)。

HPA約束防止少量的用戶擁有全部權(quán)限,而將執(zhí)行某一任務的權(quán)限指派給用戶集合中s個以上的用戶,以保障系統(tǒng)安全,同時保證訪問控制系統(tǒng)中至少存在一個包含t個用戶的用戶組被指派全部權(quán)限,以保障系統(tǒng)可用。

舉例說明:假設(shè)訪問控制系統(tǒng)中執(zhí)行某一任務所需要的權(quán)限集合為P={p1,p2,p3,p4,p5,p6,p7,p8},用戶集合為U={u1,u2,u3,u4,u5},HPA約束集合為H={h1,h2,h3,h4},其中h1=hpa〈P,U,2,3〉,h2=hpa〈P,U,5,3〉,h3=hpa〈P,U,s,5〉(s≠1),h4=hpa〈P,U,1,t〉(t≠min(m,n))。

滿足約束h1就要防止用戶集U中任何基數(shù)小于2的用戶子集的權(quán)限并集包含P,即如果任何一個用戶被授予了全部權(quán)限則不滿足這條約束,同時保證用戶集合U中至少存在一個基數(shù)為3的用戶子集的權(quán)限并集包含P,即至少有一個包含了3個U中用戶的用戶組被指派P中全部權(quán)限才滿足這條約束。h2約束防止用戶集{u1,u2,…,u5}中任何基數(shù)小于5的用戶子集的權(quán)限并集包含P,同時保證U中至少存在一個基數(shù)為3的用戶子集的權(quán)限并集包含P。顯而易見h2本身就有沖突,顯然是不會被滿足的。另外,HPA約束中當參數(shù)s,t有特殊的取值時,在約束效果上表現(xiàn)出傾向性。要滿足h3除了滿足安全性需求即防止少于s個用戶的用戶組被指派全部權(quán)限外,還要保證至少存在一個包含了5個U中用戶的用戶組被指派P中全部權(quán)限,而多于5個用戶的用戶組是不存在的,同時如果不滿足h3的可用性需求約束,該任務將無法執(zhí)行。因此,當t=min(m,n)時,其對可用性的約束可以忽略。當s=1時,HPA約束的安全性最低。要滿足h4除了滿足可用性需求即至少有一個包含了t個U中用戶的用戶組被指派P中全部權(quán)限外,還要防止少于1個用戶的用戶組被指派全權(quán)限,后者在任何訪問控制系統(tǒng)中顯然都是滿足的。因此,當s=1時,HPA的安全性約束可以忽略。

2 高階權(quán)限指派約束的安全性驗證

HPA約束在保障訪問控制系統(tǒng)的安全性的同時又約束了系統(tǒng)的可用性,因此,一個給定的訪問控制狀態(tài)是否能夠滿足一個給定的HPA約束是需要考慮的問題。給定一個訪問控制狀態(tài)ε,并且滿足一個HPA約束集合H,記為satH(ε)。定義2給出了HPA約束的安全性驗證問題:

定義2給定一個訪問控制狀態(tài)ε和一個HPA約束h,驗證ε是否滿足h,即判定sath(ε)是否為真,被稱為HPA約束的安全性驗證問題(Safety Checking Problem,SCP)。

定理1SCP既是NP-complete問題,又是coNP-complete問題。

證明:

1)證明當s=1時SCP是NP-complete問題。

當且僅當約束hpa〈{p1,p2,…,pm},{u1,u2,…,un},1,t〉在訪問控制狀態(tài)ε中得到滿足時,sathpa(ε)才為真。當s=1時,僅考慮參數(shù)t。因此,對于任意HPA約束hpa〈Pi,Ui,1,t〉,它要求Ui中至少存在一個用戶子集合能夠覆蓋權(quán)限集合Pi,而且該子集合的基數(shù)不超過t。如果基數(shù)為t的用戶集合給定了,驗證問題將可以在多項式時間內(nèi)完成:計算該集合中所有用戶的權(quán)限并集,并檢測其是否為Pi的父集。

下面將集合覆蓋問題[16]規(guī)約成當SCP的子問題s=1,從而證明當s=1時SCP是NP-complete問題。在該集合覆蓋問題中,輸入是一個有限的集合S、一個作為S的子集合家族F={S1,S2,…,Sl}以及預算B。目標是判斷是否存在B個F中的子集合,使得它們的并集為S。該問題已被證明是一個NP完全問題。規(guī)約過程可在多項式時間內(nèi)完成,具體規(guī)約方法如下:

給定S,F和B,構(gòu)造一個HPA約束f:對于S中的每一個元素,構(gòu)造一個權(quán)限,令t=B,m是集合S的基數(shù)。構(gòu)造一個HPA約束hi=hpa〈Pi,Ui,1,t〉,并構(gòu)造出一個訪問控制狀態(tài):對于F中每一個不同的子集Si(1≤i≤l),創(chuàng)造一個用戶ui∈{u1,u2,…,un},使得Si中的全部權(quán)限指派給ui。則hpa〈Pi,Ui,1,t〉是否為真當且僅當F中存在B個子集合的并集覆蓋S。因此,當s=1時的SCP既是NP問題亦是NP難度問題,故而s=1時的SCP是NP-complete問題。

2)證明當t=min(m,n)時,SCP是coNP-complete問題。

綜上所述,當s=1時SCP是NP-complete問題,當t=min(m,n)時SCP是coNP完全問題。因此SCP既是NP-complete問題亦是co-NP完全問題。

證畢。

3 高階權(quán)限指派約束的一致性驗證

每個HPA約束包含了不同的安全性需求與可用性需求,兩者互為補充,又互相排斥,當訪問控制系統(tǒng)中同時并存多個HPA約束,互斥的安全性需求與可用性需求可能會引發(fā)HPA約束的不一致性。假定存在一個訪問控制狀態(tài)ε滿足約束集合H={h1,h2,…,hn}(n≥2),記為satH(ε)。HPA約束的一致性驗證問題定義如下:

定義3給定一個HPA約束集合H={h1,h2,…,hn}(n≥2),判定是否存在滿足satH(ε)為真的訪問控制狀態(tài)ε,該問題被稱為HPA約束的一致性驗證問題(Consistency Checking Problem,CCP)。

定理2HPA約束的一致性驗證問題的計算復雜度為:CCP是NPNP問題,

證明:

證畢。

4 高階權(quán)限指派約束不一致性求解算法及仿真

以上已證明一般情形下的CCP問題是不可解問題(NPNP),即意味著在最壞情形下解決該問題將要耗費巨大的時間開銷,但是依然存在很多情形可以在可接受的時間范圍內(nèi)被有效解決。受到原始算法的啟發(fā),結(jié)合預處理及規(guī)約為SAT求解器的方法,本文設(shè)計一種針對一致性驗證問題的優(yōu)化求解算法,并通過仿真實驗驗證算法的有效性。

4.1 優(yōu)化算法

下文給出一個原始算法,并在該算法的基礎(chǔ)上進行優(yōu)化。

SA算法的時間復雜度為O(m×2|P|×|U|),該算法可以求解問題規(guī)模較小的CCP問題,但是隨著系統(tǒng)規(guī)模的增加其時間開銷呈指數(shù)級增長。因此,本文在SA算法的基礎(chǔ)上,設(shè)計一個基于預處理-規(guī)約SAT的優(yōu)化算法來求解該問題。

優(yōu)化算法(OA):該算法先經(jīng)過預處理降低需要考慮的HPA約束的數(shù)量,以及需要考慮的訪問控制狀態(tài)的數(shù)量,即刪除不影響一致性的HPA約束與明顯不滿足約束集合的訪問控制狀態(tài)。然后將CCP問題規(guī)約為SAT實例,使用SAT求解器可以結(jié)合SAT現(xiàn)有研究的優(yōu)點,并利用已有的SAT求解器提高計算效率。算法具體過程如下:

規(guī)約為SAT:求解CCP需要判定是否存在一個訪問控制狀態(tài)滿足一個HPA約束的集合。令hi=hpa〈Pi,Ui,si,ti〉,給定一個狀態(tài)ε,sathi(ε)為真意味著在Ui中不存在少于Si個用戶的權(quán)限并集包含Pi,存在不多于ti個用戶的權(quán)限并集包含Pi。由于集合覆蓋問題已經(jīng)被證明可以規(guī)約為SAT實例[3],sathi(ε)的驗證問題又可規(guī)約到集合覆蓋問題[10],因此可借用已有解決SAT求解器來求解。本文采用的是SAT4J,SAT4J是一個用Java實現(xiàn)的SAT求解器,它支持Pseudo-Boolean約束,與整數(shù)系數(shù)呈線性非等價關(guān)系。

規(guī)約步驟如下:給定一個HPA約束h=hpa〈P,U,s,t〉,對于每一個ui∈U,匹配一個參數(shù)vi,如果ui是一個基數(shù)為t并且基數(shù)大于等于k(k≤t)的用戶集合中的一員,且該集合覆蓋了P中的所有權(quán)限,則該參數(shù)為真,記為1,否則記為0。接下來給定2種類型的約束。對于每一個p∈P,令ui1,ui2,…,uix表示用戶是否被授予權(quán)限p。增加第1種類型的約束vi1+vi2+…+vix≥1,它確保P中的所有權(quán)限都被U′所覆蓋。存在m(m=|P|)個這樣的約束。繼續(xù)增加第2種類型的約束v1+v2+…+vn≤t(n=|U|),它確保|U′|≤t,只有一個這樣的約束。

4.2 仿真實驗與性能分析

為驗證本文優(yōu)化求解算法的有效性,本節(jié)進行了相應仿真實驗,運行的計算機配置如下:

CPU:Intel Core i7 4790 CPU 3.6 GHz;

RAM:DDR3 16 GB 1066MHz;

操作系統(tǒng):Windows 7 旗艦版。

該仿真實驗系統(tǒng)由Java編寫,并調(diào)用了SAT4J求解器。在實際應用中,一個訪問控制系統(tǒng)中的權(quán)限數(shù)量通常不會太大,而用戶的數(shù)量可能會比較大。因此,本實驗仿真了用戶與權(quán)限之比為2∶1以及10∶1不同環(huán)境下的OA算法的執(zhí)行效率。通過以下方法隨機生成的HPA約束實例進行實驗:

1)|P|=X,其中X是一個整形隨機變量,有X≥2,并且X小于系統(tǒng)中權(quán)限的數(shù)量MP。

2)|U|=Y,其中Y是一個整形隨機變量,有Y≥2,并且Y小于系統(tǒng)中用戶的數(shù)量MU。

3)s和t都是隨機整數(shù),其中s≤t,s的值域為[1,min(|P|,|U|)]。

4)當|P|和|U|被生成后,則從[1,MP]中隨機選取|P|個整數(shù){i1,i2,…,ix}作為權(quán)限P={pi1,pi2,…,pix}的右下標。同樣從[1,MP]中隨機選擇|U|個整數(shù)作為U={ui1,ui2,…,uix}的右下標。

實驗結(jié)果如圖1和圖2所示,其中運行時間由執(zhí)行10次算法求其平均值得出。OA(50),OA(30)分別代表執(zhí)行OA算法時仿真的訪問控制系統(tǒng)中有50個及30個HPA約束。算法的運行時間依賴于總共需要考慮的訪問控制狀態(tài)的數(shù)量,通過實驗結(jié)果可以看出,隨著系統(tǒng)規(guī)模的擴大,檢測需要的時間開銷呈拋物線增長,這是因為本文實驗借用SAT求解器來求解,一定程度上提高了其求解效率。在相同的系統(tǒng)規(guī)模下,系統(tǒng)中約束數(shù)量OA(50)比OA(30)多出20個約束,但是其系統(tǒng)開銷卻比OA(30)多了5倍以上,這是因為該問題為NPNP問題隨著約束數(shù)量的增加其系統(tǒng)開銷呈指數(shù)級增長。當用戶與權(quán)限的比例比較小時其時間開銷也比較小,在系統(tǒng)權(quán)限為20時用戶權(quán)限之比為2∶1的執(zhí)行時間小于用戶與權(quán)限之比為10∶1的時間,這是因為前者的訪問控制狀態(tài)的數(shù)量相對較少。

圖1 U∶P=2∶1時求解CCP問題的運行時間

圖2 U∶P=10∶1時求解CCP問題的運行時間

5 結(jié)束語

本文兼顧訪問控制系統(tǒng)安全性與可用性需求,提出一種高階權(quán)限指派約束。分析該約束的安全性驗證問題及一致性驗證問題,分別證明這2個問題在一般情形下為不可解問題(計算復雜度分別為NP-complete以及NPNP),同時結(jié)合預處理及規(guī)約為SAT求解器的方法,設(shè)計一種針對一致性驗證問題的優(yōu)化求解算法,并通過仿真實驗驗證該算法的有效性。下一步將在高階權(quán)限指派約束中考慮權(quán)限的權(quán)重,分析其對系統(tǒng)安全性與可用性的影響。

[1] 李瑞軒,魯劍鋒,李添翼,等.一種訪問控制策略非一致性沖突消解方法[J].計算機學報,2013,36(6):1210-1223.

[2] WANG X,SHI W,XIANG Y,et al.Efficient Network Security Policy Enforcement with Policy Space Analysis[J].IEEE/ACM Transactions on Networking,2016,24(5):2926-2938.

[3] LU J,LI R,LU Z,et al.Specification and Enforcement of Static Separation-of-Duty Policies in Usage Control[C]//Proceedings of the 12th Information Security Conference.Pisa,Italy:[s.n.],2009:403-410.

[4] LI N,WANG Q.Beyond Separation of Duty:An Algebra for Specifying High-level Security Policies[J].Journal of the ACM,2008,55(3):1-30.

[5] LU J,LI R,HU J,et al.Inconsistency Resolving of Safety and Utility in Access Control[J].EURASIP Journal on Wireless Communications and Networking,2011(1):1-12.

[6] LI R,LU J,LU Z,et al.Consistency Checking of Safety and Availability in Access Control[J].IEICE Transactions on Information and Systems Society,2010,E93-D(3):491-502.

[7] MAO B,WU S,JIANG H.Exploiting Workload Characteristics and Service Diversity to Improve the Availability of Cloud Storage Systems[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(7):2010-2021.

[8] RAWAT A S,PAPAILIOPOULOS D S,DIMAKIS A G,et al.Locality and Availability in Distributed Storage[J].IEEE Transactions on Information Theory,2016,62(8):4481-4493.

[9] LI N,WANG Q,TRIPUNITARA M V.Resiliency Policies in Access Control[J].ACM Transactions on Information and System Security,2009,12(4):1-34.

[10] SHEN L,WANG Z,ZHANG X,et al.Study on the Policy Conflict Detection in the Security Management Model[C]//Proceedings of IEEE International Conference on Signal Processing Communications and Computing.Washington D.C.,USA:IEEE Press,2015:1-5.

[11] ELKANDOUSSI A,ELBAKKALI H,ELHILALI N.Toward Resolving Access Control Policy Conflict in Inter-organizational Workflows[C]//Proceedings of the 12th IEEE/ACS International Conference of Computer Systems and Applications.Washington D.C.,USA:IEEE Press,2015:1-4.

[12] 吳迎紅,黃 皓,呂慶偉,等.基于開放邏輯R反駁計算的訪問控制策略精化[J].軟件學報,2015,26(6):1534-1556.

[13] LUPU E,SLOMNA M.Conflicts in Policy-based Distributed Systems Management[J].IEEE Transactions on Software Engineering(Special Issue on Inconsisteney Management),1999,25(6):852-869.

[14] 姚 鍵,茅 兵,謝 立.一種基于有向圖模型的安全策略沖突檢測方法[J].計算機研究與發(fā)展,2005,42(7):1108-1114.

[15] CHOLVY L,CUPPENS F.Analyzing Consistency of Security Policies[C]//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.,USA:IEEE Press,1997:103-112.

[16] PAPADIMITRIOU C H.Computational Complexity[M].[S.l.]:Addison Wesley Longman,1994.