rseq/x86: choosing rseq code signature

rseq/x86: choosing rseq code signature

[Mathieu Desnoyers]

Hi,

We are about to include the code signature required prior to restartable
sequences abort handlers into glibc, which will make this ABI choice final.
We need architecture maintainer input on that signature value.

That code signature is placed before each abort handler, so the kernel can
validate that it is indeed jumping to an abort handler (and not some
arbitrary attacker-chosen code). The signature is never executed.

Currently, tools/testing/selftests/rseq/rseq-x86.h defines RSEQ_SIG
as 0x53053053, and uses it as an immediate operand to the following
instruction opcodes (as suggested by Andy Lutomirski):

x86-32:
- .byte 0x0f, 0x1f, 0x05: nopl <sig>

x86-64:
- .byte 0x0f, 0x1f, 0x05: nopl <sig>(%rip)

The current discussion thread on the glibc mailing list leads us towards
using a trap with uncommon immediate operand, which simplifies integration
with disassemblers, emulators, makes it easier to debug if the control
flow gets redirected there by mistake, and is nicer for some architecture's
speculative execution.

The main advantage of choosing a trap instruction over a no-op is to ensure the
program traps if the execution flow gets redirected to the signature by mistake
(makes it easier to debug). It's not a hard requirement, but it would be a bonus.

Are there trap instructions that take an uncommon 4-byte immediate
operand you would recommend on x86 32/64 ? Or is the current choice of
nopl confirmed to be right one ?

Here is an example of rseq signature definition template:

/*
 * TODO: document trap instruction objdump output on each sub-architecture
 * instruction sets, as well as instruction set extensions.
 */
#define RSEQ_SIG 0x########

Thanks!

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: rseq/x86: choosing rseq code signature

[Mathieu Desnoyers]

----- On Apr 9, 2019, at 3:32 PM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:

> Hi,
> 
> We are about to include the code signature required prior to restartable
> sequences abort handlers into glibc, which will make this ABI choice final.
> We need architecture maintainer input on that signature value.
> 
> That code signature is placed before each abort handler, so the kernel can
> validate that it is indeed jumping to an abort handler (and not some
> arbitrary attacker-chosen code). The signature is never executed.
> 
> Currently, tools/testing/selftests/rseq/rseq-x86.h defines RSEQ_SIG
> as 0x53053053, and uses it as an immediate operand to the following
> instruction opcodes (as suggested by Andy Lutomirski):
> 
> x86-32:
> - .byte 0x0f, 0x1f, 0x05: nopl <sig>
> 
> x86-64:
> - .byte 0x0f, 0x1f, 0x05: nopl <sig>(%rip)
> 
> The current discussion thread on the glibc mailing list leads us towards
> using a trap with uncommon immediate operand, which simplifies integration
> with disassemblers, emulators, makes it easier to debug if the control
> flow gets redirected there by mistake, and is nicer for some architecture's
> speculative execution.
> 
> The main advantage of choosing a trap instruction over a no-op is to ensure the
> program traps if the execution flow gets redirected to the signature by mistake
> (makes it easier to debug). It's not a hard requirement, but it would be a
> bonus.
> 
> Are there trap instructions that take an uncommon 4-byte immediate
> operand you would recommend on x86 32/64 ? Or is the current choice of
> nopl confirmed to be right one ?
> 
> Here is an example of rseq signature definition template:
> 
> /*
> * TODO: document trap instruction objdump output on each sub-architecture
> * instruction sets, as well as instruction set extensions.
> */
> #define RSEQ_SIG 0x########

Peter Zijlstra suggested to use "invlpg" in user-space, which should generate
a trap. The only concern would be emulators, but ideally they would not try to
decode an instruction that is never executed. This would lead to the following
patch. Any objections/ack ?


diff --git a/tools/testing/selftests/rseq/rseq-x86.h b/tools/testing/selftests/rseq/rseq-x86.h
index 2d4887b5d3f0..e9c8a9879e18 100644
--- a/tools/testing/selftests/rseq/rseq-x86.h
+++ b/tools/testing/selftests/rseq/rseq-x86.h
@@ -7,6 +7,11 @@
 
 #include <stdint.h>
 
+/*
+ * RSEQ_SIG is used with the following privileged instructions, which trap in user-space:
+ * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
+ * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
+ */
 #define RSEQ_SIG       0x53053053
 
 #ifdef __x86_64__
@@ -78,8 +83,8 @@ do {                                                                  \
 
 #define RSEQ_ASM_DEFINE_ABORT(label, teardown, abort_label)            \
                ".pushsection __rseq_failure, \"ax\"\n\t"               \
-               /* Disassembler-friendly signature: nopl <sig>(%rip). */\
-               ".byte 0x0f, 0x1f, 0x05\n\t"                            \
+               /* Disassembler-friendly signature: invlpg <sig>(%rip). */\
+               ".byte 0x0f, 0x01, 0x3d\n\t"                            \
                ".long " __rseq_str(RSEQ_SIG) "\n\t"                    \
                __rseq_str(label) ":\n\t"                               \
                teardown                                                \
@@ -605,8 +610,8 @@ do {                                                                        \
 
 #define RSEQ_ASM_DEFINE_ABORT(label, teardown, abort_label)            \
                ".pushsection __rseq_failure, \"ax\"\n\t"               \
-               /* Disassembler-friendly signature: nopl <sig>. */      \
-               ".byte 0x0f, 0x1f, 0x05\n\t"                            \
+               /* Disassembler-friendly signature: invlpg <sig>. */    \
+               ".byte 0x0f, 0x1f, 0x3d\n\t"                            \
                ".long " __rseq_str(RSEQ_SIG) "\n\t"                    \
                __rseq_str(label) ":\n\t"                               \
                teardown                                                \


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: rseq/x86: choosing rseq code signature

[Zack Weinberg]

On Tue, Apr 9, 2019 at 4:43 PM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
> ----- On Apr 9, 2019, at 3:32 PM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:
> >
> > We are about to include the code signature required prior to restartable
> > sequences abort handlers into glibc, which will make this ABI choice final.
> > We need architecture maintainer input on that signature value.
> >
> > That code signature is placed before each abort handler, so the kernel can
> > validate that it is indeed jumping to an abort handler (and not some
> > arbitrary attacker-chosen code). The signature is never executed.
> >
> > Currently, tools/testing/selftests/rseq/rseq-x86.h defines RSEQ_SIG
> > as 0x53053053, and uses it as an immediate operand to the following
> > instruction opcodes (as suggested by Andy Lutomirski):
> >
> > x86-32:
> > - .byte 0x0f, 0x1f, 0x05: nopl <sig>
> >
> > x86-64:
> > - .byte 0x0f, 0x1f, 0x05: nopl <sig>(%rip)
> >
> > The current discussion thread on the glibc mailing list leads us towards
> > using a trap with uncommon immediate operand, which simplifies integration
> > with disassemblers, emulators, makes it easier to debug if the control
> > flow gets redirected there by mistake, and is nicer for some architecture's
> > speculative execution.
...
> Peter Zijlstra suggested to use "invlpg" in user-space, which should generate
> a trap. The only concern would be emulators, but ideally they would not try to
> decode an instruction that is never executed. This would lead to the following
> patch. Any objections/ack ?
...
> +/*
> + * RSEQ_SIG is used with the following privileged instructions, which trap in user-space:
> + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
> + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
> + */
>  #define RSEQ_SIG       0x53053053

On x86, you have to worry about what happens if control flow gets
redirected to an arbitrary byte address.  The proposed sequence `0f 01
3d 53 30 05 53` is a trap instruction if control lands seven bytes
before the beginning of the abort handler, but if it lands anywhere
_else_ within the marker sequence, you get one of these instruction
sequences, none of which trap, all but one of which will corrupt the
process state, and three of which will consume three bytes from the
beginning of the abort handler's code, continuing execution with a
misaligned PC:

    01 3d 53 30 05 53        add %edi,0x53053053(%rip)
    3d 53 30 05 53           cmp $0x53053053,%eax
    53 30 05 53 XX XX XX     push %rbx; xor %al,0xXXXXXX78(%rip)
    30 05 53 XX XX XX        xor %al,0xXXXXXX78(%rip)
    05 53 XX XX XX           add $0xXXXXXX53,%eax
    53                       push %rbx

So I'm going to suggest instead the four-byte sequence CD CF CD CF.
That's INT $0xCF if control lands either two or four bytes before the
beginning of the abort handler, and IRET if it lands one or three
bytes before.  I believe both of these possibilities are currently
also forbidden in user mode.  It doesn't need to be longer, does it?

zw

Re: rseq/x86: choosing rseq code signature

[Andy Lutomirski]

On Tue, Apr 9, 2019 at 5:51 PM Zack Weinberg <zackw@panix.com> wrote:
>
> On Tue, Apr 9, 2019 at 4:43 PM Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> > ----- On Apr 9, 2019, at 3:32 PM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:
> > >
> > > We are about to include the code signature required prior to restartable
> > > sequences abort handlers into glibc, which will make this ABI choice final.
> > > We need architecture maintainer input on that signature value.
> > >
> > > That code signature is placed before each abort handler, so the kernel can
> > > validate that it is indeed jumping to an abort handler (and not some
> > > arbitrary attacker-chosen code). The signature is never executed.
> > >
> > > Currently, tools/testing/selftests/rseq/rseq-x86.h defines RSEQ_SIG
> > > as 0x53053053, and uses it as an immediate operand to the following
> > > instruction opcodes (as suggested by Andy Lutomirski):
> > >
> > > x86-32:
> > > - .byte 0x0f, 0x1f, 0x05: nopl <sig>
> > >
> > > x86-64:
> > > - .byte 0x0f, 0x1f, 0x05: nopl <sig>(%rip)
> > >
> > > The current discussion thread on the glibc mailing list leads us towards
> > > using a trap with uncommon immediate operand, which simplifies integration
> > > with disassemblers, emulators, makes it easier to debug if the control
> > > flow gets redirected there by mistake, and is nicer for some architecture's
> > > speculative execution.
> ...
> > Peter Zijlstra suggested to use "invlpg" in user-space, which should generate
> > a trap. The only concern would be emulators, but ideally they would not try to
> > decode an instruction that is never executed. This would lead to the following
> > patch. Any objections/ack ?
> ...
> > +/*
> > + * RSEQ_SIG is used with the following privileged instructions, which trap in user-space:
> > + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
> > + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
> > + */
> >  #define RSEQ_SIG       0x53053053
>
> On x86, you have to worry about what happens if control flow gets
> redirected to an arbitrary byte address.  The proposed sequence `0f 01
> 3d 53 30 05 53` is a trap instruction if control lands seven bytes
> before the beginning of the abort handler, but if it lands anywhere
> _else_ within the marker sequence, you get one of these instruction
> sequences, none of which trap, all but one of which will corrupt the
> process state, and three of which will consume three bytes from the
> beginning of the abort handler's code, continuing execution with a
> misaligned PC:
>
>     01 3d 53 30 05 53        add %edi,0x53053053(%rip)
>     3d 53 30 05 53           cmp $0x53053053,%eax
>     53 30 05 53 XX XX XX     push %rbx; xor %al,0xXXXXXX78(%rip)
>     30 05 53 XX XX XX        xor %al,0xXXXXXX78(%rip)
>     05 53 XX XX XX           add $0xXXXXXX53,%eax
>     53                       push %rbx
>
> So I'm going to suggest instead the four-byte sequence CD CF CD CF.
> That's INT $0xCF if control lands either two or four bytes before the
> beginning of the abort handler, and IRET if it lands one or three
> bytes before.  I believe both of these possibilities are currently
> also forbidden in user mode.  It doesn't need to be longer, does it?
>

IRET works in user mode just fine.  Why are you concerned about
landing in the middle of the signature?  A misaligned jump into code
is screwy pretty much no matter what.  It does seem genuinely useful
to trap if you accidentally fall through to the beginning of the
signature, but I don't see the point of worrying about jumping to the
middle.

There's some argument that, for consistency with CET, the last couple
bytes of the signature should match ENDBR.

Mathieu, how many bytes do we have for the signature?

Re: rseq/x86: choosing rseq code signature

[Mathieu Desnoyers]

----- On Apr 9, 2019, at 9:57 PM, Andy Lutomirski luto@kernel.org wrote:

> On Tue, Apr 9, 2019 at 5:51 PM Zack Weinberg <zackw@panix.com> wrote:
>>
>> On Tue, Apr 9, 2019 at 4:43 PM Mathieu Desnoyers
>> <mathieu.desnoyers@efficios.com> wrote:
>> > ----- On Apr 9, 2019, at 3:32 PM, Mathieu Desnoyers
>> > mathieu.desnoyers@efficios.com wrote:
>> > >
>> > > We are about to include the code signature required prior to restartable
>> > > sequences abort handlers into glibc, which will make this ABI choice final.
>> > > We need architecture maintainer input on that signature value.
>> > >
>> > > That code signature is placed before each abort handler, so the kernel can
>> > > validate that it is indeed jumping to an abort handler (and not some
>> > > arbitrary attacker-chosen code). The signature is never executed.
>> > >
>> > > Currently, tools/testing/selftests/rseq/rseq-x86.h defines RSEQ_SIG
>> > > as 0x53053053, and uses it as an immediate operand to the following
>> > > instruction opcodes (as suggested by Andy Lutomirski):
>> > >
>> > > x86-32:
>> > > - .byte 0x0f, 0x1f, 0x05: nopl <sig>
>> > >
>> > > x86-64:
>> > > - .byte 0x0f, 0x1f, 0x05: nopl <sig>(%rip)
>> > >
>> > > The current discussion thread on the glibc mailing list leads us towards
>> > > using a trap with uncommon immediate operand, which simplifies integration
>> > > with disassemblers, emulators, makes it easier to debug if the control
>> > > flow gets redirected there by mistake, and is nicer for some architecture's
>> > > speculative execution.
>> ...
>> > Peter Zijlstra suggested to use "invlpg" in user-space, which should generate
>> > a trap. The only concern would be emulators, but ideally they would not try to
>> > decode an instruction that is never executed. This would lead to the following
>> > patch. Any objections/ack ?
>> ...
>> > +/*
>> > + * RSEQ_SIG is used with the following privileged instructions, which trap in
>> > user-space:
>> > + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
>> > + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
>> > + */
>> >  #define RSEQ_SIG       0x53053053
>>
>> On x86, you have to worry about what happens if control flow gets
>> redirected to an arbitrary byte address.  The proposed sequence `0f 01
>> 3d 53 30 05 53` is a trap instruction if control lands seven bytes
>> before the beginning of the abort handler, but if it lands anywhere
>> _else_ within the marker sequence, you get one of these instruction
>> sequences, none of which trap, all but one of which will corrupt the
>> process state, and three of which will consume three bytes from the
>> beginning of the abort handler's code, continuing execution with a
>> misaligned PC:
>>
>>     01 3d 53 30 05 53        add %edi,0x53053053(%rip)
>>     3d 53 30 05 53           cmp $0x53053053,%eax
>>     53 30 05 53 XX XX XX     push %rbx; xor %al,0xXXXXXX78(%rip)
>>     30 05 53 XX XX XX        xor %al,0xXXXXXX78(%rip)
>>     05 53 XX XX XX           add $0xXXXXXX53,%eax
>>     53                       push %rbx
>>
>> So I'm going to suggest instead the four-byte sequence CD CF CD CF.
>> That's INT $0xCF if control lands either two or four bytes before the
>> beginning of the abort handler, and IRET if it lands one or three
>> bytes before.  I believe both of these possibilities are currently
>> also forbidden in user mode.  It doesn't need to be longer, does it?
>>
> 
> IRET works in user mode just fine.  Why are you concerned about
> landing in the middle of the signature?  A misaligned jump into code
> is screwy pretty much no matter what.  It does seem genuinely useful
> to trap if you accidentally fall through to the beginning of the
> signature, but I don't see the point of worrying about jumping to the
> middle.
> 
> There's some argument that, for consistency with CET, the last couple
> bytes of the signature should match ENDBR.
> 
> Mathieu, how many bytes do we have for the signature?

The signature is 4 bytes. Those 4 bytes need to be uncommon.
You can have a longer instruction than that, but then the
additional bytes at the beginning of the instruction will
not be part of the signature per se.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: rseq/x86: choosing rseq code signature

[Peter Zijlstra]

On Tue, Apr 09, 2019 at 04:43:42PM -0400, Mathieu Desnoyers wrote:
> +/*
> + * RSEQ_SIG is used with the following privileged instructions, which trap in user-space:
> + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
> + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
> + */

Right, and the alternative is: 0f b9 3d $SIG, which decodes to:

  UD1 $SIG(%rip),%edi

which will trap unconditionally. The only problem is that gas will not
actually assemble it, but since we're .byte coding it, it doesn't
matter.

UD1 is specified by both AMD and Intel to take a ModR/M, unlike UD0
where they disagree on the ModR/M.

Re: rseq/x86: choosing rseq code signature

[Mathieu Desnoyers]

----- On Apr 10, 2019, at 2:54 AM, Peter Zijlstra peterz@infradead.org wrote:

> On Tue, Apr 09, 2019 at 04:43:42PM -0400, Mathieu Desnoyers wrote:
>> +/*
>> + * RSEQ_SIG is used with the following privileged instructions, which trap in
>> user-space:
>> + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
>> + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
>> + */
> 
> Right, and the alternative is: 0f b9 3d $SIG, which decodes to:
> 
>  UD1 $SIG(%rip),%edi
> 
> which will trap unconditionally. The only problem is that gas will not
> actually assemble it, but since we're .byte coding it, it doesn't
> matter.
> 
> UD1 is specified by both AMD and Intel to take a ModR/M, unlike UD0
> where they disagree on the ModR/M.

UD1 is even better from a code emulator perspective. It won't have to
try to emulate invlpg if it sees it.

Byte coding UD1 as your example above gives the following objdump output,
is it expected ?

objdump --version
GNU objdump (GNU Binutils for Debian) 2.28

x86-32:

  14:	0f b9                	ud1    
  16:	3d 53 30 05 53       	cmp    $0x53053053,%eax

x86-64:

   b:	0f b9                	ud1    
   d:	3d 53 30 05 53       	cmp    $0x53053053,%eax

Thanks!

Mathieu


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: rseq/x86: choosing rseq code signature

[Peter Zijlstra]

On Wed, Apr 10, 2019 at 11:47:40AM -0400, Mathieu Desnoyers wrote:
> ----- On Apr 10, 2019, at 2:54 AM, Peter Zijlstra peterz@infradead.org wrote:
> 
> > On Tue, Apr 09, 2019 at 04:43:42PM -0400, Mathieu Desnoyers wrote:
> >> +/*
> >> + * RSEQ_SIG is used with the following privileged instructions, which trap in
> >> user-space:
> >> + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
> >> + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
> >> + */
> > 
> > Right, and the alternative is: 0f b9 3d $SIG, which decodes to:
> > 
> >  UD1 $SIG(%rip),%edi
> > 
> > which will trap unconditionally. The only problem is that gas will not
> > actually assemble it, but since we're .byte coding it, it doesn't
> > matter.
> > 
> > UD1 is specified by both AMD and Intel to take a ModR/M, unlike UD0
> > where they disagree on the ModR/M.
> 
> UD1 is even better from a code emulator perspective. It won't have to
> try to emulate invlpg if it sees it.

Some emulators terminate on UD2, not aware of any special UD1 behaviour.

> Byte coding UD1 as your example above gives the following objdump output,
> is it expected ?
> 
> objdump --version
> GNU objdump (GNU Binutils for Debian) 2.28
> 
> x86-32:
> 
>   14:	0f b9                	ud1    
>   16:	3d 53 30 05 53       	cmp    $0x53053053,%eax
> 
> x86-64:
> 
>    b:	0f b9                	ud1    
>    d:	3d 53 30 05 53       	cmp    $0x53053053,%eax

GNU objdump (GNU Binutils for Debian) 2.31.1

     0f b9 3d 78 56 34 12    ud1    0x12345678(%rip),%edi

So I suppose your objdump is too old :/

Re: rseq/x86: choosing rseq code signature

[Mathieu Desnoyers]

----- On Apr 10, 2019, at 1:57 PM, Peter Zijlstra peterz@infradead.org wrote:

> On Wed, Apr 10, 2019 at 11:47:40AM -0400, Mathieu Desnoyers wrote:
>> ----- On Apr 10, 2019, at 2:54 AM, Peter Zijlstra peterz@infradead.org wrote:
>> 
>> > On Tue, Apr 09, 2019 at 04:43:42PM -0400, Mathieu Desnoyers wrote:
>> >> +/*
>> >> + * RSEQ_SIG is used with the following privileged instructions, which trap in
>> >> user-space:
>> >> + * x86-32:    0f 01 3d 53 30 05 53      invlpg 0x53053053
>> >> + * x86-64:    0f 01 3d 53 30 05 53      invlpg 0x53053053(%rip)
>> >> + */
>> > 
>> > Right, and the alternative is: 0f b9 3d $SIG, which decodes to:
>> > 
>> >  UD1 $SIG(%rip),%edi
>> > 
>> > which will trap unconditionally. The only problem is that gas will not
>> > actually assemble it, but since we're .byte coding it, it doesn't
>> > matter.
>> > 
>> > UD1 is specified by both AMD and Intel to take a ModR/M, unlike UD0
>> > where they disagree on the ModR/M.
>> 
>> UD1 is even better from a code emulator perspective. It won't have to
>> try to emulate invlpg if it sees it.
> 
> Some emulators terminate on UD2, not aware of any special UD1 behaviour.
> 
>> Byte coding UD1 as your example above gives the following objdump output,
>> is it expected ?
>> 
>> objdump --version
>> GNU objdump (GNU Binutils for Debian) 2.28
>> 
>> x86-32:
>> 
>>   14:	0f b9                	ud1
>>   16:	3d 53 30 05 53       	cmp    $0x53053053,%eax
>> 
>> x86-64:
>> 
>>    b:	0f b9                	ud1
>>    d:	3d 53 30 05 53       	cmp    $0x53053053,%eax
> 
> GNU objdump (GNU Binutils for Debian) 2.31.1
> 
>     0f b9 3d 78 56 34 12    ud1    0x12345678(%rip),%edi
> 
> So I suppose your objdump is too old :/

Well at least it decodes _something_ which matches the overall instruction
length of 7 bytes, which I think should be OK. So let's use ud1 unless anyone
objects.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com