Optimizations¶

The scheme as described above is the fully general variant of the scheme. Most of the time we are able to apply one or more of the following optimizations to improve binary size or performance.

In fact, if you try the above example with the current version of the compiler, you will probably find that it will not use the described virtual table layout or machine instructions. Some of the optimizations we are about to introduce cause the compiler to use a different layout or a different sequence of machine instructions.

 dc2:       48 8b 03                mov    (%rbx),%rax
 dc5:       48 8d 15 14 1e 00 00    lea    0x1e14(%rip),%rdx
 dcc:       48 89 c1                mov    %rax,%rcx
 dcf:       48 29 d1                sub    %rdx,%rcx
 dd2:       48 c1 c1 3d             rol    $0x3d,%rcx
 dd6:       48 83 f9 03             cmp    $0x3,%rcx
 dda:       77 2f                   ja     e0b <main+0x9b>
 ddc:       ba 09 00 00 00          mov    $0x9,%edx
 de1:       0f a3 ca                bt     %ecx,%edx
 de4:       73 25                   jae    e0b <main+0x9b>
 de6:       48 89 df                mov    %rbx,%rdi
 de9:       ff 10                   callq  *(%rax)
[...]
 e0b:       0f 0b                   ud2

11a6:       48 8b 03                mov    (%rbx),%rax
11a9:       48 8d 15 d0 28 00 00    lea    0x28d0(%rip),%rdx
11b0:       48 89 c1                mov    %rax,%rcx
11b3:       48 29 d1                sub    %rdx,%rcx
11b6:       48 c1 c1 3d             rol    $0x3d,%rcx
11ba:       48 83 f9 2a             cmp    $0x2a,%rcx
11be:       77 35                   ja     11f5 <main+0xb5>
11c0:       48 ba 09 00 00 00 00    movabs $0x40000000009,%rdx
11c7:       04 00 00
11ca:       48 0f a3 ca             bt     %rcx,%rdx
11ce:       73 25                   jae    11f5 <main+0xb5>
11d0:       48 89 df                mov    %rbx,%rdi
11d3:       ff 10                   callq  *(%rax)
[...]
11f5:       0f 0b                   ud2

9a2:   48 8b 03                mov    (%rbx),%rax
9a5:   48 8d 0d a4 13 00 00    lea    0x13a4(%rip),%rcx
9ac:   48 39 c8                cmp    %rcx,%rax
9af:   75 25                   jne    9d6 <main+0x86>
9b1:   48 89 df                mov    %rbx,%rdi
9b4:   ff 10                   callq  *(%rax)
[...]
9d6:   0f 0b                   ud2

struct A {
  virtual void f1();
  virtual void f2();
};

struct B : A {
  virtual void f1();
  virtual void f2();
  virtual void f3();
  virtual void f4();
  virtual void f5();
  virtual void f6();
};

struct C : A {
  virtual void f1();
  virtual void f2();
};

dd2:       48 c1 c1 3b             rol    $0x3b,%rcx

Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables¶

Dimitar et. al. proposed a novel approach that interleaves virtual tables in [1]. This approach is more efficient in terms of space because padding and bit vectors are no longer needed. At the same time, it is also more efficient in terms of performance because in the interleaved layout address points of the virtual tables are consecutive, thus the validity check of a virtual vtable pointer is always a range check.

At a high level, the interleaving scheme consists of three steps: 1) split virtual table groups into separate virtual tables, 2) order virtual tables by a pre-order traversal of the class hierarchy and 3) interleave virtual tables.

The interleaving scheme implemented in LLVM is inspired by [1] but has its own enhancements (more in Interleave virtual tables).

struct A {
  virtual void f1();
};

struct B : A {
  virtual void f1();
  virtual void f2();
};

struct C : A {
  virtual void f1();
  virtual void f3();
};

struct D : B {
  virtual void f1();
  virtual void f2();
};

CallSiteTypeId¶

CallSiteTypeId is a stable process-wide identifier of the call-site type. For a virtual call site, the type in question is the class type; for an indirect function call it is the function signature. The mapping from a type to an identifier is an ABI detail. In the current, experimental, implementation the identifier of type T is calculated as follows:

• Obtain the mangled name for “typeinfo name for T”.
• Calculate MD5 hash of the name as a string.
• Reinterpret the first 8 bytes of the hash as a little-endian 64-bit integer.

It is possible, but unlikely, that collisions in the CallSiteTypeId hashing will result in weaker CFI checks that would still be conservatively correct.

CFI_Check¶

In the general case, only the target DSO knows whether the call to function f with type CallSiteTypeId is valid or not. To export this information, every DSO implements

void __cfi_check(uint64 CallSiteTypeId, void *TargetAddr, void *DiagData)

This function provides external modules with access to CFI checks for the targets inside this DSO. For each known CallSiteTypeId, this function performs an llvm.type.test with the corresponding type identifier. It reports an error if the type is unknown, or if the check fails. Depending on the values of compiler flags -fsanitize-trap and -fsanitize-recover, this function may print an error, abort and/or return to the caller. DiagData is an opaque pointer to the diagnostic information about the error, or null if the caller does not provide this information.

The basic implementation is a large switch statement over all values of CallSiteTypeId supported by this DSO, and each case is similar to the InlinedFastCheck() in the basic CFI mode.

CFI Shadow¶

To route CFI checks to the target DSO’s __cfi_check function, a mapping from possible virtual / indirect call targets to the corresponding __cfi_check functions is maintained. This mapping is implemented as a sparse array of 2 bytes for every possible page (4096 bytes) of memory. The table is kept readonly most of the time.

There are 3 types of shadow values:

• Address in a CFI-instrumented DSO.
• Unchecked address (a “trusted” non-instrumented DSO). Encoded as value 0xFFFF.
• Invalid address (everything else). Encoded as value 0.

For a CFI-instrumented DSO, a shadow value encodes the address of the __cfi_check function for all call targets in the corresponding memory page. If Addr is the target address, and V is the shadow value, then the address of __cfi_check is calculated as

__cfi_check = AlignUpTo(Addr, 4096) - (V + 1) * 4096

This works as long as __cfi_check is aligned by 4096 bytes and located below any call targets in its DSO, but not more than 256MB apart from them.

CFI_SlowPath¶

The slow path check is implemented in a runtime support library as

void __cfi_slowpath(uint64 CallSiteTypeId, void *TargetAddr)
void __cfi_slowpath_diag(uint64 CallSiteTypeId, void *TargetAddr, void *DiagData)

These functions loads a shadow value for TargetAddr, finds the address of __cfi_check as described above and calls that. DiagData is an opaque pointer to diagnostic data which is passed verbatim to __cfi_check, and __cfi_slowpath passes nullptr instead.

Compiler-RT library contains reference implementations of slowpath functions, but they have unresolvable issues with correctness and performance in the handling of dlopen(). It is recommended that platforms provide their own implementations, usually as part of libc or libdl.

Position-independent executable requirement¶

Cross-DSO CFI mode requires that the main executable is built as PIE. In non-PIE executables the address of an external function (taken from the main executable) is the address of that function’s PLT record in the main executable. This would break the CFI checks.

Leaf Functions¶

If f() is a leaf function (i.e. it has no calls except maybe no-return calls) it can be called using a special calling convention that stores RA in a dedicated register R before the CALL instruction. f() does not spill R and does not use the RET instruction, instead it uses the value in R to JMP to RA.

This flavour of CFI is precise, i.e. the function is guaranteed to return to the point exactly following the call.

An alternative approach is to copy RA from stack to R in the first instruction of f(), then JMP to R. This approach is simpler to implement (does not require changing the caller) but weaker (there is a small window when RA is actually stored on stack).

Functions called once¶

Suppose f() is called in just one place in the program (assuming we can verify this in LTO mode). In this case we can replace the RET instruction with a JMP instruction with the immediate constant for RA. This will precisely enforce the return control flow no matter what is stored on stack.

Another variant is to compare RA on stack with the known constant and abort if they don’t match; then JMP to the known constant address.

Functions called in a small number of call sites¶

We may extend the above approach to cases where f() is called more than once (but still a small number of times). With LTO we know all possible values of RA and we check them one-by-one (or using binary search) against the value on stack. If the match is found, we JMP to the known constant address, otherwise abort.

This protection is near-precise, i.e. it guarantees that the control flow will be transferred to one of the valid return addresses for this function, but not necessary to the point of the most recent CALL.

General case¶

For functions called multiple times a return jump table is constructed in the same manner as jump tables for indirect function calls (see above). The correct jump table entry (or it’s index) is passed by CALL to f() (as an extra argument) and then spilled to stack. The RET instruction is replaced with a load of the jump table entry, jump table range check, and JMP to the jump table entry.

This protection is also near-precise.

Returns from functions called indirectly¶

If a function is called indirectly, the return jump table is constructed for the equivalence class of functions instead of a single function.

Cross-DSO calls¶

Consider two instrumented DSOs, A and B. A defines f() and B calls it.

This case will be handled similarly to the cross-DSO scheme using the slow path callback.

Non-goals¶

RCFI does not protect RET instructions:

• in non-instrumented DSOs,
• in instrumented DSOs for functions that are called from non-instrumented DSOs,
• embedded into other instructions (e.g. 0f4fc3 cmovg %ebx,%eax).