# 2-1-安全模型AC 2025.ppt：逐页可提取文字

> [原课件](../../../2-1-安全模型AC 2025.ppt)；共54页。以下是文字提取，**未经逐句纠错**；图中文字、截图代码、公式对象及动画关系可能无法完整提取。阅读主题笔记后，可按页码回原文件查看。

## 第 1 页

````text
访问控制矩阵
````

## 第 2 页

````text
访问控制
访问控制矩阵 ACM
逻辑抽象层
ACM的更改规则
针对不同的需求（安全策略），不同的更改ACM的方式：ACM 如何随时间演化，哪些状态是安全/不安全的
HRU：策略描述语言 理论
安全策略
take-grant
保密策略 BLP
完整性策略 BIBA
混合策略 中国墙
ACM的实现
访问控制列表ACL、能力表、基于角色RBAC、基于属性ABAC
ACM 怎么组织和构造
谁可更改ACM：自主型、强制型
````

## 第 3 页

````text
访问控制矩阵
Overview
访问控制矩阵 Access Control Matrix，ACM
HRU保护状态的转换描述
命令
条件命令
Harrison-Ruzzo-Ullman基本结果
````

## 第 4 页

````text
保护状态
保护状态
系统状态是所有内存、二级缓存、寄存器和系统中其他设备状态的集合
涉及安全保护的状态的集合为保护状态
P：保护状态集合，Q：P中的合法状态
Q：安全；P-Q不安全
状态转换
系统状态转换中影响到保护状态的才是本章关心的
访问控制矩阵
描述当前保护状态的最精确的模型
````

## 第 5 页

````text
访问控制矩阵
Subjects S = { s1,…,sn }
Objects O = { o1,…,om }
Rights R = { r1,…,rk }
Entries A[si, oj]  R
A[si, oj] = { rx, …, ry } 表示主体 si 对客
   体oj 有权限 rx, …, ry

保护状态用(S，O，A)表示
````

## 第 6 页

````text
现代系统的权限体系
传统安全模型只有：Read（读）Write（写）Execute（执行）
现代系统更细粒度、更丰富的权限系统
资源访问权限
隐私敏感权限（传感器/数据）
网络与通信权限
RWE之外的权限
元权限（管理ACM）
计算权限（只算不看）
条件/预算型权限，时间、空间、速率…
义务/用途约束”
````

## 第 7 页

````text
例子 1
进程 p, q
文件 f, g
权限 r, w, x, a(添加), o
		f	g	p	q
p		rwo	r	rwxo	w
q		a	ro	r	rwxo
````

## 第 8 页

````text
例子 2
Procedures inc_ctr, dec_ctr, manage
Variable counter
Rights +, –, call
		counter	inc_ctr	dec_ctr	manage
inc_ctr	+
dec_ctr	–
manage		call	call	call
````

## 第 9 页

````text
访问控制矩阵的变体
能力表：ACM的行
访问控制列表：ACM的列
````

## 第 10 页

````text
保护状态转换
状态X，操作
|– 代表状态的转换
Xi |–  Xi+1: 操作 将系统从状态 Xi 转化到Xi+1
Xi |– * Xi+1: 一些列操作 将系统从状态 Xi 转化到Xi+1
Commands often called transformation procedures
````

## 第 11 页

````text
基本转换操作
Harrison-Ruzzo-Ullman （1976）
定义的基本命令（或原语）
create subject s; create object o
Creates new row, column in ACM; creates new column in ACM
destroy subject s; destroy object o
Deletes row, column from ACM; deletes column from ACM
enter r into A[s, o]
Adds r rights for subject s over object  o
delete r from A[s, o]
Removes r rights from subject s over object  o
多个基本命令组合成复合命令
````

## 第 12 页

````text
例子
````

## 第 13 页

````text
创建文件
进程 p 创建文件 f ，拥有 r、 w 权限
	command create file(p, f)
		create object f ;
		enter own into A[p, f];
		enter r into A[p, f];
		enter w into A[p, f];
	end

令进程 p 成为文件的 g 拥有者
	command make owner(p, g)
		enter own into A[p, g];
	end
````

## 第 14 页

````text
单步命令
基本命令不能直接调用，但可定义只包含一个基本命令的命令：
单步命令
只包含一个基本命令（原语）
````

## 第 15 页

````text
条件命令
如果 p 拥有 f ，那么给与 q 对 f 的r权限, 
	command grant • read •file •1 (p, f, q)
		if own in A[p, f]
		then
			enter r into A[q, f];
	end
单一条件命令
Single condition in this command
````

## 第 16 页

````text
多条件命令
如果 p 拥有 f 且p对q有c权利，那么给与 q 对 f 的r和w权限
	command grant•read•file•2 (p, f, q)
		if own in A[p, f] and c in A[p, q]
		then
			enter r into A[q, f];
			enter w into A[q, f];
	end

条件只用and连接
Or 条件等价于两个独立的条件命令
````

## 第 17 页

````text
模型中没有条件取反
即：不能在访问控制矩阵中测试一个权限是否缺少
````

## 第 18 页

````text
Harrison-Ruzzo-Ullman基本结果
计算机安全基本问题
在什么条件下，一个计算机算法可判定一个系统是否安全？
Harrison-Ruzzo-Ullman 结果(J. ACM, 1976)
访问控制矩阵
命令描述安全策略
在HRU模型中，计算机的安全是不可判定的
````

## 第 19 页

````text
定义 “安全”
一个权限 r 被加入到原来不存在 r 的一个访问控制矩阵元素时，r 被称为泄露了。

如果一个初始状态为s0的保护系统不会泄露权限r，则对于权限r是可靠的。
````

## 第 20 页

````text
可靠问题
是否存在一个算法来判定一个初始状态为s0的保护系统 对于权限r是可靠的？
在抽象模型中, “安全” = “可靠”
具体地：
r 能否出现在 A[s,o]中？
1976年， Harrison-Ruzzo-Ullman 证明了在最普通、抽象的情形中，计算机的安全是不可判定的
但并不否定：在特定类型系统的系统中，安全性是可以判定的
````

## 第 21 页

````text
单步命令系统的可靠性问题可判断
````

## 第 22 页

````text
命令改变ACM的状态
命令是函数，调用时用不同的参数导致不同的状态
通过一个合法的命令，系统保护状态从Xi转换为Xi+1
````

## 第 23 页

````text
单步命令系统的可靠性问题可判断
证明: 
设最短命令序列 c1, …, ck 泄露了权限
delete, destroy可忽略
delete destroy之前的状态的扩展状态集合包含了之后的状态扩展集合
 所有 creates 合并成一个
因此主体、客体最多增加一个。
系统规模是有限的
由于有限的系统状态，可以用一个算法穷举所有状态，判定是否有权限泄露
````

## 第 24 页

````text
最坏情况: 将尽可能多的权限加入每一个ACM元素; 
s 个主体； o 个客体, n 个权限, 命令数的上限：
 k ≤ n(s+1)(o+1)
````

## 第 25 页

````text
一般情况下HRU模型可靠性不可判定

证明大意：
构造一个多项式时间可计算的映射 𝐹，把任意图灵机 𝑀映射成一个 HRU 系统，使得：𝑀 停机   ⟺  此𝐻RU系统泄露 𝑟
因此，
如果可靠性问题是可解的，则图灵机停机问题是可解的

图灵机Turing Machine
图灵机的停机问题是不可判定的
````

## 第 26 页

````text
图灵机
图灵机：图灵机能计算的函数类 = 部分递归函数 = Church λ-演算可计算函数 = 各种寄存器机 / RAM 机可计算函数。图灵完备（Turing-complete）计算能力

TM（Turing Machine）：
无限长的纸带(无限存储),有限的内部状态
有一个 读写头
能够 读、写、左移、右移
预设一些接受、拒绝状态，进入这些状态则停机
如不能进入任何接受拒绝状态，则永远不停机
````

## 第 27 页

````text
二进制++
图灵机程序:
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!
````

## 第 28 页

````text
输入47
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

1
1
1
1
0
1
````

## 第 29 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
1
1
1
0
1
````

## 第 30 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
1
1
0
1
````

## 第 31 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
1
0
1
````

## 第 32 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
0
1
````

## 第 33 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
1
1
````

## 第 34 页

````text
结果
47++  = 48
127++= 128
````

## 第 35 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

1
1
1
1
1
1
1
````

## 第 36 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
1
1
1
1
1
1
````

## 第 37 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
1
1
1
1
1
````

## 第 38 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
1
1
1
1
````

## 第 39 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
1
1
1
````

## 第 40 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
0
1
1
````

## 第 41 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
0
0
1
````

## 第 42 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
0
0
0
````

## 第 43 页

````text
运行
If read 1, write 0, go right, repeat.
If read 0, write 1, HALT!
If read    , write 1, HALT!

0
0
0
0
0
0
0
1


思考：检查纸带上一的个数是否是2n（一进制）
````

## 第 44 页

````text
图灵机
算法：确定，可行，有限 = 对所有合法输入都能停机并给出正确输出的图灵机程序，我们就把它看成这个问题的一个算法。
定义 :  图灵机 (TM)对应一个 7-元组 M = (Q, S, G, d, q0, qacc, qrej). Q:状态集合 S：字母表, q0：初始状态. G 纸带字母表，含空白符□，状态转移函数d:
给定 非停机状态 p, 纸带字符 x, d(p,x) = (q,y,L) 对应的动作： TM 状态变为 q, 当前注视的纸带字符 x 替换为 y, TM 左移一位.
````

## 第 45 页

````text
停机问题
判定问题：
是否存在图灵机(算法)能回答任意图灵机在任意输入下是否停机的问题？
图灵：不存在
每个TM可判定
一个自然数是否是质数
未知：哥德巴赫猜想
整数集合的命题都可转化为一个图灵机是否停机的问题
````

## 第 46 页

````text
设D(i,x)返回第i号图灵机对输入x是否停机。则构造图灵机如下：

DD(x)
if D(x,x)=停 then
    陷入不停状态
else
    停机

设DD的编号为y，则DD输入y时，是停机还是不停？即D(y,y)=?
````

## 第 47 页

````text
图灵机->ACM
A
B
C
D
…
1
2
3
4
head
s1
s2
s3
s4
s4
s3
s2
s1
A
B
C k
D end
own
own
own
Current state is k
````

## 第 48 页

````text
图灵机->ACM
A
B
X
D
…
1
2
3
4
head
s1
s2
s3
s4
s4
s3
s2
s1
A
B
X
D k1 end
own
own
own
After (k, C) = (k1, X, R)
where k is the current
state and k1 the next state
````

## 第 49 页

````text
左移 右移->ACM命令
````

## 第 50 页

````text
右移超过边界
A
B
X
Y
1
2
3
4
head
s1
s2
s3
s4
s4
s3
s2
s1
A
B
X
Y
own
own
own
After (k1, D) = (k2, Y, R)
where k1 is the current
state and k2 the next state
s5
s5
own
b k2 end
5
b
````

## 第 51 页

````text
超过边界->ACM命令
````

## 第 52 页

````text
说明
保护系统模拟了 TM
ACM中只有一个 end 权限
某一时刻只有一个对应着状态的权限
Own权限确定了纸带单元的顺序
因此某一时刻只有一个命令是可执行的（条件语句被满足）
如果TM 进入 qf  , 则权限被泄露
如果可靠性问题可判定，则 任意TM能否停机也可判定
结论: 可靠性问题是不可判定的
````

## 第 53 页

````text
限制授权系统的规模是使得安全问题易于处理的另一种方法
定理：如果主体数量是有限的，那么自由授权系统的安全问题是可判定的
````

## 第 54 页

````text
结论
安全模型表达能力越强，验证安全性越困难。最坏情况下不可判定。
简单模型描述能力有限，但可获得有效地验证安全性的方法。
````
