一种基于NFA查询重写的XML过滤技术

　　华东理工大学学报（自然科学版）一种基于NFA查询重写的XML过滤技术刘国海，虞慧群，杜丽萍（华东理工大学计算机科学与工程系，上海200237）制策略的NFA以及基于NFA的查询语句重写技术，有效地实现了独立于视图的、高效的XML精细粒度的存取控制。

　　可扩展的标志性语言（XML）为网络环境下的结构化数据表示和传输提供了技术标准，是近年来广泛用于Web服务的语言，加速了Web信息的共享。随着分布式和信息共享的快速发展，对XML信息实施高效、安全的存取控制的要求越来越高。现在，已经出现许多的支持细粒度存取控制的XML存取算法和支持高效过滤的过滤器但是大部分系统都是使用View-based的方法，或者直接从XML数据库中获得安全支持使用View-based的方法有一个非常明显的缺点就是创建和维护费用太高，不能得到用户的支持；基金项目：国家自然科学基金项目（60473055，60373075）；上海市浦江人才计划项目（05PJ14030）档的存取控制。

　　通讯联直接依赖XML数据库，从数据库中获得安全支持，这种方法也不能安全地应甩因此目前出现了能实现独立于视图（View-independent）且不依赖XML数据库的、细粒度的存取控制策略的过滤器，例如：Yfiltei过滤器就是一个高效的范围可调的XML数据过滤算法，但是系统要随时为新增加的查询语句创建不确定的自动机（NondeterministicFinite Automation，NFA），这样会大大增加系统的开销，降低系统效率，同时也没有很好地支持安全存取控制策略和考虑情景感知因素。Qfilter策略建立一个NFA来实现存取控制，通过NFA执行算法对用户提交的查询语句Q进行重写，以得到满足安全控制和情景因素的新查询语句Q，从而实现高效率的、实现情景感知的XML存取控制策略1RBAC模型中策略描述RBAC模型中的策略*显著的特点是简化授权官理，即通过角色（roles）分配许可（permission）给不同的用户（users），即在许可与用户之间增加了一个中间层roles本文中使用策略取代permission直策略是一个五兀组，其中object是策略所作用的对象，一般用Xpath语言描述；rolename是策略所起作用的角色；operation是策略所要做的操作类型，一*般有4种：read，write，update，delete；sign区分策略是允许访问+，还是拒绝访问-；Conditions是操作类型，指这些操作是逻辑运算或集合运算，如、=、乒、<、e等，只有当两个参数之间的关系满足operation时，策略才泛起作用。

　　作。

　　2由策略构建NFA 2.1基础定位路径的NFA自动机理论中的NFA由一个五元组构成，即NFAM=（Q，S，q，F），其中Q是状态的集合，包括初始状态S，可接受状态A；是输入元素的集合，包含各个输入元素、e>*等；S是传输函数集合；q是初始状态，本文的初始状态为SF是可接受状态的集合，本文中为A（Ai关联一个元组合）在NFA中，所有的策略语句都可以在一个NFA中描述清楚，在NFA中从一个状态到另一个状态的转换标识都依赖object路径中的每个定位步每条XPath语句都由4种基础定位路径组/，其中“x”是特定用来表示DTD中所定义的所有元素，而“*”是一个通配符，用来匹配表达的符号。为XPath语句的4个基础路径所对应的NFA碎片（NFAfragments），图中一个圆圈表示一个状态，两个同心圆圈表示一个可接受状态，每个箭头的连线表示一次转换，与连线一起的符号为转换的标识，表示只有输入匹配的元素才能通过这条连线的转换到下一状态。符号2.2由策略构建NFA信息关联到接受状态中表达，构建算法如下：建立初始状态S，将S加入M=（Q，S，q），F）中的状态集合Q，并将S作为初始状态q得到**个基础定位路径，查看是否存在与该定位路径匹配的、从当前状态S输出的转换，如有，则将当前状态转到下一匹配状态，并转到步骤没有，则建立新的转换，如果是/x*路径，就建立新状态i，并建立从状态S到状态i的传输，以元素x或*为该转换命名；如果是//x/*路径，就建立新的两个状态ij，并如中所示的XPath语句的基础定位路径构建NFA碎片的方法，建立新的转换；*后将新建的状态加入到状态集合Q中，将输入的元素加入到集合，中，将新的转换建立新的传输函数，并加入S中。

　　骤，所以4一舰的路只被表?次ecicpu始查看XPath语句是否结束，如果结束转到步骤4；否则继续继续取得object中的XPath语句的基础定位路径，如步骤2?样查看是否有匹配的转换，有则当前状态转到匹配的下一状态，并重新开到自动机M中，重新转到步骤3是否已经为可接受状态，如果是则转到步骤5，否则将其改名为Ai，并加入到可接受状态集合F中。

　　态A关联的集合中（对于每个可接受状态Ai，关联查看是否还有新的策略，如有则转到步骤2，没有则NFA建立完成2.3构建医疗系统策略NFA在医疗系统中，病人的医疗记录信息及其疾病信息对不同的角色有不同的访问权限，比如医生可以看到自己部门病人的个人信息和所有的医疗记录与分析；护士可以看到她负责的部门的病人记录中的名字、诊断、测试信息，但是不能查看病人的调查结果值和疾病信息；病人的家属也只能看到病人记录中的名字、诊断、测试信息，但是不能查看病人的调查结果值和疾病信息；病人也只能看到病人记录中的名字、诊断、测试信息，但是不能查看调查结果值、疾病信息和X光的检查结果。医疗机构的系统存取控制策略如下：系统首先建立初始状态s，取得策略P，并由object取得基础定位路径files，建立新状态i，并建立从状态S到状态1的转换files，再取得路径/record，同样建立新的状态2，建立从状态i到状态2的转换record，*后使用同样的方法建立路径/产，为所选策略建立的NFA图，*后object的XPath语句结束，状态4为可接受状态，改名为Ai并关联一个元组的集合　　/x“是否在激活状态的转换标识中出现，如果出现，就将对应的转换末状态ID（statelD增加进目标状态的集合如果e转换出现在激活状态的转换标识中，查看后面是否有以”*“标志的自我循环的状态，如果有，就是一个子状态即”/child“，需要激活自我循环的状态，按照前面的3个原则进行递归处理新建一行表，其中步骤为i，新查询语句为= /x”，并将新增加的目标状态都增加到Qi'关联的状态集合中。

　　/x“的末状态ID增加进目标状态的集合，并新建表行，步骤为i其中新查询语句为Q；'Q；=Qn”/x“，并将新增加/=”，并将新增加的目标状态都增加到Qi关联的状态集合中。

　　如果e转换出现在激活状态的转换标识中，查看后面是否有以“*”标志的自我循环的状态，如果有就是一个子状态即“//-hild‘，需要激活自我循环的状态，按照前面的2个原则进行递归处理新建一个临时栈Z2和关联表，将激活状态子树中的所有状态都增加进Z2的目标状态集合中，并将从激活状态到其子树中的任一状态的路径作为该状态的新查询语句，并将该状态增加进关联状态的集合，*后将Z2的目标状态作为激活状态，转到步骤2对于临时栈中的激活状态对路径”进行匹配，依照前面确定的路径“/x”、不确定的路径“/=”算法进行处理*后将临时栈Z中的目标状态都增加进实时栈Zi的目标状态中，Z中的表新建一行，步骤为i，其中新查询语句为ZiQi'且ZiQi'=状态，*后释放临时栈Z2及关联的表的情况是当查询语句为“严严…严”，运行时就要算复杂度为O（n）i，其中的转换数廿ftblishing h邱：当前的激活状态都被执行后，目标状态的集合将被压进实时栈Zi的顶端，在下个事件处理中作为激活状态3.1.3目标状态处理object路径输入完后，取出目标状态，删除非可接受状态对于其中的可接受状态A，取出其关联集合其集合中的元素为元组面的算法：查看集合是否为CD，是则从目标状态中删除该可接受状态Ai，重新取得可接受状态否则取得集合中的一个元组，继续进行步骤2角色，如果不是就删除元组，并转到步骤1同，如果不是就删除元组，并转到步骤1一个condition不满足，则删除元组，并转到步骤1将所有的目标状态处理后，取得P集合，对于其中的可接受状态A+1、A2、…、A+，从表中得到与其相关联的新查询语句Qt，3.2计算复杂度过滤器的计算复杂度包括过滤器创建和执行两个部分。对于过滤器的创建，其计算复杂度为O（n），其中n是策略的XPath语句的子路径数；对于过滤器的执行分以下3种情况讨论://’路径时，过滤器运行该查询语句时的计算复杂度为O（m），其中m是查询语句的子路径数。

　　当查询语句包含“路径时，其运行的计遍历整个NFA //‘路径时，其运行的计算复杂度为（m*ni*2*…*n，其中m是查询语句的子路径数，k是查询语句中”//’的数目，ni是当遇到第i个“/广时，当前状态下子NFA的转换数由以上分析可以看出，整个过滤器的计算复杂度是比较低的，因为”/“在查询语句中出现的几率比较小，连续出现”//=//=…//=“的情况几乎没有，所以计算也不会很复杂，因此过滤器是非常适合实际应用的3.3实例以医疗系统所建立的NFA（）为例，系统执行过程如所示即files/record//*，先进行初始化（initial），建立实时栈Z及关联的表1，并将初始状态S压入栈中，新建表行步骤为1，新查询语句为，关联的状态集合为S；取得路径files，因为激活状态为S，其匹配的转换末状态为1，将1增加进目标状态集合中，并新建表行，步骤为2，新查询语句为files，关联的状态集合为1；当取得路径//=，对照算法，新建临时栈Z及其关联表2，以状态2为根结点的子树的所有状态都增加进Z目标状态集合中，将从激活状态2到其子树中的任一状态的路径作为该状态的新查询语句，并将该状态增加进关联状态的集合以栈Z2目标状态激活，对”/test“路径进行匹配，得到目标状态集合及其新查询语句，将结果增加进实时栈Z1的目标状态与表1的新行如表1所示，*后得到的目标状态集合为3A1A5，根据算法删除非可接受状态3，还有可接受ber，所以将A5加入P的集合中，根据算法：表1查询语句执行过程表2处理”/严“路径*后得出改写后的查询语句Q'为：，满足存取控制策略，可直接进行查询。

　　4结束语随着分布式网络和信息共享的发展，对XML信息的安全存取控制越来越受到重视为不同的用户分配不同的权限，保护XML信息不被没有授权的用户访问等都是非常必要的安全措施。由于网络硬件的飞速发展，网络信息共享的用户剧增，给信息共享系统带来沉重的负担。如何设计一个高效的，范围可调的存取控制模型是现实迫切的需求本文基于RBAC的存取控制模型，进行了一些改进，建立了一个感知情景的存取控制模型，同时建立了策略的NFA图，提高了系统的效率。但是，其中还有一些地方并不完善，还需要对情景模型进行补充，还没有考虑对查询语句中断定语句的支持，在以后的工作中将进一步完善。

(完)