[Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[David Gibson]

It is quite common to have a MemoryRegion with size of INT64_MAX.
When processing alias regions in render_memory_region() it's quite
easy to find a case where it will construct a temporary AddrRange with
a non-zero start, and size still of INT64_MAX.  When means attempting
to compute the end of such a range as start + size will result in
signed integer overflow.

This integer overflow means that addrrange_intersects() can
incorrectly report regions as not intersecting when they do.  For
example consider the case of address ranges {0x10000000000,
0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second
is in fact included completely in the first.

This patch rearranges addrrange_intersects() to avoid the integer
overflow, correcting this behaviour.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 memory.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/memory.c b/memory.c
index 57f0fa4..101b67c 100644
--- a/memory.c
+++ b/memory.c
@@ -55,8 +55,8 @@ static AddrRange addrrange_shift(AddrRange range, int64_t delta)
 
 static bool addrrange_intersects(AddrRange r1, AddrRange r2)
 {
-    return (r1.start >= r2.start && r1.start < r2.start + r2.size)
-        || (r2.start >= r1.start && r2.start < r1.start + r1.size);
+    return (r1.start >= r2.start && (r1.start - r2.start) < r2.size)
+        || (r2.start >= r1.start && (r2.start - r1.start) < r1.size);
 }
 
 static AddrRange addrrange_intersection(AddrRange r1, AddrRange r2)
-- 
1.7.5.4

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Avi Kivity]

On 09/14/2011 10:02 AM, David Gibson wrote:
> It is quite common to have a MemoryRegion with size of INT64_MAX.
> When processing alias regions in render_memory_region() it's quite
> easy to find a case where it will construct a temporary AddrRange with
> a non-zero start, and size still of INT64_MAX.  When means attempting
> to compute the end of such a range as start + size will result in
> signed integer overflow.
>
> This integer overflow means that addrrange_intersects() can
> incorrectly report regions as not intersecting when they do.  For
> example consider the case of address ranges {0x10000000000,
> 0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second
> is in fact included completely in the first.

Good catch, thanks for digging this out.

> This patch rearranges addrrange_intersects() to avoid the integer
> overflow, correcting this behaviour.

I expect that the bad behaviour can still be triggered, for example by 
pointing aliases towards the end of very large regions.  Not that I 
expect this to occur in practice.

I think we should move towards using __int128 internally.  Is there any 
relevant host which does not support __int128?

Meanwhile, applied to memory/core, and will request a pull shortly.

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Avi Kivity]

On 09/14/2011 11:23 AM, Avi Kivity wrote:
>
> I think we should move towards using __int128 internally.  Is there 
> any relevant host which does not support __int128?

Crap, it's not even supported on i386.

-- 
error compiling committee.c: too many arguments to function

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[David Gibson]

On Wed, Sep 14, 2011 at 11:23:25AM +0300, Avi Kivity wrote:
> On 09/14/2011 10:02 AM, David Gibson wrote:
> >It is quite common to have a MemoryRegion with size of INT64_MAX.
> >When processing alias regions in render_memory_region() it's quite
> >easy to find a case where it will construct a temporary AddrRange with
> >a non-zero start, and size still of INT64_MAX.  When means attempting
> >to compute the end of such a range as start + size will result in
> >signed integer overflow.
> >
> >This integer overflow means that addrrange_intersects() can
> >incorrectly report regions as not intersecting when they do.  For
> >example consider the case of address ranges {0x10000000000,
> >0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second
> >is in fact included completely in the first.
> 
> Good catch, thanks for digging this out.
> 
> >This patch rearranges addrrange_intersects() to avoid the integer
> >overflow, correcting this behaviour.
> 
> I expect that the bad behaviour can still be triggered, for example
> by pointing aliases towards the end of very large regions.  Not that
> I expect this to occur in practice.

Well.. I'm pretty sure that particular case can no longer be
triggered.  But there may be other integer overflow bugs in this code,
though I didn't spot them at a glance.

> I think we should move towards using __int128 internally.  Is there
> any relevant host which does not support __int128?

Hrm, using a barely supported integer type I'd never previously heard
of seems sub-optimal.  With appropriate care it ought to be possible
to do all the necessary calculations correctly in 64 bits, even if we
need a few explicit "if (a + b) < a" tests in some places.


> Meanwhile, applied to memory/core, and will request a pull shortly.
> 

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[David Gibson]

On Thu, Sep 15, 2011 at 12:34:31PM +1000, David Gibson wrote:
> On Wed, Sep 14, 2011 at 11:23:25AM +0300, Avi Kivity wrote:
> > On 09/14/2011 10:02 AM, David Gibson wrote:
> > >It is quite common to have a MemoryRegion with size of INT64_MAX.
> > >When processing alias regions in render_memory_region() it's quite
> > >easy to find a case where it will construct a temporary AddrRange with
> > >a non-zero start, and size still of INT64_MAX.  When means attempting
> > >to compute the end of such a range as start + size will result in
> > >signed integer overflow.
> > >
> > >This integer overflow means that addrrange_intersects() can
> > >incorrectly report regions as not intersecting when they do.  For
> > >example consider the case of address ranges {0x10000000000,
> > >0x7fffffffffffffff} and {0x10010000000, 0x10000000} where the second
> > >is in fact included completely in the first.
> > 
> > Good catch, thanks for digging this out.
> > 
> > >This patch rearranges addrrange_intersects() to avoid the integer
> > >overflow, correcting this behaviour.
> > 
> > I expect that the bad behaviour can still be triggered, for example
> > by pointing aliases towards the end of very large regions.  Not that
> > I expect this to occur in practice.
> 
> Well.. I'm pretty sure that particular case can no longer be
> triggered.  But there may be other integer overflow bugs in this code,
> though I didn't spot them at a glance.

Actually, there definitely are.  addrrange_end() should probably be
redefined as the inclusive end, rather than the exclusive end, and
computed as:

	(start + size - 1) < start ? INT64_MAX : start + size - 1

Hrm, except that that doesn't handle zero size ranges.  And gets a bit
weird for INT64_MAX sized regions.

Hrm, yeah, these really should be changed to use unsigneds.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Avi Kivity]

On 09/15/2011 05:58 AM, David Gibson wrote:
> >  Well.. I'm pretty sure that particular case can no longer be
> >  triggered.  But there may be other integer overflow bugs in this code,
> >  though I didn't spot them at a glance.
>
> Actually, there definitely are.  addrrange_end() should probably be
> redefined as the inclusive end, rather than the exclusive end, and
> computed as:
>
> 	(start + size - 1)<  start ? INT64_MAX : start + size - 1
>
> Hrm, except that that doesn't handle zero size ranges.  And gets a bit
> weird for INT64_MAX sized regions.
>
> Hrm, yeah, these really should be changed to use unsigneds.
>

Unsigneds don't work because we sometimes subtract values and get into 
the negative area, due to aliases.

We're using values that are close to the end of the 63 or 64 bit range 
and playing with them.  Overflow is always close and we'll always be 
able to find a way to defeat the code (even if it doesn't occur in 
practice).  I'm tempted to declare that the memory API supports only 60 
bits of address space (and s/INT64_MAX/MEMORY_REGION_SIZE_MAX/), that 
gives us a few levels of wild offsetting before we get confused.

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[David Gibson]

On Thu, Sep 15, 2011 at 10:28:42AM +0300, Avi Kivity wrote:
> On 09/15/2011 05:58 AM, David Gibson wrote:
> >>  Well.. I'm pretty sure that particular case can no longer be
> >>  triggered.  But there may be other integer overflow bugs in this code,
> >>  though I didn't spot them at a glance.
> >
> >Actually, there definitely are.  addrrange_end() should probably be
> >redefined as the inclusive end, rather than the exclusive end, and
> >computed as:
> >
> >	(start + size - 1)<  start ? INT64_MAX : start + size - 1
> >
> >Hrm, except that that doesn't handle zero size ranges.  And gets a bit
> >weird for INT64_MAX sized regions.
> >
> >Hrm, yeah, these really should be changed to use unsigneds.
> >
> 
> Unsigneds don't work because we sometimes subtract values and get
> into the negative area, due to aliases.

I realise that, but I'm fairly confident the order of calculations can
be adjusted to cope with those cases, just as we can cope with the
overflow cases with care.

Remember that because unsigned overflow is defined, and we can use
that in some cases.


> We're using values that are close to the end of the 63 or 64 bit
> range and playing with them.  Overflow is always close and we'll
> always be able to find a way to defeat the code (even if it doesn't
> occur in practice).  I'm tempted to declare that the memory API
> supports only 60 bits of address space (and
> s/INT64_MAX/MEMORY_REGION_SIZE_MAX/), that gives us a few levels of
> wild offsetting before we get confused.

There is something to be said for that.  Although many systems have
theoretical 64-bit addressing, on powerpc at least, the biggest
actually implemented physical address bus I'm aware of is under 50
bits.

Of course, there could be some highly sparse intermediate bus
addressing schemes which screw that up.


-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Paolo Bonzini]

On 09/15/2011 04:34 AM, David Gibson wrote:
> explicit "if (a + b)<  a" tests in some places.

Please wrap these in a macro, since the addition has to be done in an 
unsigned type.  Otherwise overflow is undefined.

Paolo

Re: [Qemu-devel] [PATCH] Fix subtle integer overflow bug in memory API

[Avi Kivity]

On 09/15/2011 10:38 AM, Paolo Bonzini wrote:
> On 09/15/2011 04:34 AM, David Gibson wrote:
>> explicit "if (a + b)<  a" tests in some places.
>
> Please wrap these in a macro, since the addition has to be done in an 
> unsigned type.  Otherwise overflow is undefined.

It doesn't help if the overflow is defined but produces an incorrect result.

The fact is we need a 64+N bit datatype, where N is the nesting level of 
MemoryRegions (including aliases).  Each nesting level can overflow a 
bit.  Right now the only viable options seems to be #define 64 60, but 
I'll be happy to consider others.

-- 
I have a truly marvellous patch that fixes the bug which this
signature is too narrow to contain.