The tracker: a threat to statistical database security

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.

REFERENCES

• 1: M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
• 2: Donald D. Chamberlin , Raymond F. Boyce, SEQUEL: A structured English query language, Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, p.249-264, May 01-03, 1974, Ann Arbor, Michigan [doi>10.1145/800296.811515]
• 3: Francis Y. Chin, Security in statistical databases for queries with small counts, ACM Transactions on Database Systems (TODS), v.3 n.1, p.92-104, March 1978 [doi>10.1145/320241.320250]
• 4: David Dobkin , Anita K. Jones , Richard J. Lipton, Secure databases: protection against user influence, ACM Transactions on Database Systems (TODS), v.4 n.1, p.97-106, March 1979 [doi>10.1145/320064.320068]
• 5: FELLE6{, I.P. On the question of statistical confidentiality. J. Amer. Statist. Assoc. 67, 337 (March 1972), 7-18.
• 6: FELLEGI, I.P., AND PHILLIPS, J. L. Statistical confidentiality: Some theory and applications to data dissemination. Annals Econ. Soc'l Measurement 3, 2 (April 1974), 399-409.
• 7: M. R. Garey , D. S. Johnson, `` Strong '' NP-Completeness Results: Motivation, Examples, and Implications, Journal of the ACM (JACM), v.25 n.3, p.499-508, July 1978 [doi>10.1145/322077.322090]
• 8: HANSEN, M.H. Insuring confidentiality of individual records in data storage and retrieval for statistical purposes. Proc. AFIPS 1971 FJCC, Vol. 39, AFIPS Press, Montvale, N.J., pp. 579-585.
• 9: HAQ, M.I. Security in a statistical data base. Proc. Amer. Soc. Inform. Sci. 11 (1974), 33-39.
• 10: HOFFMAN, L.J., AND MILLER, W.F. Getting a personal dossier from a statistical data bank. Datamation16, 5 (May 1970), 74-75.
• 11: John B. Kam , Jeffrey D. Ullman, A model of statistical database their security, ACM Transactions on Database Systems (TODS), v.2 n.1, p.1-10, March 1977 [doi>10.1145/320521.320525]
• 12: NARGUNDKAR, M.S., AND SAVELAND, W. Random rounding to prevent statistical disclosure. Proc. Amer. Statist. Assoc., Soc. Statistics Sect. (1972), 382-385.
• 13: PALME, J. Software security. Datamation 20, 1 (Jan. 1974), 51-55.
• 14: SCHLORER, J. Identification and retrieval of personal records from a statistical data bank. Methods of Inform. in Medicine 14, 1 (Jan. 1975), 7-I3.
• 15: SCHLORZR, J. Confidentiality of statistical records: A threat monitoring scheme for on-line dialogue. Methods of Inform. in Medicine 15, 1 (Jan. 1976), 36-42.
• 16: SCHLORER, J. Union tracker and open statistical databases. Rep. TB-IMSD 1/78, Institut ftir Medizinische Statistik und Dokumentation, Universi~t Giessen, June 1978.
• 17: Mayer Dlugach Schwartz, Inference from statistical data bases., 1977
• 18: M. D. Schwartz , D. E. Denning , P. J. Denning, Linear queries in statistical databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.156-167, June 1979 [doi>10.1145/320071.320073]
• 19: SCHWARTZ, M.D., DENNING, D.E., AND DENNING, P.J. Securing data bases under linear queries. Information Processing 77, North-Holland Pub. Co., Amsterdam, 1977, pp. 395-398.
• 20: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 21: C. T. Yu , F. Y. Chin, A study on the protection of statistical data bases, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509432]
• 22: Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977 [doi>10.1145/356707.356711]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Design, Security

Keywords:
confidentiality, data security, database security, secure query functions, statistical database, tracker