CORRECTNESS CRITERIA FOR MULTILEVEL SECURE TRANSACTIONS

The benefits of distributed systems and shared database resources are widely recognized, but they often cannot be exploited by users who mus t protect their data by using label-based access controls. In particul ar, users of label-based data need to read and write data at different security levels within a single database transaction, which is not cu rrently possible without violating multilevel security constraints. Th is paper presents a formal model of multilevel transactions which prov ide this capability. We define four ACIS (atomicity, consistency, isol ation, and security) correctness properties of multilevel transactions . While atomicity, consistency and isolation are mutually achievable i n standard single-site and distributed transactions, we show that the security requirements of multilevel transactions conflict with some of these goals. This forces trade-offs to be made among the ACIS correct ness properties, and we define appropriate partial correctness propert ies. Due to such trade-offs, an important problem is to design multile vel transaction execution protocols which achieve the greatest possibl e degree of correctness. These protocols must provide a variety of app roaches to making trade-offs according to the differing priorities of various users. We present three transaction execution protocols which achieve a high degree of correctness. These protocols exemplify the co rrectness trade-offs proven in the paper, and offer realistic implemen tation options.