Belief reasoning in MLS deductive databases

ABSTRACT

It is envisaged that the application of the multilevel security (MLS) scheme will enhance flexibility and effectiveness of authorization policies in shared enterprise databases and will replace cumbersome authorization enforcement practices through complicated view definitions on a per user basis. However, as advances in this area are being made and ideas crystallized, the concomitant weaknesses of the MLS databases are also surfacing. We insist that the critical problem with the current model is that the belief at a higher security level is cluttered with irrelevant or inconsistent data as no mechanism for attenuation is supported. Critics also argue that it is imperative for MLS database users to theorize about the belief of others, perhaps at different security levels, an apparatus that is currently missing and the absence of which is seriously felt. The impetus for our current research is this need to provide an adequate framework for belief reasoning in MLS databases. We demonstrate that a prudent application of the concept of inheritance in a deductive database setting will help capture the notion of declarative belief and belief reasoning in MLS databases in an elegant way. To this end, we develop a function to compute belief in multiple modes which can be used to reason about the beliefs of other users. We strive to develop a poised and practical logical characterization of MLS databases for the first time based on the inherently difficult concept of non-monotonic inheritance. We present an extension of the acclaimed Datalog language, called the MultiLog, and show that Datalog is a special case of our language. We also suggest an implementation scheme for MultiLog as a front-end for CORAL.

REFERENCES

• 1: D. E. Bell and L. J. La Padula. Secure computer systems: Unified exposition and multics interpretation. Technical Report ESD-TR-75-.306, The MITRE Corporation, Bedford, MA, March 1976.
• 2: Piero A. Bonatti , Sarit Kraus , V. s. Subrahmanian, Foundations of Secure Deductive Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.406-422, June 1995 [doi>10.1109/69.390247]
• 3: M. Bugliesi. A declarative view of inheritance in logic programming, in K. Apt, editor, Proc. Joint Int. Conference and Symposium on Logic Programming, pages 113-130. The MIT Press, 1992.
• 4: Michele Bugliesi , Hasan M. Jamil, A Logic for Encapsulation in Object Oriented Languages, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.215-229, September 14-16, 1994
• 5: Michele Bugliesi , Hasan M. Jamil, A Stable Model Semantics for Behavioral Inheritance in Deductive Object Oriented Languages, Proceedings of the 5th International Conference on Database Theory, p.222-237, January 11-13, 1995
• 6: K. Selçuk Candan , Sushil Jajodia , V. S. Subrahmanian, Secure Mediated Databases, Proceedings of the Twelfth International Conference on Data Engineering, p.28-37, February 26-March 01, 1996
• 7: Frédéric Cuppens, Querying a Multilevel Database: A Logical Analysis, Proceedings of the 22th International Conference on Very Large Data Bases, p.484-494, September 03-06, 1996
• 8: D. E. Denning, T. F. Lunt, R. R. Schell, M. Heckman, and W. R. Shockley. A multilevel relational data model. In Proc. of the IEEE Symposium on Security and Privacy, pages 220-234. IEEE Computer Society Press, 1987.
• 9: D. Chimenti , R. Gamboa , R. Krishnamurthy , S. Naqvi , S. Tsur , C. Zaniolo, The LDL System Prototype, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.76-90, March 1990 [doi>10.1109/69.50907]
• 10: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian, A Logical Language for Expressing Authorizations, Proceedings of the 1997 IEEE Symposium on Security and Privacy, p.31, May 04-07, 1997
• 11: Sushil Jajodia , Pierangela Samarati , V. S. Subrahmanian , Eliza Bertino, A unified framework for enforcing multiple access control policies, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.474-485, May 11-15, 1997, Tucson, Arizona, United States
• 12: Sushil Jajodia , Ravi Sandhu, Toward a multilevel secure relational data model, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.50-59, May 29-31, 1991, Denver, Colorado, United States
• 13: Hasan M. Jamil, Implementing Abstract Objects with Inheritance in Datalogneg, Proceedings of the 23rd International Conference on Very Large Data Bases, p.56-65, August 25-29, 1997
• 14: H. M. Jamil. A logical foundation for mls deductive databases. Technical report, Department of Computer Science, Mississippi State University, USA, November 1998. Submitted for publication.
• 15: H. M. Jamil and L. V. S. Lakshmanan. A :leclarative semantics for behavioral inheritance and conflict resolution. In John Lloyd, editor, Proceedings of the 12th International Logic Programming Symposium, pages 130-}{44, Portland, Oregon, December 1995. MIT Press.
• 16: Nenad A. Jukic , Susan V. Vrbsky, Asserting beliefs in MLS relational models, ACM SIGMOD Record, v.26 n.3, p.30-35, Sept. 1997 [doi>10.1145/262762.262767]
• 17: V. Kessler and G. Wedel. Autlog- an advanced logic: of authentication. Manuscript.
• 18: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 19: T. F. Lunt , D. E. Denning , R. R. Schell , M. Heckman , W. R. Shockley, The SeaView Security Model, IEEE Transactions on Software Engineering, v.16 n.6, p.593-607, June 1990 [doi>10.1109/32.55088]
• 20: Dale Miller, A logical analysis of modules in logic programming, Journal of Logic Programming, v.6 n.1-2, p.79-108, Jan./Mar. 1989 [doi>10.1016/0743-1066(89)90031-9]
• 21: L. Monteiro and A. Porto. Contextual Logic Programruing. In 6th ALP Intl. Conf. on Logic Pr~,ramming, 1989.
• 22: G. Pernul, W. Winiwarter, and A. M. Tj()a. The deductive filter approach to mls database proto~:yping, in Proc. of the 9th Annual Computer Security A~plications Conference, Orlando, FL, December 1993.
• 23: Günther Pernul , Werner Winiwarter , A. Min Tjoa, The Entity-Relationship Model for Multilevel Security, Proceedings of the 12th International Conference on the Entity-Relationship Approach: Entity-Relationship Approach, p.166-177, December 15-17, 1993
• 24: Kenneth Smith , Marianne Winslett, Entity Modeling in the MLS Relational Model, Proceedings of the 18th International Conference on Very Large Data Bases, p.199-210, August 23-27, 1992
• 25: A Spalka. Fundamental forms of confiden;iality in deductive databases. Manuscript.
• 26: W. Winiwarter. Why is deduction required for database systems ? - some case studies. In Proc. of the ~nd Data Engineering Forum, Tokyo, Japan, November 1995.
• 27: Marianne Winslett , Kenneth Smith , Xiaolei Qian, Formal query languages for secure relational databases, ACM Transactions on Database Systems (TODS), v.19 n.4, p.626-662, Dec. 1994 [doi>10.1145/195664.195675]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: CORAL

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Datalog
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design, Languages, Management, Performance, Theory, Verification

Keywords:
MLS database, beleif assertion, deductive databases, inheritance and overriding, reasoning