ACM SIGMOD Anthology TODS dblp.uni-trier.de

The Tracker: A Threat to Statistical Database Security.

Dorothy E. Denning, Peter J. Denning, Mayer D. Schwartz: The Tracker: A Threat to Statistical Database Security. ACM Trans. Database Syst. 4(1): 76-96(1979)
@article{DBLP:journals/tods/DenningDS79,
  author    = {Dorothy E. Denning and
               Peter J. Denning and
               Mayer D. Schwartz},
  title     = {The Tracker: A Threat to Statistical Database Security},
  journal   = {ACM Trans. Database Syst.},
  volume    = {4},
  number    = {1},
  year      = {1979},
  pages     = {76-96},
  ee        = {http://doi.acm.org/10.1145/320064.320069, db/journals/tods/DenningDS79.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The query programs of certain databases report raw statistics for query sets, which are groups of records specified implicitly by a characteristic formula. The raw statistics include query set size and sums of powers of values in the query set. Many users and designers believe that the individual records will remain confidential as long as query programs refuse to report the statistics of query sets which are too small. It is shown that the compromise of small query sets can in fact almost always be accomplished with the help of characteristic formulas called trackers. Schlörer's individual tracker is reviewed, it is derived from known characteristics of a given individual and permits deducing additional characteristics he may have. The general tracker is introduced: It permits calculating statistics for arbitrary query sets, without requiring preknowledge of anything in the database. General trackers always exist if there are enough distinguishable classes of individuals in the database, in which case the trackers have a simple form. Almost all databases have a general tracker, and general trackers are almost always easy to find. Security is not guaranteed by the lack of a general tracker.

Copyright © 1979 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
[2]
Donald D. Chamberlin, Raymond F. Boyce: SEQUEL: A Structured English Query Language. SIGMOD Workshop, Vol. 1 1974: 249-264 BibTeX
[3]
Francis Y. L. Chin: Security in Statistical Databases for Queries with Small Counts. ACM Trans. Database Syst. 3(1): 92-104(1978) BibTeX
[4]
David P. Dobkin, Anita K. Jones, Richard J. Lipton: Secure Databases: Protection Against User Influence. ACM Trans. Database Syst. 4(1): 97-106(1979) BibTeX
[5]
...
[6]
...
[7]
M. R. Garey, David S. Johnson: ``Strong'' NP-Completeness Results: Motivation, Examples, and Implications. J. ACM 25(3): 499-508(1978) BibTeX
[8]
...
[9]
...
[10]
...
[11]
John B. Kam, Jeffrey D. Ullman: A Model of Statistical Databases and Their Security. ACM Trans. Database Syst. 2(1): 1-10(1977) BibTeX
[12]
...
[13]
...
[14]
...
[15]
...
[16]
...
[17]
...
[18]
Mayer D. Schwartz, Dorothy E. Denning, Peter J. Denning: Linear Queries in Statistical Databases. ACM Trans. Database Syst. 4(2): 156-167(1979) BibTeX
[19]
...
[20]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX
[21]
Clement T. Yu, Francis Y. L. Chin: A Study on the Protection of Statistical Data Bases. SIGMOD Conference 1977: 169-181 BibTeX
[22]
Bruce W. Weide: A Survey of Analysis Techniques for Discrete Algorithms. ACM Comput. Surv. 9(4): 291-313(1977) BibTeX

Referenced by

  1. Rakesh Agrawal, Ramakrishnan Srikant: Privacy-Preserving Data Mining. SIGMOD Conference 2000: 439-450
  2. Keishi Tajima: Static Detection of Security Flaws in Object-Oriented Databases. SIGMOD Conference 1996: 341-352
  3. Patrick Tendick, Norman S. Matloff: A Modified Random Perturbation Method for Database Security. ACM Trans. Database Syst. 19(1): 47-63(1994)
  4. Zbigniew Michalewicz, Jia-Jie Li, Keh-Wei Chen: Optimal Distribution of Restricted Ranges in Secure Statistical Database. SSDBM 1990: 65-79
  5. Nabil R. Adam, John C. Wortmann: Security-Control Methods for Statistical Databases: A Comparative Study. ACM Comput. Surv. 21(4): 515-556(1989)
  6. Zbigniew Michalewicz, Keh-Wei Chen: Ranges and Trackers in Statistical Databases. SSDBM 1988: 193-206
  7. Francesco M. Malvestuto, C. Zuffada: The Classification Problem with Semantically Heterogeneous Data. SSDBM 1988: 157-176
  8. Subhasish Mazumdar, David W. Stemple, Tim Sheard: Resolving the Tension between Integrity and Security Using a Theorem Prover. SIGMOD Conference 1988: 233-242
  9. Joseph F. Traub, Yechiam Yemini, Henryk Wozniakowski: The Statistical Security of a Statistical Database. ACM Trans. Database Syst. 9(4): 672-679(1984)
  10. Steven P. Reiss: Practical Data-Swapping: The First Steps. ACM Trans. Database Syst. 9(1): 20-37(1984)
  11. Robert P. Trueblood, H. Rex Hartson, Johannes J. Martin: MULTISAFE - A Modular Multiprocessing Approach to Secure Database Management. ACM Trans. Database Syst. 8(3): 382-409(1983)
  12. Wiebren de Jonge: Compromising Statistical Databases Responding to Queries about Means. ACM Trans. Database Syst. 8(1): 60-80(1983)
  13. Ezio Lefons, Alberto Silvestri, Filippo Tangorra: An Analytic Approach to Statistical Databases. VLDB 1983: 260-274
  14. Zbigniew Michalewicz: Statistical Databases: Their Model, Query Language and Security. SSDBM 1983: 391-402
  15. Dorothy E. Denning: A Security Model for the Statistical Database Problem. SSDBM 1983: 368-390
  16. Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222
  17. Ernst L. Leiss: Randomizing, A Practical Method for Protecting Statistical Databases Against Compromise. VLDB 1982: 189-196
  18. Steven P. Reiss, Mark J. Post, Tore Dalenius: Non-reversible Privacy Transformations. PODS 1982: 139-146
  19. Jan Schlörer: Security of Statistical Databases: Multidimensional Transformation. ACM Trans. Database Syst. 6(1): 95-112(1981)
  20. Francis Y. L. Chin, Gultekin Özsoyoglu: Statistical Database Design. ACM Trans. Database Syst. 6(1): 113-139(1981)
  21. Hideto Sato, Ryosuke Hotaka: For Large Meta Information of National Integrated Statistics. SSDBM 1981: 206-223
  22. Hideto Ikeda, Yasuyuki Kobayashi: Additional Facilities of a Concentional DBMS to Support Interactive Statistical Analysis. SSDBM 1981: 25-36
  23. Jitender S. Deogun, Vijay V. Raghavan: Query Directed Partitioning Scheme for Securing Statistical Databases. SSDBM 1981: 285-293
  24. Francis Y. L. Chin, Peter Kossowski: Efficient Inference Control for Range SUM Queries on Statistical Data Bases. SSDBM 1981: 239-248
  25. Jan Schlörer: Disclosure from Statistical Databases: Quantitative Aspects of Trackers. ACM Trans. Database Syst. 5(4): 467-492(1980)
  26. Dorothy E. Denning, Jan Schlörer: A Fast Procedure for Finding a Tracker in a Statistical Database. ACM Trans. Database Syst. 5(1): 88-102(1980)
  27. Dorothy E. Denning: Secure Statistical Databases with Random Sample Queries. ACM Trans. Database Syst. 5(3): 291-315(1980)
  28. Leland L. Beck: A Security Mechanism for Statistical Databases. ACM Trans. Database Syst. 5(3): 316-338(1980)
  29. Mayer D. Schwartz, Dorothy E. Denning, Peter J. Denning: Linear Queries in Statistical Databases. ACM Trans. Database Syst. 4(2): 156-167(1979)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:38:40 2008