Dynamic inference control

ABSTRACT

An inference problem exists in a multilevel database if knowledge of some objects in the database allows information with a higher security level to be inferred. Many such inferences may be prevented prior to any query processing by raising the security level of some of the objects, however this inevitably impedes information access, as a user with low authorization who queries just one of the objects with raised security must seek clearance even when not in danger of making the inference. More flexible access control is possible when inferences are prevented during query processing, however this practice can result in slow query response times. We demonstrate that access control can be made sufficiently dynamic to ensure easy access to the information users are entitled to, while retaining fast query processing. Our inference control schemes provide collusion resistance and have a query processing time that depends only on the length of the inference channels (not on the length of user query histories). In addition, our schemes provide a property we call crowd control that goes beyond collusion resistance to ensure that if a large number of users have queried all but one of the objects in an inference channel, then no one will be able to query the remaining object regardless of the level of collusion resistance provided by the scheme.

REFERENCES

• 1: A. Barani-Dastjerdi, J. Pieprzyk and R. Safavi-Naini. Security in databases: A survey study. Manuscript, 1996.
• 2: Leonard J. Binns, Implementation Considerations for Inference Detection: Intended vs. Actual Classification, Proceedings of the IFIP WG11.3 Working Conference on Database Security VII, p.297-306, September 12-15, 1993
• 3: D. Denning and T. Lunt. A multilevel relational data model. In IEEE Symposium on Security and Privacy, 1987.
• 4: S. Jajodia and C. Meadows. Inference problems in multilevel secure database management systems. In Information Security: An Integrated Collection of Essays, M. Abrams et al., eds., IEEE Computer Society Press (1995), pages 570--584.
• 5: John Hale , Sujeet Shenoi, Catalytic Inference Analysis: Detecting Inference Threats due to Knowledge Discovery, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.188, May 04-07, 1997
• 6: T. Hinke. Database inference engine design approach. In Database Security II: Status and Prospects, 1990.
• 7: T. Hinke, H. Degulach and A. Chandrasekhar. A fast algorithm for detecting second paths in database inference analysis. Journal of Computer Security, 1995.
• 8: Thomas H. Hinke , Harry S. Delugach , Asha Chandrasekhar, Layered Knowledge Chunks for Database Inference, Proceedings of the IFIP WG11.3 Working Conference on Database Security VII, p.275-295, September 12-15, 1993
• 9: T. F. Keefe , Bhavani Thuraisingham , W. T. Tsai, Secure Query-Processing Strategies, Computer, v.22 n.3, p.63-70, March 1989 [doi>10.1109/2.16229]
• 10: Ravi Kumar , Sridhar Rajagopalan , Amit Sahai, Coding Constructions for Blacklisting Problems without Computational Assumptions, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.609-623, August 15-19, 1999
• 11: T. Lunt. Access control policies for database systems. In Database Security II: Status and Prospects, pp. 41--52.
• 12: Donald G. Marks , Amihai Motro , Sushil Jajodia, Enhancing the Controlled Disclosure of Sensitive Information, Proceedings of the 4th European Symposium on Research in Computer Security: Computer Security, p.290-303, September 25-27, 1996
• 13: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 14: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 15: T. Y. Lin, Inference secure multilevel databases, Results of the Sixth Working Conference of IFIP Working Group 11.3 on Database Security on Database security, VI : status and prospects: status and prospects, p.317-332, January 1993, Simon Fraser Univ., Vancouver, British Columbia, Canada
• 16: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 17: Xiaolei Qian , Mark E. Stickel , Peter D. Karp , Teresa F. Lunt , Thomas D. Carvey, Detection and Elimination of Inference Channels in Multilevel Relational Database Systems, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.196, May 24-26, 1993
• 18: G. Smith. Modeling security-relevant data semantics. In IEEE Symposium on Security and Privacy, 1990.
• 19: Douglas R. Stinson , R. Wei, Key Preassigned Traceability Schemes for Broadcast Encryption, Proceedings of the Selected Areas in Cryptography, p.144-156, August 17-18, 1998
• 20: B. Sowerbutts and S. Cordingley. Database architectonics and inferential security. In Database Security IV, pp. 309--324.
• 21: Mark E. Stickel, Elimination of Inference Channels by Optimal Upgrading, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.168, May 16-18, 1994
• 22: Bhavani Thuraisingham, Data mining, national security, privacy and civil liberties, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.1-5, December 2002 [doi>10.1145/772862.772863]
• 23: M. B. Thuraisingham, Mandatory security in object-oriented database systems, Conference proceedings on Object-oriented programming systems, languages and applications, p.203-210, October 02-06, 1989, New Orleans, Louisiana, United States
• 24: B. Thuraisingham. Recursion theoretic properties of the inference problem. In the IEEE Third Computer Security Foundations Workshop, 1990.
• 25: M. B. Thuraisingham, Towards the design of a secure data/knowledge base management system, Data & Knowledge Engineering, v.5 n.1, p.59-72, March 1990 [doi>10.1016/0169-023X(90)90033-A]
• 26: Bhavani M. Thuraisingham, The Use of Conceptual Structures for Handling the Inference Problem, Results of the IFIP WG 11.3 Workshop on Database Security V: Status and Prospects, p.333-362, November 01, 1991
• 27: J. H. Van Lint, Introduction to Coding Theory, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 28: R. Yi , K. Levitt, Data Level Inference Detection in Database Systems, Proceedings of the 11th IEEE Computer Security Foundations Workshop, p.179, June 09-11, 1998