SINTRA Publications

1994

Unlike previous approaches to developing a trusted database system, the replicated architecture approach provides access control at a high level of assurance through replication of data and operations. We present a model of the SINTRA replicated architecture trusted database system which shows how the logical (users') view of the system and its security policy is translated into the physical structure and operations of the SINTRA system. We formalize the intended security policy for replicated architecture and demonstrate that a high level of assurance can be obtained solely from replication with virtually no change to the sturcture of the underlying database systems or the security kernel.

Relational database systems are based on a powerful abstraction: the relational data model with the relational algebra and update semantics. If the database design (i. e., the way the data is organized) satisfies criteria provided by this foundation, users have assurance that they can retrieve information in a consistent, predictable way. Multilevel secure database systems must not only provide assurance that information is protected based on its sensitivity, but should be based on a data model as sound and complete as the conventional relational model. In this paper, we present a data model with a relational algebra and update semantics for a multilevel secure database system whose protection mechanisms are provided by the replicated architecture. The approach is to systematically describe the effects of treating security labels as data and to define explicitly the semantics of these data labels for relational database operations. We also briefly compare the SINTRA data model to earlier ones from the SeaView project and their derivations.

Current projects to provide MLS computing services rarely seem to exploit advances in related fields. Specifically, the concepts of data distribution, replication, and interoperation are currently receiving much attention in the commercial database system sector but have yet to be applied to the delivery of MLS computing services. This paper explains how these concepts might be applied to help deliver MLS computing services relatively quickly and cheaply, and how they can ease integration of legacy systems and new technology into future MLS cooperative, distributed computing environments.

There are many known approaches for multilevel secure database systems. Since protection and assurance are the primary concerns in MLS databases, performance has often been sacrificed. Motivated by performance concerns, a replicated architecture approach which uses a physically distinct backend database management system for each security level is being investigated. This is a report on the behavior and performance issues for the replicated architecture approach. Especially, we compare the performance of the Secure INformation Through Replicated Architecture (SINTRA) MLS database system to that of a typical conventional (non-secure, single-level) database system. After observing the performance bottlenecks for the SINTRA, we present solutions that can alleviate them.

The database multiple-query optimization can be achieved by analyzing multiple-query sequences at a level below that used by current optimizers, but above the low-level executable code. In this paper, the concept of the "algorithm-level" representation of a database program is defined and optimization techniques that can be applied to the algorithm-level representation are discussed. Some techniques extend existing concepts, while others are new. In this paper, we also show multiple-query optimization can be performed across the update queries.

There are several proposed approaches for multilevel secure (MLS) database systems which protect classified information. The SINTRA (Secure INformation Through Replicated Architecture) database system, which is currently being prototyped at the Naval Research Laboratory, is a multilevel trusted database system based on a replicated data approach. This approach uses physical separation of classified data as a protection measure. Each database contains data at a given security level and replicas of all data at lower security levels. Project goals include good performance and full database capability. For practical reasons (e.g., ease of evaluation, portability) the SINTRA database system uses as many readily-available commercial components as possible. In this paper, security constraints and the rationale for the SINTRA prototype are described. We also present the structure and function of each component of the SINTRA prototype: the global scheduler, the query preprocessor, and the user interface. A brief description of the SINTRA recovery mechanism is also presented.

The expressiveness of the data model has a significant impact on the functionality of the resulting database system. The more general the data model, the less need be lost when the conceptual model is mapped onto a particular data model. In this paper, we explain how MLS data models can lead to a loss of database functionality or the inability to model some real world phenomena if data models are not kept general and independent of other considerations. We also present our positions with respect to developing MLS data models for MLS database systems using the object modeling technique (OMT).

We present a mechanism for communication from low to high security classes that allows partial acknowledgments and flow control without introducing covert channels. By restricting our mechanism to the problem of maintaining mutual consistency in replicated architecture database systems, we overcome the negative general results in this problem area. A queueing theory model shows that big buffers can be practical mechanisms for real database systems.

1993

In most models of trusted database systems, transactions are considered to be single-level subjects. As a consequence, users are denied the ability to execute some transactions that can be run on conventional (untrusted) database systems, namely those that perform functions that become inherently multilevel in the MLS environment. This paper introduces a notion of multilevel transaction and proceeds to an algorithm for their concurrent execution. The algorithm is proven to be correct in the sense that resulting schedule for executing the multilevel transactions is one-copy serializable.

"Design Documentation for the SINTRA Global Scheduler," NRL Memorandum Report #5542-93-7362, June 30, 1993. PostScript

In this report, we present the detailed description of the Secure Information Through Replicated Architecture (SINTRA) global scheduler. The detailed description includes: (1) the replica control algorithm, (2) design descriptions, and (3) rational behind our decision to choose specific methodology, an implementation language, and software engineering principles.

A new transaction model for multilevel-secure databases which use the replicated architecture is presented. A basic concurrency control algorithm and two variations are given based on this transaction model. We also present new correctness criteria for multilevel-secure databases which use the replicated architecture. Based on this criteria, we prove that our algorithms are correct.

Communication from a low- to a high-level system without acknowledgements will be unreliable; with acknowledgements, it can be insecure. We propose to provide quantifiable security, acceptable reliability, and minimal performance penalties by interposing a device (called the Pump) to push messages to the high system and provide a controlled stream of acknowledgements to the low system.

This paper describes how the Pump supports the transmission of messages upward and limits the capacity of the covert timing channel in the acknowledgement stream without affecting the average acknowledgement delay seen by the low system or the message delivery delay seen by the high system in the absence of actual Trojan horses. By adding random delays to the acknowledgment stream when the Pump's message buffer is full, we show how to further reduce the covert channel capacity even in the presence of cooperating Trojan horses in both the high and low systems. We also discuss engineering tradeoffs relevant to practical use of the Pump.

This volume contains the papers presented at the Sixth IFIP WG11.3 Working Conference on Database Security, as revised by the authors following presentation, together with an account of the discussions held during the meeting and the IFIP WG11.3 Research Questions List. Papers presented covered a wide range of topics in database security including the semantics of multilevel database applications, security policies and models, the inference problem, and multilevel database concurrency control.

The concurrency control lock (e.g. file lock, table lock) has long been used as a canonical example of a covert channel in a database system. Locking is a fundamental concurrency control technique used in many kinds of computer systems beside database systems. Locking is generally considered to be interfering and hence unsuitable for multilevel systems. In this paper we show how such locks can be used for concurrency control, without introducing covert channels.

The most critical problem with associated with implementing replicated architecture multilevel-secure database systems is transaction management: concurrency control, mutual consistency of replicas, and atomic recovery from failures, under the constraints of multilevel security. This paper investigates and compares the performance of five of the most promising transaction management approaches, via analytic performance modeling. We find that all five have acceptable performance and, over a wide range of circumstances, can be chosen based on structural considerations rather than performance.

1992

Replicated architecture has been proposed as a way to obtain acceptable performance in a multilevel secure database system. This architecture contains a separate database for each security level such that each contains replicated data from lower security classes. The consistency of the values of replicated data items must be maintained without unnecessarily interfering with concurrency of database operations. This paper provides a protocol to do this that is secure, since it is free of covert channels, and also ensures one-copy serializability of executing transactions. The protocol can be implemented with untrusted processes for both concurrency and recovery.

A user of a database management system has an intuitive idea of a transaction as a sequence of database commands that he or she submits. The user expects this sequence of commands to be executed in the order of submission, without interference from other database commands submitted by other users. Techniques for doing this while concurrently supporting multiple database users are well known for conventional (i.e., not multilevel) database systems. Most of the transaction management theory for multilevel secure database systems has been developed for transactions that act within a single security class. In this paper, we look at transactions that act across security classes, that is, the transaction is a multilevel sequence of database commands, which more closely resemble user expectations. We then give an algorithm for controlling concurrent execution of these transactions on a particular multilevel secure database architecture.

A new transaction model for multilevel-secure databases which use the replicated architecture is presented. A basic concurrency control algorithm and two variations are given based on this transaction model. We also present new correctness criteria for multilevel-secure databases which use the replicated architecture. Based on this criteria, we prove that our algorithms are correct.

There are two components in the scheduler for multilevel-secure databases which use the replicated architecture; global and local schedulers. Since the global scheduler, which enforces data consistency among replicas, has to make scheduling decisions based on transactions (i.e., without any knowledge of actual data or physical layout of data), an accurate analysis technique which can detect conflicts among queries is needed. The data dependence analysis introduced here provides a method for precisely determining whether the portions of relations affected by various database operations overlap without the knowledge of actual data.

The concurrency control lock (e.g. file lock, table lock) has long been used as a canonical example of a covert channel in a database system. Locking is a fundamental concurrency control technique used in many kinds of computer systems beside database systems. Locking is generally considered to be interfering and hence unsuitable for multilevel systems. In this paper we show how such locks can be used for concurrency control, without introducing covert channels.

1991

The replicated architecture for multilevel secure database systems provides security by replicating data into separate untrusted single-level database systems. To be successful, a system using the replicated architecture must have a concurrency and replica control algorithm that does not introduce any covert channels. Jajodia and Kogan have developed one such algorithm that uses update projections and a write-all replica control algorithm. The new algorithm uses replicated transactions, and a set of queues organized according to security class. A new definition of correctness is require for this approach, so we present one and use it to show that our algorithm is correct. The existence of this new algorithm increases the viability of the replicated architecture as an alternative to kernelized approaches.

Privacy Policy