[PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

There have been two attempts to fix kdd build with gcc 8.1
(437e00fe and 2de2b10b), but building with gcc 8.1 32 bit non-debug
build still yields the same error as in 437e00fe.

Ian wrote about adversarial optimisation in [0], one of the key points
is that computing an out-of-bounds pointer is UB.

<quote>
1. Adversarial optimissation hazard:

   The compiler may reason as follows:
   It is not legal to compute an out-of-bounds pointer.
   Doing so is UB.
   Therefore  ((uint8_t *)&ctrl.c32) + offset
   (which is caclulated unconditionally)
   is within the stack object `ctrl'.
   Therefore offset <= sizeof(ctrl).

1a. The compiler can continue to reason:
   Suppose offset > sizeof(ctrl.c32) but offset + len <=
   sizeof(ctrl.c32).  Because len is limited to 32-bit
   that can only happen if offset is large enough to
   wrap when len is added.  But I know that offset <= 216.
   So this situation cannot exist.
   Therefore I can remove the check for offset and
   rely only on the check for offset + len.

1b. The compiler can continue to reason:
   So offset <= 216.  I can therefore check that
   offset <= sizeof(ctrl.c32) using an instruction sequence
   that only looks at the bottom byte of offset (which on
   some architectures might be faster).

1c. If sizeof(ctrl.c32) ever becomes the same as sizeof(ctrl),
   the compiler can remove both checks entirely.
</quote>

Eliminate that UB by using uintptr_t to avoid the compiler reaching
the conclusion that offset <= sizeof(ctrl).

0: <23252.34284.742794.562828@mariner.uk.xensource.com>

Signed-off-by: Wei Liu <wei.liu2@citrix.com>
---
I don't follow the "calculated unconditionally" bit. Isn't the
calculation only done in the else branch?

This patch does make gcc happy though.

Cc: Ian Jackson <ian.jackson@eu.citrix.com>
Cc: Tim Deegan <tim@xen.org>
Cc: Marek Marczykowski <marmarek@invisiblethingslab.com>
Cc: Jan Beulich <jbeulich@suse.com>
---
 tools/debugger/kdd/kdd.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/tools/debugger/kdd/kdd.c b/tools/debugger/kdd/kdd.c
index 5a019a0a0c..054506f7a7 100644
--- a/tools/debugger/kdd/kdd.c
+++ b/tools/debugger/kdd/kdd.c
@@ -695,7 +695,8 @@ static void kdd_handle_read_ctrl(kdd_state *s)
             KDD_LOG(s, "Request outside of known control space\n");
             len = 0;
         } else {
-            memcpy(buf, ((uint8_t *)&ctrl.c32) + offset, len);
+            uintptr_t ptr_int = (uintptr_t)&ctrl.c32 + offset;
+            memcpy(buf, (uint8_t *)ptr_int, len);
         }
     }
 
-- 
2.11.0


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Ian Jackson]

Wei Liu writes ("[PATCH RFC] tools/kdd: avoid adversarial optimisation hazard"):
> There have been two attempts to fix kdd build with gcc 8.1
> (437e00fe and 2de2b10b), but building with gcc 8.1 32 bit non-debug
> build still yields the same error as in 437e00fe.
> 
> Ian wrote about adversarial optimisation in [0], one of the key points
> is that computing an out-of-bounds pointer is UB.
...
> Eliminate that UB by using uintptr_t to avoid the compiler reaching
> the conclusion that offset <= sizeof(ctrl).

Since I wrote my complaint, the code has been rearranged so that it
does not call memcpy if the bounds check fails.  nAt, least what I
wrote earlier,

 |  Therefore  ((uint8_t *)&ctrl.c32) + offset
 |  (which is caclulated unconditionally)
 |  is within the stack object `ctrl'.   

is not true of current staging.

It's still very obscure becaause this test

        if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {

depends critically on the size of offset, etc.

Is it not still possible that this test could be fooled ?  Suppose
offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.

I think offset + len might wrap around.  len looks like it can be
at most 65536-L.  So the biggest offset produces:

  0xfffffd33 + (65536-L) > L

which I think can wrap round unless L > 717.

This kind of reasoning is awful.  The code should be rewritten so that
it is obvious that it won't go wrong.  Typically that means
calculating the maximum value of len from a checked value of offset.

  if ( .... || len > sizeof - offset )

Ian.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

On Thu, Jul 26, 2018 at 01:37:45PM +0100, Ian Jackson wrote:
> Wei Liu writes ("[PATCH RFC] tools/kdd: avoid adversarial optimisation hazard"):
> > There have been two attempts to fix kdd build with gcc 8.1
> > (437e00fe and 2de2b10b), but building with gcc 8.1 32 bit non-debug
> > build still yields the same error as in 437e00fe.
> > 
> > Ian wrote about adversarial optimisation in [0], one of the key points
> > is that computing an out-of-bounds pointer is UB.
> ...
> > Eliminate that UB by using uintptr_t to avoid the compiler reaching
> > the conclusion that offset <= sizeof(ctrl).
> 
> Since I wrote my complaint, the code has been rearranged so that it
> does not call memcpy if the bounds check fails.  nAt, least what I
> wrote earlier,
> 
>  |  Therefore  ((uint8_t *)&ctrl.c32) + offset
>  |  (which is caclulated unconditionally)
>  |  is within the stack object `ctrl'.   
> 
> is not true of current staging.

I don't think that was true when you wrote your complaint either. That's
why I got confused and wrote  "I don't follow the calculated
unconditionally bit" in this patch.

> 
> It's still very obscure becaause this test
> 
>         if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> 
> depends critically on the size of offset, etc.
> 
> Is it not still possible that this test could be fooled ?  Suppose
> offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.

I also had this question.

I suspect the address, from which offset is derived, is bounded. But I
haven't found the spec for KD.

> 
> I think offset + len might wrap around.  len looks like it can be
> at most 65536-L.  So the biggest offset produces:
> 
>   0xfffffd33 + (65536-L) > L
> 
> which I think can wrap round unless L > 717.
> 
> This kind of reasoning is awful.  The code should be rewritten so that
> it is obvious that it won't go wrong.  Typically that means
> calculating the maximum value of len from a checked value of offset.
> 

Yes, I think getting offset checked is rather helpful. I didn't do that
because I didn't know what range it was supposed to be in.

Wei.

>   if ( .... || len > sizeof - offset )
> 
> Ian.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Paul Durrant]

> -----Original Message-----
> From: Xen-devel [mailto:xen-devel-bounces@lists.xenproject.org] On Behalf
> Of Wei Liu
> Sent: 26 July 2018 13:54
> To: Ian Jackson <Ian.Jackson@citrix.com>
> Cc: Xen-devel <xen-devel@lists.xenproject.org>; Wei Liu
> <wei.liu2@citrix.com>; Marek Marczykowski
> <marmarek@invisiblethingslab.com>; Jan Beulich <jbeulich@suse.com>; Tim
> (Xen.org) <tim@xen.org>
> Subject: Re: [Xen-devel] [PATCH RFC] tools/kdd: avoid adversarial
> optimisation hazard
> 
> On Thu, Jul 26, 2018 at 01:37:45PM +0100, Ian Jackson wrote:
> > Wei Liu writes ("[PATCH RFC] tools/kdd: avoid adversarial optimisation
> hazard"):
> > > There have been two attempts to fix kdd build with gcc 8.1
> > > (437e00fe and 2de2b10b), but building with gcc 8.1 32 bit non-debug
> > > build still yields the same error as in 437e00fe.
> > >
> > > Ian wrote about adversarial optimisation in [0], one of the key points
> > > is that computing an out-of-bounds pointer is UB.
> > ...
> > > Eliminate that UB by using uintptr_t to avoid the compiler reaching
> > > the conclusion that offset <= sizeof(ctrl).
> >
> > Since I wrote my complaint, the code has been rearranged so that it
> > does not call memcpy if the bounds check fails.  nAt, least what I
> > wrote earlier,
> >
> >  |  Therefore  ((uint8_t *)&ctrl.c32) + offset
> >  |  (which is caclulated unconditionally)
> >  |  is within the stack object `ctrl'.
> >
> > is not true of current staging.
> 
> I don't think that was true when you wrote your complaint either. That's
> why I got confused and wrote  "I don't follow the calculated
> unconditionally bit" in this patch.
> 
> >
> > It's still very obscure becaause this test
> >
> >         if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> >
> > depends critically on the size of offset, etc.
> >
> > Is it not still possible that this test could be fooled ?  Suppose
> > offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.
> 
> I also had this question.
> 
> I suspect the address, from which offset is derived, is bounded. But I
> haven't found the spec for KD.

I don’t think there is one. AFAIK kdd was written using a lot reverse engineering of observed behaviour of WinDBG talking over an emulated serial line.

  Paul

> 
> >
> > I think offset + len might wrap around.  len looks like it can be
> > at most 65536-L.  So the biggest offset produces:
> >
> >   0xfffffd33 + (65536-L) > L
> >
> > which I think can wrap round unless L > 717.
> >
> > This kind of reasoning is awful.  The code should be rewritten so that
> > it is obvious that it won't go wrong.  Typically that means
> > calculating the maximum value of len from a checked value of offset.
> >
> 
> Yes, I think getting offset checked is rather helpful. I didn't do that
> because I didn't know what range it was supposed to be in.
> 
> Wei.
> 
> >   if ( .... || len > sizeof - offset )
> >
> > Ian.
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xenproject.org
> https://lists.xenproject.org/mailman/listinfo/xen-devel
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

On Thu, Jul 26, 2018 at 01:37:45PM +0100, Ian Jackson wrote:
> Wei Liu writes ("[PATCH RFC] tools/kdd: avoid adversarial optimisation hazard"):
> > There have been two attempts to fix kdd build with gcc 8.1
> > (437e00fe and 2de2b10b), but building with gcc 8.1 32 bit non-debug
> > build still yields the same error as in 437e00fe.
> > 
> > Ian wrote about adversarial optimisation in [0], one of the key points
> > is that computing an out-of-bounds pointer is UB.
> ...
> > Eliminate that UB by using uintptr_t to avoid the compiler reaching
> > the conclusion that offset <= sizeof(ctrl).
> 
> Since I wrote my complaint, the code has been rearranged so that it
> does not call memcpy if the bounds check fails.  nAt, least what I
> wrote earlier,
> 
>  |  Therefore  ((uint8_t *)&ctrl.c32) + offset
>  |  (which is caclulated unconditionally)
>  |  is within the stack object `ctrl'.   
> 
> is not true of current staging.
> 
> It's still very obscure becaause this test
> 
>         if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> 
> depends critically on the size of offset, etc.
> 
> Is it not still possible that this test could be fooled ?  Suppose
> offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.

In this case, wouldn't offset > sizeof ctrl.c32 becomes true?

Wei.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Tim Deegan]

Hi,

Apologies for the delay.  Several of my other hats were on fire.

> > I suspect the address, from which offset is derived, is bounded. But I
> > haven't found the spec for KD.
> 
> I don’t think there is one.

Indeed not.  The official way to extend windbg &c is to write a plugin
that runs on the Windows machine where you run the debugger.

At 13:37 +0100 on 26 Jul (1532612265), Ian Jackson wrote:
> It's still very obscure becaause this test
> 
>         if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> 
> depends critically on the size of offset, etc.
> 
> Is it not still possible that this test could be fooled ?  Suppose
> offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.

This is > sizeof ctrl.c32.  But:

> This kind of reasoning is awful.  The code should be rewritten so that
> it is obvious that it won't go wrong.

Yes.  How about this (compile tested only, and I haven't checked the buggy
gcc versions):

diff --git a/tools/debugger/kdd/kdd.c b/tools/debugger/kdd/kdd.c
index 5a019a0a0c..64aacde1ee 100644
--- a/tools/debugger/kdd/kdd.c
+++ b/tools/debugger/kdd/kdd.c
@@ -687,11 +687,11 @@ static void kdd_handle_read_ctrl(kdd_state *s)
         }
     } else {
         /* 32-bit control-register space starts at 0x[2]cc, for 84 bytes */
-        uint32_t offset = addr;
-        if (offset > 0x200)
-            offset -= 0x200;
-        offset -= 0xcc;
-        if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
+        uint32_t offset = addr - 0xcc;
+        if (offset > sizeof ctrl.c32)
+            offset = addr - 0x2cc;
+        if (offset > sizeof ctrl.c32
+            || len > sizeof ctrl.c32 - offset) {
             KDD_LOG(s, "Request outside of known control space\n");
             len = 0;
         } else {


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

On Fri, Aug 03, 2018 at 10:54:19AM +0100, Tim Deegan wrote:
> Hi,
> 
> Apologies for the delay.  Several of my other hats were on fire.
> 
> > > I suspect the address, from which offset is derived, is bounded. But I
> > > haven't found the spec for KD.
> > 
> > I don’t think there is one.
> 
> Indeed not.  The official way to extend windbg &c is to write a plugin
> that runs on the Windows machine where you run the debugger.
> 
> At 13:37 +0100 on 26 Jul (1532612265), Ian Jackson wrote:
> > It's still very obscure becaause this test
> > 
> >         if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> > 
> > depends critically on the size of offset, etc.
> > 
> > Is it not still possible that this test could be fooled ?  Suppose
> > offset is 0xffffffff.  Then before the test, offset is 0xfffffd33.
> 
> This is > sizeof ctrl.c32.  But:
> 
> > This kind of reasoning is awful.  The code should be rewritten so that
> > it is obvious that it won't go wrong.
> 
> Yes.  How about this (compile tested only, and I haven't checked the buggy
> gcc versions):

Yes the following diff works with the buggy compiler.

> 
> diff --git a/tools/debugger/kdd/kdd.c b/tools/debugger/kdd/kdd.c
> index 5a019a0a0c..64aacde1ee 100644
> --- a/tools/debugger/kdd/kdd.c
> +++ b/tools/debugger/kdd/kdd.c
> @@ -687,11 +687,11 @@ static void kdd_handle_read_ctrl(kdd_state *s)
>          }
>      } else {
>          /* 32-bit control-register space starts at 0x[2]cc, for 84 bytes */
> -        uint32_t offset = addr;
> -        if (offset > 0x200)
> -            offset -= 0x200;
> -        offset -= 0xcc;
> -        if (offset > sizeof ctrl.c32 || offset + len > sizeof ctrl.c32) {
> +        uint32_t offset = addr - 0xcc;
> +        if (offset > sizeof ctrl.c32)
> +            offset = addr - 0x2cc;
> +        if (offset > sizeof ctrl.c32
> +            || len > sizeof ctrl.c32 - offset) {
>              KDD_LOG(s, "Request outside of known control space\n");
>              len = 0;
>          } else {
> 

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

One interesting observation is that if I revert 2de2b10b225 which turns
the type of offset from uint32_t back to uint64_t, kdd.c will build with
32 bit, but then of course 64 bit build is broken. :-/

Wei.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel

Re: [PATCH RFC] tools/kdd: avoid adversarial optimisation hazard

[Wei Liu]

After some back and forth discussion on gcc-help, it is suggested this
is a bug in gcc and I'm asked to open a bug report.

Here is the bug report for reference:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=86827

Wei.

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xenproject.org
https://lists.xenproject.org/mailman/listinfo/xen-devel