https://bugzilla.novell.com/show_bug.cgi?id=763591 https://bugzilla.novell.com/show_bug.cgi?id=763591#c1 --- Comment #1 from S M <scotty.mcmillan+novell@gmail.com> 2012-05-29 10:33:59 UTC --- I investigated the cause of this bug and found several issues in bash. I submitted a bug report using the bashbug program. This program doesn't give me any bug number to link to, so I'll just paste the details I sent to bug-bash in case it's useful. From: scotty.mcmillan@gmail.com <Scott McMillan> To: bug-bash@gnu.org Subject: Brace expansion infinite loop, memory corruption, and other bugs. Configuration Information [Automatically generated, do not change]: Machine: x86_64 OS: linux-gnu Compiler: gcc -I/home/abuild/rpmbuild/BUILD/bash-4.2 -L/home/abuild/rpmbuild/BUILD/bash-4.2/../readline-6.2 Compilation CFLAGS: -DPROGRAM='bash' -DCONF_HOSTTYPE='x86_64' -DCONF_OSTYPE='linux-gnu' -DCONF_MACHTYPE='x86_64-suse-linux-gnu' -DCONF_VENDOR='suse' -DLOCALEDIR='/usr/share/locale' -DPACKAGE='bash' -DSHELL -DHAVE_CONFIG_H -I. -I. -I./include -I./lib -fmessage-length=0 -O2 -Wall -D_FORTIFY_SOURCE=2 -fstack-protector -funwind-tables -fasynchronous-unwind-tables -g -D_GNU_SOURCE -DRECYCLES_PIDS -Wall -g -std=gnu89 -Wuninitialized -Wextra -Wno-unprototyped-calls -Wno-switch-enum -Wno-unused-variable -Wno-unused-parameter -ftree-loop-linear -pipe -fprofile-use uname output: Linux wks-smcmillan 3.1.10-1.9-desktop #1 SMP PREEMPT Thu Apr 5 18:48:38 UTC 2012 (4a97ec8) x86_64 x86_64 x86_64 GNU/Linux Machine Type: x86_64-suse-linux-gnu Bash Version: 4.2 Patch Level: 10 Release Status: release Description: The errors are all to do with brace expansion in braces.c. 1) echo {9223372036854775806..9223372036854775807} was getting an infinite loop (or crash with memory corruption or seg fault). The error was in the mkseq function, because the increment of n done before checking the loop termination condition was susceptible to incidences of undefined signed integer overflow. This is fixed in the patch below. 2) The rhs value and any user-specified increment value were always clamped to the valid range while the sequence would refuse to expand if lhs was out of range. This is because strtoimax clamps on under/overflow and sets errno, but errno was only getting checked for lhs (inside the legal_number function). expand_seqterm has been changed in the patch below so that errno is checked after using strtoimax to read the rhs and incr values. This gives more correct and consistent behaviour. 3) The incr value was an int but was getting read using strtoimax, so values beyond the range of an int were getting truncated. incr has been changed to intmax_t in the patch below to fix this problem. 4) -incr in mkseq must be valid since the sign is switched depending on the order of start and end. There was potential undefined behaviour where it was equal to INTMAX_MIN. expand_seqterm now guarantees -incr will be valid in the patch below. 5) echo {0..9223372036854775807} was getting a segmentation fault due to overflow calculating the result size in mkseq. This is because the result size calculated in mkseq is an int (necessarily, since strvec_create takes an int as an argument), and because the wrong absolute value function was getting used (abs instead of imaxabs). After applying the patch below, expand_seqterm makes extra guarantees on the end and start values passed to mkseq such that no overflow will occur during the calculation and the result will not overflow int. This means that the example input given would fail to expand. Input such as {0..2147483645} will likely give an out of memory error, which is preferable to segmentation faults or corrupted memory. Repeat-By: 1) echo {9223372036854775806..9223372036854775807} 2) echo {9223372036854775806..9223372036854775808} (note second value is more than INTMAX_MAX, but the output before applying the patch is as if it were equal to INTMAX_MAX). 3) echo {0..10..9223372036854775807}. 4) Self-evident from code, -INTMAX_MIN is not valid. 5) echo {0..9223372036854775807} Fix: A patch to apply to braces.c to fix the issues mentioned above has been pasted in below. The fixes are: 1) Check for overflow before incrementing in the loop in mkseq. 2) Check errno after strtoimax when reading the rhs and incr values in expand_seqterm. 3) incr in expand_seqterm and mkseq is now intmax_t. 4) expand_seqterm verifies that -incr is not undefined. 5) code uses imaxabs for intmax_t values and expand_seqterm verifies the start and end values won't result in a range that overflows INT_MAX. *************** *** 31,36 **** --- 31,37 ---- # include <unistd.h> #endif + #include <errno.h> #include "bashansi.h" #if defined (SHELL) *************** *** 63,69 **** static int brace_gobbler __P((char *, size_t, int *, int)); static char **expand_amble __P((char *, size_t, int)); static char **expand_seqterm __P((char *, size_t)); ! static char **mkseq __P((intmax_t, intmax_t, int, int, int)); static char **array_concat __P((char **, char **)); #else static int brace_gobbler (); --- 64,70 ---- static int brace_gobbler __P((char *, size_t, int *, int)); static char **expand_amble __P((char *, size_t, int)); static char **expand_seqterm __P((char *, size_t)); ! static char **mkseq __P((intmax_t, intmax_t, intmax_t, int, int)); static char **array_concat __P((char **, char **)); #else static int brace_gobbler (); *************** *** 305,325 **** #define ST_CHAR 2 #define ST_ZINT 3 static char ** mkseq (start, end, incr, type, width) ! intmax_t start, end; ! int incr, type, width; { intmax_t n; int i; char **result, *t; ! ! i = abs (end - start) + 1; ! result = strvec_create (i + 1); ! if (incr == 0) incr = 1; if (start > end && incr > 0) incr = -incr; else if (start < end && incr < 0) --- 306,361 ---- #define ST_CHAR 2 #define ST_ZINT 3 + /* Returns true if lhs + rhs would under/overflow outside of [minval, maxval].*/ + static int + addwilloverflow(lhs, rhs, minval, maxval) + intmax_t lhs, rhs, minval, maxval; + { + return + (((lhs > 0) && (rhs > (maxval - lhs))) + || + ((lhs < 0) && (rhs < (minval - lhs)))); + } + + /* Returns true if lhs - rhs would under/overflow outside of [minval, maxval].*/ + static int + subtractwilloverflow(lhs, rhs, minval, maxval) + intmax_t lhs, rhs, minval, maxval; + { + return + (((rhs > 0) && (lhs < (minval + rhs))) + || + ((rhs < 0) && (lhs > (maxval + rhs)))); + } + + /* Caller must guarantee that incr > INTMAX_MIN, because -incr must be + valid. + Caller must also guarantee that the expression: imaxabs(end - start) + 2 + results in no under/overflow, will not result in passing INTMAX_MIN to + imaxabs, and has a value not greater than INT_MAX. */ static char ** mkseq (start, end, incr, type, width) ! intmax_t start, end, incr; ! int type, width; { intmax_t n; int i; char **result, *t; ! ! /* strvec_create argument is an int, so must make sure that the number of ! elements in the sequence (abs(end - start) + 1), + 1 for a NULL terminator, ! does not overflow int. This is covered by the function preconditions. */ ! i = imaxabs(end - start) + 1 + 1; ! ! /* Note: potentially allocating a lot more memory than required if ! incr > 1. */ ! result = strvec_create (i); ! if (incr == 0) incr = 1; + /* caller guarantees incr is > INTMAX_MIN, so we know + -incr is valid. */ if (start > end && incr > 0) incr = -incr; else if (start < end && incr < 0) *************** *** 349,354 **** --- 385,398 ---- t[1] = '\0'; result[i++] = t; } + + /* Can't increment n with incr before loop termination check, due to the + possibility of undefined signed integer overflow. */ + if (addwilloverflow(n, incr, INTMAX_MIN, INTMAX_MAX)) + { + break; + } + n += incr; if ((incr < 0 && n < end) || (incr > 0 && n > end)) break; *************** *** 365,372 **** size_t tlen; { char *t, *lhs, *rhs; ! int i, lhs_t, rhs_t, incr, lhs_l, rhs_l, width; ! intmax_t lhs_v, rhs_v; intmax_t tl, tr; char **result, *ep, *oep; --- 409,416 ---- size_t tlen; { char *t, *lhs, *rhs; ! int i, lhs_t, rhs_t, lhs_l, rhs_l, width; ! intmax_t lhs_v, rhs_v, incr; intmax_t tl, tr; char **result, *ep, *oep; *************** *** 397,404 **** { rhs_t = ST_INT; tr = strtoimax (rhs, &ep, 10); ! if (ep && *ep != 0 && *ep != '.') ! rhs_t = ST_BAD; /* invalid */ } else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.')) { --- 441,448 ---- { rhs_t = ST_INT; tr = strtoimax (rhs, &ep, 10); ! if (errno || ep && *ep != 0 && *ep != '.') ! rhs_t = ST_BAD; /* invalid or overflow/underflow */ } else if (ISALPHA (rhs[0]) && (rhs[1] == 0 || rhs[1] == '.')) { *************** *** 417,424 **** oep = ep; if (ep && *ep == '.' && ep[1] == '.' && ep[2]) incr = strtoimax (ep + 2, &ep, 10); ! if (*ep != 0) ! rhs_t = ST_BAD; /* invalid incr */ tlen -= ep - oep; } --- 461,472 ---- oep = ep; if (ep && *ep == '.' && ep[1] == '.' && ep[2]) incr = strtoimax (ep + 2, &ep, 10); ! if (errno || *ep != 0 || incr == INTMAX_MIN) ! /* invalid incr or overflow/underflow. Also, don't allow incr ! to be INTMAX_MIN, since the mkseq function requires that -incr ! is valid. */ ! rhs_t = ST_BAD; ! tlen -= ep - oep; } *************** *** 461,466 **** --- 509,524 ---- if (width < rhs_l && lhs_t == ST_ZINT) width = rhs_l; } + + /* Check the range of the sequence satisfies the preconditions for + mkseq, to avoid overflow. */ + if (subtractwilloverflow(rhs_v, lhs_v, INTMAX_MIN + 1 + 2, INTMAX_MAX - 2) || + ((imaxabs(rhs_v - lhs_v) + 2) > INT_MAX)) + { + free (lhs); + free (rhs); + return ((char **)NULL); + } result = mkseq (lhs_v, rhs_v, incr, lhs_t, width); -- Configure bugmail: https://bugzilla.novell.com/userprefs.cgi?tab=email ------- You are receiving this mail because: ------- You are on the CC list for the bug.