趙素蕊, 高雙喜

(1. 河北經(jīng)貿(mào)大學(xué) 計(jì)算機(jī)中心, 石家莊 050061; 2. 河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院, 石家莊 050061)

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

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

1 流數(shù)據(jù)的隱私維護(hù)模型

本文提出的流數(shù)據(jù)發(fā)布隱私保護(hù)算法基于經(jīng)典的隱私保護(hù)算法, 并將其應(yīng)用在流數(shù)據(jù)的發(fā)布上. 流數(shù)據(jù)通常是逐步變更的數(shù)據(jù), 伴隨著時限的轉(zhuǎn)變, 流數(shù)據(jù)被認(rèn)為是無限的值. 為了對流數(shù)據(jù)進(jìn)行有效建模, 本文把流數(shù)據(jù)控制在一類區(qū)域內(nèi)進(jìn)行研究, 將該類區(qū)域稱為窗口.

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

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

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

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

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

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

2 算法設(shè)計(jì)

當(dāng)每次有F個新信息傳輸?shù)酱翱谥? 窗口向前發(fā)生一格的位移, 與持續(xù)傳遞的信息保持一致, 實(shí)現(xiàn)了一整套的窗口. 為了防止不同窗口之間信息的模糊, 通過不同的符號劃定窗口類. 為方便,t時間的窗口表示為W,i時間的窗口表示為Wi.

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

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

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

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

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

LCWA算法.

1) 數(shù)據(jù)輸入：Tin, 參數(shù)w,γ,k;

2) 數(shù)據(jù)輸出：Tout;

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

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

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

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

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

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

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

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

③ 將Tout從S去掉;

④ 更新W, 即向前滑動一格進(jìn)行記錄；

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

①Tout={g|g∈S};

② 對S執(zhí)行清空操作;

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

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

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

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

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

3 仿真結(jié)果與分析

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

3種模型在窗口大小|W|>變動情況下的失真比率實(shí)驗(yàn)結(jié)果如圖1所示. 由圖1可見, 本文提出的LCWA算法相比eIncognito算法能進(jìn)一步降低信息失真率, 數(shù)據(jù)隱私保護(hù)性能更優(yōu). 并且因?yàn)槟Ｐ廷蛭醇哟髮?shù)γ的限制, 從而導(dǎo)致模型Ⅱ比模型Ⅰ實(shí)驗(yàn)結(jié)果信息失真率更低. 同時, 圖1(A)也表明了窗口數(shù)值|W|>的大小與實(shí)驗(yàn)?zāi)Ｐ偷臄?shù)據(jù)信息失真率成反比.

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

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

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

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

[1] 王喆, 周春光, 周東濱, 等. 雙層結(jié)構(gòu)的流數(shù)據(jù)聚類算法 [J]. 吉林大學(xué)學(xué)報(理學(xué)版), 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] 王寅. 消費(fèi)者網(wǎng)購時行為意向?qū)€人信息泄露的影響研究 [J]. 重慶郵電大學(xué)學(xué)報(自然科學(xué)版), 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 的隱私保護(hù)方法研究進(jìn)展 [J]. 江蘇大學(xué)學(xué)報(自然科學(xué)版), 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] 劉湘雯， 王良民. 數(shù)據(jù)發(fā)布匿名技術(shù)進(jìn)展 [J]. 江蘇大學(xué)學(xué)報(自然科學(xué)版), 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.