[c18n] Proposal: Embedding function signatures in ELF binaries

[dpgao]

Background

The library-based compartmentalisation model enables a pair of mutually distrusting function caller and callee to pass data between each other through function arguments and return values while at the same time guarantees that no additional capabilities are leaked at the ABI level.

The current prototype implementation of this model partially fulfils this guarantee. For example, it assigns different execution stacks to functions in different compartments, preventing stack corruption attacks and leakage of local variables in deallocated call frames.

The next release of the prototype will provide additional protections. Namely, callers no longer need to rely on the callee for the integrity and confidentiality of the content in callee-saved registers, and both callers and callees can be sure that no capabilities in temporary registers can be leaked through a function call.

One omission, though, is that unused function argument registers and return value registers can still leak capabilities across compartments. This proposal aims to address this problem.

Design

The trampolines that perform compartment transitions are made responsible for clearing these registers. However, due to the lack of run-time information about the signature of any particular function, it is currently impossible to identify, at run-time, the unused argument and return value registers of any function.

The compiler should therefore be provide this information, one way or another, in the produced ELF binaries. For each function, its callers should at least provide information about which argument registers are unused, and the shared library that defines it should at least provide information about which return value registers are unused. This makes both sides responsible for clearing the registers that can potentially leak their own capabilities. In practice, it is simplest to require callers and callees to provide the complete set of information---if it turns out at run-time that the caller and callee disagree on which registers should be cleared for a function, an error should be raised.

For simplicity, in the discussions that follow, the 'signature' of a function refers to the set of capabilities registers used for passing arguments and return values. This is implied by the actual signature of the function.

Direct calls

If a function in another compartment is called directly (i.e., the name of the function being called is known at compile time), then both the caller's and the callee's shared libraries should have an entry for this function in their dynamic symbol tables. The compiler can therefore embed information about the function's signature in both parties' ELF files.

Under the Morello ABI's calling convention, a function's signature can be encoded in under a byte of space.

struct Elf_Signature {
    unsigned int sig_valid : 1;
    unsigned int sig_rargs : 4;
    ungigned int sig_margs : 1;
    unsigned int sig_ret : 2;
}

• sig_valid bit is set when sig_* contain meaningful values.
• sig_rargs encodes the number of register arguments taken by the function. On Morello, this number ranges from 0 to 8.
• sig_margs encodes whether the function takes memory arguments. On Morello, this indicates whether register c9 is used to pass arguments.
• sig_ret encodes how the function passes its return values. The encoding of sig_ret allows c0 and c1 to be appropriately cleared with three instructions:

  cmp sig_ret, #0b01
  csel    c1, czr, c1, hs
  csel    c0, czr, c0, hi

  • 00: the function returns values through two registers (c0 and c1 on Morello).
  • 01: the function returns a value through one register (c0 on Morello).
  • 10: the function does not return any value.
  • 11: the function returns by writing to a buffer supplied in a register (c8 on Morello).

Alternative 1: New ELF section

A new ELF section, tentatively named .c18n.signature, will be generated by the compiler toolchain. This section contains an array of elements where the i-th element corresponds to entry i of the dynamic symbol table (.dynsym).

Alternative 2: Reserved bits in dynamic symbol table entries

The st_other field in dynamic symbol table entries contains 6 unused bits. This is not enough to encode function signatures. However, if we relax the requirement that callers and callees must exactly agree on a function's signature, then the caller only needs to supply the argument registers that need to be cleared, and the callee only needs to supply the return value registers that need to be cleared. Either half of the signature is encodeable in 6 bits.

Indirect calls

Functions that are called indirectly (i.e., via a function pointer) pose a greater challenge. Arbitrary functions (including static functions) may be passed across compartment boundaries and invoked without necessarily undergoing compartment transitions.

There is tension between two problems when it comes to designing a mechanism for performing secure cross-compartment indirect function calls.

1. Callers of an indirect function require the assurance that invoking the function will cause a compartment transition and the function will execute in the compartment that it belongs to. This imposes additional costs for indirect function calls compared to direct function calls through the PLT, as the latter are guaranteed by the runtime linker to cause a compartment transition.
2. When a function pointer is created, it is impossible to statically determine, except in limited cases, whether it will be invoked from another compartment. If we conservatively cause a compartment transition every time the function pointer is invoked, this would impose unnecessary performance penalties if the function pointer is invoked from its own compartment.

Alternative 1: Manual API

I propose adding the following two APIs to the runtime linker that developers need to use to safely pass function pointers across compartments.

func_handle _rtld_safebox_func(void (*func)(void), struct Elf_Signature sig);
void (*_rtld_sandbox_func(func_handle handle, struct Elf_Signature sig))(void);

The safebox function is used by the callee compartment to wrap a function pointer into an opaque object owned by RTLD before it is passed to another compartment. The sandbox function is used by the caller to a received opaque object into a usable function pointer, which, when invoked, would perform a proper compartment transition.

The sig argument in both safebox and sandbox informs RTLD about the number of unused argument and return value registers to clear when the function pointer is invoked. Needless to say, the value of sig must match exactly between a pair of safebox and sandbox calls.

It is entirely conceivable that the compiler inserts the value for sig on both the caller and callee sides.

Alternative 2: New indirect function calling convention

When calling a function directly, the runtime linker ensures, through the symbol resolution process, that the called function has a signature that matches the what the callee expects. However, no such guarantees are currently provided when calling a function indirectly, permitting type confusion.

I propose that function pointers are to be sealed with otypes that correspond to their signatures[^1]. These function pointers can then be CInvoke-d with a data capability that corresponds to the signature expected by the caller, preventing type confusion.

[^1]: On the Morello platform, 72 otypes are need describe all possible signatures.

To implement this, the mechanism for creating function pointers needs to be changed. Whenever the address of a function is taken, regardless of whether that function is local or global, the compiler should create a dynamic relocation into a GOT entry that points to that function. During relocation, the dynamic linker will wrap the function with a trampoline and seal the resulting capability with the otype that corresponds to the function's signature. One thing to note is that local functions (e.g., static functions in C) do not appear in the dynamic symbol table and hence do not have a corresponding entry in the ELF signature section. We can work around this by just appending the signatures of local functions to the ELF signature section. Since all dynamic relocations for local functions are relative relocations, we can store the index of the signature in the currently unused symbol number field of the relocation.

The calling convention of function pointers also needs to be modified. Instead of jumping to the target with a simple indirect branch instruction, the following sequence is performed:

load otype
cinvoke function, otype

This typically requires two extra instructions (for loading the otype capability) per invocation. But in the case where a function pointer is invoked repeatedly in a loop, the load of the otype capability can be hoisted out of the loop as an optimisation.

Alternative 3: If otypes cannot be used

This is similar to alternative 2, except that the function pointers remain sealed-entry capabilities rather than sealed capabilities with custom otypes. To authenticate that a function pointer points to a trampoline, we use a user-defined permission bit that is only set for code pointers into trampolines.

Each time a function pointer is called, the compiler emits code to ensure that the called function pointer indeed has the permission bit set, where an unset bit will result in a trap. Moreover, the compiler emits instructions to clear the unused argument registers so that even if the caller mistakenly believes that the function takes fewer arguments than it actually does, it does not inadvertently leak the content in unused argument registers.

Performance-wise, this alternative should incur a very small performance overhead. Authenticating the function pointer can be done with a conditional move instruction, eliminating the possibility of branch mis-predictions. In addition, clearing unused argument registers (of which there are at most 8 on Morello) should be very inexpensive.

[kwitaszczyk]

I have a couple of questions to understand better what's expected here.

1. Is an Elf_Signature entry emitted for each non-inlined function or only functions appearing in relocations?

2. and a mismatch at run-time should trigger an error that serves as a good way to detect certain function signature mismatches

   Do you mean a mismatch between Elf_Signature and arguments that are actually passed (similarly, returned values) at run time? If so, how that could be detected at run time?

3. sigvalid bit is set when `sig*` contain meaningful values.

   When sig_* don't contain meaningful values?

4. 00: the function returns values through registers c0 and c1.

   Is that the most common case? I'd make 00 the most common case that would match the behaviour when Elf_Signature is not found.

5. 11: the function returns by writing to a buffer supplied by the caller through c8.

   I'd rephrase that not to specific to Morello in the general case: "the function returns values by writing to memory. On Morello, this indicates c8 contains a reference to a buffer with a result".

6. char reserved[3];

   What's the use case for having the reserved bytes? Are you expecting changes that would reuse these bytes while being compatible with ABIs before and after a change?

[dpgao]

On 11 Jul 2023, at 11:33, Konrad Witaszczyk @.***> wrote:

I have a couple of questions to understand better what's expected here.

• Is a Elf_Signature entry emitted for each non-inlined function or only functions appearing in relocations?

It is emitted for each entry in the dynamic symbol table (.dynsym), which includes both exported symbols and imported symbols (which also appear relocations).

• and a mismatch at run-time should trigger an error that serves as a good way to detect certain function signature mismatches

Do you mean a mismatch between Elf_Signature and arguments that are actually passed (similarly, returned values) at run time? If so, how that could be detected at run time?

Sorry for being unclear. I meant if the caller and callee have different Elf_Signatures for the same symbol, then an error should be raised.

• sigvalid bit is set when sig* contain meaningful values.

When sig_* don't contain meaningful values?

Not every symbol in .dynsym is a function symbol—some of them are object symbols. For entries in .c18n.signature that correspond to non-function symbols, the sig_valid bit is set to 0 to indicate that the entry is meaningless.

• 00: the function returns values through registers c0 and c1.

Is that the most common case? I'd make 00 the most common case that would match the behaviour when Elf_Signature is not found.

Probably not, but if Elf_Signature is not found, we can simply default to 0b00000000. And since the sig_valid bit here is 0, the remaining bits will be ignored.

• 11: the function returns by writing to a buffer supplied by the caller through c8.

I'd rephrase that not to specific to Morello in the general case: "the function returns values by writing to memory. On Morello, this indicates c8 contains a reference to a buffer with a result".

Well, I not sure if this encoding format can be (or should be) portable to other ABIs. We might need a different format for each platform anyway, so being Morello-specific here doesn’t hurt.

• char reserved[3];

What's the use case for having the reserved bytes? Are you expecting changes that would reuse these bytes while being compatible with ABIs before and after a change?

I don’t have any use cases in mind but it seems a good idea to reserve some space in case we want to associate more information with each dynamic symbol.

[kwitaszczyk]

It is emitted for each entry in the dynamic symbol table (.dynsym), which includes both exported symbols and imported symbols (which also appear relocations).

Apologies, I just noticed you mentioned .dynsym before.

In the kernel, a kernel module registers itself within a subsystem by defining an object that includes function pointers to internal kernel module's routines. Later, the kernel uses that object to branch into the kernel module. AFAIK, the kernel linker is mostly responsible for handling calls from a kernel module into the kernel and between kernel modules but not from the kernel into a kernel module. In such case, the subsystem registering a kernel module is responsible for creating trampolines, not the kernel linker.

From what I can see, .dynsym does not include such symbols exported as function pointers within objects (as they're not needed to link a kernel module). They are available in .symtab but this section is not always available as it can be stripped. It would be great to come up with a solution that allows to dynamically construct trampolines independently of a linker to internal library/module functions with their Elf_Signature entries.

I imagine this case can also appear in the user space where a program or a library obtains an object from another library with a function pointer to branch into that library. Have you thought about such case? Does anything prevent this in the user space or such calls do not currently use trampolines?

[dpgao]

I imagine this case can also appear in the user space where a program or a library obtains an object from another library with a function pointer to branch into that library. Have you thought about such case? Does anything prevent this in the user space or such calls do not currently use trampolines?

This is a great point. I guess in order to make arbitrary function pointers work we'll have to make an Elf_Signature entry for every item in .symtab, not just .dynsym. This also means that libraries cannot strip this section if they want to be used with c18n.

[brooksdavis]

char reserved[3]; What's the use case for having the reserved bytes? Are you expecting changes that would reuse these bytes while being compatible with ABIs before and after a change?

I don’t have any use cases in mind but it seems a good idea to reserve some space in case we want to associate more information with each dynamic symbol.

I might be convinced by char reserved[1], but even then I'm skeptical without a clear use case since it's always going to be possible to add .c18n.signature2 for compatible expansion should we not be able to have another flag day.

[dpgao]

I might be convinced by char reserved[1], but even then I'm skeptical without a clear use case since it's always going to be possible to add .c18n.signature2 for compatible expansion should we not be able to have another flag day.

I'm happy to go with char reserved[1], if only because some ABIs might need more bits to encode register clearing information. But I agree that we can always add more sections if needed.

@brooksdavis Do you have any thoughts on how to deal with indirect calls?

[brooksdavis]

Could you provide a trivial example of the safebox/sandbox API in expected use? I'm pretty sure that ultimate we don't want to expose them to the user and even if we need to expose them they should be reasonably type preserving.

[dpgao]

Could you provide a trivial example of the safebox/sandbox API in expected use? I'm pretty sure that ultimate we don't want to expose them to the user and even if we need to expose them they should be reasonably type preserving.

@brooksdavis Consider the following example where the main executable registers a callback with libfoo. The return type of _rtld_safebox_func and _rtld_sandbox_func is void *, so no type casting is needed. We probably need to expose this API to users, but ideally the compiler can insert them automatically.

// main.c
static int handler(char *buf, size_t len) {
    // process buffer
    return 0;
}

int main() {
    // before: libfoo_register_handler(handler);
    libfoo_register_handler(_rtld_safebox_func(handler, (struct Elf_Signature) {
        .sig_valid = 1, .sig_rargs = 2, .sig_margs = 0, .sig_ret = 1
    }));
}

// libfoo.c
static int (*handler)(char *, sizet_t);
void libfoo_register_handler(int (*f)(char *, size_t)) {
    // before: handler = f;
    handler = _rtld_sandbox_func(f, (struct Elf_Signature) {
        .sig_valid = 1, .sig_rargs = 2, .sig_margs = 0, .sig_ret = 1
    });
}

[kwitaszczyk]

@dpgao I'd like to discuss some modifications to limit the number of required changes in libraries/modules to make use of function pointer calls in the model, and possibly allow to use the model with closed-source libraries and kernel modules. What do you think about these two changes to this design:

1. Change _rtld_safebox_func() to only allow creating a function pointer to a function that is listed in symbol tables visible to a run-time linker, i.e. when compiling a program/kernel or a library/module exportable (from the program/kernel) or importable (from the library/module) functions must be placed in the symbol tables of the program/kernel or the library/module. In such case, a run-time linker could retrieve an Elf_Signature entry itself rather than requiring to specify it by the caller of _rtld_safebox_func().

2. Remove _rtld_sandbox_func() and allow to directly call a function using a function pointer returned by _rtld_safebox_func(). This would disallow the caller of the returned function pointer to indicate what's the Elf_Signature entry from their perspective. To discuss that problem, I'd consider two cases:

   • A library/module can be recompiled to use the model. The caller of the returned function pointer must cast it to a function data type that already includes information on the number of function arguments. I wonder if we could change the ABI to emit at compile-time an Elf_Signature entry for function calls using function pointers. That Elf_Signature entry could be used by a trampoline at run-time.

   • A library/module cannot be recompiled to use the model. The caller of the returned function pointer must trust the function pointer and calls the function using the Elf_Signature entry of the owner of the function.