From ac0a3526c78a321ac5ecf51f6868caea65f04158 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 11 Mar 2024 23:36:38 -0700 Subject: [PATCH 4/5] Fix problems with large brace expansions Do not mishandle brace expansions with more than INT_MAX elements. Check more carefully for integer overflow in brace expansions. Use C23-style checking for integer overflow, as that is more future-proof. * braces.c: Include . (mkseq): Width arg is size_t, not int, to avoid imposing an arbitrary limit. All uses changed. Do not assume number of elements fits in int, or that INT_MAX <= SIZE_MAX. Simplify overflow checks. Add a FIXME about an unlikely crash on interrupt. Zero pad by hand, since asprintf cannot handle widths > INT_MAX. * include/typemax.h (sh_imaxabs, ADDOVERFLOW, SUBOVERFLOW): Remove; no longer used. * lib/sh/stringvec.c: Include . (strvec_mcreate): Check for integer overflow. (strvec_flush): Don't assume vector size fits in int. * stringlib.c (substring): Don't assume string size fits in int. --- braces.c | 165 ++++++++++++++++++++++----------------------- externs.h | 2 +- include/typemax.h | 19 ------ lib/sh/stringvec.c | 6 +- stringlib.c | 4 +- 5 files changed, 87 insertions(+), 109 deletions(-) diff --git a/braces.c b/braces.c index 17d28073..860c228a 100644 --- a/braces.c +++ b/braces.c @@ -32,6 +32,7 @@ #endif #include +#include #include "bashansi.h" #include "bashintl.h" @@ -77,7 +78,7 @@ static const int brace_arg_separator = ','; static int brace_gobbler (char *, size_t, int *, int); static char **expand_amble (char *, size_t, int); static char **expand_seqterm (char *, size_t); -static char **mkseq (intmax_t, intmax_t, intmax_t, int, int); +static char **mkseq (intmax_t, intmax_t, intmax_t, int, size_t); static char **array_concat (char **, char **); #if 0 @@ -349,120 +350,114 @@ expand_amble (char *text, size_t tlen, int flags) #define ST_ZINT 3 static char ** -mkseq (intmax_t start, intmax_t end, intmax_t incr, int type, int width) +mkseq (intmax_t start, intmax_t end, intmax_t incr, int type, size_t width) { - intmax_t n, prevn; - int i, nelem; + intmax_t prevn, abs_incr; + size_t nelem; char **result, *t; + char lbuf[INT_BUFSIZE_BOUND (uintmax_t)]; if (incr == 0) incr = 1; - if (start > end && incr > 0) - incr = -incr; - else if (start < end && incr < 0) - { - if (incr == INTMAX_MIN) /* Don't use -INTMAX_MIN */ - return ((char **)NULL); - incr = -incr; - } - - /* Check that end-start will not overflow INTMAX_MIN, INTMAX_MAX. The +3 - and -2, not strictly necessary, are there because of the way the number - of elements and value passed to strvec_create() are calculated below. */ - if (SUBOVERFLOW (end, start, INTMAX_MIN+3, INTMAX_MAX-2)) + /* abs_incr = abs (incr) */ + abs_incr = incr; + if (incr < 0 && ckd_sub (&abs_incr, 0, incr)) return ((char **)NULL); - prevn = sh_imaxabs (end - start); - /* Need to check this way in case INT_MAX == INTMAX_MAX */ - if (INT_MAX == INTMAX_MAX && (ADDOVERFLOW (prevn, 2, INT_MIN, INT_MAX))) + /* Negate incr if it disagrees with start < end. */ + if ((start < end) == (incr < 0) && ckd_sub (&incr, 0, incr)) return ((char **)NULL); - /* Make sure the assignment to nelem below doesn't end up <= 0 due to - intmax_t overflow */ - else if (ADDOVERFLOW ((prevn/sh_imaxabs(incr)), 1, INTMAX_MIN, INTMAX_MAX)) + + /* prevn = abs (end - start); */ + if (start < end + ? ckd_sub (&prevn, end, start) + : ckd_sub (&prevn, start, end)) return ((char **)NULL); - /* XXX - TOFIX: potentially allocating a lot of extra memory if - imaxabs(incr) != 1 */ - /* Instead of a simple nelem = prevn + 1, something like: - nelem = (prevn / imaxabs(incr)) + 1; - would work */ - if ((prevn / sh_imaxabs (incr)) > INT_MAX - 3) /* check int overflow */ + /* The number of elements is floor (abs ((end - start) / incr)), + plus 1 for the first element, plus 1 for trailing nullptr. */ + if (ckd_add (&nelem, prevn / abs_incr, 1 + 1)) return ((char **)NULL); - nelem = (prevn / sh_imaxabs(incr)) + 1; - result = strvec_mcreate (nelem + 1); - if (result == 0) - { - internal_error (_("brace expansion: failed to allocate memory for %u elements"), (unsigned int)nelem); - return ((char **)NULL); - } - /* Make sure we go through the loop at least once, so {3..3} prints `3' */ - i = 0; - n = start; - do + result = strvec_mcreate (nelem); + if (result) { + /* Go through the loop at least once, so {3..3} expands to 3. */ + size_t i = 0; + intmax_t n; + for (n = start; ; n += incr) + { #if defined (SHELL) - if (ISINTERRUPT) - { - result[i] = (char *)NULL; - strvec_dispose (result); - result = (char **)NULL; - } - QUIT; + if (ISINTERRUPT) + { + result[i] = (char *)NULL; + strvec_dispose (result); + result = (char **)NULL; + /* FIXME: This crashes if QUIT does not throw to the + top level, which seems possible albeit unlikely. */ + } + QUIT; #endif - if (type == ST_INT) - result[i++] = t = itos (n); - else if (type == ST_ZINT) - { - int len, arg; - arg = n; - len = asprintf (&t, "%0*d", width, arg); - result[i++] = t; - } - else - { - if (t = (char *)malloc (2)) + if (type == ST_CHAR) { - t[0] = n; - t[1] = '\0'; + t = (char *)malloc (2); + if (t) + { + t[0] = n; + t[1] = '\0'; + } + } + else + { + t = itos (n); + if (type == ST_ZINT) + { + size_t tlen = strlen (t); + if (tlen < width) + { + /* Zero pad the result directly, as sprintf + does not work when INT_MAX < width. */ + char *t0 = t; + t = realloc (t, width + 1); + if (!t) + free (t0); + else + { + memmove (t + (width - tlen), t, tlen + 1); + memset (t + (n < 0), '0', width - tlen); + } + } + } } - result[i++] = t; - } - /* We failed to allocate memory for this number, so we bail. */ - if (t == 0) - { - char *p, lbuf[INT_STRLEN_BOUND(intmax_t) + 1]; - - /* Easier to do this than mess around with various intmax_t printf - formats (%ld? %lld? %jd?) and PRIdMAX. */ - p = inttostr (n, lbuf, sizeof (lbuf)); - internal_error (_("brace expansion: failed to allocate memory for `%s'"), p); - strvec_dispose (result); - return ((char **)NULL); - } + result[i++] = t; - /* Handle overflow and underflow of n+incr */ - if (ADDOVERFLOW (n, incr, INTMAX_MIN, INTMAX_MAX)) - break; + /* Bail if we failed to allocate memory for this number. */ + if (!t) + break; - n += incr; + if (i == nelem - 1) + { + result[i] = (char *)0; + return (result); + } + } - if ((incr < 0 && n < end) || (incr > 0 && n > end)) - break; + strvec_dispose (result); } - while (1); - result[i] = (char *)0; - return (result); + internal_error (_("brace expansion: cannot allocate %s elements"), + uinttostr (nelem - 1, lbuf, sizeof (lbuf))); + return ((char **)NULL); } static char ** expand_seqterm (char *text, size_t tlen) { char *t, *lhs, *rhs; - int lhs_t, rhs_t, lhs_l, rhs_l, width; + int lhs_t, rhs_t; + size_t lhs_l, rhs_l, width; intmax_t lhs_v, rhs_v, incr; intmax_t tl, tr; char **result, *ep, *oep; diff --git a/externs.h b/externs.h index 6376bf41..b60fb79e 100644 --- a/externs.h +++ b/externs.h @@ -164,7 +164,7 @@ extern int find_string_in_alist (char *, STRING_INT_ALIST *, int); extern char *find_token_in_alist (int, STRING_INT_ALIST *, int); extern int find_index_in_alist (char *, STRING_INT_ALIST *, int); -extern char *substring (const char *, int, int); +extern char *substring (const char *, size_t, size_t); extern char *strsub (const char *, const char *, const char *, int); extern char *strcreplace (const char *, int, const char *, int); extern void strip_leading (char *); diff --git a/include/typemax.h b/include/typemax.h index e3b98f47..c93fda73 100644 --- a/include/typemax.h +++ b/include/typemax.h @@ -119,23 +119,4 @@ static const unsigned long long int maxquad = ULLONG_MAX; # define SIZE_MAX ((size_t) ~(size_t)0) #endif -#ifndef sh_imaxabs -# define sh_imaxabs(x) (((x) >= 0) ? (x) : -(x)) -#endif - -/* Handle signed arithmetic overflow and underflow. Have to do it this way - to avoid compilers optimizing out simpler overflow checks. */ - -/* Make sure that a+b does not exceed MAXV or is smaller than MINV (if b < 0). - Assumes that b > 0 if a > 0 and b < 0 if a < 0 */ -#define ADDOVERFLOW(a,b,minv,maxv) \ - ((((a) > 0) && ((b) > ((maxv) - (a)))) || \ - (((a) < 0) && ((b) < ((minv) - (a))))) - -/* Make sure that a-b is not smaller than MINV or exceeds MAXV (if b < 0). - Assumes that b > 0 if a > 0 and b < 0 if a < 0 */ -#define SUBOVERFLOW(a,b,minv,maxv) \ - ((((b) > 0) && ((a) < ((minv) + (b)))) || \ - (((b) < 0) && ((a) > ((maxv) + (b))))) - #endif /* _SH_TYPEMAX_H */ diff --git a/lib/sh/stringvec.c b/lib/sh/stringvec.c index bf57d688..01e65a87 100644 --- a/lib/sh/stringvec.c +++ b/lib/sh/stringvec.c @@ -27,6 +27,7 @@ #endif #include +#include #include #include @@ -43,7 +44,8 @@ strvec_create (size_t n) char ** strvec_mcreate (size_t n) { - return ((char **)malloc ((n) * sizeof (char *))); + size_t nbytes; + return ckd_mul (&nbytes, n, sizeof (char *)) ? NULL : malloc (nbytes); } char ** @@ -72,7 +74,7 @@ strvec_len (char * const *array) void strvec_flush (char **array) { - register int i; + register size_t i; if (array == 0) return; diff --git a/stringlib.c b/stringlib.c index 7c24df62..fcfd5e2d 100644 --- a/stringlib.c +++ b/stringlib.c @@ -115,9 +115,9 @@ find_index_in_alist (char *string, STRING_INT_ALIST *alist, int flags) /* Cons a new string from STRING starting at START and ending at END, not including END. */ char * -substring (const char *string, int start, int end) +substring (const char *string, size_t start, size_t end) { - int len; + size_t len; char *result; len = end - start; -- 2.44.0