Auditing Boolean attributes

ABSTRACT

We study the problem of auditing databases which support statistical sum queries to protect the security of sensitive information; we focus on the special case in which the sensitive information is Boolean. Principles and techniques developed for the security of statistical database in the case of continuous attributes do not apply here. We prove certain strong complexity results suggesting that there is no general efficient solution for the auditing problem in this case. We propose two efficient algorithms: The first is applicable when the sum queries are one-dimensional range queries (we prove that the problem is NP-hard even in the two-dimensional case). The second is an approximate algorithm that maintains security, although it may be too restrictive. Finally, we consider a “dual” variant, with continuous data but an aggregate function that is combinatorial in nature. Specifically, we provide algorithms for two natural definitions of the auditing condition when the aggregate function is MAX.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 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: F. Chin, G. (Dsoyoglu "Auditing and Inference Control in Statistical Databases," IEEE SE-8, 1, pp. 574-582, 1982.
• 6: F. Chin, G. Osoyoglu "Security in Partitioned Dynamic Statistical Databases," Proc. IEEE COMP- SAC, pp. 594-601.
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: T. Dalenius "A Simple Procedure for Controlled Rounding," Statistik Tidsktift, 3, pp. 202-208, 1981.
• 9: 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]
• 10: A. Friedman, L. Hoffman "Towards a Fail-safe Approach to Security and Privacy," Proc. IEEE Syrup. on Security and Privacy, 1980.
• 11: Chong K. Liew , Uinam J. Choi , Chung J. Liew, A data distortion by probability distribution, ACM Transactions on Database Systems (TODS), v.10 n.3, p.395-411, Sept. 1985 [doi>10.1145/3979.4017]
• 12: G. Osoyoglu, F. Chin "Enhancing the Security of Statistical Databases with a Question-Answering System and a Kernel," IEEE SE-8, 3, pp. 223-234, 1982.
• 13: Steven P. Reiss, Practical data-swapping: the first steps, ACM Transactions on Database Systems (TODS), v.9 n.1, p.20-37, March 1984 [doi>10.1145/348.349]
• 14: Neil C. Rowe, Diophantine Inferences from Statistical Aggregates on Few-Valued Attributes, Proceedings of the First International Conference on Data Engineering, p.107-110, April 24-27, 1984
• 15: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 16: J. F. Traub , Y. Yemini , H. Woźniakowski, The statistical security of a statistical database, ACM Transactions on Database Systems (TODS), v.9 n.4, p.672-679, Dec. 1984 [doi>10.1145/1994.383392]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Security, Theory, Verification