Purely Technical Discussion: Memory-Safe Compilation Mode Inspired by Fil-C

[IceGuye]

@gwenzek

Note that on platforms that have PAC (aka ptrauth), you could implement P^I by signing all pointers. This totally works, even with unions, but it’s depressingly slow, at least last time I checked.

This reminds me about the Generational Arena in the Rust game development communities. They create their own Arena, often based on the “one struct with multiple arrays” design. They use indexes as “pointers”, and those arrays as “memory”, so they get better cpu cache and faster, and the borrow checker is being fooled so it has nothing to do with it.

To be safer, their indexes are kind of fat, and they have a specific array in the struct to store an usize, which they call “generation”. Every time they do alloc, they generate a fat Index (pointer) with the current generation, let’s say 0. When they do realloc or free, they raise the generation by 1. Now the old fat Index (pointer) still has Generation 0, but the data slot (memory) it pointing to has Generation 1. So if you use the old fat Index to access the new or freed data slot, it will return error. This will eliminate UAF.

However, this is only safe if the attacker cannot access and manipulate the generation. I am not sure if the Rust’s private fields have anything to do with it. But in Zig, if we implement this as an allocator feature in a certain compile mode (debug or releasesafe), we should be able to make it safe in compiler level.

The the generation is an integer, and its plus operation and comparison operation is faster than doing a crypto level signature and verification.

[vincentd]

Oh nice, more from Fil himself!

Zig’s [bounds-checks] are guaranteed only if you don’t race or use [*]T directly.

…or if you use ‘Release’ optimisation. I can’t think of a good reason to do so, but maybe there is one, and Fil-C would still protect your program at the coarse level. You get inter-Arena protection, but not intra-Arena protection.

So I wonder: is it possible to make the allocator interface special in this way:

• all calls to alloc just call zgc_alloc in Fil-C mode

• all calls to resize/remap just call zgc_realloc (though resize might need a new intrinsic on the Fil-C side)

• calls to free just call zgc_free or do nothing

Long idea that eventually led to an epiphany.

Someone correct me if I’m wrong, but couldn’t this be done by using a compile-time switch to replace each Allocator with a dummy version? e.g. for ArenaAllocator.

// std.heap
const std = @import("std.zig");
const builtin = @import("builtin");

const ArenaAllocator = if (builtin.os.abi == .fil1) @import("fil1/heap/ArenaAllocator.zig") else @import("heap/DummyArenaAllocator.zig");

That’s probably a a very ugly way to do it, but you get the idea.

From the outside, the DummyArenaAllocator looks like an ArenaAllocator - it has the same methods. However, every call to alloc() simply allocates from the child alloc. It also keeps an internal ArrayList [1] of all the allocation pointers, so you can run arena.reset() and free all the allocations at the same time - a lot of code uses that pattern instead of individual free calls, so this way the garbage collector gets informed when that happens.

[1] Arraylist is its own separate allocation so that an attacker can’t jump from one allocation to all the rest, like they could if linked-list nodes were stored intrusively with each allocation.

Important behaviour:

• alloc() is passed straight through to the child allocator, except the pointer is also recorded in its internal list.
• resize() still fails if you try to increase the size of an allocation that is not the most recent one - even though they’re really just individual allocations.
• free() is not a noop - it actually calls child_allocator.free(). It also removes it from the ArrayList, so they don’t get double-free’d.
• ArenaAllocator.reset() frees all the allocations no matter what option you pass to it.

Advantages:

• No change to the std.mem.Allocator Interface [edit].
• Quirks of the Allocator are preserved. - e.g. ArenaAllocator.reset().
• Does not change the behaviour of user-defined allocators.

Disadvantages:

• May confuse someone who is looking for the source code of ArenaAllocator.
• Code must be kept in lockstep with the original.
• Needs to manually written for each ‘overridden’ allocator.

…

That last point got me thinking - how often do people write Allocators that are (1) wrappers around a generic Allocator and (2) non-trivial?

• Allocators that get their memory from syscalls (directly or via std.heap.PageAllocator) need to changed anyway, to get memory from Fil-C instead.
• By ‘non-trivial’, I mean allocators which don’t just pass-through the results from the child allocator, but either (1) combine allocations into a single child allocation or (2) store allocator meta-data in the same child allocation. ArenaAllocator does both, DebugAllocator does neither.
  • A trivial allocator wrapped around the Fil-C allocator gives the same protections as the Fil-C allocator does.

In the zig-0.16.0 std.heap , the wrapping Allocators are

• ArenaAllocator (non-trivial)
• DebugAllocator (trivial)
• FixedBufferAllocator (non-trivial - think of the buffer as being a single ‘child allocation’).
• StackFallbackAllocator (trivial)

The master branch also has SafeAllocator which stores metadata within each child allocation, but it looks like it does the same job as Fil-C’s allocator, making it redundant.

Outside of that, std.Io often wraps allocators… but I think that’s solely for thread-safety.

As for large zig projects:

• Zig source code has one Allocator in src/tracy.zig, which is trivial.

• Tigerbeetle has three:

  • static_allocator (trivial)
  • counting_allocator (trivial)
  • huge_page_allocator (take a guess).

If anyone knows any major zig projects with interesting Allocators - trivial or not - I’d like to see them.

To me, this indicates that ArenaAllocator and FixedBufferAllocator are special somehow. I don’t think it’s a coincidence that they both forbid you from increasing the size of any allocation except the most recent one, and both of them allow you to not bother free’ing individual allocations and just do it as one big batch at the end.

If the problem is specific to Arena Allocators, and allocators similar to them, then it follows that a solution could (should?) be specific to them as well.

[benburkert]

@vincentd

Advantages:

• Needs no changes to std.mem.Allocator.

I don’t see this as an advantage if InvisiCaps can be implemented in std.mem.Allocator without changing the API. (Or did you mean no changes to the Allocator API?) Perhaps the raw* methods on Allocator could be used to instruct wrapped allocators to skip InvisiCaps, so that only the outermost Allocator does the capabilities book-keeping. I think ideally all allocator implementations would get memory safety free of any implementation cost.

[vincentd]

Yes, sorry, I meant without changing the Allocator API.

Perhaps the raw* methods on Allocator could be used to instruct wrapped allocators to skip InvisiCaps, so that only the outermost Allocator does the capabilities book-keeping.

Is that even possible with Fil-C’s memory strategy?

Consider an ArenaAllocator wrapped around a FixedBufferAllocator backed by a buffer: []u8 provided by the user.

Where would the ArenaAllocator store the invisicaps meta-data - the ‘upper’ and ‘aux’ words. If it stores them in the FixedBufferAllocator, then the user can edit the meta-data with buffer and it’s game over. But it can’t store them anywhere else, because Fil-C expects the meta-data to be placed at the memory address just in front of the ‘lower’ address.

Instead of forcing the outermost allocator to apply invisicaps to memory of unknown provenance, it makes more sense for the innermost allocator (Fil-C) to be the only invisicaps-aware allocator, then instruct the wrapping allocators to stop doing funny business with the allocations and just pass them through unaltered. Most wrapping allocators already do that anyway.

[benburkert]

@vincentd

Where would the ArenaAllocator store the invisicaps meta-data - the ‘upper’ and ‘aux’ words.

When the outer std.mem.Allocator is requested a *T (.create(T)), it calls alloc on the ArenaAllocator, but with a len large enough to hold the upper+aux+T. The ArenaAllocator in turn calls rawAlloc (already) on the inner Allocator (which in-turn calls alloc on the FixedBufferAllocator), which skips the invisicaps meta-data for this raw allocation. Before returning the realized *T, I think the outer Allocator would also need to interface with the Fil-C API so that T (or parts of it) could be safely passed to C/C++ code.

@vincentd

If it stores them in the FixedBufferAllocator, then the user can edit the meta-data with buffer and it’s game over.

Can you say more about why this would be game over? I’m not well versed on this stuff, but it seems that Fil-C would already need some way of preventing malicious user code from modifying capability data in the same user space memory.

[vincentd]

@benburkert

Can you say more about why this would be game over? I’m not well versed on this stuff, but it seems that Fil-C would already need some way of preventing malicious user code from modifying capability data in the same user space memory.

No worries - it took me a long time to get my head around how it works.

From invisicaps:

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.

And on the garbage collector

One way that capabilities might be implementated is if there was a totally separate address space in which the capability objects are allocated. But a simpler option exists (and what Fil-C actually does): the capability objects are at addresses that are outside of any capability’s lower/upper bounds. So, it’s never possible for LLVM IR to load or store to the capability objects.

and

Capability Allocation

Capabilities can only be created by allocation. Allocations happen via libc, such as by calling malloc, via the LLVM IR alloca instruction, and LLVM global variables.

Creating a capability allocates both the capability object itself and the payload object. The payload is the memory that the user code gets to see with loads and stores. The capability’s lower/upper bounds tell where the payload object is and how large it is.

New capabilities will choose a range of memory for the capability itself and for the payload that is free according to the garbage collector. So, a newly created capability never overlaps with any reachable capability.

New capabilities have their payload initialized to zero.

Emphasis mine.

In other words:

1. Fil-C keeps a list of what memory the user is allowed to access.
2. This list needs to be stored somewhere in memory.
3. Therefore, Fil-C puts the list in memory that the user isn’t allowed to access.

An attacker faces a chicken-and-egg scenario; in order to write to memory they don’t own, they need a corrupted capability. But in order to corrupt a capability, they need to write to memory they don’t own.

That is how Fil-C prevents malicious code from modifying the capabilities - and it all comes crashing down the moment the user gets write access to just one capability object.

[folago]

Isn’t this what the Val language (now named Hylo I think) does?
I cannot find a proper link right now, but here is the landing page

Edit: I got confused with Vale: Vale's Memory Safety Strategy: Generational References and Regions

[gwenzek]

See the picture from FilC documentation InvisiCaps: The Fil-C Capability Model

But most of the metadata is stored at the beginning of the allocation. FilC uses C ABI as a boundary between trusted code (FilC malloc) and untrusted ( your code). So since in Zig we have a vtable we can use that to separate regular code from the trusted allocator code.

But it’s a bit complicated to hide the allocator state from user code when the allocator state is a slice whose value is stored on the stack. One thing I can imagine is that ‘FixedBufferAllocator’ could use “unsafe” and set the allocated slice capability to zero (not readable). Then FixedBufferAllocator alloc could bypass the 0 capability and be responsible to write capabilities for sub allocations.

It is a breaking change because it requires that FBA receives a slice with capabilities, and in particular it means that stack allocated arrays must have such capabilities.

It’s also a departure from FilC promise of “no unsafe” keyword, but I think this is bound to happen, since currently all FilC runtime is “unsafe”, so extending this runtime in Zig will require “unsafe” Zig code too.