黃小英

（廣西工商職業(yè)技術(shù)學(xué)院，南寧 530003）

基于LBS(位置服務(wù))的隱私保護(hù)算法研究

黃小英

（廣西工商職業(yè)技術(shù)學(xué)院，南寧 530003）

0 引言

數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布是當(dāng)前數(shù)據(jù)庫應(yīng)用的兩個(gè)重要方面。一方面，數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)在各個(gè)領(lǐng)域都扮演著非常重要的角色。數(shù)據(jù)挖掘的目的在于從大量的數(shù)據(jù)中抽取出潛在的、有價(jià)值的知識(shí)（模型或規(guī)則）。傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)在發(fā)現(xiàn)知識(shí)的同時(shí)，也給數(shù)據(jù)的隱私帶來了威脅。另一方面，數(shù)據(jù)發(fā)布是將數(shù)據(jù)庫中的數(shù)據(jù)直接地展現(xiàn)給用戶。而在各種數(shù)據(jù)發(fā)布應(yīng)用中，如果數(shù)據(jù)發(fā)布者不采取適當(dāng)?shù)臄?shù)據(jù)保護(hù)措施，將可能造成敏感數(shù)據(jù)的泄漏，從而給數(shù)據(jù)所有者帶來危害。所以，如何在各種數(shù)據(jù)庫應(yīng)用中保護(hù)數(shù)據(jù)的隱私，成為近年來學(xué)術(shù)界的研究熱點(diǎn)。

1 隱私保護(hù)技術(shù)的分類與性能評(píng)估

1.1 隱私保護(hù)技術(shù)的分類

沒有任何一種隱私保護(hù)技術(shù)適用于所有應(yīng)用。隱私保護(hù)技術(shù)分為三類：

1）基于數(shù)據(jù)失真（Distorting）的技術(shù)：使敏感數(shù)據(jù)失真但同時(shí)保持某些數(shù)據(jù)或數(shù)據(jù)屬性不變的方法。例如，采用添加噪聲（Adding Noise）、交換（Swapping）等技術(shù)對(duì)原始數(shù)據(jù)進(jìn)行擾動(dòng)處理，但要求保證處理后的數(shù)據(jù)仍然可以保持某些統(tǒng)計(jì)方面的性質(zhì)，以便進(jìn)行數(shù)據(jù)挖掘等操作。

2）基于數(shù)據(jù)加密的技術(shù)：采用加密技術(shù)在數(shù)據(jù)挖掘過程中隱藏敏感數(shù)據(jù)的方法。多用于分布式應(yīng)用環(huán)境中，如安全多方計(jì)算（Secure Multiparty Computation，以下簡稱SMC）。

3）基于限制發(fā)布的技術(shù)：根據(jù)具體情況有條件地發(fā)布數(shù)據(jù)。如：不發(fā)布數(shù)據(jù)的某些域值，數(shù)據(jù)泛化（Generalization）等。

1.2 隱私保護(hù)技術(shù)的性能評(píng)估

隱私保護(hù)技術(shù)需要在保護(hù)隱私的同時(shí)，兼顧對(duì)應(yīng)用的價(jià)值以及計(jì)算開銷。通常從以下三方面對(duì)隱私保護(hù)技術(shù)進(jìn)行度量：

1）隱私保護(hù)度：通常通過發(fā)布數(shù)據(jù)的披露風(fēng)險(xiǎn)來反映，披露風(fēng)險(xiǎn)越小，隱私保護(hù)度越高。

2）數(shù)據(jù)缺損：是對(duì)發(fā)布數(shù)據(jù)質(zhì)量的度量，它反映通過隱私保護(hù)技術(shù)處理后數(shù)據(jù)的信息丟失：數(shù)據(jù)缺損越高，信息丟失越多，數(shù)據(jù)利用率（Utility）越低。具體的度量有：信息缺損（Information Loss）、重構(gòu)數(shù)據(jù)與原始數(shù)據(jù)的相似度等。

3）算法性能：一般利用時(shí)間復(fù)雜度對(duì)算法性能進(jìn)行度量。例如，采用抑制（Suppression）實(shí)現(xiàn)最小化的k-匿名問題已經(jīng)證明是NP-hard問題；時(shí)間復(fù)雜度為O(k)的近似k-匿名算法，顯然優(yōu)于復(fù)雜度為O(klogk)的近似算法。均攤代價(jià)（Amortized Cost）是一種類似于時(shí)間復(fù)雜度的度量，它表示算法在一段時(shí)間內(nèi)平均每次操作所花費(fèi)的時(shí)間代價(jià)。除此之外，在分布式環(huán)境中，通訊開銷（Communication Cost）也常常關(guān)系到算法性能，常作為衡量分布式算法性能的一個(gè)重要指標(biāo)。

2 基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)

數(shù)據(jù)失真技術(shù)通過擾動(dòng)（Perturbation）原始數(shù)據(jù)來實(shí)現(xiàn)隱私保護(hù)。它要使擾動(dòng)后的數(shù)據(jù)同時(shí)滿足：

1）攻擊者不能發(fā)現(xiàn)真實(shí)的原始數(shù)據(jù)，也就是說，攻擊者通過發(fā)布的失真數(shù)據(jù)不能重構(gòu)出真實(shí)的原始數(shù)據(jù)。

2）失真后的數(shù)據(jù)仍然保持某些性質(zhì)不變，即利用失真數(shù)據(jù)得出的某些信息等同于從原始數(shù)據(jù)上得出的信息。這就保證了基于失真數(shù)據(jù)的某些應(yīng)用的可行性。

2.1 隨機(jī)化

數(shù)據(jù)隨機(jī)化即是對(duì)原始數(shù)據(jù)加入隨機(jī)噪聲，然后發(fā)布擾動(dòng)后數(shù)據(jù)的方法。需要注意的是，隨意對(duì)數(shù)據(jù)進(jìn)行隨機(jī)化并不能保證數(shù)據(jù)和隱私的安全，因?yàn)槔酶怕誓Ｐ瓦M(jìn)行分析常常能披露隨機(jī)化過程的眾多性質(zhì)。隨機(jī)化技術(shù)包括兩類：隨機(jī)擾動(dòng)（Random Perturbation）和隨機(jī)化應(yīng)答（Randomized Response）。

2.2 隨機(jī)擾動(dòng)

隨機(jī)擾動(dòng)采用隨機(jī)化過程來修改敏感數(shù)據(jù)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)隱私的保護(hù)。一個(gè)簡單的隨機(jī)擾動(dòng)模型如表1(a)所示。

對(duì)外界而言，只可見擾動(dòng)后的數(shù)據(jù)，從而實(shí)現(xiàn)了對(duì)真實(shí)數(shù)據(jù)值的隱藏。但擾動(dòng)后數(shù)據(jù)仍然保留著原始數(shù)據(jù)分布X的信息，通過對(duì)擾動(dòng)后的數(shù)據(jù)進(jìn)行重構(gòu)如表1(b)所示，可以恢復(fù)原始數(shù)據(jù)分布X的信息。但不能重構(gòu)原始數(shù)據(jù)的精確值x1,x2,…,xn。

表1 隨機(jī)擾動(dòng)與重構(gòu)過程

隨機(jī)擾動(dòng)技術(shù)可以在不暴露原始數(shù)據(jù)的情況下進(jìn)行多種數(shù)據(jù)挖掘操作。由于通過擾動(dòng)數(shù)據(jù)重構(gòu)后的數(shù)據(jù)分布幾乎等同于原始數(shù)據(jù)的分布，因此利用重構(gòu)數(shù)據(jù)的分布進(jìn)行決策樹分類器訓(xùn)練后，得到的決策樹能很好地對(duì)數(shù)據(jù)進(jìn)行分類。在關(guān)聯(lián)規(guī)則挖掘中，通過往原始數(shù)據(jù)注入大量偽項(xiàng)（False Item）來對(duì)頻繁項(xiàng)集進(jìn)行隱藏，再通過在隨機(jī)擾動(dòng)后的數(shù)據(jù)上估計(jì)項(xiàng)集支持度，從而發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。除此之外，隨機(jī)擾動(dòng)技術(shù)還可以應(yīng)用到OLAP上實(shí)現(xiàn)對(duì)隱私的保護(hù)。

2.3 隨機(jī)化應(yīng)答

隨機(jī)化應(yīng)答的基本思想是：數(shù)據(jù)所有者對(duì)原始數(shù)據(jù)擾動(dòng)后發(fā)布，使攻擊者不能以高于預(yù)定閥值的概率得出原始數(shù)據(jù)是否包含某些真實(shí)信息或偽信息。雖然發(fā)布的數(shù)據(jù)不再真實(shí)，但在數(shù)據(jù)量比較大的情況下，統(tǒng)計(jì)信息和匯聚（Aggregate）信息仍然可以較為精確地被估算出。隨機(jī)化應(yīng)答技術(shù)與隨機(jī)擾動(dòng)技術(shù)的不同之處在于敏感數(shù)據(jù)是通過一種應(yīng)答特定問題的方式間接提供給外界的。

隨機(jī)化應(yīng)答模型有兩種：相關(guān)問題模型（Related-Question Model）和非相關(guān)問題模型（Unrelated-Question Model）。相關(guān)問題模型是通過設(shè)計(jì)兩個(gè)關(guān)于敏感數(shù)據(jù)的對(duì)立問題，

3 基于數(shù)據(jù)加密的隱私保護(hù)技術(shù)

在分布式環(huán)境下實(shí)現(xiàn)隱私保護(hù)要解決的首要問題是通訊的安全性，而加密技術(shù)正好滿足了這一需求，因此基于數(shù)據(jù)加密的隱私保護(hù)技術(shù)多用于分布式應(yīng)用中，如分布式數(shù)據(jù)挖掘、分布式安全查詢、幾何計(jì)算、科學(xué)計(jì)算等。在分布式下，具體應(yīng)用通常會(huì)依賴于數(shù)據(jù)的存儲(chǔ)模式和站點(diǎn)（Site）的可信度及其行為。

分布式應(yīng)用采用兩種模式存儲(chǔ)數(shù)據(jù)：垂直劃分（Vertically Partitioned）的數(shù)據(jù)模式和水平劃分（Horizontally Partitioned）的數(shù)據(jù)模式。垂直劃分?jǐn)?shù)據(jù)是指分布式環(huán)境中每個(gè)站點(diǎn)只存儲(chǔ)部分屬性的數(shù)據(jù)，所有站點(diǎn)存儲(chǔ)的數(shù)據(jù)不重復(fù)；水平劃分?jǐn)?shù)據(jù)是將數(shù)據(jù)記錄存儲(chǔ)到分布式環(huán)境中的多個(gè)站點(diǎn)，所有站點(diǎn)存儲(chǔ)的數(shù)據(jù)不重復(fù)。

對(duì)分布式環(huán)境下的站點(diǎn)（參與者），根據(jù)其行為，可分為：準(zhǔn)誠信攻擊者（Semihonest Adversary）和惡意攻擊者（Malicious Adversary）：準(zhǔn)誠信攻擊者是遵守相關(guān)計(jì)算協(xié)議但仍試圖進(jìn)行攻擊的站點(diǎn)；惡意攻擊者是不遵守協(xié)議且試圖披露隱私的站點(diǎn)。一般地，假設(shè)所有站點(diǎn)為準(zhǔn)誠信攻擊者。

3.1 安全多方計(jì)算

眾多分布環(huán)境下基于隱私保護(hù)的數(shù)據(jù)挖掘應(yīng)用都可以抽象為無信任第三方（Trusted Third Party）參與的SMC問題，即怎樣使兩個(gè)或多個(gè)站點(diǎn)通過某種協(xié)議完成計(jì)算后，每一方都只知道自己的輸入數(shù)據(jù)和所有數(shù)據(jù)計(jì)算后的最終結(jié)果。

可以證明，由于采用了可交換加密技術(shù)的順序無關(guān)性，在整個(gè)求集合并集的過程中，除了集合交集的大小和最終結(jié)果被披露外，沒有其它私有信息泄露，所以該計(jì)算集合并的方法是安全的。

由于多數(shù)SMC基于“準(zhǔn)誠信模型”假設(shè)之上，因此應(yīng)用范圍有限。SCAMD（Secure Centralized Analysis of Multi-party Data）協(xié)議在去除該假設(shè)基礎(chǔ)上，引入準(zhǔn)誠信第三方實(shí)現(xiàn)當(dāng)站點(diǎn)都是惡意時(shí)進(jìn)行安全多方計(jì)算；文獻(xiàn)[6]提出拋棄傳統(tǒng)分布式環(huán)境下對(duì)站點(diǎn)行為約束的假設(shè)，轉(zhuǎn)而根據(jù)站點(diǎn)的動(dòng)機(jī)，將站點(diǎn)分為弱惡意攻擊者和強(qiáng)惡意攻擊者，用可交換加密技術(shù)解決在分布環(huán)境下的信息共享問題。

當(dāng)前，關(guān)于SMC的主要研究工作集中于降低計(jì)算開銷、優(yōu)化分布式計(jì)算協(xié)議以及以SMC為工具解決問題等。

3.2 分布式匿名化

匿名化即是隱藏?cái)?shù)據(jù)或數(shù)據(jù)來源。因?yàn)閷?duì)大多數(shù)應(yīng)用而言，首先需要對(duì)原始數(shù)據(jù)進(jìn)行處理以保證敏感信息的安全；然后再在此基礎(chǔ)上，進(jìn)行數(shù)據(jù)挖掘、發(fā)布等操作。分布式下的數(shù)據(jù)匿名化都面臨在通訊時(shí)，如何既保證站點(diǎn)數(shù)據(jù)隱私又能收集到足夠的信息來實(shí)現(xiàn)利用率盡量大的數(shù)據(jù)匿名。

以在垂直劃分的數(shù)據(jù)環(huán)境下實(shí)現(xiàn)兩方的分布式k-匿名為例。兩個(gè)站點(diǎn)S1和S2，它們擁有的數(shù)據(jù)分別為{ID,A11,A12,...,A1n1}，{ID,A21,A22,...,A2n1}。其中Aij為Si擁有數(shù)據(jù)的第j個(gè)屬性。利用可交換加密在通訊過程中隱藏原始信息，再構(gòu)建完整的匿名表判斷是否滿足k-匿名條件來實(shí)現(xiàn)。

4 結(jié)論

隱私保護(hù)技術(shù)在諸多領(lǐng)域都有廣泛的應(yīng)用，是近年來學(xué)術(shù)界新興的研究課題。本文側(cè)重?cái)?shù)據(jù)庫應(yīng)用，對(duì)隱私保護(hù)技術(shù)的研究現(xiàn)狀進(jìn)行綜述。首先給出了隱私及其度量的定義，然后在對(duì)已有的隱私保護(hù)技術(shù)進(jìn)行分類的基礎(chǔ)上，介紹了基于失真、加密和匿名化的三大類隱私保護(hù)技術(shù)，特別是，對(duì)當(dāng)前隱私保護(hù)領(lǐng)域的研究熱點(diǎn)“基于數(shù)據(jù)匿名化的隱私技術(shù)”進(jìn)行了比較詳盡的闡述與分析。

容易看出，每類隱私保護(hù)技術(shù)都有不同的特點(diǎn)，在不同應(yīng)用需求下，它們的適用范圍、性能表現(xiàn)等不盡相同。當(dāng)針對(duì)特定數(shù)據(jù)實(shí)現(xiàn)隱私保護(hù)且對(duì)計(jì)算開銷要求比較高時(shí)，基于數(shù)據(jù)失真的隱私保護(hù)技術(shù)更加適合；當(dāng)更關(guān)注于對(duì)隱私的保護(hù)甚至要求實(shí)現(xiàn)完美保護(hù)時(shí)，則應(yīng)該考慮基于數(shù)據(jù)加密的隱私保護(hù)技術(shù)，但代價(jià)是較高的計(jì)算開銷（在分布式環(huán)境下，還會(huì)增加通訊開銷）。而數(shù)據(jù)匿名化技術(shù)在各方面都比較平衡：能以較低的計(jì)算開銷和信息缺損實(shí)現(xiàn)對(duì)隱私保護(hù)。

[1]J.Han and M.Kamber.Data Mining:Concepts and Techniques.2nd edition,San Francisco:Morgan Kaufmann Publishers,2006.

[2]D.Agrawal and C.C.Aggarwal.On the Design and Quantification of Privacy Preserving Data Mining Algorithms. In Sym.on Principles of Database Systems (PODS),Santa Barbara, California,USA,2001:247-255.

[3]張鵬,童云海,唐世渭,楊冬青,馬秀莉.一種有效的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法[J].軟件學(xué)報(bào),2006,17(8):1764-1774.

[4]羅永龍,黃劉生,荊巍巍,姚亦飛,陳國良.一個(gè)保護(hù)私有信息的布爾關(guān)聯(lián)規(guī)則挖掘算法[J].電子學(xué)報(bào),2005,33(5):900-903.

The privacy preservation study based on LBS

HUANG Xiao-ying

隨著數(shù)據(jù)挖掘和數(shù)據(jù)發(fā)布等數(shù)據(jù)庫應(yīng)用的出現(xiàn)與發(fā)展，如何保護(hù)隱私數(shù)據(jù)和防止敏感信息泄露成為當(dāng)前面臨的重大挑戰(zhàn)。隱私保護(hù)技術(shù)需要在保護(hù)數(shù)據(jù)隱私的同時(shí)不影響數(shù)據(jù)應(yīng)用。根據(jù)采用技術(shù)的不同，出現(xiàn)了數(shù)據(jù)失真、數(shù)據(jù)加密、限制發(fā)布等隱私保護(hù)技術(shù)。

隱私保護(hù)；隨機(jī)化；安全計(jì)算

黃小英（1976 -），女，廣西寧明人，講師，工程碩士，研究方向?yàn)橛?jì)算機(jī)應(yīng)用。

TP312

A

1009-0134(2011)5(上)-0096-03

10.3969/j.issn.1009-0134.2011.5(上).33

2011-01-05