# Take-Grant 与权限传播

> 来源：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. 两个最小推导

```text
已知：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 页桥的形式条件见原图，箭头表示沿路径方向观察到的边方向，星号表示该符号出现零次或多次：

![课件桥路径的标签条件](../assets/TakeGrant_桥的标签条件.png)

做题时优先写出每一步合法 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|)` 完成。这个结论属于该受限模型，不能推广为所有授权系统都线性可判定。

## 解题顺序

1. 标出主体/客体，逐条记录现有边与方向。
2. 找所问权限的当前来源。
3. 用 Take/Grant 推导新边，注明执行规则的主体。
4. 必要时利用岛和合法桥缩小搜索范围。
5. 回答所问的具体边是否可达。

## 自测

`A --t--> B`，`B --g--> C`，A 是主体。A 可以先取得什么？

**答案：**取得 `A --g--> C`。此后若 A 对文件 F 有 r，便可在 Grant 规则前提满足时给 C 对 F 的 r；C 是否能主动执行其他规则还取决于其节点类型。
