Please wait a minute...

Frontiers of Computer Science

Front. Comput. Sci.    2018, Vol. 12 Issue (6) : 1192-1207     https://doi.org/10.1007/s11704-016-6049-6
RESEARCH ARTICLE |
SMT-based query tracking for differentially private data analytics systems
Chen LUO1,2, Fei HE1,2()
1. Tsinghua National Laboratory for Information Science and Technology (TNList), School of Software, Tsinghua University, Beijing 100084, China
2. Key Laboratory for Information System Security, Ministry of Education, Tsinghua University, Beijing 100084, China
Download: PDF(420 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Differential privacy enables sensitive data to be analyzed in a privacy-preserving manner. In this paper, we focus on the online setting where each analyst is assigned a privacy budget and queries the data interactively. However, existing differentially private data analytics systems such as PINQ process each query independently, which may cause an unnecessary waste of the privacy budget. Motivated by this, we present a satisfiability modulo theories (SMT)-based query tracking approach to reduce the privacy budget usage. In brief, our approach automatically locates past queries that access disjoint parts of the dataset with respect to the current query to save the privacy cost using the SMT solving techniques. To improve efficiency, we further propose an optimization based on explicitly specified column ranges to facilitate the search process. We have implemented a prototype of our approach with Z3, and conducted several sets of experiments. The results show our approach can save a considerable amount of the privacy budget and each query can be tracked efficiently within milliseconds.

Keywords differential privacy      privacy budget      satisfiability modulo theory     
Corresponding Authors: Fei HE   
Just Accepted Date: 28 September 2016   Online First Date: 06 March 2018    Issue Date: 04 December 2018
 Cite this article:   
Chen LUO,Fei HE. SMT-based query tracking for differentially private data analytics systems[J]. Front. Comput. Sci., 2018, 12(6): 1192-1207.
 URL:  
http://journal.hep.com.cn/fcs/EN/10.1007/s11704-016-6049-6
http://journal.hep.com.cn/fcs/EN/Y2018/V12/I6/1192
Service
E-mail this article
E-mail Alert
RSS
Articles by authors
Chen LUO
Fei HE
1 Dwork C. Differential privacy. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. 2006, 1–12
https://doi.org/10.1007/11787006_1
2 McSherry F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. Communications of the ACM, 2009, 53: 19–30
https://doi.org/10.1145/1559845.1559850
3 Silberschatz A, Korth H F, Sudarshan S. Database System Concepts. Vol 4. New York: McGraw-Hill, 1997
4 McSherry F, Talwar K. Mechanism design via differential privacy. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. 2007, 94–103
https://doi.org/10.1109/FOCS.2007.66
5 De Moura L, Bjørner N. Z3: an efficient SMT solver. In: Proceedings of International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2008, 337–340
https://doi.org/10.1007/978-3-540-78800-3_24
6 Lichman M. UCI machine learning repository. Irvine, CA: University of California. 2013
7 Barnett M, Chang B Y E, DeLine R, Jacobs B, Leino K R M. Boogie: a modular reusable verifier for object-oriented programs. In: Proceedings of International Conference on Formal Methods for Components and Objects. 2006, 364–387
https://doi.org/10.1007/11804192_17
8 Kroening D, Tautschnig M. CBMC–C bounded model checker. In: Proceedings of the 20th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2014, 389–391
https://doi.org/10.1007/978-3-642-54862-8_26
9 Godefroid P, Levin M Y, Molnar D A. Automated whitebox fuzz testing. In: Proceedings of Network and Distributed System Security Symposium. 2008, 151–166
10 Cadar C, Godefroid P, Khurshid S, Păsăreanu C S, Sen K, Tillmann N, Visser W. Symbolic execution for software testing in practice: preliminary assessment. In: Proceedings of the 33rd International Conference on Software Engineering. 2011, 1066–1071
https://doi.org/10.1145/1985793.1985995
11 Cimatti A, Griggio A, Schaafsma B J, Sebastiani R. The NathSAT5 SMT solver. In: Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 2013, 93–107
12 Dutertre B. Yices 2.2. In: Proceedings of International Conference on Computer Aided Verification. 2014, 737–744
https://doi.org/10.1007/978-3-319-08867-9_49
13 Xiao X, Wang G, Gehrke J. Differential privacy via wavelet transforms. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(8): 1200–1214
https://doi.org/10.1109/TKDE.2010.247
14 Hay M, Rastogi V, Miklau G, Suciu D. Boosting the accuracy of differentially private histograms through consistency. Proceedings of the VLDB Endowment, 2010, 3(1–2): 1021–1032
https://doi.org/10.14778/1920841.1920970
15 Xu J, Zhang Z J, Xiao X K, Yang Y, Yu G. Differentially private histogram publication. In: Proceedings of IEEE International Conference on Data Engineering. 2012, 32–43
https://doi.org/10.1109/ICDE.2012.48
16 Chen R, Mohammed N, Fung B C M, Desai B C, Xiong L. Publishing set-valued data via differential privacy. Proceedings of the VLDB Endowment, 2011, 4(11): 1087–1098
17 Zhang J, Cormode G, Procopiuc C M, Srivastava D, Xiao X K. Privbayes: private data release via Bayesian networks. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2014, 1423–1434
https://doi.org/10.1145/2588555.2588573
18 Xiao X K, Bender G, Hay M, Gehrke J. iReduct: differential privacy with reduced relative errors. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2011, 229–240
https://doi.org/10.1145/1989323.1989348
19 Li C, Hay M, Rastogi V, Miklau G, McGregor A. Optimizing linear counting queries under differential privacy. In: Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 2010, 123–134
https://doi.org/10.1145/1807085.1807104
20 Li C, Miklau G. An adaptive mechanism for accurate query answering under differential privacy. Proceedings of the VLDB Endowment, 2012, 5(6): 514–525
https://doi.org/10.14778/2168651.2168653
21 Yuan G Z, Zhang Z J, Winslett M, Xiao X K, Yang Y, Hao Z F. Lowrank mechanism: optimizing batch queries under differential privacy. Proceedings of the VLDB Endowment, 2012, 5(11): 1352–1363
https://doi.org/10.14778/2350229.2350252
22 Peng S F, Yang Y, Zhang Z J, Winslett M, Yu Y. Query optimization for differentially private data management systems. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2013, 1093–1104
23 Agrawal R, Bayardo R, Faloutsos C, Kiernan J, Rantzau R, Srikant R. Auditing compliance with a hippocratic database. In: Proceedings of the 30th International Conference on Very Large Data Bases. 2004, 516–527
https://doi.org/10.1016/B978-012088469-8.50047-4
24 Kaushik R, Ramamurthy R. Efficient auditing for complex SQL queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2011, 697–708
https://doi.org/10.1145/1989323.1989396
25 Miklau G, Suciu D. A formal analysis of information disclosure in data exchange. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2004, 575–586
https://doi.org/10.1145/1007568.1007633
26 Motwani R, Nabar S U, Thomas D. Auditing SQL queries. In: Proceedings of the 24th IEEE International Conference on Data Engineering. 2008, 287–296
https://doi.org/10.1109/ICDE.2008.4497437
Related articles from Frontiers Journals
[1] Xiaojian ZHANG,Xiaofeng MENG. Discovering top-k patterns with differential privacy–an accurate approach[J]. Front. Comput. Sci., 2014, 8(5): 816-827.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed