K—Q：支持海量查询的隐私泄露检测算法.pdf

第30卷第 12期 计 算 机 应 用 研 究 Vol_30No．12 2013年 12月 ApplicationResearchofCompute~ Dee．2013 K．Q：支持海量查询的隐私泄露检测算法 林永妍 ，宋 玲，陈玉婵 (广西大学计算机与电子信息学院，南宁530004) 摘 要：针对推理检测需要的所有历史查询结果的数据规模较大这一问题，K—Q算法结合K-匿名模型在历史查 询结果的存储规模上进行了优化，通过推理攻击模拟算法在线检测恶意查询。在真实数据集上的实验证明了 K．Q算法可以自适应于查询规模的增长，在准确率和 内存消耗上都明显优于已有的直接基于相关元组合并优化 的T．D算法。 关键词 ：K一匿名；数据共享平 台；隐私泄露检测；推理攻击 中图分类号：TP309 文献标志码：A 文章编号：1001-3695(2013)12—3767—04 doi：10．3969／j．issn．1001—3695．2013．12．064 K—Q：algorithmforprivacydisclosuredetectionsupporting largenumberofqueries LIN Yong—yan，SONG Ling，CHEN Yu—chan (SchoolofComputer，Electronics＆Information，GuangxiUniversity，Nanning530004，China) Abstract：Akeyproblemremainedthatthedatasetrequiredtodetectinferenceattackcannotallfitinmemo~，K—Qalgo· rithm optimizedtherealdatastorageforeachhistoryquery basedonK—anonymizationmodel，itdetectedtheillegalquery on- linethroughsimulatingtherealinferenceattack．ExperimentsonrealdatademonstratethatK—Qalgorithmcanscaleonquery size，andperform ondetectaccuracyandmemory consumptionisbetterthantheexistedT—D algorithmwhichdirectlymergere- latedtuplesandalsoassuretheprivacycontrol’Sgranularity． Keywords：K—anonymity；datasharingplatfomr ；privacydisclosure；inferenceattack 数据可用性越差；b)推理检测计算的效率问题，由于K一匿名已 0 引言 被证明为 NP—hard ，计算效率较低，因此难 以适应于大规模 的查询和数据的生成环境。为了保证数据质量和查询响应的 信息时代的不断发展 ，网络上的空间数据多种多样，用户 及时性，T—D算法摈弃了匿名模型，为了防止多次查询可能存 可以很随意地查询这些数据，获取 自己感兴趣的信息。在相对 在的链接攻击，它基于推理攻击的原理对当前查询获得的数据 开放的数据共享平台中，大多数用户操作体现为对后台数据的 和全部的历史查