Skip to content

LLVM AllocToken and Heap Partitioning Support for Rust Design Doc

This document describes the overall design of LLVM AllocToken and heap partitioning support for the Rust compiler. This document does not describe allocator-internal hardening (e.g., inline metadata protection, out-of-line metadata, quarantines, etc.) or hardware-assisted heap corruption protection (e.g., ARM Memory Tagging Extension [MTE]) support for the Rust compiler.

This document is for software engineers working with the Rust programming language that want information about the overall design of LLVM AllocToken and heap partitioning support for the Rust compiler. This document assumes prior knowledge of the Rust programming language and its toolchain.

Objective

Add LLVM AllocToken and heap partitioning support to the Rust compiler (i.e., rustc).

Background

With the increasing popularity of Rust both as a general purpose programming language and as a replacement for C and C++ because of its memory and thread safety guarantees, many companies and projects are adopting or migrating to Rust. One of the most common paths to migrate to Rust is to gradually replace C or C++ with Rust in a program written in C or C++.

Rust provides interoperability with foreign code written in C via Foreign Function Interface (FFI). However, foreign code does not provide the same memory and thread safety guarantees that Rust provides, and is susceptible to memory corruption and concurrency issues, such as heap-related memory corruption issues (e.g., heap-based out-of-bound reads and writes, use after free, double free, etc).1 Therefore, it is generally accepted that linking foreign C- or C++-compiled code into a program written in Rust may degrade the security of the program.[1]–[3]

While it is also generally believed that replacing sensitive C or C++ with Rust in a program written in C or C++ improves the security of the program, Papaevripides and Athanasopoulos[4] demonstrated that this is not always the case, and that linking foreign Rust-compiled code into a program written in C or C++ with modern exploit mitigations may actually degrade the security of the program, mostly due to the absence of support for these exploit mitigations in the Rust compiler. Attacks that used this were later formalized as a new class of attacks named "cross-language attacks"[3].

Heap-related memory corruption issues are generally exploited by controlling the heap layout (also known as “heap grooming”, “heap shaping”, or “heap feng shui”[5]) so that an object subject to an out-of-bounds read or write is placed adjacent to a target object containing pointers (e.g., data pointers, function pointers, or virtual function table pointers), allowing the target object to be read or corrupted, or so that the memory of a freed target object is reclaimed by a new allocation of a different type with attacker-controlled contents, allowing the dangling reference to the target object to be used to read or corrupt the new allocation or other memory locations (i.e., use after free). Both techniques generally aim at reading or corrupting pointers to escalate an out-of-bounds read or write to a more powerful primitive, such as an arbitrary read or write to achieve an information leak or arbitrary code execution.

To protect programs from having these techniques used against them, modern memory allocators and operating systems separate allocations into isolated heap partitions (see Heap partitioning.) LLVM AllocToken[6]–[11] assigns a token identifier (i.e., an integer) to each allocation, and pass it to the allocator by rewriting allocation calls to token-enabled versions, enabling allocator-level heap organization strategies such as heap partitioning. However, in mixed-language binaries, also known as “mixed binaries” (i.e., for when C or C++ and Rust-compiled code share the same virtual address space and memory allocator), allocations in code compiled without support for it are not tokenized and are placed in a default or fallback partition, where they can be used to bypass the heap partitioning of the program.

The Rust compiler currently does not support heap partitioning when

  • building Rust-compiled code only programs.
  • linking foreign C- or C++-compiled code into a program written in Rust.
  • linking foreign Rust-compiled code into a program written in C or C++.[4]

Table I summarizes interoperability-related risks when building programs for the Linux operating system on the AMD64 architecture and equivalent without support for heap partitioning in the Rust compiler.

Table I \ Summary of interoperability-related risks when building programs for the Linux operating system on the AMD64 architecture and equivalent without support for heap partitioning in the Rust compiler.

Without using Unsafe Rust Using Unsafe Rust
Rust-compiled code only ▼I Allocations in Rust-compiled code are not tokenized and can not be partitioned by the allocator.2 ▼ Unsafe Rust is susceptible to memory corruption and concurrency issues.
▼ Allocations in Rust-compiled code are not tokenized and can not be partitioned by the allocator.
Linking foreign C- or C++-compiled code into a program written in Rust ▼ Foreign code is susceptible to memory corruption and concurrency issues.
▼ Allocations in Rust-compiled code are not tokenized and can not be partitioned by the allocator.		 ▼ Foreign code is susceptible to memory corruption and concurrency issues.
▼ Unsafe Rust is susceptible to memory corruption and concurrency issues.
▼ Allocations in Rust-compiled code are not tokenized and can not be partitioned by the allocator.
Linking foreign Rust-compiled code into a program written in C or C++3 ▲II Allocations in C- and C++-compiled code are tokenized and partitioned by the allocator.
▼ C and C++ are susceptible to memory corruption and concurrency issues.
▼ Allocations in Rust-compiled code are not tokenized and are placed in a default or fallback partition.		 ▲ Allocations in C- and C++-compiled code are tokenized and partitioned by the allocator.
▼ C and C++ are susceptible to memory corruption and concurrency issues.
▼ Unsafe Rust is susceptible to memory corruption and concurrency issues.
▼ Allocations in Rust-compiled code are not tokenized and are placed in a default or fallback partition.

I Downwards-pointing triangle (▼) precedes a negative risk indicator.
II Upwards-pointing triangle (▲) precedes a positive risk indicator.

Without heap partitioning support in the Rust compiler, allocations in Rust-compiled code are not tokenized and are placed in a default or fallback partition, where an object subject to an out-of-bounds read or write can be placed adjacent to an object containing pointers, or the memory of a freed object containing pointers can be reclaimed by a new allocation of a different type with attacker-controlled contents (i.e., use after free), allowing the heap partitioning of the program to be bypassed through the allocations of the language without support for it. Therefore, the absence of support for heap partitioning in the Rust compiler is a security concern when gradually migrating from C and C++ to Rust, and when C or C++ and Rust-compiled code share the same virtual address space and memory allocator.

1. Modern C and C++ compilers, memory allocators, and operating systems provide exploit mitigations to increase the difficulty of exploiting vulnerabilities resulting from these issues. However, some of these exploit mitigations, such as heap partitioning, are not applied when linking foreign C- or C++-compiled code into a program written in Rust, mostly due to the absence of support for these exploit mitigations in the Rust compiler (see Table I). ↩

2. An attack that successfully exploits a heap-related memory corruption vulnerability in a Rust-compiled code only program, without using Unsafe Rust, is yet to be demonstrated. ↩

3. Assuming heap partitioning (e.g., LLVM AllocToken with a token-enabled memory allocator) is enabled. ↩

Heap partitioning

Heap partitioning is an exploit mitigation that protects programs from having their heap layout controlled for exploitation by separating allocations into isolated heap partitions, so that objects in one partition can not be placed adjacent to (or have their freed memory reclaimed by) objects in another partition. Heap partitioning increases the difficulty of exploiting heap-related memory corruption issues; it does not eliminate exploitation within the same partition. It is implemented by modern memory allocators and operating systems, such as the Apple XNU kernel kalloc_type allocator[12], the Chromium PartitionAlloc allocator[13], the GrapheneOS hardened_malloc allocator[14], and the Linux kernel randomized kmalloc caches[15]. It is classified in five categories:

  • Size-based heap partitioning
  • Domain-based heap partitioning
  • Allocation site-based heap partitioning
  • Pointer-based heap partitioning
  • Type-based heap partitioning

Size-based heap partitioning

Size-based heap partitioning separates allocations into partitions derived from the allocation size (i.e., the size class of the allocation), so that objects of one size class can not be placed adjacent to (or have their freed memory reclaimed by) objects of another size class. It does not require type information (i.e., allocation token hints), because the allocation size is passed to the allocator directly. It is less comprehensive than type-based heap partitioning because objects of different types in the same size class are placed in the same partition. It is implemented by the GrapheneOS hardened_malloc allocator[14], and is inherent to segregated-fit and slab allocators.

Domain-based heap partitioning

Domain-based heap partitioning separates allocations into partitions derived from a purpose assigned to the allocation, or a security domain (i.e., a partition key), so that objects of one domain can not be placed adjacent to (or have their freed memory reclaimed by) objects of another domain. Unlike the other categories, the partition is assigned by the programmer (e.g., through a purpose-specific allocation interface) rather than derived automatically from the allocation, so it does not require allocation token hints derived by the compiler. It is implemented by the Chromium PartitionAlloc allocator[13].

Allocation site-based heap partitioning

Allocation site-based heap partitioning separates allocations into partitions derived from the allocation call site (i.e., the location in the program where the allocation is performed), so that objects allocated at one allocation call site can not be placed adjacent to (or have their freed memory reclaimed by) objects allocated at another allocation call site. The separation can be deterministic (e.g., one partition per allocation call site) or randomized (e.g., a randomly selected partition per allocation call site), and does not require type information (i.e., allocation token hints). It is less comprehensive than type-based heap partitioning because objects of different types allocated at the same allocation call site (e.g., in a generic or type-erased allocation function) are placed in the same partition. It is implemented by the Linux kernel randomized kmalloc caches[15].

Pointer-based heap partitioning

Pointer-based heap partitioning separates allocations into two partitions: one for types containing pointers and another for types not containing pointers (also known as “data splitting” or “data-only heap isolation”), so that objects containing pointers can not be placed adjacent to (or have their freed memory reclaimed by) objects not containing pointers. It is a coarse-grained implementation of type-based heap partitioning with two type classes, and protects the most common path for exploiting heap-related memory corruption issues (i.e., using a memory corruption issue to read or corrupt pointers), with minimal memory overhead. It is implemented by the Apple XNU kernel kalloc_type allocator[12] as its first level of separation.

Type-based heap partitioning

Type-based heap partitioning separates allocations into partitions derived from the allocated type, so that objects of one type can not be placed adjacent to (or have their freed memory reclaimed by) objects of another type. The comprehensiveness of the separation varies per implementation (e.g., one partition per type, one partition per type-signature group, or a fixed number of partitions selected by hashing the type). This is the most comprehensive category, and is implemented by the Apple XNU kernel kalloc_type allocator[12].

Detailed design

LLVM AllocToken and heap partitioning support for the Rust compiler will be implemented similarly to how it is implemented for Clang. It will be implemented by adding support for emitting allocation token hints and attributes to the Rust compiler code generation, and by adding heap partitioning schemes for classifying allocated types to the Rust compiler.

The Rust compiler provides support for multiple code generation backends.[16] The actual code generation is done by a third-party library, such as LLVM. The rustc_codegen_ssa crate contains backend-agnostic code and provides an abstraction layer and interface for backends to implement, such as implemented in the rustc_codegen_llvm crate.

MIR is the Rust compiler Mid-level Intermediate Representation. In MIR, heap allocations appear as calls to allocation functions: functions annotated with the internal allocator attributes (i.e., #[rustc_allocator], #[rustc_allocator_zeroed], #[rustc_reallocator], and #[rustc_deallocator]), such as __rust_alloc, __rust_alloc_zeroed, and __rust_realloc, which the Rust standard library containers and smart pointers (e.g., Arc, Box, Rc, String, and Vec via RawVec) call through the alloc::alloc::alloc family of functions and the GlobalAlloc and Allocator traits; and foreign allocation functions (e.g., malloc) called across the FFI boundary.

The rustc_codegen_ssa::mir::block module lowers MIR blocks and their terminators to the selected backend intermediate representation (IR), such as LLVM IR. The do_call method of the TerminatorCodegenHelper type in the rustc_codegen_ssa::mir::block module does the code generation for function calls, including all allocation function calls, making it the preferred location for emitting allocation token hints.

To emit allocation token hints, an allocation token abstraction will be added to the backend-agnostic code for backends that support allocation token instrumentation (i.e., attaching allocation token hints to allocation calls), such as LLVM, to implement.

LLVM AllocToken and heap partitioning support for the Rust compiler work is broken in these steps:

  • Create tracking issue.
  • Add option to the Rust compiler driver and frontend (i.e., -Zsanitizer=alloc-token, -Zsanitizer-alloc-token-scheme, -Zsanitizer-alloc-token-max, -Zsanitizer-alloc-token-extended, and -Zsanitizer-alloc-token-fast-abi), including target support specification (i.e., supported_sanitizers in target specifications).
  • Add support for emitting allocation token function attributes, module flags, and allocation token hint metadata to the Rust compiler code generation. (Broken in detailed steps below.)
  • Implement the default pointer-split heap partitioning scheme in the rustc_sanitizers crate. (See Heap partitioning schemes.)
  • Define allocation token classifications and type name encodings for cross-language LLVM AllocToken and heap partitioning support.
  • Change the initial implementation to use the defined classifications and type name encodings for cross-language LLVM AllocToken and heap partitioning support.
  • Add typed allocation paths and allocation token hints to the Rust standard library. (See Standard library and allocator support.)
  • Add token-enabled allocator interface support to the Rust standard library and to the Rust compiler allocator shim generation.
  • Add the alloc_token_infer intrinsic (i.e., the Rust equivalent of the Clang __builtin_infer_alloc_token builtin).
  • Create documentation and tests.

Add support for emitting allocation token function attributes, module flags, and allocation token hint metadata to the Rust compiler code generation work is broken in two categories:

  • Add allocation token abstraction to backend-agnostic code.
  • Implement allocation token abstraction for LLVM backend.

Add allocation token abstraction to backend-agnostic code work is broken in these steps:

  • Add support for computing an allocation token hint for a given Ty to the rustc_sanitizers crate. (See Allocation token hints.)
  • Add set_alloc_token_hint method declaration to a backend-agnostic trait declaration (e.g., BuilderMethods or a new AllocTokenMethods trait) for backends to implement. The set_alloc_token_hint method should attach an allocation token hint to a given allocation call.
  • Add support for emitting allocation token hints to the do_call method of the TerminatorCodegenHelper type in the rustc_codegen_ssa::mir::block module for calls to allocation functions when the allocated type is known, and conservative allocation token hints (i.e., an unknown type name and contains-pointer set to true) when the allocated type is unknown.

Implement allocation token abstraction for LLVM backend work is broken in these steps:

  • Add set_alloc_token_hint method implementation to the LLVM backend attaching !alloc_token metadata (i.e., an MDString type name and an i1 contains-pointer flag) to allocation calls, and any necessary FFI bindings/declarations to the rustc_codegen_llvm::llvm module.
  • Add support for emitting the sanitize_alloc_token function attribute to the sanitize_attrs function of the rustc_codegen_llvm::attributes module (i.e., adding an ALLOCTOKEN flag to SanitizerSet), with support for the #[sanitize(..)] attribute.
  • Add support for emitting the alloc-token-mode, alloc-token-max, alloc-token-fast-abi, and alloc-token-extended module flags to the LLVM backend module/context creation.
  • Add support for running the AllocTokenPass (including setting the fallback token identifier to the partition containing pointers) to the Rust compiler LLVM optimization pipeline construction (i.e., the PassWrapper in the rustc_llvm crate), if not already included in the default optimization pipelines of the LLVM version in use.

LLVM AllocToken

LLVM AllocToken is implemented as an LLVM instrumentation pass (i.e., AllocTokenPass)[7] that rewrites allocation calls in functions marked with the sanitize_alloc_token function attribute to token-enabled versions, by appending a token identifier argument and redirecting the call to a token-enabled version of the allocation function, prefixed with __alloc_token_ (see Fig. 1).

; Before AllocToken instrumentation
%ptr = call ptr @malloc(i64 %size), !alloc_token !0
...
!0 = !{!"Foo", i1 true}

; After AllocToken instrumentation
%ptr = call ptr @__alloc_token_malloc(i64 %size, i64 42)
Fig. 1. Example allocation call before and after AllocToken instrumentation.

The token identifier for a given allocation call is derived from the !alloc_token metadata attached to the allocation call by the compiler. The !alloc_token metadata format is !{<type-name>, <contains-pointer>}, where <type-name> is a string uniquely identifying the allocated type, and <contains-pointer> is a boolean indicating whether the allocated type contains pointers.[8],[9]

Table II summarizes the token identifier derivation modes supported by the AllocTokenPass.

Table II \ Summary of LLVM AllocToken token identifier derivation modes.

Mode Description
Increment Sequential counter per allocation call site, modulo the maximum number of tokens.
Random Statically-assigned pseudorandom token identifier per allocation call site.
TypeHash Stable hash (i.e., SipHash) of the allocated type name from the !alloc_token metadata, modulo the maximum number of tokens.
TypeHashPointerSplit (default) Stable hash of the allocated type name, with the token identifier space partitioned in two halves: one for types containing pointers and another for types not containing pointers.

The maximum number of tokens is configurable (i.e., -falloc-token-max for Clang, and the alloc-token-max module flag), and allocation calls without !alloc_token metadata are assigned a configurable fallback token identifier.4 The AllocTokenPass instruments known allocation library functions (e.g., malloc, calloc, realloc, and C++ operator new and variants) by default, and non-standard allocation functions annotated with !alloc_token metadata when extended coverage is enabled (i.e., -fsanitize-alloc-token-extended for Clang, and the alloc-token-extended module flag). An alternative fast ABI (i.e., -fsanitize-alloc-token-fast-abi for Clang, and the alloc-token-fast-abi module flag) encodes the token identifier in the allocation function name (e.g., __alloc_token_0_malloc, __alloc_token_1_malloc, …) instead of appending a token identifier argument, which is more efficient when the maximum number of tokens is small.

The AllocTokenPass also lowers the llvm.alloc.token.id intrinsic, which accepts !alloc_token metadata and is replaced with the constant token identifier for it. This intrinsic is used by Clang to implement the __builtin_infer_alloc_token builtin[11], which allows querying token identifiers at compile time for custom allocator interfaces.

4. The LLVM AllocToken fallback token identifier defaults to 0, which in the TypeHashPointerSplit mode falls into the half of the token identifier space for types not containing pointers. The Rust compiler will both emit explicit conservative allocation token hints (i.e., contains-pointer set to true) whenever possible, and set the fallback token identifier to the partition containing pointers, so that default or unknown is the partition containing pointers. ↩

Allocation token hints

LLVM uses !alloc_token metadata to allow the compiler to pass information about the allocated type to the AllocTokenPass (see LLVM AllocToken). This metadata is the interface between the Rust compiler heap partitioning schemes and the LLVM token identifier derivation modes, and consists of

  • a type name: a string uniquely identifying the allocated type, used by the TypeHash and TypeHashPointerSplit modes to derive stable token identifiers. For the Rust compiler, the type name will be encoded using the Rust v0 symbol mangling type encoding[17], which is deterministic, unique, and stable across crates and compilation units, except for types used across the FFI boundary when cross-language LLVM AllocToken and heap partitioning support is needed (see Type name compatibility for type-based heap partitioning schemes).
  • a contains-pointer flag: a boolean indicating whether the allocated type contains pointers, used by the TypeHashPointerSplit mode to partition the token identifier space. For the Rust compiler, this flag will be computed by the selected heap partitioning scheme (see Heap partitioning schemes).

Allocation token hints will be emitted by the Rust compiler code generation

  • for allocations performed through the typed allocation paths added to the Rust standard library (e.g., by Box::<T>::new), where the allocated type is a type parameter of the monomorphized instance being lowered (see Standard library and allocator support).
  • for all remaining calls to allocation functions (e.g., calls to __rust_alloc through type-erased paths, and calls to malloc across the FFI boundary), as conservative allocation token hints (i.e., an unknown type name and contains-pointer set to true), so that default or unknown is the partition containing pointers. Inference of the allocated type from the surrounding MIR (e.g., from Layout::new::<T>() data flow and from pointer casts, analogously to how Clang infers allocated types from sizeof expressions and casts[10]) may be added later to improve coverage of type-erased paths.

In mixed binaries, C or C++ and Rust-compiled code share the same virtual address space and generally the same memory allocator, so the heap partitioning of the program must be consistent across all its compiled code to not be bypassable through the allocations of one of the languages (see Background). For cross-language LLVM AllocToken and heap partitioning support, C or C++ and Rust-compiled code must

  • use the same token-enabled memory allocator, and have their allocation calls rewritten to the same token-enabled allocator interface. (See Token-enabled allocator interface compatibility.)
  • use the same token identifier derivation mode, maximum number of tokens, and ABI (i.e., the Clang -falloc-token-max, -fsanitize-alloc-token-fast-abi, and related options and the Rust compiler -Zsanitizer-alloc-token-* equivalent options must match), because token identifiers are computed per translation unit (e.g., token identifiers are reduced modulo the maximum number of tokens, so different maximum numbers of tokens assign different token identifiers to equivalent types).
  • assign the same token identifier to equivalent types allocated by both C- or C++- and Rust-compiled code, which requires compatible contains-pointer classifications (see Classification compatibility for the pointer-split heap partitioning scheme) and, for type-based heap partitioning schemes, compatible type name encodings (see Type name compatibility for type-based heap partitioning schemes).

Unlike cross-language LLVM CFI support[18], which requires a compatible encoding for all indirectly called function types, cross-language LLVM AllocToken and heap partitioning support degrades gracefully: classification mismatches go in the conservative direction (i.e., toward the partition containing pointers) instead of weakening the partition not containing pointers, and type name mismatches place equivalent types in different partitions instead of aggregating them in the same partition, so partial compatibility does not meaningfully degrade the security of the program.

Token-enabled allocator interface compatibility

For cross-language LLVM AllocToken and heap partitioning support, both Clang and the Rust compiler must rewrite allocation calls to token-enabled versions of the allocation functions, prefixed with __alloc_token_, with the token identifier appended as the last argument (or encoded in the function name with the fast ABI). Clang rewrites the C and C++ allocation functions (e.g., malloc to __alloc_token_malloc, and operator new to __alloc_token__Znwm), and the Rust compiler will rewrite the Rust allocator interface functions (e.g., __rust_alloc to __alloc_token___rust_alloc), which will forward to the token-enabled C allocator interface through the System allocator implementation (see Standard library and allocator support), so that a single token-enabled memory allocator serves all compiled code in a mixed binary.

Deallocation functions are not rewritten (i.e., the allocator determines the partition of a given pointer at deallocation time from the pointer itself), so memory allocated by code compiled by one compiler and deallocated by code compiled by another compiler (which already requires the same allocator to be used by both) continues to work.

Classification compatibility for the pointer-split heap partitioning scheme

For the pointer-split heap partitioning scheme, the assigned partition is determined by the contains-pointer classification only, so cross-language LLVM AllocToken and heap partitioning support requires only that Clang and the Rust compiler classify equivalent types consistently (i.e., it does not require compatible type name encodings).

Clang classifies a type as containing pointers by recursively examining pointer types, array element types, atomic value types, and struct, class, and union field types (and C++ base classes, with polymorphic classes classified as containing pointers because of the virtual function table pointer), with uintptr_t classified as containing pointers because pointers are likely to be stored as uintptr_t, and with incomplete types omitting the allocation token hint (i.e., being assigned the fallback token identifier).[9] The pointer-split heap partitioning scheme classification (see Table III) is defined to agree with the Clang classification for C types used across the FFI boundary.

Table III summarizes the classification compatibility for the pointer-split heap partitioning scheme for cross-language LLVM AllocToken and heap partitioning support.

Table III \ Classification compatibility for the pointer-split heap partitioning scheme for cross-language LLVM AllocToken and heap partitioning support.

C type Clang classification Rust type Rust classification
_Bool, bool Not containing pointers bool Not containing pointers
char, signed char, unsigned char Not containing pointers i8, …; cfi_types::c_char, c_schar, c_uchar Not containing pointers
short, int, long, long long, and unsigned variants Not containing pointers i8, i16, i32, i64, i128, …; cfi_types::c_short, …, c_ulonglong Not containing pointers
float, double Not containing pointers f32, f64 Not containing pointers
size_t, ssize_t, ptrdiff_t Not containing pointers usize, isize; cfi_types::c_size_t, c_ssize_t, c_ptrdiff_t Containing pointers for usize and isize (conservative); not containing pointers for cfi_types::c_size_t, c_ssize_t, c_ptrdiff_t (see Classifying C integer types)
uintptr_t, intptr_t Containing pointers usize, isize; cfi_types::c_uintptr_t, c_intptr_t Containing pointers
pointer (T *, const T *) Containing pointers *const T, *mut T Containing pointers
function pointer Containing pointers extern "C" fn, Option<extern "C" fn> Containing pointers
array Same as element type [T; N] Same as element type
_Atomic(T) Same as T core::sync::atomic types Same as underlying type, except AtomicUsize, AtomicIsize, and AtomicPtr (containing pointers)
struct, union Per field types; incomplete types omit the allocation token hint (i.e., fallback token identifier) repr(C) struct, union Per field types; opaque types (e.g., extern types) classified as containing pointers (conservative)
C++ polymorphic class Containing pointers (virtual function table pointer) n/a

Classifying C integer types

Rust defines explicitly-sized integer types (i.e., i8, i16, i32, …) and the pointer-sized usize and isize integer types, while C defines abstract integer types (i.e., char, short, long, …) and the pointer-sized size_t and uintptr_t integer types. This causes ambiguity if Rust integer types are used in repr(C) types shared across the FFI boundary because Clang classifies C integer types by their type alias (i.e., typedef) names (e.g., uintptr_t as containing pointers, because pointers are likely to be stored as uintptr_t, and size_t as not containing pointers), not their defined representations (e.g., pointer-sized unsigned integer).

For example, the Rust compiler currently is unable to identify if a

#[repr(C)]
pub struct Buffer {
    len: usize,
    data: [c_char; 4096],
}
Fig. 2. Example repr(C) type using Rust integer type.

represents a struct buffer { size_t len; char data[4096]; } or a struct buffer { uintptr_t len; char data[4096]; }, which Clang classifies as not containing pointers and as containing pointers, respectively.

For cross-language LLVM AllocToken and heap partitioning support, the Rust compiler must be able to identify and correctly classify C types in repr(C) types shared across the FFI boundary when AllocToken and heap partitioning are enabled.

For convenience, Rust provides some C-like type aliases for use when interoperating with foreign code written in C, and these C type aliases may be used for disambiguation. However, at the time types are classified, all type aliases are already resolved to their respective ty::Ty type representations (i.e., their respective Rust aliased types), making it currently impossible to identify C type aliases use from their resolved types.

For example, the Rust compiler currently is also unable to identify that a

#[repr(C)]
pub struct Buffer {
    len: c_size_t,
    data: [c_char; 4096],
}
Fig. 3. Example repr(C) type using C type alias.

used the c_size_t type alias and is not able to disambiguate between it and a repr(C) type using the c_uintptr_t type alias, which Clang classifies as not containing pointers and as containing pointers, respectively.

To solve this, the cfi_types crate[19][20] provides a new set of C types as user-defined types using the cfi_encoding attribute and repr(transparent) to be used for cross-language LLVM CFI support[18] and could also be used for allocation token classification (see Table III): c_size_t, c_ssize_t, and c_ptrdiff_t will be classified as not containing pointers (matching the Clang classification of size_t, ssize_t, and ptrdiff_t), and c_uintptr_t and c_intptr_t will be classified as containing pointers (matching the Clang classification of uintptr_t and intptr_t). Alternatively, the alloc_token_hint attribute allows the user to define the classification for user-defined types (see The alloc_token_hint attribute).

Type name compatibility for type-based heap partitioning schemes

For type-based heap partitioning schemes (i.e., TypeHash or TypeHashPointerSplit token identifier derivation modes with more than two maximum number of tokens), equivalent types allocated by both C- or C++- and Rust-compiled code map to the same token identifier only if Clang and the Rust compiler emit the same type name in the allocation token hint. Clang emits the canonical, fully qualified C and C++ type name (e.g., Foo, std::vector<int>) as the type name.[9] The Rust compiler will use the canonical, fully qualified C and C++ type names for repr(C) types used across the FFI boundary, and the Rust v0 symbol mangling type encoding[17] for all remaining Rust types. The alloc_token_hint attribute also allows the user to define the type name for user-defined types (see The alloc_token_hint attribute).

The alloc_token_hint attribute

To provide flexibility for the user, an alloc_token_hint attribute will also be provided. The alloc_token_hint attribute will allow the user to define the allocation token hint for user-defined types.

#![feature(alloc_token_hint)]

#[alloc_token_hint(contains_pointers = false)]
pub struct Counters([usize; 8]);

#[alloc_token_hint(type_name = "Foo", contains_pointers = true)]
#[repr(C)]
pub struct Foo {
    next: *mut Foo,
}
Fig. 5. Example user-defined types using the alloc_token_hint attribute.

For example, it will allow the user to place a type in a different partition than the one assigned by the selected heap partitioning scheme, or to use different names for types that otherwise would be required to have the same name as used in externally defined C types (see Fig. 5).

Heap partitioning schemes

Heap partitioning schemes compute allocation token hints for allocated types. Heap partitioning schemes will be implemented in the rustc_sanitizers crate, organized and structured similarly to how CFI type metadata identifier encodings are (i.e., compiler/rustc_sanitizers/src/cfi/typeid, where the typeid module provides the interface and dispatches to encoding implementations such as itanium_cxx_abi), so that more heap partitioning schemes can be implemented and provided in the Rust compiler.

The alloc_token::hint module will provide the interface for computing allocation token hints for a given Ty, and dispatch to the selected heap partitioning scheme implementation (see Fig. 4), similarly to how cfi::typeid provides typeid_for_fnabi and typeid_for_instance and dispatches to itanium_cxx_abi.

The pointer-split and type-hash-pointer-split heap partitioning schemes (see The pointer-split and type-hash-pointer-split heap partitioning schemes) will share the same hint computation (i.e., the same classification and type name encoding, implemented in the type_hash_pointer_split module), and differ only in the maximum number of tokens, so hint_for_ty will dispatch to it unconditionally (see Fig. 4); the scheme will initially only affect the alloc-token-max module flag emitted by the Rust compiler code generation.

bitflags! {
    /// Options for allocation token hints.
    pub struct AllocTokenHintOptions: u32 {
        ...
    }
}

/// An allocation token hint (i.e., the contents of the `!alloc_token`
/// metadata) for a given type.
pub struct AllocTokenHint {
    pub type_name: String,
    pub contains_pointer: bool,
}

/// Returns an allocation token hint for the given type, computed by the
/// selected heap partitioning scheme.
pub fn hint_for_ty<'tcx>(
    tcx: TyCtxt<'tcx>,
    ty: Ty<'tcx>,
    options: AllocTokenHintOptions,
) -> AllocTokenHint {
    type_hash_pointer_split::hint_for_ty(tcx, ty, options)
}
Fig. 4. Interface for computing allocation token hints in the rustc_sanitizers crate.

The heap partitioning scheme will be selectable with an option added to the Rust compiler driver and frontend (i.e., -Zsanitizer-alloc-token-scheme, defaulting to the pointer-split heap partitioning scheme), which selects the LLVM token identifier derivation mode and maximum number of tokens (i.e., the alloc-token-mode and alloc-token-max module flags). Other options equivalent to the Clang options (i.e., -Zsanitizer-alloc-token-max, -Zsanitizer-alloc-token-extended, and -Zsanitizer-alloc-token-fast-abi) will also be provided. The pointer-split heap partitioning scheme hardcodes the maximum number of tokens to two, ignoring -Zsanitizer-alloc-token-max, while the type-hash-pointer-split heap partitioning scheme uses -Zsanitizer-alloc-token-max (defaulting to the same value as Clang, i.e., the number of tokens bounded by SIZE_MAX, when not set).

The pointer-split and type-hash-pointer-split heap partitioning schemes

The pointer-split heap partitioning scheme will be the default heap partitioning scheme for the Rust compiler. It separates allocations in two partitions: one containing pointers and another not containing pointers, with default or unknown being the partition containing pointers. It uses the TypeHashPointerSplit token identifier derivation mode with the maximum number of tokens hardcoded to two (i.e., -Zsanitizer-alloc-token-max is ignored), so that the token identifier is the partition number: token identifier 0 for the partition not containing pointers, and token identifier 1 for the partition containing pointers. (With the maximum number of tokens set to two, the allocated type name has no effect on the resulting token identifier: the TypeHashPointerSplit mode computes the stable hash of the type name modulo half the maximum number of tokens, i.e., modulo one, which is always zero.)

The type-hash-pointer-split heap partitioning scheme additionally assigns a token identifier based on a stable hash of the allocated type name within each of the two partitions (i.e., one containing pointers and another not containing pointers), providing per-type token identifiers. It also uses the TypeHashPointerSplit token identifier derivation mode, but with a configurable maximum number of tokens (i.e., -Zsanitizer-alloc-token-max, defaulting to the same value as Clang, i.e., the number of tokens bounded by SIZE_MAX, when not set).

Both heap partitioning schemes use the same allocation token hint computation (i.e., the same contains-pointer classification and type name encoding, implemented in the type_hash_pointer_split module), and differ only in the maximum number of tokens emitted to the alloc-token-max module flag by the Rust compiler code generation.

The contains-pointer classification for a given type is computed by recursively examining the types composed by value in the given type (i.e., elements of arrays, slices, and tuples, fields of structs, enums, and unions, and closure and coroutine captured state). Pointer indirections (i.e., references, raw pointers, and function pointers) classify the type as containing pointers without examining the pointed-to type. When in doubt, the classification is conservative (i.e., types that can not be classified are classified as containing pointers), because misclassifying a type not containing pointers into the partition containing pointers only loses part of the separation benefit for that type, while misclassifying a type containing pointers into the partition not containing pointers breaks the guarantee of the partition not containing pointers.

Table IV defines the partition assignment for Rust types in the pointer-split scheme.

Table IV \ Partition assignment for Rust types in the pointer-split heap partitioning scheme.

Rust type Contains pointers Partition
bool No 0 (not containing pointers)
char No 0 (not containing pointers)
i8, i16, i32, i64, i128 No 0 (not containing pointers)
u8, u16, u32, u64, u128 No 0 (not containing pointers)
isize, usize5 Yes 1 (containing pointers)
f16, f32, f64, f128 No 0 (not containing pointers)
str No 0 (not containing pointers)
array, slice Same as element type Same as element type
tuple Yes, if any element type contains pointers Per element types
struct, enum Yes, if any field type of any variant contains pointers Per field types
union Yes, if any field type contains pointers Per field types
closure, coroutine Yes, if any captured/state type contains pointers Per captured/state types
reference (&T, &mut T) Yes 1 (containing pointers)
raw pointer (const T, mut T) Yes 1 (containing pointers)
function pointer Yes 1 (containing pointers)
standard library pointer-containing types (e.g., Arc<T>, Box<T>, NonNull<T>, Rc<T>, String, Vec<T>) Yes (per field types) 1 (containing pointers)
trait object (dyn Trait) Yes (unknown concrete type) 1 (containing pointers)
extern type (opaque) Yes (unknown) 1 (containing pointers)
unknown (no type information) Yes 1 (containing pointers)

The classification applies to the allocated (i.e., pointed-to) type, not to the owning type: for example, the allocation made for a Vec<u8> or String has allocated type [u8] and is placed in the partition not containing pointers, while an allocation made for Box<Vec<u8>> has allocated type Vec<u8> (i.e., a struct containing a pointer) and is placed in the partition containing pointers.

5. isize and usize are classified as containing pointers, consistent with how Clang classifies uintptr_t and intptr_t, and because pointers may be stored as usize (e.g., via ptr::expose_provenance and ptr::with_exposed_provenance[21], and AtomicUsize). This trades part of the separation benefit (e.g., Vec<usize> are placed in the partition containing pointers) for conservative classification. (See also Classifying C integer types.) ↩

Additional heap partitioning schemes

Additional heap partitioning schemes can be implemented as sibling modules of type_hash_pointer_split and selected with the -Zsanitizer-alloc-token-scheme option, similarly to how additional CFI type metadata identifier encodings can be implemented as sibling modules of itanium_cxx_abi. For example:

  • Allocation site-based schemes (i.e., Increment and Random token identifier derivation modes), which do not require allocation token hints.
  • Custom schemes (e.g., separating additional type classes, such as types containing function pointers or virtual function table pointers from types containing only data pointers).

Standard library and allocator support

Rust heap allocations are performed through type-erased interfaces (i.e., GlobalAlloc::alloc, Allocator::allocate, and alloc::alloc::alloc are passed a core::alloc::Layout), so the allocated type is not available at the allocation call inside the Rust standard library (e.g., the __rust_alloc call inside alloc::alloc::alloc), even though it is available in the generic callers (e.g., Box::<T>::new, RawVec::<T>, Rc::<T>, and Arc::<T>), which are monomorphized with the concrete allocated type.

To solve this, typed allocation paths will be added to the Rust standard library: internal, unstable, generic allocation functions annotated with a new internal attribute (e.g., #[rustc_alloc_token_hint]) whose type parameter identifies the allocated type, and which perform the raw allocation call (e.g., the call to __rust_alloc) directly. When the Rust compiler code generation lowers a monomorphized instance of one of these functions, it will attach the allocation token hint computed for the type argument to the allocation call within it. The standard library containers and smart pointers (e.g., Arc, Box, Rc, String, and Vec via RawVec) will be changed to route their allocations through the typed allocation paths. Allocations that do not go through the typed allocation paths (e.g., direct calls to alloc::alloc::alloc with a runtime Layout) will have conservative allocation token hints (see Allocation token hints).

With extended coverage enabled, the AllocTokenPass rewrites the annotated __rust_alloc, __rust_alloc_zeroed, and __rust_realloc calls to token-enabled versions (i.e., __alloc_token___rust_alloc(size, align, token_id), …). The Rust compiler allocator shim generation (which currently generates the __rust_alloc family of symbols forwarding to the #[global_allocator] registered allocator or the default allocator) will be extended to also generate the token-enabled versions, forwarding to

  • a new unstable, token-enabled method of the GlobalAlloc trait[22] (e.g., alloc_with_token(layout: Layout, token: usize)), with a default implementation that ignores the token and calls GlobalAlloc::alloc, for backward compatibility with existing allocators.
  • the token-enabled C allocator interface (i.e., __alloc_token_malloc, …) in the System allocator implementation, so that programs using the default allocator can use a token-enabled C memory allocator for the whole program, including foreign code, in mixed binaries.

Additionally, an alloc_token_infer intrinsic (i.e., the Rust equivalent of the Clang __builtin_infer_alloc_token builtin[11], lowered to the llvm.alloc.token.id intrinsic) will be provided for allocator and arena implementers to query the token identifier for a given type at compile time (e.g., core::intrinsics::alloc_token_infer::<T>() -> usize).

Allocation token instrumentation will be enabled by the sanitizer option-Zsanitizer=alloc-token, will be detectable with the cfg(sanitize = "alloc-token") conditional compilation option (i.e., the Rust equivalent of the Clang __SANITIZE_ALLOC_TOKEN__ preprocessor macro), and will support the #[sanitize(..)] attribute. It is recommended to rebuild the standard library with allocation token instrumentation enabled by using the Cargo build-std feature (i.e., -Zbuild-std) when enabling it, so that allocations performed by the standard library are instrumented with allocation token hints.

Dependency considerations

LLVM AllocToken and heap partitioning support depends on LLVM for code generation and the AllocTokenPass LLVM instrumentation pass (available since the LLVM 22)[7]. The Rust compiler already supports using LLVM for code generation, and the AllocTokenPass runs in the default optimization pipelines (it does not require LTO, unlike LLVM CFI support[18]).

Heap partitioning additionally depends on a token-enabled memory allocator (i.e., an allocator that implements the token-enabled allocation interface and uses token identifiers to separate allocations into partitions).

Work estimates

LLVM AllocToken and heap partitioning support for the Rust compiler work is broken in these steps:

  • Create tracking issue.
  • Add option to the Rust compiler driver and frontend (i.e., -Zsanitizer=alloc-token and related options).
  • Add support for emitting allocation token function attributes, module flags, and allocation token hint metadata to the Rust compiler code generation.
  • Implement the default pointer-split heap partitioning scheme in the rustc_sanitizers crate.
  • Define allocation token classifications and type name encodings for cross-language LLVM AllocToken and heap partitioning support.
  • Change the initial implementation to use the defined classifications and type name encodings for cross-language LLVM AllocToken and heap partitioning support.
  • Add typed allocation paths and allocation token hints to the Rust standard library.
  • Add token-enabled allocator interface support to the Rust standard library and to the Rust compiler allocator shim generation.
  • Add the alloc_token_infer intrinsic.
  • Create documentation and tests.

Results

TBD.

Performance

TBD.

Acknowledgments

Thanks to melver (Marco Elver) for designing and implementing LLVM AllocToken in Clang and LLVM. Thanks also to benhawkes (Ben Hawkes), ckennelly (Chris Kennelly), jakos-sec (Jakob Koschel), liblor (Loris Reiff), stefan-blair (Stefan Blair), theofficialflow (Andy Nguyen), vitalybuka (Vitaly Buka), and the Rust community for all their help throughout this project.

References

  1. Y. Song. “On Control Flow Hijacks of unsafe Rust.” GitHub. https://stanford-cs242.github.io/f17/assets/projects/2017/songyang.pdf.
  2. R. de C Valle. “Exploit Mitigations.” The rustc book. https://doc.rust-lang.org/nightly/rustc/exploit-mitigations.html.
  3. S. Mergendahl, N. Burow, and H. Okhravi. “Cross-Language Attacks.” NDSS Symposium 2022. https://www.ndss-symposium.org/wp-content/uploads/2022-78-paper.pdf.
  4. M. Papaevripides and E. Athanasopoulos. “Exploiting Mixed Binaries.” ACM. https://dl.acm.org/doi/pdf/10.1145/3418898.
  5. A. Sotirov. “Heap Feng Shui in JavaScript.” Black Hat Europe 2007. https://www.blackhat.com/presentations/bh-europe-07/Sotirov/Presentation/bh-eu-07-sotirov-apr19.pdf.
  6. “AllocToken.” Clang Documentation. https://clang.llvm.org/docs/AllocToken.html.
  7. M. Elver. “[AllocToken] Introduce AllocToken instrumentation pass.” GitHub. https://github.com/llvm/llvm-project/pull/156838.
  8. M. Elver. “[Clang] Wire up -fsanitize=alloc-token.” GitHub. https://github.com/llvm/llvm-project/pull/156839.
  9. M. Elver. “[AllocToken, Clang] Implement TypeHashPointerSplit mode.” GitHub. https://github.com/llvm/llvm-project/pull/156840.
  10. M. Elver. “[AllocToken, Clang] Infer type hints from sizeof expressions and casts.” GitHub. https://github.com/llvm/llvm-project/pull/156841.
  11. M. Elver. “[Clang][CodeGen] Implement code generation for __builtin_infer_alloc_token().” GitHub. https://github.com/llvm/llvm-project/pull/156842.
  12. “Towards the next generation of XNU memory safety: kalloc_type.” Apple Security Engineering and Architecture. https://security.apple.com/blog/towards-the-next-generation-of-xnu-memory-safety/.
  13. “PartitionAlloc Design.” Chromium Documentation. https://chromium.googlesource.com/chromium/src/+/main/base/allocator/partition_allocator/PartitionAlloc.md.
  14. “hardened_malloc.” GrapheneOS. https://github.com/GrapheneOS/hardened_malloc.
  15. “Randomized slab caches for kmalloc().” LWN. https://lwn.net/Articles/938246/.
  16. “Backend Agnostic Codegen.” Guide to Rustc Development. https://rustc-dev-guide.rust-lang.org/backend/backend-agnostic.html.
  17. “Rust Symbol Mangling (v0).” The Rust RFC Book. https://rust-lang.github.io/rfcs/2603-rust-symbol-name-mangling-v0.html.
  18. R. de C Valle. “LLVM Control Flow Integrity (CFI) Support for Rust Design Doc.” https://rcvalle.com/docs/rust-cfi-design-doc/.
  19. R. de C Valle. “cfi_types.” GitHub. https://github.com/rcvalle/rust-cfi-types.
  20. R. de C Valle. “LLVM CFI and Cross-Language LLVM CFI Support for Rust.” https://rcvalle.com/blog/2023/12/09/llvm-cfi-and-cross-language-llvm-cfi-support-for-rust/.
  21. “Provenance.” The Rust Standard Library. https://doc.rust-lang.org/std/ptr/index.html#provenance.
  22. “GlobalAlloc.” The Rust Standard Library. https://doc.rust-lang.org/std/alloc/trait.GlobalAlloc.html.