hckrnws
The foundations of a provably secure operating system (PSOS) (1979) [pdf]
(csl.sri.com)
130
91
by rurban
by rurban
I'd worked on the previous system, KSOS, mentioned in the article. I wrote the file system and all of the drivers, while at an aerospace company. We'd used formal specifications in SPECIAL. Nobody could prove anything about SPECIAL yet, but I wrote a compiler-like syntax and type checker, so it was at least type valid. It was a good language for writing down invariants. I used it to describe file system consistency and recovery. Another group started work on PSOS, but never got past the design stage. I managed to avoid getting sucked into that, because it looked like a death march.
SRI, which was a think tank, just did abstract designs. It was extreme waterfall. One group wrote a spec, and a contractor implemented it. This did not work too well. They did have Boyer and Moore, and those two made real progress on proof systems. I used their prover for another project, and talked to them a lot. But they were not closely associated with PSOS. Specifications in SPECIAL, which is quantifier-oriented were not compatible with Boyer-Moore theory, which uses constructive mathematics and recursive functions.
The big problem in that era was that the hardware wasn't ready for secure operating systems. KSOS was for the 16-bit PDP-11 line, and it took a cram job to make it fit. The Modula I compiler wasn't very space-efficient. Optimizations had to come out to make it fit, and the result was too slow.
Microprocessors weren't quite ready yet. Neither Intel nor Motorola had a decent MMU. The suitable target machines were all minicomputers, which were on the way out. PSOS never got far enough to pick an implementation target.
Capability-based systems work, but they create a new problem - ticket management. You have lots of tickets which let some piece of software do something, and now you have to track and manage them. It's like physical key control. It's the same reason that Windows access control lists are little used. You also still have the delegation problem - A can't do X, but A can talk to B, which can do X. Most modern attacks involve that approach.
Most of the early secure OS work was funded by NSA. NSA had an internal division in those Cold War days - the important stuff was at Fort Meade, and the less-important stuff was some distance away at FANX, an annex out by Friendship (now BWI) Airport. FANX had personnel ("HR" today), training (including the cryptographic school), safe and lock testing and evaluation, networking, and computer security. Being exiled to FANX was bad for careers. This set back the computer security work.
There was also industry pushback. The operating system testing criteria were borrowed from the safe and lock people. Something submitted for testing got two tries. First try, the evaluators told the vendor what was wrong. Second try was pass/fail with no feedback. That's how locks for vaults were evaluated. Computer vendors (there was not much of a separate OS industry yet) hated this. They eventually got a testing system where "certified labs" did the testing, and a vendor could have as many tries as they were willing to pay for.
Some good secure OSs came out of that, and passed testing. But they were obscure, and for obscure hardware - Prime, Honeywell, etc. If you dig, you can find the approved products list from the 1980s.
What really killed all that was the growth of the computer industry. In the 1960s and 1970s, the government was the biggest purchaser of computers and electronics. As the industry grew, the government became a minor purchaser with a slow update cycle, and could not get design-level attention from major vendors. There was much grumbling about this from military people, especially the USAF, as they were sidelined during the 1980s.
1. In "If A1 was the answer, what was the question," thr author pointed out that features and assurance levels were mandated together. Buyers often didn't need specific features which made it more costly and slow to develop for nothing. The festures the market demanded weren't present. So, TCSEC-certified, high security was unmarketable.
2. In a similar vein, Lipner's "Ethics of Perfectiom" talked about how it took two to three quarters to make a significant change to the VAX Security Kernel. The market was wanting major features every quarter. They couldn't afford to lag behind all the competition in velocity.
3. Another person mentioned changes in DOD (other government?) purchasing policy to order COTS products from many vendors. Those vendors were also sometimes paying campaign contributions or hiring ex-Pentagon people to be favored. Their products weren't TCSEC A1. So, corruption and supplier diversity both forced government agencies to use insecure products which made secure products less competitive.
4. Similarly, the NSA started pushing lower-assurance like CC EAL4 and later Commercial Solutions for Classified. They were also selling GOTS gear guaranteed to get their approval. In these ways, they caused a surge of low-assurance competition with high-assurance vendors.
5. They promoted, required expensive certs for, and basically killed the Seperation Kernel Protection Profile. Spending millions on something that ultinately didn't matter to them doesn't inspire more EAL6+ certifications.
So, those are the examples I remember.
Part of it is inertia, but part of it is ignorance. Enthusiasts spend tons of money and effort building another GPU enabled terminal or safe programming languages - and maybe that's fine, but I wonder what we could've accomplished if people were simply aware what a well-designed capability OS could be like, because this is literally the only OS paradigm in existence (that I know of) that's even worth any serious effort.
In a capability system, you pass resource capabilitys to subsystems. You can not use resource handles that were not passed to you just like a function can not access variables that were not passed to it (except for explicit global variables.
In ambient authority systems, as a common example, you can just blindly convert what are effectively strings into resource handles (the metaphorical equivalent of casting integers to raw pointers). Your access is mediated by a orthogonal system that tells you which resource handles/pointers you are allowed to use. That is like having a program that runtime checks every pointer access is allowed instead of just preventing you from manufacturing pointers.
You coordinate across subsystems by naming certain resources in the global ambient space in a coordinated fashion (effectively a global variable which is basically just a named memory location in the common memory space). That way the subsystem knows the global you put their parameters/resources in.
While you can still program like that, everybody now knows it is a terrible way to live. Parameter passing and local variables with explicit global variables is almost always the way to go. That same lesson should be learned for operating systems.
I don't think the authors had that in mind when they wrote this, but to look back at and imagine a future where such things had taken hold is truly scary.
"The road to hell is paved with good intentions."
Idk, just guessing
[dead]
[dead]
Rebuild everything from scratch, with AI agents. Then make them prove what they wrote.
On the contrary, the whole selling point of capability-based systems is that they're the solution to preventing these sorts of confused-deputy attacks.
[deleted]
OP is arguably the first paper that introduces ocaps. Some of the issues are discussed in "Capability Myths Demolished" https://papers.agoric.com/assets/pdf/papers/capability-myths...
Later, there were encrypted capabilities, which are signed data, like TLS certs. These get kind of bulky. And hardware support, in a few machines.
If the communications channel is not a unix domain socket and is instead something like a TCP connection, you don't have this option available to you.
You aren't always just sending bits from one process to another!
I have not studied to see how the existing capability-based operating systems solve this problem, because it seems that this is not a simple solution. If the capabilities are very fine-grained, to make certain that IPC really cannot happen, that might be cumbersome to use, while coarse-grained capabilities could be circumvented. To really prevent IPC without appropriate capabilities, a lot of the convenient features of a UNIX-like system must be forbidden, like the existence of files that can be read by any user, or directories like /tmp , where anyone can write a file.
We also have it on mobile operating systems, although some things are a rather coarse-grained.
On desktop there's just a lot of inertia. Everyone switching to a new thing is kind of impossible, and some simple add-on to existing systems would look like containers/docker.
I think capability-oriented programming languages might actually be an easier way to switch to that model, as it's much easier to adopt a new application than a new OS. E.g. with language-level capabilities (ocaps) you can implement a safe plugin system. That's pretty much non-existent now and is quite relevant - e.g. getting pwned via an IDE plugin is the reality.
So maybe a "new Emacs" can be a way to get people to adopt capabilities beyond what we already have in the browser/cloud/etc. - IDE written in a new programming stack which is inherently secure to the point of running potentially-unsafe plugins.
You still need code signing because users need to be able to grant privileges in a way that sticks across upgrades. The object they want to privilege isn't a set of files on disk but a logical app as defined by (more or less) a brand name+app name even as it changes over time.
You still need antivirus software because users can be tricked into giving capabilities to programs that appear legit but are actually malicious.
Modern operating systems (iOS, Android) are capability oriented operating systems to the extent that makes sense. For some reason there's a meme that says capabilities are a magic wand that solves all security problems, but it's not the case.
[deleted]
Wasn’t that the reason why Microsoft went allout against Java? Write once, run anywhere. JVM was a “trojan horse” and theoretically could have dominated the world.
If a binary has the capability to withdraw money from my account, I don't want that capability given to just any binary.
There are still considerations when designing parts of the system to be secure, while also making them have the functions that are desired (although a proxy capability system can be used to add arbitrary further restrictions if needed), but the core system can use proxy capabilities as the core security system.
Hashes would still be useful, but that is if you want to check that the package is the one that you intended; it does not prevent you from installing or writing whatever program you want to do, nor to make the program secure, which would be done by separate mechanisms; however, knowing that the package is the one that you intended can be one of the steps of the security, but not the main one.
However, security is not the only issue in a computer and operating system design, although it is a significant issue.
The paper adds little to TCSEC/"Orange Book"/FOLDOC publications. Yet the poster doesn't deserve all the negative karma.
On a consumer CPU/GPU/NPU, software just isn't going to be enough to fix legacy design defects. Have a great day. =3
so it seems a lot more feasible to control access and sharing between those units and write of off the intranode case as a lost cause
Likely doesn't help OS users either way. Best regards =3
A check that a whatever is downloaded cannot exceed it's capabilities.
Part of the challenge is that hardware tried and has failed to be trustworthy in implementing security boundaries. The failure appears to be because a misalignment of incentives.
I think the premise of a capability based operating system can help a lot, but for something to work in the long term the incentives need to aligned.
That's already handled by the sandbox.
The reality is that we're water meatballs, we're so easy to fool, and we need the cold calculating power of code to protect us from ourselves.
I've recently been looking into Guix SD as a solution. Its package management is designed to keep programs independent of each other, so containers are cheap and lightweight. Trying out untrusted software is as easy as `guix shell --container --pure --no-cwd [program]`, which blocks access to the network, file system, and environment variables. Right now I'm adding more advanced capability management: limits on CPU, memory, storage space, network use, etc.
There are more interesting, general, and lower level innovations out there - sure. But the mobile OSes do have improved security from some kind of permission system, VM (only partially because native components are common), one user account per app (IIRC) and such.
But even better no OS, and no attack surface. Only what you need, and properly isolated.
The IBM System/38 did this around the same time, along with its successor - the AS/400. When the AS/400 switched to POWER (or PowerPC AS), they started using standard RAM, but are still able to have a tag bit for each 16byte(?) pointer using ECC, but the instructions to do that aren't privileged. The AS/400 or "i" as it's now called is still around.
It's probably a bot nonetheless, which poses the question: why do people do that? What do they gain by posting resume comments on HN with LLM bots?
Boebert’s objection is about whether Alice can transmit unauthorized authority to Bob across a security boundary that’s supposed to prevent that flow. Your SCM_RIGHTS example is a case where the kernel is deliberately providing a sanctioned channel for authority transfer, with the kernel’s blessing, between two processes that the kernel does not consider to be on opposite sides of a mandatory access control boundary. Unix has no (*)-property. There is no “high” and “low” in the Bell-LaPadula sense on a standard Unix system. So of course the kernel mediates the transfer cleanly; it’s not enforcing any policy that would be violated by the transfer.
The moment you try to extend this to the actual case under dispute—Alice is “high,” Bob is “low,” and the security policy says high-to-low information flow is forbidden—then if the kernel refuses to deliver the fd across the boundary, the security property was enforced by the separate MAC layer, not the capability mechanism.
The conflation which is endemic in this whole debate is between “capabilities as a kernel-mediated authority mechanism” and “capabilities as a property that holds across all observable behavior of the system.” Unix file descriptors are the former. Boebert’s objection is about the latter.
Absent a misunderstanding on your part, the only way I can coherently interpret your argument is that you are arguing that the presence of kernel data structures mediating the handles somehow makes it not a capability system. That there is some background element mediating the validity of your capability representation and thus that is just a MAC layer; unless you can write the byte representation of your handle into memory and somebody else can read it out and then have access to that resource it is not a capability.
One, that allows forging capabilitys unless they are cryptographically secure against collisions.
Two, the actual essence of capabilitys is not being bearer tokens, it is non-construction. Capabilitys are derived from existing capabilitys, not manifested into existence. They have provenance. It is the OS equivalent of not allowing programs to cast arbitrary integers to pointers and thus manifesting pointers into existence which breaks basically every high level memory safety guarantee. You do not allow programs to cast arbitrary data into handles to resources which is what ambient authority systems effectively require.
The original PSOS paper makes a few claims that are in tension with one another, and then buries the lede about how that tension can be addressed. Here's a few passages, directly quoted from the paper:
> [...] there are several important pragmatic reasons why PSOS capabilities are useful as a naming and protection mechanism for supporting abstract objects.
> 1. The capability mechanism has a very simple implementation. This allows capabilities to be built into the system at the lowest level of abstraction, thus making capabilities available for the most primitive objects.
> 2. Capabilities are uniform in size, making them easy to manage.
> 3. The inclusion of access rights in capabilities permits efficient fine-grained control of access to objects.
> 4. Capabilities can be written into storage (including secondary storage) and retrieved from storage in the same manner as other data, and therefore have many of the properties of other data.
Item 4 above is the one that should draw the most attention. I don't think anyone would contest the claim that PSOS has wonderful ergonomics for managing access to resources, but the moment you want to impose a system-wide access control policy then you must add another security mechanism, completely outside the capability abstraction, that adds some friction. This is fully acknowledged by the PSOS authors, although frankly they buried the lede since this is the only thing that the secure systems folks really cared about at the time. From the section on Store permissions:
> Because simplicity of the basic capability mechanism is extremely important to achieve the goals of PSOS, any means for restricting the propagation of capabilities should not add complexity to the capability mechanism. [...] A few access rights (only one is currently used by PSOS itself) are reserved as store permissions. This is the only burden placed on the capability mechanism.
> By properly choosing the segments that are capability store limited, some very useful restrictions on the propagation of capabilities can be achieved. The restriction used in PSOS is not allowing a process to pass certain capabilities to other processes or to place these capabilities in storage locations (e.g., a directory or interprocess communication channel) accessible to other processes. [...] The store permission mechanism has been selected as primitive in the system because it achieves the desired result with negligible additional complexity or cost.
This appears as claim 8 in the summary section of the paper near the end:
> Propagation of capabilities can be restricted by use of capability store permissions. The passage of a capability to other users can be prevented by not including process store permission in that capability's access rights.
Ok, so that's the PSOS paper and it's claims. Boebert's paper--really a note, since it is a mere 3 pages--states its argument in fairly direct terms:
> The attack is made possible by an inherent attribute of pure capability machines: the right to exercise access carries with it the right to propagate that access. Thus even if an omniscient oracle correctly creates capabilities, it cannot control their further propagation. If extra mechanisms are imposed to impose this control, the machine is no longer an unmodified capability machine.
The only issue here is, perhaps, semantic: Boebert (correctly) states that an unmodified capability machine cannot provide what is considered a very basic mandatory security policy, but the PSOS folks already acknowledged this by stating that the system needs a capability store permission manager for mandatory security policy enforcement. The phrasing that they used--"the store permission mechanism has been selected as primitive in the system"--is the bait-and-switch where they treat it like part of the capability model rather than making it clear that it is an entirely distinct mechanism that must be composed with pure capabilities to achieve the (genuinely difficult) security properties that systems designers were seeking.
I suspect the horse is already dead it's worth double-tapping to make sure, so let's continue. The Myths paper muddies the waters further by making this claim after supposedly debunking Boebert:
> Boebert’s result is valid in any capability system that cannot distinguish between data transfer and capability transfer. But partitioned and type-enforced capability systems do not have this problem, and password capability systems have been engineered to avoid this problem [1, 11].
> Moreover, it has been formally verified that any capability system enforcing independent controls on data transfer and capability transfer can enforce both confinement and the *-Property [22].
We'll focus on reference [22] since that is the stronger claim here. That paper is Shapiro & Weber (2000) "Verifying the EROS Confinement Mechanism": https://flint.cs.yale.edu/cs428/doc/eros-verify.pdf
This is the motivation for their paper, which is stated unambiguously:
> Boebert [1] and Karger [9] have argued that unmodified capability systems cannot enforce even basic mandatory access controls such as the *-property. Both have proposed solutions in the form of hybrid protection architectures. Karger has also argued that unmodified capability systems cannot enforce confinement [8]. Given that EROS is a pure capability system, and that its security design rests on its ability to enforce confinement, a rigorous verification of the EROS confinement mechanism is necessary.
For some reason, they decide to respond to these claims in the Related work section, just before their conclusion, although they do address them head-on:
> Boebert [1] and Karger [9] show that pure capability systems cannot enforce the *-property. While their conclusion is correct, capability systems do provide sufficient strength to construct mandatory policies at a higher level of abstraction with reasonable performance, as has been done in KeySafe [14].
> Karger has also shown that unmodified capability systems cannot enforce the confinement policy [8]. The apparent discrepancy results from differences in term definition. Karger’s confinement policy is a mandatory access control policy: "this piece of information must not be disclosed to that set of unauthorized parties." That is, it is a policy concerning the flow of information to subjects. Lampson’s confinement problem [10] imposes a weaker constraint: information can flow out of the subsystem only through authorized channels. That is, in the Lampson definition the channels define an encapsulation boundary to be enforced.
> We believe that the KeySafe architecture can enforce both the *-property and Karger’s confinement policy, but this does not directly contradict their claims. KeySafe is a reference monitor built on top of a more primitive capability mechanism; such a reference monitor constitutes a modified capability system in the sense of Karger’s discussion.
It's worth questioning whether the Myths authors were justified in citing this paper the way they did. But either way, I think it's pretty clear that once you pin down a precise definition of the terms used in the discussion, there is little disagreement among any of these authors. However, in casual arguments this precision is lost and you end up with a situation where two things are true at the same time but people choose to talk about only one at a time and think they're winning arguments:
1. An unmodified capability machine cannot enforce the *-property or mandatory access control confinement policies.
2. Modifying a capability machine to enforce such policies (and provide proof of enforcement) is straightforward because there is a single clearly-defined interface through which the systems may be composed.
My stance is that the PSOS folks screwed up their marketing. They really do have a superior product, so to speak, but they tried to downplay the fact that it did not provide a solution to the genuinely difficult problem of enforcing MAC policies (which was really about reference monitor discipline, not capabilities or ACLs). The right pitch for ocap design is "we offer a cleaner, more compositional, more auditable substrate for authority management--which is itself a substantial contribution and worth caring about--and on top of that substrate you can build the same MAC policies you'd build on any other substrate, but with better starting axioms and clearer proof structures." That's a contribution that doesn't need to be defended against Boebert because it doesn't claim (or appear to claim) what Boebert showed couldn't be claimed.
In SeL4 it’s kinda like this: A capability is an opaque handle you can invoke to RPC into some other process or into the kernel. There’s no worry about how fine grained capabilities are because there’s no global table of permission bits or anything like that. Processes can invent capabilities whenever they want. Because caps just let other processes call your code, you can programmatically make them do anything.
Suppose I want to give a process read only access to a file I have RW access to. The OS doesn’t need a special “read only capability” type. It doesn’t need to. Instead, my process just makes capabilites for whatever I actually want on the fly. In this case, I just make a new capability. When it’s invoked I see the associated request, if the caller is making a read request, I proxy that request to the file handle I have. (Also another cap). And if it’s a write request, I can reject it. Voila!
This is how you can write the filesystem and drivers in userland. One process can be in charge of the block devices. That process creates some caps for reading and writing raw bytes to disk. It passes the “client side” of that cap to a filesystem process, which can produce its own file handle caps for interacting with directories and files, which can be passed to userland processes in turn. Its capabilities all the way down.
Or, if a program requests access to a camera, you can provide a capability with a still picture, a video file, a filter (e.g. that resizes the picture or modifies the colour) from some source (including, but not limited to, a camera), etc; this can be helpful in case e.g. you do not have a camera on your computer, or for testing.
(Other people have similar ideas, sometimes independently than I do.)
There is also a way to transmit capabilities across a network; I had thought of how a protocol would be made to do such a thing.
On the other hand, I cannot see how this approach can be scaled to something like a personal computer.
For some programs that I run, e.g. for an Internet browser, I may want to not authorize them to access anything on SSDs/HDDs, except for a handful of configuration files and for any files they may create in some cache directories.
For other programs that I run, I may want to let them access most or all files in certain file systems. Any file system that I use contains typically many millions of files.
Therefore it is obvious that using one capability per file is not acceptable. Moreover, such programs may need to access immediately many thousands of files that have been just created by some other program that has run before them, for instance a linker running after a compiler.
Assuming that a pure capability-based system is used, not some hybrid between ACLs and capabilities, there must be some more general kinds of capabilities, that would grant access simultaneously to a great number of resources, based on some rules, e.g. all files in some directory can be read, all files with a certain extension or some other kind of name pattern from some directory may be written or deleted or renamed, and so on.
Personally I think the biggest challenge is UX. The systems engineering is good, and it works just fine.
> For other programs that I run, I may want to let them access most or all files in certain file systems. Any file system that I use contains typically many millions of files. Therefore it is obvious that using one capability per file is not acceptable.
Yeah, of course! Just make a capability representing the containing directory or filesystem. Then the program is free to open and browse files within that directory, but nothing outside of it.
I agree with others in this thread. Think of the capability like a bearer token. You wouldn't make a token per file. Just make one for the directory.
IIUC one problem with such layering of capability processing is that each passed layer results in a context switch (i.e. switch of memory mappings, thrashing of caches, etc.) and its on top of the cost of passing through the kernel. In other words, you may need to pay cost of N syscalls for one multi-layered capability-based operation.
As an example, when you invoke a capability, your process hands the callee your scheduler time-slice. So its not like linux where your process yields to the scheduler. The same CPU core will handle the entire call -> process -> return computation pipeline between multiple processes.
I'm not sure how fast it ends up in practice compared to a similar system built on top of linux. I suspect a lot of the difference would come down to implementation choices. And if its still not fast enough, you can always just set up a ring buffer or something between processes to share data directly.
You're moving the burden of enforcement from the kernel to the user level ?
In an automated way, or have implemented as hand-written wrappers? And regardless, have you published the code (and/or talked about how it works) anywhere? It'd be really nice to have a gentler onramp to sandboxing things, and nix should be well-placed for it.
https://blog.invisiblethings.org/2008/09/02/three-approaches...
Or some exotic processor no one would ever sell successfully. =3
There is likely a PoC around someplace if people dig a bit. =3
It happened in 2006 and never happened after that. I would consider it as secure as it gets.
I also imagine a system where graphical programs must call a trusted system file picker to receive a fd. Receiving the capability grants permission. Ideally, Chrome could export browser history to a file, but we live in a fallen world. In any case, an alternative browser must request access through the system file picker, selecting an exported file or selecting the Chrome app data folder. It trades automatic import with user selection. The user has ultimate power, and programs make noise when doing such requests.
Please forgive me that I don't know Android system architecture. Searching tells me something about the Storage Access Framework, but I don't know if that truly meets what I describe.
from a mechanism point of view a 'capability' is really more a bearer token, the result of a policy decision, a credential that we can give to the OS to show that we have been given access without going through the rules-based machine for every operation.
[deleted]
Thus, writing a robust and secure OS may actually be possible by competent programmers in most compiled languages. Best of luck =3
I've often pondered how it was really implemented too. Best of luck. =3
"Why Multi-Threaded Code Can Sometimes Misbehave (Weak Memory Concurrency)" (Computerphile)