Achieving stricter correctness requirements in multilevel secure database management systems

TY - JOUR

T1 - Achieving stricter correctness requirements in multilevel secure database management systems

AU - Atluri, Vijayalakshmi

AU - Jajodia, Sushil

AU - Bertino, Elisa

PY - 1993

Y1 - 1993

N2 - 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 concurrency 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 levelwise serializability has many desirable properties, it suffers from the inconsistent retrieval problems that may seriously harm database integrity. In this paper, we demonstrate how pairwise 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 concurrency control protocol such that it meets the stricter correctness requirements, we achieve our goal without modifying the Trusted Oracle concurrency control algorithm in any way. In other words, in this paper, we do not propose a new scheduler for concurrency control, but propose algorithms, if used with the Trusted Oracle scheduler, to generate pairwise 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.

AB - 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 concurrency 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 levelwise serializability has many desirable properties, it suffers from the inconsistent retrieval problems that may seriously harm database integrity. In this paper, we demonstrate how pairwise 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 concurrency control protocol such that it meets the stricter correctness requirements, we achieve our goal without modifying the Trusted Oracle concurrency control algorithm in any way. In other words, in this paper, we do not propose a new scheduler for concurrency control, but propose algorithms, if used with the Trusted Oracle scheduler, to generate pairwise 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.

UR - http://www.scopus.com/inward/record.url?scp=84974765219&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974765219&partnerID=8YFLogxK

U2 - https://doi.org/10.3233/JCS-1993-2404

DO - https://doi.org/10.3233/JCS-1993-2404

M3 - Article

SN - 0926-227X

VL - 2

SP - 311

EP - 351

JO - Journal of Computer Security

JF - Journal of Computer Security

IS - 4

ER -