传统数据库隐私泄露的研究

杨高明，李敬兆，张顺香，朱广丽

（安徽理工大学 计算机科学与工程学院，安徽 淮南 232001）

1 引言

随着信息技术和数据库技术的快速发展，各行各业均存储了海量数据，这些数据仍然以惊人的速度不断产生.为有效从数据中提出有效知识而不泄露个人隐私信息，在数据发布之前需要进行隐私保护，于是隐私保护的数据发布技术应运而生[1].隐私保护的数据发布目的就是在数据发布给使用者之前，对数据进行某种形式的变化，使数据包含尽可能多的有用信息并使个人隐私信息得到保护.

隐私保护的数据发布包括两方面的内容：一方面为防止私有敏感信息的泄漏提供有力的技术保障，消除信息拥有者在共享信息时的顾虑，促进信息交流和共享；另一方面还强调减少实施隐私保护所带来的非敏感信息损失，保证共享信息的质量，提高共享信息的可用性.隐私保护的数据发布需要考虑两方面的敌对攻击，即连接攻击和背景知识攻击.对于连接攻击目前主要采用k-匿名方法予以解决，而对于背景知识攻击主要解决方法较多，如(α,k)-匿名，l-多样性，t-逼近等方法.这些方法目前都不是完美的解决方案，存在这样那样的问题，有许多问题需要解决.

本课题的预期研究成果，将有助于指导隐私保护的数据发布过程，极大提高发布的数据的隐私保护度，提高数据的效用，减少信息损失，具有重要的现实意义，有着较高的研究价值和良好的应用前景.

2 k-匿名发布技术的研究

随着网络技术和数据存储技术的发展，产生和存储了大量的数据.仅仅从这些数据中删除明确的标识符(如姓名、身份证号码)并不能阻止隐私的泄露，通过与外部数据的联接(link)依然可以发现个体的敏感属性[1].Samarati和Sweeney[2]为解决隐私发布提出k-匿名技术.对数据集中泄露信息的准标识符属性采用概化和隐匿处理，使每个记录都至少与其他k-1个记录的准标识符有相同值.概化处理使得数据的精确度有所降低，但是基本保持了原来的语义信息，但过度的概化会造成不必要的信息损失，降低数据的效用.隐匿技术可以看做概化的特殊形式，即所有值均以“*”代替[3].保证发布的数据质量并使隐私信息得到保护是一项挑战性的工作，隐私保护的数据发布必须考虑数据质量和数据效用之间的平衡.

图1 数据集属性分类树

基于概化的技术实现k-匿名[4]模型需要考虑数据集的属性.对于分类属性，具体的值被给定的分类树概化值取代.在图1中，父节点Professional比子节点Engineer和Lawyer更一般.根节点ANY_Job代表Job的最一般值.如果一个数值属性区间分类系统给定了，情况与分类属性相似，更普遍情况是没有为数值属性预定义的分类系统.

目前学者提出许多实现k-匿名的方法，前人已经证明采用概化/隐匿技术实现最优化匿名是NP难度问题，于是有人提出基于聚类的[5]方法.基于聚类的方法首先采用某种衡量标准将数据集划分成簇，对仅包含数值属性的数据集一般发布簇的质心和簇的记录数;对包含数值属性和分类属性的数据集，通常概化簇使它们达到k-匿名[6].相比仅仅使用概化/隐匿技术的k-匿名需求，基于聚类的方法在匿名可以产生更好的数据质量.

概化实现k-匿名模型存在搜索空间过大问题，许多作者提出的启发式方法虽然减小了搜索空间，但是存在信息损失过大，数据效用降低的问题.另外还有其他一些问题，比如文献[7]对离群点敏感.由于文中的算法选择最远的点开始构造新的簇，如果数据集包含远距离的离群点，这些离群点就有可能被选择作为构造新簇的种子，结果会导致信息损失过大.

3 (α,k)-匿名的研究

概化/隐匿方法建立在预定义的域概化层次树结构和值概化层次树结构之上，会带来不必要的信息损失.为减少信息损失，G.Aggarwal等提出使用聚类方法实现k-匿名[8].k-匿名模型可以有效的抵御连接攻击，但是对于背景知识攻击和同质攻击却无能为力[9].为抵御背景知识攻击和同质攻击Machanavajjhala A提出l-多样性模型[9]，它要求每个簇类的敏感值要满足l-多样性约束，以提高敏感值与其所属个体的连接难度，该模型使用概化/隐匿方法，王智慧等[6]提出适用聚类方法实现l-多样性隐私保护，他们首先对数据进行聚类，然后对聚类后的簇概化处理;(α,k)-匿名模型[10]也是为了弥补k-匿名模型的不足而提出的隐私模型，它是通过控制等价类中敏感值的出现频率来实现敏感值的多样性.韩建民等[11]针对(α,k)-匿名模型限制每个敏感值为固定的α，提出为每个敏感值设置一个敏感值，这种方法对敏感值数目较少时可以很好的提高隐私保护度，对于敏感数值较多的情况就不适用了.

4 连续数据发布的研究

在连续数据发布模型中，数据发布者有以前的版本T1,…,Tp-1，现在需要发布Tp，其中Ti是Ti-1插入或者删除数据以后的更新版本.这个问题假设同一个个体的全部记录在所有的发布中不变.即使每个发布T1,……,Tp被单独匿名，隐私需求可能通过比较不同的版本和排除一些可能的受害者敏感值而受到损害.这个问题假设数据动态更新，而序列匿名假设数据是静态的且在一次发布中可以全部得到.进一步说，这个问题假设所有的发布共享同一个数据库模式，而序列发布问题假设全部发布是同一个基础表的投影.

连续的数据发布问题假设攻击者知道时间戳和受害者的QID，所以攻击者确切知道哪个发布包含受害者的记录.Byun等[12]首先提出一种插入新记录的隐私保护连续匿名发布技术.具体地说，它保证每个版本满足l-多样性，这要求每个qid组包含至少l个不同敏感值.如果一个值在qid组内发生的很频繁，攻击者可以容易推导出受害者的敏感值.因此这个实例不能阻止属性联接攻击.

数据流作为一种新型的数据模型，它以不同的更新速率连续地流进和流出计算机系统，具有实时性、连续性、无界性、无序性等特点，这些特点决定了只能对数据流进行单遍扫描.近年越来越多的学者关注数据流管理系统[13]和数据流挖掘算法的研究，并取得了许多成果.随着数据挖掘工具能力的不断增强，对个人隐私和数据安全造成了很大威胁.为了保护客户隐私，删除明确表明客户身份的信息，比如姓名、地址、电话号码等，然而剩余的属性依然可以被用来发动链接攻击.如果恶意攻击者知道顾客的个别属性，就很容易定位到某个具体顾客[2].

目前在对原始数据的保护主要方法有：扰动、数据交换、k-匿名等.近来有学者研究增量k-匿名方法，该方法在新的元组到来以后插入旧元组集或者从旧元组集删除元组，增量数据发布主要研究旧发布和新发布之间匿名泄露问题[14].匿名数据流和匿名增量数据集有某些相似性，它们都随着时间推移增加数据量，但是增量数据集和数据流中所讨论的推理攻击的假设条件并不一样，因此增量更新的数据匿名算法并不适合数据流.

5 总结与结论

传统数据库领域面临隐私泄露的风险，有许多学者研究如何抵御隐私数据的泄露，提出了很多有效的技术和方法.本文从传统数据库的角度对目前存在的技术进行了梳理.重点探讨了k-匿名、l-多样性、(α,k)-匿名等隐私保护技术.

〔1〕杨高明，杨静，张健沛.隐私保护的数据发布研究[J].计算机科学.2011,38(9):11-17.

〔2〕Sweeney L. Achieving k-anonymity privacy protection using generalization and suppression [J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems. 2002, 10(5): 571-588.

〔3〕Kisilevich S, Rokach L, Elovici Y, et al. Efficient Multidimensional Suppression for K-Anonymity [J]. IEEE Transactions on Knowledge and Data Engineering. 2010,22(3): 334-347.

〔4〕杨晓春，王雅哲，王斌，等.数据发布中面向多敏感属性的隐私保护方法[J].计算机学报，2008,31(04):574-587.

〔5〕童云海，陶有东，唐世渭，等.隐私保护数据发布中身份保持的匿名方法[J].软件学报，2010,21(04):771-781.

〔6〕王智慧，许俭，汪卫，等.一种基于聚类的数据匿名方法[J].软件学报，2010,21(04):680-693.

〔7〕Byun J, Kamra A, Bertino E, et al. Efficient k -anonymization using clustering techniques [C]. Bangkok,Thailand: Springer Verlag, 2007.

〔8〕Aggarwal G, Panigrahy R, Tom, et al. Achieving anonymity via clustering [J]. ACM Trans. Algorithms.2010,6(3):1-19.

〔9〕Machanavajjhala A, Kifer D, Gehrke J, et al. l-diversity:Privacy beyond k-anonymity [J]. ACM Transactions on Knowledge Discovery from Data. 2007, 1(1): 1-52.

〔10〕Wong R, Li J, Fu A, et al. (α, k)-anonymous data publishing[J]. Journal of Intelligent Information Systems.2009, 33(2): 209-234.

〔11〕韩建民，于娟，虞慧群，等.面向敏感值的个性化隐私保护[J].电子学报，2010,38(7):1723-1728.

〔12〕Byun J, Sohn Y, Bertino E, et al. Secure anonymization for incremental datasets[C]. Seoul, Korea, Republic of: Springer Verlag, 2006.

〔13〕金澈清，钱卫宁，周傲英.流数据分析与管理综述[J].软件学报，2004,15(8):1172-1181.

〔14〕Wu Y, Sun Z, Wang X. Privacy Preserving k -Anonymity for Re-publication of Incremental Datasets[C]. IEEE Computer Society, 2009.