* Integer overflow during brace expansion
@ 2012-02-27 16:22 Leon Weber
2012-02-27 16:52 ` Mikael Magnusson
0 siblings, 1 reply; 7+ messages in thread
From: Leon Weber @ 2012-02-27 16:22 UTC (permalink / raw)
To: zsh-workers
[-- 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 --]
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: Integer overflow during brace expansion 2012-02-27 16:22 Integer overflow during brace expansion Leon Weber @ 2012-02-27 16:52 ` Mikael Magnusson 2012-02-27 16:54 ` Mikael Magnusson 0 siblings, 1 reply; 7+ messages in thread From: Mikael Magnusson @ 2012-02-27 16:52 UTC (permalink / raw) To: Leon Weber; +Cc: zsh-workers 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Integer overflow during brace expansion 2012-02-27 16:52 ` Mikael Magnusson @ 2012-02-27 16:54 ` Mikael Magnusson 2012-02-27 17:01 ` Mikael Magnusson 0 siblings, 1 reply; 7+ messages in thread From: Mikael Magnusson @ 2012-02-27 16:54 UTC (permalink / raw) To: Leon Weber; +Cc: zsh-workers 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. */ ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Integer overflow during brace expansion 2012-02-27 16:54 ` Mikael Magnusson @ 2012-02-27 17:01 ` Mikael Magnusson 2012-02-27 17:35 ` Peter Stephenson 0 siblings, 1 reply; 7+ messages in thread From: Mikael Magnusson @ 2012-02-27 17:01 UTC (permalink / raw) To: Leon Weber; +Cc: zsh-workers 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Integer overflow during brace expansion 2012-02-27 17:01 ` Mikael Magnusson @ 2012-02-27 17:35 ` Peter Stephenson 2012-03-01 14:30 ` Peter Stephenson 0 siblings, 1 reply; 7+ messages in thread From: Peter Stephenson @ 2012-02-27 17:35 UTC (permalink / raw) To: Leon Weber, zsh-workers 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Integer overflow during brace expansion 2012-02-27 17:35 ` Peter Stephenson @ 2012-03-01 14:30 ` Peter Stephenson 2012-03-01 16:20 ` Wayne Davison 0 siblings, 1 reply; 7+ messages in thread From: Peter Stephenson @ 2012-03-01 14:30 UTC (permalink / raw) To: zsh-workers 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 ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Integer overflow during brace expansion 2012-03-01 14:30 ` Peter Stephenson @ 2012-03-01 16:20 ` Wayne Davison 0 siblings, 0 replies; 7+ messages in thread From: Wayne Davison @ 2012-03-01 16:20 UTC (permalink / raw) To: Peter Stephenson; +Cc: zsh-workers [-- 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.. ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2012-03-01 16:20 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2012-02-27 16:22 Integer overflow during brace expansion Leon Weber 2012-02-27 16:52 ` Mikael Magnusson 2012-02-27 16:54 ` Mikael Magnusson 2012-02-27 17:01 ` Mikael Magnusson 2012-02-27 17:35 ` Peter Stephenson 2012-03-01 14:30 ` Peter Stephenson 2012-03-01 16:20 ` Wayne Davison
Code repositories for project(s) associated with this public inbox https://git.vuxu.org/mirror/zsh/ This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).