An efficient multiversion algorithm for secure servicing of transaction reads

ABSTRACT

We propose an efficient multiversion algorithm for servicing read requests in secure multilevel databases. Rather than keep an arbitrary number of versions of a datum, as standard multiversion algorithms do, the algorithm presented here maintains only a small fixed number of versions—up to three—for a modified datum. Each version corresponds to the state of the datum at the end of an externally defined version period. The algorithm avoids both covert channels and starvation of high transactions, and applies to security structures that are arbitrary partial orders. The algorithm also offers long-read transactions at any security level conflict-free access to a consistent, though slightly dated, view of any authorized portion of the database. We derive constraints sufficient to guarantee one-copy serializability of executions histories, and then exhibit an algorithm that satisfies these constraints.

REFERENCES

• AJ93: Paul Ammann , Sushil Jajodia, Distributed timestamp generation in planar lattice networks, ACM Transactions on Computer Systems (TOCS), v.11 n.3, p.205-225, Aug. 1993 [doi>10.1145/152864.152865]
• AJF93: Paul Ammann, Sushil Jajodia, and Phyllis Frankl. Globally consistent event ordering in one-directional distributed environments. Technical Report ISSE-TR-93-104, George Mason University, Fairfax, VA 22030, August 1993.
• AJJ92: Paul Ammann , Frank Jacckle , Sushi Jajodia, A Two Snapshot Algorithm for Concurrency Control in Multi-Level Secure Databases, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.204, May 04-06, 1992
• BHG87: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• BL76: D.E. Bell and L.J. LaPadula. Secure computer systems: Unified exposition and multics interpretation. Technical Report MTI't- 2997, The Mitre Corporation, Bedford, MA, March 1976.
• CK93: Oliver Costich , Myong H. Kang, Maintaining Multilevel Transaction Atomicity in MLS Database Systems with Replicated Architecture, Proceedings of the IFIP WG11.3 Working Conference on Database Security VII, p.329-355, September 12-15, 1993
• CM92: James W. Gray, III , Paul F. Syverson, A Multilevel Transaction Problem for Multilevel Secure Database Systems and Its Solution for the Replicated Architecture, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.192, May 04-06, 1992
• Com83: Committee on Multilevel Data Management Security, Air Force Studies Board, National Research Council, Washington, DC. Multilevel Data Management Security, 1983.
• Cos92: Oliver Costich, Transaction Processing Using an Untrusted Scheduler in a Multilevel Database with Replicated Architecture, Results of the IFIP WG 11.3 Workshop on Database Security V: Status and Prospects, p.173-189, November 01, 1991
• Den82: Dorothy Elizabeth Rob Denning, Cryptography and Data Security, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• DoD85: DoD Computer Security Center. Trusted Computer System Evaluation Criteria, December 1985. DoD 5200.28-STD.
• FM89: Judy Froscher and Cathy Meadows. Achieving a trusted database management system using parallelism. In C. Landwehr and S. Jajodia, editors, Database Security II: Status and Prospects, pages 151-160. North Holland, 1989.
• HC86: Meichun Hsu , Arvola Chan, Partitioned two-phase locking, ACM Transactions on Database Systems (TODS), v.11 n.4, p.431-446, Dec. 1986 [doi>10.1145/7239.7477]
• Jae92: Frank Jaeckle. A two snapshot algorithm for concurrency control in secure multi-level databases. Master's thesis, George Mason University, 1992.
• JK90: Sushil J ajodia and Boris Kogan. Transaction processing in multilevel-secure databases using replicated architecture. In Proceedings of the Symposium on Research in Security and Privacy, Oakland, CA, May 1990.
• KJ90: Boris Kogan , S. Jajodia, Concurrency control in multilevel-secure databases based on replicated architecture, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.153-162, May 23-26, 1990, Atlantic City, New Jersey, United States
• KK92: Iwen E. Kang , Thomas F. Keefe, On Transaction Processing for Multilevel Secure Replicated Databases, Proceedings of the Second European Symposium on Research in Computer Security, p.329-348, November 23-25, 1992
• KT90: T.F. Keefe and W.T. Tsai. Multiversion concurrency control for multilevel secure database systems. In Proceedings of the Symposium on Research in Security and Privacy, pages 369-383, Oakland, CA, May 1990.
• Mav93: Padmaja Mavuluri. On the fly reading of entire databases. Master's thesis, George Mason University, 1993.
• McD93: John Pierce McDermott, III, Transaction management in replicated-architecture multilevel-secure database systems, George Mason University, Fairfax, VA, 1994
• MJS91: John McDermott, Sushil Jajodia, and Ravi Sandhu. A single-level scheduler for the replicated architecture for multilevel-secure databases. In Seventh Annual Computer Security Application Conference, pages 2- 11, San Antonio, TX, December 1991.
• MPL92: C. Mohan , Hamid Pirahesh , Raymond Lorie, Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.124-133, June 02-05, 1992, San Diego, California, United States
• PMC+92: Hamid Pirahesh , C. Mohan , Josephine Cheng , T. S. Liu , Pat Selinger, Parallelism in relational data base systems: architectural issues and design approaches, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.4-29, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319060]
• Pu86: Calton Pu. On-the-fly, incremental, consistent reading of entire databases. Algorithmica, 1(3):271-287, October 1986.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

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

General Terms:
Algorithms, Theory