Integer overflow during brace expansion

Integer overflow during brace expansion

[Leon Weber]

[-- Attachment #1: Type: text/plain, Size: 2018 bytes --]

Hi,

When parsing and expanding 'dotdot' type brace expressions (e.g. {1..3}),
zsh can encounter integer overflows because the range start and end
values are stored in two integers without proper bounds checking
(rstart and rend in glob.c:2092). Particularly,
this happens when one of the range boundaries is <=-2147483648
or >=2147483648, like in this example:

> zsh% echo {-2147483648..-2147483646}

This will cause zsh to eat up 100% CPU iterating through the loop declared
in line 2147 in glob.c. In that loop, rend is decreased until it underflows.
In the third and fourth iterations, we have these conditions:

//
// third iteration
//
> Breakpoint 15, xpandbraces (list=0x7ffff7fee340, np=0x7fffffffd460) at glob.c:2149
> 2149 p = dupstring(str3);
> (gdb) p rend
> $56 = -2147483648
> (gdb) p rstart
> $57 = -2147483648
> (gdb) cont
> Continuing.

//
// fourth iteration
//
> Breakpoint 15, xpandbraces (list=0x7ffff7fee340, np=0x7fffffffd460) at glob.c:2149
> 2149 p = dupstring(str3);
> (gdb) p rend
> $58 = 2147483647
> (gdb) p rstart
> $59 = -2147483648

This gdb output clearly shows that rend has underflown and is now at the
far positive end of the valid integer values. zsh will keep iterating
over that loop and decreasing rend for a really long time.

For comparison, a bash shell handles this correctly:

> bash$ echo {-2147483648..-2147483646}
> -2147483648 -2147483647 -2147483646

I have been able reproduce this issue on Ubuntu x86_64 and x86 using zsh 4.3.10,
4.3.11, and git revision db7d0ac34143ed2378c2fd98845b2ae5eaaf6bbb.

All mentioned line numbers reference to git revision
db7d0ac34143ed2378c2fd98845b2ae5eaaf6bbb.

Regards,

    -- Leon.

PS: I already posted this on the sourceforge bug tracker before finding out that's
    not in use. Perhaps it would be good to note this details somewhere visible
    along with some hints on where to really report bugs, since the sf tracker
    is the first google hit on 'zsh bugs' and this mailing list doesn't show up
    anywhere near that.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 198 bytes --]

Re: Integer overflow during brace expansion

[Mikael Magnusson]

On 27 February 2012 17:22, Leon Weber <leon@leonweber.de> wrote:
> Hi,
>
> When parsing and expanding 'dotdot' type brace expressions (e.g. {1..3}),
> zsh can encounter integer overflows because the range start and end
> values are stored in two integers without proper bounds checking
> (rstart and rend in glob.c:2092). Particularly,
> this happens when one of the range boundaries is <=-2147483648
> or >=2147483648, like in this example:
>
>> zsh% echo {-2147483648..-2147483646}
>
> This will cause zsh to eat up 100% CPU iterating through the loop declared
> in line 2147 in glob.c. In that loop, rend is decreased until it underflows.
> In the third and fourth iterations, we have these conditions:
[snippysnip]
> This gdb output clearly shows that rend has underflown and is now at the
> far positive end of the valid integer values. zsh will keep iterating
> over that loop and decreasing rend for a really long time.
>
> For comparison, a bash shell handles this correctly:
>
>> bash$ echo {-2147483648..-2147483646}
>> -2147483648 -2147483647 -2147483646

$ echo {-2147483648..2147483646}
zsh: segmentation fault  bash
and if you do this
$ echo {0..214783646}^C
it doesn't free the allocated memory until you exit the shell :).

(Of course, just for comparison. In zsh you can't even abort the
process with ctrl-c ;).)

The fix is fairly simple, just change the types involved to zlong. A
problem is that sprintf is used to convert the generated numbers back
to a string, and zlong can be an int or a long, but I forgot if we
have a modifier macro that expands to the correct thing. I remember
asking about it before (and possibly saying I would look in to fixing
it), but at the moment I don't remember what the result was.

With hardcoding it to %ld though, we get
% echo {-121474853646..-121474853650..2}
{-121474853660..-121474853646..3}
-121474853646 -121474853648 -121474853650 -121474853660 -121474853657
-121474853654 -121474853651 -121474853648

-- 
Mikael Magnusson

Re: Integer overflow during brace expansion

[Mikael Magnusson]

On 27 February 2012 17:52, Mikael Magnusson <mikachu@gmail.com> wrote:
> On 27 February 2012 17:22, Leon Weber <leon@leonweber.de> wrote:
>> Hi,
>>
>> When parsing and expanding 'dotdot' type brace expressions (e.g. {1..3}),
>> zsh can encounter integer overflows because the range start and end
>> values are stored in two integers without proper bounds checking
>> (rstart and rend in glob.c:2092). Particularly,
>> this happens when one of the range boundaries is <=-2147483648
>> or >=2147483648, like in this example:
>>
>>> zsh% echo {-2147483648..-2147483646}
>>
>> This will cause zsh to eat up 100% CPU iterating through the loop declared
>> in line 2147 in glob.c. In that loop, rend is decreased until it underflows.
>> In the third and fourth iterations, we have these conditions:
> [snippysnip]
>> This gdb output clearly shows that rend has underflown and is now at the
>> far positive end of the valid integer values. zsh will keep iterating
>> over that loop and decreasing rend for a really long time.
>>
>> For comparison, a bash shell handles this correctly:
>>
>>> bash$ echo {-2147483648..-2147483646}
>>> -2147483648 -2147483647 -2147483646
>
> $ echo {-2147483648..2147483646}
> zsh: segmentation fault  bash
> and if you do this
> $ echo {0..214783646}^C
> it doesn't free the allocated memory until you exit the shell :).
>
> (Of course, just for comparison. In zsh you can't even abort the
> process with ctrl-c ;).)
>
> The fix is fairly simple, just change the types involved to zlong. A
> problem is that sprintf is used to convert the generated numbers back
> to a string, and zlong can be an int or a long, but I forgot if we
> have a modifier macro that expands to the correct thing. I remember
> asking about it before (and possibly saying I would look in to fixing
> it), but at the moment I don't remember what the result was.
>
> With hardcoding it to %ld though, we get
ie, this:

diff --git i/Src/glob.c w/Src/glob.c
index 8f8127c..78b197c 100644
--- i/Src/glob.c
+++ w/Src/glob.c
@@ -2089,7 +2089,8 @@ xpandbraces(LinkList list, LinkNode *np)
 	char *dots, *p, *dots2 = NULL;
 	LinkNode olast = last;
 	/* Get the first number of the range */
-	int rstart = zstrtol(str+1,&dots,10), rend = 0, err = 0, rev = 0, rincr = 1;
+	zlong rstart = zstrtol(str+1,&dots,10), rend = 0;
+	int err = 0, rev = 0, rincr = 1;
 	int wid1 = (dots - str) - 1, wid2 = (str2 - dots) - 2, wid3 = 0;
 	int strp = str - str3;

@@ -2134,7 +2135,7 @@ xpandbraces(LinkList list, LinkNode *np)
 	    }
 	    if (rstart > rend) {
 		/* Handle decreasing ranges correctly. */
-		int rt = rend;
+		zlong rt = rend;
 		rend = rstart;
 		rstart = rt;
 		rev = !rev;
@@ -2147,7 +2148,7 @@ xpandbraces(LinkList list, LinkNode *np)
 	    for (; rend >= rstart; rend -= rincr) {
 		/* Node added in at end, so do highest first */
 		p = dupstring(str3);
-		sprintf(p + strp, "%0*d", minw, rend);
+		sprintf(p + strp, "%0*ld", minw, rend);
 		strcat(p + strp, str2 + 1);
 		insertlinknode(list, last, p);
 		if (rev)	/* decreasing:  add in reverse order. */

Re: Integer overflow during brace expansion

[Mikael Magnusson]

On 27 February 2012 17:54, Mikael Magnusson <mikachu@gmail.com> wrote:
>>
>> The fix is fairly simple, just change the types involved to zlong. A
>> problem is that sprintf is used to convert the generated numbers back
>> to a string, and zlong can be an int or a long, but I forgot if we
>> have a modifier macro that expands to the correct thing. I remember
>> asking about it before (and possibly saying I would look in to fixing
>> it), but at the moment I don't remember what the result was.

I found the old thread now, pws suggested just using %ld and casting
the value to long, to which I replied something incomprehensibly
stupid, "but %d won't work if I cast to long". If nobody sees a
problem with the above patch, I can commit it with this change.

-               sprintf(p + strp, "%0*ld", minw, rend);
+               sprintf(p + strp, "%0*ld", minw, (long)rend);

-- 
Mikael Magnusson

Re: Integer overflow during brace expansion

[Peter Stephenson]

On Mon, 27 Feb 2012 18:01:23 +0100
Mikael Magnusson <mikachu@gmail.com> wrote:
> I found the old thread now, pws suggested just using %ld and casting
> the value to long, to which I replied something incomprehensibly
> stupid, "but %d won't work if I cast to long". If nobody sees a
> problem with the above patch, I can commit it with this change.
> 
> -               sprintf(p + strp, "%0*ld", minw, rend);
> +               sprintf(p + strp, "%0*ld", minw, (long)rend);

I think that sounds OK for now.  It would be quite nice to ensure we
could output the full range one day, which isn't *that* difficult.
However, that's a different problem.

Leon Weber <leon@leonweber.de> wrote:
> PS: I already posted this on the sourceforge bug tracker before finding
> out that's not in use. Perhaps it would be good to note this details
> somewhere visible along with some hints on where to really report bugs,
> since the sf tracker is the first google hit on 'zsh bugs' and this
> mailing list doesn't show up anywhere near that.

It's fine to have a record there, the problem is it doesn't actually
notify anyone as currently configured; I'm pretty sure it used to, so
this may be due to upgrades at Sourceforge.  I've told it to report new
entries to zsh-workers@zsh.org.  If nobody minds, I could get it to
report all changes to the list, which would be even safer.

-- 
Peter Stephenson <pws@csr.com>            Software Engineer
Tel: +44 (0)1223 692070                   Cambridge Silicon Radio Limited
Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, UK


Member of the CSR plc group of companies. CSR plc registered in England and Wales, registered number 4187346, registered office Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, United Kingdom
More information can be found at www.csr.com. Follow CSR on Twitter at http://twitter.com/CSR_PLC and read our blog at www.csr.com/blog

Re: Integer overflow during brace expansion

[Peter Stephenson]

On Mon, 27 Feb 2012 17:35:23 +0000
Peter Stephenson <Peter.Stephenson@csr.com> wrote:
> On Mon, 27 Feb 2012 18:01:23 +0100
> Mikael Magnusson <mikachu@gmail.com> wrote:
> > I found the old thread now, pws suggested just using %ld and casting
> > the value to long, to which I replied something incomprehensibly
> > stupid, "but %d won't work if I cast to long". If nobody sees a
> > problem with the above patch, I can commit it with this change.
> > 
> > -               sprintf(p + strp, "%0*ld", minw, rend);
> > +               sprintf(p + strp, "%0*ld", minw, (long)rend);
> 
> I think that sounds OK for now.  It would be quite nice to ensure we
> could output the full range one day, which isn't *that* difficult.

Here's the simple case: zlong is long long, rather than something more
baroque (obviously long is unproblematic), and this is supported by the
libraries.

I'm not sure how much work is really worth it.  The more baroque cases,
like quad_t, are probably out of fashion enough to be untestable, unless
anyone knows otherwise, and I would think most systems that provide long
long also provide %lld.  The problems disappear on native 64-bit
systems (we don't use long long unless long is 32-bit and long long is
64-bit).

Index: configure.ac
===================================================================
RCS file: /cvsroot/zsh/zsh/configure.ac,v
retrieving revision 1.137
diff -p -u -r1.137 configure.ac
--- configure.ac	10 Aug 2011 11:31:18 -0000	1.137
+++ configure.ac	1 Mar 2012 14:04:13 -0000
@@ -1010,6 +1010,37 @@ main() { return sizeof(ino_t) < 8; }
     fi
   fi
 fi
+AH_TEMPLATE([ZLONG_IS_LONG_LONG],
+[Define to 1 if the zlong type uses long long int.])
+if test "$zsh_cv_64_bit_type" = "long long"; then
+  dnl Remember this so we can get (s)printf output right.
+  AC_DEFINE(ZLONG_IS_LONG_LONG)
+fi
+
+dnl We'll blithely assume print supports the same types as sprintf.
+AC_CACHE_CHECK(for %lld printf support, zsh_cv_printf_has_lld,
+[AC_TRY_RUN(
+[#include <stdio.h>
+#include <string.h>
+int main(int argc, char **argv)
+{
+   long long foo = (long long)400;
+   char buf[20];
+   sprintf(buf, "before%lldafter", foo);
+   if (!strcmp(buf, "before400after")) {
+      return 0;
+   }
+   return 1;
+}
+],
+zsh_cv_printf_has_lld=yes,
+zsh_cv_printf_has_lld=no,
+zsh_cv_printf_has_lld=no)])
+AH_TEMPLATE(PRINTF_HAS_LLD,
+[Define to 1 if printf and sprintf support %ldd for long long.])
+if test x$zsh_cv_printf_has_lld = xyes; then
+  AC_DEFINE(PRINTF_HAS_LLD)
+fi
 
 dnl Check for sigset_t.  Currently I'm looking in
 dnl <sys/types.h> and <signal.h>.  Others might need
Index: Src/exec.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/exec.c,v
retrieving revision 1.209
diff -p -u -r1.209 exec.c
--- Src/exec.c	1 Mar 2012 03:33:18 -0000	1.209
+++ Src/exec.c	1 Mar 2012 14:04:13 -0000
@@ -3252,7 +3252,11 @@ execcmd(Estate state, int input, int out
 	    }
 	    if (isset(PRINTEXITVALUE) && isset(SHINSTDIN) &&
 		lastval && !subsh) {
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		fprintf(stderr, "zsh: exit %lld\n", lastval);
+#else
 		fprintf(stderr, "zsh: exit %ld\n", (long)lastval);
+#endif
 		fflush(stderr);
 	    }
 
Index: Src/glob.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/glob.c,v
retrieving revision 1.81
diff -p -u -r1.81 glob.c
--- Src/glob.c	29 Feb 2012 17:06:07 -0000	1.81
+++ Src/glob.c	1 Mar 2012 14:04:14 -0000
@@ -2148,7 +2148,11 @@ xpandbraces(LinkList list, LinkNode *np)
 	    for (; rend >= rstart; rend -= rincr) {
 		/* Node added in at end, so do highest first */
 		p = dupstring(str3);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		sprintf(p + strp, "%0*lld", minw, rend);
+#else
 		sprintf(p + strp, "%0*ld", minw, (long)rend);
+#endif
 		strcat(p + strp, str2 + 1);
 		insertlinknode(list, last, p);
 		if (rev)	/* decreasing:  add in reverse order. */
Index: Src/prompt.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/prompt.c,v
retrieving revision 1.62
diff -p -u -r1.62 prompt.c
--- Src/prompt.c	9 May 2011 09:49:09 -0000	1.62
+++ Src/prompt.c	1 Mar 2012 14:04:14 -0000
@@ -663,12 +663,20 @@ putpromptchar(int doprint, int endchar, 
 		break;
 	    case 'L':
 		addbufspc(DIGBUFSIZE);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		sprintf(bv->bp, "%lld", shlvl);
+#else
 		sprintf(bv->bp, "%ld", (long)shlvl);
+#endif
 		bv->bp += strlen(bv->bp);
 		break;
 	    case '?':
 		addbufspc(DIGBUFSIZE);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		sprintf(bv->bp, "%lld", lastval);
+#else
 		sprintf(bv->bp, "%ld", (long)lastval);
+#endif
 		bv->bp += strlen(bv->bp);
 		break;
 	    case '%':
@@ -764,7 +772,11 @@ putpromptchar(int doprint, int endchar, 
 		    if (funcstack->tp == FS_EVAL)
 			lineno--;
 		    addbufspc(DIGBUFSIZE);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		    sprintf(bv->bp, "%lld", flineno);
+#else
 		    sprintf(bv->bp, "%ld", (long)flineno);
+#endif
 		    bv->bp += strlen(bv->bp);
 		    break;
 		}
@@ -772,7 +784,11 @@ putpromptchar(int doprint, int endchar, 
 		/* FALLTHROUGH */
 	    case 'i':
 		addbufspc(DIGBUFSIZE);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+		sprintf(bv->bp, "%lld", lineno);
+#else
 		sprintf(bv->bp, "%ld", (long)lineno);
+#endif
 		bv->bp += strlen(bv->bp);
 		break;
 	    case 'x':
Index: Src/utils.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/utils.c,v
retrieving revision 1.265
diff -p -u -r1.265 utils.c
--- Src/utils.c	3 Dec 2011 23:15:38 -0000	1.265
+++ Src/utils.c	1 Mar 2012 14:04:14 -0000
@@ -275,9 +275,13 @@ zerrmsg(FILE *file, const char *fmt, va_
 #endif
     char *errmsg;
 
-    if ((unset(SHINSTDIN) || locallevel) && lineno)
+    if ((unset(SHINSTDIN) || locallevel) && lineno) {
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+	fprintf(file, "%lld: ", lineno);
+#else
 	fprintf(file, "%ld: ", (long)lineno);
-    else
+#endif
+    } else
 	fputc((unsigned char)' ', file);
 
     while (*fmt)
Index: Src/Modules/parameter.c
===================================================================
RCS file: /cvsroot/zsh/zsh/Src/Modules/parameter.c,v
retrieving revision 1.53
diff -p -u -r1.53 parameter.c
--- Src/Modules/parameter.c	19 Jan 2011 12:42:53 -0000	1.53
+++ Src/Modules/parameter.c	1 Mar 2012 14:04:14 -0000
@@ -531,7 +531,11 @@ functracegetfn(UNUSED(Param pm))
 	char *colonpair;
 
 	colonpair = zhalloc(strlen(f->caller) + (f->lineno > 9999 ? 24 : 6));
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+	sprintf(colonpair, "%s:%lld", f->caller, f->lineno);
+#else
 	sprintf(colonpair, "%s:%ld", f->caller, (long)f->lineno);
+#endif
 
 	*p = colonpair;
     }
@@ -559,7 +563,11 @@ funcsourcetracegetfn(UNUSED(Param pm))
 	char *fname = f->filename ? f->filename : "";
 
 	colonpair = zhalloc(strlen(fname) + (f->flineno > 9999 ? 24 : 6));
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+	sprintf(colonpair, "%s:%lld", fname, f->flineno);
+#else
 	sprintf(colonpair, "%s:%ld", fname, (long)f->flineno);
+#endif
 
 	*p = colonpair;
     }
@@ -594,7 +602,11 @@ funcfiletracegetfn(UNUSED(Param pm))
 	     */
 	    colonpair = zhalloc(strlen(f->caller) +
 				(f->lineno > 9999 ? 24 : 6));
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+	    sprintf(colonpair, "%s:%lld", f->caller, f->lineno);
+#else
 	    sprintf(colonpair, "%s:%ld", f->caller, (long)f->lineno);
+#endif
 	} else {
 	    /*
 	     * Calling context is a function or eval; we need to find
@@ -604,7 +616,7 @@ funcfiletracegetfn(UNUSED(Param pm))
 	     * together with the $functrace line number for the current
 	     * context.
 	     */
-	    long flineno = (long)(f->prev->flineno + f->lineno);
+	    zlong flineno = f->prev->flineno + f->lineno;
 	    /*
 	     * Line numbers in eval start from 1, not zero,
 	     * so offset by one to get line in file.
@@ -614,7 +626,11 @@ funcfiletracegetfn(UNUSED(Param pm))
 	    fname = f->prev->filename ? f->prev->filename : "";
 
 	    colonpair = zhalloc(strlen(fname) + (flineno > 9999 ? 24 : 6));
-	    sprintf(colonpair, "%s:%ld", fname, flineno);
+#if defined(ZLONG_IS_LONG_LONG) && defined(PRINTF_HAS_LLD)
+	    sprintf(colonpair, "%s:%lld", fname, flineno);
+#else
+	    sprintf(colonpair, "%s:%ld", fname, (long)flineno);
+#endif
 	}
 
 	*p = colonpair;

-- 
Peter Stephenson <pws@csr.com>            Software Engineer
Tel: +44 (0)1223 692070                   Cambridge Silicon Radio Limited
Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, UK


Member of the CSR plc group of companies. CSR plc registered in England and Wales, registered number 4187346, registered office Churchill House, Cambridge Business Park, Cowley Road, Cambridge, CB4 0WZ, United Kingdom
More information can be found at www.csr.com. Follow CSR on Twitter at http://twitter.com/CSR_PLC and read our blog at www.csr.com/blog

Re: Integer overflow during brace expansion

[Wayne Davison]

[-- Attachment #1: Type: text/plain, Size: 467 bytes --]

On Thu, Mar 1, 2012 at 6:30 AM, Peter Stephenson
<Peter.Stephenson@csr.com>wrote:

> +   long long foo = (long long)400;
> +   char buf[20];
> +   sprintf(buf, "before%lldafter", foo);
> +   if (!strcmp(buf, "before400after")) {
>

I think it'd be nice to get some higher bits involved in that check.
 Perhaps something like this:

    long long foo = ((long long)0xdead << 40) | 0xf00d;

compares to before62677660341432333after (and needs a larger buf).

..wayne..