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.

I’ve been following CHERI too for a while… and I would say: not similar at all.

I think the article you linked to is all over the place. Let me summarise:
CHERI has tagged memory and “capabilities” on top of ARM/MIPS/RISC-V’s traditional paging. Each memory address is tagged to tell if it contains a “capability” (address, upper bound, protection bits) or regular data. Capabilities are used as pointers, but each memory access using one is bounds-checked and checked for privilege (read/write/execute). The tags are stored in separate memory areas instead of in a special bit in 9-bit bytes (which is what historic capability hardware did) — this makes it possible to use off-the-shelf DRAM, and traditional OS’es with only small modifications, with one address space per process as usual.

What this does in practice is adding bounds-checking to C/C++ programs, requiring only a recompile instead of having to be rewritten in a properly type-safe, memory-safe language.
Temporal safety (protection against dangling pointers) needs a system or kernel service similar to a garbage collector though, and the overhead is not negligible.

In particular they mentioned that their capabilities system makes it safe to run everything in one address space and this makes it possible to get speed ups from avoiding context switches.

I think they mean that CHERI reduces the need to break up a program into multiple isolated processes (a type of “compartmentalisation”) to achieve better security, which is how e.g. Chrome (and web browsers based on it) are designed.
So far, I’ve not seen any paper about using CHERI instead of the protection offered by traditional paging with protection but I’m sure that would be possible, and that is something that historic systems did.

What (I got the impression that) The Mill does is to put all programs in the same address range, but not in the same protection domain. Protection is decoupled from paging. I’d think that a Unix-like system on The Mill would work largely the same as on other hardware just that the memory layout inside each process would not overlap that of any other process (except for shared objects).
The Mill does have fine-grained address ranges, and support revocation so that it would be feasible to temporarily pass access to individual objects in a Portal call instead of sharing full pages like on other hardware. Revocation in the capability model can get complex and expensive, and I think that this in CHERI would also require a service scheme such as with dangling pointers.

• This reply was modified 2 years, 6 months ago by  Findecanor.
• This reply was modified 2 years, 6 months ago by  Findecanor.
• This reply was modified 2 years, 6 months ago by  Findecanor.

Thank you for adding more details to my response to OP. Some further details:

1) Any system that relies on distinguishing caps from other data must deal with C unions and the equivalent in even more typeless languages such as asm. If an integer is added to a a memory location, is that an integer sum or an address increment? Similar problems arise when pointers are not simple memory addresses, as in XOR-bi-directional lists, for example. Grants avoid this, because in grants a pointer is whatever is given as an address to the LOAD and STORE instructions, regardless of how the address was constructed. The CHERI approach is not wrong given that they chose to use caps, but there will still be programs that violate typing enough to require rewrite.

2) Yes, Mill decouples paging from protection. All running programs share the paging; each protection domain (a turf in Mill terminology) has its own rights, which can cross page boundaries.

3) Both CHERI and Mill have chosen a unified single address space, and yes, that choice greatly improves performance on general purpose codes.

4) Revoke is a problem in any protection system that allows sharing. Caps systems generally have fine-grain protection at the granularity of the individual malloc allocation, while grants systems usually have coarse grained protection at the granularity of the mmap call or file open. The fine grain of caps leads to having many more things to keep track of than are present in a grants system, leading to garbage collection, while a grants can use a single-owner model and update (and revoke) rules typical of a conventional process model.

However, revoke offers semantic issues as well as implementation troubles: just what does it mean to revoke a right? If I create an object with certain rights, and I pass it on to you with its rights so you can use it too – can you in turn pass it on to a third party? If so, and I then revoke it, is the revoke only for you an not him, or for both of you? The meanings get messy.