A Pufferfish privacy mechanism for monitoring web browsing behavior under temporal correlations. Issue 92 (May 2020) - Liang, Wenjuan
Abstract: Monitoring web browsing behavior can benefit for many data mining tasks, such as top-k mining and suspicious behavior watching. However, directly releasing private browsing data to the public would raise user concerns from a privacy perspective. Differential privacy, the current gold standard in data privacy, does not adequately address privacy issues in correlated data. For this reason, Pufferfish privacy, a recent generalization of differential privacy for correlated data, can be used. The goal of our work is to share useful statistics of on-line browsing behavior to perform monitoring tasks while protecting individual user privacy. To achieve this goal, the privacy requirements in our problem are specified in the Pufferfish framework firstly. Then a privacy leakage computation model (PLCM) is designed based on the previous privacy specification, which can be used to make a quantitative analysis of the maximum privacy leakage caused by temporal correlations. Since the computational complexity of PLCM is too high and cannot meet the real-time requirement, three strategies (bounding the number of secret pairs, limiting the maximum length of sessions and avoiding solving the subproblems repeatedly) are proposed to promote efficiency thirdly. At last, a privately continual release algorithm for web monitoring is presented based on the maximum privacy leakage calculated in the previous steps, which can reduce the computational complexity and the added noise significantly. Formal privacy analysis shows that our scheme satisfies ϵ-Pufferfish privacy. Extensive experiment results on the real-world dataset illustrate that our scheme outperforms other state-of-the-art techniques.