基于部分重編碼的流數據發布隱私保護算法

趙素蕊, 高雙喜

(1. 河北經貿大學 計算機中心, 石家莊 050061; 2. 河北經貿大學 信息技術學院, 石家莊 050061)

在實際應用中, 數據多是持續變化的, 而不是靜態的, 這些數據稱為流數據[1]. 流數據會隨時間不斷變化, 如社交平臺的親友數據內容、 醫院的診療記錄、 企業產品的售賣信息等[2]. 在將上述流數據信息對外發布時, 必須保護數據隱私. 動態數據具有變化無常、 流動極快、 潛在無限等顯著特征, 相比靜態數據, 流數據在空間、 時間兩維度上, 因此保護數據隱私難度較大[3-6]. Li等[7]提出了以擾動為基礎的數據匿名算法, 即將任意噪聲數據融入原始數據中, 原始數據被擾動后, 攻擊者很難再從中獲得原始數據所涵蓋的信息; 文獻[8]提出了CASTLE算法, 把數據流匿名化等同于一個連續聚類操作, 假設在一個時延閾值內元組沒有到達, 則其發布形式將表現為連續; 文獻[9]對CASTLE算法進行改進, 提出了B-CASTLE算法, 其存在產生不平衡簇的問題, 可利用對簇大小的最大限制進行定義來解決； 文獻[10]提出的FAANST算法為了達到運算速度提升的目的, 只對唯一的k匿名簇集進行維護, 完成元組的批量發布. 在抵御相似性攻擊方面, 已有許多優秀的隱私保護算法應用于靜態數據的相似性攻擊隱私保護方面[11]. 但在應用中, 由于數據生成的形式具有多樣化的特點, 數據在不斷變化, 因此許多隱私保護算法不再適用[12-13]. 如客戶在金融機構進行相關交易時, 其對應的金融數據將會實時更新, 即流數據; 用戶進行Web訪問時, 新用戶的訪問請求會生成新的訪問數據信息, 并保存下來.

本文提出一種新的流數據發布隱私保護算法, 結合流數據的動態特征, 在某有限窗口中緩沖上述流數據, 結合數據各動態階段對敏感屬性分級的定義, 設計一種可用于流數據狀態的隱私保護模型, 在一定程度上弱化相似性攻擊對流數據的干擾. 數據發布模型的構建選擇自頂向下的局部編碼窗口算法, 使算法的執行效率大幅度提升, 可最大限度地規避流數據的相似性漏洞.

1 流數據的隱私維護模型

本文提出的流數據發布隱私保護算法基于經典的隱私保護算法, 并將其應用在流數據的發布上. 流數據通常是逐步變更的數據, 伴隨著時限的轉變, 流數據被認為是無限的值. 為了對流數據進行有效建模, 本文把流數據控制在一類區域內進行研究, 將該類區域稱為窗口.

定義1((w,γ,k)-窗口) 假設Tin表示輸入信息, 源于Tin的輸出信息一般標記為Tout.Tin主要緩存于大小為|W|>的窗口中,Tout一般被視為(w,γ,k)-窗口, 僅當其同時滿足以下兩類要求：

1) 針對每條信息r∈Tin,Tout中出現一種等價類型, 包括r匿名化的數據信息；

2) 針對各種等價類型E∈Tout,Tin中出現一類窗口W, 基本滿足E由W中的信息匿名化后產生, 且W中的數據信息符合(w,γ,k)-匿名要求.

假設窗口由j類大小一致的格子構成, 其中j表示一類正整數. 若F表示窗口中各類格子的值, 則窗口的大小為|W|>=j×F.

推理1假設S表示一類符合(w,γ,k)-窗口要求的匿名方式,S主要接收Tin流數據, 從而生成Tout流數據. 若窗口Tin每次向前發生一個格子的位移,S符合逾期要求, 且當窗口Tin每次向前發生一個格子的位移, 促使其首個格子里的信息過期, 同時輸出其格子里的信息.

定義2((w,γ,k)-窗口匿名) 符合k-匿名, 并且其相似度的數值最大為γ, 匿名化的流數據通常被視為是(w,γ,k)-窗口匿名, 且僅當其符合(w,γ,k)-窗口及逾期要求.

2 算法設計

當每次有F個新信息傳輸到窗口中, 窗口向前發生一格的位移, 與持續傳遞的信息保持一致, 實現了一整套的窗口. 為了防止不同窗口之間信息的模糊, 通過不同的符號劃定窗口類. 為方便,t時間的窗口表示為W,i時間的窗口表示為Wi.

隨著非靜態化輸入信息Tin的到達, 窗口逐步向前發生位移, 持續出現了一整套窗口W1,W2,…,Wi,Wi+1,…. 當窗口Wi向前發生一格位移時, 出現了新型窗口Wi+1. 首格中的信息表示最初的數據信息, 同時落在窗口Wi+1的外側, 是要求輸出的, 因此將此類記錄稱為逾期信息. 伴隨著窗口持續的移動, 要求輸出一整套逾期信息的格子.

若Tin表示輸入信息, 針對其執行(w,γ,k)-窗口決策.Tin接近窗口后, 其緩存于末尾格子中. 當其窗口由Wi移動到Wi+1時, 要求出現包括一切窗口Wi逾期信息的等價類型. 所以, 敏感屬性值及敏感級必須與窗口中的信息轉變保持一致.

敏感屬性的等級屬于一類變量范疇. 窗口W中的敏感級由時間數據信息確定, 且流數據一般是時刻變化的, 必須依照數據信息的變化檢測相關敏感分級, 鑒于逾期信息的敏感分級與目前窗口信息的敏感分級的差異, 所以必須產生窗口Wi+1整套記錄的符合(w,γ,k)-匿名要求的匿名化數據信息, 然后輸出匿名數據中含有逾期信息的等價類型.Tout表示輸出的等價類型, 當窗口移動一格到達Wi+1時, 落在窗口Wi+1中, 完成輸出.

綜上所述, 本文對所有類型的記錄進行區分. 符號定義為：R(W)表示窗口W的所有記錄；Ro(W)表示窗口W完成輸出的記錄；Rn(W)表示窗口W未完成輸出的記錄；Re(W)表示窗口W的首格記錄, 也稱為過期數據；Ren(W)表示窗口W過期數據中未完成輸出的記錄；V(W)表示窗口W所有記錄敏感屬性值組成的數據集；Vn(W)表示窗口W未完成輸出記錄的敏感屬性值組成的數據集；L(W)表示V(W)的敏感級別；Ln(W)表示Vn(W)的敏感級別.

LCWA算法對輸入流數據Tin匿名化符合(w,γ,k)-窗口及過期條件的數據. LCWA算法過程描述如下.

LCWA算法.

1) 數據輸入：Tin, 參數w,γ,k;

2) 數據輸出：Tout;

3) 在窗口W中, 對前|W|>條Tin記錄進行緩沖操作;

4) 使S={g}作為等價類數據集合, 并進行初始化, 使其為空集;

5) 一旦從Tin有任意的F條記錄到達; 則若Ren(W)=0, 更新W, 即向前滑動一格進行記錄, 否則轉5)；

6) 根據Vn(W)生成Ln(W), 確保按敏感級別實施分級；

7) 根據V(W)生成L(W), 確保按敏感級別實施分級；

8) 若Ren(W)>0, 同時針對所有敏感值v∈Vn(W), 且其在Ln(W)與L(W)中的敏感級別一致:

① 對所有的Vn(W)賦權值,S={g}=TDL(w,γ,k)；

②Tout={g|r∈g, 對每個r∈Ren(W)};

③ 將Tout從S去掉;

④ 更新W, 即向前滑動一格進行記錄；

9) 若Ren(W)<0, 則：

①Tout={g|g∈S};

② 對S執行清空操作;

10) 更新W, 即向前滑動一格進行記錄.

定理1給定窗口W, 在LCWA算法中, 若時間t滿足UNEQUAL的要求, 且按其流程實施.Ren(W)的概念與上文相同, 則Ren(W)中的每條信息均屬于S中的一種等價類型.

證明： 假設UNEQUAL流程被實施, 則窗口W中至少有兩個格子, 即j>1. 設j=1, 則W中僅有一個格子, 格子中的一切數據均為逾期數據信息, 開始置入到Tout中并執行輸出操作. 當目前窗口向W移動時, 窗口數據信息均是時間Tin輸入的, 所以窗口中一般沒有逾期且已執行輸出操作的數據信息. 從而Vn(W)=V(W), 由此可推斷出Ln(W)=L(W), 與UNEQUAL條件下的Ln(W)/L(W)≠0矛盾. 所以,j>1.

在早期階段, 窗口中的數據均未能被執行輸出操作, 算法實施UNEQUAL流程. 所以在時間t前至少調用過一類UNEQUAL流程. 不妨假設時間t1的窗口W1是時間t前的最終調用UNEQUAL流程. 在窗口W1中,R(W1)數據匿名化后出現等價類型, 將其類型標記為S.

若窗口W和窗口W1沒有交集, 因為j>1, 則在t1和t之間至少也存在一段調用流程的時間, 即t2. 時間t2或許是進行NULL或UNEQUAL操作. 若時間t2實施UNEQUAL流程, 則時間處于t2時, 除了末尾一個格子的信息外均開始被執行輸出操作. 并且由于W1為時間t前最后一類實施EQUAL的窗口, 同時W1∩W=?, 因而W中沒有信息被輸出. 所以, 存在Ln(W)/L(W)=0, 且R(W)=Rn(W), 與Ln(W)/L(W)≠0矛盾. 因此, 時間t2實施了NULL流程.t1和t之間不存在輸出信息, 則窗口W也不存在輸出信息. 所以, 在W中,Ln(W)/L(W)=0且R(W)=Rn(W)與Ln(W)/L(W)≠0矛盾. 因此, 窗口W1與窗口W相交于一點, 兩類窗口至少有一類統一的格子, 則W的首個格子中的數據落到W1中, 所以Ren(W)中的信息屬于S中的某種等價類型.

3 仿真結果與分析

本文實驗采用開放數據集Census(http：//ipums.org), 選用以往數據集中的7類屬性共50萬條信息. 預操作數據的主要目的為刪除具備空值的信息. 與多數隱私保護仿真實驗相同, 將Occupation稱為敏感屬性. 將本文LCWA算法和經典Incognito算法進行比較. Incognito算法是一類自底向上的整體重編碼計算方法, 每次檢測等價類型是否符合k-匿名要求. 本文實驗將Incognito算法延伸到每步反復檢測等價類型是否符合(w,r,k)-匿名要求, 即eIncognito算法. 針對流數據的功能研究, 本文將比較|W|>與F轉變時3類模型的情況. 模型的設定是(w,r,k)中轉變3類指標的取值： 模型Ⅰ為(1.0,0.6,3.0); 模型Ⅱ為(1.0,1.0,3.0); 模型Ⅲ為(1.0,1.0,3.0). 運用不同的計算方法： 模型Ⅰ與模型Ⅱ采用LCWA計算方法, 模型Ⅲ采用eIncognito計算方法.

3種模型在窗口大小|W|>變動情況下的失真比率實驗結果如圖1所示. 由圖1可見, 本文提出的LCWA算法相比eIncognito算法能進一步降低信息失真率, 數據隱私保護性能更優. 并且因為模型Ⅱ未加大對參數γ的限制, 從而導致模型Ⅱ比模型Ⅰ實驗結果信息失真率更低. 同時, 圖1(A)也表明了窗口數值|W|>的大小與實驗模型的數據信息失真率成反比.

圖1 3種模型的信息量損失曲線Fig.1 Information loss curves of 3 models

圖1中3種模型實驗所消耗的時間如圖2所示. 由圖2可見, LCWA算法表現優于eIncognito算法. 由圖2(A)可見, 當窗口框架增加時, 3種模型的作業時間均有提升； 由圖2(B)可見, 模型Ⅰ的限制比模型Ⅱ嚴重, 由于考慮到LCWA算法屬于一類自頂向下的計算方法, 模型Ⅱ要求更多的循環流程.

圖2 3種模型的執行時間比較Fig.2 Comparisons of execution time of 3 models

綜上所述, 本文在流數據的基礎上提出了一種新的數據信息匿名算法. 通過把數據限制于一類窗口中， 根據流數據的變化, 促使敏感值的劃定和數據同時變更實現對流數據發布信息隱私保護, 有利于維護流數據的匿名安全. 其模型中采用了LCWA算法, 是一類自頂向下部分重編碼的計算方法, 與整體重編碼的計算方法elncognito相比, 極大減小了信息量虧損, LCWA算法的精確性也較其他算法更高.

[1] 王喆, 周春光, 周東濱, 等. 雙層結構的流數據聚類算法 [J]. 吉林大學學報(理學版), 2005, 43(3): 303-307. (WANG Zhe, ZHOU Chunguang, ZHOU Dongbin, et al. Clustering Data Streams of Two-Tier Structure [J]. Journal of Jilin University (Science Edition), 2005, 43(3): 303-307.)

[2] Memon I. Authentication User’s Privacy: An Integrating Location Privacy Protection Algorithm for Secure Moving Objects in Location Based Services [J]. Wireless Personal Communications, 2015, 82(3): 1585-1600.

[3] Jin X. Research into Mining Algorithm of Efficient Privacy Protection Frequent Pattern Based on Granular Computation [J]. Boletin Tecnico/Technical Bulletin, 2016, 69(14): 2188-2195.

[4] 王寅. 消費者網購時行為意向對個人信息泄露的影響研究 [J]. 重慶郵電大學學報(自然科學版), 2017, 29(6): 830-836. (WANG Yin. Investigating the Impact of Customers’ Online Shopping Behavior Intention on Personal Information Disclosure in Online Shopping Process [J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2017, 29(6): 830-836.)

[5] 彭曉冰， 李啟順， 王麗珍, 等. 面向SVM 的隱私保護方法研究進展 [J]. 江蘇大學學報(自然科學版), 2017, 38(1): 78-85. (PENG Xiaobing， LI Qishun， WANG Lizhen， et al. Research Progress of Privacy-Preserving Support Vector Machines [J]. Journal of Jiangsu University (Natural Science Edition), 2017, 38(1): 78-85.)

[6] 劉湘雯， 王良民. 數據發布匿名技術進展 [J]. 江蘇大學學報(自然科學版), 2016, 37(5): 562-571. (LIU Xiangwen， WANG Liangmin. Advancement of Anonymity Technique for Data Publishing [J]. Journal of Jiangsu University (Natural Science Edition), 2016, 37(5): 562-571.)

[7] LI Feifei, Papadimitriou S, Mihaila G A, et al. Hiding in the Crowd: Privacy Preservation on Evolving Streams through Correlation Tracking [C]//International Conference on Data Engineering. Piscataway, NJ: IEEE, 2007: 686-695.

[8] Cao J, Carminati B, Ferrari E, et al. CASTLE: A Delay-Constrained Scheme forkSanonymizing Data Streams [C]//International Conference on Data Engineering. Piscataway, NJ: IEEE, 2008: 1376-1378.

[9] WANG Pu, LU Jianjiang, ZHAO Lei, et al. B-CASTLE: An Efficient Publishing Algorithm forK-Anonymizing Data Streams [C]//WRI Global Congress on Intelligent Systems. Washington, DC: IEEE Computer Society, 2010: 132-136.

[10] Zakerzadeh H, Osborn S L. FAANST: Fast Anonymizing Algorithm for Numerical Streaming Data [C]//Data Privacy Management and Autonomous Spontaneous Security. Berlin: Springer-Verlag, 2011: 36-50.

[11] Muthu Lakshmi N V, Sandhya Rani K. Privacy Preserving Association Rule Mining of Mixed Partitioned Model in Distributed Database Environment [J]. International Journal of Computer Science & Information Technology, 2014, 5(1): 340-349.

[12] Chan M, Elsherbini H, ZHANG Xiaowen. User Density and Spatial Cloaking Algorithm Selection: Improving Privacy Protection of Mobile Users [C]//Sarnoff Symposium. Piscataway, NJ: IEEE, 2017: 1-2.

[13] George J A, Hemalatha M. OpenID Multiple Key Protection Algorithm to Improve Privacy in Cloud-Based Identity Services [J]. International Journal of Applied Engineering Research, 2015, 10(16): 37569-37573.