课件8：第4-1~2节信息流控制

• 由执行if语句而导致的流xy称为隐式流， 以区别于由一个赋值语句导致的显式流。
• 隐式流是指不是由显式赋值形成的但却又 存在的暗流。
• 间接流是由若干个具有传递关系的显式流 形成的，
• 给定在状态s中的一个客体x和在s’中的客体y。 设H(x|y’)是给定ys’时xs的暧昧度。H(x|y)是在 给定ys时xs的暧昧度。
• 例2 考虑语句序列 “z := x；y := z”。
• 该序列的执行能够通过中间变元z，以及 直接流xz，导致一个间接流xy。
• 但是该序列没有导致流zy，因为y的最 后值没有揭示关于z的初始值的任何信息。
• 其实z只是一个中间变元，不是信息源。
• 例3 考虑语句“z := x+y”和“z := xy”， 此处“”表示按位模2加。
• 一般说来可执行语句的执行都会产生信 息的流动，并改变系统的状态。
• 例如，执行交换两个单元内容的过程 SWITCH（X，Y）的结果使得X的内容 流向Y和Y的内容流向了X。
• 信息流伴随着改变一个客体值的运算。
• 一 个 流 xsys’ 是 允 许 的 ， 当 且 仅 当 SC(xs)≤SC(ys’)，即y的最后类至少和x的初 始类一样大。
• 3）反对称的：若A≤B且又有B≤A，则有A=B。
• 2、有限格
• 在保护系统中，主体、客体（包括存储段、变量 单元等）的个数是有限的。研究有限格是必要的。 有限格还有以下性质：
1）任何有限格都存在最小上界（也称为最大元素， 记为HIGH）和最大下界（也称为最小元素，记为 LOW）。设L={a1,a2,…,an}，根据最大元素与最小 元素的定义有：
关系 2、不同安全类客体之间信息的流动关系。
4.1 信息流的格模型
• 格模型是Denning D.E.于1975年在他的博士 论文“计算机系统中的安全信息流”中发表 的。
• 格模型是用来描述信息流的信道与策略，但 不是指定信息从一个客体流向另一个客体。
• 格模型也是状态转移类模型：通过格结构的 流动策略、状态和状态转换对信息流系统进 行形式化。
x：代表x的名字与它的值，
SC(x)：表示它的安全类。
xs：强调x在信息状态s中的值 SC(xs)：强调x在信息状态s中的安全类 • 客体安全类SC(x)可是一个常量或变元。
• 静态约束：对于固定类的客体，在x的生 命期中，SC(x)都是常数，即对于所有的 信息状态s和s’都有SC(xs)= SC(xs’)。
• 隐式流与间接流的区别：间接流是由若 干个具有传递关系的显式流形成的，而 隐式流则是指不是由显式赋值形成的但 却又存在的暗流。
• 值得注意的是，甚至当x1时，对y的赋 值会被跳过，流xy也会出现。
• 不过，必须有对y赋值的可能性，并且这 一赋值必须以x的值为控制条件。否则， y的值不能减少关于x的不肯定性。
例如：设(L，⊙，)和(S，∧，∨)是两个格，定义一 个代数系统(L×S，·，+)如下：
对于任意的（a1,b1）、(a2，b2) L×S有：
• (a1,b1)·(a2，b2)=(a1⊙a2，b1∧b2)
• (a1,b1)+(a2，b2)=(a1a2，b1∨b2)，则称
• (L×S，·，+)是格(L，⊙，)和(S，∧，∨)的积代 数。
• 例5 考虑语句“if (x=1) and (y=1) then z:= 1”,这里z的初值为0。
• 假定x与y两者都是0或1，且这两种取值 都是等概率的，因此，有H(x)= H(y)=1。
• z=1蕴涵着x=y=1，而z=0蕴涵着x=0的可 能性是2/3，对y也是类似的。(？)
• xy z
• 00 0
• 假设x的取值为0或1，且是等概率的，因 此有H(x)=1。
• 当该语句执行后，y中便含有x的确切值， 使得H(x|y’)=0。因此只有一个比特的信 息(量)从x传送到y。
• 即使x不限制在[0，1]范围内，y的值也减 少了x的不肯定性（y=1蕴涵着x=1，而 y=0蕴涵着x1）。
• 由执行if语句而导致的流xy称为隐式流， 以区别于由一个赋值语句导致的显式流。
• 请注意，如果x的值是已知的，语句“y:= x” 的执行就不导致流xy，这是因为：
H(x|y’)= H(x|y)=H(x)=0。
• 如果x和y都被表达为32比特，则容量就是 32比特。
• 如果x和y都是n维向量，且每一个向量元素 是32比特，则容量是32n比特。
• 在这种情况中，当所有的字都是等概率时， 就达到了满容量。
•
信 率 所
有道分可容布能量，的：流概设x率Ps(y分x的)表布信上示道传在容送状量的态是信s下“息x在量的x之的概
和”，即：
C(，x，y)=Ps(x) I(，x，y，s，s’)
• 注意，如果y能用n比特表达，任何传送 给y的命令序列的信道容量至多是n比特。
• 例1 考虑赋值句 “y := x”。
• 任何一个信息流动策略都可以找到一个 格来描述。
• 如果你给出的流Байду номын сангаас策略不符合一个格的 要求，可以按照格的定义重新把它修改 成一个格.
• 例如，可把图4-3（a）所示非格策略， 改变成图4-3（b）的格图。
• 改变的方法如下：
F
E
High F
C
D
A
B
C
DE
AB
A
B
1、D、E等价，压缩为一个类 Low 2、F、DE无最小上界，可添加一个结点HIGH 3、A、B无最大下界，可添加一个结点Low 4、A、B无最小上界，可添加一个结点AB
{x,y}
{x,z} {y,z}
{x }
{y}
{z}
(b) { } (low)
4、格的乘积
格的代数系统形式：
• 设(L，⊙，)是一个代数系统，⊙和是集合L上的 二元运算。
• 如果运算⊙和都满足交换律、结合律，并且也满足 吸收律(即有a⊙(ab)=a和aa⊙b=a)，则代数系统(L， ⊙，)也是格。
信息从x流到y是授权的当且仅当x≤y； • 如果x、y都有可变类，那么SC(y)是它在流动
之后的类，SC(x)是它在流动之前的类。
4.1.3 状态转换与信息流
• 状态转换是由创建和删除一个客体、改 变一个客体的值或它的安全类产生的。
• 设s’是在状态s下执行命令序列后到达的 状态，表示为：s s’。
• 考虑赋值句 “y := x”。认为存在从x到y 的直接流x y。
• 考虑语句序列 “z := x；y := z”。该序 列的执行能够通过中间变元z，以及直接 流xz，导致一个间接流xy。
• 考虑语句“If x=1 then y := 1”。执行本语 句之前，y的初始值为0。
• 当该语句执行后，y中便含有x的确切值， 只有一个比特的信息（量）从x传送到y。
4.1.1 格与信息流动策略
• 1、格的定义：如果（L，≤）是一个偏序集合， L中每一对元素a和b都有最大下界与最小上界， 则称二元组（L，≤）是格。
• 格中的最大下界和最小上界分别用a⊙b和ab表 示。（L，≤）是一个偏序集合，蕴涵着关系≤具 有以下性质（其中A、B、C是L中的元素）：
• 1）自反的：A≤A。 2）传递的：若A≤B且B≤C， 则A≤C。
(1) LOW= a1⊙a2⊙…⊙an (2) HIGH= a1a2…an 2）且对于任意元素A∈L有ALOW=A，A⊙HIGH=A，即 LOW为运算的幺元素，HIGH为⊙运算的幺元素。
3、线性格与子集格
1）线性格：在N个元素的集合S上，这N个 元素之间的关系是一个线性序的关系。 对于所有的S中的元素a和b都有： （1）ab=max(a,b) （2）a⊙b=min（a,b） （3）LOW元素对应于位于线性序最低端 元素，而HIGH元素对应于最高端元素。
第4章 信息流控制原理
4.1 信息流的格模型 4.2 基于格的多级安全模型 4.3 信息流控制机制综述 4.4 基于执行的信息流控制 4.5 基于编译的信息流控制 4.6 实际系统的信息流机制
概述
• 信息的泄漏原因： 1、访问控制机制有缺陷 2、缺乏适当的信息流策略 3、缺乏实现信息流策略的适当机制。 • 信息流控制策略： 1、规定信息的安全类和客体安全类之间的
• 如果在状态s中y不存在，那么H(x|y)=H(x)。
• 根据信息论的知识，如果H(x|y’)≤H(x|y)，那 么在状态s中命令序列的执行导致了从x到y 的信息流，记为xsys’。
• 由流xsys’传送的信息量是： • I(，x，y，s，s’)= H(x|y’) - H(x|y)
• 由此定义可以看出，信息流总是伴随着 改是的最允变后许一类的个至，客少当体和且值x仅的的当运初S算始C(。类xs一)一≤S样个C大(流ys。x’)s，即yys’
• 01 0
• 10 0
• 11 1
• 暧昧度H(x|z’)和H(y|z’)都近似0.7比特， • 因此，x和y传递的信息量各近似于0.3比
2）子集格：给定一个有限集合S，可以由S 上的所有子集集合上的一个非线性排序 形成一个子集格。
• 有序关系≤对应于子集间的包含关系；
• 最大元素对应于所有子集的并（∪）， 是全集S本身；
• 最小元素对应于所有子集的交（∩）， 是空集{ }。
图4-1 线性格与子集格
1 0 (a)
{x,y,z} (high)
• 假设x是在范围[0，15]中的整数变元，所有 的取值都是等概率的。设pi表示x=i的概率， 显然，当0≤i≤15时，pi=1/16，其他取值时， pi=0 ；
• 如果y初始时不存在，那么：
• H(x|y)=H(x)=pilog2(1/pi)=16·1/16·log216= 4
• 因为在赋值后，x的值能够根据y的值确定， 即H（x|y’）=0。因此有0-4个比特的信息量 传送给y。