保護隱私的（Ｌ，Ｋ）匿名

摘要:提出了一種在K－匿名之上的(L，K)－匿名方法，用于對K－匿名后的數據進行保護，并給出了(L，K)－匿名算法。實驗顯示該方法能有效地消除K－匿名后秘密屬性信息的泄漏，增強了數據發布的安全性。

關鍵詞:數據發布; 隱私; K－匿名; 信息泄漏; (L，K)－匿名

中圖分類號:TP311文獻標志碼:A

文章編號:1001－3695(2008)02－0526－03

研究表明，接近87%的美國人口可以通過郵編#65380;性別和出生日期的鏈接來確定個體身份。這種在數據發布中通過屬性鏈接，推理出個體隱私信息的方法，稱為鏈接攻擊。目前，為了避免類似這樣的鏈接攻擊，保護私有信息不被泄漏，主要采用K－匿名[1]方法，對準標志符進行泛化和隱匿。準標志符就是用來標志個體信息的一組屬性集。K－匿名就是對一個發布表中一條記錄r，保證至少有K-1條記錄與r在準標志符上的投影值相等，這樣該組記錄上的個體身份將不能惟一確定。例如，表1是一張預發布的信息表，經過2－匿名后得到表2。從表2中可以看出元組t1{data，job，zip }={*，teacher，53175}=t2{data，job，zip}，同理有t3=t4，t5=t6，這樣表2中的個體信息不能惟一確定。但是如果元組t1和元組t2職業是一個重要人物，那么他的秘密屬性(salary)的信息就被泄漏了。以前對K－匿名的研究只對標志個體身份的屬性進行泛化和隱匿，沒有考慮匿名后秘密屬性信息由于缺乏多樣性而導致的信息泄漏。本文在研究K－匿名的基礎上考慮身份信息泄漏的同時還考慮匿名后敏感信息的泄漏情況，針對這個問題進行研究，提出了(L，K)－匿名的模型，并給出了相應的算法。

1相關工作

數據發布問題的研究重點在于身份認證和保護隱私信息。保護隱私信息的主要方法有添加噪聲#65380;數據交換和數據隱匿[2]。這些方法理論上可以在一定程度上保證隱私信息的泄露，但是在實際應用中往往出現可以發布的數據已經失真或者不存在的情況。

1998年L.Sweeney提出了一種用來保護隱私信息的K－匿名模型。由于K－匿名技術能夠簡單有效地對發布的隱私數據進行保護，近年來得到了廣泛關注。文獻[3]證明，獲得最佳的K－匿名數據是NP－完全問題。現在有許多用泛化和隱匿技術來實現K－匿名的算法，主要可以分為:全域泛化[4，5]和局部泛化[6，7]兩類。這些方法都是研究如何實現K－匿名技術，沒有考慮K－匿名后存在的信息泄漏的處理。

文獻[8]對K－匿名后的數據進行研究，其主要思想是基于背景知識來分析匿名后的信息泄漏，但是背景知識對不同用戶來說是很難確定的，根據不同用戶的情況需要泛化的數據量也不同。因此，為了防止基于背景知識的攻擊，可以采用其他有效的方法，而不是采用K－匿名技術。本文通過分析K－匿名后每組數據的不同值的個數與K值之間的關系，提出(L，K)－匿名模型來保護匿名后的秘密屬性泄漏。

2(L，K)－匿名模型

2.1(L，K)－匿名模型

定義1準標志符QI。數據持有者能夠識別出的可以與外部信息相連接的隱私信息的全部關鍵屬性集，稱為準標志符。

定義2K－匿名。T(A1，A2，A3，…，An)是一個表，QIT是與T相關聯的準標志符，當且僅當在T[QIT]中出現的每一個有序的值至少要在T[QIT]中出現K(K≥2)次，就說T滿足K－匿名。

定義3(L，K)－匿名。給定一個表T，如果T滿足K－匿名的要求，并且在準標志符QI上的值相同的一組記錄中，敏感屬性不同值至少有L個，T滿足(L，K)－匿名。其中:K≥2;1

實例說明(L，K)－匿名。表2是經過2－匿名的信息表，元組t1和元組t2在準標志符QI={data，job，zip}上有相同的映射值。t1[QI]={1976，teacher，53175}=t2[QI]，但是在屬性salary上t1[salary]=t2[salary]={5000}，那么該屬性值只出現一次，即L=1，這樣該組的收入信息就被泄漏。對于元組t3和元組t4而言，t3[salary]={8000}，t4[salary]={7000}，那么L=2，這組數據的信息不能被惟一確定。表2的元組可以分為三組，由于單組最小不同值的個數是1，該表是不符合(L，K)－匿名定義的。下面通過介紹泛化和隱匿技術來說明如何獲得滿足(L，K)－匿名的表。

2.2泛化和隱匿

(L，K)－匿名的過程是對需要保密的數據進行泛化和隱匿的過程。通過泛化和隱匿得到一個可以發布沒有信息泄漏的表。隱匿就是去除單元值或一個元組的所有值。屬性泛化的思想就是一個值被一個更不確切的值所替換，這個值比原來的值更一般。例如，表1中原來的屬性data{1976，1965}被泛化成表2的data{19**}，泛化后的數字在語義上表示更大的時間區域。如果經過一次泛化后還不能滿足匿名要求，那么就需要對該屬性連續泛化，直到滿足匿名要求為止。分別對不同的屬性進行不同層次泛化得到的結果構成一個泛化格。如果表1的準標志符為{data，zip}，那么對表1準標志符屬性域和屬性值的連續泛化以及構成的泛化格如圖1所示。

如果表1的秘密屬性為S={salary}，L=2，K=2，可以通過自頂向下的方法對泛化格中的節點進行搜索。其中，每個泛化格的節點都代表一個泛化后的數據表，這樣筆者可以從這些節點中找到符合(2，2)－匿名的表。泛化格中圓括號表示該節點泛化后不滿足(L，K)－匿名的元組個數。

數據經過泛化后就會出現一定程度的失真，泛化程度越高，數據失真度就越大。本文發布的數據常常是用來分析或者研究某些問題，因此在發布數據的時候不僅要保護隱私的泄漏，還要保證發布的數據有較小的損失。本文采用文獻[6]中精確度Prec的計算方法來計算數據失真。

3算法

本章給出(L，K)－匿名的算法。本文的研究重點是(L，K)－匿名，對于實現K－匿名的方法另文討論。本文在泛化格上自頂向下逐層計算每個節點滿足(L，K)－匿名的元組數量，哪一層出現不滿足(L，K)－匿名的節點時，在計算完該層所有節點后，找出該層具有最高精確度且滿足(L，K)－匿名的節點，那么該節點處的泛化表就是要發布的信息表。

輸入:初始表IT;準標志符QI;屬性泛化格GL;L和K的值

輸出:(L，K)－匿名表LKT

步驟:

a)讀入初始表IT和準標志符QI，泛化格GL。

b)對于泛化格頂層開始向下的每層節點，循環執行以下操作，即對于同層節點分別做下面的操作:

(a)找到節點對應的泛化表GM;

(b)計算表GM中在準標志符上投影值相同的元組個數Ki和對應的秘密屬性的不同值的個數Li;

(c)判斷2≤min Ki

(d)該層有標記則計算候選集中節點的精確度Prec，取精確度最大節點的表GM即LKT。

c)輸出表LKT。

4實驗

筆者在一個數據集上對本文提出的算法進行了測試，結果發現(L，K)－匿名方法能有效地消除K－匿名后的秘密屬性的信息泄漏。

4.1實驗設置

1)數據集實驗使用具有六個屬性的表。表3給出數據集中屬性#65380;屬性類型#65380;泛化層次以及出現不同值的個數。選取前五個作為準標志符，最后一個作為秘密屬性。數據由一個隨機函數產生，大小從0變化到5 000。

2)軟硬件環境硬件環境:Interl Pentium4 CPU#65380;512 MB SDRAM內存;操作系統:Microsoft Windows XP;編程環境:Microsoft Visual C++編譯器。

4.2(L，K)－匿名的精確度分析

在數據集中分別取500~5 000個記錄作為本文初始表。選擇K=2和K=3時，應用K－匿名算法來得到泛化后的表，然后用(L，K)－匿名算法檢測K－匿名后的表的泄漏情況。表4給出了秘密屬性泄漏的情況。從表4可以看出K－匿名會出現屬性泄漏，而且當記錄數和K值增加的時泄漏信息會越來越嚴重，所以非常有必要對秘密屬性進行K－匿名。應用(L，K)－匿名算法分別獲得符合(2，2)－匿名和(3，3)－匿名的表LKT。圖2給出了(L，K)－匿名的數據精確度隨記錄數變化情況。從圖2可以看出，當給定L和K值時，精確度隨記錄數的增加而增加;K值越大泛化的層次相應增加，數據精確度降低;L值越大對秘密屬性不同值要求越高，泛化的層次也相應增加，數據損失加大，精確度降低。

4.3(L，K)－匿名執行時間分析

圖3給出了算法的執行時間隨記錄數變化的曲線。從圖3可以看出，當記錄數增加時，執行時間隨之增大。記錄數目增加后，(L，K)－匿名需要更多的時間泛化和搜索符合定義的記錄，因此必然會出現時間增長的情況，而且隨著K和L值增大，相應的執行時間也越長。

5結束語

隱私泄漏隨著網絡技術的發展越來越受到人們的關注。本文針對K－匿名后的分組數據缺乏多樣性而導致的信息泄漏提出(L，K)－匿名模型，給出相應的算法，并通過實驗證明(L，K)－匿名能有效地消除K－匿名后的信息泄漏。該模型必將為防止隱私泄漏提供更有效的技術保護。

參考文獻:

[1]SWEENEY L. K－anonymity: a model for protecting privacy[J].Int’1 Journal on Uncertainty， Fuzziness and Knowledge－based System， 2002，10(5):557－570.

[2]ADAM N R， WORTMAN J C. Security－control methods for statistical databases[J]. ACM Computing Surveys，1989，21(4):515－556.

[3]MEYERSON A，WILLIAMS R. On the complexity of optimal K－anonymity[C]//Proc of the 23rd ACM SIGACT－SIGMOD－SIGART Symposium on Principles of Database Systems. New York:[s.n.]，2004:223－228.

[4]SWEENEY L. Achieving K－anonymity privacy protection using genera－lization and suppression[J].Int’l Journal on Uncertainty， Fuzz－iness and Knowledge－based Systems，2002，10(5):571－588.

[5]LeFEVRE K，DeWITT D，RAMAKRISHNAN R. Incognito:efficient full domain K－anonymity[C]//Proc of SIGMOD.2005.

[6]FUNG B C M， WANG K， YU P S. Top－down specialization for information and privacy preservation [C]//Proc of ICDE.2005:205－216.

[7]AGGARWAL G ， FEDER T， KENTHAPADI K.Anonymizing tables[C]//Proc of ICDT.2005:246258.

[8]MACHANAVAJJHALA A，GEHRKE J，KIFER D. l－diversity:privacy beyond K－anonymity[EB/OL].[2005].http://www.cs.cornell.edu/_mvnak.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”