← all systems · see it in The System
Formal security policy model
A mathematically precise statement of a security policy: it represents the initial state of a system, the way the system moves from one state to another, and a definition of a 'secure' state, supported by a proof that if the system starts secure and the model's assumptions hold, every later state is secure (src:tcsec-1985). The field calls such a scheme for specifying and enforcing security policies a computer security model (src:wp:computer-security-model). Walked as the practice and the structure together: security modellers who take an informal policy (military classification, commercial accounting controls, financial-market walls) and a target system, state 'secure' formally (access-control rules such as Bell-LaPadula's, or pure statements such as noninterference), prove that the rules keep it, map the model onto a real design (Multics, seL4) and hand it to engineers and evaluators (TCSEC classes B2 to A1, Common Criteria EAL6-7).
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Formal security policy model (computer security policy), sys:security-model, Formal security models (reference monitor, Bell-LaPadula) |
| born at | 1972-1973 (MITRE task begun summer 1972; first volume 1973) |
| born precision | about a year |
| boundary | Inside: the model itself (its vocabulary of subjects, objects, access modes and labels or domains and observations; its definition of a secure state or of allowed information flow; its rules or commands for every change of state; its theorems and proofs) and the modelling practice that makes, refines, interprets and proves it (modellers, the formalisms they borrow, proof tools, the interpretation onto a target design). Outside: the informal policy it formalises (military classification, commercial integrity controls, financial regulation), the computer system it describes (Multics, seL4, a cloud authorizer), the mechanisms that enforce it once built (reference monitors, access-control code, data diodes), the attackers and covert channels that test it, and the evaluators and acquirers who rely on it. |
| nested level | Part of computer security's policy-and-models floor and of access control's 'who may do what' floor; the machine sense of 'security policy' (a kind on security policy's shelf). Built from mathematics (set theory, lattices, automata, logic) and borrowed policies; carried into practice by operating-system design and certification. |
| scale | technological |
Measures (17) published science
| characteristic clock: first modelling burst | about 3 (1972 to 1975) years |
| seL4 information-flow proof duration | 21 months |
| seL4 information-flow proof effort | about 51 person-months |
| seL4 information-flow proof size | 27,756 lines of Isabelle/HOL |
| seL4 C code covered | 8,830 lines of C |
| seL4 functional correctness proof effort | about 25 person-years |
| rules in Bell-LaPadula volume II | 10 rules, each proved to preserve the security properties |
| Clark-Wilson rules | 9 (5 certification, 4 enforcement) rules |
| Graham-Denning protection rules | 8 rules |
| covert channel bandwidth counted high (TCSEC guideline) | more than 100 bits per second |
| Cedar authorizer speed against OpenFGA | 28.7-35.2 times faster |
| Cedar authorizer speed against Rego | 42.8-80.8 times faster |
| data diode transfer speed (CC EAL7+ product) | 1-10 Gbit/s |
| minimum analysts for a Chinese Wall (Brewer-Nash theorem T3) | the number of company datasets in the largest conflict-of-interest class (more if analysts choose the same dataset) subjects |
| take-grant safety decision time (specific systems) | linear time complexity |
| birth of the formal model (MITRE task) | summer 1972 date |
| lag from Bell-LaPadula unified exposition to noninterference | about 6 (1976 to 1982) years |
Open contentions (4) open contention
Where sources or readings disagree. Both stay on the map.
- C-1815 When were formal security policy models born?
booked: The map dates them to 1972 time-sharing computers, with the older policies they state alongside.
the other reading: the policies it states are older than computers: classification rules, accounting's controls 'derived long before computer systems came into existence', the Stock Exchange's walls; the noninterference approach applies to 'entirely manual systems' (Goguen and Meseguer 1982), so the formal model need not need a computer - C-1816 Should a security model describe the mechanism or just what must stay secret?
booked: The map keeps both kinds of model.
the other reading: access-control formulations are the toolbox for building secure systems and need 'no radical security modeling' later (Bell 2005); access-control formulations describe a mechanism, give no guidance where it proves inadequate and admit perverse interpretations; noninterference is a pure statement of policy (Rushby 1992); the two are incomparable: Bell-LaPadula stricter on read-up, noninterference stricter on covert channels (encyclopedia) - C-1817 Are there truly different kinds of security policy?
booked: The map books the commercial policies as their own kinds, beside the result that many are equivalent.
the other reading: integrity policies need distinct mechanisms; a lattice model is not sufficient (Clark and Wilson 1987); the Chinese Wall cannot be correctly represented by a Bell-LaPadula model (Brewer and Nash 1989); any AND/OR/NOT policy is isomorphic to any other of the same width; the multiplicity was 'more apparent than real' (Bell 2005, on his 1990 result) - C-1818 Is formally proving a system secure worth the cost?
booked: The map keeps both: it marks the highest assurance levels, and doubts about its value in practice.
the other reading: formal verification is the distinguishing feature of the highest class (TCSEC A1; CC EAL7); Bell doubted it was necessary; 1980s tools needed stubs and commenting-out; its greatest benefit is writing down the specification (Schaefer, via Bell); machine-checked proof to the C code 'rules out the possibility of invalidation by implementation errors in this code', under stated assumptions (seL4 2013)
Cross-scale patterns seen here (23) our proposal
Shapes that recur when the same kind of problem is solved at different scales, and how each shows in Formal security policy model. Each links to every other system that shows it.
- barrier-gates-complexity (structural)
With rigorous separation between levels, one computer could host several classification levels at once; without it, 'separate computers had to be used for each different security level' or 'color changes' run sequentially. The without-the-barrier case is shown in the source. - borrowed-then-held (structural)
Controls first held outside the computer by people and law, then held inside it: accounting's double entry and separation of duty ('derived long before computer systems came into existence') became Clark-Wilson's enforcement rules; the Stock Exchange's Chinese Walls, kept manually, became a mandator - causal ceiling (structural)
A limit set by the structure, not by the analyst's means: for general protection systems no algorithm can decide whether a subject can ever acquire a right (HRU, by reduction from Turing machines); and on commodity hardware 'the absence of such channels is not fully enforceable'. - nested ladder (structural)
TCSEC classes as logical subsets ('an exercise in giving partial credit'): D < C1 < C2 < B1 < B2 < B3 < A1, the model requirement rising from an informal statement (B1) to a formal model proven consistent (B2) to a formal top-level specification and verified design (A1); Common Criteria EAL1-EAL7 wi - same role, different builds (structural)
The job 'say exactly what a computer may allow, and show that it keeps to it' built as a state machine with a basic security theorem (Bell-LaPadula), an automaton with inputs and outputs (noninterference), certified transformation procedures with separation of duty (Clark-Wilson), access history (Br - same shape, opposite sign (structural)
One rule, levels monotone along a directory path, proposed with both signs: Bell wanted levels non-increasing away from the root (a parent holds its children's metadata); Case Western argued non-decreasing (resolving a path reads every node above). Program direction chose the second ('compatibility' - symmetry breaking (name the cut) (structural)
Before a Chinese Wall analyst's first access every company dataset in a conflict class is equally open ('the actual choice of dataset is totally unrestrained'); the first access is the cut, and the wall it raises sets everything the analyst may see after. Bell: 'a user's free-will choice limiting fu - templating (structural)
One module reused unchanged across systems: TCSEC listed Bell-LaPadula as the representative model for B2-A1 products; any boolean-lattice implementation 'could support any other boolean policy, given enough width and the provision of a personality module'; the same model was interpreted for Multics - the whole sets the local reference (structural)
Each component reads secure against its own model, yet local readings do not close into a global one: two identical A1 systems 'could also be also be combined so badly that the composite has no security at all'; no closed-form composition without a network view; and between two levels, some platform - trade one property for another (structural)
Expressiveness traded for decidability, with kinds along the trade: HRU's general protection systems (safety undecidable), its mono-operational systems (decidable, 'not terribly realistic'), take-grant (decidable in linear time), Cedar 'finely balanced' for a sound and complete SMT encoding. Also st - Umwelt: each system carves its own slice of one shared medium (structural)
Each model sees its own slice of the same machine: Bell-LaPadula sees subjects, objects and accesses (and not covert channels); noninterference sees inputs and outputs; at network level the subjects are hosts and the objects connections; the seL4 proof covers storage channels and logical time, but ' - who opens the door (structural)
Doors installed ahead of time by the receiving side: every rule answers 'a well-formed class of request' and no two rules the same request, so the model has a prepared door for every request before any arrives; in Clark-Wilson only TPs certified for a CDI may change it, and only the certifier may ch - conservation law plus closure (partial)
The Basic Security Theorem is a conservation statement (secure states stay secure) that predicts nothing about a system until a rule set closes it: volume I's change relation W was 'not constructive', and only the ten rules made it usable for system calls. Bell also states a 'conservation of complex - holding / entrainment (partial)
In seL4 the kernel's fixed partition schedule sets when each partition runs: 'scheduler choices do not leak information between partitions'. The whole sets the clock of its parts. - namespace completeness (the map predicts its gaps) (partial)
Bell's boolean-lattice result: a policy alphabet fixes the lattice, every AND/OR/NOT policy of a given width has its place in it, and he produced constructive solutions for every published policy; ORCON, thought impossible, was then given a design. - outside-to-inside (partial)
The partition of duties among employees, an outside arrangement, moves inside the system as Clark-Wilson's enforcement rules, but only partly: 'computers cannot verify' external consistency, so certification stays with people. - seed (partial)
Noninterference, a one-line definition (low outputs the same whatever the high inputs), unpacked a family: intransitive noninterference, nonleakage, declassification, termination, timing and probabilistic variants, quantitative leakage, hyperproperties. Seed check: maybe. - The carry (partial)
A Chinese Wall analyst can hold at most one company dataset per conflict class; the excess passes to another analyst, so the wall needs at least as many analysts as the largest class has companies, and more 'should two or more users choose to access the same dataset'. The wait face: Bell's early dil - The Payment to Entropy (partial)
Assurance pays a toll at each hand-off down the chain model, specification, code, machine: TCSEC A1 shows the FTLS consistent with the model formally only 'where possible' and the implementation consistent with the FTLS only informally; verification tools needed 'manual stubs, drivers, and artful co - lightning (surface)
A stored attack released on command: back doors that persist through recompilation, 'to craft a pointed attack much later and launch that attack on command'. - red-queen (surface)
Covert channels and models keep running: storage channels closed by proof, timing channels then only reduced in bandwidth ('the best that can be expected is to reduce channel bandwidth'); a bandwidth bar (100 bits per second) rather than a win. Neither side's improvement shown as stalemate over time - runaway from an unstable balance (surface)
Once government nurturing and community evaluation stopped, high-assurance supply fell on itself: no sales, vendors treat products as under-performers, the stock frozen, attrition, 'everyone wants to be second through the gate'. The balance point (government funding and evaluation) is named; the run - same toolkit, independent builds (surface)
Different groups built different policies from the same parts (subjects, objects, labels, simple security and *-property rules): Clark-Wilson, Brewer-Nash (who adopted Bell-LaPadula's concepts on purpose) and Bell's boolean lattice. Shared ancestry is visible, so this is the dark twin's risk: surfac
Valence: what it trades, and with whom (13) published science
Each exchange with a neighbour, read from both sides: who gains, who pays, and what carries it.
- Accounting (the field and practice) via sys:accounting · Formal security policy model gain
- Human (Homo sapiens) via sys:human · Formal security policy model gain
- Government via sys:government · Formal security policy model gain
- Mathematics (the field: the practice and the structures it studies) via sys:mathematics · Formal security policy model gain
- Operating system via sys:operating-system · Formal security policy model gain
- Programming language via sys:programming-language · Formal security policy model gain
- Computer security via sys:computer-security · Formal security policy model gain
- Access control via sys:access-control · Formal security policy model gain
- Security policy and governance via sys:security-policy · Formal security policy model gain
- Proof assistant (Metamath, Lean, Isabelle and the like) via sys:proof-assistant · Formal security policy model gain
- Security audit and compliance via sys:security-audit · Formal security policy model gain
- Covert channel via sys:covert-channel · Formal security policy model loss
- Financial regulation (the Chinese Wall) via sys:financial-regulation · Formal security policy model gain
Partners and parts published science
Built from / builds (8)
- Information security
- Human (Homo sapiens)
- Mathematics (the field: the practice and the structures it studies)
- Security labels and clearances
- Proof assistant (Metamath, Lean, Isabelle and the like)
- Access matrix and access modes
- High-assurance evaluated systems against speedy approval of low-assurance systems
- Covert channels against the model's confinement of information
Sits inside / holds (3)
expressed by (14)
- Generation/Synthesis
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Quality Improvement/Refinement
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Evolvability/Plasticity Engineering (Design for Future Variation)
- Sensing/Scanning
- Hypothesis/Goal Selection
- Mapping/Modeling
- Uncertainty Reduction/Learning
- Social Learning / Public Information Use
- Validation of Effectiveness
- Quality Control & Error Correction
floor filled by (22)
- Information security
- Human (Homo sapiens)
- Mathematics (the field: the practice and the structures it studies)
- Operating system
- Access control
- MULTICS
- seL4
- Security labels and clearances
- Bell-LaPadula model
- Proof assistant (Metamath, Lean, Isabelle and the like)
- Biba integrity model
- Clark-Wilson integrity model
- Brewer and Nash (Chinese Wall) model
- Trusted Computer System Evaluation Criteria (Orange Book)
- Security audit and compliance
- Product evaluation and certification (Common Criteria, FIPS 140, EMVCo)
- Access matrix and access modes
- Noninterference
- Graham-Denning model
- Harrison-Ruzzo-Ullman (HRU) model
- Take-grant protection model
- Hyperproperties
Kinds (10)
- Bell-LaPadula model
- Security policy and governance
- Biba integrity model
- Clark-Wilson integrity model
- Brewer and Nash (Chinese Wall) model
- Noninterference
- Graham-Denning model
- Harrison-Ruzzo-Ullman (HRU) model
- Take-grant protection model
- Hyperproperties
Notes published science
- Bell and LaPadula's famous '*-property' was a placeholder: Bell scribbled a star on the blackboard while they hunted for a proper name, warned that 'if we didn't change the name right then, we'd be stuck with it forever', and nothing came to them (src:bell-2005).
- Bell's 'Computer Security Intermediate Value Theorem': connect a computer at one classification level to one at another through any network cloud, and some box inside the cloud must be handling both levels. You can move the hard part, 'but you cannot eliminate it' (src:bell-2005).
- Whether a user of a computer can ever end up with a forbidden permission is, in general, mathematically undecidable (Harrison, Ruzzo and Ullman 1976, by building a Turing machine out of access rights), so 48 years later Amazon's Cedar policy language was deliberately 'finely balanced' to stay on the decidable side (src:hru-1976, src:cutler-2024-cedar).
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
formal security policy models as security modellers describe them: the computer system and the policy it must keep, up to the assurance and design guidance others act on (reader's view)
- L1: The computer system and the world it holds: subjects (users, processes) and objects (files, segments, devices, connections), information at different sensitivities, and the informal policy people want kept
- L2: Abstraction: entities named as subjects and objects, access modes (r, w, a, e, c; later view and alter), labels in a partial order, the state as current accesses, matrix, level function and object hierarchy; for noninterference, domains with inputs and outputs
- L3: The definition of 'secure': a secure state (simple security, the *-property, discretionary security), or a flow statement (noninterference: low outputs independent of high inputs), or certification and enforcement rules (Clark-Wilson), or walls between conflict-of-interest classes (Brewer-Nash)
- L4: Rules for every change of state: get and release access, give and rescind access, create and delete objects, change levels (ten rules in Bell-LaPadula's second volume); commands over the access matrix (HRU); eight protection rules (Graham-Denning); four graph-rewriting rules (take-grant)
- L5: The theorem and its proof: the Basic Security Theorem (each rule preserves security, so security is inductive); unwinding theorems for noninterference; machine-checked proofs (Isabelle/HOL, Lean); decidability of safety (undecidable in general, decidable for restricted systems)
- L6: Interpretation and correspondence: the model mapped onto a real design (the Multics interpretation; hosts and connections for a network), a descriptive or formal top-level specification shown consistent with the model, and in seL4 a refinement proof down to 8,830 lines of C
- L7: Assurance and guidance others act on: a certified rating (B2 to A1 under TCSEC, EAL6-7 under the Common Criteria) that acquirers rely on; a conceptual toolbox and vocabulary for designing secure systems; analyses that show a policy change keeps permissions the same
the boardroom (shared floors)
- L3: What 'secure' means: a secure state defined over subjects, objects and labels (Bell-LaPadula, Biba), a flow statement over inputs and outputs (noninterference), integrity by certified transformations (Clark-Wilson), walls set by access history (Brewer-Nash)
- L4: The rules for every change of state, each answering one class of request, no two rules answering the same request; refined by engineering experience (trusted subjects, current level, object hierarchy) and tailored to a target system
- L5: The proof that the rules keep the definition: the Basic Security Theorem by induction over states, unwinding theorems for noninterference, machine-checked proofs, decidability results for safety
- L6: The model mapped onto a real design: interpretations (Multics, Trusted Xenix, Blacker's hosts and connections), top-level specifications shown consistent with the model, refinement to code
- L7: Assurance and guidance others act on: evaluators judge the developer's understanding through the model; acquirers rely on the rating; designers use the toolbox; policy authors rely on analyses
way in: Attacks, counterexamples and leaks (tiger teams, perverse interpretations, covert channels)
- L1: Systems under attack: tiger teams penetrating every system they tried; back doors that persist through recompilation
- L2: A gap found in a model: perverse interpretations that satisfy the letter of an access-control model but not its intent; covert channels left out of scope; a published unwinding theorem shown incorrect
way in: Engineers building prototypes from the model
- L1: Engineering tasks building secure prototypes on the model, and the difficulties they hit
- L2: Questions brought back to the modeller (what level for the scheduler that must read and write every level?)
- L3: Refinements proposed from the workbench: Schiller's 'current security level' shortcut; trusted subjects exempt from the *-property; the object hierarchy for Multics directories
way in: Evaluation criteria (TCSEC 1985, Common Criteria Part 3)
- L1: Published evaluation criteria that grade systems by assurance: the TCSEC classes D to A1 (1985), the Common Criteria assurance levels EAL1-EAL7
- L2: The class requirement read: an informal statement of the model at B1; a formal model proven consistent with its axioms from B2; ADV_SPM.1 formal TOE security policy model at EAL6 and EAL7
- L3: The requirement turned into deliverables: a model with a proof, a top-level specification (descriptive below A1, formal at A1) and a correspondence argument
way in: Mathematics: set theory, lattices, automata, logic
- L1: The mathematical stock the modeller draws on: set theory, partial orders and lattices (Birkhoff's text), automata, traces, logics
- L2: A formalism chosen: state transition models, temporal logic models, denotational semantics models or algebraic specification models; automata with inputs and outputs (noninterference); sets of trace sets (hyperproperties)
way in: Questions about a written policy set (does this refactoring change who may do what?)
- L1: A policy set written in a policy language (Cedar, Rego, OpenFGA) and a question about it from its authors
- L2: The policies and question compiled symbolically to SMT
way in: The informal policy to be formalised (military classification, commercial integrity controls, financial-market walls)
- L1: A policy people already keep on paper: the DoD multilevel classification policy; accounting's well-formed transactions and separation of duty; the UK Stock Exchange's Chinese Wall rules, which have the authority of law
- L2: The policy read for its goal and its terms: disclosure for the military policy, integrity ('preventing fraud and error') for the commercial one; 'security' defined before anything else
way in: The proof tool: obligations discharged or refused (inner)
- L1: The proof state held in a verification system or proof assistant (Isabelle/HOL, an LCF-style prover for higher-order logic; earlier verification tools that needed manual stubs)
- L2: Obligations reported proved or stuck: unwinding conditions checked step by step; a failed obligation exposes a leak (the original seL4 scheduler)
way in: The target system (Multics, Unix, a network of hosts, a microkernel)
- L1: The real system the model must describe: Multics segments and directories, Unix files, a network of hosts, the seL4 kernel
- L2: The system learned from its documentation (Organick's book on Multics) or its specification and code
- L3: The system's entities mapped to the model's: segments and files as objects with a hierarchy; at network level 'hosts' as subjects and 'connections' as resources
way out: Answers about policy sets back to their authors
- L1: Policies changed by their authors; requests decided by the evaluation engine
- L3: Validation reported back while policies are written
- L5: An analysis result: the refactored policy set authorises exactly what the old one did, or a difference is found
way out: Design guidance to engineers (rules into system calls and specifications)
- L1: Systems built: KSOS, PSOS, KVM, Multics; later SCOMP, GEMSOS, XTS-300/400; seL4 extended with a partition scheduler
- L3: A top-level specification of the trusted computing base written against the model
- L4: Rules cast in a constructive form to guide the core system calls
way out: Evidence to evaluators, ratings to acquirers
- L1: A rating acquirers rely on: SCOMP at A1, Multics at B2; data diodes certified to CC EAL7+
- L6: The evaluator's judgement of how well the developer understood the security functionality
- L7: The model and its correspondence to the functional specification handed over as assurance evidence (ADV_SPM)
way out: Models, theorems and vocabulary published to the field
- L1: A shared vocabulary and toolbox the field designs with
- L3: Reports and papers (MITRE volumes, symposium papers, journal articles)
- L5: Results written up: basic security theorem, unwinding theorems, hyperproperty decomposition
way out: Properties built into enforcing mechanisms (MAC modules, one-way links)
- L1: Requests allowed or refused; data moved one way only, from low to high
- L2: Mechanism configured to it: FreeBSD's mac_biba policy module; a data diode built to the *-property
- L3: A property chosen for enforcement (no write down; no read down for integrity)