InvisiCaps: The Fil-C Capability Model

InvisiCaps：Fil-C 能力模型

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. Fil-C 确保了 C 和 C++ 语言中所有操作的内存安全性。C 语言内存安全中最困难的部分是指针安全。Fil-C 通过一种针对指针的能力系统（Capability System）来实现指针安全。具体而言，每个指针都会动态跟踪它被允许访问的内存对象，并动态禁止使用该指针访问非该对象的任何内存。

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. 使用指针能力模型实现内存安全意味着：禁止访问指针允许访问对象范围之外的内存；禁止访问已释放的对象；禁止向只读数据写入；禁止对非数据对象（如函数指针或 Fil-C 运行时内部的“特殊”对象，例如线程内部结构或 jmp_bufs）进行读写；禁止任何会破坏 Fil-C 对指针能力理解的读写操作，从而避免导致这些规则无法被有效执行。

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. 除了内存安全之外，Fil-C 的另一个目标是极致的兼容性。这意味着 Fil-C 的能力模型必须允许大多数（理想情况下是全部）“安全”的 C 指针用法；即那些被广泛使用且除非违反上述规则否则不会导致漏洞的惯用法。这意味着甚至要支持 C 规范中被视为未定义行为的指针用法。同时，它还意味着要保持 sizeof(T*) 与预期一致——即在 64 位平台上为 8 字节。本文将介绍 Fil-C 的能力模式——InvisiCaps（隐形能力），它是如何在实现所有这些目标的同时，提供合理的性能和内存占用的。

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: 设计一个满足这些需求的能力模型难度极大，目前仍是一个活跃的研究领域。Fil-C 已经历了多种能力系统，InvisiCaps 只是最新的一个。为了理解这一过程的艰辛，让我们回顾一下之前的模型及其被放弃的原因：

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. PLUT（指针下界、上界、类型）： 该模型要求将指针扩展为 256 位（四个 64 位指针）。它要求预先知道每个分配对象的类型，且无法有效支持联合体（unions）。PLUT 也不具备线程安全性，这意味着在多线程程序中它无法保证内存安全。PLUT 不需要垃圾回收（GC），而是与 isoheap 分配器配合使用。释放后使用（Use-after-free）不会被视为错误（未被检测到），但无法利用它来破坏能力。
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. SideCaps（侧车加能力）： 这是一个巧妙的能力模型，解决了 PLUT 的线程安全问题。SideCaps 是一种极具挑战性的竞争原子协议，允许仅使用 128 位原子操作来原子化地编码 256 位数据。我为 SideCaps 感到自豪，但它们表现糟糕。它们极其缓慢（当时 Fil-C 比普通 C 慢 200 倍）。此外，它们要求在分配时知道类型，因此无法有效支持联合体。释放后使用不会被视为错误，但无法利用它来破坏任何 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. MonoCaps（单调能力）： 转向 MonoCaps 的主要优势在于，对象的类型无需在分配时确定，而是可以在程序使用对象的过程中单调地揭示。这允许了某种程度上有意义的联合体使用，并消除了在 malloc 调用点推断类型的需求。MonoCaps 还将 Fil-C 的性能开销降低到约 10 倍，将指针大小减小到 128 位，解锁了 C++ 支持，并增加了在释放后使用时确定性崩溃的能力，而不仅仅是防止能力破坏。MonoCaps 的出现也伴随着 Fil 的“不可思议垃圾回收器”（Unbelievable Garbage Collector）的引入。没有 GC 是无法实现 MonoCaps 的。

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. InvisiCaps 是对 MonoCaps 的重大改进：InvisiCaps 在 64 位系统上允许使用 64 位指针（如果 Fil-C 支持 32 位系统，它也将允许 32 位指针）。到目前为止，InvisiCaps 已将最坏情况下的性能开销降低到约 4 倍。InvisiCaps 仍有我尚未探索的性能优化空间，因此它们可能会变得更快。InvisiCaps 允许有意义的联合体使用。内存位置的类型可以在其生命周期内发生变化。InvisiCaps 在实现这一点的同时，没有牺牲能力模型的线程安全性。

What Are InvisiCaps Most Like?

InvisiCaps 最像什么？

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 capability metadata “outside” of the address space visible to the program. InvisiCaps 可以被视为 SoftBound 的一种易于实现且完全线程安全的变体。InvisiCaps 受该研究启发很大。与 SoftBound 不同，InvisiCaps 不允许通过指针竞争来逃避内存安全，并且它们允许使 C 和 C++ 的所有特性（包括函数指针使用等微妙之处）变得安全。SoftBound 和 InvisiCaps 之间最大的相似之处在于，它们都将能力元数据放置在程序可见地址空间“之外”。

InvisiCaps can also be thought of as a software implementation of CHERI. Unlike CHERI, InvisiCaps are more compatible (pointers are 64-bit, not 128-bit or 256-bit) and InvisiCaps have a more deterministic use-after-free story. InvisiCaps 也可以被视为 CHERI 的软件实现。与 CHERI 不同，InvisiCaps 兼容性更好（指针是 64 位的，而不是 128 位或 256 位），并且 InvisiCaps 在处理释放后使用问题时具有更强的确定性。

The Intuition Of InvisiCaps

InvisiCaps 的直觉

Let’s start with a simple intuition for how InvisiCaps work, without worrying about how a pointer and its capability are stored in memory. Let’s just consider: A pointer in a local variable, not in memory. We’ll call this a flight pointer. The layout of the object that the pointer points at. For our example, let’s consider a pointer that points into the middle of an object. The flight pointer has two parts: The lower bound ptr. This gives us the lower bounds for the purpose of bounds checking pointer accesses. It also pointers right above the object header, which contains: The upper bound ptr. We’ll use this for the upper bounds check. This has to be at least as large as the lower bound ptr. It can be exactly equal to the lower bound ptr, for objects that cannot be accessed at all. 让我们从 InvisiCaps 如何工作的简单直觉开始，而不必担心指针及其能力是如何存储在内存中的。我们只考虑：一个位于局部变量中而非内存中的指针。我们称之为“飞行指针”（flight pointer）。以及该指针所指向对象的布局。在我们的示例中，考虑一个指向对象中间的指针。飞行指针包含两部分：下界指针（lower bound ptr）。这为指针访问的边界检查提供了下界。它还指向对象头部的正上方，其中包含：上界指针（upper bound ptr）。我们将使用它进行上界检查。它必须至少与下界指针一样大。对于完全无法访问的对象，它可以与下界指针完全相等。