https://bugzilla.novell.com/show_bug.cgi?id=763591
https://bugzilla.novell.com/show_bug.cgi?id=763591#c1
--- Comment #1 from S M 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
#endif
+ #include
#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.