The way Unix decides who can read a file is the wrong foundation for security. It was known to be the wrong foundation by 1972, and SELinux is the end of a fifty year chain of attempts to replace it that finally made it into the kernel you are running today. That is a strong claim, and it takes three long parts to defend, one mechanism at a time.

Each mechanism was built to fix a specific failure of the one before it, so each one starts with that failure and ends with the problem the next one had to solve. The same example runs from beginning to end, a web server and an encryption pipeline on the same machine, and every mechanism gets to decide the same request, because the fastest way to see what a security model can and cannot say is to ask it the same question you asked the last one.

This is not a tutorial on writing SELinux policy, there are good ones already. It is about why the thing exists, what it actually solved, what it didn’t, and by the end of it you should be able to decide for yourself whether you want it on your machines.

Why permissions are not enough

The example

A machine runs a web server, let’s say Apache, that serves pages to the internet. On the same machine, a user, let’s call her Alice, has a plaintext file that must never leave the machine as it is, so there is an encryption program, and the rule of the house is that the plaintext goes into the encryption program, ciphertext comes out, and only the ciphertext can be handed to the program that sends things out to the network. Plaintext, encrypt, ciphertext, send, in that order and no other.

The security requirement has two parts

1. Only the encryption program may turn Alice’s plaintext into something that can be sent out.
2. The web server must never be able to read the plaintext, even if it is compromised, and even if it is running as root.

Every mechanism in this series gets asked the same two questions, can you express these rules, and can you enforce them when one of the programs on the machine is under the attacker’s control. Most of the history of this field is the story of mechanisms that could do one but not the other.

What Unix permissions can and cannot say

Unix permissions, the rwx bits you see in ls -l, answer exactly one question, which users may do what to this file. Every file has an owner and a group, and three sets of read, write and execute bits, for the owner, for the group and for everyone else. Every process runs as some user, and when it asks the kernel to open a file, the kernel looks at which user the process is running as, looks at the bits, and says yes or no. This is what the textbooks call discretionary access control, DAC, discretionary because the owner of the file decides, at their own discretion, who else gets in, and can change their mind at any time with chmod.

This model has two properties that matter for our example, and both are so familiar that we have stopped seeing them as design decisions.

First, the decision is about the user, never about the program. The kernel doesn’t know or care whether the process asking to read Alice’s plaintext is her encryption program, her text editor, a script she downloaded, or a copy of the web server that an attacker managed to run with her user ID. If it runs as Alice, it can read whatever Alice can read. This is the Trojan horse problem, a program you run can do everything you can do, including the things you didn’t ask for, and it is the reason the security literature uses the word discretionary in a slightly disapproving tone, the protection is only as good as the judgement of every program that ever runs with your identity.

Second, root. Root is not a user with a lot of permissions, root is the user for whom the check is skipped. Every permission bit in the system is a suggestion as far as root is concerned. And because Unix needed a way for ordinary users to do a few privileged things (change their password, bind port 80, deliver mail..etc.), it grew the setuid bit, a program that runs as its owner instead of as the person who ran it, which in practice means a couple of dozen programs on any system that run as root when you ask them to. Every one of them is a door, and a large part of Unix security history in the eighties and nineties is a list of setuid programs whose doors didn’t lock.

Running the example

Let’s run the request. Alice’s plaintext is a file owned by Alice with mode 600, so only Alice can read it. The encryption program runs as Alice, so it can read the plaintext and write the ciphertext. The web server runs as www-data (the parent process starts as root to bind port 80 and stays root, the child processes that actually answer requests run as www-data), so the part of it that talks to the internet can’t read a mode 600 file owned by Alice. On a normal day, this works.

Now let’s look at the bad day. The web server has a bug and the attacker gets it to run their code. The attacker is www-data, so they can’t read Alice’s file directly, but they can read every file www-data can read, which on a real machine is a lot, and they can start looking for a setuid program with a bug, and the moment they find one they are root and Alice’s mode 600 is decoration. If the bug is in the part of the server that is still running as root, they skip the middle step.

That covers rule 2, the web server holds until the first setuid bug. Rule 1 is worse, because we cannot state it at all. There is no way to say, in this model, that the encryption program is the only program allowed to turn the plaintext into something that goes to the network, because the model has no vocabulary for programs. Alice can run cat on her plaintext and pipe it straight into the sending program, and as far as the kernel is concerned that is exactly as legitimate as running the encryption program, because both of them are Alice. The pipeline is a convention between programs, and the kernel enforces none of it.

So Unix permissions can enforce rule 2 only until somebody becomes root, and they cannot express rule 1 at all. The reason is not a bug, it is the basic design, the check is keyed to who is asking and blind to what is asking. That diagnosis was written down before the Unix permission bits were even published.

The reference monitor, 1972

The document everyone still cites is the Computer Security Technology Planning Study of 1972, usually just called the Anderson report. James P. Anderson’s company ran the study for the US Air Force with a panel of experts, and it was not the first warning, a Defense Science Board task force chaired by Willis Ware had described the problem in 1970, but it is the one that gave the fix a name. The Air Force’s problem was concrete, they wanted to run programs of different classification levels on the same computer, and the computers of the day made that impossible in practice, not because of any particular bug, but because nothing in the architecture prevented one program from getting at another’s data.

The report’s answer was an idea rather than a product, the reference monitor. The reference monitor is the part of the system that sits between every subject (a process, a user) and every object (a file, a device, another process) and decides, for every single access, whether it is allowed. The Unix permission check is a reference monitor of a sort. What the report added were three requirements that a monitor has to meet before anyone should trust it

1. It must always be invoked, there is no way to get to an object that bypasses the check.
2. It must be tamperproof, no subject can modify it or the data it decides with.
3. It must be small enough to be analysed and tested, so that you can actually verify it is correct instead of hoping.

The implementation of a monitor that meets all three is what the report calls a security kernel, which is where the word kernel comes from in this context, if the thing has to be small enough to verify, it has to be the smallest possible core of the system, with everything else (the editor, the compiler, the web server..etc.) living outside it and treated as untrusted.

If we look at the Unix check against the three requirements, it fails the first one by design, root is a documented way around it. Nobody ever really asked about the second and third, the check is a few lines inside a kernel that is now millions of lines, all running with the same privilege. But the deeper point, which the report makes almost in passing, is that a reference monitor decides according to a policy, and the policy is separate from the monitor. The Unix check has its policy, owner, group, other, built into it, and as we just saw, that policy can’t even express the rule we want. Separating the two is the idea that every later part of this series is built on.

The Orange Book, 1983

The Anderson report became the intellectual basis of the document that dominated the field for the next twenty years, the Department of Defense Trusted Computer System Evaluation Criteria, published in 1983 and revised in 1985, known to everyone as the Orange Book because of its cover. If you have ever seen a vendor brag that their system was C2 certified, this is where that comes from.

The Orange Book defines a ladder of evaluation classes, D at the bottom (no protection to speak of), C1 and C2, then B1, B2 and B3, and A1 at the top. The step that matters for this series is the one between C2 and B1, because it is exactly the line between what Unix does and what everything after it is about.

• C2, controlled access protection, is discretionary access control done properly, per user accounts, per object permissions, auditing, and object reuse (clearing memory and disk blocks before handing them to the next user). Most Unix systems of the nineties, and Windows NT, were evaluated at C2, and it is a fair description of a well run Unix box.
• B1, labeled security protection, is the first class that requires mandatory access control. The system attaches a label to every process and every storage object and enforces a policy over those labels that the owner of the file cannot override. This is on top of the discretionary permissions, not instead of them, but the new check is one whose answer is not up to Alice, or to any program running as Alice, or even to root in the ordinary sense. It is up to the policy.
• B2, B3 and A1 add a formal model, covert channel analysis, a trusted path, a system actually structured around a small reference monitor, and finally formal verification of the design against the model. Only a handful of systems ever reached A1, and they turn up again below.

The point to take from the ladder is not the letters. It is that by 1983 the people who had thought hardest about the problem had concluded that permissions, however carefully administered, top out at C2, and that everything above that line requires labels and a policy that users and programs cannot bend. That conclusion then stayed inside the military and its contractors for fifteen years, which is the next problem.

The Inevitability of Failure, 1998

In 1998 a group at the NSA (Peter Loscocco, Stephen Smalley and four colleagues, two names that will come up again and again) published a paper with the title The Inevitability of Failure: The Flawed Assumption of Security in Modern Computing Environments. It is short, it is readable, and it is the thesis of everything that follows.

The flawed assumption in the title is the assumption that you can build secure applications on top of an operating system that provides no mandatory security. The paper takes the security technology the industry was excited about at the time, firewalls, Kerberos, IPsec, SSL, and shows for each one that its guarantees quietly depend on the operating system underneath doing something it cannot do. A firewall can only enforce a policy if the machine it runs on cannot be made to bypass it. Kerberos can prove who you are to a server, but a malicious program running as you can fake the login prompt and collect your password, or simply read the file where your tickets are kept and be you. IPsec and SSL protect data on the wire, but if the attacker is on either end and reads the data before it is encrypted, the protection is, in the paper’s own words, only illusory. The examples are 1998 examples, substitute a container runtime, a password manager or a TLS terminator and the argument doesn’t change.

The paper says the operating system has to provide two things, mandatory access control, so that the system rather than the user or the program decides what may flow where, and a trusted path, so that the user knows they are talking to the real login program. And then it makes what I think is the most important point in this whole story, mandatory security is not the same thing as the military’s classification levels. The military policy, which the example runs through below, is one policy, and what is actually needed is a mechanism that can enforce whatever policy the system requires. One of the paper’s own examples is an assured pipeline, which makes sure that data flowing from a designated source to a designated destination has to pass through a designated subsystem on the way, and in its section on cryptography it warns that without mandatory controls there is no guarantee the encryption is ever invoked, because the program that calls it can be bypassed or modified. That is our example, rule 1 and rule 2, stated in 1998 by the people who would go on to build SELinux.

Where that left things

Four things from this carry through everything that follows.

• Unix permissions decide by user, so they cannot distinguish the encryption program from any other program Alice runs, they are switched off entirely by root, and their policy is fixed, nobody can change it.
• The Anderson report said in 1972 that a trustworthy system needs a reference monitor that is always invoked, tamperproof and small, enforcing a policy that is separate from the mechanism.
• The Orange Book said in 1983 that anything beyond user permissions requires labels and mandatory control, and drew the line at B1.
• The NSA said in 1998 that until the operating system provides this, every security product built on top of it is standing on sand.

The obvious objection is that this is all very well for the military, and that nobody else has Secret and Unclassified files. The objection is right, and it is the reason the next twenty five years of this story happened the way they did. The military had an answer ready in the seventies, you label everything with a classification level and enforce two rules, no reading up and no writing down, and it was elegant, provable, and the basis of every A1 system ever built. Run the web server and the encryption pipeline through it and watch exactly where it breaks, because the way it breaks is what everything after it was built to fix.

Multilevel security, and why it stayed in the military

The 1998 NSA paper said the fix is mandatory access control, a policy that neither Alice nor her programs nor root can bend. That leaves the question of what the policy should say, and for more than a decade there was exactly one serious answer, the one the military had been using since before there were computers.

Multilevel security fixed both failures of the permission bits. It stops a compromised program from leaking what its user can read, and it makes root irrelevant to the decision. What it could not do was state rule 1, only the encryption program may turn plaintext into something that can be sent, and the reason it couldn’t is the same reason it never left the military. The next mechanism was designed around exactly that reason.

Levels

If you have seen a spy film you already know the policy. Documents are classified Unclassified, Confidential, Secret or Top Secret, people are cleared to a level, and a person may read a document only if their clearance is at least the document’s classification. The military ran on this for decades before there were computers, so when the Air Force asked in the early seventies how to put Secret and Unclassified work on the same machine, the policy was already written, it only had to be made precise enough for a machine to enforce it.

David Bell and Leonard LaPadula did that at MITRE, in a series of reports starting in 1973, with the version everyone cites being the 1976 unified exposition, which also worked through how the model applied to Multics. The Bell-LaPadula model, BLP from here on, attaches a label to every subject (a process running on behalf of a cleared user) and to every object (a file, a segment, a device), where a label is a level plus, optionally, a set of compartments (Secret with the NATO compartment is not comparable to Secret with the Nuclear compartment, neither dominates the other, which is what makes the labels a lattice rather than a ladder). Then it states two rules

1. The simple security property, a subject may read an object only if the subject’s label dominates the object’s label. No read up. A Confidential process cannot read a Secret file.
2. The *-property (pronounced star property, the report says the name is for historical reasons), a subject may write an object only if the object’s label dominates the subject’s label. No write down. A Secret process cannot write into a Confidential file. (The 1976 version is fussier about what counts as reading and writing, and only applies the rule to untrusted subjects, which is where the example below ends up.)

The first rule is the one everybody expects. The second is the clever one, because it is the answer to the Trojan horse problem from the permission bits. Under Unix permissions the danger was never that an Unclassified user reads the Secret file directly, it was that some program running as the Secret user copies the file somewhere the Unclassified user can get at it. The *-property forbids exactly that. A process that has read Secret data is a Secret process, and a Secret process cannot write anywhere a Confidential process could later read, so the copy cannot happen, no matter how malicious the program is and no matter what the user who ran it intended. The model does not need to know anything about the program’s intentions, because information at a level has no way to be copied into anything at a lower level. (There are two exceptions and the authors were upfront about both, trusted subjects, which we get to below, and what the 1976 report calls communication paths, leaks through timing and resource usage that no label check sees and that it admits may never be fully closed. There is also a third rule applying discretionary permissions on top, but it is the two mandatory rules that do the work.)

Kenneth Biba turned the whole thing upside down in 1977 and got an integrity model out of it, no read down and no write up, so that untrusted low integrity data can never contaminate a high integrity process or file. Where BLP is about keeping secrets from leaking out, Biba is about keeping untrusted data from getting in, and our example has both problems, the plaintext must not leak, and nothing unencrypted may be slipped in between the encryption program and the network. You might think BLP for the secrets plus Biba for the integrity covers it. It does not, and Boebert and Kain showed why in 1985, whichever way you assign integrity levels along the pipeline, either the plaintext and the ciphertext sit at the same level and the policy cannot tell them apart, or data has to flow up in integrity at every step and every step needs another trusted exception, which is where type enforcement starts.

The systems that were actually built

This was not theory. Between the late seventies and the early nineties several operating systems were built around BLP, and the Orange Book’s A1 class, verified design, was written with them in mind. Honeywell’s SCOMP, a security kernel on a Level 6 minicomputer with hardware support for the kernel boundary, was the first system evaluated at A1, in 1985. Gemini Computers’ GEMSOS followed, evaluated at A1 in the mid nineties after a decade of work. Multics itself was evaluated at B2. There were earlier kernel projects too, KSOS at Ford Aerospace and KVM/370 at SDC in the late seventies, that produced most of the lessons without producing a product.

These systems did what they were designed to do. If you had Secret and Unclassified users on one SCOMP, the Unclassified users could not read the Secret files, no program the Secret users ran could leak them, and the vendor had a formal proof that this was so. That is a remarkable thing to be able to say about a computer, and it is worth noticing that in 1985 somebody could say it, because by 2000 nobody running a commercial operating system could.

Running the example

Let’s run the request.

We label Alice’s plaintext Secret. Alice is cleared to Secret, so her processes can read it. The web server runs at Unclassified, because it talks to the internet and the internet is as Unclassified as it gets. The simple security property says the web server cannot read the plaintext, and it does not matter whether the web server is compromised or running as root, because the label check is mandatory, the kernel does not ask who you are, it asks what level you are at, and there is no level at which a process talking to the internet gets to read Secret files. That is rule 2, enforced, and it is already better than anything Unix permissions could do. The *-property does the other half, any process at Secret, including a compromised editor Alice happens to be running, cannot write to the network, because the network is Unclassified and that would be a write down. The plaintext cannot leak.

Now the encryption program. It reads the plaintext, so it is a Secret process. It produces ciphertext, which by the whole point of the exercise is safe to send, so it needs to write it somewhere the sending program at Unclassified can read. That is a write down, and BLP forbids it. The pipeline we wanted, plaintext, encrypt, ciphertext, send, is, from the model’s point of view, indistinguishable from the leak it was designed to prevent, because the model reasons about levels and only about levels, and it has no way to know that the bytes coming out of this particular program are safe when the bytes coming out of cat are not.

The military ran into this constantly. It is the downgrade problem, somebody has to declassify a document, an encryptor has to put Secret traffic on an Unclassified wire, a printer spooler has to move things around, and the model’s answer, designed in from the first prototype, is the trusted subject, a process exempt from the *-property. Mark the encryption program trusted and it can write down. That is exactly the moment the model stops helping, because trusted does not mean the model has verified the program does the right thing, it means the model has agreed not to look. Rule 1 has not been expressed. What has been expressed is that the encryption program is allowed to break the rule, and every other program that ever gets marked trusted (there were always more than anyone liked) has the same exemption, with nothing in the policy that says what any of them may do with it.

There is a second, quieter failure. Everything Alice runs at Secret can read the plaintext, her editor, her mail client, her shell, whatever she downloaded. The model stops them leaking it down, but it does nothing about them reading it, modifying it, or handing a doctored version to the encryption program, because they are all at the same level and the model has no concept of one program at a level being more trusted than another. There is no least privilege inside a level. The label belongs to the user’s session, not to the program, and that is the deepest reason MLS never left the military.

Why it stayed in the military

It is tempting to say MLS failed commercially because it was expensive, or slow, or because the evaluations took years, and all of that is true, but it is not the reason. The reason is that the policy is the military’s policy. Outside a classified environment nobody has a lattice of clearances. A bank does not care whether the teller’s process is at Secret, it cares whether the program that moves money is the program that is supposed to move money, and whether the web server can get at the customer database. Those are questions about programs and data flows, not about levels, and BLP cannot even ask them.

The engineering problems made it worse. Because a process can only ever write at or above its level, everything drifts upward, a job that needs a single Secret input has to run at Secret and then everything it writes is Secret, however little of it came from the Secret file (systems with floating labels, where a process is raised automatically to the highest label it has read, Weissman’s high water mark in ADEPT-50 in 1969 and later the compartmented mode workstations, do this without even asking, and Weissman already noted that his scheme tends to overclassify), so objects migrate to the top of the lattice, the system slowly becomes system high, and somebody has to be trusted to bring things back down, which is the exemption again. The formal models allowed covert channels, a Secret process modulating disk usage or CPU timing so that an Unclassified process could read it, and B2 and above required you to hunt for and measure those channels, which was a research career rather than an engineering task. And for the user it meant multiple sessions, a Secret desktop and an Unclassified desktop and no cut and paste between them, which is the correct behaviour and also the reason the users hated it.

None of this means the ideas were wrong. Labels on every object, a mandatory check the user cannot override, a policy with a formal statement, these all survived, they are in SELinux today (there is an MLS policy in Red Hat Enterprise Linux that is a direct descendant of all this, and we will get to it), and the *-property is still the cleanest explanation of why the Trojan horse problem is solvable at all. What was wrong was the assumption that levels are the only thing worth labelling.

Where that left things

What multilevel security settled, and what it could not, comes down to four points.

• BLP enforces rule 2 completely, the web server cannot read the plaintext and no program of Alice’s can leak it, and it does so without ever asking who is root. On this point it is a strict improvement over permissions, and everything after it keeps this property.
• BLP cannot state rule 1. The only tool it has for the encryption step is an exemption, and an exemption does not add the rule we wanted, it switches off the rule we already had, for that one program.
• BLP has no least privilege inside a level, because the label belongs to the user, not the program. Every program Alice runs is equally trusted with her plaintext.
• Adding Biba’s integrity levels does not rescue it, the pipeline breaks under every assignment of integrity levels, which Boebert and Kain proved in 1985.

What we need is a policy that talks about programs. It has to let us say that this kind of program may read this kind of data and write that kind of data and nothing else, so that the pipeline is a sequence of steps the kernel enforces, with no step that can be skipped and no program that can substitute for another. In 1985, an engineer at Honeywell and a professor at the University of Minnesota wrote a short paper proposing exactly that. They called it type enforcement, their worked example was a labeller that every page must pass through before it may reach a printer, which is our pipeline with the encryption program swapped for a rubber stamp, and they said in as many words that the encryption case is the same construction.

Type Enforcement

Multilevel security could keep the web server away from Alice’s plaintext and stop the plaintext leaking to the network, and still could not say the one sentence our example is about, only the encryption program may turn plaintext into something that can be sent.

Type enforcement is the first mechanism that can state rule 1, and it does so with a construction so simple you can check it by reading a table. Every system that implemented it, in a coprocessor, in a firewall and in a Unix kernel, also made the same mistake, they built their one kind of policy into the thing that enforced it, and undoing that mistake took the rest of the decade.

Two tables

In 1985, Earl Boebert, at Honeywell’s Secure Computing Technology Center in Minnesota, and Richard Kain, a professor at the University of Minnesota who consulted for them, published a ten page paper at the National Computer Security Conference with the rather dry title A Practical Alternative to Hierarchical Integrity Policies. Most of the ideas that a Fedora machine enforces on every file access today are already in it.

Their starting observation is that integrity belongs to programs, not to users. Secrecy levels bind naturally to the person a process works for, but a hierarchical integrity policy, Biba’s, binds its integrity level to the subject as well, and then the only way to let a labeller or an encryptor do its job is to trust it, module by module, which they call an excessive need for trust. So for integrity they drop the order. In addition to its level, every object gets a type, which is just a name (plaintext, ciphertext, web page, mail spool..etc.), every subject, every running process, gets a domain, which is also just a name, and the domains and types are not ordered in any way. The policy over them is two tables.

The first is the domain definition table. Its rows are domains, its columns are types, and each cell says what a process in that domain may do to objects of that type, read, write, execute, nothing. That is the whole of the type enforcement policy for data, in one grid you can print out and check, and in their design it is the third check, after the levels and the access control lists, and it can only take rights away.

The second is the domain transition table. Its rows and columns are both domains, and each cell says whether a process in one domain may move into another (in their design by calling into a subsystem that lives in the other domain, in the Unix versions that came later by executing a particular program). This is the part with no equivalent in anything we have seen so far. The policy gets to say that the only way into the encryption domain is through the encryption program, and that a process in Alice’s shell domain that goes through it leaves Alice’s domain and arrives in the encryption domain with the encryption domain’s row of the first table and nothing else. (The systems that followed widened this second table into a domain interaction table that also says which domains may create, signal or destroy which, but the transition is the part that matters.)

What happened to the label is the important part. In BLP the label was Alice’s, her clearance, and every process she ran carried it. In type enforcement the label belongs to the program. Alice’s shell is in one domain, her editor in another, the encryption program in a third, and although all three run as Alice, the kernel does not treat them the same. Least privilege inside a single user, which was the deepest thing BLP could not do, falls out of the design with no extra machinery, and the trust moves from the user to the program. In the paper’s own pipeline everything sits at one level and none of the domains needs any privilege, and on a system with no levels at all, which is what Sidewinder and DTE turned out to be, there is no order left for anyone to be exempt from. (On SAT and LOCK the levels were still checked first, and moving the ciphertext down to the network’s level was still a downgrade that needed a privileged domain.)

Assured pipelines

The paper’s worked example is about integrity, the hierarchical integrity policies in the title are Biba’s, and the construction they build, the one every later system kept coming back to, is what they called an assured pipeline. You have data that must pass through a particular program before it may reach a particular destination. Their example is hard copy that has to go through a labeller that stamps the classification on every page before it can reach the printer, and they say in as many words that a cryptographic subsystem, where nothing may go out on the insecure wire in unencrypted form, is the same construction. You want the kernel, not the good behaviour of the programs, to guarantee that there is no path around it.

With the two tables this is simple. You give the pipeline’s output a type that only the transforming program may write, you let the stage that talks to the destination read that type and nothing else, and you make sure, in the transition table, that the untrusted domain can call the transformer but cannot call the last stage directly. Then you read the tables and confirm that no other domain has a path from the input to the destination. Because the tables are the entire policy and nothing else exists, that check is a check of the whole system and not of one program, and since there is no trusted subject and nobody is exempt, the pipeline is assured in the plain sense that it is the only route that exists. What the tables prove is that nobody but the encryptor can write ciphertext and that the sender can read nothing but ciphertext. That the encryptor actually encrypts, rather than copying the plaintext into a file with the ciphertext label, is a property of that one program, which you now have to check once, instead of checking every program on the machine.

Let’s write ours down. Alice’s plaintext is of type plaintext. Her shell runs in the user domain, which may read and write plaintext (she has to be able to create the thing) and may enter the encrypt domain, through the encryption program and nothing else. The encrypt domain may read plaintext and write ciphertext, and nothing else, it cannot touch the network and it cannot write plaintext. The send domain may read ciphertext and write to the network, and cannot read plaintext. The web server runs in the httpd domain, which may read web pages and write to the network, and has no entry for plaintext at all.

Now the bad day. The web server is compromised and the attacker is running code in the httpd domain, so when it asks to read the plaintext the cell for httpd and plaintext is empty and the request is denied, and it does not matter which user the web server is running as, or whether it is root, because the table has no column for users. If the attacker finds a setuid bug and becomes root, the process is still in the httpd domain, still denied. If Alice, or a program pretending to be Alice, runs cat on the plaintext and pipes it to the sending program, cat runs in the user domain, which can read plaintext but cannot write to the network, and the sending program, if it can be made to run from there at all, is in the send domain, which cannot read plaintext. The only cell in the table that reads plaintext and produces something the send domain can read is the encrypt domain’s, and the only way into the encrypt domain is through the encryption program. That is rule 1, and this is the first mechanism in the series that can say it.

LOCK and Sidewinder

Boebert and Kain were not describing a thought experiment, they were describing part of a system. The Secure Ada Target, and then the LOCK project (the LOgical Coprocessing Kernel, at Honeywell and, after the group was spun out in 1989, at Secure Computing Corporation) was an attempt to build a system beyond A1 that enforced both the military’s levels and type enforcement, and to take the access decisions out of the host altogether, into a separate hardware coprocessor called the SIDEARM, with the memory management hardware enforcing whatever it decided, so that the reference monitor was tamperproof in the most literal way possible. LOCK took most of a decade, produced a great deal of formal assurance work and not a great deal of product, and never completed an A1 evaluation. It is the reason the people involved spent the nineties thinking about how to get the ideas onto systems people actually ran.

The first place it reached anyone outside the government was a firewall. In 1994 Secure Computing shipped Sidewinder, a firewall built on a Unix whose kernel enforced type enforcement, so that each proxy ran in its own domain and a compromised web proxy could not reach the mail proxy’s data or the firewall’s own configuration. This is our pipeline again, with the internet as the untrusted input and the internal network as the destination, and it worked. Sidewinder was sold for years on the argument that even if you broke a proxy you were stuck in its domain. It is also the first time type enforcement was something you could buy, which meant the technique had a commercial track record by the time anyone tried to put it in Linux.

The parallel line, DTE

Meanwhile Trusted Information Systems, Steve Walker’s company, took the same two ideas and asked the practical question, what would it take to retrofit this onto an ordinary Unix, with ordinary Unix programs, without labelling every file on the disk by hand. Lee Badger, Dan Sterne, David Sherman, Kenneth Walker and Sheila Haghighat published the answer in 1995 in two papers, Practical Domain and Type Enforcement for UNIX and A Domain and Type Enforcement UNIX Prototype, DTE for short, with a prototype built on OSF/1 running on the Mach microkernel, a paper on using it to confine programs that run as root the year after, and one applying it to firewalls in 1997.

DTE kept the domains and the types and the two tables (written in a small policy language rather than as literal grids) and made two engineering decisions that matter for the rest of this story. The first was implicit typing. Instead of storing a type on every file, the policy assigns types by path, everything under /home/alice/secret is plaintext, everything under /var/www is web content, and the kernel works out the type of a file from where it lives. This made DTE deployable on an existing filesystem in an afternoon, and it created the problem of what happens when a file is renamed or hard linked into a differently typed directory, a problem we will meet again in part 3 wearing different clothes. The second was that a domain is entered by executing a designated entry point program, exactly the transition table’s transition, so that the encryption program is the door to the encrypt domain and nothing else is.

Run the example on DTE and you get the same answer as on LOCK. The web server’s domain has no access to the plaintext type, the pipeline is the only path, root is just another process in whatever domain it happens to be in. The difference is that DTE ran on a Unix, with a shell and a compiler and a web server, and the policy was a text file, which makes it the direct ancestor of the policy language SELinux still uses.

Closing Points and Remarks

Type enforcement can express our rule, and the systems that implemented it enforced it. So why is this not the end of the series? Several points are worth noting

• The policy could be changed, but only within one model. Boebert and Kain say it themselves, in the SAT prototype the tables are set when a version of the reference monitor is installed and stay static until a newer version is installed, and they present that as a prototype limitation to be removed later. On Sidewinder the type enforcement database was part of the product, and the documented way to change it was to reboot into a second kernel with the security checks switched off, edit, and reboot again. On DTE the policy was a text file, the 1995 prototype read it at every boot, by 1996 TIS could extend it on a running system, and how to change it safely underneath processes that were already running was still the subject of a research paper in 1998.
• In every one of them, the code doing the enforcing knew what a label was. It knew that a subject carried a domain (and on LOCK a level as well), that an object carried a type, and exactly how those combined into a yes or a no. LOCK had actually split the deciding from the enforcing, the coprocessor decided and the memory hardware enforced, but both halves were built for that one model.
• So you could change what the table said, on DTE by editing a text file, but not what kind of table it was. Ask for a policy that was not a domain and a type, plus a lattice on LOCK, and you were rebuilding the thing that enforced it.

In other words, these systems had solved the question of what the policy should say, and left the policy’s shape baked into the mechanism, the model the decision was made in and the code that stopped httpd from reading the plaintext could not be changed independently. That is the thing LOCK’s own designers had started to pull apart when they split the decider from the enforcer, and finishing the job fell to a group of people, several of them from the LOCK and Sidewinder team, who spent the nineties on it, first on a microkernel that promised to make it easy, and then on one that actually did.

Disclosure

Nothing in this series comes from privileged information, it is all based on the published papers and reports in the reference section.

Please note that this series is my own reading of the history; I might have skipped or been extremely loose about how specific systems worked. If you do find incorrect information, please contact me so I can correct it.

References

• Willis H. Ware (chair), Security Controls for Computer Systems, Report of the Defense Science Board Task Force on Computer Security, RAND R-609, February 1970: https://csrc.nist.gov/files/pubs/conference/1998/10/08/proceedings-of-the-21st-nissc-1998/final/docs/early-cs-papers/ware70.pdf
• James P. Anderson, Computer Security Technology Planning Study, ESD-TR-73-51, October 1972: https://csrc.nist.gov/csrc/media/publications/conference-paper/1998/10/08/proceedings-of-the-21st-nissc-1998/documents/early-cs-papers/ande72.pdf
• Department of Defense Trusted Computer System Evaluation Criteria (the Orange Book), DoD 5200.28-STD, December 1985: https://csrc.nist.gov/csrc/media/publications/conference-paper/1998/10/08/proceedings-of-the-21st-nissc-1998/documents/early-cs-papers/dod85.pdf
• Loscocco, Smalley, Muckelbauer, Taylor, Turner and Farrell, The Inevitability of Failure: The Flawed Assumption of Security in Modern Computing Environments, 21st National Information Systems Security Conference, 1998: https://www.nsa.gov/portals/75/documents/what-we-do/research/selinux/documents/inevit-abs.pdf
• D. Elliott Bell and Leonard J. LaPadula, Secure Computer Systems: Mathematical Foundations, MITRE MTR-2547, 1973: https://apps.dtic.mil/sti/citations/AD0770768
• D. Elliott Bell and Leonard J. LaPadula, Secure Computer System: Unified Exposition and Multics Interpretation, MITRE MTR-2997, 1976: https://csrc.nist.gov/csrc/media/publications/conference-paper/1998/10/08/proceedings-of-the-21st-nissc-1998/documents/early-cs-papers/bell76.pdf
• Kenneth J. Biba, Integrity Considerations for Secure Computer Systems, MITRE MTR-3153, 1977: https://apps.dtic.mil/sti/citations/ADA039324
• Lester J. Fraim, SCOMP: A Solution to the Multilevel Security Problem, IEEE Computer, July 1983: https://ieeexplore.ieee.org/document/1654440
• Loscocco, Smalley, Muckelbauer, Taylor, Turner and Farrell, The Inevitability of Failure: The Flawed Assumption of Security in Modern Computing Environments, 1998: https://www.nsa.gov/portals/75/documents/what-we-do/research/selinux/documents/inevit-abs.pdf
• W. E. Boebert and R. Y. Kain, A Practical Alternative to Hierarchical Integrity Policies, Proceedings of the 8th National Computer Security Conference, Gaithersburg, 1985, pp. 18-27: https://www.cs.purdue.edu/homes/ninghui/courses/426_Fall10/handouts/boebert-kain-te-ncsc-85.pdf
• O. Sami Saydjari, Joseph M. Beckman and Jeffrey R. Leaman, LOCK Trek: Navigating Uncharted Space, IEEE Symposium on Security and Privacy, 1989: https://ieeexplore.ieee.org/document/36291
• O. Sami Saydjari, LOCK: An Historical Perspective, ACSAC 2002 (classic papers session): https://www.acsac.org/2002/papers/classic-lock.pdf
• Lee Badger, Daniel F. Sterne, David L. Sherman, Kenneth M. Walker and Sheila A. Haghighat, Practical Domain and Type Enforcement for UNIX, IEEE Symposium on Security and Privacy, 1995: https://ieeexplore.ieee.org/document/398923
• Lee Badger, Daniel F. Sterne, David L. Sherman, Kenneth M. Walker and Sheila A. Haghighat, A Domain and Type Enforcement UNIX Prototype, USENIX Security Symposium, 1995: https://www.usenix.org/legacy/publications/library/proceedings/security95/badger.html