# HRU 与安全性不可判定

> 来源：2-1 第 10–54 页；系统基础 PDF 第 12–20 页。课件中的“可靠性/safety”是特定权限传播问题，不泛指系统的一切安全属性。

## 1. 从静态矩阵到动态系统

ACM 记录某一时刻权限；HRU 用命令描述矩阵如何改变。命令可检查已有权限，再执行一串基本原语。

六种原语：创建主体、创建客体、销毁主体、销毁客体、向单元加入权限、从单元删除权限。

```text
command grant_read(p,f,q)
  if own in A[p,f]
  then enter r into A[q,f]
end
```

意思：如果 p 拥有 f，就允许把 f 的读权交给 q。条件是命令可执行的前提，动作才改变状态。

课件标准形式中，条件检查权限是否存在，并以 AND 合取；不能直接用“某权限不存在”作为同一种条件测试。含 OR 的情况可拆成不同命令。

## 2. 什么叫权限泄露

某权限 r 被加入原来没有 r 的矩阵项，课件称为一次泄露。这个词是模型中的技术定义；分析时需要结合所问初始状态、权限和允许命令，不能把任何现实中的正常授权都直接称为事故。

安全性问题是：从给定初始状态出发，是否存在某一串合法命令，使所关心的权限发生这种传播？

```text
X₀ → X₁ → … → Xₙ
问：是否存在能到达“r 泄露”的 Xₙ 的命令序列？
```

“不存在攻击者非法执行命令”也不够：安全问题可能恰好来自合法命令的组合效果。

## 3. 一般结论

一般 HRU 系统的安全性问题不可判定：不存在对任意这样的系统都能有限时间准确给出答案的统一算法。

证明思路是将任意图灵机的运行编码为权限状态变化，使得“机器停机”对应“特定权限泄露”。若安全性可统一判定，停机问题也能被统一判定，产生矛盾。

图灵机是描述计算过程的抽象模型，包含状态、纸带、读写头和转移规则。这里不需要把课件逐帧二进制加一动画全部背下；要理解“权限系统能模拟一般计算”的作用。

## 4. 限制模型后可以怎样

课件讨论单步命令系统：每条命令只含一个基本操作，安全性可判定。单步是“动作数为一个”，不能只按 if 条件数判断。

直观上，受限命令不再拥有任意复杂的组合表达能力，课件通过缩减可能序列，把问题限制到可穷举的范围。它还给出受限情形的步骤上界形式 `n(s+1)(o+1)`，其中 n 是权限种类数，s/o 是初始主体/客体规模；不能把该界套用到一般 HRU。

Take-Grant 是另一种具体受限模型，后面能给出有效的权限传播判定。

## 5. 考试表达模板

> HRU 用访问控制矩阵表示保护状态，用条件命令表示状态变化。一般安全性问题询问特定权限是否会泄露。通过模拟图灵机并归约停机问题，可知一般情形不可判定；这不否定受限模型下存在判定算法。

## 自测

1. “不可判定”是否表示每个具体系统都无法分析？——否。
2. “今天没找到泄露序列”能否证明永不存在？——不能。
3. 两个条件、一条 enter 动作，是否必然不是单步命令？——不是，单步看动作数。
