We present a method for verifying information flow properties of software programs using inductive assertions and theorem proving. Given a program annotated with information flow assertions at cutpoints, the method uses a theorem prover and operational semantics to generate and discharge verification conditions. This obviates the need to develop a verification condition generator (VCG) or a customized logic for information flow properties. The method is compositional: a subroutine needs to be analyzed once, rather than at each call site. The method is being mechanized in the ACL2 theorem prover, and we discuss initial results demonstrating its applicability.

Achieving interactive consistency among processors in the presence of faults is an important problem in fault tolerant computing, first cleanly formulated by L. Lamport, R. Pease, and M. Shostak (1980; 1982) and solved in selected cases with their Oral Messages (OM) algorithm. Several machine supported verifications of this algorithm have been presented, including a particularly elegant formulation and proof by John Rushby using EHDM and PVS (S. Owre et al., 1992, 1995; J. Rushby, 1992). Rushby proposes interactive consistency as a benchmark problem for specification and verification systems. We present a formalization of the OM algorithm in the ACL2 logic and compare our formalization and proof to his. We draw some conclusions concerning the range of desirable features for verification systems. In particular, while higher order functions, strong typing, lambda abstraction, and full quantification have some value they come with a cost; moreover, many uses of such features can be easily translated into simpler logical constructs, which facilitate more automated proof discovery. We offer a cautionary note about comparing systems with respect to a small set of problems in a limited domain.

A communication policy is a specification for permitted communication among system agents. A system exhibits noninterference with respect to a policy if every agent is insensitive to the presence of agents with which it may not communicate. A communication policy specifies the presence or absence of communication between agents, but it does not specify how permitted communication may occur. In this paper we present a refinement of a communication policy, which we call a connection policy. A connection policy specifies the channels along which permitted communication may occur. A system observes controlled interference when its connection policy is satisfied. When a connection policy is consistent with a communication policy, controlled interference guarantees noninterference. We discuss Rushby's notion of separation. In light of controlled interference, and briefly relate controlled interference to type enforcement. The formalization of the controlled interference theory is built on the state-based formulation of noninterference previously developed by two of the authors. A theme of this paper is that a state-based approach to these issues is simple and useful.

We outline an approach to modeling noninterference-style security policies using a state-based model, as opposed to an event-based or i/o-based model. We believe that this approach provides a richer, more intuitive formalism for security modeling tha

We outline an alternative approach to modeling noninterference-style security policies using a state-based model (as opposed to an event-based or i/o-based model). We believe that this approach provides a richer, more intuitive formalism for security modeling than the event-based approach and provides a link to other current research in specification and verification of concurrent and distributed systems. We describe the state-based approach for deterministic and non-deterministic systems with both transitive and intransitive security policies.>

Current verification technology provides tools for the verification of programs written in a high-level language. Even verified high-level programs may not satisfy their specifications when executed, due to errors in tower-level software and hardware. We discuss an attempt at eliminating this problem with the design of an execution environment consisting of a compiler, operating system, and processor, each of which has been mechanically verified.

One criterion for "Beyond Al" certification according to the DoD Trusted Computer Systems Evaluation Criteria will be code-level verification. We argue that, while verification at the actual code level may be infeasible for large secure systems, it is possible to push the verification to a low level of abstraction and then map the specification in an intuitive manner to the source code. Providing a suitable mapping requires adhering to a strict discipline on both the specification and code sides. We discuss the issues involved in this problem, particularizing the discussion to a mapping from Gypsy specifications to C code.

This paper examines the application of two covert channel analysis techniques to a high level design for a real system, the Honeywell Secure Ada® Target (SAT). The techniques used were a version of the noninterference model of multilevel security due to Goguen and Meseguer and the shared resource matrix method of Kemmerer. Both techniques were applied to the Gypsy Abstract Model of the SAT. The paper discusses the application of the techniques and the nature of the covert channels discovered. The relative strengths and weaknesses of the two methods are discussed and criteria for an ideal covert channel tool are developed.

A noninterference formulation of MLS applicable to the Secure Ada® Target (SAT) Abstract Model is developed. An analogous formulation is developed to handle the SAT type enforcement policy. Unwinding theorems are presented for both MLS and Multidomain Security (MDS) and the SAT Abstract Model is shown to satisfy both MLS and MDS. Generalizations and extensions are also considered.

This paper examines the application of two covert channel analysis techniques to a high level design for a real system the Honeywell Secure Ada Target (SAT). The techniques used were a version of the non-interference model of multilevel security due to Goguen and Meseguer and the shared resource matrix method of Kemmerer. Both techniques were applied to the Gypsy abstract model of the SAT. The paper discusses the application of the techniques and the nature of the covert channels discovered. The relative strengths and weaknesses of the two methods are discussed and criteria for an ideal covert channel tool are developed.

A non-interference formulation ofMLS applicable to the Secure Ada Target (SAT) Abstract Model is developed. An analogous formulation is developed to handle the SAT type enforcement policy. Unwinding theorems are presented for both MLS and Multi-Domain Security (MDS) and the SAT Abstract Model is shown to satisfy both MLS and MDS. Generalizations and extensions are also considered.

The Secure Ada Target (SAT) machine is designed to meet or exceed the DoD requirements for multi-level secure systems. This paper describes the require-ments on such designs, our approach to meeting these requirements by introducing tagged objects, and a specialized tagged object processor (TOP) that handles all operations involving tagged objects. Basic system security is achieved using a small software kernel and the TOP. The structure of our proofs, such that the system satisfies appropriate security properties, will be outlined. Brief remarks concerning the implementation of user Ada programs on the SAT system conclude the paper. Our design approach is largely independent of CPU selection, though implementation details necessarily depend on the processor selection.