Capability Machines and the CHERI Bounds Encoding

Every mitigation of this kind works around the same structural fact: in a conventional address space, a pointer is an integer, and an integer carries no information about what it may point at. A bounds check needs a length, which means the length must be stored somewhere the check can find it, and every scheme so far has either duplicated it in a descriptor, hidden it in a side table, or encoded it in spare bits. A capability architecture takes the remaining step: make the pointer itself a structured object that carries its bounds, its permissions, and an unforgeable identity.

The design is not new. Capability-based addressing was implemented in the 1960s and 1970s on machines whose word formats reserved bits for a tag and a set of access rights. What is new is that the idea has been reworked to fit a 64-bit load-store architecture without changing the instruction set beyond a set of additions, which is the CHERI project’s contribution.

A pointer with a type

A CHERI capability is a 128-bit value with a 64-bit address, a bounds pair, permission bits, and a tag bit that the hardware maintains and software cannot set. The tag is the load-bearing part: only values produced by legitimate capability operations carry it, and an attempt to construct a capability by writing the 128 bits into memory and loading them back produces an invalid value, because the load path clears the tag when the stored bits do not match what the hardware recorded.

128-bit capability
+--------+--------------+------------------+--------------+
| tag(1) | permissions  | bounds base/top  | address (64) |
+--------+--------------+------------------+--------------+

The permissions are fine-grained rights: load, store, execute, and a handful of others covering sealing and system registers. Bounds are an inclusive base and an exclusive top, and every dereference checks that the address lies within them. The check is a pair of comparisons in the load-store path, performed by the hardware on every access, with no shadow table and no compiler instrumentation.

The important property is transitivity. A capability that permits narrowing can produce a smaller capability, and the hardware enforces that the result’s bounds are a subset of the source’s. There is no operation that widens bounds. A program that holds a capability for one object cannot manufacture one for an adjacent object, because the arithmetic that would compute the adjacent address either stays within the current bounds or produces a value whose tag is cleared. The result is that spatial safety is a property of the address space rather than of the code that uses it: a wild write through a corrupted pointer faults, and the fault is attributable to the instruction.

Why the bounds are compressed

The obvious encoding, two 64-bit bounds plus a 64-bit address plus permissions, is 208 bits, which is more than a 128-bit register holds and far more than a cache line wants to spend per pointer. CHERI’s answer is to exploit alignment. Because allocations are aligned to a power of two, the low bits of the base are zero and the low bits of the top are determined by the base’s alignment, so the bounds can be stored as a base plus a length in a floating-point-like format: a few exponent bits that give the alignment, and a set of mantissa bits that give the offset.

The compression is exact whenever base and top fall on the grid the chosen exponent implies, which power-of-two sizes and alignments satisfy and other objects satisfy only by luck. For an object of 4096 bytes aligned to 4096, the bounds fit with few mantissa bits. For an object of 100 bytes the bounds cannot be represented exactly, and the hardware rounds outward: the representable bounds enclose the object, and the rounding is upward on both ends, so the capability’s bounds may be slightly larger than the object. The rounding is bounded by the precision of the mantissa, and it means a small overrun at the very end of a heap object can fall inside the capability’s bounds and escape detection.

This is the same granule problem that memory tagging has, in a different form. Tagging’s blind spot is the slack in the last granule; the capability’s blind spot is the rounding slack in the compressed bounds. The capability’s advantage is that the slack is a property of the object’s size and alignment rather than a fixed 16 bytes, so large aligned objects have exact bounds and small odd-sized ones have a few bytes of slack.

The tag bit is what makes the encoding unforgeable. Storing a capability to memory writes the 128 bits, and the hardware records whether the value was a valid capability at the time of the store. A load from a location the hardware has not seen a valid store to returns a value with the tag clear. A program that overwrites a capability in memory with bytes from an overflow, the classic function-pointer overwrite, produces a value that faults when it is used as a pointer, because the tag is gone. The corruption still happens; the resulting value is inert.

The compartment model

Spatial safety is only half of what a capability machine offers. The other half is that capabilities can be withheld, which turns the address space into a set of compartments.

A conventional process has one address space and one set of permissions: every thread can read and write every mapped page, subject to page-level protection. A capability machine can give a library a capability for its own data and nothing else, so a bug inside that library cannot reach the rest of the process’s memory even though it runs in the same address space with the same privilege level. The library’s code receives a capability for its code region, data capabilities for its globals and heap, and no capability for anything else. A wild pointer in the library is a wild pointer within a region it already owns, or a fault.

The mechanism that makes this practical is the sealed capability. A sealed capability has its permissions reduced to a single operation, enter, and cannot be unsealed except by a holder of the matching seal. This is how a compartment’s entry point is exposed: the caller gets a sealed capability that can only be invoked, and the callee decides whether to unseal it and grant further rights. The pattern is the object-capability model applied at instruction granularity, and it gives a way to build a call interface whose authority is exactly what the callee chooses to delegate.

The cost is the discipline. Every pointer that crosses a compartment boundary must be a capability with the right bounds and permissions, and code that assumed it could pass an arbitrary integer as an address must be rewritten. C’s model of a pointer as an integer that can be cast, incremented, and compared is incompatible with a type that carries provenance; the language needs a way to express “this pointer came from that object”, which is why CHERI C compilers implement provenance-aware semantics for pointer arithmetic rather than treating pointers as integers.

What it costs and what it does not solve

The hardware cost is register pressure and memory footprint. A capability is twice the width of an address, so every pointer in a structure doubles, and a program with a pointer-heavy data structure sees its memory footprint grow substantially. Registers are 128 bits wide or capabilities are held in pairs, which reduces the number of pointers that fit in the register file. The bounds checks themselves are cheap, two comparisons in parallel with the address computation, but the tag maintenance on load and store is not free, and the tag-clearing rule on stores requires the store path to know whether the value being stored is a capability.

It does not solve temporal safety. A capability for a freed object remains valid as a value: its bounds still describe the region, its tag is still set, and dereferencing it reads whatever the allocator has put there. Making free invalidate capabilities requires either a revocation mechanism that walks every copy, which is expensive without hardware support for reverse maps, or a generation scheme layered on top, which is the same problem memory tagging solves with its retag-on-free. The CHERI line of work addresses this with additional mechanisms, but the base architecture’s guarantee is spatial.

It also does not solve intra-object overflows. A capability’s bounds cover the whole object, so an index that walks from one field of a struct into the next passes every check, exactly as it does under shadow memory. Fine-grained bounds require a capability per field, which is a change to the data model rather than to the hardware.

The deployment obstacle is the one that has kept capability machines out of general-purpose processors for decades: an architecture that changes the size and semantics of a pointer is not binary-compatible with anything. A program must be recompiled, its libraries recompiled, and the parts written in assembly or generated by a compiler that does not understand capabilities must be handled specially. That is a whole-system transition, and whole-system transitions happen rarely for reasons that have nothing to do with the technical merit of the design. Where it has been deployed, in embedded and research systems and in the security-oriented processors derived from the work, the benefit is that a whole class of memory-safety bugs becomes a fault at the offending instruction, with the bounds and the object identified by the hardware rather than reconstructed by a tool.