第四章 多级安全数据模型1.ppt

第四章多级安全关系数据模型朱虹华中科技大学计算机学院 第四章多级安全关系数据模型 4 1多实例问题 多级安全关系数据模型是怎样提出的1 受保护的客体标记粒度 在操作系统中 受保护的客体是文件和目录 在数据库系统中 受保护的客体可以有多种选择 表 属性 元组 元素DBMS应该实现哪个粒度的标记 表级 实现容易 但不灵活 数据元素级 导致许多问题 如多实例 2 表级标记粒度 表SOD StarshipObjectiveDestination 其中Starship是主关键字若为表级标记 标记为普通 秘密级主体查询的结果 StarshipObjectiveDestinationEnterpriseExplorationTalosVoyagerSpyingMars普通级用户查询的结果 StarshipObjectiveDestinationEnterpriseExplorationTalosVoyagerSpyingMars问题 秘密级主体要修改该表会怎样 不方便 3 属性级标记粒度 表SOD StarshipObjectiveDestination 的各属性标记StarshipUObjectiveCDestinationS标记为S 机密级 主体查询的结果 StarshipUObjectiveCDestinationSEnterpriseExplorationTalosVoyagerSpyingMars实际上缺少这一应用 4 元组级标记粒度 表SOD StarshipObjectiveDestination 的元组级标记标记为S 机密级 主体查询的结果 StarshipObjectiveDestinationTLEnterpriseExplorationTalosUVoyagerSpyingMarsS标记为普通的主体查询结果 StarshipObjectiveDestinationTLEnterpriseExplorationTalosU 5 元素级标记粒度 表SOD StarshipObjectiveDestination 的元素级标记 每个元组的每个列给定一个标记标记为S 机密级 主体查询的结果 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUEnterpriseSSpyingSMarsS标记为U 普通级 的主体查询结果 StarshipObjectiveDestinationEnterpriseUExplorationUTalosU 6 多实例问题 1 什么是多实例 2 多实例的类型有哪些 3 多实例是怎样出现的 4 是否可以消除多实例 6 多实例的问题 1 什么是多实例 主关键字的唯一性 主关键字的最小性约束 不允许表中出现相同主关键字的记录多实例 在元组级 元素级标记下允许出现主关键字相同而标记不同的记录 2 多实例的类型 实体多实例 属性多实例 2 多实例的类型 实体多实例和属性多实例 实体多实例S 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUEnterpriseSSpyingSMarsS问题 系统中有多少个实体 1个还是2个 属性多实例S 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUEnterpriseUSpyingSMarsS问题 Enterprise的真正目的和目的地是什么 2 多实例的类型 元组级标记的多实例 S 实例 StarshipObjectiveDestinationTLEnterpriseExplorationTalosUEnterpriseSpyingMarsS问题 有几条飞船 Enterprise的真正目标和目的地是什么 3 多实例是怎样出现的 实体多实例 S 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUVoyagerSSpyingSMarsSU 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUU 用户插入 Voyager Exploration Mars 拒绝插入 导致隐通道接收该语句 覆盖高安全级数据 导致严重的完整性问题不覆盖高安全级数据 高安全级主体看到两条记录 导致实体多实例 由于高安全级用户导致的实体多实例 U 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosUS 用户插入 Enterprise Exploration Mars 拒绝插入 否认服务接收该语句 实体多实例 3 多实例是怎样出现的 实体多实例 3 多实例是怎样产生的 属性级多实例 S 实例 StarshipObjectiveDestinationEnterpriseUExplorationUTalosSVoyagerSSpyingSMarsSU 实例 StarshipObjectiveDestinationEnterpriseUExplorationUNullUU 用户发出更新语句 UpdateSODSetDestination Rigel WhereStarship Enterprise 拒绝更新 产生隐通道允许更新 覆盖高安全级数据 导致完整性错误不覆盖高安全级数据且执行成功 高安全级用户看到两个元组 3 多实例是怎样产生的 多实例是必须的吗 有不同意见 可以引入假象 coverstory S 实例StarshipObjectiveDestinationEnterpriseUExplorationUTalosUEnterpriseUSpyingSMarsS另一种意见 允许假象存在 多实例不应该用于支持假象 可以建立另一张表 Starship Objective Real Objective Destination Real Destination 4 多实例可以消除吗 有一种解决方法 只要高安全级的更新与唯一性要求产生冲突 拒绝更新 只要低安全级用户做出与唯一性要求冲突的更新 覆盖高安全级的元组 是否可以接受 多实例问题的根源 违背了关系数据库数据真实性的原则 数据库中的数据是外部世界的真实反映有更好的方法吗 对传统关系模型的扩展 Denning SeaView 模型 安全视图模型 Jajodia Sandhu模型基于信赖的语义模型基于数据语义的模型 MLR模型 4 1 2多实例的解决方法 多级关系数据模型与传统的关系数据模型有哪些不同 4 1 2多实例的解决方法 不必考虑标记问题 考虑标记的问题 关系操作 实体完整性 引用完整性 在关系模型的基础上引入新的完整性约束 完整性约束 与标记的粒度有关 关系集合 没有 有 逻辑数据对象赋予安全标记属性 传统关系模型 多级关系数据模型 4 2安全数据视图模型 SeaView 多级关系定义 一个多级关系是由关系模式 R A1 C1 An Cn TC 表示的 属性Ai及其密级Ci是单级的当且仅当Ci是定义在一个单级表示的域上 否则称其为多级的 一个多级关系的元组可表示为 a1 c1 an cn tc tc为整个元组的密级 不失一般性 这里只考虑 U C S和TS 的情形 读写规则遵循BLP模型的限制 安全级是c的用户看到的是由c支配的所有元素 每个安全级上都存在一个实例 4 2安全数据视图模型 SeaView 2 多级关系的不同实例的访问遵循的原则 出现在给定访问级别的用户的查询结果中的每个元组必须出现在具有更高访问级别用户的查询结果的实例中 低一级别实例中的为空的元素在高一级实例中替换为非空元素 S 用户看到的结果 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUEnterpriseUSpyingSMarsSSU 用户看到的结果 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUEnterpriseUNullUNullUU 4 2安全数据视图模型 SeaView SeaWiew中客体的密级满足下列规则 数据库访问级别完整性 如前所述容器的概念关系模式的安全级必须支配它所属的数据库的安全级 2 可见数据规则关系中数据的最低安全级支配所属关系模式的安全级 属性安全级的最大下界必须支配关系模式的安全级 3 视图访问安全级完整性视图定义者的安全级必须支配视图定义中出现的所有关系和视图的安全级 4 2安全数据视图模型 SeaView 3 完整性规则多级实体完整性设AK是组成关系模式R的主关键字的属性集合 在关系R的元组中 AK中所有属性Ai有相同的安全级 并且它受其他属性安全级的支配 AK中所有属性的值不能为空 2 引用完整性如果一个关系的外键在给定安全级可见 则包含所引用主关键字的元组在此安全级也是可见的 并且外键元素的安全级必须支配所引用的主关键字各元素的安全级 4 2安全数据视图模型 SeaView 3 完整性规则 3 多实例完整性规则 a 给定一个关系R 外观主关键字AK及其安全级CK 对每个不在AK中的属性Ai 下面的函数依赖成立 AK CK Ci Ai多值依赖 复习 设R是属性集U上的一个关系模式 X Y Z是U的子集 并且Z U X Y 关系模式R U 中多值依赖X Y成立 当且仅当对R的任意关系r 给定一对 x z 值 有一组Y的值与其对应 且这组值仅仅决定于x值而与z值无关 4 2安全数据视图模型 SeaView 3 完整性规则 多实例完整性多值依赖的例子 课程 教员XYZ课程教员参考书物理李勇普通物理物理李勇光学原理物理王军普通物理物理王军光学原理b 对每一个不在AK中的属性Ai R满足多值依赖 AK CK Ai Ci 4 2安全数据视图模型 SeaView 4 多级关系的访问查询操作的访问 主体可以对多级关系中具有与自己相同或更低安全级别的实例执行查询操作 符合BLP模型向下读 写操作 插入和删除 允许对一个属性在不同安全级赋予不同的值 SeaView模型根据主体与已存在的数据客体的安全级区分下面两种情况 4 2安全数据视图模型 SeaView 1 主体的安全级受数据的安全级支配 或不可比 低安全级主体修改高安全级数据 当主体向关系插入一个元组而关系中已经存在与此元组具有相同主关键字的不可见元组 则产生一个实体多实例 当主体更新给定元组中的某个属性 而此属性为空值 但其实际上隐藏一个具有更高安全级的数据时 产生一个元素多实例 4 2安全数据视图模型 SeaView 2 主体的安全级支配数据的安全级 当主体向关系插入一个元组而关系中已经存在与此元组具有相同主关键字的低安全级元组 则产生一个实体多实例 当主体更新给定元组中的某个属性 而此属性已经存在一个具有较低安全级的值 产生一个元素多实例 4 2安全数据视图模型 SeaView 例 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUEnterpriseUSpyingSMarsSS当一个TS安全级的用户执行下列语句 UPDATESODSETObjective Spying WHEREStarship Enterprise 将插入两条元组 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUEnterpriseUSpyingSMarsSSEnterpriseUSpyingTSTalosUTSEnterpriseUSpyingTSMarsSTS 4 2安全数据视图模型 SeaView 缺点 一个写操作可能产生多个元组 产生的元组数目 最坏情况下 是关系的非主关键字属性取值数的指数个 其实这些属性中有许多是不合逻辑的 后来人们对多实例完整性进行了改进 4 3Jajodia Sandhu模型 模型的特点 1 重新定义了多实例完整性2 空值完整性3 实例间完整性 4 3Jajodia Sandhu模型 基本定义 关系模式的定义一个多级关系模式是这样的格式 R A1 C1 A2 C2 An Cn TC a 其中每个Ai是域Di内的一个数据属性 每个Ci是属性Ai的级别属性 TC是元组级别属性 b Ci的域是由集合 Li Hi 指定的 这个集合枚举了安全级别的允许值 范围从最大下界 glb Li到最小上界 lub Hi c TC的域是集合 lub Li i 1 n lub Hi i 1 n 4 3Jajodia Sandhu模型 基本定义 2 关系实例对每个关系模式R 有一状态相关的关系实例集合 Rc A1 C1 A2 C2 An Cn TC 实际上是c级别上用户可见数据的集合a 在给定的安全级集合内 每个访问级别c上都有一个这样的集合 b 每个关系实例是一形如 a1 c1 a2 c2 an cn tc 的不同元组集合 其中每个ai Di或ai null c ci tc lub ci i 1 n c 如果ai非空 则ci Li Hi 要定义ci 即使ai是空值 即安全级属性不能为空 4 3Jajodia Sandhu模型 基本定义 3 规定 每个元组t中的元素t Ai 在访问级t Ci 或更高的实例中是可见的 取值为真实值 t Ai 在较低访问级别的实例中会被空值替换 4 3Jajodia Sandhu模型 核心完整性 1 实体完整性设AK是R的外观主关键字 主关键字中不包含安全级的那部分 多级关系R满足实体完整性当且仅当对于所有R的实例Rc和t Rc有 1 Ai AK 则t Ai null 2 Ai Aj AK 则t Ci t Cj 即AK内所有属性安全级相同 3 Ai不属于AK 则t Ci t CAK 这里定义CAK为外观主关键字的级别 非主键属性的级别应高于键的级别 主关键字安全级最低 4 3Jajodia Sandhu模型 核心完整性 空值的语义存在的二义性 确实为空 实例的级别低于属性的级别 使得此属性不可见 从而表现为空元组间的包含概念 非空值对空值的包含 subsumption 要求 空值的安全级等于元组的主关键字的级别 而且空值被非空值包含 一个元组t包含元组s 如果对任何一个属性Ai 下列两者之一成立 t Ai Ci s Ai Ci t Ai null且s Ai null 4 3Jajodia Sandhu模型 核心完整性 元组的包含的例子 对于U 实例 若此时S用户的实例是 不是 4 3Jajodia Sandhu模型 核心完整性 元组包含的例子 对于U 实例 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUS用户的实例是 StarshipObjectiveDestinationTCEnterpriseUExplorationUTalosUUEnterpriseUExplorationUMarsSSEnterpriseUSpyingSMarsSS在U 实例中 被包含的元组需要去掉 4 3Jajodia Sandhu模型 核心完整性 2 空值完整性多级关系R满足空值完整性 当且仅当对R的每个实例Rc满足如下条件 1 对所有t Rc t Ai null t Ci t CAK 即 空值的安全级别与主键相同 2 Rc不含有两个有包含关系的元组 如果对每个属性Ai 不会出现下列情形 a t Ai Ci s Ai Ci 或 b t Ai null且s Ai null 则元组t包容元组s 4 3Jajodia Sandhu模型 核心完整性 3 实例间完整性一个多级关系Rc满足实例间完整性 当且仅当对所有c c 存在一过滤函数Rc Rc c 这里 满足以下性质 对每个满足t CAK c 的元组t Rc 存在元组t Rc 满足t AK CAK t AK CAK 2 对每个不属于AK的Ai有 t Ai Ci 若t Ci c t Ai Ci 否则 3 通过彻底消除包Rc 中所有的包含元组得到过滤函数的最后结果 4 Rc 中所有元组都是从上述规则导出的 4 3Jajodia Sandhu模型 核心完整性 过滤函数将多级关系映射成不同实例 过滤函数限制每个用户看到在他许可的那部分多级关系 U 用户看到的过滤后的实例 S 用户看到的实例 4 3Jajodia Sandhu模型 核心完整性 空值完整性受到破坏的例子 包含关系受到破坏 4 3Jajodia Sandhu模型 核心完整性 4 多实例完整性 PI R满足多实例完整性 当且仅当对每个Rc有对所有Ai AK CAK Ci Ai 允许下面的实例存在 禁止下面的实例存在 问题出在哪里 4 3Jajodia Sandhu模型 核心完整性 多实例完整性 PI 表明 多级关系的主键是AK CAK CR CR为不在AK中的属性的安全级属性集 与SeaView模型不同的是 PI只要求函数依赖 去掉了多值依赖 防止产生大量的多实例元组 限制了在同一实体产生的实体多实例中 同一安全级上 每个属性只有一个取值 4 3Jajodia Sandhu模型 对数据操纵的影响 1 规定和限制多级关系用R A1 C1 An Cn TC 表示 A1表示外观主键c 用户直接看到并且与c实例Rc交互R的剩余实例可以分成三种情况 1 Rc c 使得c c 3 Rc c 使得c 与c不可比 4 3Jajodia Sandhu模型 对数据操纵的影响 2 特性的限制 处理问题的思路 保持信息的 向上 流动 语句格式尽量接近标准SQL从安全考虑 由于 特性的限制 1 c 用户不能插入 更新 删除Rc c 4 3Jajodia Sandhu模型 插入语句 3 插入语句C 用户执行的INSERT语句 假设t为插入元组 安全级属性Ci全部隐式地赋予值c 且t Ci c t TC 发出插入操作的当前用户的安全级 如果Ai包含在插入语句的属性列里那么t Ai ai 如果Ai不在列表中则t Ai Null 1 i n 若关系中存在与所插入元组t主键相同的元组t 若t TC t TC 为满足多实例完整性 拒绝插入 若t TC t TC 允许插入 4 3Jajodia Sandhu模型 插入语句的例子 U 用户想插入元组 插入后的结果 4 3Jajodia Sandhu模型 插入语句的例子 S 用户插入元组 插入后的结果 两个元组是属于不同实体的 4 3Jajodia Sandhu模型 插入语句的例子 U 用户插入元组 插入后的结果 插入必须接受 产生实体多实例 4 3Jajodia Sandhu模型 更新语句 4 更新语句 1 语句格式 C 用户执行的UPDATE语句 谓词p 可能包括含安全级属性的条件 在SET子句中只能包含数据属性 相应的等级属性隐式地决定了是c 对等于用户安全级的实例的影响与传统UPDATE相同 对更低级关系实例无影响 操作结果反映给安全级高于c的用户的实例 4 3Jajodia Sandhu模型 更新语句的例子 U 用户执行的UPDATE语句 实际上此时的数据为 4 3Jajodia Sandhu模型 更新语句的例子 修改后的结果 U 用户看到的 S 用户看到的 实际上是插入了一条元组 U用户看到的是什么 为什么 包容关系 4 3Jajodia Sandhu模型 更新语句的例子 S 用户发出的更新语句 更新的结果 是否正确 是 4 3Jajodia Sandhu模型 更新语句的例子 S 用户发出的更新语句 更新的结果 4 3Jajodia Sandhu模型 更新语句的例子 U 用户发出的更新语句 更新后S 用户看到的结果 传递更新数据 4 3Jajodia Sandhu模型 关于更新的形式化 2 更新的形式化c 用户对Rc的UPDATE操作 设s t Rc t满足谓词p 第一步 对s中的每个元组t t被元组t 替代 除了在set子句中给出新值的属性外 t 与t完全相同 类似于不带安全级情形下的UPDATE的语义 4 3Jajodia Sandhu模型 关于更新的形式化 c 用户对Rc的UPDATE操作 被更新的属性Ai的t Ci c时设s t Rc t满足谓词p 第二步 为了避免信号通道 我们需要引入另外的元组t 对于低于c的级别的用户隐藏t被t 替换的效果 c是执行UPDATE语句的用户的安全级 4 3Jajodia Sandhu模型 更新的形式化例子 执行UPDATE语句之前 U 用户看到的 S 用户看到的 S 用户发出的更新语句 4 3Jajodia Sandhu模型 更新的形式化例子 S 用户看到的结果 第三步 对安全级高于c的数据的影响 传递性 对于每个属于SET子句的Ak 若t Ak NULL 令 即 c 用户修改等于其安全级的t Ak 的非空值为sk 对于Rc c 有多个元组在Rc c中 与t有相同的外观主键 即u A1 C1 t A1 C1 且u Ak Ck t Ak Ck 将被修改为u Ak Ck 为保持多实例完整性必须修改u Ak 的值为sk 4 3Jajodia Sandhu模型 更新影响高安全级实例 为维护实例间完整性 我们在Rc c中插入t 和t 若t 存在并在消除包容时保留下来 实际上就是c 用户更新了标记为c的属性时 不必插入新元组 4 3Jajodia Sandhu模型 DELETE语句 5 删除操作 删除操作删除Rc中满足谓词条件的元组 从 特性来看 只有那些满足t TC c这个附加条件的元组t才会被从Rc中删除 为保持实例间完整性 多实例化的元组也被从Rc c中删除 若t C1 c 则删除t时 Rc c任何实例化元组将从Rc c中删除 于是t代表的实体从多级关系中消失 若t C1 t C1 4 3Jajodia Sandhu模型 比较 与SeaView模型相比 更新时产生了更新数据的 向上 传递 从而在一定程度上减少了多实例的产生 由于INSERT UPDATE语句的操作可能导致不止插入一条元组 仍然会产生大量的多实例 4 3Jajodia Sandhu模型 多级关系分解与恢复算法 TCB子集法实现DBMS 依赖底层的多级操作系统实现强制访问控制 多级关系的物理存储 拆分为单级关系的集合 多级关系被访问时 再由单级关系恢复而成 前述Rc不是实际数据库中保存的数据 而是恢复得到的结果 分解与恢复算法 分解 水平分解 垂直分解 SeaView 水平分解 Jajodia Sandhu 安全级信息保存在数据库中 又没有加密 存在一定风险 4 3Jajodia Sandhu模型 多级关系分解与恢复算法 4 3Jajodia Sandhu模型 多级关系分解与恢复算法 分解 对于每个多级关系模式 R A1 C1 An Cn TC 分解是 单级基关系Dc A1 C1 An Cn 的集合 每个安全级c上有一个关系 元组安全级是c的元组集合 4 3Jajodia Sandhu模型 c级别用户的查询 c级别的用户查看到的实例 c 用户总是看到并与c 实例Rc交互 c级别的用户更新 插入 修改 删除 元组就会被加入到Dc 修改或者删除Dc c 用户发出更新时 Dc被修改 而在其他Dc c c中没有变化 Rc的改变必须正确地反映到Rc c 并且在Dc c 这是在恢复的过程中完成的 对c c的Dc 的集合并运算 INSERT UPDATE和DELETE处理时 实施分解算法 4 3Jajodia Sandhu模型 分解 插入语句的处理 插入语句 a 分解将插入元组t到Dc b 元组t的构造 t Ai ai若Ai被包含在INSERT语句的属性列表中 t Ai NULL若Ai不在列表中 并且t Ci c 对于1 i n成立 c 没有其他的插入 对于Rc c的集合 恢复算法将使用对c c的Dc 的集合并运算重构Rc c 由于t在Dc中 它将在Rc c中 4 3Jajodia Sandhu模型 分解 UPDATE语句的处理 更新语句 只有Dc内的元组会被修改 情形I 假设c 用户成功地执行了update语句 再次设 S t属于Rc t满足谓词p 对于每个t属于S 要考虑两种情形 t C1 c 此时在c级上没有元组t的多实例 元组t由c级用户创建 只有一个元组u属于Dc 满足u A1 C1 t A1 C1 动作 用元组u 替换u a u A1 C1 u A1 C1 b 并且对于k 1 直接在原有的元组基础上修改 4 3Jajodia Sandhu模型 分解 UPDATE语句的处理 更新语句 只有Dc内的元组会被修改 情形II 2 t C1 c 这时 元组t将在c级被多实例化t在更新前没有在c级被多实例化 t来自Dc c 不存在元组u属于Dc 满足u A1 C1 t A1 C1 动作 加入元组u到Dc元组u的产生 u A1 C1 t A1 C1 并且对于k 1 是一个特殊的记号 表明这个值从Dt Ck 中相应的元组得到 4 3Jajodia Sandhu模型 分解 UPDATE语句的处理 更新语句 只有Dc内的元组会被修改 情形II 2 t C1 动作 用下面的元组u 替换u u A1 C1 u A1 C1 并且对于k 1 4 3Jajodia Sandhu模型 分解 DELTETE语句的处理 删除语句 只有Dc内的元组会被删除从Dc中删除元组u u满足条件 u A1 C1 t A1 C1 并且对于k 1 i 若t Ci c 则u Ai Ci t Ai Ci 且 ii 若t Ci 4 3Jajodia Sandhu模型 恢复算