string.unpack segfaulting due to integer overflow and mixed sign comparisons

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

string.unpack segfaulting due to integer overflow and mixed sign comparisons

Sam Roberts
lpack for 5.1 from:

http://www.tecgraf.puc-rio.br/~lhf/ftp/lua/#lpack

testcase:

string.unpack("", "A"..0xffffffff, 2)

On linux i386 with 32-bit int and size_t.

Generally, the lack of checking for invalid args, like negative string
positions, makes me nervous. In particular,

lua -l pack -e 'print(string.unpack("", "b", -100))'

because int i = -100; size_t len = 0; if(i+1 > len) evaluates to
true... the -99 gets promoted to a very large size_t, so ends up being
larger than most string lengths.

Also, while (isdigit(*f)) N=10*N+(*f++)-'0'; will wrap N for large
enough repeat counts, though this should just result in confusion if
it wraps back into the 0 < N < len range, not segfaults.


fix:

Index: pack/lpack.c
===================================================================
--- pack/lpack.c        (revision 27854)
+++ pack/lpack.c        (working copy)
@@ -129,7 +129,7 @@
    case OP_STRING:
    {
     ++N;
-    if (i+N>len) goto done;
+    if (i+N < i || i+N>len) goto done;
     lua_pushlstring(L,s+i,N);
     i+=N;
     ++n;

Reply | Threaded
Open this post in threaded view
|

Re: string.unpack segfaulting due to integer overflow and mixed sign comparisons

Chris Emerson
Hi,

On Tue, Jun 26, 2012 at 03:51:43PM -0700, Sam Roberts wrote:

> Also, while (isdigit(*f)) N=10*N+(*f++)-'0'; will wrap N for large
> enough repeat counts, though this should just result in confusion if
> it wraps back into the 0 < N < len range, not segfaults.
>
> fix:
>
> Index: pack/lpack.c
> ===================================================================
> --- pack/lpack.c        (revision 27854)
> +++ pack/lpack.c        (working copy)
> @@ -129,7 +129,7 @@
>     case OP_STRING:
>     {
>      ++N;
> -    if (i+N>len) goto done;
> +    if (i+N < i || i+N>len) goto done;

I don't think this is right - in C overflow of signed integers is undefined
behaviour.  The C compiler can (and some now do) assume that "i+N < i"
(with N positive) can't happen, and that test can be optimised out.

I haven't looked at it in enough detail to provide the right fix, sorry.
:-)

Regards,

Chris

Reply | Threaded
Open this post in threaded view
|

Re: string.unpack segfaulting due to integer overflow and mixed sign comparisons

Joshua Phillips
On Wed, Jun 27, 2012 at 09:14:23AM +0100, Chris Emerson wrote:

> On Tue, Jun 26, 2012 at 03:51:43PM -0700, Sam Roberts wrote:
> > Index: pack/lpack.c
> > ===================================================================
> > --- pack/lpack.c        (revision 27854)
> > +++ pack/lpack.c        (working copy)
> > @@ -129,7 +129,7 @@
> >     case OP_STRING:
> >     {
> >      ++N;
> > -    if (i+N>len) goto done;
> > +    if (i+N < i || i+N>len) goto done;
>
> I don't think this is right - in C overflow of signed integers is undefined
> behaviour.  The C compiler can (and some now do) assume that "i+N < i"
> (with N positive) can't happen, and that test can be optimised out.
>
> I haven't looked at it in enough detail to provide the right fix, sorry.
> :-)

You're right, you can't do the check after the overflow, because the
overflow itself is undefined behaviour.
This document goes into more detail (and shows how hard it is to use C
safely!): http://www.fefe.de/intof.html

Reply | Threaded
Open this post in threaded view
|

Re: string.unpack segfaulting due to integer overflow and mixed sign comparisons

William Ahern
On Wed, Jun 27, 2012 at 12:42:16PM +0100, Joshua Phillips wrote:

> On Wed, Jun 27, 2012 at 09:14:23AM +0100, Chris Emerson wrote:
> > On Tue, Jun 26, 2012 at 03:51:43PM -0700, Sam Roberts wrote:
> > > Index: pack/lpack.c
> > > ===================================================================
> > > --- pack/lpack.c        (revision 27854)
> > > +++ pack/lpack.c        (working copy)
> > > @@ -129,7 +129,7 @@
> > >     case OP_STRING:
> > >     {
> > >      ++N;
> > > -    if (i+N>len) goto done;
> > > +    if (i+N < i || i+N>len) goto done;
> >
> > I don't think this is right - in C overflow of signed integers is undefined
> > behaviour.  The C compiler can (and some now do) assume that "i+N < i"
> > (with N positive) can't happen, and that test can be optimised out.
> >
> > I haven't looked at it in enough detail to provide the right fix, sorry.
> > :-)
>
> You're right, you can't do the check after the overflow, because the
> overflow itself is undefined behaviour.
> This document goes into more detail (and shows how hard it is to use C
> safely!): http://www.fefe.de/intof.html

It's not just C, it's any language with fixed-width value representations.
C, however, is far less lenient with the consequences. Or rather, the
consequences are quicker. (Most such bugs in Java, Perl, Lua, etc still
linger around; they're just rarely triggered.)

But that's a bonus. When you know--as you should--that there's an ax hanging
over your head, you tend to be a little more cautious.

Reply | Threaded
Open this post in threaded view
|

Re: string.unpack segfaulting due to integer overflow and mixed sign comparisons

Sam Roberts
In reply to this post by Chris Emerson
On Wed, Jun 27, 2012 at 1:14 AM, Chris Emerson
<[hidden email]> wrote:
>> -    if (i+N>len) goto done;
>> +    if (i+N < i || i+N>len) goto done;
>
> I don't think this is right - in C overflow of signed integers is undefined
> behaviour.  The C compiler can (and some now do) assume that "i+N < i"
> (with N positive) can't happen, and that test can be optimised out.

Interesting, is this true for unsigned, too?

I hope that modular addition is well-defined over uint32_t, I use it a
bunch, and haven't had any problems, yet, but maybe haven't hit the
"right" kind of optomizing compiler.

Anyhow, signed overflow is possible in other place in struct, such as
it's atoi() variant, that does no bounds checking.

I'd another patch that converted all the int values that are never
allowed to be negative to size_t, but it was a lot more intrusive, and
it wasn't clear, given how struct handles indexes that are out of
bounds, how to maintain a backwards compatible API.

Probably lua should have a luaL_checkunsigned().

Cheers,
Sam

Reply | Threaded
Open this post in threaded view
|

Re: string.unpack segfaulting due to integer overflow and mixed sign comparisons

William Ahern
On Wed, Jun 27, 2012 at 05:37:19PM -0700, Sam Roberts wrote:

> On Wed, Jun 27, 2012 at 1:14 AM, Chris Emerson
> <[hidden email]> wrote:
> >> -    if (i+N>len) goto done;
> >> +    if (i+N < i || i+N>len) goto done;
> >
> > I don't think this is right - in C overflow of signed integers is undefined
> > behaviour.  The C compiler can (and some now do) assume that "i+N < i"
> > (with N positive) can't happen, and that test can be optimised out.
>
> Interesting, is this true for unsigned, too?
>
> I hope that modular addition is well-defined over uint32_t, I use it a
> bunch, and haven't had any problems, yet, but maybe haven't hit the
> "right" kind of optomizing compiler.

Unsigned arithmetic is well-defined on overflow (or rather, unsigned types
cannot overflow at all because unsigned arithmetic is specifically defined
as modulo 2^N). I seem to remember someone on comp.lang.c or comp.std.c who
recently claimed that he used a modern C compiler (albeit for legacy
hardware) which had to emulate modulo arithemtic in software. You could
disable compliant mode for considerable performance gains.

C99 added several guarantees about object and value bit representations for
unsigned integers generally, and the extended fixed-width types especially.
But I don't think there was any existing implementation at the time that
would have been penalized, so they went ahead and made the guarantee.

> Anyhow, signed overflow is possible in other place in struct, such as
> it's atoi() variant, that does no bounds checking.
>
> I'd another patch that converted all the int values that are never
> allowed to be negative to size_t, but it was a lot more intrusive, and
> it wasn't clear, given how struct handles indexes that are out of
> bounds, how to maintain a backwards compatible API.
>
> Probably lua should have a luaL_checkunsigned().
>

Lua 5.2 does have luaL_checkunsigned.