原课件;共54页。以下是文字提取,未经逐句纠错;图中文字、截图代码、公式对象及动画关系可能无法完整提取。阅读主题笔记后,可按页码回原文件查看。
第 1 页#
访问控制矩阵
|
第 2 页#
访问控制 访问控制矩阵 ACM 逻辑抽象层 ACM的更改规则 针对不同的需求(安全策略),不同的更改ACM的方式:ACM 如何随时间演化,哪些状态是安全/不安全的 HRU:策略描述语言 理论 安全策略 take-grant 保密策略 BLP 完整性策略 BIBA 混合策略 中国墙 ACM的实现 访问控制列表ACL、能力表、基于角色RBAC、基于属性ABAC ACM 怎么组织和构造 谁可更改ACM:自主型、强制型 |
第 3 页#
访问控制矩阵 Overview 访问控制矩阵 Access Control Matrix,ACM HRU保护状态的转换描述 命令 条件命令 Harrison-Ruzzo-Ullman基本结果 |
第 4 页#
保护状态 保护状态 系统状态是所有内存、二级缓存、寄存器和系统中其他设备状态的集合 涉及安全保护的状态的集合为保护状态 P:保护状态集合,Q:P中的合法状态 Q:安全;P-Q不安全 状态转换 系统状态转换中影响到保护状态的才是本章关心的 访问控制矩阵 描述当前保护状态的最精确的模型 |
第 5 页#
访问控制矩阵 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 页#
现代系统的权限体系 传统安全模型只有:Read(读)Write(写)Execute(执行) 现代系统更细粒度、更丰富的权限系统 资源访问权限 隐私敏感权限(传感器/数据) 网络与通信权限 RWE之外的权限 元权限(管理ACM) 计算权限(只算不看) 条件/预算型权限,时间、空间、速率… 义务/用途约束” |
第 7 页#
例子 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 页#
例子 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 页#
访问控制矩阵的变体 能力表:ACM的行 访问控制列表:ACM的列 |
第 10 页#
保护状态转换 状态X,操作 |– 代表状态的转换 Xi |– Xi+1: 操作 将系统从状态 Xi 转化到Xi+1 Xi |– * Xi+1: 一些列操作 将系统从状态 Xi 转化到Xi+1 Commands often called transformation procedures |
第 11 页#
基本转换操作 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 页#
例子
|
第 13 页#
创建文件 进程 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 页#
单步命令 基本命令不能直接调用,但可定义只包含一个基本命令的命令: 单步命令 只包含一个基本命令(原语) |
第 15 页#
条件命令 如果 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 页#
多条件命令 如果 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 页#
模型中没有条件取反 即:不能在访问控制矩阵中测试一个权限是否缺少 |
第 18 页#
Harrison-Ruzzo-Ullman基本结果 计算机安全基本问题 在什么条件下,一个计算机算法可判定一个系统是否安全? Harrison-Ruzzo-Ullman 结果(J. ACM, 1976) 访问控制矩阵 命令描述安全策略 在HRU模型中,计算机的安全是不可判定的 |
第 19 页#
定义 “安全” 一个权限 r 被加入到原来不存在 r 的一个访问控制矩阵元素时,r 被称为泄露了。 如果一个初始状态为s0的保护系统不会泄露权限r,则对于权限r是可靠的。 |
第 20 页#
可靠问题 是否存在一个算法来判定一个初始状态为s0的保护系统 对于权限r是可靠的? 在抽象模型中, “安全” = “可靠” 具体地: r 能否出现在 A[s,o]中? 1976年, Harrison-Ruzzo-Ullman 证明了在最普通、抽象的情形中,计算机的安全是不可判定的 但并不否定:在特定类型系统的系统中,安全性是可以判定的 |
第 21 页#
单步命令系统的可靠性问题可判断
|
第 22 页#
命令改变ACM的状态 命令是函数,调用时用不同的参数导致不同的状态 通过一个合法的命令,系统保护状态从Xi转换为Xi+1 |
第 23 页#
单步命令系统的可靠性问题可判断 证明: 设最短命令序列 c1, …, ck 泄露了权限 delete, destroy可忽略 delete destroy之前的状态的扩展状态集合包含了之后的状态扩展集合 所有 creates 合并成一个 因此主体、客体最多增加一个。 系统规模是有限的 由于有限的系统状态,可以用一个算法穷举所有状态,判定是否有权限泄露 |
第 24 页#
最坏情况: 将尽可能多的权限加入每一个ACM元素; s 个主体; o 个客体, n 个权限, 命令数的上限: k ≤ n(s+1)(o+1) |
第 25 页#
一般情况下HRU模型可靠性不可判定 证明大意: 构造一个多项式时间可计算的映射 𝐹,把任意图灵机 𝑀映射成一个 HRU 系统,使得:𝑀 停机 ⟺ 此𝐻RU系统泄露 𝑟 因此, 如果可靠性问题是可解的,则图灵机停机问题是可解的 图灵机Turing Machine 图灵机的停机问题是不可判定的 |
第 26 页#
图灵机 图灵机:图灵机能计算的函数类 = 部分递归函数 = Church λ-演算可计算函数 = 各种寄存器机 / RAM 机可计算函数。图灵完备(Turing-complete)计算能力 TM(Turing Machine): 无限长的纸带(无限存储),有限的内部状态 有一个 读写头 能够 读、写、左移、右移 预设一些接受、拒绝状态,进入这些状态则停机 如不能进入任何接受拒绝状态,则永远不停机 |
第 27 页#
二进制++ 图灵机程序: If read 1, write 0, go right, repeat. If read 0, write 1, HALT! If read , write 1, HALT! |
第 28 页#
输入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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
结果 47++ = 48 127++= 128 |
第 35 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
运行 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 页#
图灵机 算法:确定,可行,有限 = 对所有合法输入都能停机并给出正确输出的图灵机程序,我们就把它看成这个问题的一个算法。 定义 : 图灵机 (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 页#
停机问题 判定问题: 是否存在图灵机(算法)能回答任意图灵机在任意输入下是否停机的问题? 图灵:不存在 每个TM可判定 一个自然数是否是质数 未知:哥德巴赫猜想 整数集合的命题都可转化为一个图灵机是否停机的问题 |
第 46 页#
设D(i,x)返回第i号图灵机对输入x是否停机。则构造图灵机如下: DD(x) if D(x,x)=停 then 陷入不停状态 else 停机 设DD的编号为y,则DD输入y时,是停机还是不停?即D(y,y)=? |
第 47 页#
图灵机->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 页#
图灵机->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 页#
左移 右移->ACM命令
|
第 50 页#
右移超过边界 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 页#
超过边界->ACM命令
|
第 52 页#
说明 保护系统模拟了 TM ACM中只有一个 end 权限 某一时刻只有一个对应着状态的权限 Own权限确定了纸带单元的顺序 因此某一时刻只有一个命令是可执行的(条件语句被满足) 如果TM 进入 qf , 则权限被泄露 如果可靠性问题可判定,则 任意TM能否停机也可判定 结论: 可靠性问题是不可判定的 |
第 53 页#
限制授权系统的规模是使得安全问题易于处理的另一种方法 定理:如果主体数量是有限的,那么自由授权系统的安全问题是可判定的 |
第 54 页#
结论 安全模型表达能力越强,验证安全性越困难。最坏情况下不可判定。 简单模型描述能力有限,但可获得有效地验证安全性的方法。 |