一種高階權限指派約束的安全性與一致性驗證

,,,

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

0 概述

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

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

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

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

1 高階權限指派約束的定義

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

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

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

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

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

2 高階權限指派約束的安全性驗證

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

定義2給定一個訪問控制狀態ε和一個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〉在訪問控制狀態ε中得到滿足時,sathpa(ε)才為真。當s=1時,僅考慮參數t。因此,對于任意HPA約束hpa〈Pi,Ui,1,t〉,它要求Ui中至少存在一個用戶子集合能夠覆蓋權限集合Pi,而且該子集合的基數不超過t。如果基數為t的用戶集合給定了,驗證問題將可以在多項式時間內完成:計算該集合中所有用戶的權限并集,并檢測其是否為Pi的父集。

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

給定S,F和B,構造一個HPA約束f:對于S中的每一個元素,構造一個權限,令t=B,m是集合S的基數。構造一個HPA約束hi=hpa〈Pi,Ui,1,t〉,并構造出一個訪問控制狀態:對于F中每一個不同的子集Si(1≤i≤l),創造一個用戶ui∈{u1,u2,…,un},使得Si中的全部權限指派給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 高階權限指派約束的一致性驗證

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

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

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

證明:

證畢。

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

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

4.1 優化算法

下文給出一個原始算法,并在該算法的基礎上進行優化。

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

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

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

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

4.2 仿真實驗與性能分析

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

CPU:Intel Core i7 4790 CPU 3.6 GHz;

RAM:DDR3 16 GB 1066MHz;

操作系統:Windows 7 旗艦版。

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

1)|P|=X,其中X是一個整形隨機變量,有X≥2,并且X小于系統中權限的數量MP。

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

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

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

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

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

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

5 結束語

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

[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].計算機研究與發展,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.