Affiliations: [a] Center for Secure Information Systems and Department of Information and Software Systems Engineering, George Mason University, Fairfax, VA 22030-4444, U.S.A. | [b] Dipartimento di Scienze dell'Informazione, Universita degli Studi di Milano, Via Comelico 39/41, 20135 Milano, Italy
Note: [*] A preliminary version of this paper appeared in the Proceedings of IEEE Symposium on Research in Security and Privacy, Oakland, California, May 1993. This work was supported in part by the National Science Foundation under grant number IRI-9303416 and by a DARPA grant, administered by the Office of Naval Research under grant number N0014-92-J-4038.
Abstract: Although high assurance multilevel secure database management systems (DBMSs) are slowly becoming commercially available, these systems have yet to offer a concurrency control protocol that is free of signaling channels and produces serializable (one-copy serializable when multiple versions of data are maintained) histories. In this paper, we consider the multiversion con currency control algorithm that has been implemented in the Trusted Oracle DBMS. It guarantees levelwise serializability, which is a weaker notion of correctness than one-copy serializability. While level wise serializability has many desirable properties, it suffers from the inconsistent retrieval problems that may seriously harm database integrity. In this paper, we demonstrate how pair wise serializability and one-copy serializability, stricter correctness criteria than levelwise serializability, can be achieved, using the Trusted Oracle scheduler. It is important to note that rather than taking the usual approach of modifying the underlying con currency control protocol such that it meets the stricter correctness requirements, we achieve our goal without modifying the Trusted Oracle con currency control algorithm in any way. In other words, in this paper, we do not propose a new scheduler for con currency control, but propose algorithms, if used with the Trusted Oracle scheduler, to generate pair wise or one-copy serializable histories. Our approach is based on the assumption that all transactions that are running during a certain interval are known in advance. We perform a static analysis of the read- and write-sets of these transactions to recognize conflicts among transactions. The results of the analysis are used to control the order of submission of the transactions in such a way that stricter correctness requirements are met. All the algorithms proposed in this paper are implementable with untrusted code.
