The Long Road to SELinux, Part 2: From a microkernel to mainline Linux

Table of Contents

At the end of part 1 we had, for the first time, a mechanism that could say our sentence. Type enforcement gives every program a domain and every piece of data a type, the policy is two tables, and the pipeline from Alice’s plaintext to the network is assured because the tables contain no other route. LOCK enforced it in hardware, Sidewinder enforced it in a firewall you could buy, and TIS’s DTE enforced it on an ordinary Unix. Every one of them had the same shape underneath, the thing doing the enforcing knew what a label meant, that a subject carries a domain and maybe a level, that an object carries a type, and how those combine into a decision. Even on LOCK, where a coprocessor did the deciding and the kernel did the enforcing, both halves were built for that one model. The tables were data and could be changed, but the model they filled in could not. Ask for a different kind of policy, a user attribute, a Clark-Wilson rule, levels and types combined some other way, and you were rewriting the monitor.

Getting from there to the kernel you are running took three steps, and each one fixed the problem the step before it left behind. DTOS took the model out of the kernel and found that the kernel then had to cache decisions it could not take back, Flask made the cache fast and revocable on a research kernel nobody ran, and SELinux got Flask into Linux by agreeing not to be Linux’s security model, bringing with it a policy language that could write our pipeline down for an ordinary machine and an example policy almost nobody could run.

DTMach and DTOS

DTOS is the system that took the model out of the kernel. The kernel stopped knowing what a label meant, one separate program knew instead, and that program could be replaced. It is the single design decision that separates SELinux from everything before it, and DTOS also discovered the two things that go wrong the moment you make it.

Mach

If you weren’t around for it, Mach was the operating system research project of the late eighties, a kernel from Carnegie Mellon that did as little as possible, memory, threads, and a way for tasks to send messages to each other through ports, and left everything else, the filesystem, the network stack, the Unix personality, to be built as servers running outside the kernel and talking to it over those ports. The pitch was that a small kernel with well defined message interfaces would be easier to get right, easier to distribute across machines, and easier to build unusual systems on top of. (Mach’s actual legacy is that a descendant of it is the bottom half of the kernel in every Mac and iPhone, but that came later.)

For the people who had just spent a decade on LOCK, Mach’s shape was interesting for a specific reason. The reference monitor from part 1 wants to be small and to sit between every subject and every object. In a Mach system, every interesting object, a file, a task, a memory region, is reached through a port, and every operation on it is a message. Control who may send which messages to which ports and you have a reference monitor, a small one, in the one place all the messages already go through.

DTMach

Trusted Information Systems had already built a Mach with levels on it, Trusted Mach, a product in its own right, and done a design study in 1990 for a distributed version. Secure Computing’s Distributed Trusted Mach programme, DTMach, ran from 1991 to 1993 for the Air Force’s Rome Laboratory and took that design onto the Mach 3 microkernel with the LOCK ideas added, type enforcement as well as levels, tasks and ports and memory objects all labelled, and, carried over from LOCK, a split between security servers that make the decisions and a kernel that enforces them. It ended with Secure Computing’s design and an early prototype the NSA built from it, rather than a system, and a lot of the work was simply finding out what it means to put a type on a port. It is mostly remembered for what its successor did with the split.

DTOS, and the split

The successor was the Distributed Trusted Operating System, DTOS, which Secure Computing built under an NSA contract from late 1993 to 1997, Secure Computing doing the kernel and the security server and the NSA doing the Unix server that ran on top. The idea that matters is a division of labour, and it fits on a napkin.

DTOS: object managers hold labels as opaque identifiers and enforce, one security server decides, and each manager keeps its own cache that a revocation cannot fully reach Object managers, they enforce Mach microkernel owns tasks, ports, memory SIDs: task 12, file 47, port 9 its own cache of answers (two levels) Unix server on top (Lites) owns files, the file system its own cache, kept its own way open file table, permission already used the managers never learn what SID 12 means, they only know that the server said yes or no about it Security server, it decides the policy, in one place levels + domains and types SID 12 = Unclassified, httpd SID 47 = Secret, plaintext replace this program and the managers do not change (a different model, not a different day) (12, 47) ? access vector, one bit per operation policy changed, flush the kernel's cache, pull back pages no way to reach a permission that has migrated into the Unix server, or an operation already half done two caches, no protocol between them, so no guarantee they enforce the same policy
The DTOS split. Object managers hold labels as numbers they do not understand and enforce whatever the security server answers, the security server holds the whole policy. Each manager also kept its own cache, and that is where the trouble started.

On one side are the object managers. In DTOS that is the microkernel itself and the servers that own things, the file server owns files, the kernel owns tasks and ports and memory. An object manager is responsible for enforcing decisions. When a task asks to read a file, the file server is the thing that either hands over the bytes or doesn’t. What the object manager does not do is decide. It doesn’t know what a level is, or a type, or a domain.

On the other side is one server, the security server, and it does nothing but decide. An object manager sends it a question, this subject’s label, that object’s label, and it answers with an access vector, one bit for each operation that pair is allowed, according to whatever policy it has been loaded with, and the object manager checks the bit for the operation actually asked for. The object managers know how to enforce, the security server knows what the rules are, and the interface between them is small enough to write down, two labels in, a vector of bits out.

The reason this matters is that the policy is now a separate program, and, this is the part that is new relative to LOCK, the object managers no longer know what a label means. The DTOS security server that Secure Computing built enforced levels, domains and types together (a subject’s context was a level, a domain, a user and a group, an object’s a level and a type), but nothing in the object managers depended on that. They saw a security identifier for each label, a number whose meaning belonged to the security server (not a perfectly opaque one, the top byte named the class of object, but nothing that told the kernel what a domain was), and you could write a different security server with a different policy, or a policy language, or a different model altogether, Biba or a Chinese Wall, and the file server would not need to know. A policy whose answers change over time was another matter, and it is the thing DTOS never got right.

Run the example. The web server, in the httpd domain, asks the file server to open Alice’s plaintext. The file server does not know whether to allow it. It sends the security server the two identifiers it holds, the one on the httpd task and the one on the file, the security server looks them up, finds the httpd domain and the plaintext type, finds that cell of its type enforcement table empty, and sends back an access vector with the read bit clear, and the file server refuses. The encryption program, in the encrypt domain, asks for the same file, the file server asks the same question with a different first identifier, and this time the read bit is set. Same enforcement code, same file server, and it never needed to know what a domain was.

The assurance work

DTOS was also, and this is easy to skip over, a serious attempt to do the formal side properly, because these were the people who had tried to take LOCK through A1 and had opinions about what formal assurance should and should not cost. They wrote a formal specification of the microkernel’s security policy, a study of which policies the architecture could support (the generalized security policy specification, which took policies from the literature and asked, for each one, whether DTOS could host it, levels, Biba, type enforcement and the Chinese Wall yes, pure Clark-Wilson, originator control, and any policy that has to take back a permission while it is in use, no), a composability study on how to reason about a system as a composition of its components, and a lessons learned report at the end that is unusually honest about what went wrong.

The Flask design did not come out of nowhere. It came out of a list of things DTOS had shown were possible and a shorter list of things it had shown were broken. Two items on the shorter list are what Flask was built to fix.

The two things DTOS could not do

The first is cost, and what it did to the cache. If every access check is a message to another server, then every file read, every port send, every page fault that touches a protected object pays for a round trip through the microkernel’s message passing, and on the hardware of the time Mach’s message passing was not cheap, that was one of the reasons Mach itself never took over the world. So DTOS cached. The kernel kept the answers it had been given (it had a two level cache of access vectors, with a whole apparatus of flush calls, timeouts and hints about which bits were safe to cache), and the Unix server on top kept its own answers in its own way. The lessons learned report says plainly that caching was a significant impediment to the goal of policy flexibility, because a decision cached at one moment is assumed to still be valid when it is looked up later, which by itself rules out any policy whose answers change over time. DTOS patched the kernel’s cache with flushes, a policy identifier and cache control bits, but there was no common cache module that every object manager used, and no protocol guaranteeing that all of them were enforcing the same version of the policy at the same moment.

The second is revocation, which is the same wound seen from the other side. Suppose the file server has asked, and been told yes, and remembered it, and the encryption program has the plaintext open. Now the administrator changes the policy, the encryption program has a bug, take away its access to the plaintext. The security server loads the new policy and will answer no from now on, it can tell the kernel to flush its cache, and Mach’s memory system can even pull back pages that had been mapped. What it cannot reach is the permission that has migrated somewhere else, into the Unix server’s open file table, into an operation that is already half way through. DTOS had no general way for the security server to say, the answer I gave you earlier is withdrawn, and have every object manager find every place it had acted on that answer. A policy change took effect for the kernel and for future accesses, and not reliably for what was already in flight, which in practice meant that the thing everybody wanted from a separate security server, that you could change the policy on a running system, only half worked.

So DTOS had caching but no way to keep the caches coherent, and it had revocation but no way for the revocation to reach everywhere a permission had gone. Once the decision and the enforcement are in different places, the enforcement has to hold on to decisions, for speed, and the decider has to be able to take every one of them back, for correctness, and DTOS could do the first but only sometimes the second.

Where that left things

DTOS’s record comes down to four points.

  • DTOS got the architecture right. Policy in a separate program, object managers that enforce without understanding, an interface of two labels in and a vector out. Everything after this keeps that shape.
  • It answered our example correctly, and, more to the point, the file server could have been left alone while somebody swapped the policy underneath it, which nothing in part 1 could do.
  • Caching without coherence, and revocation without reach. Those are the two things a separate security server forces you to solve, and DTOS solved neither cleanly.
  • The report Secure Computing wrote at the end of the programme in 1997 is candid about the rest. The Mach code base the prototype was built on was, in their words, too complex and poorly structured to provide any meaningful assurance, DTOS would not be pursued beyond that year, and the next kernel would be one from the University of Utah called Fluke.

The system that fixed the cache, with one cache module in every object manager and a small protocol for keeping every cache consistent with the security server, was built on Fluke.

Flask

DTOS left two problems behind, caching without coherence and revocation without reach, and Flask fixed both, in the design completely and in the code as far as the microkernel, and it is the design document for SELinux. If you read the 1999 paper and then look at the Linux kernel’s security/selinux directory, you will recognise its core, the access vector cache, the security server and the security identifiers.

Who built it

Between 1997 and 1999 a group from the University of Utah’s Flux research group (Jay Lepreau’s group, who had built a microkernel called Fluke), from Secure Computing (Ray Spencer, from the DTOS team) and from the NSA (Peter Loscocco and Stephen Smalley, the first two names on the Inevitability of Failure paper) moved the DTOS security architecture into Fluke. They called the result Flask (the paper never says what it stands for, Utah’s web page says Flux Advanced Security Kernel and Secure Computing’s report says Fluke Advanced Security Kernel, so take your pick), and published it at USENIX Security in 1999.

What the object manager is allowed to know

The first move Flask makes is to be very disciplined about what the two sides of the DTOS napkin are allowed to know about each other, because the less the object managers know, the more the policy can change without touching them.

A security context is the full label, a string that means something to the policy, in SELinux today that looks like system_u:system_r:httpd_t:s0, a user, a role, a type, and optionally a level. Anything that understands the policy can read it, but the object managers never interpret it, they handle the string only where they have to (the file server stores contexts on disk so labels survive a reboot, the network server sends them to other machines) and even then as an opaque blob. What an object manager works with is a security identifier, a SID, an integer the security server hands out to stand for a context, which the object manager attaches to every object it owns and every subject it serves. The file server knows that this file has SID 47 and that process has SID 12, and it has no idea what 47 or 12 mean. That is the point. The file server’s code is finished, it does not have to be revisited when someone adds a level to the policy.

The second move is about the shape of the question, and here Flask took what DTOS already had and made it the rule for everyone. The question is never may 12 read 47, it is what may 12 do to 47, for a given class of object (a file, a directory, a socket, a process), and the security server answers with an access vector, a bitmap with one bit per permission the class supports, read, write, execute, getattr, lock..etc. DTOS’s kernel had asked for vectors too, what is new is that every object manager asks the same way, through the same small interface, which matters because of what comes next.

The cache

Every object manager in Flask has an access vector cache, the AVC. When the file server needs to know whether 12 may read 47, it looks in its cache for the entry (12, 47, file), and if it is there it reads the bit and is done, no message, no security server, a hash lookup. If it is not there it asks the security server (in Flask a separate server, reached by a message, which is why the cache matters so much), gets the whole access vector back, stores it, and from then on every question about that pair of labels and that class is answered locally. A running system asks the same few thousand questions over and over, this web server, these web pages, read, read, read, so the cache hit rate is extremely high, and the cost of the always invoked check drops to something you can afford on every file operation. That is problem one.

Flask: every object manager has an access vector cache, misses go to the security server, and a revocation carries a sequence number, removes the entry, runs a callback over migrated permissions and is acknowledged File server (an object manager) access vector cache (AVC) (12, 47, file) read=0 seq 41 (31, 47, file) read=1 seq 41 (52, 88, file) read=1 seq 40 a hit answers here, no message sent migrated permissions open descriptors, mappings, each with a callback that knows how to re-check it Security server the policy SID 12 = httpd_t, SID 47 = plaintext_t SID 31 = encrypt_t remembers who it told what, a separate server, reached by message miss, ask vector + seq A policy change takes read on (31, 47) away revoke (31, 47) read, seq 42 sent to every manager that might hold it 1. the AVC drops the entry, any answer older than seq 42 for that pair is refused from now on 2. the callbacks run, the encryptor's open descriptor is re-checked and marked revoked 3. the manager tells the server it is done, the change counts as made only when all have The sequence number is there because messages cross, an answer computed just before the change could arrive just after the revocation and quietly bring the permission back.
The Flask cache and the revocation protocol. Hits are answered locally, misses go to the security server, and a revocation carries a sequence number, empties the entry, runs the callbacks over the permissions that have already been used, and is acknowledged before the change counts.

The revocation protocol

Problem two is what happens to all those cached answers when the policy changes, and the Flask answer is a small protocol that is the most elegant thing in the whole design.

The security server keeps track of which permissions it has handed to which object managers. When a policy change takes one of them away, it sends a revocation to every object manager that might be holding it, naming the pair of SIDs and the permissions, each object manager’s AVC removes them from its cache and does whatever else it has to (more on that in a moment), and then tells the security server it is done, and only when every one of them has answered does the security server treat the change as made. The sequence numbers are there because those messages can cross, an access vector the security server computed just before the change can arrive at the object manager just after the revocation, and if the AVC cached it the revoked permission would quietly come back, so every answer is stamped with a sequence number, the revocation carries a newer one, and an AVC never accepts an answer older than the last revocation it has seen for that pair. It is a small protocol, small enough that they proved it correct with a theorem prover, and it deals with the cache.

It does not deal with permissions that have already been used, and this is the part DTOS could only manage for memory, where Mach’s own machinery could pull back a mapping, and knew it could not manage anywhere else. The encryption program didn’t just get a cached yes, it opened the file, and it is holding a descriptor, and it may have mapped the file into its memory, and none of those things will ask the AVC again on their own. Flask calls these migrated permissions, the permission has migrated out of the reference monitor into some piece of state in the object manager, and the protocol handles them by having each object manager register with its AVC a callback that knows how to find and revoke the state that depends on a vector. When a revocation arrives and a vector is invalidated, the callbacks run, the file server walks its open descriptors and re-checks them against the new policy, and the encryption program’s next read on a file it is no longer allowed to read fails. The security server does not need to know what a descriptor is, and the file server does not need to know why the policy changed.

What the prototype could not do everywhere was stop an operation already under way. The paper says the file server could not interrupt an operation in progress, and that complete revocation, in-flight operations included, was implemented only in the microkernel, where Fluke’s atomic, restartable kernel calls made it tractable. So in the file server the change reached the descriptors but not a read that had already passed its check.

Labelling decisions

There is a third question Flask makes the security server answer, and it is easy to overlook because it isn’t an access check. When a new object comes into existence, when the encryption program creates the ciphertext file, or when Alice’s shell executes the encryption program and a new process image appears, somebody has to decide what label the new thing gets. In DTE the answer was a rule baked into the kernel, files get the type of their directory, processes get the domain of their entry point. Flask makes it a policy decision. The object manager asks the security server for a labelling decision, given the creating subject’s SID and the parent or program’s SID and the class, what SID should the new object have, and the security server answers from the policy. That is how the encryption program’s process ends up in the encrypt domain without the file server or the process manager knowing anything about domains, the policy said so, and it is how a file written by the encrypt domain into a spool directory can be labelled ciphertext rather than inheriting the directory’s type. (The same machinery handles polyinstantiation, where the security server gets to say which of several instances of an object, a per level /tmp for instance, a given subject should see.) The prototype’s own security server enforced levels, types, identities and roles all at once, with the level logic written in code. The point was never that Flask is type enforcement, it is that the object managers no longer care which of those the policy is.

Running the example

The web server runs with SID 12, which the security server knows stands for a context with the httpd_t type in it (these are SELinux style names, the paper never published Flask’s policy language, so treat them as names and not as Flask source), and Alice’s plaintext file has SID 47, which stands for plaintext_t. When the web server asks the file server to open the plaintext for reading, the file server looks up (12, 47, file) in its AVC, doesn’t find it, asks the security server, and gets back an access vector with the read bit clear, stamped with the current sequence number, which it caches before refusing the open, so when the attacker sitting in the web server tries again the refusal comes straight out of the cache without a round trip. The encryption program runs with SID 31, encrypt_t, because when Alice’s shell executed it the process manager asked for a labelling decision and the policy said transition, and when it asks to open the plaintext the file server misses on (31, 47, file), asks, gets the read bit set, and allows and caches it. When it creates the ciphertext file there is another labelling decision, ciphertext_t, and the sending program, in send_t, may read that and write to the network, and may not read plaintext_t, by the same mechanism and the same cache.

Now the administrator decides the encryption program has a bug and removes its read access to plaintext_t. The security server changes its policy, bumps the sequence number for the pair (31, 47), and sends the file server a revocation of read for that pair. The file server’s AVC drops the permission and runs its callback, which finds the open descriptor the encryption program is holding, re-checks it, and marks it revoked, and then the file server tells the security server it is done. The encryption program’s next read fails (a read that was already past its check when the revocation arrived would have finished, that is the in-flight case above), and nothing in the file server’s code mentions plaintext, encryption, or the reason for the change.

Where that left things

Flask’s record comes down to three points.

  • Flask had the architecture. Policy separated from mechanism with a clean interface between them, labels the mechanism doesn’t interpret, a cache that makes the always invoked check affordable, a protocol that keeps the caches consistent when the policy changes, and labelling decisions that let the policy, rather than the kernel, decide what new things are called.
  • All of those are in the kernel you are running today, with one change of method, Linux mostly re-checks an open file’s permission each time it is used rather than chasing it down with a callback.
  • What Flask didn’t have was a kernel anybody would actually run. Fluke was a research microkernel built to try out ideas, it had partial POSIX support, servers that the paper itself calls not robust, benchmarks that took more than twice as long as FreeBSD on the same hardware, revocation callbacks that were only complete inside the microkernel, and there was never a complete public release.

Nobody was going to deploy it or write software for it, and as far as the Inevitability of Failure argument is concerned, an architecture that only runs on a research kernel proves nothing about the systems people actually use. If the point was to show that mainstream operating systems could have mandatory access control, somebody had to put Flask into a mainstream operating system, and the NSA picked Linux, because, in the words of its own FAQ, of its growing success and open development environment, and because it would give the work the widest possible review. The first public release of Security-Enhanced Linux went out in December 2000, as a patch to a 2.2 kernel, and getting it from there into the kernel everybody downloads took until the end of 2003, and a change in how Linux accepts security code at all.

SELinux enters Linux

SELinux got into Linux by agreeing not to be Linux’s security model. The NSA offered the kernel a complete mandatory access control architecture, Linus Torvalds declined to choose it, or anything else, and asked instead for a set of hooks that any security model could sit behind, and SELinux went into the mainline kernel in 2003 as the first mandatory access control module behind them. That compromise is the reason SELinux is in the kernel you are running, and the reason that kernel still ships without any policy of its own. What came with it was a policy language that could write our pipeline down for an ordinary Linux machine, and an example policy that confined everything and that almost nobody could run.

The patch

On the 22nd of December 2000, Peter Loscocco announced on the Linux kernel mailing list that the NSA’s Information Assurance Research Office was making a prototype of a security enhanced Linux available on its web site, under the GPL. The architecture, the announcement said, had been implemented for Mach and for Fluke and had now been integrated into Linux, as a patch to the 2.2.12 kernel, for x86 only, tested only on Red Hat 6.1, with a set of configuration files as an example of a general purpose security policy. Slashdot ran it the same day as the NSA releasing a high security version of Linux, which made a better headline than a description.

The announcement itself was much more modest. The NSA was not presenting a complete security solution for Linux, it was presenting an example of how mandatory access controls that can confine any process, the superuser included, could be added to Linux, and it was not asking for the patch to go into 2.2, or even 2.4, only offering it as a starting point for discussing the 2.5 series. The paper describing it a few months later lists, among the policies it was meant for, restricting a web server to only authorized data and guaranteeing that data is processed as required, which are our rule 2 and rule 1. The example policy came from NAI Labs, which was what the research group at Trusted Information Systems had become when Network Associates bought TIS in 1998, and it drew on that group’s own Domain and Type Enforcement work, the DTE of part 1.

Putting Flask into Linux changed its shape in one important way. Linux is not a microkernel, there is no file server or process manager to act as object managers, there is one kernel with the file, process, socket and IPC code all inside it, so those subsystems became the object managers, and the security server, which in Flask was a separate server reached by a message, became, in the words of the paper that described the port, merely a kernel subsystem. The access vector cache came along too, one for the whole kernel, and what got cheaper was the miss, a question the cache could not answer was now a function call rather than a message to another server.

Two more pieces came across from Fluke and had to be fitted to Unix. Files need labels that survive a reboot, and Linux had no extended attributes to keep them in, so the patch kept Flask’s persistent SIDs, a small integer standing for each label with a table in each filesystem mapping the numbers to security contexts, and stored each file’s number in a spare field of its ext2 inode on disk. And programs that set or read labels need a way to ask, so, as on Fluke, the patch added variants of the ordinary system calls that carry a label (execve_secure runs a program in a context you name). The checks themselves were written straight into the kernel code wherever a process touches an object, the obvious thing to do for a patch maintained outside the kernel, and about the worst for one that hopes to be merged. By the spring of 2001 the patch had moved to 2.4, and the cost was modest, the cheapest system calls got a third slower (a one byte read or write went from 1.45 to 1.93 microseconds), but a kernel compile and a web server benchmark showed no significant difference, before anyone had optimized anything.

Linus asks for hooks

The NSA made its case at the 2.5 Kernel Summit, in San Jose on the 30th and 31st of March 2001, where Loscocco gave the talk. According to Rik Farrow’s report, the talk was frank that the implementation focused on enforcement, not policy, and the session ended with Linus saying that he liked the code he had seen, that there were many security projects under way and he did not want to have to choose between them, and that if a function call could replace each section of code the NSA had added it might be acceptable, since people who did not want the security could replace the call with a function that simply returns. Loscocco told Farrow later that he was disappointed he didn’t get more support.

A week later Linus wrote down what he meant, in an email that was still being quoted on the kernel mailing list two years later. He wouldn’t mind better infrastructure in the kernel for things like SELinux, he said, but nobody agreed on the right solution, he was not interested in any one approach, TE, DTE, MLS or whatever, and what he could accept was either true simplicity, which the plain euid == 0 check is, or something truly generic, where SELinux would be just a matter of loading the SELinux module. He even sketched it, a structure full of pointers to security check functions (SELinux, he noted, had about 140 points it wanted to hook into), an opaque security ID, which only the module understands, on the process, the file, the inode and the directory cache, and a kernel with no policy at all that simply calls the security procedure, which might choose to fail the operation (he suggested -EFASCIST as the error code). He was not interested in the fight between the security people, he wanted the indirection that gets him out of that picture, and the market could fight out which policy actually ends up being used.

The next day he added the part that made it buildable. Not at the system call level, which is too intrusive and costs cycles on the path he cares most about, but on the kernel’s own objects, processes, files, directory entries, inodes, which he guessed meant five to ten kinds of object, maybe two hundred places to intercept, and a patch of a few thousand lines. And the natural default policy, the one you get with no module loaded, was the one Linux already had, capabilities.

This is Flask’s own argument turned on Flask. Flask pulled the policy out of the object managers so that they would not care which policy they were enforcing, and Linus asked for the same separation one level up. The NSA had spent the better part of a decade arguing that the code doing the enforcing should not know what a label means, and the answer from the kernel’s maintainer was that the kernel should not even know which security model it is carrying labels for.

The Linux Security Modules

Crispin Cowan, chief scientist at WireX, whose Immunix distribution had security extensions of its own that it wanted in the kernel, announced the Linux Security Modules project on the 10th of April 2001, with the explicit goal of producing something the mainline would accept, and its mailing list went from nothing to 202 subscribers in the first day. It became a joint effort, WireX, the SELinux team, SGI and the Janus project, plus individuals like Greg Kroah-Hartman and James Morris, and the 2002 paper that described the result lists Linus’s requirements as three things the framework had to be.

  1. It had to be truly generic, so that using a different security model was merely a matter of loading a different kernel module.
  2. It had to be conceptually simple, minimally invasive and efficient.
  3. It had to be able to support the existing POSIX capabilities logic as an optional security module.

The framework that came out of it is simple. Just before the kernel acts on one of its own objects, a hook calls a function through a table, and the function answers part 1’s reference monitor question, may this subject perform this operation on this object. The process, the inode, the open file and the other kernel objects that matter each got an opaque security field, a pointer the kernel never looks at, where a module can hang its labels. The hooks are mostly restrictive, they come after the kernel’s own checks and can refuse what the kernel would have allowed, and the one place a module gets a say in something the Unix check turned down is capable(), the question of whether a privileged process may override it. That is also what let the capabilities logic move out into an optional module, as Linus had asked. Stacking several modules was left for the modules to sort out, the measured cost was a few percent, and the framework went into the development kernel in July 2002.

SELinux was rewritten to sit behind the hooks while this was going on, at NAI Labs, by Stephen Smalley, Chris Vance and Wayne Salamon. The checks that had been written into the kernel moved into hook functions, the labels moved into the opaque fields, and the report on the port recommends always building SELinux into the kernel, because a module loaded after boot cannot always work out the right labels for the processes and files that already exist. The persistent SIDs had to come out of the ext2 inode too, since every file hook lives in the generic filesystem layer and none reaches into ext2 itself, so they went into an ordinary file until extended attributes made it into the kernel.

Not everybody was pleased. Christoph Hellwig spent 2002 and early 2003 objecting on the kernel mailing list that the hooks were all over the place, cost performance and code size, and served only one module, SELinux. His patch removing the catch all system call the framework had added for modules went in at the end of 2002, and programs ended up talking to SELinux through a small filesystem of its own, selinuxfs.

The merge

Smalley posted the SELinux module for comment on the 1st of May 2003, while patches it needed were still waiting, among them the handlers that let ext2 and ext3 store security labels as extended attributes. The last missing hook went in at the start of July, Andrew Morton took Smalley’s patch for 2.6.0-test1 into the -mm tree in the middle of the month, and it went from there into Linus’s tree, so that 2.6.0-test3, released on the 8th of August 2003, was the first mainline release with SELinux in it. Linus’s release note gave it one sentence, that merging the SELinux security architecture also grew the patch, even though it may not be all that noticeable for most normal users, and 2.6.0 went out on the 17th of December with an announcement that did not mention it at all.

So by the end of 2003 Flask’s design was in the kernel almost everybody runs. A file’s label was an extended attribute called security.selinux holding the context as a string (in 2.6.0 only ext2 and ext3 could store one), the whole module was about 12,000 lines of kernel code, the security server and the cache some 7,000 of them, behind 132 hooks, and Linus’s guesses had held up, a few thousand lines of framework, eight kinds of kernel object carrying a security field, and about two hundred places where the kernel calls a hook. What it did not have was a policy. The kernel does not ship one, then or now, and until something loads one it allows everything. It takes a compiled policy from user space through a file in selinuxfs. Its configuration help in 2.6.0 told you that you would also need a policy configuration and a labelled filesystem, pointed you at the NSA for an example, and recommended the development option, under which the kernel booted in permissive mode, logging everything and denying nothing, unless you asked for enforcing.

The policy language

A policy for that security server is a text file in a small declarative language, the same one, with additions, since 2000, and most of the work is done by the type enforcement statements, part 1’s tables written out one cell at a time. A type declaration names a type and gives it attributes (domain, file_type, exec_type..etc.) that other rules can use for whole groups of types. An allow rule is one cell of the domain definition table, allow httpd_t httpd_config_t:file read says that a process in httpd_t may read a file of type httpd_config_t. A type_transition rule is one of Flask’s labelling decisions, a process in this domain that executes a program of this type moves into that domain, a file this domain creates in a directory of this type gets that type. And a neverallow rule is an assertion that a cell must stay empty, which the compiler checks against the whole policy and which never reaches the kernel at all.

Around those sit roles and users, which decide which domains a person can end up in (an SELinux user is separate from the Unix uid, so su to root does not change who you are to the policy). There are also constraints, rules that can refuse what the allow rules permit (the example policy uses them to stop a process changing its SELinux user or role unless its domain is trusted to), and contexts for things that are not files, such as network ports (port 80 is http_port_t). File labels come from a list of path patterns that ships with the policy, file_contexts, which never goes into the kernel.

The example policy was mostly written in m4 macros that each expand into a handful of rules. domain_auto_trans(a, b, c) says that a process in domain a that executes a file of type b moves into domain c, and expands into the type_transition plus eight allow rules that make the move actually work (a may execute b, c may be entered through b, the two may use each other’s file descriptors and c may tell a when it exits..etc.). And it was built in one go. The whole tree was concatenated and expanded by m4 into a single policy.conf, close to 30,000 lines by the end of 2003, the compiler, checkpolicy, turned that into a binary for the kernel, and a program called setfiles walked the disk writing each file’s label from file_contexts into its extended attribute. So a policy was one thing for the whole machine, and any change, a new user, a new domain, a single allow rule, was an edit to the source tree and a rebuild of all of it.

How the 2003 example policy reached the kernel: the source tree is expanded by m4 into policy.conf, compiled by checkpolicy, which also checks the neverallow assertions, into policy.15, and loaded into the security server, while setfiles writes a security.selinux label onto every file from the file contexts The policy, from source tree to kernel the example policy's tree macros/ domains/program/ 25 built, 104 in unused/ rbac users constraints assert.te pipeline.te, ours m4 expands the macros policy.conf about 30,000 lines checkpolicy compiles it and refuses any rule that breaks a neverallow policy.15 a binary, loaded into the kernel's security server The labels, from file contexts to disk file_contexts a path pattern and a label /home/alice/secret(/.*)? plaintext_t setfiles make relabel walks every file on the disk an extended attribute on every file security.selinux = system_u:object_r:plaintext_t read when the kernel loads the inode One policy for the whole machine. Adding the pipeline means adding a file to the tree and rebuilding all of it, and a program the tree says nothing about runs with whatever the domain that started it may do.
Building the 2003 example policy. The whole tree is expanded into one policy.conf, checkpolicy compiles it and checks every neverallow on the way, and setfiles writes a label onto every file from the file contexts.

Running the example

Here is our pipeline as a file you would have dropped into the example policy’s domains/program directory at the end of 2003, with its file contexts. It compiles against the NSA’s policy 1.4 from that December, with the web server’s domain switched on, and it is only the part that says what we want, a domain that actually runs needs more (the terminal it prints to, the directories on the way to Alice’s files..etc.), which you found by running the program and reading the denials.

# domains/program/pipeline.te
type plaintext_t, file_type;
type ciphertext_t, file_type;
type encrypt_exec_t, file_type, exec_type;
type encrypt_t, domain;
role user_r types encrypt_t;

# Alice's shell runs the encryptor and lands in encrypt_t
domain_auto_trans(user_t, encrypt_exec_t, encrypt_t)
uses_shlib(encrypt_t)

# Alice writes the plaintext, the encryptor may only read it
create_dir_file(user_t, plaintext_t)
r_dir_file(encrypt_t, plaintext_t)

# whatever the encryptor creates in the spool is ciphertext
file_type_auto_trans(encrypt_t, var_spool_t, ciphertext_t)

# the sender is a daemon that reads ciphertext and sends it
daemon_domain(send)
allow send_t var_spool_t:dir r_dir_perms;
r_dir_file(send_t, ciphertext_t)
can_network(send_t)

# rules 1 and 2, checked by checkpolicy on every build
neverallow ~encrypt_t ciphertext_t:file { create write append };
neverallow ~{ user_t encrypt_t } plaintext_t:file read;
neverallow httpd_t plaintext_t:file read;

# file_contexts/program/pipeline.fc
/home/alice/secret(/.*)?    system_u:object_r:plaintext_t
/usr/bin/encrypt            system_u:object_r:encrypt_exec_t
/usr/sbin/send              system_u:object_r:send_exec_t

It is part 1’s two tables with names on them. domain_auto_trans is the transition table, the only way into encrypt_t is to execute a file labelled encrypt_exec_t, and doing that from Alice’s shell moves the process there whether it wants to move or not. The macros after it are cells of the definition table, file_type_auto_trans is Flask’s labelling decision (what the encryptor creates in the spool is ciphertext_t, not the directory’s type), and daemon_domain declares the sender and has the init scripts start it in send_t. The last three lines are what part 1 left to a person reading the table, nothing but the encryptor may create or write ciphertext, nothing but the encryptor and user_t, the domain every ordinary login lands in, may read plaintext, and the web server may never read plaintext. Each time the policy is built, checkpolicy checks them against every rule in it, macros expanded and attributes resolved. Against the December 2003 policy all three hold, and one line anywhere in the tree letting httpd_t read plaintext_t makes the compiler refuse to build the policy and name the rule that broke it. It also refuses the moment you move two of the contributed modules across, backup and quota, because both may read every file on the machine, which is what a backup program is for, and the policy cannot have that and our rule at the same time until somebody decides which one gives way.

At run time the kernel sees only the compiled tables, and our bad day goes like this. The attacker is running code inside the web server, as root, and asks to open Alice’s plaintext. On the way to a file the kernel checks every directory it passes through, and our file contexts label Alice’s secret directory itself plaintext_t, so the first check that matters is whether the web server may search that directory. The ordinary Unix check runs first, the directory is Alice’s, so it asks whether root may override its permissions, and under SELinux even that is a question for the policy, dac_override is a permission a domain has or doesn’t, and the example policy’s Apache domain has it. So the Unix check passes, and the kernel calls the hook, which with SELinux loaded is selinux_inode_permission. It takes the SID of the process and the SID of the directory and asks the access vector cache about httpd_t, plaintext_t and the directory class, the cache misses, the security server is called like any other function, finds no allow rule, the answer is cached with the search bit clear, and the open fails with EACCES before the file’s own read check is ever reached.

One request in Linux 2.6.0: the web server's open call is checked at every directory on the path, and at Alice's plaintext_t directory it passes the Unix check, reaches the LSM hook, and SELinux's hook function, access vector cache and security server, Flask's three pieces now running as ordinary kernel code, refuse the search before the file is reached Linux 2.6.0, the web server asks to read Alice's plaintext the web server, running as root in httpd_t open("/home/alice/secret/plaintext") the kernel checks every directory first, and /home/alice/secret is plaintext_t too the ordinary Unix check runs first, on each directory owner, group and mode, and root may override them passes, the policy lets httpd_t use root's dac_override, a refusal here ends it the LSM hook security_inode_permission() the kernel knows a module registered for the hook, not which one the SELinux module selinux_inode_permission() takes the SID of the task and the SID of the directory the directory's comes from its security.selinux attribute Flask's object manager, now a function inside the kernel access vector cache, one for the whole kernel (httpd_t, plaintext_t, dir) miss Flask kept one per object manager, here every hook shares this one security server, called like any other function decides from policy.15, loaded through /selinux/load Flask's was a separate server, reached by sending it a message no allow rule, search denied, open() fails with EACCES the file's own read check is never reached, and the denial is cached for the next try Being root gets the request past the Unix check and no further, the hook can only take access away.
The web server’s request on Linux 2.6.0, stopped at Alice’s plaintext_t directory before it reaches the file. The Unix check runs first, the kernel calls whatever is behind the hook, and Flask’s three pieces, the object manager, the cache and the security server, are now functions in the same kernel.

There are two catches, and both belong to the policy rather than the mechanism. The first is Alice. In the example policy every ordinary login lands in user_t, Alice’s and everybody else’s, and user_t, like every user domain the policy’s macros generate, may use the network. The second assertion has to exempt user_t because Alice writes the plaintext, so as far as the policy is concerned every other user’s shell may read it too (only the Unix permissions keep them out), and Alice herself can read it and open a socket, and cat piped into a network program is exactly what rule 1 forbids. Making rule 1 hold for her too means taking the network away from her login, which is one line in the macro every user domain on the machine is built from, the administrator’s included, or giving her a domain of her own, and neither stays inside the pipeline’s file. The second is the web server. The February 2001 example policy had no domain for one at all (it declared a type for the web port and, in its report’s words, no domain was allowed to bind it), and every domain in it could read every user’s home directory, so a plaintext left with the ordinary home directory type would have been readable by anything. When an Apache domain did arrive, that summer, it could read every file under /home as well. By December 2003 there was a much tighter Apache domain, in a directory called unused, one of 104 files a default build left out next to the 25 it built, so which programs on your machine had a domain depended on which files you had moved across, and on what you had written yourself.

Closing Points and Remarks

Several points are worth noting though

  • Flask went into Linux almost intact, its security server and cache turned into ordinary kernel code reached by a function call, which made a check on every access cheap enough for a general purpose kernel, and it got in on the condition that it would not be Linux’s security model. The kernel has hooks, 132 of them in 2.6.0, and SELinux is one module behind them, which is why the same kernel later carried AppArmor, Smack and the rest, and why it ships no policy of its own.
  • The language could say our sentence twice, as allow rules and transitions that the kernel enforces on every access, and as neverallow assertions that the compiler checks against the whole policy every time it is built. In part 1 that second check was a person reading a table, here it is a program.
  • The only policy anyone had to start from was the NSA’s example, and it said what it was. Smalley’s guide to configuring it says the example concentrates on protecting the base system, confining system processes and protecting administrators, and that trusted pipelines and data confidentiality, which is to say our example, can be achieved but are not demonstrated in it.

The mechanism held up. From the summer of 2002 Russell Coker, who was porting SELinux to Debian and contributing a good deal of the example policy, ran machines on the internet that let anyone log in as root, with SELinux as the only protection, and the problems visitors found (a readable /etc/shadow, a writable /dev/nvram) were gaps in the policy and its labels, which he closed one by one. The policy was the part nobody had finished. Smalley’s guide tells an administrator to start in permissive mode, exercise the system, collect the denials and decide which to turn into allow rules, and to look for daemons left in the init scripts’ domain because nobody had written them one. A contributed script, newrules.pl, could turn the denials into allow rules for you, and in December 2003 it moved into the SELinux tools as audit2allow. Coker had estimated in 2002 that at least 500 more policy files would have to be written before most people could simply pick the parts they needed, and at the end of 2003 the NSA’s own FAQ still said the example configuration was not yet complete. So the mechanism worked, on every access, and the policy everybody started from was one its own authors expected you to finish, which almost nobody could.

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