KCFI sanitizer

[samitolvanen]

Summary

The KCFI sanitizer, enabled with -fsanitize=kcfi, implements a
forward-edge control flow integrity scheme for indirect calls. It
uses a !kcfi_type metadata node to attach a type identifier for each
function and injects verification code before indirect calls.

Unlike the current CFI schemes implemented in LLVM, KCFI does not
require LTO, does not alter function references to point to a jump
table, and never breaks function address equality. KCFI is intended
to be used in low-level code, such as operating system kernels,
where the existing schemes can cause undue complications because
of the aforementioned properties. However, unlike the existing
schemes, KCFI is limited to validating only indirect calls and is
not compatible with executable-only memory.

KCFI does not provide runtime support, but always traps when a
type mismatch is encountered. Users of the scheme are expected
to handle the trap. With -fsanitize=kcfi, Clang emits a kcfi
operand bundle to indirect calls, and LLVM lowers this to a
known architecture-specific sequence of instructions for each
callsite to make runtime patching easier for users who require this
functionality.

A KCFI type identifier is a 32-bit constant produced by taking the
lower half of xxHash64 from a C++ mangled typename. If a program
contains indirect calls to assembly functions, they must be
manually annotated with the expected type identifiers to prevent
errors. To make this easier, Clang generates a weak SHN_ABS
__kcfi_typeid_<function> symbol for each address-taken function
declaration, which can be used to annotate functions in assembly
as long as at least one C translation unit linked into the program
takes the function address. For example on AArch64, we might have
the following code:

.c:
  int f(void);
  int (*p)(void) = f;
  p();

.s:
  .4byte __kcfi_typeid_f
  .global f
  f:
    ...

Note that X86 uses a different preamble format for compatibility
with Linux kernel tooling. See the comments in
X86AsmPrinter::emitKCFITypeId for details.

As users of KCFI may need to locate trap locations for binary
validation and error handling, LLVM can additionally emit the
locations of traps to a .kcfi_traps section.

Similarly to other sanitizers, KCFI checking can be disabled for
a function with a no_sanitize("kcfi") function attribute.

[samitolvanen]

Addressed Fangrui's feedback.

[samitolvanen]

In D119296#3625796, @MaskRay wrote:

It uses LLVM prefix data to store a type identifier for each function and injects verification code before indirect calls.

Is "prefix data" stale now?

Yes, I forgot to update the commit message here. Fixed.

There are 30+ comments not marked as "done". Having so many is distracting to reviewers as it's unclear whether this is in a ready-for-review state.

My bad, I wasn't familiar with the convention here. I've just been marking my replies as done.

I personally definitely don't consider this in a ready-for-land state.

I left some questions about your comments below. PTAL.

clang/lib/Driver/SanitizerArgs.cpp

63–65

This variable is only used to indicate whether -fno-sanitize-recover command line parameter can be used with the sanitizer. It makes no sense to allow this with KCFI as we always emit a recoverable instruction sequence, hence it's included here.

Also, ud2 absolutely is recoverable in the kernel, and Linux specifically uses ud2 to trigger warnings in assembly code.

clang/test/CodeGen/kcfi.c

3

If -O2 has different behavior, having the test in clang/test/CodeGen is likely a layering violation.

Good point, the -O2 test isn't actually relevant anymore as we no longer rely on it. I'll drop it.

Optimization tests should be placed in llvm/test/, in the relevant pass.

Yes, the InstCombine test below covers this already.

3

If may be useful to have a -x c++ test.

Would you mind elaborating on this? The main difference with -x c++ is the name mangling, I'm not sure if that adds much value in this case.

Add a not-address-taken external linkage function.

Added.

clang/test/Driver/fsanitize.c

652

Use modern spelling --target=. -target is deprecated

It doesn't look like --target works here:

clang-15: error: unsupported option '--target'; did you mean '-target'?

Also the rest of the file uses -target, so perhaps these can all be updated at once when the flag is deprecated?

llvm/lib/Target/X86/X86AsmPrinter.cpp

130

A previous comment isn't done. This doesn't explain that the double-int3 before and after the identifier is an objtool requirement (or similar).

These are not objtool requirements, and I believe the comments do explain why the int3 padding is added. The first two are to reserve some space for runtime patching this code, and the latter two is to avoid call target gadgets in the checks. I'm obviously happy to improve the comments, is there something specific you'd like me to add?

[samitolvanen]

Addressed the rest of Fangrui's comments after clarifying the open questions with him offline.

[MaskRay]

clang/lib/Driver/SanitizerArgs.cpp

63–65

ud2 being recoverable in the kernel is insufficient. The IR should consider this recoverable. In the presence of a failure, the control flow should be transferred as if no failure happens. E.g. for an asan out-of-bounds failure, the code should behave as if the failure is ignored.

[samitolvanen]

clang/lib/Driver/SanitizerArgs.cpp

63–65

ud2 being recoverable in the kernel is insufficient. The IR should consider this recoverable. In the presence of a failure, the control flow should be transferred as if no failure happens. E.g. for an asan out-of-bounds failure, the code should behave as if the failure is ignored.

Sure, that's exactly now the code we emit here works as well. There are no traps emitted to the IR code, we only add an operand bundle to indirect calls, which doesn't affect the control flow as far as the IR is concerned.

[samitolvanen]

• Added a missing equivalency check to MachineInstr.

[MaskRay]

Mostly looks good.

clang/lib/CodeGen/CodeGenModule.cpp

2325

Use llvm::all_of or llvm::any_of

llvm/lib/Target/AArch64/AArch64AsmPrinter.cpp

332

Add const. Delete blank line after the declaration.

350

Add const

384

delete blank line

401

delete blank line

llvm/lib/Target/AArch64/AArch64KCFI.cpp

63

delete blank line

104

delete blank line

llvm-project doesn't typically add a blank line after a variable declaration. please fix other places in this patch.

112

delete blank line

118

don't use early return if the then part is simple.

llvm/lib/Target/AArch64/GISel/AArch64CallLowering.cpp

1185

} else if (Info.CFIType) {
  ...
}

llvm/lib/Target/X86/X86KCFI.cpp

102

delete blank line

108

MaskRayUnsubmittedDone
delete blank line

116

delete blank line

122

Fix this in a way similar to AArch64.

[samitolvanen]

Addressed Fangrui's feedback.

llvm/lib/Target/AArch64/AArch64AsmPrinter.cpp

332

Deleted the blank line, but this can't be const because it's assigned to in the if statement below.

[MaskRay]

Worth waiting a bit and checking whether @pcc has more comments.

[samitolvanen]

• Simplified AArch64 by dropping the KCFI_CHECK_BTI pseudo and just using a different caller-saved temporary register if needed.
• Added -verify-machineinstrs to llc tests.

[samitolvanen]

Based on the recent LKML discussions about X86 retbleed mitigations (https://lore.kernel.org/lkml/[e-mail]/), we're going to need some changes to the code generated for X86.

[MaskRay]

(Will read new updates.)

Note that release/15.x is branching soon (https://discourse.llvm.org/t/llvm-15-0-0-release-schedule/63495): 2022-07-26.
It seems that we can miss the branch to have more time mature the feature and have it for 16.0.

[samitolvanen]

Addressed conflicts with X86 retbleed mitigations (https://lore.kernel.org/lkml/[e-mail]/):

1. Changed the type check instruction sequence emitted by X86AsmPrinter::LowerKCFI_CHECK not to include the full constant, which allows us to freely position the function preamble without worrying about call target gadgets at indirect call sites.
2. Changed the lowering code to take patchable-function-prefix into account, and allowed -fpatchable-function-entry=N,M where M>0 to be used in Clang with KCFI.
3. As we must maintain alignment of the function entry on X86 to avoid performance regressions (https://lore.kernel.org/lkml/87ilnuuiw8.ffs@tglx/), changed the preamble padding to ensure the function entry remains aligned with KCFI, also when combined with patchable-function-prefix.

[samitolvanen]

In D119296#3673297, @MaskRay wrote:

It seems that we can miss the branch to have more time mature the feature and have it for 16.0.

Sure, that sounds reasonable.

[joaomoreira]

I really like this revision. It removes the redundancy of having KCFI passes both in CodeGen and in the backend; it detangles CALL instructions from KCFI by creating a new MIR instruction; it fixes alignment while still supporting the -fpatchable-function-entry option; it doesn't add hashes/gadgets through the code as it was before needed by the use of cmp instructions. With all this said, the patch LGTM.

I tested the patch compiling toy snippets and also compiling the kernel and found no issues.

Some minor suggestions/not so relevant:

• Change the name of CFIType to CFIHash, as it is probably more descriptive.
• Change the KCFI.* into CFI.* where the passes/structures can be re-used by a different CFI approach. For example, X86KCFI::emitCheck can be easily re-used by other CFI schemes. Similarly, the LowerKCFI_CHECK function can also be easily re-used. Because these other approaches are hypothetical by now, this is not a big deal... but may be subject to changes in the future, in case someone comes up with new schemes.
• Deny the ENDBR64/32 opcodes as valid hashes for the CFIType. There was an effort in the past to prevent it from being emitted as an immediate, thus, perhaps, we should also care. Since FineIBT may inherit hashes from KCFI, it would be great to prevent these from becoming valid indirect targets or needing to be checked.

Some relevant optimizations/improvements for future work:

• When LTO is used, hashes may be suppressed for non-local + non-address taken functions.
• As suggested by Andy Cooper, add a salt attribute that allows to differentiate hashes of functions with the same prototype.

llvm/include/llvm/CodeGen/SelectionDAGNodes.h

625

I wonder if CFIHash would be a more descriptive name.

[samitolvanen]

• Ensured that we don't emit ENDBR64/32 as the type hash on X86.

[samitolvanen]

In D119296#3684022, @joaomoreira wrote:

Some minor suggestions/not so relevant:

• Change the name of CFIType to CFIHash, as it is probably more descriptive.

My thinking here was that Type is more generic than a Hash, but I don't really have a strong opinion about this.

• Change the KCFI.* into CFI.* where the passes/structures can be re-used by a different CFI approach. For example, X86KCFI::emitCheck can be easily re-used by other CFI schemes. Similarly, the LowerKCFI_CHECK function can also be easily re-used. Because these other approaches are hypothetical by now, this is not a big deal... but may be subject to changes in the future, in case someone comes up with new schemes.

Sure, it should be trivial for a future patch that wants to reuse this code to rename the functions and classes as needed.

• Deny the ENDBR64/32 opcodes as valid hashes for the CFIType. There was an effort in the past to prevent it from being emitted as an immediate, thus, perhaps, we should also care. Since FineIBT may inherit hashes from KCFI, it would be great to prevent these from becoming valid indirect targets or needing to be checked.

Good point. It should be quite unlikely that we'll end up randomly generating ENDBR as a hash, but I added a helper to the X86 code to ensure we don't end up emitting these values.

Some relevant optimizations/improvements for future work:

• When LTO is used, hashes may be suppressed for non-local + non-address taken functions.
• As suggested by Andy Cooper, add a salt attribute that allows to differentiate hashes of functions with the same prototype.

Agreed, and another request from Peter Z was to add a flag to omit ENDBR from functions with the !kcfi_type attribute. I think these can all be separate follow-up patches.

[joaomoreira]

llvm/lib/Target/X86/X86AsmPrinter.cpp

126

Can we use another constant blinding scheme, such as a Value++ or anything else? This way, we would prevent endbrs from being emitted in the indirect branch guards too.

Since we are using Value (prologue) and ~Value (caller/guard) for doing the checks, we also need to check if ~ENDBR was picked as a KCFIType, otherwise ENDBR will be emitted in the ibranch guards.

llvm/test/CodeGen/X86/kcfi.ll

92

We need to also ensure/test that these are not emitted in the caller/indirect branch guards.

I assume that in the current scheme (blinding with ~Value) would be unfeasible to do this, so maybe we need a different approach for masking (as suggested above).

[samitolvanen]

• Changed MaskKCFIType to also avoid negative invalid patterns and return Value + 1 for clarity.

llvm/lib/Target/X86/X86AsmPrinter.cpp

126

Can we use another constant blinding scheme, such as a Value++ or anything else? This way, we would prevent endbrs from being emitted in the indirect branch guards too.

Since we are using Value (prologue) and ~Value (caller/guard) for doing the checks, we also need to check if ~ENDBR was picked as a KCFIType, otherwise ENDBR will be emitted in the ibranch guards.

I don't mind changing this to Value + 1, but that actually doesn't change anything because we emit -Value in indirect call checks, not ~Value. Therefore, using ~Value works equally well here.

Specifically, this code currently emits ~Valuein the preamble and -(~Value) == Value + 1 in the indirect call check. Switching to Value + 1 simply reverses the order; we'll emit Value + 1 in the preamble and -(Value + 1) == ~Value in the indirect call check.

However, you are right that we also need to avoid -ENDBR in this function. I'll fix that and clarify the comment.

llvm/test/CodeGen/X86/kcfi.ll

92

Added a test for -ENDBR too.

[joaomoreira]

llvm/lib/Target/X86/X86AsmPrinter.cpp

126

Oops, got confused with the operands, tks for clearing it up. Otherwise, changes LGTM.

[MaskRay]

OK, so we could just not make the symbols weak and end up failing at link time if there's a mismatch. That sounds reasonable to me.

For STB_WEAK SHN_ABS __kcfi_typeid_*, there is no duplicate definition error. Is this behavior intentional?
Note: I don't think we should change lld to recognize some symbol prefix and enforce more rigid diagnostics.
An error must be implemented with existing ELF features.

clang/lib/CodeGen/CodeGenModule.cpp

2345–2347

if (const llvm::MDNode *MD = F.getMetadata(llvm::LLVMContext::MD_kcfi_type))
  Type = ...
else
  continue;

[MaskRay]

llvm/lib/Target/AArch64/AArch64AsmPrinter.cpp

330

const?

331

delete blank line

[samitolvanen]

Addressed Fangrui's comments.

[samitolvanen]

In D119296#3733753, @MaskRay wrote:

For STB_WEAK SHN_ABS __kcfi_typeid_*, there is no duplicate definition error. Is this behavior intentional?

Yes, this is by design. Multiple translation units must be able to take the address of the same function declaration, and it must be possible to link them together.

Note: I don't think we should change lld to recognize some symbol prefix and enforce more rigid diagnostics.
An error must be implemented with existing ELF features.

Sure, that's reasonable. I don't think we need more diagnostics here as __kcfi_typeid_ value mismatches are unlikely, but should the need arise, we can figure out the best way to implement them later. Note that this must also work with LTO when linking bitcode files, so we can't rely on ELF features alone.

llvm/lib/Target/AArch64/AArch64AsmPrinter.cpp

330

This can't be const because we assign to this array below in the for (auto &Reg : ScratchRegs) loop.

[efriedma]

clang/docs/ControlFlowIntegrity.rst

319

To clarify, by "indirect call checking", do you mean function pointers specifically? Or does this also work for C++ vtables/member function pointers?

[samitolvanen]

clang/docs/ControlFlowIntegrity.rst

319

Yes, function pointers only. I'll clarify this part.

[samitolvanen]

Clarified that KCFI checks only function pointers in the documentation.

[samitolvanen]

llvm/include/llvm/CodeGen/MachineInstr.h

265

This fails on 32-bit architectures as PointerEmbeddedInt doesn't allow storing 32 bits in a 32-bit pointer:

// Note: This '<' is correct; using '<=' would result in some shifts
// overflowing their storage types.
static_assert(Bits < sizeof(uintptr_t) * CHAR_BIT,
              "Cannot embed more bits than we have in a pointer!")

[samitolvanen]

llvm/include/llvm/CodeGen/MachineInstr.h

265

PointerSumType also needs space for a tag, which we don't have in a 32-bit pointer. Looks like we just need to always store CFIType in ExtraInfo to avoid this issue, similarly to HeapAllocMarker.