Journal of Computer Security

A network of computers is vulnerable to the cascading problem when data of a security level d can be passed to a user with a lower security clearance u elsewhere on the network, without having to defeat any single component of the system that has an accreditation range great enough to allow users of level u and data of level d on a single system. An algorithm of time complexity order O ( an 3 ) and space complexity O ( an 2 ) is given to solve the cascade detection problem, where a is the number of security levels for data, and n is the number of nodes in the network. Also, the cascade correction problem, to remove all cascading paths from a network for a given cost, under restrictive conditions is shown to be NP-complete.

We analyze the DEC fuzzy time technique (Hu [HU]) for both a single computer system and a network of hosts. Specifically, we investigate covert channels in a model of a fuzzy time system and in a network model of n fuzzy time hosts and one nonfuzzy time host. The fuzzy time operating system model predicts a covert channel with a datarate of roughly 50 bits per second, given a mean time between upticks of 20 milliseconds as in the VAX security kernel. We suggest several countermeasures including scheduler redesign which will close or reduce the channels that we analyze.

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