InvisiCaps: The Fil-C Capability Model

Home

Installing

Documentation

Releases

GitHub

Meet Fil

InvisiCaps: The Fil-C Capability Model

Fil-C ensures memory safety of all operations in the C and C++ language. The hardest part of C memory safety is pointer safety. Fil-C achieves pointer safety using a capability system for pointers. Specifically, each pointer dynamically tracks what object in memory it should be allowed to access, and using that pointer to access any memory that is not that object is dynamically prohibited.

Achieving memory safety using a pointer capability model means:

Prohibiting accesses that are out of bounds of the object the pointer is allowed to access.

Prohibiting accesses to freed objects.

Prohibiting writes to readonly data.

Prohibiting reads and writes to non-data objects, such as function pointers, or "special" objects internal to the Fil-C runtime (like the innards of threads or jmp_bufs).

Prohibiting reads or writes that would corrupt Fil-C's understanding of any pointer's capability, leading to failure to meaningfully enforce any of these rules.

In addition to memory safety, Fil-C's other goal is fanatical compatibility. This means that Fil-C's capability model also has to allow most (or ideally all) "safe" uses of C pointers; that is, idioms that are in widespread use and don't lead to exploitation unless they violate the above rules. This means even supporting uses of pointers that the C spec deems to be undefined behavior. And it means preserving sizeof(T*) to be the same as what you'd expect - i.e. 8 bytes on 64-bit platforms.

This article describes how Fil-C's capability mode, called InvisiCaps (Invisible Capabilities), achieves all of these goals while also providing reasonable performance and memory usage.

How Hard Can It Be?

Designing a capability model that satisfies these requirements is sufficiently hard that it is an area of active research. Fil-C has now gone through multiple capability systems; InvisiCaps are just the latest. To appreciate the difficulty of this journey, let's review the previous models and why they were abandoned:

PLUT (Pointer Lower Upper Type): This required making pointers 256 bits (four 64-bit pointers). This model required knowing the type of each allocation up front and didn't meaningfully support unions. PLUTs were also not thread-safe, which meant that they were not memory safe in multi-threaded programs. PLUTs did not require a GC; they were coupled with an isoheap allocator. Use-after-free was not an error (was not detected), but could not be used to corrupt capabilities.

SideCaps (Sidecar plus Capability): This was an ingenious capability model that solved the thread safety of PLUTs. SideCaps were a heroic racy atomic protocol that allowed 256 bits of data to be encoded atomically using only 128-bit atomic operations. I am very proud of SideCaps, but they were awful. They were extremely slow (back then, Fil-C was 200x slower than normal C). And, they required knowing the type at allocation time, so they did not meaningfully support unions. Use-after free was not an error (was not detected), but could not be used to corrupt any SideCaps.

MonoCaps (Monotonic Capabilities): The main advantage of switching to MonoCaps was that the type of an object did not have to be determined at allocation time, but could be monotonically revealed as the program used the object. This allowed somewhat meaningful union usage, and obviated the need to infer the type at malloc callsites. MonoCaps also reduced the perf overhead of Fil-C to about 10x, reduced pointer size to 128 bits, unlocked C++ support, and added the ability to deterministically panic on use-after-free rather than only preventing capability corruption on use-after-free. MonoCaps also coincided with the introduction of Fil's Unbelievable Garbage Collector. It's not possible to do MonoCaps without a GC.

InvisiCaps are a major improvement over MonoCaps:

InvisiCaps allow for 64-bit pointers on 64-bit systems (and would allow for 32-bit pointers if Fil-C supported 32-bit systems).

InvisiCaps have thus far allowed for a reduction of performance overhead to about 4x in the bad cases. There are still performance optimization opportunities with InvisiCaps that I haven't explored so they're likely to get faster still.

InvisiCaps allow for meaningful union usage. The type of a memory location can change over the lifetime of that location.

InvisiCaps achieve this without sacrificing thread safety of the capability model.

What Are InvisiCaps Most Like?

InvisiCaps can be thought of as a practical-to-implement and totally thread-safe variant of SoftBound. InvisiCaps are heavily inspired by that work. Unlike SoftBound, InvisiCaps don't allow memory safety escapes by racing on pointers, and they allow for making all features of C and C++ safe, including subtle stuff like function pointer usage. The greatest similarity between SoftBound and InvisiCaps is that they both place the...