Affiliations: Center For Secure Information Systems, Department of Information and Software Systems Engineering, George Mason University, Fairfax, VA 22030, USA
Note: [*] The work of Paul Ammann was partially supported by the National Science Foundation under grant CCR-9202270.
Note: [†] The work of S. Jajodia was partially supported by a grant from ARPA, administered by the Office of Naval Research under grant number N0014-92-J-4038, by National Science Foundation under grant number IRI-9303416, and National Security Agency under contract number MDA904-94-C-611B.
Abstract: We offer a concurrency conirol algorithm for replicated, secure, multilevel databases. We compare the algorithm with a multiversion approach and with the typical full-replication approach. In the full-replication approach, each security level maintains a container that holds a complete copy of data at lower security levels. In the approach described here, access to data at lower security levels is through shared, read-only snapshots, where a constant number of snapshots at each level – two, as it turns out – is sufficient. We derive necessary properties for snapshots, give a switching algorithm to assign read-downs to snapshots, specify a snapshot creation algorithm, demonstrate that the approach is free of indirect channels and starvation, and prove one-copy serializability on execution histories. In contrast to some comparable algorithms, our algorithm is correct for any security structure that is a partial order.
