有向图模型委托范文

论文关键词：信息安全访问控制委托有向无环图算法

论文摘要：委托是常见的一种安全策略形式，委托可以用带标识的有向图对其严格地形式化建模，称为委托图。给出了委托图的定义存储，委托图中实现委托的算法，委托图无环性判定算法，并进行了分析，讨论了委托图的性质。

1引言

委托是访问控制的一个重要方面，通常被处理为管理任务的一个特殊情形。管理任务必须规定好谁来产生新的安全规定，谁来更新或者撤销现有的安全规则。而委托意一味着修改现有的安全策略，也就是谁可以委托或者撤销现，包括用户一用户一机器和机器一机器委托…，本文只关注用户一用户委托，在这种情况下，主动实施委托的实体成为委托人(delegator)，获得本次委托权限的实体称为受托人(delegatee)。以下几种情况下，组织可能需要实施委托。

(1)职能备份。某人出差或者长时间休假，因而需要将其工作权力委托给其他人，以保证原工作职能的继续。

(2)权力下放。当组织建立或者重组时，权力可以通过委托的方式从高级职位向低级职位扩散。

(3)工作协同。组织间或者组织内部需要协同工作时，可能需要以委托方式给参与者授权。

委托具有许多特性，比如，委托的临时性，部分性，受限传播性(即是否允许多步委托)，单调性(委托者是否会失去委托的权限，其中单调性委托指委托者不会失去委托的权限，非单调性委托指委托者会失去委托的权限，又可以称为全权委托)。

委托可以用带标识的有向图对其严格地形式化建模，有向图具有成熟的算法。

2基本概念

本文约定U为普通用户，AU为系统管理用户，系统中所有用户UUAU，0为访问对象，P为用户对访问对象之上执行的权限，R为角色，角色就是权限的集合，N为自然数集。本文的定义，算法对于角色委托同样适用，只不过角色委托会更复杂，设计角色的继承等问题。定义1：委托授权状态：在访问控制系统中，某一时刻权限(包括角色)委托授权的全集称为该时刻委托授权状态(ps)。

授权状态可用有向图G(V，E)表示定义2：设G(V，E)是一个有向图，其中V是G的顶点集合，单射函数：vu把图G的每一个顶点映射为参与委托授权活动的惟一用户(委托人或受托人)，即对v∈V，ju∈U，使得(v)-u，E是G的带标识的有向边集合，对v，v∈V，如果占(v)对S(v，)实施了单调委托授权o；则从图的顶点v．到v，之间建立一条有向边(V，o；v，)，有向边的起点为v，终点为v，，边的标识为。如果(V)对S(v)实施了非单调委托授权o，则从图的顶点v．到v之间建立一条起点带有一个小黑点的有向边(V．，o；v，)，有向边的起点为v，，终点为v，，边的标识为o。每一条有向边。可以用一个三元组<盯，t，1／0>标识，其中a，t，1／o分别表示委托授权标识，委托授权时刻，o是(1)否(0)可被传播。

称G为委托授权的带标识有向图，简称委托图。授权根结点代表的是系统管理用户au，au∈AU，从该结点引出的有向弧对应系统授予用户的基本权限或者角色。根结点可以有多个，即可以有多个系统管理用户。为了简单起见，我们以一个访问对象0上的一个授权p为例来说明，如图1所示。其中系统管理用户all在时刻5把权限P委托授权给用户u，授权标识为CI，U可以继续委托；普通用户u在时刻10把权限P委托授权给用户u，，授权标识为o，，U，不可以继续委托；普通用户U．在时刻l5把权限P委托授权给用户u，授权标识为Ou可以继续委托；普通用户u在时刻20把权限P委托授权给用户u，授权标识为o，U不可以继续委托；普通用户u在时刻25把权限P委托授权给用户u，授权标识为，U不可以继续委托。

3存储结构

委托用有向图表示后，委托过程实质上变成了在有向图上增加图顶点和有向边的过程。相应地，委托撤销过程实质上变成了在有向图上删除有向边或顶点的过程。

为了讨论委托图上的插入、删除和查询等算法，定义委托图的链式存储结构。我们使用图的邻接表存储结构，图理论证明，当图的边比较稀疏的时候，用邻接表比用邻接矩阵节省存储空间，特别当和边相关联的信息较多时更是这样。

设图上有12个用户顶点，对图中每个顶点建立一个链表，顶点结构为：

VertexID是顶点惟一标识，一顶点代表一用户，也可以用DelegatorID表示。InDegree是顶点入度，表示该顶点的用户获得的委托授权个数，OutDegree是顶点出度，表示该顶点的用户委托的授权个数，FirstAre是用户的委托链域，指向该用户享有的第一个委托授权结点。

DelegateID是此次委托惟一标识，DelegateeID表示受托人，DelegateTime表示此次委托的时间，YNDelegate表示受托人是否能够把获得的权限继续委托出去，0是不可以，1是可以。NextArc指向同一委托人下一个委托授权结点。

采用邻接表作为存储结构，优点是对任意用户的查找是随机的，一旦用户找到，则该用户当前享有的授权总数和委托授权总数都能够找到。用户顶点可以使用数组存储，有利于实现用户随机删除和插入操作。另外应该有数据结构记录委托图的顶点数n，授权弧的条数k，用户数lUUAUl=m，其中n<=m。通过图的邻接表存储结构查找用户及该用户当前享有的授权个数和该用户委托出去的授权个数的时间复杂度为O(n)。

^O哥Cic：m=il但要判断任意两个用户之间是否存在委托关系，则需要搜索这两个用户的委托链表，不如采用邻接矩阵存储结构方便。

例子的存储结构如图2所示。

4委托实施算法

算法1委托实施算法输入:n)当前委托图G(v,E>(2)委托请求req(Q)，委托人u2，受托人u3输出:新的委托图G(V’，E’)Begin

(1)对委托请求req(6)的有效性进行判别，如果委托用户不是系统当前合法用户，则req(Q)为非法委托请求，返回原委托图G(V,E)。如果req(a)为有效委托请求，转步骤2(委托请求req(司的有效性可以加入很复杂的约束条件)。

(2)如果req(v)为有效委托请求，则如果G(V,E)中存在v},v},v}}v;，使得a(v;)=u2,并且8(v;)=u3，则创建以v，为起点，以v。为终点的标识有向边(v;,6,vj)。如果是非单调委托，则边的起点带一个小黑点。

如果G(V,E)中不存在v;,v;}v}，使得8(v;)=u,>则创建顶点v}(当req(司是有效请求时，v、必然存在)，再创建以v、为起点，以v;为终点的标识有向边((v,}},v;)o如果是非单调委托，则边的起点带一个小黑点。

5委托图性质

用户之间的委托关系是反自反的，反对称的和传递的，委托关系的传递性含义是:同一权限p，如果用户u、对用户咦实施了委托6}，用户呜对用户隽实施了委托吼，则称u，对u。进行了间接授权。自我委托现象即用户把自己享有的权限再授予自己，被看作为毫无意义的，因此应该有效防止。委托图应该也是反自反的，反对称的和传递的。循环授权被认为是不必要的，也是不安全的授权管理策略，它作为一条重要的授权管理策略在每一个访问控制系统中必须予以禁止。要保证用户之间没有循环授权，委托图中不应该出现环，委托图应该是有向无环图。

在任意时刻，图G(V,E)中不应该存在循环授权，Entropy(drift)-Entropy(syn)一Entropy(backup),syn代表数据同步过程。

4实验及分析

为分析服务漂移的效率搭建了一个测试环境，本地服务器群及远程服务器群都简化为一台服务器，对系统的服务漂移耗时(包括限制带宽的情况)进行了测试。测试的应用服务器主要配置为:2.4G的CPU,512M内存。本地服务器及远程服务器操作系统是WindowsXPSP3，灾备中心服务器为操作系统是RHELS从图3可以看出，系统服务漂移耗时在5秒左右，不同的网络带宽耗时相差无几。证明了该服务漂移方法是高效、迅速的。

5小结

本文针对一种远程容灾系统的服务漂移设计实现方法通过在灾备中心逻辑卷实时镜像本地服务器的数据，在灾难发生时，将灾备中心逻辑卷挂载到远程服务器的卷上，并由网关控制数据转发实现访问的重定向。该方法保证了应用服务在本地服务器与远程服务器的有效切换以实现应用级的容灾。新晨：