Achieving stricter correctness requirements in multilevel secure databases: The dynamic case

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. One such commercially available high assurance multilevel secure DBMS is the Trusted Oracle DBMS. The multiversion concurrency control protocol that has been implemented in this system guarantees level-wise serializability, a notion of correctness weaker than one-copy serializability. In this paper, we demonstrate how pairwise serializability and one-copy serializability, stricter notions of correctness than level-wise serializability, can be achieved using Trusted Oracle, while making no modification to the underlying concurrency control protocol. Therefore, in this paper, we do not propose a new concurrency control protocol, but propose algorithms, if used on top of Trusted Oracle, generate pairwise or one-copy serializable histories. Our approach requires predeclaration of data items each transaction is going to access since recognizing conflicts among transactions based on examining the read- and write-sets of transactions, is the basis for achieving our objective. All the protocols proposed in this paper to achieve stricter correctness criteria are secure and implementable with untrusted code.