【作者】 王宁；

【导师】 于戈；

【作者基本信息】 东北大学 ， 计算机软件与理论， 2017， 博士

【摘要】 随着互联网技术的迅猛发展以及信息技术的不断普及,信息系统产生大量具有丰富语义的数据。通过对这些数据进行挖掘分析,可获取更有价值的信息来指导商务活动,提升消费者以及用户体验。然而,数据中包含大量隐私敏感信息,如何在保护隐私信息的前提下,发布有价值的查询挖掘结果成为亟待解决的问题。差分隐私模型,作为新兴的隐私保护技术,在面对强背景知识的攻击者时,仍能可靠地保护敏感信息,并可以提供严格的理论证明。因此构建高可用的差分隐私发布结果成为当下数据安全领域的研究热点。本文围绕高维数据上满足差分隐私约束的统计信息发布问题展开讨论。基于高维数据的统计值查询本质上依赖列(维)或列(维)组合对应的计数值。高维数据的查询结果对单条记录十分敏感,一条记录可能会对所有列以及列组合的计数值产生影响,因此需要添加大量的噪音以实现隐私保护的目的。这使得传统的基于数据低敏感假设而设计的发布方法,在高维数据发布问题上不可用。面对该挑战,本文根据高维数据统计查询的特点,设计相应的数据发布策略。大部分基于高维数据的统计信息查询可分为两类:计数值统计信息查询和top-kk统计信息查询,进一步,计数值统计信息查询可分为单位计数值查询和范围计数值查询,top-k统计信息查询分为top-k频繁列查询和top-k频繁列组合(项集)查询。本文针对不同的查询设计了不同的发布方案,主要研究内容和创新点包括:第一,研究了高维数据上适用于单位计数值查询的差分隐私直方图发布问题,提出了基于截断技术和分组技术的混合方发布方法。该方法充分利用截断技术和分组技术的优点并克服其不足之处。其次,设计了具有低敏感度的惩罚函数,可有效衡量发布结果中因截断和分组而引入的误差。而较低的敏感度亦可优化截断长度和分组大小的选择。基于该惩罚函数,采用两阶段选择方法,进一步优化截断长度和分组大小的选取。使用真实数据集进行的实验评估证明,基于两阶段参数选择方法的混合技术发布的直方图比当前解决相同问题的最好技术在精度上有显著提高。第二,研究了高维数据上适用于范围计数值查询的差分隐私直方图发布问题,提出了基于三阶段处理框架的发布技术。该技术主要面向满足一定图依赖关系的序列数据。传统的差分隐私技术是针对数据域中的值与值之间具有全序关系的情况设计。而图约束是一种偏序关系。针对该问题,三阶段处理框架首先利用截断技术对数据库中的原始数据进行截断处理,以降低单条序列数据对最终发布值的影响。随后,依赖查询负载,将表示依赖关系的图结构分解为满足全序关系的子域,以充分利用已有数据发布技术。最后,为每个子域构建负载感知的树结构并进行一致性调整。基于调整后的树,可以发布具有较高精确度的事件直方图。大量实验评估验证了上述三个阶段的优化处理的有效性。第三,研究了差分隐私top-kk频繁项集发布问题,提出了PrivSuper挖掘框架。具体地,已有技术直接将差分隐私基本的构建模块(指数机制或拉普拉斯机制)应用于Apriori挖掘框架,来发布差分隐私top-k频繁项集。该方法不可避免地造成隐私预算消耗与k的数量成正比。较大的隐私预算消耗意味着过多的噪音被添加到发布结果中,使发布结果无用。因此,设计差分隐私技术的目标是在满足隐私约束的前提下,降低隐私预算的消耗。针对上述问题,PrivSuper以满足差分隐私约束的方式直接搜索最大频繁项集。在频繁项集挖掘中,一个频繁项集的所有子集都为频繁项集。所以,当PrivSuper探测到一个最大的频繁项集,可以在不消耗任何隐私预算的前提下,直接判定该项集的某些子集是频繁的。此外,提出了新的自定义差分隐私构建模块“序列指数机制”,该机制用于选择候选项,以扩展当前的频繁项集。理论研究表明,如果当前频繁项集不可以被进一步扩展时,即该项集为最大频繁项集,序列指数机制不消耗隐私预算。与以前基于Apriori的发布技术的对比实验,验证了PrivSuper的有效性。第四,研究了差分隐私top-k频繁列发布问题,提出了两阶段选择方法。当前解决频繁列发布问题的技术是直接从整个列域中选择频繁的列。然而,该类技术经常会对频数接近于临界值的列产生误判断,这里临界值指在第k频繁列对应的频数值(计数值)。本文提出的两阶段选择方法的核心思想为将列域中的列按其是否接近临界值分为两类,然后利用这两类中列的特点分别调用不同的频繁列选择技术。除此之外,本文根据列的分布信息,设计满足差分隐私约束的隐私节约机制,对列域进行自适应地动态分块,采用以块为中心的方式选择频繁列。通过隐私节约机制,可以在不消耗隐私预算的前提下选择部分频繁列。最后,本文从理论上分析了隐私节约机制的隐私保护程度。大量基于真实数据集的实验验证了本文提出技术在发布结果精确度方法的显著效果。总之,本文分别研究了基于高维数据的差分隐私数据发布问题,包括适用于单位计数值查询和范围计数值查询的差分隐私直方图发布问题,差分隐私top-kk频繁项集发布问题,以及top-k频繁列发布问题,并提出了有效的解决方案。理论分析和实验结果都表明,本文提出的方法较之前最好的方法有显著的提高。更多还原

【Abstract】 With the rapid development of Internet and widespread usage of information technology,the big data era is coming with strong and ever-growing demands on analyzing data.These analyses are crucial and worth billion dollars in the business,which can be used to guide business activities to further improve the user experi-ence.Such analyzed data typically contain sensitive individual information.Hence,it is becoming an urgent issue to publish analysis results without posing privacy.Recently,differential privacy(DP),as the first practical privacy protection model,has attracted a lot of attention,as it can provide rigorous theoretical guarantee,even in the face of attackers with strong background knowledge.Not surprisingly,it is becoming a new research hotspot in the data security domain to design a DP-based algorithm with high utility output.This dissertation discusses how to publish statistics for high dimensional data under DP.These statistics essentially depend on the counts of some columns(dimensions)or column(dimension)patterns.However,a single record in high dimensional data may have a significant impact on the count of each column.In another word,the statistics are greatly sensitive to the variation of one record.That challenges existing works proposed under the assumption of low sensitivity,because now a large amount of noises have to be added into the published values,so as to protect the individual information.The problem this dis-sertation studies thereby is to build a series of new publication strategies for queries on high dimensional data.To the best of our knowledge,most queries basically fall into two categories:count publication and top-k columns publication.Each of them can be further divided,that is,unit count and range count for the former;frequent itemsets and frequent columns for the latter.This dissertation designs different yet important techniques specific to various queries,all of such contributions can be summarized as below.Firstly,a hybrid solution based on the truncating technique and grouping tech-nique is proposed to publish a differentially private histogram,which can be utilized to answer the unit count query on high dimensional data.Prior works have validated that truncating records or grouping columns can individually and effectively improve the accuracy of published results in different scenarios.The new hybrid solution is designed on top of such two techniques for accuracy,by leveraging their advantages.Besides,a smart penalty function with low sensitivity is designed to measure the errors caused by truncating and grouping operations.It contributes to computing more accurate parameters,such as truncating length and grouping size.Moreover,by a two phase selection method,such parameters can be derived efficiently,while,simultaneously,the final results are published with high accuracy.Extensive ex-periments on a broad spectrum of real-world datasets validate the effectiveness of the hybrid method with the two-phase selection technique,when compared with state-of-the-art methods.Secondly,a three-step framework is proposed to publish a differentially private histogram for range count query on high dimensional data.And the framework focuses on sequence data,which follow some dependence and can be modeled by a graph.Sequences might be identified by arbitrary paths in the graph.It poses great challenges to existing differentially private mechanisms because they mainly target at normalized domains with fixed and aligned dimensions.To tackle this problem,the three-step framework publishes data in three steps:1)carefully truncates the original sequences by trading off errors introduced by the truncation with those introduced by the noise added to guarantee privacy,2)decomposes the graph into path sub-domains based on a given group of queries so that some existing techniques can be used,and 3)employs a deeply optimized approach to construct a tree-based histogram for each sub-domain,to enhance the accuracy of range queries.Besides,the consistency enforcement is run for the tree-based histogram,to further boost the accuracy.Finally,we evaluate the performance of all proposals through a series of experiments.Thirdly,a new differentially private mining framework is designed to publish all top-k frequent itemsets.Most existing frameworks directly apply the generic differ-ential privacy mechanisms(laplace mechanism and/or exponential mechanism)into the Apriori framework to mine top-k results.That is simply but makes the privacy budget consumption proportional to k.A large privacy budget consumption means more noises are required and then impairs the accuracy of published itemsets.Hence,reducing the budget consumption is a key research direction.Towards this end,a novel framework called "PrivSuper" is designed and implemented,which contains both a new algorithm and a new differential privacy mechanism.Specifically,Priv-Super directly searches for maximal frequent itemsets,and then immediately adds their sub-itemsets to the final results with cost-free budget consumption.During the search,PrivSuper applies a customized mechanism to extend the current item-set with one more item,termed "sequence exponential mechanism".Notably,this mechanism does not consume any privacy budget,if the current itemset cannot be further extended(i.e.,it is one maximal frequent itemset).Extensive experiments using several real datasets demonstrate that PrivSuper achieves significantly higher result utility compared to previous Apriori-based solutions.Finally,a two-phase selection solution is proposed to publish top-k frequent columns under differential privacy.Existing works directly select frequent columns from the column domain,which is far from ideal due to the large privacy consump-tion or misjudgments for columns with frequencies close to the frequency(called threshold)of the kth frequent column.The new two phase selection solution is presented to carefully choose frequent columns in two different phases.Its main idea is to classify columns into two distinct categories based on whether or not the frequency is close to the threshold.Frequent columns are chosen from the two categories using different techniques,based on the property of columns in different categories.Furthermore,by analyzing the distribution of columns,a privacy free mechanism is designed to partition the columns into blocks dynamically and choose the frequent columns in a block-centric way.Hence,some columns can be judged as frequent without consuming privacy budget.Finally,the privacy free mechanism is proved to satisfy differential privacy theoretically.Extensive experiments on real datasets verify the significant improvement of our proposals on the accuracy.To sum up,this dissertation focuses on differentially private data publication on high dimensional data,including the problems of histogram publications for the unit count query and range count query,and the problems of top-k frequent itemsets and frequent columns publication.Many important and effective techniques are proposed to solve these problems.Theoretical analysis and experiments show our proposals significantly outperform existing up-to-date methods.更多还原