Object capabilities overload references

Security by capabilities is uncontroversial, and even orthodox, judging by its ubiquity in new systems. (Operating systems take an unusually long time to adopt new ideas, due to their strong network effects, so it's easy for an idea to be orthodox without being used in any popular system.) One particularly popular variant – at least in research, if not in deployed systems – is the object-capability system, in which having a capability is identified with having a reference to an object.

It's easy to see why this is popular: it elegantly exploits the existing properties of object reference to provide powerful security guarantees without doing anything to explicitly track capabilities.

Unfortunately, it tends to be incompatible with reflection, and especially with heap-traversal operations like Squeak's nextObject, which allows iterating through all objects in memory. If you can see arbitrary objects, you can see arbitrary capabilities, and the object-capability system is useless.

Elegance often means making one component do several things. Sometimes this works well, but sometimes the component can't support all the loads placed on it. I think object capabilities are a case of this. They make the object-reference graph do the work of tracking who has what capabilities, but this works only if programs can't do much to modify the graph.

E has this problem twice: not only does it use reference for capabilities, it uses ordinary message passing as its mechanism for calling between security domains, relying on lack of reflection to prevent untrusted code from doing anything more than send messages. There's no access control on messages, so modules generally expose their untrusted interfaces through proxy objects which understand only public messages. Reflection would let programs see past the proxies to the objects behind them, allowing them to send messages to internal objects and defeating the domain boundary.

Reusing basic language features for security is seductively simple, but it's dangerous — once language semantics are security-critical, it's hard to extend them safely.

If it's good enough for a real antivirus, it's good enough for a fake one

I encountered a piece of scareware recently — “Windows Vista Antispyware”, which claimed to be part of Windows and to have detected viruses and other malware, and demanded money to “remove” them.

It was slickly done. The UI looked like part of the Windows Security Center control panel, there were only a few typos and stylistic missteps, and the infections it reported were the (randomly selected) names of real malware. But it would have been more convincing if it hadn't claimed the machine was infected with the dreaded EICAR-Test-File.

Single-user Unix

There are a few basic security rules that every Unix newbie is taught, and one of them is: don't log in as root. So when I went to demonstrate something to a new coworker a while ago, and began by logging in as root, it was an awkward moment.

Was I being reckless? No, I was using Unix as a single-user OS. This was a shared machine, used for testing and little else, and there was no reason to distinguish multiple users; everyone needed root access anyway. Having multiple accounts would have been useless complexity; all we needed was a single-user system. Unix can be one, if you log in as root.

It's not a very good single-user OS, because most of its safety checks are user-based. When everything runs as root, a minor accident can destroy everything on the machine. But this machine had no valuable data on it — at worst, we'd be forced to reinstall everything, so we didn't even bother to use a shared non-root account. Safety just wasn't much of an issue. Security wasn't an issue at all; everyone who used that machine needed to know the root password anyway.

This isn't an unusual situation. Most personal computers have only a single user, and many others are shared among several users with no personal data. The user-based security model was developed for timeshared machines, which are now quite rare. Yet our orthodoxy still says user-based security is necessary, and systems without it are not to be taken seriously. Even after decades in which the most important computers have been personal ones, and even now that single-user smartphones have become the most fashionable platforms, we still judge operating systems by their ability to protect multiple users from each other, not their ability to protect a single user from malicious code. Security, we think, means inter-user security, whether or not that's a good model of the threats we face.

So I feel guilty every time I log in as root. I've been indoctrinated too thoroughly; even though I know it's not really a problem, I feel compelled to make excuses, and to point out that it wasn't me who set up that machine, and I wouldn't have done it that way. But I shouldn't. A single-user system is not necessarily a bad thing, even if it's Unix.

The worst thing about viruses is...

Today I heard someone praising Linux as a desktop OS, on the grounds that it's not very susceptible to viruses. This, he said, was good because it “saves cycles” and cuts down on reinstalls.

Not because they're a security threat. That, apparently, was not on the radar.

I think the cycles he was talking about were those taken by antivirus software, not by the viruses themselves, but the point is clear: many users see viruses as an annoyance, not a threat. Performance and convenience — those are the things that matter.

The speaker was a programmer who is involved in designing network protocols. Maybe he was only giving the reasons he thought his audience would understand. I didn't ask; I'm afraid of what the answer would be.

The inevitable interpreter

This must be the cutest code injection method ever. Hovav Shacham's paper The Geometry of Innocent Flesh on the Bone: Return-into-libc without Function Calls (on the x86) describes yet another method of injecting code into a process by clobbering its stack. The cute part isn't the title (although it did tempt me to read the paper). The cute part is that this method uses a Turing-complete language for which an interpreter already exists by accident.

It's a generalization of a well-known method called return-into-libc: if you can overwrite a function's return address, you can turn its return into a call to some existing function, such as one from a common library like libc. If you can arrange for the return address of that call to be another library function, you can call a series of them: it's threaded code, expressed through return addresses. This lets you run code of your choosing without injecting any machine code of your own, so it works even if you don't have write access to any executable memory.

But it's limited in its expressiveness, because it only calls the functions provided by the target library, and those usually don't form a complete basis for computation. The available libraries don't generally include functions for branching, looping, moving data around, and the other trivial operations that enable computation. (Languages whose standard libraries contain lots of high-order functions may be more vulnerable in this respect, but since they're not so widely used and most of them are memory-safe, they aren't very attractive attack targets.) Return-into-libc exploits an accidental threaded-code interpreter, but not a very flexible one: it can call arbitrary functions, but it can't compute much.

This paper removes this limitation by showing that the provided functions are not the only possible targets for return-into-libc. Any sequence of instructions ending in a ret can in principle be called as a function, and such sequences are common — they occur at every return site of every function! Furthermore, many such sequences perform useful operations such as arithmetic, conditionals, moves, and looping. These are the missing primitives needed to make return-into-libc Turing-complete. The necessary sequences occur quite frequently in real code, so any substantial x86 library contains a Turing-complete threaded-code interpreter.

The paper also argues that it's difficult for any x86 library to avoid accidentally providing such an interpreter. The architecture goes out of its way to provide convenient instructions for common operations, and to give the common instructions short representations. In particular it provides function return, the crucial operation for this attack, as the convenient one-byte ret instruction. Many other useful instructions are also only one or two bytes, so useful sequences can be quite short. This means they occur not only at intended return sites but as frame shifts inside other instructions, and even in literal constants. So even if a compiler carefully arranged for all return sites to be useless for return-into-libc purposes, the necessary sequences would still appear elsewhere. On x86, it's hard to avoid making the return-into-libc language Turing-complete.

It's not hard to make a Turing-complete language. Many language implementors have done so by accident, when they took languages not intended as programming languages and added convenient features like functions without realizing the implications. Many absurdly simple mathematical systems are also Turing-complete, including ones that don't look like languages, such as Fractran and Rule 110 and Conway's Game of Life. But this is the first case I've heard of where a Turing-complete language exists in the wild, without anyone intending to implement anything like an interpreter at all, as an inevitable consequence of a machine's architecture.

(Via Z-Bo on LtU. This is old news, but I hadn't heard of it, so maybe you haven't either.)