Forward-Edge CFI for Virtual Calls¶

This scheme works by allocating, for each static type used to make a virtual call, a region of read-only storage in the object file holding a bit vector that maps onto to the region of storage used for those virtual tables. Each set bit in the bit vector corresponds to the address point for a virtual table compatible with the static type for which the bit vector is being built.

For example, consider the following three C++ classes:

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

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

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

The scheme will cause the virtual tables for A, B and C to be laid out consecutively:

The bit vector for static types A, B and C will look like this:

Bit vectors are represented in the object file as byte arrays. By loading from indexed offsets into the byte array and applying a mask, a program can test bits from the bit set with a relatively short instruction sequence. Bit vectors may overlap so long as they use different bits. For the full details, see the ByteArrayBuilder class.

In this case, assuming A is laid out at offset 0 in bit 0, B at offset 0 in bit 1 and C at offset 0 in bit 2, the byte array would look like this:

char bits[] = { 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 0, 5, 0, 0 };

To emit a virtual call, the compiler will assemble code that checks that the object’s virtual table pointer is in-bounds and aligned and that the relevant bit is set in the bit vector.

For example on x86 a typical virtual call may look like this:

ca7fbb:       48 8b 0f                mov    (%rdi),%rcx
ca7fbe:       48 8d 15 c3 42 fb 07    lea    0x7fb42c3(%rip),%rdx
ca7fc5:       48 89 c8                mov    %rcx,%rax
ca7fc8:       48 29 d0                sub    %rdx,%rax
ca7fcb:       48 c1 c0 3d             rol    $0x3d,%rax
ca7fcf:       48 3d 7f 01 00 00       cmp    $0x17f,%rax
ca7fd5:       0f 87 36 05 00 00       ja     ca8511
ca7fdb:       48 8d 15 c0 0b f7 06    lea    0x6f70bc0(%rip),%rdx
ca7fe2:       f6 04 10 10             testb  $0x10,(%rax,%rdx,1)
ca7fe6:       0f 84 25 05 00 00       je     ca8511
ca7fec:       ff 91 98 00 00 00       callq  *0x98(%rcx)
  [...]
ca8511:       0f 0b                   ud2

The compiler relies on co-operation from the linker in order to assemble the bit vectors for the whole program. It currently does this using LLVM’s type metadata mechanism together with link-time optimization.

 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 Indirect Function Calls¶

Under forward-edge CFI for indirect function calls, each unique function type has its own bit vector, and at each call site we need to check that the function pointer is a member of the function type’s bit vector. This scheme works in a similar way to forward-edge CFI for virtual calls, the distinction being that we need to build bit vectors of function entry points rather than of virtual tables.

Unlike when re-arranging global variables, we cannot re-arrange functions in a particular order and base our calculations on the layout of the functions’ entry points, as we have no idea how large a particular function will end up being (the function sizes could even depend on how we arrange the functions). Instead, we build a jump table, which is a block of code consisting of one branch instruction for each of the functions in the bit set that branches to the target function, and redirect any taken function addresses to the corresponding jump table entry. In this way, the distance between function entry points is predictable and controllable. In the object file’s symbol table, the symbols for the target functions also refer to the jump table entries, so that addresses taken outside the module will pass any verification done inside the module.

In more concrete terms, suppose we have three functions f, g, h which are all of the same type, and a function foo that returns their addresses:

f:
mov 0, %eax
ret

g:
mov 1, %eax
ret

h:
mov 2, %eax
ret

foo:
mov f, %eax
mov g, %edx
mov h, %ecx
ret

Our jump table will (conceptually) look like this:

f:
jmp .Ltmp0 ; 5 bytes
int3       ; 1 byte
int3       ; 1 byte
int3       ; 1 byte

g:
jmp .Ltmp1 ; 5 bytes
int3       ; 1 byte
int3       ; 1 byte
int3       ; 1 byte

h:
jmp .Ltmp2 ; 5 bytes
int3       ; 1 byte
int3       ; 1 byte
int3       ; 1 byte

.Ltmp0:
mov 0, %eax
ret

.Ltmp1:
mov 1, %eax
ret

.Ltmp2:
mov 2, %eax
ret

foo:
mov f, %eax
mov g, %edx
mov h, %ecx
ret

Because the addresses of f, g, h are evenly spaced at a power of 2, and function types do not overlap (unlike class types with base classes), we can normally apply the Alignment and Eliminating Bit Vector Checks for All-Ones Bit Vectors optimizations thus simplifying the check at each call site to a range and alignment check.

Shared library support¶

EXPERIMENTAL

The basic CFI mode described above assumes that the application is a monolithic binary; at least that all possible virtual/indirect call targets and the entire class hierarchy are known at link time. The cross-DSO mode, enabled with -f[no-]sanitize-cfi-cross-dso relaxes this requirement by allowing virtual and indirect calls to cross the DSO boundary.

Assuming the following setup: the binary consists of several instrumented and several uninstrumented DSOs. Some of them may be dlopen-ed/dlclose-d periodically, even frequently.

• Calls made from uninstrumented DSOs are not checked and just work.

• Calls inside any instrumented DSO are fully protected.

• Calls between different instrumented DSOs are also protected, with

  a performance penalty (in addition to the monolithic CFI overhead).

• Calls from an instrumented DSO to an uninstrumented one are

  unchecked and just work, with performance penalty.

• Calls from an instrumented DSO outside of any known DSO are

  detected as CFI violations.

In the monolithic scheme a call site is instrumented as

if (!InlinedFastCheck(f))
  abort();
call *f

In the cross-DSO scheme it becomes

if (!InlinedFastCheck(f))
  __cfi_slowpath(CallSiteTypeId, f);
call *f

void __cfi_check(uint64 CallSiteTypeId, void *TargetAddr)

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

void __cfi_slowpath(uint64 CallSiteTypeId, void *TargetAddr)

Hardware support¶

We believe that the above design can be efficiently implemented in hardware. A single new instruction added to an ISA would allow to perform the CFI check with fewer bytes per check (smaller code size overhead) and potentially more efficiently. The current software-only instrumentation requires at least 32-bytes per check (on x86_64). A hardware instruction may probably be less than ~ 12 bytes. Such instruction would check that the argument pointer is in-bounds, and is properly aligned, and if the checks fail it will either trap (in monolithic scheme) or call the slow path function (cross-DSO scheme). The bit vector lookup is probably too complex for a hardware implementation.

//  This instruction checks that 'Ptr'
//   * is aligned by (1 << kAlignment) and
//   * is inside [kRangeBeg, kRangeBeg+(kRangeSize<<kAlignment))
//  and if the check fails it jumps to the given target (slow path).
//
// 'Ptr' is a register, pointing to the virtual function table
//    or to the function which we need to check. We may require an explicit
//    fixed register to be used.
// 'kAlignment' is a 4-bit constant.
// 'kRangeSize' is a ~20-bit constant.
// 'kRangeBeg' is a PC-relative constant (~28 bits)
//    pointing to the beginning of the allowed range for 'Ptr'.
// 'kFailedCheckTarget': is a PC-relative constant (~28 bits)
//    representing the target to branch to when the check fails.
//    If kFailedCheckTarget==0, the process will trap
//    (monolithic binary scheme).
//    Otherwise it will jump to a handler that implements `CFI_SlowPath`
//    (cross-DSO scheme).
CFI_Check(Ptr, kAlignment, kRangeSize, kRangeBeg, kFailedCheckTarget) {
   if (Ptr < kRangeBeg ||
       Ptr >= kRangeBeg + (kRangeSize << kAlignment) ||
       Ptr & ((1 << kAlignment) - 1))
         Jump(kFailedCheckTarget);
}

An alternative and more compact enconding would not use kFailedCheckTarget, and will trap on check failure instead. This will allow us to fit the instruction into 8-9 bytes. The cross-DSO checks will be performed by a trap handler and performance-critical ones will have to be black-listed and checked using the software-only scheme.

Note that such hardware extension would be complementary to checks at the callee side, such as e.g. Intel ENDBRANCH. Moreover, CFI would have two benefits over ENDBRANCH: a) precision and b) ability to protect against invalid casts between polymorphic types.