Reply To: How similar is Mill access protection to CHERI?

We’ve had a fairly close relationship with the CHERI project for quite a while. Both projects are addressing the same issues, just in different ways: CHERI is a capability (caps) system, while Mill is a grant system. Both want to support localized security, so that programs and program parts are limited so they can’t use or misuse data that doesn’t belong to them.

In a capability system, rights are attached to references, i.e. pointers. In a grant system, rights are attached to data, i.e. what the pointers point to. In practice both work well and provide similar security in the common usage; the difference in semantics only comes up in the details. There are also differences in costs, and part of each project has been focused on architectural ideas to bring those costs down.

Because caps carry rights indications, a caps architecture must prevent forging of pointers and their rights; you can’t just take a random integer and call it a pointer, which C programs tend to do often. Grants have no rights in their pointers, so grant pointers can be built in traditional ways.

Caps pointers need space for the rights indicators, typically needing more bits than are free in a usual pointer size. Consequently caps are usually implemented as wide pointers, which causes trouble when the pointers must be stored in externally defined data structures that expect a traditional pointer size. The problem can be somewhat avoided by adding a level of indirection. The indirection cost can be mitigated by careful caching of the indirections; this is the approach CHERI has taken. A grant pointer is the usual size, and so doesn’t have the wide pointer problem.

A pointer-connected graph structure is a good example to show the difference between caps and grant semantics. Say you want to call a function to let it work on the graph, passing a pointer to one of the nodes (the “entry node”) of the graph, and giving it the necessary rights to get the work you need done. In caps like CHERI, you must mark the pointer with rights that let the callee do its job; this may not need any more than just copying a pointer you had that already gave you those rights. This pointer lets the callee access the node it points to.

But that entry node is just one of maybe many nodes in the whole graph. It probably contains pointers to other nodes – and those have pointers to still more, forming the linked structure of the whole graph. If the callee wants to access the next node on from the entry, it gets the pointer to that node out of the entry node and follows it. But that pointer carries rights too, set up when you created the whole graph. If you set it up right then the callee can wander throughout the whole graph, following pointers at will.

In contrast, a grants system attaches the rights to the entry node, or rather to the memory address range occupied by the node. As part of the function call, you (the grantor caller) say where and which rights you are giving to the grantee callee. The granted node contains pointers, just like in the caps case, but in grants those pointers have no attached rights. To let the callee wander over the graph you must grant rights to each node in the graph.

And there is the difference: in caps, it is easy to give rights to a whole structure, but hard to give rights to only part of a structure like just the entry node; you can’t stop the callee from following the internal pointers. In grants, it is easy to give rights to a single node, but hard to give rights to a whole linked structure.

There are workarounds on both sides. In caps, you can build the inner links out of non-traversable pointers that are keyed on something about the grantee, like an unforgeable ID. In grants, you can arrange that all the nodes are allocated from a memory region (an arena) and then grant the whole arena. And there are hybrid systems.

Which is better? It’s a mass of tradeoffs, too much to go into here. Mill chose grants primarily due to the wide pointer and pointer forging problems; we wanted to be able to compile existing C programs and have them run correctly and performatively without modification. CHERI thinks they can do that with acceptable performance and not that much rewrite in a caps model. Frankly, I’d prefer caps if it can be done – but it’s not clear caps can do it in general purpose applications.