计算机研究与发展JournaIofCbl11PuterResearchandDevelopmentISSN100O一1239lCNll一1777lTP44(Suppl.):214一219，2007数据发布中维护敏感数据高可用性的隐私保护方法王雅哲杨晓春王斌于戈(东北大学信息科学与工程学院沈阳110004)(yaZh司122@163.Cor。)ATechniqueforPreservingHighUsabilityofSensitiveDatainDataPublishingWangyazhe，YangXiaochun，Wa眼Bin，andyuGe(&六田lofl刀ormatifon&ienceandEng￡er￡ng，nOrt为NasternUeni二￡y，the儿，S以ngll0004)AbstractTrade一offbetweensafetyandusabilityisthemainconcerninprivacypreservingdatapublishingproblems。Recentlytherepresentedanoveltechnique一anatomyforpublishingsensitivedata，whichcanassurethesafetyandaccuracyofpublisheddata。Butthedisadvantageofanatomyisthatitrnaygreatlydisturbtheassociationanddistributioninformationinthemicrodata。Tosolvethisproblem，anewmethodcalledClassAnatomyispresented，whichcanpreservethesafetyandaccuracyinjustthesamewayasanatomy.Andmeanwhile，ClassAnatomycanpreservemoreinformationinthemicrodatabydividingthedataspaceaccordingtotheclassinformationofthequasi一identifierattributes.TwodifferentClassAnatomyalgorithmsaregiven:thetoP一downsingledimensionaldivisionalgorithm一TDAandthebottom一uPmulti-dimensionaldivisional即rithm一BUA.Experimentresultsshowthatwithoutcompromisingsafety，ClassAnatomycandramaticallyreducetheinformationlossinpublisheddataandrnakethedatamoreuseful.Keywordsdatapublishing;dataprivacy;datausability;anatomymethod;1一diversity摘要数据的安全性和可用性是敏感数据发布与共享环境中面临的主要问题.近期提出了一种利用有损连接保证敏感数据发布的安全性的方法一Anatomy，其优点在于发布的数据中保留了原始数据的准确值.但是用Anatomy方法处理数据会损失大量数据的关联信息和分布信息，降低数据的可用性.针对这种问题提出了维护数据高可用性的ClassAnatomy方法，它继承了Anatomy方法的安全性和准确性等优点，并通过对数据空间进行分类划分的方法保留原始数据的关联及分布信息.给出了两种lassAnCatomy算法，包括基于信息论的自顶向下的单维分类划分算法(Tl〕A)和基于高维网格的自底向上的覆盖分类划分算法(BUA).实验结果表明，lassAnatComy方法在保证数据安全性的基础上能够极大地减少数据的信息损失，从而提高数据的可用性.关健词数据发布;数据隐私;数据可用性;Anatomy方法;1一多样性中图法分类号TP309在信息化的现代社会，各组织机构为了合作或研究目的常发布一些包含个体隐私信息的数据.这种应用面临的主要技术挑战是数据的安全性和可用性.数据发布中面临的主要安全问题是链接攻个体信息的数据进行连接的方式推演出隐私数据.可用于链接攻击的属性叫做准标识符(quasi-identifier，Ql).为了防止链接攻击，近期提出了一种新颖的隐击川，即将隐匿了个体标识属性的数据(如姓名、身份证号等)通过其他属性与由其他渠道得到的包含收稿日期:2007一07一05私保护方法—Anatomy[1.它通过准标识符属性2与敏感属性间的有损连接保护数据的隐私信息.如基金项目:国家自然科学基金项目(印匆刃36);教育部新世纪优秀人才支持计划基金项目;霍英东教育基金会青年教师优选课题基金项目(1沙仍27)王雅哲等:数据发布中维护敏感数据高可用性的隐私保护方法图1为发布的医疗记录表经过Anatomy方法处理后得到的数据.从图中可以看出，Anatomy方法首先将原始数据记录分组，然后将准标识符信息和分组号发布为准标识符属性表(QIT)，将各分组的敏感数据统计信息发布为敏感属性表(51，).通过分组号建立两表间的有损连接保护敏感信息.如图1所示，假设恶意用户可以确定Qrr表中的记录1为Anne的信息，但是通过分组号与ST表进行连接，可得到Anne的敏感属性取值为flu和gastrtiis的概率各为1/2，不能确定Anne的真实敏感属性值，发布的数据是安全的.Anatomy方法发布数据的安全性由1一多样性保证〔2一]3.1一多样性指发布的数据中的每个分组最多只有1/2的记录具有相同的敏感属性值.uTPelDI乙扣法八尹Su，G阳“户IDGm“户ID及义”5巴GJu”t1(Allne)110020Ml1lful2220050Fl1gastritis1312002lM22dysPePsial4202063F22headache15200026M33月ul6301066F33gastrltlsl(a)QIT(b)ST图IAnatomy方法处理后发布的数据虽然Anatomy方法保证了发布数据的安全性与准确性，但在没有考虑到准标识符与敏感属性间的关系，因此可能极大扰乱原始数据的关联和分布信息，如果在分组时考虑到准标识符属性的分类信息，在保证敏感属性的1一多样性同时尽量将具有相同的准标识符属性类别的记录分为一组就能在分组间保留更多的原始数据信息，使发布的数据具有更高的可用性.然而用户的应用需求难以预期，因此分类划分要考虑所有的准标识符属性.另外，精细的划分可能会破坏分组的2一多样性，危害隐私数据的安全.因此本文面临的挑战是如何在不破坏数据安全性的同时在所有准标识符属性上进行精细的分类划分，保留尽量多的数据关联及分布信息.针对以上问题本文提出了ClassAnatomy方法.它继承了Anatomy方法发布数据的安全性和准确性等优点，并通过在准标识符属性上对原始的数据空间进行分类划分的方法改进了其破坏原始数据关.根据分类划分策略的不同，2种具体的ClassAnatomy算法:基于信(TDA)和基于高维网格的自底向上的覆盖分类划分算法(BUA)，并通过大量的实验对得到的数据的可用性进行了对比分析.1相关工作保护隐私信息是数据发布与共享环境中面临的主要问题，如何保护隐私信息安全，同时发布具有高可用性的数据一直是研究的热点问题.sweeney提出了k一匿名模型保护隐私数据不受链接攻击川.概括和隐匿是实现数据k一匿名化的主要方法〔’川，文献【5一12〕深人研究了基于概括和隐匿的k一匿名化问题.Mcyerson等人在文献〔21]中证明通过最少的概括实现数据k一匿名化(k>2)是NP难的.因此许多算法〔6一川都采取启发式方法缩小搜索空间.文献〔]8提出了一种自顶向下逐步特化的方法，在进行k一匿名化的同时保留数据的分类信息.文献〔]3提出了一种更强的隐私保护要求一1-多样性.本文方法基于这种隐私保护要求.文献〔]2提出了一种新颖的方法—Anatomy.它通过准标识符属性和敏感属性间的有损连接来保护隐私数据的安全，并且给出了基本的Anatomy算法.由于基本的Anatomy算法可能会极大地破坏原始数据准标识符属性和敏感属性之间的关联信息与数据的分布信息.本文针对以上问题进行了研究，提出了更好的保留原始数据的关联及分布信息的ClassAliatOnly方法.2问题定义设T二{t，，勺，…，，，}为用户要发布的原始数据表.T中含有n条记录t*(1簇1簇n).设T包含d个准标识符属性Al，AZ，…，AJ和一个敏感属性，其中A，1(镇1簇d)的值域记为D‘，可以是分类属性，如Sex，IZP‘心e，也可以是数值型属性，如Age.A:的值域记为D:，是分类属性〔”〕.记t〔]1为记录t的A‘属性的值，t【d十1〕为其敏感属性的值.每条记录t都可以看成是d维数据空间月内的一个点，整个数据表可以看做口内的点集.保护发布数据的安全性的思想主要基于Anatomy，即在数据记录的分组内建立准标识符属性和敏感属性的有损连接.因此沿用Anatomy方法中分组，2一多样性划分等一些基本概念的定义〔21.2.iclassAnatomy法如何在不破坏安全性的前提下对原始A:联及分布信息的缺点本文提出了息论的自顶向下的单维分类划分算法空间进行尽可能精细的分类划分是ClassAnatomy方法要解决的主要问题.这里定义平均划分度(Al男Div)衡量分类划分精细程度:AtjgDi。=1成忍习《N蔽一万不下一IQG‘t，__T}1入qg，其中，旧G*}为划分出的每个分组的大小，N明为原始数据记录被分成的分组数，}T}为原始数据表的大小.对准标识符属性，在值域上定义最小划分粒度的顺序序列，并在其上定义划分层次树.定义1.分类划分.在准标识符属性构成的d维数据空间中根据准标识符属性的类别将数据记录分组，每个分组具有相同的准标识符属性类别，每条记录属于且仅属于一个分组.根据划分策略的不同，分类划分可分为两类:单维分类划分和覆盖分类划分.定义2.单维分类划分.对于每个准标识符属性A‘1(成1成d)，在其值域D‘上定义划分及认:且一’D云，将D*分成互不重叠的子区间.将每个且v*作用于标识符属性构成的d维数据空间，将其划分成互不重叠的子空间，每个子空间中的记录被分成一组.定义3.覆盖分类划分.对准标识符属性构成的d维数据空间定义划分DivT:DlxDZx二‘XDd~D;XD玉X…xD二，将数据空间分成若干子空间.子空间互不重叠，或者被某各子空间覆盖.每条数据记录只与包含它的最小子空间中的记录分成一组.定义4.1一多样性分类划分.1一多样性分类划分将原始数据记录分成的每个分组都满足1一多样性.定义5.安全准分组.1一多样性分类划分将原始数据表中记录分成的每个分组都叫做一个安全准分组，记为QG‘.所有安全准分组的集合记为QG，.定理1.安全准分组一定存在.证明.文献【3」中给出原始数据表T具有1一多样性性质的条件:T中出现最频繁的敏感属性值的个数不大于n/Z.如果此条件不满足，无论是其他k一匿名方法还是Anatomy方法都无法得到满足1-多样性的结果[3〕。可以将此条件称为可对原始数据表进行1一多样性划分的初始条件.当T满足初始条件，在最坏的情况下，安全准分组存在且只有一个，即原始数据表.3ClassAnatomy方法lCassAnatomy法分为两个阶段:分类划分计算机研究与发展0207，44(增刊)(ClassDivide)阶段和精细划分(FineDivide)阶段.ClassAnatomy的重点在于ClassDivide阶段，之后FineDivide算法可沿用基本的Anatomy算法.ClassAnatomy算法的结构如算法1所示.算法1.ClassAnatomy.输人:原始数据表T、准标识符属性的划分层次树;输出:准标识符属性表QIT、敏感属性表ST，①CI口ssD艺ivde(T);了，将原始数据表划分成安全准分组QG，，/③凡②foreachQGneDivide(QG‘任QG:‘);④输出QIT，ST.本文提出了两种不同的oassAnatomy算法:基于信息论的自顶向下的单维分类划分算法—TDA—适用于原始数据密度小或敏感属性值分布比较集中的情况;基于高维数据空间网格的自底向上的覆盖分类划分算法—BUA，一一适用于原始数据密度大且敏感属性值分布较均匀的情况.3.1自顶向下的单维分类划分算法TDA算法根据准标识符属性的划分层次树对原始数据表在准标识符属性上进行自顶向下划分.设划分层次树上的一个节点为v，其子节点记为hcild(v)，在节点v上的一次划分记为div(v).如果一次划分将分成的每个分组都满足1一多样性，那么此划分就是合法的.另外，如果两个划分div(v1)和div(vZ)都是合法的，但是按照某种衡量标准div(v，)比div(。:)划分成的分组敏感属性值的多样性更好，就认为div(vl)比div(vZ)更有效.引入信息理论中嫡的概念定义多样性损失(dievlsrtyl侧)来衡量划分的有效性.对于准标识符属性A上的一次划分div(v)，设兀为在此属性上取值属于v的所有记录的集合，cT为在此属性上取值属于。(‘echi公(v))的所有记录的集合.}兀}，}Tc}分别表示集合中记录的条数.敏感属性的值域为Ds.对于一个记录的集合G，多样性的量度可表示为嫡的形式]3[:Divers(G)=一习，Cl玉p(，)150(p(:))，其中P(:)为敏感属性取值为:的记录条数占集合中总记录条数的比例.每次划分的多样性损失可定义为DiverLsos(v)=Divers(Tv)一c七认似又鲁(，)11u}Devi八‘.)cT算法2.TDA.输人:原始表T、每个准标识符属性的划分层次树;王雅哲等:数据发布中维护敏感数据高可用性的隐私保护方法输出:准分组Q炕.①将DivT初始化为每个准标识符属性划分层次树的根节点;②whileDivT中存在合法的划分己iv(x)do③计算并找到最小的DiversLos:(x);④用child(x)替换DivT中的x;⑤endwhile⑥按照DivT划分原始数据表T，并输出准分组QG，.算法2给出TDA的具体步骤.TDA算法维护一个DivT向量.DivT首先被初始化为准标识符属性划分层次树的根节点，然后在其中选择合法的且最有效的划分节点对原始数据进行划分，并更新iDvT.循环进行，直到不存在合法的划分，3.2自底向上的覆盖分类划分方法在数据密度大且敏感属性值分布比较均匀的情况下，自顶向下的单维分类划分算法可能需要较长的搜索时间.算法3给出了一种基于高维空间网格的自底向上的覆盖分类划分算法.算法3.BUA输人:原始数据表T按照准标识符属性构成的d维数据空间几、每个准标识符属性的划分层次树;输出:准分组QG，.①按照准标识符属性最小的划分粒度将口划分成网格Grids;②QG:=0;③do找到Grids中存在所有合法的网格x;④将每个合法网格内的数据记录构成一个准分组添加到QG，;⑤在。内删除所有添加到QG，内的记录;⑥初亡egr(Grid:);⑦whileGridt.护日;⑧if存在剩余的未被划分的记录⑨PrcoessResidual:();⑩endif该算法根据属性的划分层次将准标识符属性构成的d维数据空间划分成网格(grid).划分首先从最小粒度进行，然后将每个满足1一多样性的网格中的数据记录提取出来构成安全准分组，对剩下的记录按照更大的粒度进行划分(merge).对于剩余的记录，在不破坏1一多样性的同时将其添加到较近的安全准分组中.BUA算法对数据空间进行划分后提取所有安全准分组.如果还有剩余的记录，则需进行网格合并，即对于每个分类属性将当前的划分粒度扩大到划分层次树上的上层节点，对于数值型属性将相邻的划分区间两两合并.合并后重新构成的网格远大于原来的网格.这是基于这样的假设:原始数据空间数据密度较大，且敏感属性值分布均匀，在较小的划分粒度上的大部分网格都满足1一多样性的性质，因此剩下的数据记录就变得比较稀疏，需要将网格扩大到较大的范围才能构成满足1一多样性的安全准分组.其他的不同合并方法将在以后的工作中进一步考虑.对于剩余记录，需要在不破坏安全性的基础上将剩余记录添加到类别最相近安全准分组中.具体方法是搜索已划分出的所有安全准分组，优先在包含剩余记录的最小网格空间中开始搜索，如果找不到可添加的安全准分组再逐步扩大搜索范围，优先选择较小的准分组进行添加.4实验及结果分析实验采用随机数据生成器生成两组不同的模拟数据集，其中数据集TSI的敏感数据值分布比较集中.数据集TSZ的敏感数据值分布较为分散.数据集的规模取为103一104.数据集涉及5个准标识符属性(包含1个数值型属性及4个分类属性)和一个敏感属性.数据集的具体信息如表1所示:表1实验数据集信息属性类型不同敏感值个数划分层次A群数值型动态划分区间G已nder分类型划分层次树(Zlevel)尺口ec分类型划分层次树(3level)卉妇~eg分类型划分层次树(Zlevel)E以“‘口t艺on分类型划分层次树(4level)Income(class)分类型无(敏感属性)lCassAnatomy方法的安全性由1一多样性保证.因此只需测试数据的可用性.本文以对发布数据进行查询的结果的精确性来衡量发布数据的信息损失.本文构造了若干具有不同覆盖度的查询集(查询数量大于103，覆盖度为1%一10%)，并定义信息损失度InofrsoL:=0镇艺1共!01Er。/QI，(}Q}为查询集的大小).其中￡rr*=Irlt?一rl，’、1/rlt兮(rl，?为查询q‘对原始数据的真实结果，lr叮为对发布数据的近似查询结果).4.1实验结果分析首先验证TDA和BUA与基本Anatomy算法(BA)对于不同集得到的发布的信息损失，实验设定多样性参1二3.选择覆盖度为10%的计算机研究与发展2007，44(增刊)查询测试集.图2给出了实验结果:宗）55另9一｝璐口七召‘1洲570603510（冲）550闷uo~｝曰二口召三905706035110一axoatasetcadinrality(留1)(幻数据集路1的平均划分度10一3xoa拍setcaainrality(”2)b)数据集兀2的平均划分度(图2不同算法发布的安全数据的信息损失比较从图2可以看出，对于两种不同的数据集TDA与BUA的信息损失都远小于BA算法.说明了本文方法能够很好地保留数据的原始信息.图中结果显示对数据集1污1，BUA算法的结果略好于TDA算法，而对数据集丁52，Tl〕A算法的结果较好.这是由于在数据敏感信息分布较均匀的情况下，对数据空间在小粒度上进行分类划分得到的多数子空间内的记录基本上都能构成合法的准分组.因此自底向宋）uo｝51>「0肠巴，是.3L.0.0.0.02684Q工，1上搜索的BUA算法的结果好一些.而在敏感信息分布不均匀的情况下，BUA算法在较小的划分粒度上不能过滤掉大部分记录，合并后子空间粒度大大增加，此时，TDA算法的结果优于BUA算法.为了对两种ClassAnatomy算法进行进一步对比分析，本文测试了两种算法的平均划分度，结果如图3所示:（*）uo『5｝卜~Q。助.J。之10一3xoaasetcatdinali钾ra)数据集昭1的平均划分度(10一。xoatasetcauinrality(b)数据集昭2的平均划分度图3不同ClassAnatomy算法的平均划分度比较从图3可以看出，对于敏感数据值分布较为均匀的数据集两种算法的平均划分度都比较小.对于数据集151，BUA算法的平均划分度小于TDA算法，而对于数据集TSZ，TDA算法的平均划分度较小，这进一步说明了上面分析的结论.另外，从图3还可以看出，随着数据集数据量的增大，平均划分度逐渐减小.这说明随着数据空间数据密度的增大，分0宙9）5的召7曰吕洲~目口匕旧己1类划分更易于在精细的划分粒度上得到满足1一多样性的准分组，使得发布的数据的信息损失相对较小.图4显示了采用覆盖度不同的查询集进行测试，对信息损失实验结果的影响.实验选择大小为5000的数据集进行测试.从图中可以看出，信息损失量的测试结果不受查询集的覆盖度的不同的影响.宙）5明。闷uo~1月u仁己‘一0750603516003150QueryCoverage(叼QueryCoerage(哪v(a)查询集对留1信息损失衡量的影响b)查询集对乃2信息损失衡量的影响(图4不同查询测试集对的信息损失衡量的影响王雅哲等:数据发布中维护敏感数据高可用性的隐私保护方法5结论及未来工作本文研究了安全数据发布中的数据可用性的问题，提出了维护数据高可用性的CI玺&、latomy方法，并给出了两种的CI玺因七lat0Illy算法.ClaSSAnatomy的特点是即保证了发布数据的安全性与准确性，又保证较低的信息损失，且算法时间复杂度低，易于实现.实验结果显示，IC赴粉勺latonly方法与基本的Anatonly方法相比能更好保留原始数据间的关联及分布信息.今后将继续研究支持分类的Anatomy方法，另外也将进一步研究多敏感属性数据发布问题.参考文献〔1〕LSween即，k一onaymity:Anll记elforprotectingphvacy.Inten1ationalJournalnoUncetrainty，Fuzziness，andKnowled盼Basedsystems，2002，10(5):557一570[21XKXiao，YFTao.AnBtOmy:。。pleand。班ecttevprivacypreesrvation.In:Prcoofthe32ndlnt’IConfonVe叮LargeDataBase，Newyork:ACMPres，2006.139一150[3]^Machanavjajhala，JGehrke，DKefer.1一diversity:Privcayebyondk一anonymitylnPrcoofthe22ndlnt’ICbnfonDataEngineering，LosAlamitos:IEEECbnlputerS龙ietyPrse，2006[4〕PSamarati，Lsweeney.General云ztzndatatoprvoideaon，m、tywhendisclsoi飞inforn妞tionln:Prcoofthel7thACM51(;ACI，一SIGMOD一SIGz、RT衍rnposiumonPrinciplesfoaDtab脱5邓tems，Newyork:ACMPress，1998[5]CC瑰garwal.onk一ano叮mityandthecurseofdimensionalityIn:Pxcoofthe3lstlnt’IConfonVeryLa馆eDataBases，NewYork:ACMP~，2005.901一909[61GAggarwal，TFe血r，KKellthapadi，etal.八Jlonynllzedatbles.In:Prcoofthelothlnt’1助nfonDatab搜Th仪》ry，eBrlin:Spri呢er，2005.246一258219[7]RBayarodnadRAgraw公.Dataphvacythroughoptin班Ik-anony介tion.In:PrcooftheZlstlnt，16nfonaDtaE吃ineedng，L巧川翻itso:IEEEC冶mputers冗ietyPres，2005.217一228[8]BCMFung，Kwang，PSYu.To-pdowns卿ialotionfroinforl11ationandprivacyprseavrtion.In:PrcooftheZlstlnt’1肠nfonaDtaE雌ineeting，LosAI习nlitos:IEEE(为mPuter5又ietyPres，2005.205佗16[9]vlyengar.Transfo二1吃datatosatisfyp‘cavycsnotraints.In:P叹ofthesthACMSIGKDDInt’1(为nfonKnowledgeDisocve尽andDataMini呢，Newyork:ACMPres，2002.279一288[10]KLeFevre，DJDewitt，RRaamkrishnan.1llcognito:Efifcientufll一domaink一anonymity.In:PrcooftheACMSIGMODInt’10川fonManagementofData，Newyork:ACMPres，2005.29一60[11」KLeFevre，DJDewitt，RRalllakrishnan.Mondrianmultidimensional卜annoymitylnPrcofothe22ndlnt’ICbnfnoDataEngineeri眼，L韶Aiamitso:IEEECbmputerS又ietyPress，2006[12〕AMeyerson，RWilliasm.Onthecomplexityof叩timalk-anonymity.In:Prcofothe23rdACMSIGACT一SIGMOD-SIGARTSym卯siumonP巧nciPlesofDatab践Systelns.NewYork:ACMPres.2004.223一228王雅哲女，1984年生，硕士研究生，主要研究方向为数据隐私保护.杨晓春女，1973年生，副教授，CCF高级会员，主要研究方向为数据库理论与技术、数据隐私、无线传感器网络数据管理(yangxc@mail.neu.edu.cn).王斌男，1972年生，博士研究生，主要研究方向为分布式数据处理、ZPP、Web查询处理.于戈男，1962年生，教授，博士生导师，cF高级会员，主要研究方向为分布式数据库、Web服务、数据流.
