Auditing for secure statistical databases

ABSTRACT

A statistical database (SDB) is an ordinary database that returns statistical information to user queries. The security problem for the SDB is to control the use of the SDB so that only statistical information is available and no sequence of queries is sufficient to infer protected information about any individual. When such information is obtained, the SDB is said to be compromised. Many researchers have studied different protection mechanisms to prevent an SDB from being compromised. However, most of these mechanisms are either ineffective or inefficient or are only applicable to large SDBs. Auditing in SDBs is initially proposed in the form of investigating log trails manually. In this paper, we present a practical technique for managing the past history of user's queries, discuss how the sequence of all the answered queries of the SDB can be reduced and stored in finite storage, and describe how this storage scheme can provide an effective way of checking compromise. We believe that this will help us to develop a more practical and efficient tool for protection in a small SDB than the previously known mechanisms. We also extend the idea to batched queries and a more general environment for better protection and performance. We also state that the problem of maximizing the amount of information to the users without compromising the SDB is NP-complete.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Leland L. Beck, A security machanism for statistical database, ACM Transactions on Database Systems (TODS), v.5 n.3, p.316-3338, Sept. 1980 [doi>10.1145/320613.320617]
• 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: Francis Y. Chin , Gultekin Ozsoyoglu, Statistical database design, ACM Transactions on Database Systems (TODS), v.6 n.1, p.113-139, March 1981 [doi>10.1145/319540.319558]
• 5: Chin F. Y., Ozsoyoglu G., "Security of Statistical Databases", Chapter 3, Advances in Computer Security Management, Hayden & Son, Inc., 1980.
• 6: Chin F. Y., Ozsoyoglu G., "Auditing and Inference Control in Statistical Databases", Tech. Report #81-1, CIS, Cleveland State University, 1981.
• 7: DeMillo R., Dobkin D., Lipton R. J., "Combinatorial Inference", Foundations of Secure Computation edited by DeMillo et al. Academic Press 1978, pp. 27-38, (presented at a 3 day workshop held at Georgia Institute of Technology, Atlanta Oct. 1977).
• 8: Denning D. E., "Are Statistical Databases Secure?", (Proc. AFIPS NCC Vol 47, 1948).
• 9: Dorothy E. Denning , Peter J. Denning , Mayer D. Schwartz, The tracker: a threat to statistical database security, ACM Transactions on Database Systems (TODS), v.4 n.1, p.76-96, March 1979 [doi>10.1145/320064.320069]
• 10: Dorothy E. Denning, Secure statistical databases with random sample queries, ACM Transactions on Database Systems (TODS), v.5 n.3, p.291-315, Sept. 1980 [doi>10.1145/320613.320616]
• 11: Dorothy E. Denning , Jan Schlörer, A fast procedure for finding a tracker in a statistical database, ACM Transactions on Database Systems (TODS), v.5 n.1, p.88-102, March 1980 [doi>10.1145/320128.320138]
• 12: Dobkin D., Lipton R. J., Reiss S. P., "Aspects of the Database Security Problem", Proceedings on a Conference on Theoretical Computer Science, Waterloo, Canada, 1977, pp. 262-274.
• 13: Fellegi I. P., Phillips J. L., "Statistical Confidentiality: Some Theory and Applications to Data Dissemination", Annals of Econ. Soc'l Measurement, 3, 2, 1972, pp. 399-409.
• 14: Garey M., Johnson D. and Stockmeyer L., "Some Simplified NP-Complete Graph Problems", Journal Theo. Comp. Sci., 1, 1976, pp. 237-267.
• 15: Hoffman L. J., Modern Methods for Computer Security and Privacy, Prentice-Hall, 1977.
• 16: 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]
• 17: Nargundkar M. S., Saveland W., "Random Rounding to Prevent Statistical Disclosure", Proc. Amer. Stat. Assoc., Soc. Stat. Sec., 1972, pp. 382-385.
• 18: Steven P. Reiss, Security in Databases: A Combinatorial Study, Journal of the ACM (JACM), v.26 n.1, p.45-57, Jan. 1979 [doi>10.1145/322108.322113]
• 19: Schlorer J., "Identification and Retrieval of Personal Records from a Statistical Databank", Methods of Info. in Medicine, 14, 1, 1975, pp. 7-15.
• 20: Schlorer J., "Confidentiality of Statistical Records: A Threat Monitoring Scheme for On-line dialogue", Methods of Info. in Medicine, 15, 1, 1976, pp. 36-42.
• 21: Schlorer J., "Union Tracker and Open Statistical Databases", TBIMSD 1/78, Inst. Med. Statist. Dok., Univ. Giessen, 1979
• 22: 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]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.4 System Management
          Subjects: Management audit

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

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Management, Security