How hard is it to determine whether or not a given system satisfies a given security policy? What is the most general system that we can prove to be secure (or nonsecure)? This issue determines the level of abstraction at which we can analyze security. If we can prove that a broad class of systems is secure, then we can prove that a model of a system is secure by determining that it falls into that class. More concretely, we can characterize systems that we can prove to be secure.

In what follows, we use a generic security policy to determine under what conditions we can prove systems to be secure. The results are disappointing and incomplete, and current research focuses on tightening them, but this work lays the theoretical foundation for all that follows, and understanding it is critical to understanding the limits of what we can achieve.

This part of the book presents the underpinnings and theoretical foundations of computer security and several key results.

Chapter 2, “Access Control Matrix,” describes a widely used representation of access permissions. The representation is simple enough to capture any access rules and therefore is a useful starting point for deriving theoretical results.

Chapter 3, “Foundational Results,” studies the safety question of when security is decidable. It presents three models: the Harrison-Ruzzo-Ullman model, which looks at arbitrary systems; the Take-Grant Protection Model, which looks at a specific system; and the Schematic Protection Model and its descendents, which look at a specific class of systems.