[PATCH] arm: explicitly place .fixup in .text

[PATCH] arm: explicitly place .fixup in .text

[Nick Desaulniers]

From: Kees Cook <keescook@chromium.org>

There's an implicit dependency on the section ordering of the orphaned
section .fixup that can break arm_copy_from_user if the linker places
the .fixup section before the .text section. Since .fixup is not
explicitly placed in the existing ARM linker scripts, the linker is free
to order it anywhere with respect to the rest of the sections.

Multiple users from different distros (Raspbian, CrOS) reported kernel
panics executing seccomp() syscall with Linux kernels linked with LLD.

Documentation/x86/exception-tables.rst alludes to the ordering
dependency. The relevant quote:

```
NOTE:
Due to the way that the exception table is built and needs to be ordered,
only use exceptions for code in the .text section.  Any other section
will cause the exception table to not be sorted correctly, and the
exceptions will fail.

Things changed when 64-bit support was added to x86 Linux. Rather than
double the size of the exception table by expanding the two entries
from 32-bits to 64 bits, a clever trick was used to store addresses
as relative offsets from the table itself. The assembly code changed
from::

    .long 1b,3b
  to:
          .long (from) - .
          .long (to) - .

and the C-code that uses these values converts back to absolute addresses
like this::

        ex_insn_addr(const struct exception_table_entry *x)
        {
                return (unsigned long)&x->insn + x->insn;
        }
```

Since the addresses stored in the __ex_table are RELATIVE offsets and
not ABSOLUTE addresses, ordering the fixup anywhere that's not
immediately preceding .text causes the relative offset of the faulting
instruction to be wrong, causing the wrong (or no) address of the fixup
handler to looked up in __ex_table.

x86 and arm64 place the .fixup section near the end of the .text
section; follow their pattern.

Cc: stable@vger.kernel.org
Link: https://github.com/ClangBuiltLinux/linux/issues/282
Link: https://bugs.chromium.org/p/chromium/issues/detail?id=1020633#c36
Reported-by: Manoj Gupta <manojgupta@google.com>
Reported-by: Nathan Chancellor <natechancellor@gmail.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Nick Desaulniers <ndesaulniers@google.com>
Debugged-by: Nick Desaulniers <ndesaulniers@google.com>
Worded-by: Nick Desaulniers <ndesaulniers@google.com>
Tested-by: Manoj Gupta <manojgupta@google.com>
Tested-by: Nathan Chancellor <natechancellor@gmail.com>
---
 arch/arm/kernel/vmlinux.lds.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/arch/arm/kernel/vmlinux.lds.h b/arch/arm/kernel/vmlinux.lds.h
index 8247bc15addc..e130f7668cf0 100644
--- a/arch/arm/kernel/vmlinux.lds.h
+++ b/arch/arm/kernel/vmlinux.lds.h
@@ -74,6 +74,7 @@
 		LOCK_TEXT						\
 		HYPERVISOR_TEXT						\
 		KPROBES_TEXT						\
+		*(.fixup)						\
 		*(.gnu.warning)						\
 		*(.glue_7)						\
 		*(.glue_7t)						\
-- 
2.24.0.432.g9d3f5f5b63-goog

Re: [PATCH] arm: explicitly place .fixup in .text

[Nicolas Pitre]

On Fri, 22 Nov 2019, Nick Desaulniers wrote:

> From: Kees Cook <keescook@chromium.org>
> 
> There's an implicit dependency on the section ordering of the orphaned
> section .fixup that can break arm_copy_from_user if the linker places
> the .fixup section before the .text section. Since .fixup is not
> explicitly placed in the existing ARM linker scripts, the linker is free
> to order it anywhere with respect to the rest of the sections.
> 
> Multiple users from different distros (Raspbian, CrOS) reported kernel
> panics executing seccomp() syscall with Linux kernels linked with LLD.
> 
> Documentation/x86/exception-tables.rst alludes to the ordering
> dependency. The relevant quote:
> 
> ```
> NOTE:
> Due to the way that the exception table is built and needs to be ordered,
> only use exceptions for code in the .text section.  Any other section
> will cause the exception table to not be sorted correctly, and the
> exceptions will fail.
> 
> Things changed when 64-bit support was added to x86 Linux. Rather than
> double the size of the exception table by expanding the two entries
> from 32-bits to 64 bits, a clever trick was used to store addresses
> as relative offsets from the table itself. The assembly code changed
> from::
> 
>     .long 1b,3b
>   to:
>           .long (from) - .
>           .long (to) - .
> 
> and the C-code that uses these values converts back to absolute addresses
> like this::
> 
>         ex_insn_addr(const struct exception_table_entry *x)
>         {
>                 return (unsigned long)&x->insn + x->insn;
>         }
> ```
> 
> Since the addresses stored in the __ex_table are RELATIVE offsets and
> not ABSOLUTE addresses, ordering the fixup anywhere that's not
> immediately preceding .text causes the relative offset of the faulting
> instruction to be wrong, causing the wrong (or no) address of the fixup
> handler to looked up in __ex_table.

This explanation makes no sense.

The above is valid only when ARCH_HAS_RELATIVE_EXTABLE is defined. On 
ARM32 it is not, nor would it make sense to be.


Nicolas

Re: [PATCH] arm: explicitly place .fixup in .text

[Nick Desaulniers]

On Fri, Nov 29, 2019 at 1:33 PM Nicolas Pitre <nico@fluxnic.net> wrote:
>
> On Fri, 22 Nov 2019, Nick Desaulniers wrote:
>
> > From: Kees Cook <keescook@chromium.org>
> >
> > There's an implicit dependency on the section ordering of the orphaned
> > section .fixup that can break arm_copy_from_user if the linker places
> > the .fixup section before the .text section. Since .fixup is not
> > explicitly placed in the existing ARM linker scripts, the linker is free
> > to order it anywhere with respect to the rest of the sections.
> >
> > Multiple users from different distros (Raspbian, CrOS) reported kernel
> > panics executing seccomp() syscall with Linux kernels linked with LLD.
> >
> > Documentation/x86/exception-tables.rst alludes to the ordering
> > dependency. The relevant quote:
> >
> > ```
> > NOTE:
> > Due to the way that the exception table is built and needs to be ordered,
> > only use exceptions for code in the .text section.  Any other section
> > will cause the exception table to not be sorted correctly, and the
> > exceptions will fail.
> >
> > Things changed when 64-bit support was added to x86 Linux. Rather than
> > double the size of the exception table by expanding the two entries
> > from 32-bits to 64 bits, a clever trick was used to store addresses
> > as relative offsets from the table itself. The assembly code changed
> > from::
> >
> >     .long 1b,3b
> >   to:
> >           .long (from) - .
> >           .long (to) - .
> >
> > and the C-code that uses these values converts back to absolute addresses
> > like this::
> >
> >         ex_insn_addr(const struct exception_table_entry *x)
> >         {
> >                 return (unsigned long)&x->insn + x->insn;
> >         }
> > ```
> >
> > Since the addresses stored in the __ex_table are RELATIVE offsets and
> > not ABSOLUTE addresses, ordering the fixup anywhere that's not
> > immediately preceding .text causes the relative offset of the faulting
> > instruction to be wrong, causing the wrong (or no) address of the fixup
> > handler to looked up in __ex_table.
>
> This explanation makes no sense.
>
> The above is valid only when ARCH_HAS_RELATIVE_EXTABLE is defined. On
> ARM32 it is not, nor would it make sense to be.

Hmm...I thought that was the smoking gun. From the description in
Documentation, I thought they meant that exception table entry lookup
was changed to be homogeneous for 32b AND 64b arch's, but as you point
out they're not.  Now with the reference to ARCH_HAS_RELATIVE_EXTABLE,
I know to look through:
include/asm-generic/extable.h
include/linux/extable.h
lib/extable.c
kernel/extable.c
arch/arm/mm/extable.c
arch/arm/mm/fault.c (__do_kernel_fault() calls fixup_exception(),
which is of interest).

Looks like the exception table is sorted by address of faulting
instruction, then binary searched when an exception occurs.  Seems the
exception table is like an array of pairs of addresses (address of
faulting instruction from the get_user() call, address of fixup
handler) (when !ARCH_HAS_RELATIVE_EXTABLE), IIUC.

Reviewing the logs from the bugreport
(https://bugs.chromium.org/p/chromium/issues/detail?id=1020633#c44)
indeed the error string looks like the error message from
__do_kernel_fault() in arch/arm/mm/fault.c where a call to
fixup_exceptions() in arch/arm/mm/extable returned 1 because the call
to search_exception_tables() in kernel/extable.c returned NULL.

So I was right that `no address of the fixup handler to (be) looked up
in __ex_table`, but not quite right about *why* it fails to be looked
up.

search_exception_tables() in kernel/extable.c calls 3 functions:
1. search_kernel_exception_table()
2. search_module_extables()
3. search_bpf_extables()

So the next question is which one of the above should have found the
exception table entry, and why did it not when LLD placed the orphaned
.fixup section BEFORE .text?  All three of the above do some
processing on the address but in the end all call search_extable().

I really don't think kernel modules are involved.

Since we're observing the fault via a call to seccomp(), which IIUC
takes a BPF program when setting a filter (SECCOMP_SET_MODE_FILTER),
I'm curious to look into search_bpf_extables() first.  Maybe
constructing a BPF program involves insertion of special exception
handler?  Looks like bpf programs are stored in an rb_tree called
bpf_tree.  They have an auxiliary field that contains a pointer to an
exception table entry.  "Auxiliary" makes it sounds optional, and the
only assignment I can find to this field is in
arch/x86/net/bpf_jit_comp.c, so I doubt it's relevant for arm.  It
also just looks like it's zero initialized (bpf_prog_alloc_no_stats()
in kernel/bpf/core.c) for arch generic code.

That leaves just search_kernel_exception_table().  I wonder if it
fails because we put garbage entries in, or sorted it improperly?

Oh, and messing around with grep, it looks like entries to the
exception table can be sorted at build time rather than boot time via
CONFIG_BUILDTIME_EXTABLE_SORT?

I don't see the pr_notice from sort_main_extable() (kernel/extable.c
called from start_kernel() in init/main.c) in the bugreports:
https://bugs.chromium.org/p/chromium/issues/attachmentText?aid=421842
https://github.com/ClangBuiltLinux/linux/issues/282
(But IIRC, the log level may not be set to display these).

CONFIG_BUILDTIME_EXTABLE_SORT is selected by arch/arm/Kconfig if
CONFIG_MMU, which I highly suspect is already selected for the above
two reports. (Would an arm32 based chromebook not have an MMU? I doubt
it.)

So there may be an ordering dependency in scripts/sortextable.{c|h}?
Neither mention `fixup`.

Will continue debugging more tomorrow or later this week, but please
stop me if any of the above is also incorrect.  Some ideas for further
experiments:
- scripts/check_extable.sh sounds like some kind of validator.
Manoj/Nathan, I wonder if you linked the problematic kernel with LLD
than ran `./scripts/check_extable.sh vmlinux` if it would warn? Dunno
about all those command line flags though.
- if we apply a similar diff to the patch I posted, but force .fixup
to be before .text for BFD (as LLD is placing the orphaned section
currently), relinked with BFD and could reproduce the issue, that
seems like proof about the implicit section ordering.
```
diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
index 319ccb10846a..adfb5297f359 100644
--- a/arch/arm/kernel/vmlinux.lds.S
+++ b/arch/arm/kernel/vmlinux.lds.S
@@ -58,6 +58,7 @@ SECTIONS
 #ifdef CONFIG_ARM_MPU
        . = ALIGN(PMSAv8_MINALIGN);
 #endif
+       .fixup : { *(.fixup) }
        .text : {                       /* Real text segment            */
                _stext = .;             /* Text and read-only data      */
                ARM_TEXT
```

-- 
Thanks,
~Nick Desaulniers

Re: [PATCH] arm: explicitly place .fixup in .text

[Nicolas Pitre]

On Tue, 3 Dec 2019, Nick Desaulniers wrote:

> On Fri, Nov 29, 2019 at 1:33 PM Nicolas Pitre <nico@fluxnic.net> wrote:
> >
> > On Fri, 22 Nov 2019, Nick Desaulniers wrote:
> >
> > > From: Kees Cook <keescook@chromium.org>
> > >
> > > There's an implicit dependency on the section ordering of the orphaned
> > > section .fixup that can break arm_copy_from_user if the linker places
> > > the .fixup section before the .text section. Since .fixup is not
> > > explicitly placed in the existing ARM linker scripts, the linker is free
> > > to order it anywhere with respect to the rest of the sections.
> > >
> > > Multiple users from different distros (Raspbian, CrOS) reported kernel
> > > panics executing seccomp() syscall with Linux kernels linked with LLD.
> > >
> > > Documentation/x86/exception-tables.rst alludes to the ordering
> > > dependency. The relevant quote:
> > >
> > > ```
> > > NOTE:
> > > Due to the way that the exception table is built and needs to be ordered,
> > > only use exceptions for code in the .text section.  Any other section
> > > will cause the exception table to not be sorted correctly, and the
> > > exceptions will fail.
> > >
> > > Things changed when 64-bit support was added to x86 Linux. Rather than
> > > double the size of the exception table by expanding the two entries
> > > from 32-bits to 64 bits, a clever trick was used to store addresses
> > > as relative offsets from the table itself. The assembly code changed
> > > from::
> > >
> > >     .long 1b,3b
> > >   to:
> > >           .long (from) - .
> > >           .long (to) - .
> > >
> > > and the C-code that uses these values converts back to absolute addresses
> > > like this::
> > >
> > >         ex_insn_addr(const struct exception_table_entry *x)
> > >         {
> > >                 return (unsigned long)&x->insn + x->insn;
> > >         }
> > > ```
> > >
> > > Since the addresses stored in the __ex_table are RELATIVE offsets and
> > > not ABSOLUTE addresses, ordering the fixup anywhere that's not
> > > immediately preceding .text causes the relative offset of the faulting
> > > instruction to be wrong, causing the wrong (or no) address of the fixup
> > > handler to looked up in __ex_table.
> >
> > This explanation makes no sense.
> >
> > The above is valid only when ARCH_HAS_RELATIVE_EXTABLE is defined. On
> > ARM32 it is not, nor would it make sense to be.
> 
> Hmm...I thought that was the smoking gun. From the description in
> Documentation, I thought they meant that exception table entry lookup
> was changed to be homogeneous for 32b AND 64b arch's, but as you point
> out they're not.  Now with the reference to ARCH_HAS_RELATIVE_EXTABLE,
> I know to look through:
> include/asm-generic/extable.h
> include/linux/extable.h
> lib/extable.c
> kernel/extable.c
> arch/arm/mm/extable.c
> arch/arm/mm/fault.c (__do_kernel_fault() calls fixup_exception(),
> which is of interest).
> 
> Looks like the exception table is sorted by address of faulting
> instruction, then binary searched when an exception occurs.  Seems the
> exception table is like an array of pairs of addresses (address of
> faulting instruction from the get_user() call, address of fixup
> handler) (when !ARCH_HAS_RELATIVE_EXTABLE), IIUC.

Exact. And those are absolute addresses.

To save on memory footprint, this table was made into relative addresses 
on 64-bit targets with the restriction that the relative offsets have to 
fit in a 32-bit value and not be negative. On 32-bit targets there is no 
point using relative addresses as the absolute addresses use only 32 
bits already, and then we don't have to compute the absolute address at 
run time.

> Reviewing the logs from the bugreport
> (https://bugs.chromium.org/p/chromium/issues/detail?id=1020633#c44)
> indeed the error string looks like the error message from
> __do_kernel_fault() in arch/arm/mm/fault.c where a call to
> fixup_exceptions() in arch/arm/mm/extable returned 1 because the call
> to search_exception_tables() in kernel/extable.c returned NULL.
> 
> So I was right that `no address of the fixup handler to (be) looked up
> in __ex_table`, but not quite right about *why* it fails to be looked
> up.
> 
> search_exception_tables() in kernel/extable.c calls 3 functions:
> 1. search_kernel_exception_table()
> 2. search_module_extables()
> 3. search_bpf_extables()
> 
> So the next question is which one of the above should have found the
> exception table entry, and why did it not when LLD placed the orphaned
> .fixup section BEFORE .text?  All three of the above do some
> processing on the address but in the end all call search_extable().
> 
> I really don't think kernel modules are involved.
> 
> Since we're observing the fault via a call to seccomp(), which IIUC
> takes a BPF program when setting a filter (SECCOMP_SET_MODE_FILTER),
> I'm curious to look into search_bpf_extables() first.  Maybe
> constructing a BPF program involves insertion of special exception
> handler?  Looks like bpf programs are stored in an rb_tree called
> bpf_tree.  They have an auxiliary field that contains a pointer to an
> exception table entry.  "Auxiliary" makes it sounds optional, and the
> only assignment I can find to this field is in
> arch/x86/net/bpf_jit_comp.c, so I doubt it's relevant for arm.  It
> also just looks like it's zero initialized (bpf_prog_alloc_no_stats()
> in kernel/bpf/core.c) for arch generic code.
> 
> That leaves just search_kernel_exception_table().  I wonder if it
> fails because we put garbage entries in, or sorted it improperly?

Well, if you can reproduce the issue (would be very helpful) then you 
can add some printk to log search_exception_tables() and figure out for 
sure actually which category is involved here. Unlike with user space, 
kernel exceptions are relatively rare events and they shouldn't flood 
your log.

> Oh, and messing around with grep, it looks like entries to the
> exception table can be sorted at build time rather than boot time via
> CONFIG_BUILDTIME_EXTABLE_SORT?
> 
> I don't see the pr_notice from sort_main_extable() (kernel/extable.c
> called from start_kernel() in init/main.c) in the bugreports:
> https://bugs.chromium.org/p/chromium/issues/attachmentText?aid=421842
> https://github.com/ClangBuiltLinux/linux/issues/282
> (But IIRC, the log level may not be set to display these).
> 
> CONFIG_BUILDTIME_EXTABLE_SORT is selected by arch/arm/Kconfig if
> CONFIG_MMU, which I highly suspect is already selected for the above
> two reports. (Would an arm32 based chromebook not have an MMU? I doubt
> it.)
> 
> So there may be an ordering dependency in scripts/sortextable.{c|h}?
> Neither mention `fixup`.
> 
> Will continue debugging more tomorrow or later this week, but please
> stop me if any of the above is also incorrect.  Some ideas for further
> experiments:
> - scripts/check_extable.sh sounds like some kind of validator.
> Manoj/Nathan, I wonder if you linked the problematic kernel with LLD
> than ran `./scripts/check_extable.sh vmlinux` if it would warn? Dunno
> about all those command line flags though.
> - if we apply a similar diff to the patch I posted, but force .fixup
> to be before .text for BFD (as LLD is placing the orphaned section
> currently), relinked with BFD and could reproduce the issue, that
> seems like proof about the implicit section ordering.
> ```
> diff --git a/arch/arm/kernel/vmlinux.lds.S b/arch/arm/kernel/vmlinux.lds.S
> index 319ccb10846a..adfb5297f359 100644
> --- a/arch/arm/kernel/vmlinux.lds.S
> +++ b/arch/arm/kernel/vmlinux.lds.S
> @@ -58,6 +58,7 @@ SECTIONS
>  #ifdef CONFIG_ARM_MPU
>         . = ALIGN(PMSAv8_MINALIGN);
>  #endif
> +       .fixup : { *(.fixup) }
>         .text : {                       /* Real text segment            */
>                 _stext = .;             /* Text and read-only data      */
>                 ARM_TEXT
> ```
> 
> -- 
> Thanks,
> ~Nick Desaulniers
>