| 标题 | 基于后序遍历请求树的访问控制策略匹配算法 |
| 范文 | 边力++王炜++姬瑞龙++王永强++郭睿志 摘 要：为解决传统访问控制策略匹配算法中因产生大量无用路径而导致性能低下的问题，提出了一种改进的基于后序遍历请求树的策略匹配算法。该算法对请求树的节点进行后序遍历，并采用及时截止剪枝方法，避免了大量无用路径的产生，有效降低了匹配输出结果大小，提高了策略匹配效率。实验证明，该算法较之传统的策略匹配算法大大提升了性能。 关键词：策略匹配；后序遍历；访问控制 DOIDOI：10.11907/rjdk.151962 中图分类号：TP312 文献标识码：A 文章编号文章编号：1672-7800（2015）012-0058-05 0 引言 访问控制策略匹配的目的是在访问控制策略库定义的策略集中，找到适用于访问控制决策请求的策略，并利用这些策略对访问请求进行判决。如果找到一条策略，它的目标中的主体、客体、操作等信息与访问请求中相应的值相同，则该条策略适用于该请求，完成一次策略匹配。当策略集中所有这样的策略被查找出来时，策略匹配过程完成。 在一些大型的信息系统中，由于策略考虑的安全属性较多，加之策略库中的策略规模庞大，因此一个好的策略匹配算法尤为重要，它能有效提高大规模策略匹配的效率。现有的许多模式匹配算法[1-3]的思想都是对请求树的节点进行先序遍历，且需要遍历所有路径，这样会产生大量的无用节点和无用路径，如果将这些算法用于大型系统，则随着策略数量的增加，策略匹配的性能会急剧恶化。 为了改进策略匹配效率，使其适用于复杂的匹配规则和庞大的策略库，本文基于经典的PathStack算法[1]，提出一种改进的基于后序遍历请求树的策略匹配算法。在策略匹配过程中，为了避免搜索大量的无用节点，算法对请求树的节点进行后序遍历，以保证匹配至某个节点时， 其之前的节点都是匹配的；同时在匹配过程中，采用一种称之为“及时截止剪枝”方法，即当发现存在不匹配情况时，及时将不匹配的策略子树“连根剪去”，避免搜索大量的无用路径。 1 相关理论 1.1 访问控制机制 访问控制机制功能由请求处理、访问控制预处理、策略判决和决策执行4个部分组成，如图1所示。 图1 访问控制机制功能 请求处理和决策执行功能由策略执行点（PEP，Policy Enforcement Point）完成，主要负责与上层应用交互，接收来自用户的访问请求，将其转换为策略决策点可识别的决策请求，并将策略决策点作出的访问控制判决结果返回给上层应用，由上层应用访问相应的文件。 访问控制预处理和策略判决功能由策略决策点（PDP， Policy Decision Point）完成，主要负责从PEP获取决策请求，从请求中提取安全标记内容，并和访问控制策略库中的策略匹配，然后依据匹配的策略对决策请求作出判决，将判决结果返回给PEP。 访问控制策略库用于存放由安全管理员配置的访问控制策略。PDP通过与访问控制策略库交互，从策略库中匹配出与请求相关的安全策略。 访问控制机制处于操作系统的内核层，介于I/O管理器与文件系统之间。I/O管理器捕获用户发出的文件访问请求，并送至访问控制机制对其判决。如果判决的结果是“允许访问”，则访问控制机制将请求继续向下传送至文件系统，由文件系统驱动访问；如果判决的结果是“拒绝访问”，则访问控制机制丢弃该请求，并向应用层返回结果。 1.2 扩展访问控制标记语言XACML 扩展访问控制标记语言XACML（eXtensible Access Control Markup Language）是由结构化信息标准促进组织OASIS（Organization for the Advancement of Structured Information Standards）于2003年提出的基于XML的访问控制描述标准[4]，它继承了XML通用性、平台无关性、可扩展性等优点。在XACML中定义了一种访问控制策略描述语言及数据类型、函数和组合算法等。 在访问请求转换过程中，需要将访问控制模型中的元素转换为XACML中的元素，元素映射关系如表1所示。 XACML的决策请求通常以 XACML的决策请求还可用请求树的形式表示，如图2所示。 图2 请求树 当访问请求转换完成后，请求处理部分将转换后的决策请求发送给PDP，由PDP依据决策请求进行策略匹配等后续操作。 1.3 PathStack算法原理 对于一个查询Q，其根节点为q，对应一个栈Sq和一个流Tq，流Tq代表查询节点q在XML文档树中对应的所有数据节点的有序列表，其编码方式为区域编码[5]，且Tq中所有节点按编码的begin值排序。对查询Q中任意查询节点q，其双亲节点为parent（q），对应的栈分别为Sq和Sparent（q）。栈Sq中的每一个数据节点除了存放该数据节点的区域编码外，还需要存放一个指针P，指向该节点在双亲栈Sparent（q）中最近的祖先节点。通过指针P，所有节点的栈就构成了一个栈链[6]。 PathStack算法实现时，先将查询树分解成几条简单的路径，再对每条路径分别匹配，最后将匹配结果合并，完成查询，如图3所示。 图3 节点栈链 图3（a）是一个XML文档中数据节点树其中的一个枝，图3（b）是其栈链。由于C1指向B2且B2指向A2，因此（A2， B2， C1）是匹配结果；在SA栈中，由于A1位于A2之下，因此A2是A1的后代，因此（A1， B2， C1）是匹配结果；在SB栈中，由于B1位于B2之下，因此B2是B1的后代，因此（A1， B1， C1）也是匹配结果。 2 匹配算法 2.1 算法思想 将请求树分解为多条路径，对于每条路径，按后序遍历的方式自底向上对节点逐个匹配，当匹配至请求树的根节点时，先序输出一个匹配结果，即从根节点到叶节点依次输出。如果一条路径的第n个匹配结果与前一条路径的第n个匹配结果的根节点不相同，则剪去策略树中这两个匹配结果对应的根节点及其子节点，形成一个新的策略树，然后在新的策略树中递归调用该过程。如果最后每条路径的匹配结果存在相同的根节点，则匹配成功，否则匹配失败。 2.2 匹配过程 下面先通过一个实例来说明策略匹配过程。为方便描述，假设策略库中XACML策略集树如图4所示。 为了区分相同的节点，应对策略集树中的每个节点进行编码。本算法采用目前最流行的编码方案，即区域编码。每个节点用四元组（docno， begin，end， level）来表示该节点在XACML策略树中的位置，其中docno表示XACML文档标识，通过docno，可以表示存储于不同文件中的策略；begin和end分别表示深度优先遍历策略树时节点的起始和结束位置；level表示节点在策略树中的层次。需要进行策略匹配的请求树如图5所示。 图4 XACML策略集树 图5 待匹配的请求树 匹配的过程如下： （1）将请求树分解为3条路径，即：① Target/Subject/Alice；② Target/Resource/File3；③ Target/Action/read。 （2）对每条路径进行匹配。对于第①条路径的节点，从节点Alice开始由底向上匹配，得到的匹配结果为： Target （1，5：15，5）/Subject （1，6：8，6）/Alice （1，7：7，7）； Target （1，65：75，5）/Subject （1，66：68，6）/Alice （1，67：67，7）。 对于第②条路径的节点，从节点File3开始由底向上匹配，得到的匹配结果为： Target （1，34：44，5）/Resource （1，38：40，6）/File3 （1，39：39，7）。 （3）对匹配过程及时截止剪枝。匹配第②条路径得到的第一个匹配结果的根节点为Target （1，34：44，5），而前一条路径的第一个匹配结果的根节点为Target （1，5：15，5），因此剪去策略树中这两个匹配结果对应的根节点Target （1，34：44，5）和Target （1，5：15，5）及其子节点，形成的新策略树如图6所示。 图6 及时截止剪枝之后的策略树 继续对新策略树递归进行上述过程，得到3条路径的最终匹配结果为： Target （1，65：75，5）/Subject （1，66：68，6）/Alice （1，67：67，7）； Target （1，65：75，5）/Resource （1，69：71，6）/File3 （1，70：70，7）； Target （1，65：75，5）/Action （1，72：74，6）/read （1，73：73，7）。 3条路径都有相同的根节点，则匹配成功，找到了与决策请求对应的策略，如图7所示。 2.3 算法描述 该策略匹配算法可以用以下伪代码描述： Algorithm PolicyMatch（Q） Input： 根节点为r的请求树Q Output： 匹配结果 1 for each path[i] in Q 2 PostOrder（path[i]） //对于Q中的每条路径后序遍历 3 for each node[j] in path[i] 4 MatchfrompolicyTree（node[j]） //对每条路径中的节点匹配 5 if（isRoot（node[j]）） 6 PreOrderOutput（result[i， j]） //匹配至根节点时先序输出结果 7 end if 8 end for 9 if（i>0） 10 if（Root（result[i， 0]）！= Root（result[i-1， 0]）） //及时截止剪枝 11 StopMatch（） //停止该路径的匹配 12 Cut（Root（result[i， 0]）） //剪枝 13 Cut（Root（result[i-1， 0]）） 14 end if 15 end if 16 end for 图7 策略匹配结果 通过策略匹配过程可以看出，上述策略匹配算法具有以下特点： （1）由于匹配的过程是按请求树节点后序遍历的顺序，因此可以保证当匹配至某个节点时，其之前的节点都是匹配的，避免了大量无用节点的产生。 （2）通过实时检测匹配输出结果的根节点，采用“及时截止剪枝”方法，有效降低了匹配输出结果的大小，提高了策略匹配效率，避免了大量无用路径的产生。 3 算法性能分析 3.1 时间复杂度 对于一个请求，假设请求树中每条路径需要匹配的节点数为n，则匹配一条路径的时间复杂度为O（n），如果匹配的路径总数为m，则算法的总体时间复杂度为O（m*n）。 如果使用经典的策略匹配算法，则在最好和最坏的情况下，都需要遍历所有路径和所有节点。因此，两种情况的时间复杂度相同，均为O（m*n）。 如果使用基于后序遍历请求树的策略匹配算法，在最坏的情况下，所有路径中的所有节点都需要匹配和输出，即所有策略都与请求树匹配，则该算法与经典算法的时间复杂度相同，为O（m*n）；最好的情况下，匹配第一条路径时即得出在策略集中没有匹配的策略，则时间复杂度为O（n），此时匹配效率要比经典算法高得多。 假设经典算法匹配的路径总数为m1，本算法匹配的路径总数为m2，由于在匹配的过程中一旦发现不匹配的节点就及时停止对该路径的匹配并剪去该路径，则m2≤m1。假设本算法中，路径匹配的概率为p（0≤p≤1），即m2=pm1，则平均时间复杂度为O（pm1*n）。当p越小时，需要匹配的路径数就越少，该算法的平均时间复杂度就比经典算法越低，可见该算法的匹配效率比经典算法得到了一定的提高。 3.2 实验分析 将该算法应用于主机保密管控系统。系统通过控制台与服务器和客户端交互，利用文件安全标记对客户端文件强制访问控制。安全标记包括主体、密级、空间、时间、只读等多个属性。 实验通过对加标记的文件进行读取操作，分别测试应用PathStack算法和本文算法的访问控制机制对文件处理性能的影响。当对一个文件读取时，需要按路径层次遍历文件的存储位置，因此在每层路径中都要进行访问控制决策。通常系统中文件存储的路径深度不会超过10层，因此本实验选取一个大小为2M的文件为样本，将其分别存储于1～10层路径下，测试加上访问控制机制前后各层中文件读取的时间，并进行对比分析。 （1）实验样本。待测文件：一个2M的文件File1。文件标记如表2所示。 表2 文件安全标记 标记字段[]保密级别[]使用空间[]使用时间[]使用主体[]只读标记[]打印标记 字段值[]confidential[]any[]8：00-18：00[]any[]0[]1 主体标记：主体的当前许可级别fc为confidential，最大许可级别fs为secret，许可级别的范围[lC-RH， lC-WL]为[unclassified， secret]。访问控制策略数量：10条。 （2）测试环境。处理器为Intel Pentium 4 2.4GHZ，内存为1.0GB，操作系统为Windows XP SP3。 （3）测试方法。对每层的文件读取操作各重复10次，并计算平均值。 （4）测试结果。实验数据如表3所示。 数据以折线坐标图表示，见图8。 图8 文件读取时间开销比较 可以发现，随着文件存储路径深度的增加，时间开销增加的比例也呈上升趋势，这是由每层路径增加的访问控制决策导致的。但是开销增加的比例并不随着路径深度线性递增，因为文件处理时间开销的增加不仅取决于文件存储的路径深度和每层路径增加的访问控制决策，还受到文件系统和策略匹配成功概率等因素的制约。从实验可以看出，本文提出的算法与传统的匹配算法在性能上提升很大。 4 结语 本文基于经典的PathStack算法，提出一种改进的基于后序遍历请求树的策略匹配算法。算法对请求树的节点进行后序遍历，并采用及时截止剪枝方法，避免了传统策略匹配算法中搜索大量无用路径的问题。实验证明该算法提高了策略匹配效率，适用于复杂的匹配规则和庞大的策略库。但是该算法的性能还依赖于匹配成功的概率，在最坏的情况下仍要遍历所有路径，下一步将重点研究不依赖匹配成功概率的算法。 参考文献参考文献： [1] BRUNO N，KOUDAS N，SRIVASTAVA D.Holistic twig joins：optimal XML pattern matching[C].In：Proceedings of the ACM SIGMOD International Conference on Management of Data， Madison， ACM Press， 2002： 310-321. [2] LU J，LING TW，CHAN CY，et al.From region encoding to extended dewey：on efficient processing of XML twig pattern matching[C].In：Proc. of the 31st International Conference on Very Large Data Bases， Trondheim， ACM Press， 2005： 193-204. [3] 谢辉. 基于UCON改进模型的授权管理关键技术研究[D]. 郑州： 解放军信息工程大学， 2009. [4] SIMON GODIK， TIM MOSES.Extensible access control markup language（XACML） Version 1.0[S].OASIS Standard， 2003. [5] ZHANG C， NAUGHTON J，DEWITT D，et al.On supporting containment queries in relational database management systems[C].Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data， New York， ACM Press， 2001： 425-436. [6] 黄渊. XML数据的编码方案与结构连接算法研究[D]. 武汉： 华中科技大学， 2006. （责任编辑：杜能钢） |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。