一種用戶連續(xù)查詢中隱私風險評估的方法

馬永東 王文濤 王銀款

摘 要：用戶在線查詢服務中的隱私風險評估與隱私保護有著等同的重要性。關于用戶查詢隱私保護的研究引起了廣泛關注，而對于用戶查詢隱私風險評估的研究較少。其中，連續(xù)查詢作為查詢一種重要表現，合理地對用戶連續(xù)查詢進行隱私風險評估，能夠有效抵抗用戶查詢中隱私泄露。因此，本文基于隱馬爾可夫模型（Hidden Markov Model，HMM）首次提出了一種能夠動態(tài)評估用戶連續(xù)查詢隱私風險的方法，通過分析用戶連續(xù)查詢時存在的重要特征，以概率的方式評估用戶每次查詢時的隱私風險大小。最后，為了驗證該方法的有效性，采用美國在線（AOL）真實的用戶查詢日志數據進行分析和證明，實驗結果表明該方法具有較高的風險評估準確率，同時評估時間符合實際的用戶查詢需求。

關鍵詞： 用戶連續(xù)查詢;查詢隱私風險;HMM模型;動態(tài)評估文章編號： 2095-2163（2019）03-0049-05?中圖分類號： TP309?文獻標志碼： A

0?引?言

近年來，在線查詢極大提高工作及學習效率，但也隨之帶來了各種隱私泄露問題[1-4]。面對這一狀況，國內外眾多學者提出了不同的解決方法，如匿名查詢[3]、覆蓋查詢[4]、安全通信[5]、數據混淆[6]等。以上方法在一定程度上實現了隱私保護，但對隱私保護成本以及隱私保護合理性卻未能給予適當關注。其主要原因是用戶的每次查詢中隱私風險是不同的。特別是在用戶連續(xù)查詢的場景下，如在查詢一個復雜的醫(yī)學問題時，需要用戶多次查詢或進行更長時間的查詢。若采用現有的查詢隱私保護方法，很容易造成隱私保護強度過高，如文獻[7]中假設用戶的每次查詢都是高風險查詢，對用戶的每次查詢采用相同的隱私保護方法進行保護，但這卻會影響用戶實際的查詢精確度和查詢時間效率。而查詢風險評估與隱私保護是同等重要的[8]，目前僅有部分工作考慮了對用戶查詢時隱私泄露的風險評估[9-10]。

針對上述問題，本文結合實際查詢場景，通過對用戶在連續(xù)查詢時存在的兩大重要特性，即：遞進關系（Progressive Relationship， PR）和共現關系（Co-occurrence Relationship， CR）進行分析。其中，PR是指用戶對當前的查詢結果不滿意時，將另外補充新詞來縮小查詢范圍，進行再次查詢。CR是指當用戶的2個或2個以上的查詢頻繁在同一個Session中共現時，則可以認為此時的查詢之間存在共現關系，且該查詢間有著緊密的相關關系。采用HMM建立用戶查詢動態(tài)風險評估方案，對用戶的每次查詢進行風險大小評估，就可以根據用戶查詢風險進行合理的隱私保護，實現隱私保護的同時，在很大程度上也節(jié)省了隱私保護成本。

1?相關工作

本節(jié)主要對現有用戶查詢隱私保護技術和查詢風險評估兩個方面給出優(yōu)缺點分析。對此可做研究闡述如下。

在查詢隱私保護技術中，Roger[5]提出了一種在查詢時隱藏用戶身份與第三方監(jiān)控的方法。文獻[11-12]在此基礎上提出了協作方案，以便讓每個用戶提交由其他用戶生成的查詢，使得用戶隱藏在各自的用戶組內。然而，該解決方案的響應時間比較慢，嚴重依賴后端系統(tǒng)的可用性，因此該方法無法得到廣泛的應用。Balsa等人[13]提出了一種混淆的私有Web搜索（OB-PWS）方案，通過將生成的虛擬查詢和用戶的真實查詢一同發(fā)送到搜索引擎，以防止對搜索概要文件的準確推斷，并提供查詢可拒絕性。Howe等人[14]提出了一種隨機發(fā)布虛擬查詢方法，在程序生成的誘餌流中混淆用戶的查詢來實現Web搜索中的隱私保護方法。Domingo等人[12]提出并驗證了一套保證用戶查詢隱私的方法和協議。但是以上方法在查詢效率方面無法滿足用戶需求。此外，Arampatzis等人[15]還提出一種使用模糊或混亂的查詢來替換私有用戶查詢，從而近似于目標搜索結果。接下來，經過排序的查詢結果用于覆蓋私有用戶感興趣的內容。但只能落入預定義字典的查詢中，極大地限制了用戶靈活性。后續(xù)工作中進一步考慮了生成的查詢與真實查詢之間的語義相關性[16]，注入與原始查詢術語具有相似特異性的誘餌術語[17]來維護用戶查詢的匿名性和通用性。以上方法中均沒有解決用戶每次查詢時的風險高低的問題。

查詢風險評估與隱私保護起著同等重要的作用[17]。然而，只有有限的工作考慮了對用戶查詢時隱私泄露的風險評估。Peddinti等人[9]基于機器學習分類器對TMN（TrackMeNot）提供的隱私保障進行了評估。Gervais等人[10]通過機器學習算法學習用戶的原始查詢和假查詢之間的可鏈接性，對TMN和假查詢生成等查詢混淆技術進行了評價。Howe等人[14]通過對現有6種混淆技術的隱私特性進行定性分析，卻沒有對這些技術做出定量的分析和比較。Chow等人[18]提出了2個可以用來區(qū)分TMN虛擬查詢和實際用戶查詢的方法。然而，現有研究很少對用戶在線查詢進行動態(tài)隱私泄露風險評估，但是這對隱私保護卻至關重要。因此，本文針對用戶連續(xù)查詢提出一種動態(tài)風險評估的方法，為用戶查詢隱私保護提供一個較好的解決思路。

2?基于動態(tài)風險評估模型

2.1?預備知識

隱馬爾可夫模型（Hidden Markov Model，HMM）是一種統(tǒng)計模型，用來描述一個含有隱含未知參數的馬爾可夫過程，已廣泛應用于模式識別、詞性標注和信息提取方面[19]。

HMM是根據可觀察的參數確定該過程的隱含參數，繼而利用這些參數展開后續(xù)分析。在HMM中，輸出狀態(tài)并不是直接可見的，每一個狀態(tài)在可能輸出的符號上都有一概率分布。因此輸出符號的序列能夠透露出狀態(tài)序列的一些信息。為更清晰描述整個HMM過程，設用戶查詢序列為X=x1，x2，…，xn，其中xi代表每一個節(jié)點，且每個節(jié)點xi都存在著一個轉移概率P，那么，在一個隱馬爾可夫模型M上，一個查詢序列X被觀測的概率為在所有可能路徑上的概率之和。這里可將其寫作如下數學形式：

2.2?參數確定

在建立HMM模型時，結合用戶的PR和CR查詢特征，從轉移概率和觀測概率角度進行分析。研究可得闡釋分述如下。

（1）轉移概率。是指用戶給出先前查詢數據序列后，再經過若干時間后得到用戶的另一查詢數據的條件概率。如相連的兩節(jié)點q1，q2之間存在著一個轉移概率Pq1→q2，由于用戶在連續(xù)查詢場景下，用戶查詢數據可區(qū)分的風險取決于用戶之前的查詢數據，如果考慮同一主題中的先前數據，則該數據的信息增益會變高。設Xt為HMM中個人可識別敏感信息或者是敏感主題，則Xt節(jié)點之間的轉移概率為pXt|Xt-1，可以對節(jié)點之間已發(fā)生的轉換次數進行加權計算，研究可推得其數學公式如下：

（2）觀測概率。是指某個節(jié)點可能發(fā)生的查詢行為，如用戶ui經過q查詢了e的概率為Pe|q。該值基于用戶的歷史查詢數據進行分析和計算獲得，每個節(jié)點包含一組具有觀測概率的觀測值，將這些觀測概率建模為不同用戶在先前數據pui|Xt中找到的給定數據Xt的概率。用戶查詢特定主題的數據越多，則對用戶興趣數據的推斷精確度越高，該查詢風險也越高。同理，采用加權計數的方式確定查詢風險，研究可推得其數學公式如下：

2.3?查詢動態(tài)風險評估

在用戶連續(xù)查詢場景中，假設用戶當前的查詢?yōu)閄T，只與前一查詢XT-1相關。例如用戶在查詢一個復雜問題（醫(yī)學知識等）時，當前的查詢結果不滿足用戶的查詢需求時，用戶會添加或刪除前一次的查詢內容，而修改后的查詢與修改前的查詢之間有密切的聯系，所以是滿足一階馬爾可夫性質。

已知用戶查詢時的轉移概率和觀察概率，通過多屬性效用理論對用戶的查詢進行風險等級劃分，本文將用戶的查詢風險一共劃分為5個等級。等級越高則查詢風險越高，在隱私保護時需要增加隱私保護強度;查詢風險等級越低，則用戶查詢內容中涉及的用戶隱私較少，因此，在隱私保護時無需采用高強度的隱私保護方法。本文的查詢風險等級劃分符合“GB/T 33132-2016信息安全技術、信息安全風險處理實施指南”和“GB/T 31722-2015信息技術、安全技術、信息安全風險管理”的需求[20]。在本文研究中設定的查詢風險等級見表1。

表1中不同的風險等級所代表的隱私風險高低是不同的。當用戶查詢中沒有包含新的查詢時，HMM模型會根據用戶歷史查詢對用戶進行風險評估。一旦出現新的查詢時，首先會進行模型訓練，然后對用戶查詢進行評估。且本文中的風險評估是動態(tài)的，會隨著時間的推移和用戶的查詢數據的積累，HMM模型對用戶查詢隱私風險評估也在動態(tài)地變動與調整。

3?實驗分析與評估

本文的實驗分析環(huán)境為Intel（R） Core（TM） i5-3337U CPU @ 1.80 GHz， RAM為8 G，系統(tǒng)類型為Windows10，所有的算法和仿真實驗均通過python而得到設計完成。

3.1?數據預處理

研究采用的實驗數據為2006年AOL公布了3個月的用戶真實查詢日志，提供了超過65萬用戶的2 000萬個用戶搜索查詢。每一條AOL查詢日志數據由5部分組成，分別是：用戶ID、查詢字符串、查詢時間、查詢內容的排名以及查詢內容的URL。實驗數據集明細詳見表2。

在實驗評估前，首先對AOL數據集進行預處理，對無效查詢、空查詢等施以過濾處理。然后將清洗后的數據集按80%，20%比例進行劃分，其中80%用于模型訓練，20%用于結果測試。此外，為了提高模型訓練效率，采用了k均值聚類方法將訓練數據分割成k個聚類，使用并行處理技術同時訓練k個數據集，這樣極大地提高了數據訓練效率。

在高風險查詢評估中，本文設定癌癥、懷孕和酒精三個主題作為高風險查詢主題。為了提取包含以上3個主題的查詢，使用了自然語言處理包NLTK[21]和Gensim[22]進行主題建模和提取相關查詢主題，對每個高風險主題識別一些同義單詞。本文使用了WordStream提供的免費關鍵字工具，該工具利用最新的Google關鍵字API尋獲了數百個相關的關鍵字結果[23]。然后對這些關鍵詞進行主題建模，得到與主題相關的關鍵詞。如對“癌癥”敏感主題、應用主題建模后可得相關度高的單詞為腫瘤、乳腺癌、甲狀腺、白血病、胰腺等。

3.2?實驗評估

3.2.1?查詢風險分析

在數據預處理部分，本文從AOL數據中提取了“癌癥、懷孕和酒精”作為高風險查詢內容進行研究。如圖1所示。圖1中，preg表示用戶查詢中包含“懷孕”的信息，隨著查詢次數的增多，其隱私風險也在增加。cancer表示用戶查詢中包含“癌癥”的信息，而且隨著用戶查詢次數的增多，其隱私風險也在增加。同理，alcohol也是如此。

從圖1可得，3個敏感主題均是隨著查詢次數的增多，查詢隱私風險在逐步上升。結合表1中等級劃分，當用戶查詢超過50次左右時，用戶的查詢風險等級為2級，表明實驗結果符合風險等級的設定。

3.2.2?時間開銷

時間開銷主要是指當用戶進行查詢時，對用戶的查詢進行風險評估所花費的時間開銷。

如圖2所示，用戶查詢中80%的查詢時間開銷低于0.5 s，可得本文的評估時間在用戶實際查詢場景中是允許的。但在用戶最初的查詢中，查詢時間偏高，其主要原因是剛開始需要模型訓練，因此初始查詢時間花費較多，隨著用戶查詢次數的增多，用戶的查詢時間也會隨之穩(wěn)定、且時間逐漸變小。但是仍有一些查詢時間高于0.5 s，當用戶查詢中出現新的查詢時，HMM模型需要對數據重新訓練，故而所需時間要長于一般查詢時間，但整體查詢時間是可以接受的。

最后，研究得到不同用戶查詢風險變化趨勢如圖3所示。隨著有效查詢時間的增長，不同用戶每次查詢隱私風險不同。這是由于用戶的查詢內容不同，所包含的隱私信息是不同的，因此，用戶查詢風險也在動態(tài)變化。

4?結束語

用戶查詢風險評估對用戶查詢隱私保護起到非常重要的作用。本文提出了一種可以動態(tài)評估用戶查詢隱私風險的方法，對區(qū)分內容隱私風險高低具有良好的借鑒價值。最后從時間開銷、風險大小和動態(tài)評估效果三個方面進行了仿真實驗驗證，實驗結果表明，本文方案是高效、且可行的。未來研究將對該評估方法與隱私保護算法相結合，提出一種基于動態(tài)評估用戶查詢風險的隱私保護方案，為用戶查詢隱私保護提供一種有益的解決思路和方法。

參考文獻

[1]CHAIRUNNANDA P ， PHAM N ， HENGARTNER U . Privacy： Gone with the typing！ Identifying Web users by their typing patterns[C]// 2011 IEEE Third International Conference on Privacy， Security， Risk and Trust （PASSAT） and 2011 IEEE Third International Confernece on Social Computing （SocialCom）. Boston， MA， USA： IEEE， 2011：974-980.

[2]?HANSELL S. AOL removes search data on vast group of Web users[N]. The New York Times，2006-08-08（ C4）.

[3]?SU J ， SHUKLA A ， GOEL S， et al. De-anonymizing Web browsing data with social networks[C]// Proceedings of the 26th International Conference on World Wide Web.Perth， Australia： ACM， 2017：1261-1269.

[4]?TOCH E， WANG Yang， CRANOR L F. Personalization and privacy： A survey of privacy risks and remedies in personalization-based systems[J]. User Modeling and User-Adapted Interaction， 2012，22（1-2）：203-220.

[5]?ROGER D. Tor and circumvention： Lessons learned[C]//Advances in Cryptology-CRYPTO 2011. Berlin/Heidelberg：Springer，2011： 485-486.

[6]?TEJA S， SAXENA N. On the effectiveness of anonymizing networks for Web search privacy[C]//Proceedings of the 6th ?ACM Symposium on Information， Computer and Communications Security， ASIACCS 2011. Hong Kong， China：ACM， 2011：483-489.

[7]?AHMAD W U， CHANG Kaiwei， WANG Hongning. Intent-aware query obfuscation for privacy protection in personalized Web search[C]//The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. Ann Arbor， MI， USA：ACM， 2018：285-294.

[8]?AHMAD W U ， RAHMAN M M ， WANG Hongning. Topic model based privacy protection in personalized Web search[C]// Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval. Pisa，Italy：ACM， 2016：1025-1028.

[9]?PEDDINTI S T， SAXENA N. On the privacy of Web search based on query obfuscation： A case study of trackmenot[M]//ATALLAH M J， HOPPER N J. Privacy Enhancing Technologies. PETS 2010. Lecture Notes in Computer Science. Berlin/Heidelberg：Springer，2010，6205： 19-37.

[10]GERVAIS A， SHOKRI R， SINGLA A， et al. Quantifying Web-search privacy[C]// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security （CCS '14）. Scottsdale， Arizona， USA：ACM， 2014： 966-977.

[11]CASTELL-ROCA J， VIEJO A， HERRERA-JOANCOMART J. Preserving users privacy in Web search engines[J]. Computer Communications， 2009，32 （13-14）： 1541-1551.

[12]DOMINGO-FERRER J ， BRAS-AMORS M， WU Qianhong， et al. User-private information retrieval based on a peer-to-peer community[J]. Data & Knowledge Engineering， 2009， 68（11）：1237-1252.

[13]BALSA E， TRONCOSO C， DIAZ C. OB-PWS： Obfuscation-based private Web search[C]//2012 IEEE Symposium on Security and Privacy （SP）. San Francisco， CA， USA：IEEE，2012： 491-505.

[14]HOWE D C， NISSENBAUM H. TrackMeNot： Resisting surveillance in Web search[C]//Lessons from the Identity Trail： Anonymity， Privacy， and Identity in a Networked Society. Oxford： Oxford University Press， 2009： 417-436.

[15]ARAMPATZIS A ， DROSATOS G ， EFRAIMIDIS P. Versatile query scrambling for private Web search[J]. Information Retrieval， 2015， 18（4）：331-358.

[16]?SNCHEZ D， CASTELL-ROCA J， VIEJ O A. Knowledge-based scheme to create privacy-preserving but semantically-related queries for Web search engines[J]. Information Sciences， 2013， 218： 17-30.

[17]PANG ?H H， DING Xuhua， XIAO Xiaokui. Embellishing text search queries to protect user privacy[J]. Proceedings of the VLDB Endowment ，2010，3（1）：598-607.

[18]CHOW R， GOLLE P. Faking contextual data for fun， profit， and privacy[C]// Proceedings of the 2009 ACM Workshop on Privacy in the Electronic Society， WPES 2009. Chicago， Illinois， USA：ACM， 2009： 105-108.

[19]RABINER L， JUANG B. An introduction to hidden Markov models[J]. ?IEEE ASSP Magazine， 1986，3（1）：4-16.

[20]國家市場監(jiān)督管理總局國家標準技術審評中心 . 全國標準信息公共服務平臺[EB/OL].http：//www.std.gov.cn/gb/gbQuery.

[21]NLTK project. NLTK 3.4 documentation [EB/OL]. [2018-11-17].http：//www.nltk.org/.

[22]gensim[EB/OL]. [2019-01-31]. ?https：//radimrehurek.com/gensim/.

[23]Bryant B D， Miikkulainen R. From word stream to gestalt： A direct semantic parse for complex sentences [R]. Austin， TX： University of Texas， 2001.