基于交互式级联布隆过滤器的一体化网络访问控制缓存系统

祁晖 ，底晓强 ，李锦青 ，杨华民 ，姜会林

（1.长春理工大学 计算机科学技术学院，长春 130022；2.长春理工大学 空间光电技术国家地方联合工程研究中心，长春 130022）

基于交互式级联布隆过滤器的一体化网络访问控制缓存系统

祁晖1，2，底晓强1，2，李锦青1，杨华民1，姜会林2

（1.长春理工大学 计算机科学技术学院，长春 130022；2.长春理工大学 空间光电技术国家地方联合工程研究中心，长春 130022）

通过深入研究基于级联布隆过滤器的缓存方案，重新构造了基于角色的访问控制（RBAC）系统的缓存结构，设计并实现了基于交互式级联布隆过滤器的访问控制缓存系统。在访问控制决策点（PDP）上设计了专门的数据结构来存储基于角色的访问控制规则及其散列函数值，并根据这些信息高效地生成、更新辅助决策点（SDP）的级联布隆过滤器，降低了SDP对缓存存储空间的需求，提高了级联布隆过滤器的更新效率。该系统可应用于大规模、分布式的应用系统和网络系统，以加快访问控制速度，提升系统整体服务质量。

访问控制；RBAC；布隆过滤器；一体化网络；缓存

访问控制是保障系统安全的重要手段，基于RBAC的访问控制系统已得到了广泛应用，包括大规模分布式企业应用和网络应用［1-6］。以网络应用为例，访问控制系统的一般架构如图1所示。在该架构中，策略实施点（PEP）解析接入请求，然后从策略决策点获取访问控制决策以决定客户端是否可以接入网络。

在上述集中式访问控制架构中，PDP决定了整个访问控制系统的性能，且当其出现故障时，访问控制系统失效。为了解决这些问题，研究人员提出了分布式访问控制架构，如图2所示。该架构在接入点上引入了辅助决策点（SDP），用于缓存访问控制决策。当PEP接收应用请求时，会向SDP发送访问控制请求，如果SDP根据缓存的信息可以进行决策，则立即向PEP返回决策结果，否则，它会向PDP发送请求，由其根据访问控制规则作出决策，然后SDP会将PDP返回的决策结果缓存起来以备之后处理相同的请求。由于SDP与PEP在同一个节点，对于SDP可以处理的访问控制请求，访问控制决策过程将十分高效。另一方面，即使PDP出现故障，只要SDP缓存了足够的信息，访问控制系统依旧可以正常工作。

图1 网络应用的访问控制架构

图2 分布式访问控制架构

分布式访问控制架构因其较好的性能和容错能力，受到了极大关注。目前，已提出了不少SDP的缓存策略，其中，基于级联布隆过滤器的缓存策略被证明具有较好的时间和空间效率。本文改进了该策略，使其具有更低的存储空间需求及更高的管理性能。

接下来，本文首先介绍了访问控制缓存的相关研究工作；然后详细阐述了本文的方案，包括系统方案、实现原理和详细设计；之后通过仿真实验对本文方案的性能进行了验证；最后对全文做了总结。

1 相关研究

访问控制决策缓存是提高访问控制系统性能的一项重要措施，在许多系统中得到了应用，如文献［7］所设计的访问控制系统就在内存中创建了一个映射表，以主体和对象标识作为关键字，以压缩后的访问控制规则作为值。当主体访问某个对象时，访问控制系统首先在内存的映射表中查找访问控制规则，仅当内存中不存在相关规则时，系统才会到后端数据库中查找，并将其载入内存映射表。这种方式有效降低了访问控制系统的响应时间，极大提高了系统的吞吐量。但该方式是针对特定应用的，访问控制规则的压缩方法并不通用，同时由于需要存储主、客体标识，因此在拥有大量主、客体的环境下将占用大量内存空间或导致缓存命中率不高。文献［8］，［9］提出了一种分布式环境下的缓存策略，根据PDP的决策结果推断角色与权限的映射关系，然后将它们存储于SDP中。该策略支持基于RBAC模型的访问控制系统，通用性强，但由于缓存更新和决策时需要遍历缓存数据，因此响应时间较长。文献［10］提出了基于级联布隆过滤器的分布式缓存策略，该策略在SDP中使用级联布隆过滤器存储会话和权限关系。得益于布隆过滤器的特性，该策略的检索性能较好，且占用的存储空间稳定。但该策略的管理性能不佳，在更新会话权限关系时需要遍历整个集合。文献［11］比较了各种缓存策略，并指出基于级联布隆过滤器的缓存策略在时间效率和空间效率上均有较好的表现。文献［12］提出了一种使用相联阵列的硬件数据结构来缓存授权决策的方案，该方案支持基于访问控制矩阵和CPOL的缓存策略，但不支持基于级联布隆过滤器的缓存策略。本文优化了文献［11］中的基于级联布隆过滤器的实现方案（不少研究人员使用该文献的实现作为基准测试程序或使用了该文献的测试数据［12］），使其占用更少的存储空间，并具备更好的管理性能。

2 系统方案

2.1 系统架构

本文的系统架构如图3所示。

图3 分布式访问控制系统结构

本系统将RBAC策略（包括用户、角色、权限及它们之间的关系）集中存储于PDP节点；管理员与该节点交互更新RBAC策略；PDP节点还使用关系数据库存储每一级的布隆过滤器结构。

PDP将布隆过滤器结构通过网络发送给多个SDP，后者在内存中生成级联布隆过滤器；当管理员更新RBAC策略时，PDP会将更新消息发送给SDP，由后者更新内存中的级联布隆过滤器。

普通用户将访问控制请求发送给SDP，由SDP验证请求是否满足访问控制规则。

2.2 实现原理

本系统的核心数据结构是级联布隆过滤器，该结构的基础是布隆过滤器，它是一个时间和空间上都高效的用于检索的数据结构。假设有一个集合A，为了存储该集合中的元素，需要定义一个m比特的数组，以及一组哈希函数，每个函数独立地将A中的元素映射成0到m-1中的一个整数，即hi：U→{0，1，…，m-1}，对于所有的i=1，…，k，其中：U为A中的元素和不在A中的元素组成的全集，k为哈希函数的个数。当存储a∈A时，计算hi(a)，然后将数组中相应的位置1；当要确定某个元素e是否在A中时，计算hi(e)，然后检查数组中相应位的值是否为1，若任意hi(e)对应的位的值为0，则e∉A，否则认为e∈A。对于布隆过滤器，可能存在e∉A，但所有hi(e)对应的数组中的位的值均为1，即存在假阳性。另一方面，将一个元素加入布隆过滤器很简单，但要从中删除一个元素则并不容易，不能简单地将要删除元素的哈希值所对应的数组中的位置0，因为其他未删除元素可能需要将该位置1。为此，人们提出了计数布隆过滤器，它并不是一个m比特的数组，而是m个计数器数组，每个计数器占若干比特。当添加一个元素时，是将数组中相应位置的计数器加1，删除元素时，则将相应位置的计数器减1。

为了保留布隆过滤器的时间和空间效率，同时解决其假阳性问题，人们提出了级联布隆过滤器，即使用多级（多个）布隆过滤器。假设一个级数为d的级联布隆过滤器，第i级的布隆过滤器记为BFi，BFi存储的元素集合记为Ai。第1级布隆过滤器BF1存储集合A中的元素，即A=A1；A2是集合U-A1中所有对于BF1假阳性的元素集合；Ai是Ai-2中所有对于BFi-1假阳性的元素集合；Ad-1中所有对于BFd假阳性的元素将存入一个哈希表中，即Ad+1将以一个列表的形式存储。级联布隆过滤器的结构如图4所示。假定级联布隆过滤器分为4级，则Ai+1是Ai-1中所有对于BFi的假阳性元素所组成的集合，所以有A1⊇A3⊇A5和A2⊇A4，且A5并不存储到布隆过滤器中，取而代之的是使用哈希表来存储A5中的元素。对于元素E1∈A1且不属于其他集合，则验证E1是BF1成员时将返回true，而验证其是BF2成员时将返回false；对于元素E4∈A4⊆A2，则验证其是BF1，…，BF4成员时均返回true，但E4∉A5，因此E4∉A；对于元素E6∉Ai，对任意Ai都成立，因此在验证其时BF1成员时将返回false。

图4 级联布隆过滤器结构。

2.3 详细设计

文献［11］使用上文的级联布隆过滤器存储系统的会话信息——用户-权限关系，由于用户频繁登录退出系统，使得级联布隆过滤器中的内容频繁更新，而更新对于级联布隆过滤器是一个相对耗时的操作。为此，本文将相对稳定的角色-权限关系存储于级联布隆过滤器中。由于角色数通常远小于用户数，因此本文的级联布隆过滤器所需存储空间更小，生成和更新的效率更高。此外，本文在PDP端设计了专门的数据结构存储级联布隆过滤器的相关信息，实现了在每级布隆过滤器使用比特数组（而非计数器数组）来存储数据，从而进一步降低存储空间。

本文在PDP端除了将用户、角色、权限及它们之间的关系存储到关系数据库中，还设计了两个3元组用于存储级联布隆过滤器的相关信息。其中一个三元组为 T1=（level，index，count），其中 level是级联布隆过滤器的级别标识，index是布隆过滤器的索引，count是布隆过滤器的计数器，该三元组用于模拟级联布隆过滤器中的每一级计数布隆过滤器；另一个三元组为T2=（level，role，permission）二元组为（role，permission），其中level是级联布隆过滤器的级别标识，role是角色，permission是权限，该三元组用于存储级联布隆过滤器每一级的元素，包括最后的哈希表。

假设级联布隆过滤器的级数为d。当管理员添加一个角色-权限关系时，系统需要执行以下步骤：

（1）在关系数据库中添加角色-权限关系；

（2）确定全集U（角色-权限的笛卡儿积）是否有变化，假设要添加的元素为e（e表示添加的角色-权限关系），添加前的全集为U，添加后的全集为U'；

（3）使用BF1的哈希函数计算e的所有哈希值，然后根据哈希值在T1（第一个三元组所对应的关系表）中将所有level为1，且index为哈希值的计数器值加1；

（4）将三元组（1，e所对应的角色，e所对应的权限）添加到T2（第二个三元组所对应的关系表）中；

（5）判断集合U'-U-e中每个元素是否是BF1中的成员，对于不是BF1成员的元素，使用BF2的哈希函数计算其所有哈希值，然后更新T1中的相关计数器，并在T2中添加相应记录；

（6）设置变量 i=2，…，d+1，确定集合 Ai-2（在T2中查询所有level=i-2的记录）中所有对于BFi-1假阳性的元素，使用BFi的哈希函数计算它们的哈希值，然后更新T1中的相关计数器（当i=d+1时不用执行此操作），并在T2中添加相应记录。

（7）将步骤3至6中对T1的更新操作发送到SDP以更新缓存中的级联布隆过滤器。

当管理员删除一个角色-权限关系时，系统需要执行以下步骤：

（1）在关系数据库中删除角色-权限关系；

（2）确定全集U（角色-权限的笛卡儿积）是否有变化，删除前的全集为U，删除后的全集为U'；

（3）令集合E=A1-（U-U'）；

（4）对E中的每个元素e，使用BF1的哈希函数计算其所有哈希值，然后根据哈希值在T1中将所有level为1，且index为哈希值的计数器值减1；

（5）从T2中删除元素e所对应的记录；

（6）从E中删除e，重复步骤4，直到E为空；

（7）判断集合A2-（U-U'）中每个元素是否是BF1中的成员，对于不是BF1成员的元素，使用BF2的哈希函数计算其所有哈希值，然后更新T1中的相关计数器，并在T2中删除相应记录；

（8）设置变量 i=2，…，d+1，确定集合 Ai-2中所有对于BFi-1假阳性的元素，使用BFi的哈希函数计算它们的哈希值，然后更新T1中的相关计数器（当i=d+1时不用执行此操作），并在T2中删除相应记录。

（9）将步骤3至8中对T1的更新操作发送到SDP以更新缓存中的级联布隆过滤器。

本文在SDP缓存中存储的是角色-权限关系，并不包含用户信息，而实际的访问控制系统需要确定用户和权限的关系。为此，可以在用户登录系统后将用户及其关联的角色信息保存到用户端，并借助公钥加密系统对用户端的信息进行签名，以避免用户随意篡改登录信息。这样，用户在发送请求时，系统就能提取用户的角色信息，之后根据SDP中缓存的角色-权限关系确定用户是否拥有某个权限。

3 实验与分析

3.1 测试方案

本文将访问控制缓存系统应用于一体化网络环境，以测试其在大规模、分布式系统中的性能。一体化网络是近年受到广泛关注的一个新兴研究领域，它是一种融合地面互联网和空间网络，能在任何地点、任何时间、以任何方式提供信息服务高速宽带信息网络［13-17］。

一体化网络架构如图5所示。在一体化网络中，访问控制系统的缓存节点SDP可部署于网络的接入节点上，如地面无线基站或低轨卫星（LEO），而访问控制系统的决策点（PDP）则部署于地面互联网上。管理员维护PDP中的访问控制规则，即用户、角色、权限和它们之间的关系，然后PDP自动将级联布隆过滤器同步到基站或LEO上。当移动终端接入网络，或在不同网络间切换时，如从空间网络切入地面网络（从LEO切换到基站），或从地面网络切入空间网络（从基站切换到LEO），则接入节点可以直接利用缓存的级联布隆过滤器对用户进行访问控制。

图5 一体化网络架构

3.2 测试环境

本文的测试环境包括两个部分：一体化网络仿真环境和访问控制系统环境。前者利用GTK导出的真实卫星轨道数据及空间通信参数计算空间网络数据传输延迟，然后使用WebGL对一体化网络结构和数据传输过程可视化；后者使用Java技术开发，包括访问控制管理和访问控制缓存两个子系统。仿真环境如图6所示。

图6 一体化网络仿真环境

3.3 结果分析

本文主要比较了使用传统级联布隆过滤器和本文的改进方案在缓存空间占用上的差异，实验数据来源于文献［11］的公开数据，测试方法也与该文献相同，包括了缓存的创建，向缓存中添加数据、删除数据等一系列操作，从实验结果看，本文的改进方案确实需要更少的缓存空间，如图7所示。

图7 缓存空间占用对比

图8 接入空间网络时的访问控制延迟对比

此外，本文还测试了接入空间网络时，使用缓存（在LEO上完成访问控制）和不使用缓存（在地面完成访问控制）的访问控制延迟对比，如图8所示。从测试结果不难看出，对于空间网络这种高延迟环境，使用缓存能极大提高访问控制效率。

4 结语

本文将访问控制缓存系统应用到一体化网络环境中，使得网络接入点可以就近快速处理访问控制请求，提高了访问控制效率；同时，由于缓存采用了级联布隆过滤器，因此其空间占用较为稳定，并不会随着存储内容的巨大变化而明显改变。

与传统的基于级联布隆过滤器的访问控制方案不同，本文将角色-权限关系这种较为稳定的信息存储在级联布隆过滤器中，降低了缓存的更新频率。同时，本文在PDP端存储并计算级联布隆过滤器的关键信息，以加快其生成和更新速度。利用这些信息，SDP可以不使用计数布隆过滤器来存储数据，从而减少了存储空间的开销。

［1］李昊，张敏，冯登国，等.大数据访问控制研究［J］.计算机学报，2017，40（01）：72-91.

［2］刘庆云，沙泓州，李世明，等.一种基于量化用户和服务的大规模网络访问控制方法［J］.计算机学报，2014，37（05）：1195-1205.

［3］王于丁，杨家海，徐聪，等.云计算访问控制技术研究综述［J］.软件学报，2015，26（05）：1129-1150.

［4］冯朝胜，秦志光，袁丁，等.云计算环境下访问控制关键技术［J］.电子学报，2015，43（02）：312-319.

［5］Almutairi A，Sarfraz M，Basalamah S，et al.A distributed access control architecture for cloud computing［J］.IEEE Softw，2012，29（2）：36-44.

［6］Qi H，Ma H，Li J，et al. Access control model based on role and attribute and its applications on space-ground integration networks［C］. in 2015 4th International Conference on Computer Science andNetwork Technology （ICCSNT），2015.

［7］Borders K，Zhao X，Prakash A.CPOL：High-performance policy evaluation［C］.in Proceedings of the 12th ACM Conference on Computer and Communications Security，New York，NY，USA，2005.

［8］Wei Q，Crampton J，Beznosov K，et al.Authorization recycling in RBAC systems［C］.in Proceedings of the13th ACM Symposium on Access Control Models and Technologies，New York，NY，USA，2008.

［9］Wei Q，Crampton J，Beznosov K，et al.Authorization recycling in hierarchical RBAC systems［J］.ACM Trans.Inf.Syst.Secur.，2011，14（1）：3：1-3：29.

［10］Tripunitara M V，Carbunar B.Efficient access enforcement in distributed role-based access control（RBAC） deployments［C］.in Proceedings of the 14th ACM Symposium on Access Control Models and Technologies，New York，NY，USA，2009.

［11］Komlenovic M，Tripunitara M，Zitouni T. An empirical assessment of approaches to distributed enforcement in role-based access control （RBAC）［C］. in Proceedings of the First ACM Conference on Data and Application Security and Privacy，New York，NY，USA，2011.

［12］Bloom G，Simha R.Hardware-enhanced distributed access enforcement for role-based access control［C］.in Proceedings of the 19th ACM Symposium on Access Control Models and Technologies，New York，NY，USA，2014.

［13］姜会林，刘显著，胡源，等.天地一体化信息网络的几个关键问题思考［J］.兵工学报，2014，35（S1）：96-100.

［14］李凤华，殷丽华，吴巍，等.天地一体化信息网络安全保障技术研究进展及发展趋势［J］.通信学报，2016，37（11）：156-168.

［15］黄惠明，常呈武.天地一体化天基骨干网络体系架构研究［J］.中国电子科学研究院学报，2015，10（05）：460-467+491.

［16］于海洋，杨华民，姜会林，等.一种全球覆盖的多层星座链路分析［J］.长春理工大学学报：自然科学版，2014，37（03）：56-59.

［17］从立钢，杨华民，王杨惠，等.基于复制的DTN网络路由算法研究［J］.长春理工大学学报：自然科学版，2016，39（04）：119-124.

Access Control Cache System for Integrated Network Based on Interactive Cascade Bloom Filter

QI Hui1，2，DI Xiaoqiang1，2，LI Jinqing1，YANG Huamin1，JIANG Huilin2
（1.School of Computer Science and Technology，Changchun University of Science and Technology，Changchun 130022；2.National and Local Joint Engineering Research Center of Space and Optoelectronics Technology，Changchun University of Science and Technology，Changchun 130022）

This paper studies the scheme based on cascade bloom filter，reconstructs the cache structure based on role-based access control（RBAC），and designs and implements the access control cache system based on interactive cascade bloom filter.This system uses special data structure to store the role-based access control rules and their hash values on the policy decision point（PDP） and efficiently generates and updates the cascade bloom filter on the secondary decision point （SDP） based on this information，reducing requirements for cache storage space on the SDP and improving the updating efficiency of cascade bloom filter.This system can be used in large-scale，distributed application system and network system to speed up access control and improve the overall service quality of the system.

access control；rbac；bloom filter；integrated network；cache

TP393

A

1672-9870（2017）05-0099-05

2017-10-19

国家“863”计划项目（2015AA015701）；吉林省科技发展计划项目（20150204081GX）；吉林省教育厅科研项目（吉教科合字［2016］第378号）

祁晖（1983-），男，博士，讲师，E-mail：qihui@cust.edu.cn

底晓强（1978-），男，博士，副教授，E-mail：dixiaoqiang@cust.edu.cn