Foundational Results

Security is a state of well-being for information and infrastructure. In a secure system, the risk of successful yet undetected theft, tampering, or disruption of information and services is kept low or acceptable.

A security policy is a rule that divides all possible system states into two sets: authorized (secure) and unauthorized (nonsecure). A secure system must start in an authorized state and never transition into an unauthorized one. A breach happens when the system enters an unauthorized state.

The CIA triad captures three core security goals. For a set of entities X and some information or resource I:

Design Principles

These principles help build secure systems:

• Simplicity – Simpler systems are easier to reason about and have fewer bugs
• Open Design – Security should not rely on obscurity; assume attackers know the design
• Compartmentalization – Limit blast radius by isolating components
• Least Privilege – Grant only the minimum access needed for each task
• Fail-Safe Defaults – Default to deny; require explicit allowance
• Complete Mediation – Check every access, not just some
• No Single Point of Failure – Redundancy so one failure does not compromise the whole system

A security model formalizes a policy so we can analyze it. Below are common access control types and classic models.

Access Control Types

• DAC (Discretionary) – The user decides who can access their objects. Example: file permissions you set.
• MAC (Mandatory) – The system enforces rules; users cannot change them. Example: military classification levels.
• ORCON (Originator-Controlled) – Only the creator of the object controls who can access it.

Bell-LaPadula (Confidentiality)

This model protects against information leakage in systems with security levels (e.g., military: Unclassified, Secret, Top Secret). Each subject has a clearance; each object has a classification. A subject dominates an object if the subject’s clearance is at least as high as the object’s classification.

• Simple Security Condition – A subject can read an object only if the subject dominates the object (no “read up”).
• *-Property (Star Property) – A subject can write to an object only if the object dominates the subject (no “write down”). This prevents high-level data from flowing to low-level objects.

Biba (Integrity)

Biba addresses integrity (trustworthiness of data), the dual of confidentiality. Integrity levels prevent low-integrity data from corrupting high-integrity data.

• Strict Integrity – Read only from objects of equal or higher integrity; write only to objects of equal or lower integrity.
• Low-Water-Mark – When you read from a lower-integrity object, your integrity drops (your “water mark” goes down).
• Ring Policy – Allows any read; restricts writes by integrity level.

Chinese Wall & RBAC

• Chinese Wall – For conflict-of-interest (e.g., consultants). Once you access Company A’s data, you cannot access Company B’s (competitor) data. Prevents insider trading and conflicts.
• RBAC (Role-Based Access Control) – Access is granted by role (e.g., Manager, Developer), not by individual. Users assume roles; each role has authorized transactions. Simplifies management in large organizations.

The access control matrix is a formal model of who can do what. We have:

• S (Subjects) – Active entities (users, processes) that request access
• O (Objects) – Resources being protected (files, memory, devices)
• A[s, o] – The set of rights that subject s has on object o (e.g., read, write, execute)

Commands update the matrix (e.g., create object, grant right). Two special rights:

• Copy (or Grant) – Allows the possessor to give rights they have to others
• Own – Allows adding or revoking rights for that object
• Attenuation of privilege – You cannot grant a right you do not have yourself

A natural question: Is there an algorithm that can tell us if a given system is secure? This reduces to the safety problem: Can a particular right r ever be leaked (granted to an unauthorized subject)?

Through a reduction from the Halting Problem (which is known to be undecidable), we can prove that the safety problem is undecidable for general protection systems. No algorithm can correctly answer this for all systems. For restricted systems (e.g., where each command does only one primitive operation), safety becomes decidable.