基于部分重编码的流数据发布隐私保护算法

赵素蕊, 高双喜

(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.