A Covert Channel-Free Validation Algorithm Using Timestamp Order for Multilevel-Secure Optimistic Concurrency Control

摘要

Although multilevel secure optimistic concurrency control (MLS/OCC) is capable of providing much higher parallelism compared to the locking-based scheme, the use of transaction aborts as the main mechanism for maintaining consistency is a serious disadvantage in the sense that it can induce unnecessary aborts problem due to clumsy definition of conflict and starvation problem due to indefinite delay of high-level transactions in order to avoid covert timing channel. From this line, the refinements of MLS/OCC will take a closer look at the following questions: (1) Are timestamps useful to refine validation of transactions in order to reduce the risk of restart among equal-level transactions. (2) Can starvation due to prevention of covert channel be solved in a more elegant way than has been suggested so far?rnIn order to reap the potential advantage of high parallelism and delay-secureness, this sort of unnecessary aborts problem should be alleviated. The basic refinement philosophy for the solution on unnecessary aborts problem is to incorporate the advantage of timestamp ordering into MLS/OCC. To this end, timestamp ordering is employed mainly for transaction validation. In this sense, we call this approach MLS/OTSO. This variant is shown to preserve the security semantics of the MLS/OCC while significantly reducing the cost of its validation phase. We should note at this point that the MLS/OTSO algorithm presents an opportunity for reducing the amount of work wasted by restarted transactions. Write timestamps can be tested when items are read as well as during validation-, thus allowing transactions to detect certain inevitable restarts earlier in their execution. We will pursue this possibility further in MLS/OTSO, although the resulting algorithm would not really be an optimistic one, but we note that this modification may indeed be worth considering for performance reasons.