Note: [1] An earlier version of this paper appeared in IEEE Symposium on Security and Privacy, Oakland, CA, May 1996, pp. 74–84.
Note: [2] The work of Sushil Jajodia and Indrakshi Ray was partially supported by National Security Agency under grants MDA904-96-1-0103 and MDA904-96-1-0104 and by US Air Force/Rome Labs under grant F30602-97-1-0139. The work of Indrakshi Ray was also partially supported by a George Mason University Fellowship Award.
Note: [3] The work of Paul Ammann was partially supported by US Air Force/Rome Labs under grants F30602-97-1-0139.
Abstract: Multilevel transactions have been proposed for multilevel secure databases; in contrast to most proposals, such transactions allow users to read and write across multiple security levels. The security requirement that no high level operation influence a low level operation often conflicts with the atomicity requirement of the standard transaction processing model. In particular, others have shown that no concurrency control algorithm based on the standard transaction processing model can guarantee both atomicity and security. This conflict motivates us to propose an alternative semantic-based transaction processing model for multilevel transactions. Our model uses the semantics of the application to analyze an application and reason about its behavior. Our notion of correctness is based on semantic correctness instead of serializability as in the standard transaction processing model. Semantic correctness ensures that database consistency is maintained, transactions output consistent data, and all partially executed transactions complete. We show how an example application can be analyzed to assure semantic correctness and how this analysis can be automated. We also propose a simple timestamp-based multiversion concurrency control algorithm for transaction processing on a kernelized architecture. The advantages of our model over the standard transaction processing model are that atomicity can be assessed, and for some applications ensured via off line analysis, more concurrency is achieved, lesser synchronization between security levels is required, and a larger class of multilevel transactions can be processed.
