Package: sed;
Reported by: bugs <at> feusi.co
Date: Sat, 7 Jul 2018 14:01:03 UTC
Severity: normal
Tags: fixed
Done: Assaf Gordon <assafgordon <at> gmail.com>
Bug is archived. No further changes may be made.
Message #11 received at 32082 <at> debbugs.gnu.org (full text, mbox):
From: project-repo <bugs <at> feusi.co> To: Assaf Gordon <assafgordon <at> gmail.com>, 32082 <at> debbugs.gnu.org Subject: Re: bug#32082: heap buffer overflow in sed/execute.c, line 992 Date: Sun, 8 Jul 2018 09:41:26 +0200
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 "bugs <at> feusi.co" 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: <916db1d1-f158-fb30-76ef-e9c6f76c40f2 <at> gmail.com>
On Sat, Jul 07, 2018 at 10:28:36PM -0600, Assaf Gordon wrote:
> Hello,
>
> On 07/07/18 05:01 AM, bugs <at> feusi.co 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 "bugs <at> feusi.co" 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 <assafgordon <at> gmail.com>
> 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 bugs <at> feusi.co 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 bugs <at> feusi.co,
> +# 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
>
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.