21：第7.3~5节推理泄漏原理课件.ppt

第7.3~5节推理泄漏与控制 7.3 统计数据库模型 7.4 推理控制机制 7.5 推理攻击方法 推理控制模型* 本节将使用推理控制模型对敏感数据的泄漏问题进一步做理论探讨。 介绍几种对数据库统计推理泄漏的方法 数据库统计推理控制机制 对数据库的推理攻击 限制统计的机制 7.3 统计数据库模型 1、信息状态 统计数据库系统的信息状态有两个分量：存储在数据库中的数据和外部知识。 外部知识是指用户关于数据库所拥有的知识。有两类： 工作知识，是关于数据库中所表达的属性和可用的统计类型的知识； 补充知识，是数据库非正常提供的知识，可能是机密的。 2、统计类型 特征公式：统计是对有公共属性的记录子集算出，子集由特征公式C指定。非形式地说，特征公式是在属性值上应用算子or（+），and（*）和not（~）的任意逻辑公式。例如： （性别=男）*（（部门=计划处）+（部门=销售部））） 简写为：男*（计划处+销售部） 查询集：属性值与特征公式C匹配的记录的集合称为查询集。例如，C=男*销售部的查询集由“李三多”、“齐贺礼”的记录组成。 用C代表公式及其查询集两者 |C|表示查询集中的记录个数。 用ALL代表查询集是整个数据库的公式。 对任何查询集C，有C∈ALL 由公式（A1= a1）*（A2= a2）…（AM= aM）描述的查询集称为基本集合，这里aj是Aj的某个值。若属性Aj有|Aj|种可能的值，则数据库有：E= 个基本集合， 其中有些可能是空集合。 设g代表所有基本集合的最大基数，即g是具有相同属性值的个体的最大个数。（重复个体） 如果g=1，那么每一个体能用唯一的基本集合来识别。当数据库总记录数N?E时，才有可能g=1。 表7.3中部分属性的可能值如下： 性别：男，女 2 部门：计划处，技术部，销售部，经理室 4 评语：甲，乙，丙，丁 4 若表7.3的属性仅限于性别、部门和评语，则 E=2*4*4=32。 因为没有任何同事有公共特征，即因每一记录都唯一地可识别，所以g=1。 统计类型有二类：矩统计量和顺序统计量 矩统计量 q(c,e1,…,eM)= （7-1） 形式的统计量称为有限矩，这里e1，…，eM都是非负整数。e1+…+eM称为矩的阶数。 Count(c)=|c| 可以写成q(c,0,…,0)是0阶矩。 Sum(c,Ai)= 可以写成q(c,0,…,0,1,0,…,0)是1阶矩。 注意Sum仅能应用于数值性数据， Count可以用来算出相对频度，相对频度表示被统计个体占总记录数的百分数。 属性A1的方差，属性A1和A2的协方差，以及相关系数可以用二阶矩等表达。 A1的方差 A1和A2的协方差 A1和A2的相关系数 以后将用q(c) 表达（7-1）形式的任意统计和由有限矩导出的任意统计。 顺序统计量 常用的最大值、最小值、中值三个。因为它们根据查询集中元素属性值的大小按序排列而确定的，故名顺序统计量。分别为： 顺序统计量 值得注意的是：当|C|是偶数时，C中某属性的中值是指两个中间值的较小者，而不是它们的平均值。 如表7.3中所有男同事的工资是（550，600，750，800， 800， 1000）， 所以median(男，工资)=750。 m阶统计 从m个不同属性值推得的统计称为m阶统计，例如， Count（ALL）是0阶统计， Count（男），Sum（ALL，工资），Count（计划处+销售部）是1阶统计， Count（男*计划处），Sum（男*工资）都是2阶统计。 3、敏感统计的泄漏 如果一个统计能泄漏出某个体（个人、单位、集团等）的太多的机密信息，则称此统计为敏感的。敏感性的确切标准是由系统的安全策略确定的。 例如，美国人口普查局对经济数据的和所用的标准是“n-响应，k%-支配”规则。即如果一个和的统计能确定其中不多于n个加数占和数的k%以上，则称此统计为敏感的。 例如，若一次查询得出两个个体的某属性值之和 ，而由外部知识知道 ，显然 。 根据查询集大小是2或大于2的机密信息计算的统计也可能被分类为敏感的，因为若有“知道一个或几个值”的补充知识，则容易推出另一个值。 所有敏感的统计是不允许实施的。 此外，限制某些非敏感统计也许是必须的，如果它们可能导致敏感统计的泄漏。 例7-1 假定在抽样数据库中仅根据大小为1的查询集算出的那些数据才算敏感的，那么