LinuxLists.cc - [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On 2021-11-22 09:03, Peter Zijlstra wrote:
> Objtool based IBT validation in 3 passes:
>
> --ibt-fix-direct:
>
> Detect and rewrite any code/reloc from a JMP/CALL instruction
> to an ENDBR instruction. This is basically a compiler bug since
> neither needs the ENDBR and decoding it is a pure waste of time.
>
> --ibt:
>
> Report code relocs that are not JMP/CALL and don't point to ENDBR
>
> There's a bunch of false positives, for eg. static_call_update()
> and copy_thread() and kprobes. But most of them were due to
> _THIS_IP_ which has been taken care of with the prior annotation.
>
> --ibt-seal:
>
> Find and NOP superfluous ENDBR instructions. Any function that
> doesn't have it's address taken should not have an ENDBR
> instruction. This removes about 1-in-4 ENDBR instructions.
>

I did some experimentation with compiler-based implementation for two of
the features described here (plus an additional one). Before going into
details, just a quick highlight that the compiler has limited visibility
over handwritten assembly sources thus, depending on the feature, a
compiler-based approach will not cover as much as objtool. All the
observations below were made when compiling the kernel with defconfig, +
CLANG-related options, + LTO sometimes. Here I used kernel revision
0fcfb00b28c0b7884635dacf38e46d60bf3d4eb1 with PeterZ's IBT Beginning
patches applied on top (plus changes to Kbuild), thus, IBT was not
really enforced. Tests consisted mostly of Clang's synthetics tests +
booting a compiled kernel.

Prototypes of the features are available in:
https://github.com/lvwr/llvm/tree/joao/ibt -- I fixed as many corner
cases I could find while trying it out, but I believe some might still
be haunting. Also, I'm not very keen to Kbuild internals nor to however
the kernel patches itself during runtime, so I may have missed some
details.

Finally, I'm interested in general feedback about this... better ways of
implementing, alternative approaches, new possible optimizations and
everything. I should be AFK for a few days in the next weeks, but I'll
be glad to discuss this in January and then. Happy Holidays :)

The features:

-mibt-seal:

Add ENDBRs exclusively to address-taken functions regardless of its
linkage visibility. Only make sense together with LTO.

Observations: Reduced drastically the number of ENDBRs placed in the
kernel binary (From 44383 to 33192), but still missed some that were
later fixed by objtool (Number of fixes by objtool reduced from 11730 to
540). I did not investigate further why these superfluous ENDBRs were
still left in the binary, but at this point my hypotheses spin around
(i) false-positive address-taken conclusions by the compiler, possibly
due to things like exported symbols and such; (ii) assembly sources
which are invisible to the compiler (although this would more likely
hide address taken functions); (iii) other binary level transformations
done by objtool.

Runtime testing: The kernel was verified to properly boot after being
compiled with -mibt-seal (+ LTO).

Note: This feature was already submitted for upstreaming with the
llvm-project: https://reviews.llvm.org/D116070

-mibt-fix-direct:

Direct calls to functions which are known to have ENDBR instructions are
fixed to target the first instruction after the ENDBR (+4 offset). Does
not necessarily depend on LTO, but is meaningfully improved by it
because it depends on after-linking stuff to successfully identify
targets that will have ENDBRs (aliases and assembly functions are a big
complication here, so this currently won't try to optimize calls to
functions which exist in the compiler context as declarations).

Observations: I did a quick change on objtool to collect stats on the
number of fixes applied. Without -mibt-fix-direct objtool had to fix
227552 direct calls/jmps. Without LTO, -mibt-fix-direct reduced this
number to 218455. With LTO this number was reduced to 1728.

Runtime testing: The kernel was verified to properly boot when compiled
with -mibt-fix-direct both with and without LTO. I tried a more
aggressive approach for non-LTO compilation, which was trying to
optimize based on declarations (when functions were not visible) and
noticed that in this scenario the kernel would crash very early in the
boot process. I did not investigate further, but my hypothesis is that
this approach mistakenly optimizes calls to assembly functions without
ENDBRs, leading to random weirdness and doom.

-mibt-preceding-endbr:

Instead of placing ENDBRs after the function entry label, place it right
before. Indirect calls are fixed (using a sub instr) to target 4 bytes
before the function entry point. Address values which are reused after
the indirect call are fixed back to their original value (using an add
instr). Indirect calls that use in-memory pointers are transformed to
first load the function pointer from memory into a free register, then
do the sub, then call it. This does not depend on LTO.

Runtime testing: The runtime test was done using a kernel whose asm
functions were not fixed regarding the position of ENDBRs. Yet, perhaps
surprisingly, the kernel still boots when compiled with
-mibt-preceding-endbr. I don't really know how many indirect calls to
assembly functions happened, but I assume that these would have crashed
if IBT was being enforced due to the misplaced ENDBRs (and it could also
have crashed in these early tests due to indirect calls targeting
unknown instruction 4 bytes before assembly functions, thus the surprise
factor when I saw the kernel booting). Kernel booted alright with
-mibt-preceding-endbr with and without LTO. CONFIG_RETPOLINE was
disabled for testing this.

2022-02-09 05:26:16

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 08, 2022 at 06:21:16PM -0800, Joao Moreira wrote:
> > > Note: This feature was already submitted for upstreaming with the
> > > llvm-project: https://reviews.llvm.org/D116070
> >
> > Ah nice; I see this has been committed now.
>
> Yes, but then some front-end changes also required this fix
> https://reviews.llvm.org/D118052, which is currently under review (posting
> this here in case someone is trying this out).
>
> >
> > Given that IBT will need to work with both Clang and gcc, I suspect the
> > objtool approach will still end up needing to do all the verification.
> >
> > (And as you say, it has limited visibility into assembly.)
>
> Agreed that at this point objtool provides more coverage. Yet, besides being
> an attempt to relief objtool and improve a bit the compiler support as
> mentioned in the series cover letter, it is still nice to reduce the
> left-over nops and fixups which end-up scattered all around.
>
> FWIIW, https://reviews.llvm.org/D118438 and https://reviews.llvm.org/D118355
> are also being cooked. Comments and ideas for new approaches or improvements
> in the compiler support for this are very welcome :)

Ah, excellent, thanks for the pointers. There's also this in the works:
https://reviews.llvm.org/D119296 (a new CFI mode, designed to play nice
to objtool, IBT, etc.)

--
Kees Cook

2022-02-09 06:15:30

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Wed, Nov 24, 2021 at 11:30:37AM -0800, Josh Poimboeuf wrote:
> On Mon, Nov 22, 2021 at 06:03:07PM +0100, Peter Zijlstra wrote:
> > +static int validate_ibt_reloc(struct objtool_file *file, struct reloc *reloc, char **name)
> > +{
> > + struct instruction *dest;
> > + struct section *sec;
> > + unsigned long off;
> > +
> > + sec = reloc->sym->sec;
> > + off = reloc->sym->offset + reloc->addend;
> > +
> > + dest = find_insn(file, sec, off);
> > + if (!dest)
> > + return 0;
> > +
> > + if (name && dest->func)
> > + *name = dest->func->name;
>
> I think these checks can be further narrowed down by only looking for
> X86_64_64 relocs.
>
> > + list_for_each_entry(insn, &file->endbr_list, call_node) {
> > + if (ibt_seal) {
> > + elf_write_insn(file->elf, insn->sec,
> > + insn->offset, insn->len,
> > + arch_nop_insn(insn->len));
> > + }
>
> Like the retpoline rewriting, I'd much rather have objtool create
> annotations which the kernel can then read and patch itself.
>
> e.g. have '.ibt.direct_call_sites' and '.ibt.unused_endbr_insns'
> sections.

Why have the kernel do that work at every boot when it can be known at
link time?

--
Kees Cook

2022-02-09 10:43:13

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

>> Note: This feature was already submitted for upstreaming with the
>> llvm-project: https://reviews.llvm.org/D116070
>
> Ah nice; I see this has been committed now.

Yes, but then some front-end changes also required this fix
https://reviews.llvm.org/D118052, which is currently under review
(posting this here in case someone is trying this out).

>
> Given that IBT will need to work with both Clang and gcc, I suspect the
> objtool approach will still end up needing to do all the verification.
>
> (And as you say, it has limited visibility into assembly.)

Agreed that at this point objtool provides more coverage. Yet, besides
being an attempt to relief objtool and improve a bit the compiler
support as mentioned in the series cover letter, it is still nice to
reduce the left-over nops and fixups which end-up scattered all around.

FWIIW, https://reviews.llvm.org/D118438 and
https://reviews.llvm.org/D118355 are also being cooked. Comments and
ideas for new approaches or improvements in the compiler support for
this are very welcome :)

Tks,
Joao

2022-02-09 12:36:25

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

> Ah, excellent, thanks for the pointers. There's also this in the works:
> https://reviews.llvm.org/D119296 (a new CFI mode, designed to play nice
> to objtool, IBT, etc.)

Oh, great! Thanks for pointing it out. I guess I saw something with a
similar name before ;)
https://www.blackhat.com/docs/asia-17/materials/asia-17-Moreira-Drop-The-Rop-Fine-Grained-Control-Flow-Integrity-For-The-Linux-Kernel.pdf

Jokes aside (and perhaps questions more targeted to Sami), from a
diagonal look it seems that this follows the good old tag approach
proposed by PaX/grsecurity, right? If this is the case, should I assume
it could also benefit from features like -mibt-seal? Also are you
considering that perhaps we can use alternatives to flip different CFI
instrumentation as suggested by PeterZ in another thread?

Tks,
Joao

2022-02-09 12:45:23

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Wed, Feb 09, 2022 at 12:41:41PM +0100, Peter Zijlstra wrote:
> On Tue, Feb 08, 2022 at 03:43:27PM -0800, Kees Cook wrote:

> > Why have the kernel do that work at every boot when it can be known at
> > link time?
>
> I have patches that write a 4 byte #UD there instead of a nop. That
> would make !IBT hardware splat as well when it hits a sealed function
> (and in that case actually having those extra ENDBR generated is a
> bonus).
>
> Anyway, I have some newer patches and some hardware, except it's a NUC
> and working with those things is a royal pain in the arse since they
> don't have serial. I finally did get XHCI debug port working, but
> there's no XDBC grub support, so now I managed to boot a dead kernel and
> the thing is a brick until I can be arsed to connect a keybaord and
> screen to it again :-(
>
> KVM/qemu has no IBT support merged yet, so I can't use that either.

FWIW, those patches live here:

git://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git x86/wip.ibt

2022-02-09 13:26:17

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Thu, Dec 23, 2021 at 06:05:50PM -0800, [email protected] wrote:
> On 2021-11-22 09:03, Peter Zijlstra wrote:
> > Objtool based IBT validation in 3 passes:
> >
> > --ibt-fix-direct:
> >
> > Detect and rewrite any code/reloc from a JMP/CALL instruction
> > to an ENDBR instruction. This is basically a compiler bug since
> > neither needs the ENDBR and decoding it is a pure waste of time.
> >
> > --ibt:
> >
> > Report code relocs that are not JMP/CALL and don't point to ENDBR
> >
> > There's a bunch of false positives, for eg. static_call_update()
> > and copy_thread() and kprobes. But most of them were due to
> > _THIS_IP_ which has been taken care of with the prior annotation.
> >
> > --ibt-seal:
> >
> > Find and NOP superfluous ENDBR instructions. Any function that
> > doesn't have it's address taken should not have an ENDBR
> > instruction. This removes about 1-in-4 ENDBR instructions.
> >
>
> I did some experimentation with compiler-based implementation for two of the
> features described here (plus an additional one). Before going into details,
> just a quick highlight that the compiler has limited visibility over
> handwritten assembly sources thus, depending on the feature, a
> compiler-based approach will not cover as much as objtool. All the
> observations below were made when compiling the kernel with defconfig, +
> CLANG-related options, + LTO sometimes. Here I used kernel revision
> 0fcfb00b28c0b7884635dacf38e46d60bf3d4eb1 with PeterZ's IBT Beginning patches
> applied on top (plus changes to Kbuild), thus, IBT was not really enforced.
> Tests consisted mostly of Clang's synthetics tests + booting a compiled
> kernel.
>
> Prototypes of the features are available in:
> https://github.com/lvwr/llvm/tree/joao/ibt -- I fixed as many corner cases I
> could find while trying it out, but I believe some might still be haunting.
> Also, I'm not very keen to Kbuild internals nor to however the kernel
> patches itself during runtime, so I may have missed some details.
>
> Finally, I'm interested in general feedback about this... better ways of
> implementing, alternative approaches, new possible optimizations and
> everything. I should be AFK for a few days in the next weeks, but I'll be
> glad to discuss this in January and then. Happy Holidays :)
>
> The features:
>
> -mibt-seal:
>
> Add ENDBRs exclusively to address-taken functions regardless of its linkage
> visibility. Only make sense together with LTO.
>
> Observations: Reduced drastically the number of ENDBRs placed in the kernel
> binary (From 44383 to 33192), but still missed some that were later fixed by
> objtool (Number of fixes by objtool reduced from 11730 to 540). I did not
> investigate further why these superfluous ENDBRs were still left in the
> binary, but at this point my hypotheses spin around (i) false-positive
> address-taken conclusions by the compiler, possibly due to things like
> exported symbols and such; (ii) assembly sources which are invisible to the
> compiler (although this would more likely hide address taken functions);
> (iii) other binary level transformations done by objtool.
>
> Runtime testing: The kernel was verified to properly boot after being
> compiled with -mibt-seal (+ LTO).
>
> Note: This feature was already submitted for upstreaming with the
> llvm-project: https://reviews.llvm.org/D116070

Ah nice; I see this has been committed now.

Given that IBT will need to work with both Clang and gcc, I suspect the
objtool approach will still end up needing to do all the verification.

(And as you say, it has limited visibility into assembly.)

-Kees

--
Kees Cook

2022-02-09 13:42:05

by Josh Poimboeuf

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 08, 2022 at 03:43:27PM -0800, Kees Cook wrote:
> On Wed, Nov 24, 2021 at 11:30:37AM -0800, Josh Poimboeuf wrote:
> > On Mon, Nov 22, 2021 at 06:03:07PM +0100, Peter Zijlstra wrote:
> > > +static int validate_ibt_reloc(struct objtool_file *file, struct reloc *reloc, char **name)
> > > +{
> > > + struct instruction *dest;
> > > + struct section *sec;
> > > + unsigned long off;
> > > +
> > > + sec = reloc->sym->sec;
> > > + off = reloc->sym->offset + reloc->addend;
> > > +
> > > + dest = find_insn(file, sec, off);
> > > + if (!dest)
> > > + return 0;
> > > +
> > > + if (name && dest->func)
> > > + *name = dest->func->name;
> >
> > I think these checks can be further narrowed down by only looking for
> > X86_64_64 relocs.
> >
> > > + list_for_each_entry(insn, &file->endbr_list, call_node) {
> > > + if (ibt_seal) {
> > > + elf_write_insn(file->elf, insn->sec,
> > > + insn->offset, insn->len,
> > > + arch_nop_insn(insn->len));
> > > + }
> >
> > Like the retpoline rewriting, I'd much rather have objtool create
> > annotations which the kernel can then read and patch itself.
> >
> > e.g. have '.ibt.direct_call_sites' and '.ibt.unused_endbr_insns'
> > sections.
>
> Why have the kernel do that work at every boot when it can be known at
> link time?

True, but:

- The kernel is already doing several other flavors of boot-time
self-patching. IMO it's better to consolidate such craziness in one
place (or a limited number of places) if we can. It seems more
robust, and limits confusion about who's patching what and when.

- Patching text at link time has pitfalls and I'd like to avoid (as much
as reasonably possible) objtool having the ability to brick the
kernel.

--
Josh

2022-02-09 16:18:42

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 08, 2022 at 03:43:27PM -0800, Kees Cook wrote:
> On Wed, Nov 24, 2021 at 11:30:37AM -0800, Josh Poimboeuf wrote:
> > On Mon, Nov 22, 2021 at 06:03:07PM +0100, Peter Zijlstra wrote:
> > > +static int validate_ibt_reloc(struct objtool_file *file, struct reloc *reloc, char **name)
> > > +{
> > > + struct instruction *dest;
> > > + struct section *sec;
> > > + unsigned long off;
> > > +
> > > + sec = reloc->sym->sec;
> > > + off = reloc->sym->offset + reloc->addend;
> > > +
> > > + dest = find_insn(file, sec, off);
> > > + if (!dest)
> > > + return 0;
> > > +
> > > + if (name && dest->func)
> > > + *name = dest->func->name;
> >
> > I think these checks can be further narrowed down by only looking for
> > X86_64_64 relocs.
> >
> > > + list_for_each_entry(insn, &file->endbr_list, call_node) {
> > > + if (ibt_seal) {
> > > + elf_write_insn(file->elf, insn->sec,
> > > + insn->offset, insn->len,
> > > + arch_nop_insn(insn->len));
> > > + }
> >
> > Like the retpoline rewriting, I'd much rather have objtool create
> > annotations which the kernel can then read and patch itself.
> >
> > e.g. have '.ibt.direct_call_sites' and '.ibt.unused_endbr_insns'
> > sections.
>
> Why have the kernel do that work at every boot when it can be known at
> link time?

I have patches that write a 4 byte #UD there instead of a nop. That
would make !IBT hardware splat as well when it hits a sealed function
(and in that case actually having those extra ENDBR generated is a
bonus).

Anyway, I have some newer patches and some hardware, except it's a NUC
and working with those things is a royal pain in the arse since they
don't have serial. I finally did get XHCI debug port working, but
there's no XDBC grub support, so now I managed to boot a dead kernel and
the thing is a brick until I can be arsed to connect a keybaord and
screen to it again :-(

KVM/qemu has no IBT support merged yet, so I can't use that either.

2022-02-11 17:14:08

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 08, 2022 at 09:18:44PM -0800, Joao Moreira wrote:
> > Ah, excellent, thanks for the pointers. There's also this in the works:
> > https://reviews.llvm.org/D119296 (a new CFI mode, designed to play nice
> > to objtool, IBT, etc.)
>
> Oh, great! Thanks for pointing it out. I guess I saw something with a
> similar name before ;) https://www.blackhat.com/docs/asia-17/materials/asia-17-Moreira-Drop-The-Rop-Fine-Grained-Control-Flow-Integrity-For-The-Linux-Kernel.pdf
>
> Jokes aside (and perhaps questions more targeted to Sami), from a diagonal
> look it seems that this follows the good old tag approach proposed by
> PaX/grsecurity, right? If this is the case, should I assume it could also
> benefit from features like -mibt-seal? Also are you considering that perhaps
> we can use alternatives to flip different CFI instrumentation as suggested
> by PeterZ in another thread?

So, lets try and recap things from IRC yesterday. There's a whole bunch
of things intertwining making indirect branches 'interesting'. Most of
which I've not seen mentioned in Sami's KCFI proposal which makes it
rather pointless.

I think we'll end up with something related to KCFI, but with distinct
differences:

- 32bit immediates for smaller code
- __kcfi_check_fail() is out for smaller code
- it must interact with IBT/BTI and retpolines
- we must be very careful with speculation.

Right, so because !IBT-CFI needs the check at the call site, like:

caller:
cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
je 1f # 2 bytes
ud2 # 2 bytes
1: call __x86_indirect_thunk_rax # 5 bytes

.align 16
.byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
func:
...
ret

While FineIBT has them at the landing site:

caller:
movl $0xdeadbeef, %r11d # 6 bytes
call __x86_indirect_thunk_rax # 5 bytes

.align 16
func:
endbr # 4 bytes
cmpl $0xdeadbeef, %r11d # 7 bytes
je 1f # 2 bytes
ud2 # 2 bytes
1: ...
ret

It seems to me that always doing the check at the call-site is simpler,
since it avoids code-bloat and patching work. That is, if we allow both
we'll effectivly blow up the code by 11 + 13 bytes (11 at the call site,
13 at function entry) as opposed to 11+4 or 6+13.

Which then yields:

caller:
cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
je 1f # 2 bytes
ud2 # 2 bytes
1: call __x86_indirect_thunk_rax # 5 bytes

.align 16
.byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
func:
endbr # 4 bytes
...
ret

For a combined 11+8 bytes overhead :/

Now, this setup provides:

- minimal size (please yell if there's a smaller option I missed;
s/ud2/int3/ ?)
- since the retpoline handles speculation from stuff before it, the
load-miss induced speculation is covered.
- the 'je' branch is binary, leading to either the retpoline or the
ud2, both which are a speculation stop.
- the ud2 is placed such that if the exception is non-fatal, code
execution can recover
- when IBT is present we can rewrite the thunk call to:

lfence
call *(%rax)

and rely on the WAIT-FOR-ENDBR speculation stop (also 5 bytes).
- can disable CFI by replacing the cmpl with:

jmp 1f

(or an 11 byte nop, which is just about possible). And since we
already have all retpoline thunk callsites in a section, we can
trivially find all CFI bits that are always in front it them.
- function pointer sanity

Additionally, if we ensure all direct call are +4 and only indirect
calls hit the ENDBR -- as it optimal anyway, saves on decoding ENDBR. We
can replace those ENDBR instructions of functions that should never be
indirectly called with:

ud1 0x0(%rax),%eax

which is a 4 byte #UD. This gives us the property that even on !IBT
hardware such a call will go *splat*.

Further, Andrew put in the request for __attribute__((cfi_seed(blah)))
to allow distinguishing indirect functions with otherwise identical
signature; eg. cookie = hash32(blah##signature).

Did I miss anything? Got anything wrong?

2022-02-14 21:41:46

by Sami Tolvanen

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Fri, Feb 11, 2022 at 5:38 AM Peter Zijlstra <[email protected]> wrote:
> I think we'll end up with something related to KCFI, but with distinct
> differences:
>
> - 32bit immediates for smaller code

Sure, I don't see issues with that. Based on a quick test with
defconfig, this reduces vmlinux size by 0.30%.

> - __kcfi_check_fail() is out for smaller code

I'm fine with adding a trap mode that's used by default, but having
more helpful diagnostics when something fails is useful even in
production systems in my experience. This change results in a vmlinux
that's another 0.92% smaller.

> Which then yields:
>
> caller:
> cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
> je 1f # 2 bytes
> ud2 # 2 bytes
> 1: call __x86_indirect_thunk_rax # 5 bytes

Note that the compiler might not emit this *exact* sequence of
instructions. For example, Clang generates this for events_sysfs_show
with the modified KCFI patch:

2274: cmpl $0x4d7bed9e,-0x4(%r11)
227c: jne 22c0 <events_sysfs_show+0x6c>
227e: call 2283 <events_sysfs_show+0x2f>
227f: R_X86_64_PLT32 __x86_indirect_thunk_r11-0x4
...
22c0: ud2

In this case the function has two indirect calls and Clang seems to
prefer to emit just one ud2.

> .align 16
> .byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
> func:
> endbr # 4 bytes

Here func is no longer aligned to 16 bytes, in case that's important.

> Further, Andrew put in the request for __attribute__((cfi_seed(blah)))
> to allow distinguishing indirect functions with otherwise identical
> signature; eg. cookie = hash32(blah##signature).

Sounds reasonable.

> Did I miss anything? Got anything wrong?

How would you like to deal with the 4-byte hashes in objtool? We
either need to annotate all function symbols in the kernel, or we need
a way to distinguish the hashes from random instructions, so we can
also have functions that don't have a type hash.

Sami

2022-02-14 22:53:44

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> On Fri, Feb 11, 2022 at 5:38 AM Peter Zijlstra <[email protected]> wrote:
> > I think we'll end up with something related to KCFI, but with distinct
> > differences:
> >
> > - 32bit immediates for smaller code
>
> Sure, I don't see issues with that. Based on a quick test with
> defconfig, this reduces vmlinux size by 0.30%.
>
> > - __kcfi_check_fail() is out for smaller code
>
> I'm fine with adding a trap mode that's used by default, but having
> more helpful diagnostics when something fails is useful even in
> production systems in my experience. This change results in a vmlinux
> that's another 0.92% smaller.

You can easily have the exception generate a nice warning, you can even
have it continue. You really don't need a call for that.

> > Which then yields:
> >
> > caller:
> > cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
> > je 1f # 2 bytes
> > ud2 # 2 bytes
> > 1: call __x86_indirect_thunk_rax # 5 bytes
>
> Note that the compiler might not emit this *exact* sequence of
> instructions. For example, Clang generates this for events_sysfs_show
> with the modified KCFI patch:
>
> 2274: cmpl $0x4d7bed9e,-0x4(%r11)
> 227c: jne 22c0 <events_sysfs_show+0x6c>
> 227e: call 2283 <events_sysfs_show+0x2f>
> 227f: R_X86_64_PLT32 __x86_indirect_thunk_r11-0x4
> ...
> 22c0: ud2
>
> In this case the function has two indirect calls and Clang seems to
> prefer to emit just one ud2.

That will not allow you to recover from the exception. UD2 is not an
unconditional fail. It should have an out-going edge in this case too.

Heck, most of the WARN_ON() things are UD2 instructions.

Also, you really should add a CS prefix to the retpoline thunk call if
you insist on using r11 (or any of the higher regs).

> > .align 16
> > .byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
> > func:
> > endbr # 4 bytes
>
> Here func is no longer aligned to 16 bytes, in case that's important.

The idea was to have the hash and the endbr in the same cacheline.

> > Did I miss anything? Got anything wrong?
>
> How would you like to deal with the 4-byte hashes in objtool? We
> either need to annotate all function symbols in the kernel, or we need
> a way to distinguish the hashes from random instructions, so we can
> also have functions that don't have a type hash.

Easiest would be to create a special section with all the hash offsets
in I suppose. A bit like -mfentry-section=name.

2022-02-15 17:06:24

by Sami Tolvanen

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Mon, Feb 14, 2022 at 2:25 PM Peter Zijlstra <[email protected]> wrote:
> On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> > I'm fine with adding a trap mode that's used by default, but having
> > more helpful diagnostics when something fails is useful even in
> > production systems in my experience. This change results in a vmlinux
> > that's another 0.92% smaller.
>
> You can easily have the exception generate a nice warning, you can even
> have it continue. You really don't need a call for that.

Sure, but wouldn't that require us to generate something like
__bug_table, so we know where the CFI specific traps are?

> > In this case the function has two indirect calls and Clang seems to
> > prefer to emit just one ud2.
>
> That will not allow you to recover from the exception. UD2 is not an
> unconditional fail. It should have an out-going edge in this case too.

Yes, CFI failures are not recoverable in that code. In fact, LLVM
assumes that the llvm.trap intrinsic (i.e. ud2) never returns, but I
suppose we could just use an int3 instead. I assume that's sufficient
to stop speculation?

> Also, you really should add a CS prefix to the retpoline thunk call if
> you insist on using r11 (or any of the higher regs).

I actually didn't touch the retpoline thunk call, that's exactly the
code Clang normally generates.

> > How would you like to deal with the 4-byte hashes in objtool? We
> > either need to annotate all function symbols in the kernel, or we need
> > a way to distinguish the hashes from random instructions, so we can
> > also have functions that don't have a type hash.
>
> Easiest would be to create a special section with all the hash offsets
> in I suppose. A bit like -mfentry-section=name.

OK, I'll take a look. With 64-bit hashes I was planning to use a known
prefix, but that's not really an option with a 32-bit hash.

Sami

2022-02-15 23:53:20

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 15, 2022 at 08:56:03AM -0800, Sami Tolvanen wrote:
> On Mon, Feb 14, 2022 at 2:25 PM Peter Zijlstra <[email protected]> wrote:
> > On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> > > I'm fine with adding a trap mode that's used by default, but having
> > > more helpful diagnostics when something fails is useful even in
> > > production systems in my experience. This change results in a vmlinux
> > > that's another 0.92% smaller.
> >
> > You can easily have the exception generate a nice warning, you can even
> > have it continue. You really don't need a call for that.
>
> Sure, but wouldn't that require us to generate something like
> __bug_table, so we know where the CFI specific traps are?

It also means the trap handler needs to do a bunch of instruction
decoding to find the address that was going to be jumped to, etc.

> > > In this case the function has two indirect calls and Clang seems to
> > > prefer to emit just one ud2.
> >
> > That will not allow you to recover from the exception. UD2 is not an
> > unconditional fail. It should have an out-going edge in this case too.
>
> Yes, CFI failures are not recoverable in that code. In fact, LLVM
> assumes that the llvm.trap intrinsic (i.e. ud2) never returns, but I
> suppose we could just use an int3 instead. I assume that's sufficient
> to stop speculation?

Peter, is there a reason you want things in the specific order of:

cmp, je-to-call, trap, call

Isn't it more run-time efficient to have an out-of-line failure of
the form:

cmp, jne-to-trap, call, ...code..., trap, jmp-to-call

I thought the static label stuff allowed the "default out of line"
option, as far as pessimizing certain states, etc? The former is certainly
code-size smaller, though, yes, but doesn't it waste space in the cache
line for the unlikely case, etc?

> > Also, you really should add a CS prefix to the retpoline thunk call if
> > you insist on using r11 (or any of the higher regs).
>
> I actually didn't touch the retpoline thunk call, that's exactly the
> code Clang normally generates.
>
> > > How would you like to deal with the 4-byte hashes in objtool? We
> > > either need to annotate all function symbols in the kernel, or we need
> > > a way to distinguish the hashes from random instructions, so we can
> > > also have functions that don't have a type hash.
> >
> > Easiest would be to create a special section with all the hash offsets
> > in I suppose. A bit like -mfentry-section=name.
>
> OK, I'll take a look. With 64-bit hashes I was planning to use a known
> prefix, but that's not really an option with a 32-bit hash.

32-bit hashes would have both code size and runtime benefits: fewer
instructions for the compare therefore a smaller set of instructions
added.

--
Kees Cook

2022-02-16 04:11:55

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 15, 2022 at 12:03:12PM -0800, Kees Cook wrote:
> On Tue, Feb 15, 2022 at 08:56:03AM -0800, Sami Tolvanen wrote:
> > On Mon, Feb 14, 2022 at 2:25 PM Peter Zijlstra <[email protected]> wrote:
> > > On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> > > > I'm fine with adding a trap mode that's used by default, but having
> > > > more helpful diagnostics when something fails is useful even in
> > > > production systems in my experience. This change results in a vmlinux
> > > > that's another 0.92% smaller.
> > >
> > > You can easily have the exception generate a nice warning, you can even
> > > have it continue. You really don't need a call for that.
> >
> > Sure, but wouldn't that require us to generate something like
> > __bug_table, so we know where the CFI specific traps are?
>
> It also means the trap handler needs to do a bunch of instruction
> decoding to find the address that was going to be jumped to, etc.

arch/x86/kernel/alternative.c:apply_retpolines() has all that, since we
need to to know that to re-write the thunk-call.

> > > > In this case the function has two indirect calls and Clang seems to
> > > > prefer to emit just one ud2.
> > >
> > > That will not allow you to recover from the exception. UD2 is not an
> > > unconditional fail. It should have an out-going edge in this case too.
> >
> > Yes, CFI failures are not recoverable in that code. In fact, LLVM
> > assumes that the llvm.trap intrinsic (i.e. ud2) never returns, but I
> > suppose we could just use an int3 instead. I assume that's sufficient
> > to stop speculation?
>
> Peter, is there a reason you want things in the specific order of:
>
> cmp, je-to-call, trap, call
>
> Isn't it more run-time efficient to have an out-of-line failure of
> the form:
>
> cmp, jne-to-trap, call, ...code..., trap, jmp-to-call
>
> I thought the static label stuff allowed the "default out of line"
> option, as far as pessimizing certain states, etc? The former is certainly
> code-size smaller, though, yes, but doesn't it waste space in the cache
> line for the unlikely case, etc?

Mostly so that we can deduce the address of the trap from the retpoline
site, also the above has a fairly high chance of using jcc.d32 which is
actually larger than jcc.d8+ud2.

2022-02-16 06:23:14

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

>>
>> Mostly so that we can deduce the address of the trap from the
>> retpoline
>> site, also the above has a fairly high chance of using jcc.d32 which
>> is
>> actually larger than jcc.d8+ud2.
>
> Ah, yeah, that's an interesting point.
>
> Still, I worry about finding ways to convinces Clang to emit precisely
> cmp/je/trap/call, but I guess we'll catch it immediately if it doesn't.
> :P

This can probably be done more easily/precisely if implemented directly
in the compiler's arch-specific backend. At least for x86 it wasn't a
hassle to emit a defined sequence of instructions in the past. The price
is that it will require a pass specific to each supported architecture,
but I guess this isn't that bad.

Perhaps this is discussion for a different mailing list, idk... but
just pointing that it is not a huge wall.

2022-02-16 06:33:57

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 15, 2022 at 10:05:50PM +0100, Peter Zijlstra wrote:
> On Tue, Feb 15, 2022 at 12:03:12PM -0800, Kees Cook wrote:
> > On Tue, Feb 15, 2022 at 08:56:03AM -0800, Sami Tolvanen wrote:
> > > On Mon, Feb 14, 2022 at 2:25 PM Peter Zijlstra <[email protected]> wrote:
> > > > On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> > > > > I'm fine with adding a trap mode that's used by default, but having
> > > > > more helpful diagnostics when something fails is useful even in
> > > > > production systems in my experience. This change results in a vmlinux
> > > > > that's another 0.92% smaller.
> > > >
> > > > You can easily have the exception generate a nice warning, you can even
> > > > have it continue. You really don't need a call for that.
> > >
> > > Sure, but wouldn't that require us to generate something like
> > > __bug_table, so we know where the CFI specific traps are?
> >
> > It also means the trap handler needs to do a bunch of instruction
> > decoding to find the address that was going to be jumped to, etc.
>
> arch/x86/kernel/alternative.c:apply_retpolines() has all that, since we
> need to to know that to re-write the thunk-call.

Ah, okay, well that makes things easier. :)

> > > > > In this case the function has two indirect calls and Clang seems to
> > > > > prefer to emit just one ud2.
> > > >
> > > > That will not allow you to recover from the exception. UD2 is not an
> > > > unconditional fail. It should have an out-going edge in this case too.
> > >
> > > Yes, CFI failures are not recoverable in that code. In fact, LLVM
> > > assumes that the llvm.trap intrinsic (i.e. ud2) never returns, but I
> > > suppose we could just use an int3 instead. I assume that's sufficient
> > > to stop speculation?
> >
> > Peter, is there a reason you want things in the specific order of:
> >
> > cmp, je-to-call, trap, call
> >
> > Isn't it more run-time efficient to have an out-of-line failure of
> > the form:
> >
> > cmp, jne-to-trap, call, ...code..., trap, jmp-to-call
> >
> > I thought the static label stuff allowed the "default out of line"
> > option, as far as pessimizing certain states, etc? The former is certainly
> > code-size smaller, though, yes, but doesn't it waste space in the cache
> > line for the unlikely case, etc?
>
> Mostly so that we can deduce the address of the trap from the retpoline
> site, also the above has a fairly high chance of using jcc.d32 which is
> actually larger than jcc.d8+ud2.

Ah, yeah, that's an interesting point.

Still, I worry about finding ways to convinces Clang to emit precisely
cmp/je/trap/call, but I guess we'll catch it immediately if it doesn't.
:P

--
Kees Cook

2022-02-16 06:38:34

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 15, 2022 at 08:56:03AM -0800, Sami Tolvanen wrote:
> On Mon, Feb 14, 2022 at 2:25 PM Peter Zijlstra <[email protected]> wrote:
> > On Mon, Feb 14, 2022 at 01:38:18PM -0800, Sami Tolvanen wrote:
> > > I'm fine with adding a trap mode that's used by default, but having
> > > more helpful diagnostics when something fails is useful even in
> > > production systems in my experience. This change results in a vmlinux
> > > that's another 0.92% smaller.
> >
> > You can easily have the exception generate a nice warning, you can even
> > have it continue. You really don't need a call for that.
>
> Sure, but wouldn't that require us to generate something like
> __bug_table, so we know where the CFI specific traps are?

Yes, but since you're going to emit a retpoline, and objtool already
generates a list of retpoline sites, we can abuse that. If the
instruction after the trap is a retpoline site, we a CFI fail.

> > > In this case the function has two indirect calls and Clang seems to
> > > prefer to emit just one ud2.
> >
> > That will not allow you to recover from the exception. UD2 is not an
> > unconditional fail. It should have an out-going edge in this case too.
>
> Yes, CFI failures are not recoverable in that code. In fact, LLVM
> assumes that the llvm.trap intrinsic (i.e. ud2) never returns, but I
> suppose we could just use an int3 instead. I assume that's sufficient
> to stop speculation?

It is. int3 is also smaller by one byte, but the exception is already
fairly complicated, but I can see if we can make it work.

> > Also, you really should add a CS prefix to the retpoline thunk call if
> > you insist on using r11 (or any of the higher regs).
>
> I actually didn't touch the retpoline thunk call, that's exactly the
> code Clang normally generates.

Yeah, and it needs help, also see:

https://lore.kernel.org/lkml/[email protected]/

Specifically, clang needs to:

- CS prefix stuff the retpoline thunk call/jmp;
- stop doing conditional indirect tail-calls.

2022-02-16 06:47:03

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On 2022-02-11 05:38, Peter Zijlstra wrote:
> On Tue, Feb 08, 2022 at 09:18:44PM -0800, Joao Moreira wrote:
>> > Ah, excellent, thanks for the pointers. There's also this in the works:
>> > https://reviews.llvm.org/D119296 (a new CFI mode, designed to play nice
>> > to objtool, IBT, etc.)
>>
>> Oh, great! Thanks for pointing it out. I guess I saw something with a
>> similar name before ;)
>> https://www.blackhat.com/docs/asia-17/materials/asia-17-Moreira-Drop-The-Rop-Fine-Grained-Control-Flow-Integrity-For-The-Linux-Kernel.pdf
>>
>> Jokes aside (and perhaps questions more targeted to Sami), from a
>> diagonal
>> look it seems that this follows the good old tag approach proposed by
>> PaX/grsecurity, right? If this is the case, should I assume it could
>> also
>> benefit from features like -mibt-seal? Also are you considering that
>> perhaps
>> we can use alternatives to flip different CFI instrumentation as
>> suggested
>> by PeterZ in another thread?
>
> So, lets try and recap things from IRC yesterday. There's a whole bunch
> of things intertwining making indirect branches 'interesting'. Most of
> which I've not seen mentioned in Sami's KCFI proposal which makes it
> rather pointless.
>
> I think we'll end up with something related to KCFI, but with distinct
> differences:
>
> - 32bit immediates for smaller code
> - __kcfi_check_fail() is out for smaller code
> - it must interact with IBT/BTI and retpolines
> - we must be very careful with speculation.
>
> Right, so because !IBT-CFI needs the check at the call site, like:
>
> caller:
> cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
> je 1f # 2 bytes
> ud2 # 2 bytes
> 1: call __x86_indirect_thunk_rax # 5 bytes
>
>
> .align 16
> .byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
> func:
> ...
> ret
>
>
> While FineIBT has them at the landing site:
>
> caller:
> movl $0xdeadbeef, %r11d # 6 bytes
> call __x86_indirect_thunk_rax # 5 bytes
>
>
> .align 16
> func:
> endbr # 4 bytes
> cmpl $0xdeadbeef, %r11d # 7 bytes
> je 1f # 2 bytes
> ud2 # 2 bytes
> 1: ...
> ret
>
>
> It seems to me that always doing the check at the call-site is simpler,
> since it avoids code-bloat and patching work. That is, if we allow both
> we'll effectivly blow up the code by 11 + 13 bytes (11 at the call
> site,
> 13 at function entry) as opposed to 11+4 or 6+13.
>
> Which then yields:
>
> caller:
> cmpl $0xdeadbeef, -0x4(%rax) # 7 bytes
> je 1f # 2 bytes
> ud2 # 2 bytes
> 1: call __x86_indirect_thunk_rax # 5 bytes
>
>
> .align 16
> .byte 0xef, 0xbe, 0xad, 0xde # 4 bytes
> func:
> endbr # 4 bytes
> ...
> ret
>
> For a combined 11+8 bytes overhead :/
>
> Now, this setup provides:
>
> - minimal size (please yell if there's a smaller option I missed;
> s/ud2/int3/ ?)
> - since the retpoline handles speculation from stuff before it, the
> load-miss induced speculation is covered.
> - the 'je' branch is binary, leading to either the retpoline or the
> ud2, both which are a speculation stop.
> - the ud2 is placed such that if the exception is non-fatal, code
> execution can recover
> - when IBT is present we can rewrite the thunk call to:
>
> lfence
> call *(%rax)
>
> and rely on the WAIT-FOR-ENDBR speculation stop (also 5 bytes).
> - can disable CFI by replacing the cmpl with:
>
> jmp 1f
>
> (or an 11 byte nop, which is just about possible). And since we
> already have all retpoline thunk callsites in a section, we can
> trivially find all CFI bits that are always in front it them.
> - function pointer sanity
>

Agreed that it is sensible to support CFI for CPUs without CET. KCFI is
a win.
Yet, I still think that we should support FineIBT and there are a few
reasons
for that (other than hopeful performance benefits).

- KCFI is more prone to the presence of unintended allowed targets.
Since the
IBT scheme always rely on the same watermark tag (the ENDBR
instruction), it
is easier to prevent these from being emitted by JIT/compilers (fwiiw,
see
https://reviews.llvm.org/rGf385823e04f300c92ec03dbd660d621cc618a271 and
https://dl.acm.org/doi/10.1145/3337167.3337175).

- Regarding the space overhead, I can try to verify if FineIBT can be
feasibly
reshaped into:

caller:
movl $0xdeadbeef,%r10 # 6 bytes
sub $0x5,%r11 # 4 bytes
call *(%r11) # 5 bytes

.align 16
endbr # 4 bytes
call __x86_fineibt_thunk_deadbeef # 5 bytes
func+4:
...
ret

__x86_fineibt_thunk_deadbeef:
xor $0xdeadbeef, %r10
je 1f
ud2
1:
retq

This scheme would require less space and less runtime patching. We would
need
one additional byte on callees to patch both the ENDBR and the 5-byte
call
instruction, plus space to hold the thunks somewhere else. The thunks
overhead
is then dilluted across the functions belonging to the same equivalence
set,
as these will use the same thunk. On a quick analysis over defconfig, it
seems
that the number of equivalence sets are ~25% of the number of functions
(thus,
space overhead is cut to a fourth). I guess this would only require the
KCFI
compiler support to emit an additional "0xcc" before the tag.

Thunks can also be placed in a special section and dropped during boot
to
reduce the runtime memory footprint.

What do you think, is this worth investigating?

Also, in my understanding, r11 does not need to be preserved as,
per-ABI, it
is a scratch register. So there is no need to add $0x5,%r11 back after
the
call. Let me know if I'm mistaken.

>
> Additionally, if we ensure all direct call are +4 and only indirect
> calls hit the ENDBR -- as it optimal anyway, saves on decoding ENDBR.
> We
> can replace those ENDBR instructions of functions that should never be
> indirectly called with:
>
> ud1 0x0(%rax),%eax
>
> which is a 4 byte #UD. This gives us the property that even on !IBT
> hardware such a call will go *splat*.

Given that the space overhead is a big concern, isn't it better to use
the
compiler support to prevent ENDBRs in the first place? Patching #UD is
kinda
cool, yeah, but I don't see it providing meaningful security guarantees
over
not having the ENDBRs emitted at all.

>
> Further, Andrew put in the request for __attribute__((cfi_seed(blah)))
> to allow distinguishing indirect functions with otherwise identical
> signature; eg. cookie = hash32(blah##signature).
>
>
> Did I miss anything? Got anything wrong?

I understand that Today there are not too many CET-enabled CPUs out
there,
and that the benefits might be a bit blurred currently. Yet, given that
this
is something that should continuously change with time, would you object
to
FineIBT as a build option, i.e., something which might not be supported
by
alternatives when using defconfig?

2022-02-16 12:30:34

[permalink] [raw]

Subject: Re: [RFC][PATCH 6/6] objtool: Add IBT validation / fixups

On Tue, Feb 15, 2022 at 10:05:50PM +0100, Peter Zijlstra wrote:

> > Peter, is there a reason you want things in the specific order of:
> >
> > cmp, je-to-call, trap, call
> >
> > Isn't it more run-time efficient to have an out-of-line failure of
> > the form:
> >
> > cmp, jne-to-trap, call, ...code..., trap, jmp-to-call
> >
> > I thought the static label stuff allowed the "default out of line"
> > option, as far as pessimizing certain states, etc? The former is certainly
> > code-size smaller, though, yes, but doesn't it waste space in the cache
> > line for the unlikely case, etc?
>
> Mostly so that we can deduce the address of the trap from the retpoline
> site, also the above has a fairly high chance of using jcc.d32 which is
> actually larger than jcc.d8+ud2.

Also; and I think I mentioned this a few emails back, by having the
whole CFI thing as a single range of bytes it becomes easier to patch.

2022-03-02 09:20:19