基于稀疏索引和哈希表的訪問控制策略檢索方法

高 瑞,韓 斌,王東升,劉嘎瓊

(江蘇科技大學(xué) 計算機(jī)學(xué)院，鎮(zhèn)江 212100)

訪問控制是一種安全技術(shù)，用于規(guī)范主體對客體的訪問，內(nèi)容包括主體認(rèn)證、控制策略實現(xiàn)和安全審計[1]．其中控制策略被用于判斷主體對客體的某些訪問操作是否能夠被執(zhí)行，它依托于訪問控制模型而存在．常見的訪問控制模型有：自主訪問控制模型(discretionary access control,DAC)[2]，基本思想是系統(tǒng)中的主體可以完全自主地將其對客體的權(quán)限授予給其他主體，具有自主性強(qiáng)、靈活性高的特點；強(qiáng)制訪問控制模型(mandatory access control,MAC)[3]，基本思想是系統(tǒng)安全管理員為每個用戶授予客體某一級別的訪問許可證，具有安全性強(qiáng)的特點；基于角色的訪問控制模型(role-based access control,RBAC)[4]，基本思想是將用戶與角色關(guān)聯(lián)，角色與權(quán)限關(guān)聯(lián)，用戶通過角色獲得訪問權(quán)限，具有方便權(quán)限管理的特點．

隨著大數(shù)據(jù)和云計算的快速發(fā)展，云計算環(huán)境下的數(shù)據(jù)安全訪問問題變得日益突出，傳統(tǒng)的訪問控制模型如DAC、MAC和RBAC等無法完成對主體動態(tài)授權(quán)和對客體細(xì)粒度訪問控制．針對上述問題，文獻(xiàn)[5]提出基于屬性的訪問控制模型(attribute-based access control,ABAC)，該模型通過引入實體屬性概念，把主體屬性、客體屬性、環(huán)境屬性進(jìn)行搭配作為對主體進(jìn)行動態(tài)授權(quán)的依據(jù)，通過制定策略對客體進(jìn)行細(xì)粒度訪問控制，因此在云計算環(huán)境下ABAC模型擁有更強(qiáng)的適應(yīng)能力．

近年來研究人員對ABAC模型下的策略表示形式[6-8]和策略檢索方法[9-11]進(jìn)行了多方面的研究．文獻(xiàn)[6]利用XML語言對策略進(jìn)行表示，能夠容易地表示復(fù)雜策略；文獻(xiàn)[7]利用決策圖表示策略，能夠直觀地展示策略內(nèi)部屬性的限制條件；文獻(xiàn)[8]對策略進(jìn)行了形式化描述，能夠更好地反映屬性和屬性值之間的關(guān)系且有利于策略檢索的實施；文獻(xiàn)[9]通過對策略表進(jìn)行冗余規(guī)則處理并利用基于語義樹的策略索引來提高策略檢索的效率；文獻(xiàn)[10]通過對策略表實施規(guī)則精化，縮減策略規(guī)模并采用多種緩存機(jī)制來提高策略檢索的性能．其中文獻(xiàn)[9]和文獻(xiàn)[10]針對的是用XML語言描述的策略且引用了第三方的策略評估引擎，所以在實施方面會受到平臺和框架的限制．文獻(xiàn)[11]提出了一種基于前綴標(biāo)記的策略檢索方法(下稱，標(biāo)記檢索法)，通過將訪問請求與訪問控制策略的前綴標(biāo)記進(jìn)行位運算，從而快速定位策略位置．文獻(xiàn)[8]對文獻(xiàn)[11]的方法進(jìn)行了改善，提出了基于屬性分組的訪問控制策略檢索方法(下稱，分組檢索法)將前綴標(biāo)記中的主屬性標(biāo)記進(jìn)行分組，從而縮小策略檢索范圍．文獻(xiàn)[8]和文獻(xiàn)[11]用前綴標(biāo)記表示策略中的屬性會對策略格式要求較高，具體表現(xiàn)在進(jìn)行檢索之前，策略中的屬性要嚴(yán)格按照規(guī)定順序排列好并且策略中沒有被要求的屬性也無法在策略中缺省，否則策略中的屬性無法與前綴標(biāo)記中的數(shù)值一一對應(yīng)，這使得策略中的冗余屬性較多，檢索效率降低．并且沒有考慮到在實際應(yīng)用中訪問局部性原理[12]，會造成訪問請求重復(fù)出現(xiàn)情況，從而進(jìn)一步消耗策略的檢索時間．

針對上述問題，文中使用形式化語言對策略進(jìn)行描述并且提出了基于稀疏索引和哈希表的訪問控制策略檢索方法(下稱，多級檢索法)來解決策略檢索效率較低的問題，利用策略表生成哈希緩存表、稀疏索引哈希表和稠密索引表來構(gòu)建一個多層級的檢索體系，縮小檢索范圍，提高檢索效率．

1 相關(guān)知識

1.1 ABAC模型

ABAC是一個通過對系統(tǒng)中實體屬性進(jìn)行計算從而得出主體是否能對客體進(jìn)行訪問的訪問控制模型．實體屬性指的是ABAC中的主體屬性(Subject)、客體屬性(Object)、環(huán)境屬性(Environment)和操作屬性(Permission)，所以通常用四元組(S,O,E,P)來描述ABAC模型．在ABAC模型下，主體訪問客體的過程如圖1．步驟1：主體對客體發(fā)起訪問請求；步驟2：ABAC訪問控制機(jī)制評估收集到的主體屬性、客體屬性、環(huán)境屬性和策略通過計算進(jìn)行決策；步驟3：根據(jù)決策結(jié)果判斷主體能否訪問客體．

圖1 主體訪問客體過程Fig.1 Process of subject access to object

步驟2中決策的過程其實就是利用收集到的主客體屬性和環(huán)境屬性到策略表中檢索到對應(yīng)的策略并且進(jìn)行匹配的過程，所以策略檢索是ABAC模型實施的重要環(huán)節(jié)，而策略檢索的效率將直接影響到ABAC模型的實用性．

1.2 策略檢索

訪問控制策略是系統(tǒng)對訪問請求屬性和屬性值的要求，通常描述訪問控制策略的形式有3種：訪問控制策略描述語言XACML；邏輯上的形式化；策略決策圖.文中采用形式化的方式來描述策略．

策略在形式上是由多個鍵值對構(gòu)成，鍵值對中的鍵是屬性名稱，值是屬性名稱的取值范圍．為了區(qū)分不同類別的屬性，主體屬性以s為標(biāo)識，客體屬性以o為標(biāo)識，環(huán)境屬性以e為標(biāo)識，操作屬性以p為標(biāo)識．對策略進(jìn)行形式化定義[8]．

定義1屬性鍵值對．用avp表示：avp?(AttrName=Value)．

定義2屬性謂詞值對．用apvp表示：apvp?(AttrName∝Value).其中：AttrName為屬性名稱，Value為屬性的取值，∝為關(guān)系運算符，∝∈(≤,≥,<,>,=,≠)．

定義3基于屬性的訪問請求．用request表示：request={avp1,avp2,…,avpn}．

定義4訪問控制策略．用policy表示：policy=auth?{apvp1,apvp2,…apvpn}.其中：auth∈(grant,deny),grant表示這是一條正向授權(quán)策略，deny表示這是一條負(fù)向授權(quán)策略．

定義5屬性匹配．當(dāng)request的屬性集合包含policy的集合，且在屬性名相同的情況下，request的屬性值符合policy屬性取值范圍的要求．

訪問控制策略檢索是系統(tǒng)在策略表中查找是否存在一條策略使得訪問請求能夠滿足這條策略的屬性及其屬性值的全部要求．如果訪問請求中的屬性和屬性值滿足了策略表中的某條策略對屬性和屬性值的要求并且此條策略是正向授權(quán)策略，那么發(fā)起訪問請求的主體就可以執(zhí)行自己請求的操作．這里將策略分為正向授權(quán)策略和負(fù)向授權(quán)策略是為了縮減策略檢索的范圍，如果訪問請求與負(fù)向授權(quán)策略匹配成功，則在策略表中立即停止檢索，拒絕請求．

通過舉例說明直接檢索法，標(biāo)記檢索法，分組檢索法在檢索過程中的差異，其中：policyn表示策略表中的第n條策略，簡寫為pyn；name簡寫為n；auth簡寫為a；grant簡寫為g；deny簡寫為d；sq,eq,cq分別為環(huán)境，客體，操作屬性變量，其中q為正整數(shù)；x為刪除文件；r為讀文件；w為寫文件;m,n,i,j,c,b,k,y,f為字符患或常量．

表1 ABAC部分策略表

若request={s2=a, s8=f, e9=33,o1=1,p3=r,p4=w}，直接檢索法將request與策略表中策略進(jìn)行逐條比較，首先s2=a不滿足py1中SA中的要求，檢索下一條py2，發(fā)現(xiàn)request不滿足SA中s3=b的要求，繼續(xù)檢索下一條，發(fā)現(xiàn)request滿足py3的所有屬性及其對應(yīng)的屬性值的要求，匹配負(fù)向策略py3，但是py3中的auth值為deny，所以request被拒絕．直接檢索法的不足之處在于每次都是將request和py的屬性和屬性值一起比較，因為大部分py屬性與request屬性都會匹配失敗，所以在進(jìn)行策略檢索時會浪費很多比較屬性值的時間．標(biāo)記檢索法改善了直接檢索法的不足，將py屬性先抽取出來與request的屬性進(jìn)行匹配，若屬性匹配成功才會繼續(xù)匹配屬性值．這時將request的屬性s2、s8、e9、o1、p3、p4與py1的屬性s3、s7、e3、o1、o3、p2進(jìn)行屬性匹配，發(fā)現(xiàn)s2不滿足py1的屬性要求．檢索下一條，發(fā)現(xiàn)py2要求s3=b，但request沒有s3這個主體屬性，所以繼續(xù)檢索下一條，發(fā)現(xiàn)request的屬性s2、s8、e9、o1、p3、p4與py3的屬性s8、p4匹配成功，這時繼續(xù)比較值，發(fā)現(xiàn)屬性值也匹配成功，匹配負(fù)向策略py3，訪問請求被拒絕．標(biāo)記檢索法的不足之處在于每次檢索時仍然和直接檢索法一樣對策略表進(jìn)行逐條查找，所以系統(tǒng)想要檢索的策略在策略表中的位置對檢索效率影響較大．并且兩種方法都沒有對可能多次出現(xiàn)的訪問請求做緩存處理．

2 策略檢索方法

針對直接檢索法和標(biāo)記檢索法在策略檢索范圍縮減和重復(fù)的訪問請求處理方面的不足，多級檢索法構(gòu)建了一個多層級的檢索體系，縮減策略檢索范圍，并且對訪問請求及其授權(quán)結(jié)果進(jìn)行緩存．通過稀疏索引表來縮減策略表中需要檢索的范圍，采用哈希表作為緩存快速判斷訪問請求是否已被檢索過，避免相同的訪問請求重復(fù)檢索造成時間浪費，提高檢索效率．

2.1 生成稀疏索引表

生成稀疏索引表的過程如圖2.

圖2 稀疏索引表的生成過程

將策略表中每一條策略的所有屬性及其對應(yīng)的索引值抽取出來放到稠密索引表中，其中稠密索引表中l(wèi)istKey列中內(nèi)容源于策略表中的policy列，policyIndex列與策略表中index列一一對應(yīng)，attrNum列是對listKey列中的屬性個數(shù)進(jìn)行統(tǒng)計．將稠密索引表中index列和attrNum列的部分記錄抽取出來，放到稀疏索引表中，其中稀疏索引表中sparseAttrNum列是稠密索引表中attrNum列去除了重復(fù)數(shù)值的集合，sparseIndex列是稠密索引表attrNum列中被抽取的記錄所對應(yīng)的index數(shù)值．在圖2中，policyIndex簡寫為pI；index簡寫為i；attrNum簡寫為aN；sparseAttrNum簡寫為sA；sparseIndex簡寫為sI．

2.2 用哈希表優(yōu)化策略檢索過程

為了進(jìn)一步提高策略檢索效率，縮減策略檢索范圍，文中檢索方法采用了兩張哈希表，第一張將已經(jīng)生成的稀疏索引表轉(zhuǎn)換成哈希表，第二張將哈希表作為策略檢索過程中的緩存來使用．圖3是用哈希表存儲稀疏索引表的數(shù)據(jù)，在查找時可以避免遍歷整個稀疏索引表，利用哈希表中的attrNum_key直接獲取index_value．在圖3中，attrNum_key簡寫為ak；index_value簡寫為iv．

圖3 稀疏索引哈希表的生成過程Fig.3 Process of generating sparse index hash table

圖4是用哈希表作為所有訪問請求的緩存表，其中hashKey存儲的是requestn的內(nèi)容，當(dāng)訪問請求滿足了策略集中某一條策略的要求且此條策略是正向策略，則hashValue存儲auth=grant，如果訪問請求不能滿足策略集中任一策略要求或此條策略是負(fù)向策略，則value存儲auth=deny．

圖4 哈希緩存表Fig.4 Hashcache table

2.3 基于稀疏索引和哈希表的策略檢索舉例

通過具體例子闡述多級檢索法的檢索過程，如圖5，其中requestn簡寫為reqn．

圖5 多級檢索過程Fig.5 Process ofmultilevel retrieval

給定4條不同類型的訪問請求，如表2．

表2 訪問請求表

request1檢索過程如下：首先檢查哈希緩存表中是否已經(jīng)存儲request1，此時哈希緩存表為空，所以沒有存儲，將request1作為hashKey存儲到哈希緩存表中，hashValue默認(rèn)存儲auth=grant；然后計算出request1中不重復(fù)屬性個數(shù)的值是7，查找稀疏索引哈希表中ak=7所對應(yīng)的iv=2，直接定位到稠密索引表中的i=2的位置，檢查request1中的屬性是否滿足listKey中屬性要求，發(fā)現(xiàn){s4,e1,e4,r3,p9,p20,p30}?{s1,s2,e1,e2,o1,o3,p1}，所以不滿足本條策略的要求，繼續(xù)檢索下一條策略，發(fā)現(xiàn){s1,s2,e1,e2,o1,o3,p1}?{s1,s2,e1,e2,o1,o3,p1}，滿足要求，pI=0，則定位到策略表中i=0時對應(yīng)的policy，發(fā)現(xiàn)request1中的屬性值滿足本條policy的要求且auth=grant，正向策略匹配成功，通過請求，不用更新hashValue值．

request2的檢索過程與request1的檢索過程基本一致，但request2所匹配policy的auth值是deny，負(fù)向策略匹配成功，拒絕請求．最后將auth=deny更新到哈希緩存表中request2所對應(yīng)的hashValue中．

request3的檢索過程如下：檢索哈希緩存表中是否已經(jīng)存儲request3，發(fā)現(xiàn)request3就是request1，直接獲取對應(yīng)的hashValue值為auth=grant，正向策略匹配成功，請求通過．

request4的檢索過程與request1的檢索過程基本一致，但是檢索到策略表發(fā)現(xiàn)request4中的o7=10不滿足策略表中i=13所對應(yīng)policy的o7≤0的要求，所以要回到稠密索引表中向下檢索，發(fā)現(xiàn)request4不能滿足下一條策略的屬性要求，沒有匹配成功，拒絕請求．將auth=deny更新到哈希緩存表中request4對應(yīng)的hashValue中．

多級檢索法的流程如圖6．

圖6 多級檢索法流程Fig.6 Flow chat ofmultilevel retrieval

由圖6可知，文中提出的多級檢索法，對于訪問請求request1和request4只需檢索一次哈希緩存表、一次稀疏索引哈希表、兩次稠密索引表和一次策略表即可得出結(jié)果．request2只需檢索一次哈希緩存表、一次稀疏索引哈希表、一次稠密索引表和一次策略表即可得出結(jié)果．request3只需檢索一次哈希緩存表．

3 仿真實驗及性能分析

為了驗證多級檢索法的檢索效率，需要分別測試直接檢索法、標(biāo)記檢索法以及多級檢索法，測試所用計算機(jī)的CPU型號是英特爾i7-6770HQ，內(nèi)存大小為16GB，操作系統(tǒng)是Windows10,集成開發(fā)環(huán)境是IntellijI DEA，編程語言是Java．其中直接檢索法和標(biāo)記檢索法實現(xiàn)了文獻(xiàn)[11]中的相關(guān)算法的描述，文獻(xiàn)[11]中的直接檢索法是標(biāo)記檢索法的對比方法．

3.1 空間消耗比較

空間消耗是指Java程序在運行時所要占據(jù)的物理內(nèi)存空間，空間消耗過大會觸發(fā)Java虛擬機(jī)JVM進(jìn)行垃圾回收，嚴(yán)重影響程序性能．采用JDK工具集中jconsole程序?qū)ava集成開發(fā)環(huán)境Intellij IDEA進(jìn)程進(jìn)行監(jiān)控，記錄Intellij IDEA在運行不同檢索方法程序時的堆內(nèi)存空間大?。涗浨靶枰謩佑|發(fā)JVM的垃圾回收器，將JVM的垃圾回收機(jī)制在程序運行時對程序的空間消耗的影響降到最低．

針對3種檢索方法在策略數(shù)量分別為10 000、20 000、30 000、40 000、50 000的環(huán)境中進(jìn)行測試．實驗結(jié)果如圖7，多級檢索法、標(biāo)記檢索法和直接檢索法的平均內(nèi)存消耗分別為100.72；88.19和83.96 MB．

圖7 空間消耗比較Fig.7 Comparison of space consumption

這表明多級檢索法相較于標(biāo)記檢索法和直接檢索法由于3張中間表緩存的存在需要消耗更多的堆內(nèi)存空間．標(biāo)記檢索法運行時平均堆內(nèi)存空間比直接檢索法大是因為標(biāo)記檢索法比直接檢索法多了1張中間表緩存．而直接檢索法沒有任何緩存，所以運行時平均堆內(nèi)存空間最?。?/p>

3.2 時間消耗比較

3種方法在檢索時間方面的消耗主要比較兩個方面：最壞情況下的檢索時間，以及一般情況下的檢索時間．

直接檢索法和標(biāo)記檢索法都是在策略表中從上到下逐條檢索，所以最好的情況是訪問請求匹配成功策略表的第一條；最壞的情況是訪問請求匹配成功策略表的最后一條．多級檢索法最好的情況是訪問請求已經(jīng)在哈希緩存表中，可以直接獲取檢索結(jié)果；最壞的情況是訪問請求屬性的個數(shù)與策略表中策略屬性個數(shù)的最大值相等并且匹配成功的是策略表中策略屬性個數(shù)的最小值所對應(yīng)的策略，這要求訪問請求必須添加大量冗余屬性鍵值對使得檢索策略時程序在稀疏索引表和策略表中來回跳躍檢索，降低了檢索效率．

根據(jù)策略的形式化描述編寫程序生成5份策略表，每份策略表中的策略數(shù)量分別為10 000，20 000，30 000，40 000，50 000．在這5份策略表中分別檢索能夠造成最壞情況的request所對應(yīng)的policy，檢索10次，取平均時間．3種方法在最壞情況的時間消耗，如圖8，標(biāo)記檢索法相比直接檢索法能夠減少平均26.48%檢索時間，多級檢索法相比直接檢索法能夠減少平均17.11%檢索時間．因為多級檢索法和標(biāo)記檢索法都屬于先檢索屬性，屬性匹配后才檢索屬性值，所以兩種方法檢索效率接近．而直接檢索法是直接檢索屬性鍵值對，沒有分級檢索，所以在檢索效率上不如標(biāo)記檢索法和多級檢索法．

圖8 最壞情況下的時間消耗Fig.8 Time consumption of the worst situation

圖8是3種方法在最壞情況下的性能表現(xiàn)，但這種極端情況在實際系統(tǒng)中難以出現(xiàn)，所以文中仍然使用之前選取的5份訪問請求樣本作為普通情況下訪問請求的樣本，策略表中的策略數(shù)量仍為10 000條，每份樣本中的比例構(gòu)成不變．

實驗結(jié)果如圖9，與直接檢索法相比，多級檢索法能夠減少平均67.49%的檢索時間，與標(biāo)記檢索法相比，多級檢索法能夠減少平均58.49%的檢索時間．隨著樣本中訪問請求數(shù)量的增加，多級檢索法與直接檢索法和標(biāo)記檢索法的差距會逐漸擴(kuò)大，這表明在實際應(yīng)用中，系統(tǒng)訪問請求并發(fā)數(shù)越大，重復(fù)的訪問請求越多，多級檢索法的檢索效率越高．

圖9 一般情況下的時間消耗Fig.9 Time consumption of general situation

3.3 算法分析和綜合性能比較

根據(jù)3種算法在空間和時間上的開銷比較，可以看出多級檢索法在算法設(shè)計時運用了以空間換時間的設(shè)計思想，通過運行時堆內(nèi)存空間的增加換取策略檢索時間消耗的減少．從理論上分析這3種算法，設(shè)策略集中有n條策略，每條策略中有m個屬性約束，request中有k個屬性鍵值對，根據(jù)上述對3種算法的描述可得直接檢索法算法時間復(fù)雜度為O(nmk)，標(biāo)記檢索法的時間復(fù)雜度為O(nm+mk)，多級檢索法的時間復(fù)雜度為O(cm+mk)，其中c的值在一般情況下遠(yuǎn)小于n．所以多級檢索法在一般情況下的時間消耗要少于標(biāo)記檢索法和直接檢索法．

表3是多級檢索法與其他方法在普通情況下的綜合性能比較，比較的維度有訪問控制模型、平均內(nèi)存消耗、平均時間消耗、需維護(hù)的表數(shù)目．

表3 與其他幾種方法的綜合性能比較

4 結(jié)論

訪問控制是實現(xiàn)系統(tǒng)安全的重要手段，而ABAC模型是一種能夠較好實現(xiàn)細(xì)粒度授權(quán)的訪問控制模型，其中實現(xiàn)細(xì)粒度控制的關(guān)鍵技術(shù)是策略檢索，策略檢索的性能優(yōu)劣將直接影響到系統(tǒng)的實用性．文中提出一種基于稀疏索引和哈希表的訪問控制策略檢索方法，對基于前綴標(biāo)記運算的策略檢索方法和基于屬性分組的訪問控制策略檢索方法中的策略表預(yù)處理和分級檢索思想進(jìn)行吸取和改善，引入三張中間表，構(gòu)建了一個多層級的檢索體系，縮減策略檢索范圍，提高策略檢索效率．實驗結(jié)果表明，多級檢索法在ABAC模型中的有著比直接檢索法和標(biāo)記檢索法更高的檢索效率．