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

第7.3~5节推理泄漏与控制; 推理控制模型* ;7.3 统计数据库模型 ;表7.3 敏感数据库表示例;1、信息状态;2、统计类型 ;查询集：属性值与特征公式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。 ;统计类型有二类：矩统计量和顺序统计量 ;Count可以用来算出相对频度，相对频度表示被统计个体占总记录数的百分数。;属性A1的方差，属性A1和A2的协方差，以及相关系数可以用二阶矩等表达。 A1的方差 A1和A2的协方差 A1和A2的相关系数 以后将用q(c) 表达（7-1）形式的任意统计和由有限矩导出的任意统计。 ;顺序统计量 ;顺序统计量 ;m阶统计;3、敏感统计的泄漏 ;例如，若一次查询得出两个个体的某属性值之和 ，而由外部知识知道 ，显然 。 ;根据查询集大小是2或大于2的机密信息计算的统计也可能被分类为敏感的，因为若有“知道一个或几个值”的补充知识，则容易推出另一个值。 所有敏感的统计是不允许实施的。 此外，限制某些非敏感统计也许是必须的，如果它们可能导致敏感统计的泄漏。 ;例7-1 假定在抽样数据库中仅根据大小为1的查询集算出的那些数据才算敏感的，那么 Sum(销售部，工资)=2100 Sum（男*销售部，工资）=1600 都不是敏感的，但 Sum(女*销售部，工资) = Sum(销售部,工资)- Sum(男*销售部,工资)=500， 暴露了销售部唯一女同事黄爱玲的工资值。因此以上两个统计之一应被限制。（例1） ;设R是特定用户提出的统计集合，而K是用户的补充知识。每当用户能从R和K推出限制统计的某些东西，就出现统计泄漏。 用信息论术语来说，“若H(q|K,R)H(q|K)，就出现统计泄漏”。 这里H(q|K)和H(q|K,R)分别是给定K和给定K、R时q的暧昧度。 ;敏感统计的统计泄漏称为个体泄漏。如果此泄漏不需要补充知识，即K是空，称为结果泄漏；如果补充知识是必需的，则称外部泄漏。 对个体泄漏，为了把泄漏的值和特定个体匹配起来，补充知识总是需要的。 如例1中，Sum(女*销售部，工资)=500，仅当用户知道黄爱玲是销售部唯一的女同事，才能确定这是她的工资。 ;由统计集合R所泄漏的信息量用 H(q|K)?H(q|K,R)定义。当q被确切地确定时，即H(q|K,R)=0时，称为确切泄漏，否则称为近似泄漏。确切泄漏又可分为选择性泄漏（指定个体的泄漏）和简单泄漏（非选择性）。或分为全局泄漏（泄漏全部个体的机密值）和局部泄漏（非全局泄漏）。例1是一种确切泄漏。 ;近似泄漏又可分为三种类型： ;揭示出对某y，q≠y，即在否定意义上的泄漏（否定泄漏）。例如，上例可推出 Sum（销售部*女，工资）≠750 揭示出q以概率p属于区间[L，U]，即在概率意义上的泄漏。用式子表示为 [L，U]称为可信区间，p称为可信程度。 ;例7-3 设q的估计值是近似正态分布的随机变元q^，其标准离差是 ，那么有 即q有90%的可能性落在区间 中;4、完全秘密性和保护 ;泄漏是受保护的与可泄漏的;注意，这一定义已覆盖了近似泄漏的所有形式，除了否定泄漏。也覆盖了确切泄漏，此时p=1，而k=0。 显然，对足够大的k和足够小的p，任何统计都是可泄漏的。 我们仅关注于相对小的k和接近于1的p的泄漏。当一个满足等式（7-2）的估计值 能根据发布的统计集合R得出，就出现了泄漏。 ;例如 设q=Su