来源:2-2 第 1–16 页。图的方向和节点类型是本节的关键。
1. 用图代替矩阵#
节点表示主体或客体,有向边 A --r--> B 表示 A 对 B 具有 r 权限。
- r/w 等是访问数据的权限。
- t(take)和 g(grant)是改变权限关系的能力。
- 只有主体能主动执行规则,不能让纯客体像进程一样主动做操作。
不要因为课件图中只有简单形状,就忽略边的方向;也不能把一般保护图一概看成无环图。
2. 四种规则#
| 规则 | 前提与效果 |
|---|---|
| Take | A 对 B 有 t,B 对 C 有 α,则主体 A 可获得对 C 的 α |
| Grant | A 对 B 有 g,A 对 C 有 α,则主体 A 可把对 C 的 α 给 B |
| Create | 主体创建新节点,并按规则建立权限边 |
| Remove | 主体删除自己相应边上的部分权限 |
Take 是取走/复制对方已有权,Grant 是赠送自己已有权。 规则添加的权限不会凭空换成任意其他权限。
3. 两个最小推导#
已知:Alice --t--> Bob,Bob --r--> File 可推出:Alice --r--> File 已知:Alice --g--> Bob,Alice --w--> File 可推出:Bob --w--> File |
第二种情形需要 Alice 是执行 Grant 的主体。若只有 Bob --g--> Alice,不等于 Alice 可以把自己的权限给 Bob。
4. tg 路径、岛与桥#
tg 路径是由 t/g 权限边组成的路径,分析时要保留每条边相对于行进方向的箭头。
岛是只含主体、通过 tg 路径连通的最大区域。在模型规则允许的推导下,同岛主体可以共享已有权限。
桥是连接主体端点的特定 tg 路径,用来分析跨岛转移;中间可能涉及客体。不是任何把两个岛画起来的线都满足桥的标签条件。
第 9 页桥的形式条件见原图,箭头表示沿路径方向观察到的边方向,星号表示该符号出现零次或多次:

做题时优先写出每一步合法 Take/Grant,核对执行者是否为主体。只说“图连着所以能共享”不能替代推导。
5. can-share#
can-share(r,x,y,G₀) 表示:能否从初始图 G₀ 出发,执行有限次合法规则后,得到 x --r--> y。
若这条边初始就有,答案自然为真。否则需寻找对 y 已有 r 的来源,以及 x 能否通过岛、桥和相应扩展取得该权。
当端点涉及客体,要进一步检查主体能否借 Grant 初始扩展、借 Take 最终扩展来协助;不能只套“同岛主体”结论。
课件给出的标准 Take-Grant 共享判定可在线性时间 O(|V|+|E|) 完成。这个结论属于该受限模型,不能推广为所有授权系统都线性可判定。
解题顺序#
- 标出主体/客体,逐条记录现有边与方向。
- 找所问权限的当前来源。
- 用 Take/Grant 推导新边,注明执行规则的主体。
- 必要时利用岛和合法桥缩小搜索范围。
- 回答所问的具体边是否可达。
自测#
A --t--> B,B --g--> C,A 是主体。A 可以先取得什么?
**答案:**取得 A --g--> C。此后若 A 对文件 F 有 r,便可在 Grant 规则前提满足时给 C 对 F 的 r;C 是否能主动执行其他规则还取决于其节点类型。