Brace expansion infinite loop, memory corruption, and other bugs.

[Scott McMillan]

A week or so ago I submitted a bug report using the bashbug command
that involved some
overflow issues with braces.c on OpenSUSE12.1 X86_64. Browsing the
patches, I got
the impression that braces.c hasn't been modified since the original
4.2 release, so the
same bugs should exist in the most recent version.

I also submitted potential fixes for the issues. I noticed that the
code in the patch I
submitted was forgetting to set errno = 0 before calling strtoimax.
Therefore I thought I
might as well send a slightly updated patch, which is a bit neater and
at least doesn't have
that particular bug in it.

Regards,
Scott.

----------------------------------PREVIOUS MESSAGE FOR
REFERENCE------------------------------------
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.

<old patch removed>

braces.c.patch
Description: Binary data