A Fast Procedure for Finding a Tracker in a Statistical Database.

@article{DBLP:journals/tods/DenningS80,
  author    = {Dorothy E. Denning and
               Jan Schl{\"o}rer},
  title     = {A Fast Procedure for Finding a Tracker in a Statistical Database},
  journal   = {ACM Trans. Database Syst.},
  volume    = {5},
  number    = {1},
  year      = {1980},
  pages     = {88-102},
  ee        = {http://doi.acm.org/10.1145/320128.320138, db/journals/tods/DenningS80.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

To avoid trivial compromises, most on-line statistical databases refuse to answer queries for statistics about small subgroups. Previous research discovered a powerful snooping tool, the tracker, with which the answers to these unanswerable queries are easily calculated. However, the extent of this threat was not clear, for no one had shown that finding a tracker is guaranteed to be easy.

This paper gives a simple algorithm for finding a tracker when the maximum number of identical records is not too large. The number of queries required to find a tracker is at most O(log₂S) queries, where S is the number of distinct records possible. Experimental results show that the procedure often finds a tracker with just a few queries. The threat posed by trackers is therefore considerable.

Copyright © 1980 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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Francis Y. L. Chin: Security in Statistical Databases for Queries with Small Counts. ACM Trans. Database Syst. 3(1): 92-104(1978) BibTeX

[2]

...

[3]

George I. Davida, David J. Linton, C. Russel Szelag, David L. Wells: Database Security. IEEE Trans. Software Eng. 4(6): 531-533(1978) BibTeX

[4]

Richard A. DeMillo, David P. Dobkin, Richard J. Lipton: Even Data Bases That Lie Can Be Compromised. IEEE Trans. Software Eng. 4(1): 73-75(1978) BibTeX

[5]

...

[6]

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) BibTeX

[7]

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

[8]

...

[9]

John B. Kam, Jeffrey D. Ullman: A Model of Statistical Databases and Their Security. ACM Trans. Database Syst. 2(1): 1-10(1977) BibTeX

[10]

...

[11]

...

[12]

Jan Schlörer: Disclosure from Statistical Databases: Quantitative Aspects of Trackers. ACM Trans. Database Syst. 5(4): 467-492(1980) BibTeX

[13]

...

[14]

...

[15]

...

[16]

...

Referenced by

1. Arie Shoshani: OLAP and Statistical Databases: Similarities and Differences. PODS 1997: 185-196
2. Zbigniew Michalewicz, Jia-Jie Li, Keh-Wei Chen: Optimal Distribution of Restricted Ranges in Secure Statistical Database. SSDBM 1990: 65-79
3. Mary McLeish: Further Results on the Security of Partitioned Dynamic Statistical Databases. ACM Trans. Database Syst. 14(1): 98-113(1989)
4. Nabil R. Adam, John C. Wortmann: Security-Control Methods for Statistical Databases: A Comparative Study. ACM Comput. Surv. 21(4): 515-556(1989)
5. Zbigniew Michalewicz, Keh-Wei Chen: Ranges and Trackers in Statistical Databases. SSDBM 1988: 193-206
6. Wiebren de Jonge: Compromising Statistical Databases Responding to Queries about Means. ACM Trans. Database Syst. 8(1): 60-80(1983)
7. Ezio Lefons, Alberto Silvestri, Filippo Tangorra: An Analytic Approach to Statistical Databases. VLDB 1983: 260-274
8. Zbigniew Michalewicz: Statistical Databases: Their Model, Query Language and Security. SSDBM 1983: 391-402
9. Dorothy E. Denning: A Security Model for the Statistical Database Problem. SSDBM 1983: 368-390
10. Arie Shoshani: Statistical Databases: Characteristics, Problems, and some Solutions. VLDB 1982: 208-222
11. Ernst L. Leiss: Randomizing, A Practical Method for Protecting Statistical Databases Against Compromise. VLDB 1982: 189-196
12. Jan Schlörer: Disclosure from Statistical Databases: Quantitative Aspects of Trackers. ACM Trans. Database Syst. 5(4): 467-492(1980)
13. Dorothy E. Denning: Secure Statistical Databases with Random Sample Queries. ACM Trans. Database Syst. 5(3): 291-315(1980)