bug#32082: heap buffer overflow in sed/execute.c, line 992

[project-repo]

Hi, 
Thanks for the quick response. that patch seems to work at first glance.
I'll keep fuzzing and tell you if I find anything interesting. Oh yes,
about my name: I had some problems once when I reported a bug using my
real name, with people sending me phishing emails and things, so I set
up this email address which I could use for reporting bugs. Crediting
this bug to "address@hidden" is perfect, thanks. Then, to your second
question: I actually used an off-the-shelf afl fuzzer for this fuzzing
process. The first crashes started to appear about 6 hours after I
started. The setup was as follows: I ran 6 parallel fuzzers which each
called sed as "sed -f /dev/stdin testfile". The file "testfile" was a
rather large file piped from /dev/urandom, which aided the fuzzing
process, as the bug I reported only causes a segmentation fault when
the "testfile" has specific properties. I didn't compile sed with
address sanitizer as it produced a bunch of false positives when I tried
to use it. The fuzzing input file was a complex regex string
which I pulled off the internet somewhere, although it does not bear
much resemblance to the buggy file, so I don't think it mattered so much.

Thanks again for fixing this so quickly and analysing this bug in such
detail. This will be very helpful for my project. :)

cheers,
project-repo
In-Reply-To: <address@hidden>

On Sat, Jul 07, 2018 at 10:28:36PM -0600, Assaf Gordon wrote:
> Hello,
> 
> On 07/07/18 05:01 AM, address@hidden wrote:
> > I am working on a project in which I use the afl fuzzer to fuzz
> > different open-source software. In doing so, I discovered a
> > heap buffer overflow in sed/execute.c, line 992.
> 
> Thank you for this interesting bug report, and for providing such easy
> way to reproduce. I can confirm this is reproducible, and in fact is
> a very old bug! fantastic work.
> 
> It took some time and lots of squinting to track it down, so I'll write
> it here in details for others.
> 
> Your sed script file was:
> ====
> 10s11\91
> \0^0s1011
> \00a
> \0^0s111w0
> ====
> 
> The input file content doesn't matter for the bug, so I won't focus on it.
> 
> Interested readers - If you like challenges, stop reading this email and
> spend couple of minutes trying to understand the above script.
> fun a-plenty :)
> 
> I assume that all the 1's and 0's are because AFL mutated bit by bit
> until something was triggered. They aren't critical for the bug, so
> here's a simpler and more concise buggy program:
> 
> ====
>    seq 2 | valgrind sed -e '/^/s///p ; 2s//\9/'
> ====
> 
> It might still not be immediately clear why there is a bug here.
> An even simpler version of the above program does not seem buggy at
> first, because the invalid backref is detected:
> ===
>   $ seq 2 | sed -e '/^/p; 2s//\9/'
>   1
>   1
>   2
>   sed: -e expression #1, char 0: invalid reference \9 on `s' command
> ===
> 
> However, this detection suppressed under "--posix", so the bug is
> actually there:
> ====
>   $ seq 2 | valgrind sed --posix -e '/^/p; 2s//\9/'
> 
>   1
>   1
>   2
>   ==19663== Invalid read of size 4
>   ==19663==    at 0x10FD51: ??? (in /bin/sed)
>   ==19663==    by 0x110402: ??? (in /bin/sed)
>   ==19663==    by 0x10B106: ??? (in /bin/sed)
>   ==19663==    by 0x50802E0: (below main) (libc-start.c:291)
>   ==19663==  Address 0x5a9df74 is 20 bytes after a block of size 16 in
>   [....]
> ====
> 
> The novelty of this bug report is that using few more "previous regexes"
> and the ^/$ optimization [1], the safety check is bypassed even when not
> using "--posix".
> [1] https://git.savannah.gnu.org/cgit/sed.git/commit/?id=6dea75e7
> 
> 
> Attached is a suggested fix.
> It seems very simple, but I encourage everyone to double-check my logic
> and perhaps detect more problems.
> 
> comments very welcomed,
>  - assaf
> 
> 
> P.S.
> 1. You haven't provided a name, so I credited you as "address@hidden" in
> the commit message. If you'd like something else, let me know.
> 
> 2. Out of curiosity, are you using stock AFL or a modified one?
> If stock AFL, how long did you run it before something was triggered,
> and how was it configured (and which input files) ?
> I used AFL on previous version of sed for 24 hours without any bug detected.
> 
> 
> 
> 
> 
> 
> 

> From 1644a080b8a22aa36ff187218f9895a06127efdd Mon Sep 17 00:00:00 2001
> From: Assaf Gordon <address@hidden>
> Date: Sat, 7 Jul 2018 22:03:38 -0600
> Subject: [PATCH] sed: fix heap buffer overflow from invalid references
> 
> Under certain conditions sed would access invalid memory based on
> the requested back-reference (e.g. "s//\9/" would access the 9th element
> in the regex registers without checking it is at least 9 element in
> size).
> 
> The following examples would trigger valgrind errors:
>     seq 2 | valgrind sed         -e '/^/s///p ; 2s//\9/'
>     seq 2 | valgrind sed --posix -e '/2/p ;     2s//\9/'
> 
> Reported by address@hidden in
> https://lists.gnu.org/r/bug-sed/2018-07/msg00004.html .
> 
> * NEWS: Mention the bugfix.
> * sed/execute.c (append_replacement): Check number of allocated regex
> replacement registers before accessing the array.
> * sed/testsuite/bug32082.sh: Test sed for this behaviour under valgrind.
> * sed/testsuite/local.mk (T): Add new test.
> ---
>  NEWS                  |  5 ++++
>  sed/execute.c         |  2 +-
>  testsuite/bug32082.sh | 82 
> +++++++++++++++++++++++++++++++++++++++++++++++++++
>  testsuite/local.mk    |  1 +
>  4 files changed, 89 insertions(+), 1 deletion(-)
>  create mode 100755 testsuite/bug32082.sh
> 
> diff --git a/NEWS b/NEWS
> index 6c2fbaf..0c50526 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -2,6 +2,11 @@ GNU sed NEWS                                    -*- outline 
> -*-
>  
>  * Noteworthy changes in release ?.? (????-??-??) [?]
>  
> +** Bug fixes
> +
> +  sed no longer accesses invalid memory (heap overflow) when given invalid
> +  references in 's' command [bug#32082, present at least since sed-4.0.6].
> +
>  
>  * Noteworthy changes in release 4.5 (2018-03-31) [stable]
>  
> diff --git a/sed/execute.c b/sed/execute.c
> index 2804c5e..7a4850f 100644
> --- a/sed/execute.c
> +++ b/sed/execute.c
> @@ -987,7 +987,7 @@ static void append_replacement (struct line *buf, struct 
> replacement *p,
>            curr_type &= ~REPL_MODIFIERS;
>          }
>  
> -      if (0 <= i)
> +      if (0 <= i && i < regs->num_regs)
>          {
>            if (regs->end[i] == regs->start[i] && p->repl_type & 
> REPL_MODIFIERS)
>              /* Save this modifier, we shall apply it later.
> diff --git a/testsuite/bug32082.sh b/testsuite/bug32082.sh
> new file mode 100755
> index 0000000..6a77656
> --- /dev/null
> +++ b/testsuite/bug32082.sh
> @@ -0,0 +1,82 @@
> +#!/bin/sh
> +# sed may access to uninitialized memory whe invalid backreference
> +# are used under certain circumstances.
> +# Before sed 4.6 these would result in "Invalid read size of 4" reported
> +# by valgrind from execute.c:992
> +
> +# Copyright (C) 2018 Free Software Foundation, Inc.
> +
> +# This program is free software: you can redistribute it and/or modify
> +# it under the terms of the GNU General Public License as published by
> +# the Free Software Foundation, either version 3 of the License, or
> +# (at your option) any later version.
> +
> +# This program is distributed in the hope that it will be useful,
> +# but WITHOUT ANY WARRANTY; without even the implied warranty of
> +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
> +# GNU General Public License for more details.
> +
> +# You should have received a copy of the GNU General Public License
> +# along with this program.  If not, see <https://www.gnu.org/licenses/>.
> +. "${srcdir=.}/testsuite/init.sh"; path_prepend_ ./sed
> +print_ver_ sed
> +
> +require_valgrind_
> +
> +printf '1\n2\n' > in || framework_failure_
> +printf '1\n2\n\n' > exp-posix || framework_failure_
> +printf '1\n1\n2\n2\n' > exp-no-posix || framework_failure_
> +
> +#
> +# Test 1: with "--posix"
> +#
> +# using "--posix" disables the backref safety check in
> +# regexp.c:compile_regex_1(), which is reported as:
> +#     "invalid reference \\%d on `s' command's RHS"
> +
> +valgrind --quiet --error-exitcode=1 \
> +  sed --posix -e '/2/p ; 2s//\9/' in > out-posix 2> err-posix || fail=1
> +
> +echo "valgrind report for 'posix' test:"
> +echo "=================================="
> +cat err-posix
> +echo "=================================="
> +
> +
> +# Work around a bug in CentOS 5.10's valgrind
> +# FIXME: remove in 2018 or when CentOS 5 is no longer officially supported
> +grep 'valgrind: .*Assertion.*failed' err-posix > /dev/null \
> +  && skip_ 'you seem to have a buggy version of valgrind'
> +
> +compare exp-posix out-posix || fail=1
> +compare /dev/null err || fail=1
> +
> +
> +
> +#
> +# Test 2: without "--posix"
> +#
> +# When not using "--posix", using a backref to a non-existing group.
> +# would be caught in compile_regex_1.
> +# As reported in bugs.gnu.org/32082 by address@hidden,
> +# using the recent begline/endline optimization with few "previous regex"
> +# tricks bypasses this check.
> +
> +valgrind --quiet --error-exitcode=1 \
> +  sed -e  '/^/s///p ; 2s//\9/' in > out-no-posix 2> err-no-posix || fail=1
> +
> +echo "valgrind report for 'no-posix' test:"
> +echo "===================================="
> +cat err-no-posix
> +echo "===================================="
> +
> +# Work around a bug in CentOS 5.10's valgrind
> +# FIXME: remove in 2018 or when CentOS 5 is no longer officially supported
> +grep 'valgrind: .*Assertion.*failed' err-no-posix > /dev/null \
> +  && skip_ 'you seem to have a buggy version of valgrind'
> +
> +compare exp-no-posix out-no-posix || fail=1
> +compare /dev/null err || fail=1
> +
> +
> +Exit $fail
> diff --git a/testsuite/local.mk b/testsuite/local.mk
> index b4a4f5a..bf4559f 100644
> --- a/testsuite/local.mk
> +++ b/testsuite/local.mk
> @@ -43,6 +43,7 @@ LOG_COMPILER = false
>  
>  T =                                  \
>    testsuite/misc.pl                  \
> +  testsuite/bug32082.sh              \
>    testsuite/cmd-l.sh                 \
>    testsuite/cmd-R.sh                 \
>    testsuite/colon-with-no-label.sh   \
> -- 
> 2.11.0
>