（计算机应用技术专业论文）网络搜索日志中的隐私度量方法研究.pdf

网络搜索日志中的隐私度量方法研究摘要 论文题目： 专业： 硕士生： 指导教师： 网络搜索日志中的隐私度量方法研究 计算机应用技术 刘俊裕 刘玉葆副教授 摘要 随着互联网的发展及搜索引擎的广泛引用，针对用户搜索日志的分析与研究有了 较快速的发展，并被应用于用户个性化剖析、搜索结果排序调整、搜索关键词修正和 建议等等，为搜索引擎及用户带来额外价值，成为信息检索领域的一个研究热门。与 此同时，由于搜索日志当中包含较深的用户使用痕迹，表面的及潜在的各种用户隐私 资料。如果在搜索日志分析研究之余不能处理好隐私保护问题，将造成用户隐私暴露 的风险。2 0 0 6 年8 月，美国在线的搜索日志隐私泄漏丑闻向世人敲响了警钟。此后，在 信息检索社区，有相当一部分学者开始对搜索日志隐私保护问题进行研究。然而，这 些研究都以特定的情景或上下文假设作为前提。同时，没有人提出令人信服的统一隐 私威胁度量标准去描述搜索日志中的隐私威胁程度。 论文从建立合理的隐私度量出发，结合统计学和语义学对搜索日志建立层次分类 模型，对隐私威胁度量进行量化刻画。将此隐私权威胁度量作为搜索日志隐私分析的 一个参考标准。 语义模型包括语义层次结构、语义相似度和语义含量三个方面。语义层次结构由 开放目录计划的网页目录数据构造而成。而语义相似度则建立在语义本体w o r d n e t 之 上。语义相似度实现了两种相似度的计算方法，并作出改进。自上而下迭代地求解搜 索日志的查询与开放目录语义层次结构中的结点之间的语义相似度，形成对搜索查询 的多粒度、多层次分类。把多次分类中有最大相似度的结点作为在开放目录语义层次 结构中给予搜索记录的最佳定位位置。根据搜索日志在开放目录语义层次结构中的定 位信息，结合其深度、祖先结点和后代结点等信息，给语义含量下定义。统计模型借 鉴信息检索和文本挖掘中常用的t f i d f 权重模型来描述隐私攻击者对查询日志的隐私 - i 网络搜索日志中的隐私度量方法研究摘要 攻击能力。和一般t f i d f 的计算方法有所区别，我们将搜索日志看作文档，并视搜索 引擎为语料库，结合t f - i d f 对搜索日志进行统计分析。 语义含量结合t f - i d f 表构成查询日志的可识别度；将语义含量根据对查询日志的 分类标签进行加权，得出查询日志的敏感度。最终以可识别度和敏感度作为查询日志 隐私度量。我们透过详尽的建模过程展示其合理性，并以有效的搜索日志算法展现其 可用性。 以论文提出的查询日志隐私度量，实现一个对a o l 用户搜索日志分析的原型演示 平台。 关键词：隐私度量；搜索曰志；本体；语义分析；w o r d n e t 网络搜索日志中的隐私度量方法研究a b s t r a c t t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： r e s e a r c ho nq u e r yl o gi d e n t i f i a b i l i t ya n ds e n s i t i v i t y c o m p u t e ra p p l i c a t i o na n dt e c h n o l o g y j u n y ul i u a s s o c i a t ep r o f e s s o ry u b a ol i u ab s t r a c t t h ea n a l y s i sa n dr e s e a r c ho nq u e r yl o ga r ep r o s p e r o u st o g e t h e rw i t ht h er a p i dd e - v e l o p m e n to fi n t e r n e ta n ds e a r c he n g i n e s f o c u s i n go nt h ep u r p o s e ss u c ha sp e r s o n a l i z e d p r o f i l e ，r a n k i n gr e f i n e m e n t ，q u e r yc o r r e c t i o n ，a n dq u e r ya d v i c e ，t h eq u e r yl o gr e - s e a r c hc o m m u n i t yi sh e a t e di nt h ei n f o r m a t i o nr e t r i e v a ls o c i e t y t h es t u d yo nq u e r y l o g b r i n g sb o n u sb o t ht ot h es e a r c he n g i n e sa n dt h e i re n du s e r s b u tt h es i g n a t u r e s ，m a r k s ， f i n g e r p r i n t sa n do t h e rp r i v a c yi n f o r m a t i o na r ea l w a y si n e v i t a b l ya n du n c o n s c i o u s l yl e f t a n dc o n c e a l e di nt h eq u e r yl o g t h er i s ko fp r i v a c yi n f o r m a t i o na r ec o n t i n g e n ti nt h e p u b l i s h ，i n v e s t i g a t i o n ，r e s e a r c ha n do t h e ru b i q u i t o u ss c e n e si fw i t h o u ta p p r o p r i a t ep r e s e r - v a t i o na n dp r o t e c t i o n ag o o de x a m p l er i g h th e r ei sa o ll e a r n tal e s s o nf r o mt h ea o l q u e r yl o gp r i v a c yb r e a c hs c a n d a li na u g ，2 0 0 6 a sar e s u l t ，s o m es c h o l a r sl a u n c h e dt h e s t u d yo nq u e r yl o gp r i v a c yp r e s e r v a t i o n h o w e v e r ，m o s to ft h ew o r k sa r ej u s to nt h e f l y m a n yr e s e a r c ho nq u e r yl o gp r i v a c yp r e s e r v a t i o ni nt h ec o n t e x ta r eb a s e do nt h e i r o w na s s u m p t i o n s i ti si nn e e dau n i f i e de v a l u a t i o ns t a n d a r dt od e s c r i b et h ed e g r e eo f p r i v a c yp r e s e r v a t i o no rh o wp r i v a c yap r i v a c yt e c h n i cp e r f o r m e do nq u e r yl o gp r i v a c y p r e s e r v a t i o n t h ed i s s e r t a t i o na i m sa te s t a b l i s h i n gas e to fr e a s o n a b l eq u e r yl o gp r i v a c yp r e s e r - v a t i o ne v a l u a t i o nm e t h o d s t om a k ei th a p p e n ，s o m ep r i v a c ye v a l u a t i o nm e t r i c sa r e p r o p o s e di nt h et h e s i s ，c o m b i n i n gb o t ht h es t a t i s t i c a la n ds e m a n t i ca s p e c t s s e m a n t i ch i e r a r c h y ，s e m a n t i cs i m i l a r i t y , a n ds e m a n t i c c o n t e n tm a k eu pt h es e m a n - t i cm o d e l t h es e m a n t i ch i e r a r c h yi sd e r i v e df r o mt h eo p e nd i r e c t o r yp r o j e c t ( o d p ) ， i i i 网络搜索日志中的隐私度量方法研究 a b s t r a c t s a y , at r e es t r u c t u r e b e s i d e s ，t h es e m a n t i cs i m i l a r i t yb u i l to nt h es e m a n t i co n t o l o g y w 0 r d n e t t w os i m i l a r i t i e sc a l c u l a t i o nm e t h o d sa r ed i s c u s s e di nt h et h e s i sa n ds o m ei m o p r o v e m e n t sd e p l o y e d o n ep a i ro ft e r m s ，w h i c ha r ef r o maq u e r ya n dan o d eo fo d p s e m a n t i ch i e r a r c h yr e s p e c t i v e l y , i se m p l o y e dt ot h es e m a n t i cs i m i l a r i t yf u n c t i o nf o rc l a s - s i f y i n g a f t e raf e wr e c u r s i v ec l a s s i f i c a t i o ns t e p sa td i f f e r e n td e p t ho ft h eh i e r a r c h y , a m u l t i - g r a n u l a rc l a s s i f i c a t i o nf o rq u e r yl o gf o r m e d t h e nw ep o s i t i o naq u e r yo nt h en o d e o fo d ps e m a n t i ch i e r a r c h yb yc o n s i d e r i n gt h ei t sm a xs i m i l a r i t y a tl a s t ，as e m a n - t i cc o n t e n td e r i v e df r o md e p t h ，a n c e s t o r s ，a n dd e s c e n d a n t so ft h en o d e t h es t a t i s t i c a l m o d e lb e n e f i t sf r o mt h ef a m o u st f - i d fw e i g h tm o d e l w ew e i g h tt h eq u e r yf o rac l e a r d e s c r i p t i o no fh o wd a n g e r o u saq u e r yi sw h i l ee x p o s i n gt ot h em a l i c i o u s r a t h e rt h a nt h e t r a d i t i o n a lm e t h o d ，w ed on o te s t i m a t et f i d fw e i g h tf r o mal o c a lc o r p u s ，b u tt r e a tt h e s e a r c he n g i n eq u e r y i n gr e t u r na sa r e s p o n s ef r o ma e n o r m o u so n e w ed e f i n eas e n s i t i v i t yw e i g h tv e c t o rb a s e do nt h e g e n e r a lc l a s s e si no d ph i e r a r c h ys o d i f f e r e n tq u e r yh a si t so w n w e i g h t t h ew e i g h tt o g e t h e rw i t hs e m a n t i cc o n t e n tr e s u l ti n q u e r yl o gs e n s i t i v i t y a n dc o m b i n i n gt h es e m a n t i cc o n t e n ta n dt f i d fc o u l dp r o d u c e q u e r yl o gi d e n t i f i a b i l i t y s e n s i t i v i t ya n di d e n t i f i a b i l i t ya r et h et w ou l t i m a t em e t r i c sw e p r o p o s e df o rq u e r yl o gp r i v a c y f i n a l l y , ap r o t o t y p es y s t e mi si m p l e m e n t e dt op e r f o r ma o lq u e r yl o ga n a l y s i sa n d e v a l u a t i o n k e yw o r d s ：p r i v a c ye v a l u a t i o n ；q u e r yl o g ；o n t o l o g y ；s e m a n t i ca n a l y s i s ；w o r d n e t i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明本人完全意识到本声明的法 律结果由本人承担 学位论文作者签名：童立垡整 日期：丝也：! ：兰 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、 院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以 采用复印、缩印或其他方法保存学位论文 学位论文作者签名：未1 】俊岳毒 日期：2 户l o 年6 月上日 网络搜索日志中的隐私度量方法研究 第1 章引言 第1 章引言 随着互联网的兴起，搜索引擎得到长足的发展。搜索引擎公司之间的竞争达到了 白热化。市场竞争的激烈，加快了对用户使用搜索引擎及类搜索引擎工具留下的历史 记录搜索日志( q u e r yl o g ) 的分析、研究与深度挖掘。对搜索日志的分析可以获得用 户个性化剖析、提升搜索效果、搜索建议及搜索词修正等等一系列的额外价值。搜索 日志分析与搜索引擎的发展同一步调，已经成为信息检索领域的一个研究热门。 2 0 0 6 年8 月，美国在线( a m e r i c ao n l i n e ，a o l ) 本着为信息检索研究社区提供帮助的 初衷，对其发布自家搜索引擎时长三个月的搜索日剧1 引。这是一份庞大的数据，显 示出a o l 对研究社区的极大友善。这个数据集除了将用户i d 用伪码替换，并没有经过 其他处理。像这样缺少高强度匿名保护措施的大规模搜索日志数据集，这是前所未有 的。整个数据集结构良好地呈现了大约6 5 万用户的近两千万条搜索记录。本是善意的 数据集发布，却以大量个人用户隐私信息暴露告终p 引。这对a o l 和依赖这类数据进行 研究的学者们都是一个沉重的打击。 在这场用户隐私数据泄漏的丑闻当中，最严重的就莫过于个人用户被单独地从搜 索日志数据集中识别出来。即使在数据发布之前，a o l 将社会保险号、驾驶执照号和 信用卡号等直接蕴含用户个人身份的内容删除，纽约时报( n e wy o r kt i m e n y t ) 的记 者还是从被处理过的数据中人工识别出个人用户州。他们证实一名i d 为4 4 1 7 7 4 9 的用户 就是居住在美国佐治亚( g e o r 西a ) 州l i l b u r n 地区的一位老太太，t h e l m aa r n o l d 。老太太 查询过大量关于l i l b u r n 地区的商业和服务信息。这一点提示使得猜测方很快将她的住 处缩小到这一地区。而这一地区只有1 1 0 0 0 左右的人口。随后老太太又搜索了j a r r e t t a r n o l d 。这是她的其中一位家庭成员。当然，在浑然不觉有任何风险的前提下，老 太太又连续搜索了其他家庭成员的名字。这无疑帮了n y t 个大忙。n y t 记者透过 在y a h o o ! w h i t e p a g e 目录服务查询l i l b u r n 地区姓a r n o l d 的居民名单。结果只有1 4 人。 目标又进一步缩小至难以置信的规模。不幸的是，a r n o l d 老太太出现在名单里。再加 上老太太搜索的某些老年医疗信息，最后结果不言而喻。即使能够这么巧合而又这么 精确地识别出单个用户的机率实际上并不会太高，但一个个案就足够让广大搜索引擎 一】 网络搜索日志中的隐私度量方法研究 第1 章引言 用户忧心。 由于这样的丑闻，众多集体诉讼和抱怨连同媒体的口诛笔伐纷纷投向了a o l 。a o l 顿时被千夫所指，成为千古罪人。期间，有评论者认为，a o l 及所有的搜索引擎服务 提供商根本就不应该将搜索日志这样的敏感数据发布到公共领域。显然这不符合搜索 引擎公司的实际。搜索引擎公司需要保证搜索服务质量；在线广告投放商需要掌握一 定的用户搜索日志以作广告投放分析；再者，最近兴起的个性化搜索引擎也需要关心 用户的一系列搜索兴趣和行为模式。作为利益的主体，搜索引擎公司会尽量争取将搜 索日志发布至研究社区供研究用途，递交到第三方作分析以至政府机构的安全审查。 出于对用户需求的精确把握，在进行搜索日志分析研究时，会提出包含用户行 为、习惯、及兴趣的各种数据，识别出用户在使用搜索引擎时所潜在的趋势及模式。 然而，在这些被用以正当分析用途的搜索日志当中，除了用户i d 这种唯一性的信息被 隐匿了外，却还隐含着大量而详尽的个人资料。搜索日志的分析研究，充满着机遇与 挑战。a o l 在发布的搜索日志数据集饱受隐私泄漏丑闻责难的事件，更能说明，即使 像a o l 这样专业的互联网搜索引擎公司，面对在搜索服务上的隐私泄漏威胁，也有百 密一疏的时候。而过去简单地将用户i d 作替换这种简单直观甚至有些天真的隐私保护 方法，显然早已力不从心，失去其本应有的保护作用。 隐藏在搜索日志背后的潜在隐私威胁无处不在，并且难以预测。到目前为止，国 内外学者对搜索日志隐私保护的问题上进行了有限的研究。这些研究都是基于特定的 应用情景或上下文假设。同时，在研究中，没有人提出一套令人信服的统一隐私威胁 度量标准去衡量搜索日志的隐私攻击与保护的程度。 因此，本论文对搜索日志进行语义和统计方面的分析，旨在建立可用并有效的搜 索日志隐私度量而着手研究。 1 1 背景知识 建立搜索日志隐私威胁度量，首先要明确什么是搜索目志的隐私泄漏，什么是搜 索日志的隐私攻击以及一次成功的搜索日志隐私攻击的定义。本节对以上若干问题进 行描述。 一2 一 网络搜索日志中的隐私度量方法研究 第1 章引言 1 1 1 搜索日志( q u e r yl o g ) 要描述什么是搜索日志的隐私泄漏，首先要对搜索日志进行定义。由于本论文研 究的对象都是以a o l 在2 0 0 6 年发布的搜索日志数据荆为基础，我t f 以a o l 搜索日志数据 集为标准作格式定义。 q = q l ，q n 如公式1 1 所示，q 是搜索日志的数据集，q i 是一条实例，即搜索记录( q u e r ) r ) ，n 是 搜索日志数据集中实例基数。公式1 2 是实例的详细信息，i d 代表本搜索记录的用户 标识，整个搜索日志数据集中相同的用户有多条搜索记录，毛是搜索记录g 的搜索记录 集，t i 是集丁中的一个搜索关键词。 q2 弛正) ，其中qeq , 写= 。1 ，k ) ( 1 2 ) 正d 、= q t 引俄i d = 劬i d ，其中吼q ，q j q 显然，互d 代表搜索日志中同一用户的所有搜索词项。 1 1 2 隐私攻击 在搜索日志数据集中，同一用户搜索过的词项的集合用正d 表示，其中i d 是用户在 搜索日志数据集中的标识。在搜索日志的隐私问题中，最严重的隐私问题是用户可能 被独立地重新识别出来。这种依赖分析属于特定用户的搜索日志来识别用户的隐私攻 击形式被称作重识别攻击( r e - i d e n t i f i c a t i o na t t a c k ) 。这种攻击模式通常是假设特定的 目标用户的搜索词项集合正d 中的一部分会被攻击者掌握并用作用户重识别，我们称作 识别集合厅= q l q t ) 。假设，是隐私攻击者实行隐私攻击前可利用的搜索日志信 息。若攻击者能够利用集合j 提供的信息结合攻击者自身的先验知识p ，将目标用户的 范围缩小到一定程度甚至直接将目标用户识别出，就可以认为攻击者实施了一次成功 3 网络搜索日志中的隐私度量方法研究 第1 章引言 的隐私攻击。 也np 。纪u 八i v l 6 其中，也d 2 t , d ，6 0 公式1 3 描述了攻击者的一次隐私攻击。u 表示攻击成功后攻击者能够确定将用 户i d 与之配对的个人身份集合。极端情况下，u 只有一个元素，例如n y t 识别出老太 太。p 表示攻击者的先验知识。由于先验知识的不确定与不可知，不在本论文的讨论范 围。所以，隐私攻击的模式可以简化成利用互d 的子集k 。去识别目标用户i d 所归属的身 份集合u 的问题。 1 2 国内外研究现状 l i 等p 1 在w w w 2 0 0 7 国际会议的q u e r yl o ga n a l y s i s 研讨会上对搜索日志的分析应 用以及相关隐私暴露与保护问题作了伞面的介绍，标志着面向搜索日志的隐私保护问 题研究的开端。 x u 等陋1 利用用户的个人文档资料，结合两词项在语料库中的共现( c o e x i s t e n c e ) 率 建立搜索关键词的层次结构( h i e r a r c h y ) ，将搜索关键词自顶向下加入至u h i e r a r c h y 巾 去。这个树型层次结构是以用户为导向的，每一个结点上的搜索关键词含有支持 度( s u p p o r t ) 信息，表示搜索关键词在文档中的出现次数。利用支持度信息建立用 户的个性化搜索引擎，改善用户的搜索质量。随着用户使用个性化搜索引擎的时 间推移，用户搜索的关键词会被不断加入到已经建立的h i e r a r c h y q b 去，h i e r a r c h y 的 信息越加完善。在这个h i e r a r c h y 中的支持度基础上根据信息熵( i n f o r m a t i o ne n t r o p y ) 计算用户的个人信息泄漏程度，设定暴露比率( e x p o s u r er a t i o ) 和信息详细度 ( m i n i m u md e t a i l e d ) ，控制信息暴露程度，以保护用户隐私信息的泄漏。其建立 的典型的h i e r a r c h y 如图1 1 所示。图1 1 展示了不同阀值对h i e r a r c h y 中信息暴露程度的 控制。虚线右下方为受保护区域。x u 等例之后又利用k 匿名的思想，结合基于用户 池( u s e rp 0 0 1 ) 的查询代理模型为用户查询提供面向匿名化的隐私保护。h o n g - 等p 叫也在 搜索日志隐私保护问题上就k 匿名模型作了一定的研究与探讨。 一4 一 网络搜索日志中的隐私度量方法研究 第1 章引言 1 一j m i n i d e t a i l = 0 3 e x p r a t i o = 6 9 图1 - 1h i e r a r c h y q b 的信息暴露受阂值的控制 a d a re 提出两种方法提供搜索日志的隐私保护u 1 1 。其一是直接删除法，自定义一 些敏感的搜索关键词项集合及频数较少的搜索查询直接从搜索日志上删除；其二是借 鉴秘密共享( s e c r e ts h a r i n g ) u 引的方法，将重复出现t 次的查询进行加密，并分割成t 块替 换这条查询的t 个实例，使得原来t 次重叠的查询变成t 条各不相同的查询，并且需要完 整的t 块密文方能还原原始查询。引入跟秘密共享类似的机制，可以将搜索日志原来的 一些统计特性破坏，使攻击者在统计方法方面的攻击能力降低。这两种方法都是以牺 牲可用性作为代价以增强隐私的保护。而秘密共享的方法没有度量标准去衡量一条重 复出现的查询是否有加密的价值，是盲目的加密。其对于要对公共领域发布的搜索日 志，实用价值不大。 p o b l e t eb 等在a o l 搜索日志上利用u r l 作为边定义成g r a p h ，提出基于u r l 的 站点( w e b s i t e ) 方隐私保护问题u 引。具有相同u r l 域的查询作为结点组合成g r a p h 。一 个g r a p h 是属于同一个站点，即需要保护的隐私面向的对象是被用户点击进入的站点， 而非搜索引擎使用者一用户。文章描述在这样的g r a p h 里泄漏了特定站点的一些商业敏 感信息，比如在线购物网站。面对这种隐私问题，作者提出移除边、结点等消除隐私 的基本方法。但是，作者没有给出判定边、结点是否应该被消除的条件。从相反的 个角度，作者在搜索日志当中找到跟以往研究截然不同的隐私泄漏问题。 郑佳谦的硕士学位论文【14 j 涉及用户在w e b 环境中隐私泄漏问题的探讨，并给出有 ，5 一 网络搜索日志中的隐私度量方法研究第1 章引言 效的保护方法。而他所研究的隐私泄漏问题集中在浏览记录而非搜索日志上，并且是 将隐私泄漏情景限定在一定的上下文之中。 z h e n g 等【1 别提出利用r s a 算法对搜索日志进行加密传输达到隐私保护的目的。k u m a r r 将搜索日志作t o k e n - b a s e d ( 基于单个搜索关键词) 的h a s h i n g 后，用搜索日志的统 计分布特征将9 9 的查询匹配回原来的搜索日志当中1 1 6 1 。即使是不可逆的h a s h i n g 保 护方法也存在很大的隐私攻击隐患，r a s 力i 密传输的保护方法也不在话下。v a d r e v u s 等u 7 1 提出利用搜索日志中的地区、位置信息以及一些与位置有隐含关联的关键词建 立面向位置的搜索日志分类器。同时，j o n e sr 等也建立了复杂的人口统计学分类 器1 1 引，对搜索日志的隐私攻击方法进行了扩展。这些研究，使搜索日志隐私保护问题 面临严峻的考验。 在搜索日志的语义分析和分类问题上，b e i t z e ls m 1 1 9 和s h e np 叫均做了有效的研究 工作。b e i t z e ls m 主要将半监督机器学习方法伫1 。2 3 1 应用到搜索日志的分类问题中。此 外，b e i t z e ls m 还建立一种精确的人工标注搜索日志类标签的方法捧刮运用在搜索引擎 实时流分析之上1 2 5 1 。s h e n 等将目前一些出色的分类器及搜索引擎集成，建立了目前已 知的搜索日志分类性能最好的集成算法分类器【2 6 2 7 1 。 d i n u ri 等1 建立了基于统计数据库( s t a t i s t i c a ld a t a b a s e ) 1 2 9 1 的数据可用性及隐 私保护度量模型，并证明达到各种面向统计的隐私保护程度与数据可用性的 权衡( t r a d e o f f ) 代价。d w o r kc 删在此基础上提出差别隐私( d i f f e r e n t i a lp r i v a c y ) 模 型。m i c h a e l aa 等p 1 | ) 及k o r o l o v aa 等m 1 将差别隐私及其扩展应用在搜索日志的统计级 别隐私保护中。 c o o p e ra 对现今搜索日志隐私保护研究的现状作了综述m 。从综述看来，目前 展开的研究中的度量标准都有较大的差别，没有达成一个广泛的共识。对隐私攻击的 设想和假定也各不相同，处于一种百花齐放但是各自为政的状况。文章还从道德、法 律等层面上对搜索日志隐私保护作了一定的探讨。 综上所述，目前展开的研究都有特定的情景或者特定的假设，没有一个统一的标 准来衡量隐私威胁的程度。从文献 1 6 ，1 8 模拟的两次隐私攻击中可知，现今数据挖掘 研究的极大发展，也赋予了用心不良的潜在隐私攻击者强大的力量。隐私保护，特别 是和个人用户日常生活息息相关的搜索日志的隐私保护形势越显严峻。在搜索日志隐 一6 网络搜索日志中的隐私度量方法研究第l 章引言 私保护研究中，国内外学者都趋向达成一个共识性的度量标准来对隐私程度作出衡 量，评价隐私保护算法的好坏，断定经过隐私保护处理的数据( 搜索日志) 在公共领域 发布的安全性。 1 3 论文研究的主要内容及意义 在背景知识一节，我们介绍了对搜索日志进行的一种典型重识别的隐私攻击模 式( 1 1 2 ) 。搜索日志面对的这种威胁是应当得到保护的。但是，在研究相关的隐私 保护方法之前，一个必要前提是要知道哪些查询是否有被用作重识别攻击的潜在威 胁。这种威胁有多大? 怎么去衡量? 本文的研究内容就是针对上述几个问题给出一 个可靠的答案。这需要结合语义和统计对搜索日志的可识别度( i d e n t i f i a b i l l i t y ) 和敏感 度( s e n s i t i v i t y ) 作一个深刻的量化定义，从而理解搜索日志当中存在的隐私威胁程度。 可识别度和敏感度从两个方面刻画了搜索日志的隐私保护问题；前者表示隐私攻击者 对于目标用户搜索日志的攻击能力( 重识别能力) ，而后者是攻击者攻击特定用户的价值 表示。结合两者，方可将搜索日志隐私威胁的程度问题表述完整。 研究的目标： 建立可识别度( h l e n t i f i a b i l i t y ) 、敏感度( s e n s i t i v i t y ) 的度量方法： 以a o l 搜索日志为基础建立的一个基于用户搜索关键词的层次结构，面向搜索日 志隐私分析的本体( o n t o l o g y ) 。 研究的意义： 将我们提出的隐私度量方式帮助搜索引擎公司去描述其搜索日志的潜在隐私风 险，指导其在搜索日志发布前的隐私保护工作； 为搜索日志隐私保护研究社区建立度量方法，并利用产生的隐私保护本体作后续 工作； 实现原型系统，并在线提供服务，让搜索引擎终端用户查询他们自己的搜索关键 词，了解自己的搜索行为的隐私威胁程度。 7 一 网络搜索日志中的隐私度量方法研穿第1 章引言 1 4 章节安排 本论文一共分为5 章。本章介绍阅读本论文需要的背景知识、本领域的研究现状以 及研究的主要内容及其意义；第2 章我们提出关于搜索日志隐私威胁分析的语义模型 和统计模型；第3 章结合语义和统计模型，给出可识别度和敏感度的定义；第4 章将前 两章的模型及在模型之上的整个搜索日志威胁分析框架作原型实现，并利用原型系统 对a o l 搜索日志数据进行隐私威胁度分析；第5 章总结全文，指出研究工作存在的不 足、可能的改进以及后续的工作方向。 一8 一 网络搜索日志中的隐私度量冉浩研究第2 章语义模型与统计模型 第2 章语义模型与统计模型 在介绍语义模型和统计模型之前，先介绍一下整个搜索日志分析框架的架构。 在图2 一l 可以看到，原始的搜索口志经过预处理后需同时经过语义模型和统计模 型的处理，输出搜索日志的语义信息和统计信息。可识别度和敏感度均由这两种信息 计算得出。两个模型是隐私度量方法的基础。论文的研究主要存模型的定义、笈计与 实现上展开。 21 语义模型 = = ：= = j 。：= i 兰三乡 、童j 纠 l ，一j ：二、 r = = ： ，毒7 一 图2 1 搜索日志隐私分析框架架构 作为对于可识别度和敏感度都有贡献的语义模型，需要考虑到如f 两点需求： 在搜索日志的隐私攻击模式中，攻击者凭借已经取得的部分用户搜索日志( 子 集”之匹配( 识别) 用户。决定攻击者的隐私攻击能力的是关于特定用户的搜索日 志子集，当中包含的提示信息的多少。 在衡量用户搜索日志被攻击的价值时，可以归结到搜索日志中所蕴含的信息量多 少及信息的类别。 9 网络搜索日志中的隐私度量a 法研究 第2 章语义模型与统模型 为使语义模型拥有描述搜索日志中信息的类别与量的能力，建立搜索同志语义层 次结构井在其上对搜索日志进行层次递归分类。而并不只是将搜索日志在语义上进行 传统的水平式分类。分类信息对应信息的类别：在层次模型上的层次信息，则可以对 搜索日志信息的量恰当表述。进行多粒度分类，不但能够将搜索日志从类别上表示 不同语义，还可以在层次上表示同类语义的详尽程度。比如说，f o o t b a l l 可以直接 给予s p o r t s 的标签，但足b a l lg a m e s l ：l s p o r t s 更详尽更确切的描述没有被s p o r t s 标签所体 现。语义模型，即语义层次分类模型，在解决搜索日志的语义分类前提下，并对搜索 h 志中袁义的详尽程度量化刻画。 21 1o d p 与多层次分类算法 建立层次语义模型，一般需要借助语义本倒k ( s e m a n t i co n t o l o g y ) 觌。文献吲利用 共现率构造面向单个用户的语义本体。目前，利用概率模型或者其他自动化方法构造 的本体在质最上和领域专家人工精心调配相比的还是有一定差距。本文中的语义层次 模型选择开放目录计划( o p e nd i r e c t o r yp r o j e c to d p ) | 提供的网页目录本体。 盆 恻 吖= = 、 态i ：j 9 龟冬奄 图2 - 2o d p 中深度为l 的1 6 个结点 o p e nd i r e c t o r yp r o j e c t o p e n d i r e c t o r y p r o j e c t 是现存最大的人 川贞目录，同叫是g o o g l e 、a o l 、a l e x a 等 多家搜索引擎公刊的核心嘲页目录数据来源”“。o d p 的根节点是t 0 p 节点，并无实际 语义：而深度为1 的次顶层即很好地概括了互联网站点的分类。图2 2 t = i j o d p 深度 ) 9 1 酗j o d p 节点。搜索日志利用o d p 作为语义层次模型的奉体，正好与搜索互联网 1 0 网络搜索日志中的隐私度量方法研究第2 章语义模型与统计模型 而产生的搜索日志相切合。a d u l t 、a r t s 、b u s s i n e s s 、s p o t s 、“k i da n dt e e n s 是o d p 的1 6 个二级结点。直观地看，这些二级结点能够很好地涵盖用户使用互联网搜 索服务的绝大部分用途。关于o d p 的详细结构与统计信息将在第4 章中介绍与讨论。 o d p 上的递归分类算法 相对于多粒度的层次分类，我们称非层次分类为水平分类。水平分类往往是用 一组层次基本对等的标签对分类目标实例作标注。如o d p 次顶层中的1 6 个结点的值 就是典型的同一层次标签。标签s p o r t s 和h e a l t h 相当，而s p o r t s 下的后代结点，如b a l l g a m e s ( 球类运动) ，则与h e a l t h 相去甚远。 多粒度层次分类的思想是递归地在不同层次作水平分类。递归分类遵守相似度期 望最大化( s i m i l a r i t ye x p e c t a t i o nm a x i m i z a t i o n ) 原则。如图2 - 3 ，在o d p 层次结构中， 当一条搜索日志的词项在本层次的标签中水平分类完毕，选取相似度大的一个标签的 结点作为本层次的分类结果，然后继续在此结点的子结点的层次中重复上述分类操 作，直至相似度不再增加，递归结束。在图2 3 ( b ) 中，假设某条关于新闻的搜索日志， 按层次分类，就会沿图中虚线的路径不断往深层次递归分类。 ( a ) 同一层次的标签 ( b ) 不同层次之间递归分类 图2 - 3o d p 层次结构中的结点与标签 一1 1 网络搜索日志中的隐私度量方法研究第2 章语义模型与统计模型 算法1 基于语义层次结构的递归分类算法 i n p u t ： 搜索日志记录的一个词项，t o d p 语义层次结构，日 o u t p u t ： 对于词项t 在0 d p 语义层次结构日中最相似的结点，m a t c h 1 ：m a t c h ，m a x s i m 最相似结点及其相似度 2 ：c a n d i d a t e4 - - r o o t o f ( h ) i 汉h i e r a r h c yh 的根结点t o p 作默认候选 3 ：s i m o f c a n d i d a t e + - - 0 候选结点的相似度，默认候选结点相似度为o 4 ：d o 5 ： m a x s i m - s i m o f c a n d i d a t e 6 ： m a t c h - - c a n d i d a t e 7 ：f o ry c h i l d c h i l d r e n o f ( m a t c h ) d o 8 ：l i t 与结, 点, , c h i l d 的相似度 9 ： s i m + - - a v e r a g eo fs i m i l a r i t y ( t ，w ) ，v w w o r d s ( c h i l d ) 1 0 ：i fs i m o f c a n d i d a t e m a x s i m 1 6 ：r e t u r nm a t c h 设计递归分类算法的动机源于我们相信一条搜索日志代表着用户的搜索意图。从 图2 3 ( b ) 中的典型的递归分类留下的路径，我们可以认为，在o d p 层次结构上对搜索 日志的递归分类，是对用户当时搜索意图的估计。当每一轮水平分类中，都得到本层 次中最贴近用户搜索意图的一个标签来作描述。而随着递归的次数增加，层次越深， 用以描述的标签表达的语义越确切，语义范围越小。当递归的分类得到的相似度没有 递增( 比最大相似度小) ，相当于过度地将用户搜索意图划分到一个更小的语义范围，而 一】2 一 网络搜索日志中的隐私度量方法研究 第2 章语义模型与统计模型 导致在此层次作水平分类所得的相似度相对上一层次有所降低。因此，算法停止。算 法描述如算法l 所示。 算法中的o d p 语义层次结构定义为： 定义2 1o d p 语义层次结构就是一棵树h ，日上每一个结，点n o d e ，均有表示其 结点语义的词组w _ o r d s ( n 以e ) ，其q w o r d s ( t o p ) 0 。 而其中的s i m i l a r i t y ( w 1 ，w 2 ) 是一个语义相似度函数，s i m i l a r i t yw l ，w 2 ) 0 ，1 】，伽1 ，叫2 表示输入的一对词项，函数返回值代表w 1 ，删2 的语义相似程度。 语义层次结构的递归分类算法主要由两个循环构成。算法的第2 和第3 行代表初始 状态，将o d p 层次结构的根结点作为对目标词项的分类候选结点，对应相似度为0 。 第4 行至第1 5 行是后置条件的外循环，当候选节点相似度比当前最大相似度小时，循环 中止。后置的循环终止条件判定确保此循环至少执行一次。第5 行和第6 行更新当前最 大相似度和对应结点的状态信息。第9 行至第1 4 行的内循环遍历当前候选结点的孩子， 选取相似度最大的孩子作为新的候选结点。第1 6 行返回具有最大相似度的结点，算法 结束。 由于多义词的存在，算法最后返回的结点在全局范围未必是与目标词项最相似的 结点。若考虑全局最相似结点，即会违反层次递归分类的假设前提。y a r o w s k y 3 7 1 认 为在一定的上下文当中，多义词在每次陈述和搭配中只表现出其中一个词义( o n e s e n s e