GNU bug report logs - #32082
heap buffer overflow in sed/execute.c, line 992

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 32082 in the body.
You can then email your comments to 32082 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: bugs <at> feusi.co
To: bug-sed <at> gnu.org
Subject: heap buffer overflow in sed/execute.c, line 992
Date: Sat, 7 Jul 2018 13:01:14 +0200

[Message part 1 (text/plain, inline)]

Hi,
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. Following is a
detailed backtrace:

=================================================================
==18674==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000fb8 at pc 0x55d4f61c3909 bp 0x7ffc4fa90580 sp 0x7ffc4fa90578
READ of size 8 at 0x602000000fb8 thread T0
    #0 0x55d4f61c3908 in append_replacement sed/execute.c:992
    #1 0x55d4f61c3908 in do_subst sed/execute.c:1071
    #2 0x55d4f61c3908 in execute_program sed/execute.c:1507
    #3 0x55d4f61c516a in process_files sed/execute.c:1677
    #4 0x55d4f619c649 in main sed/sed.c:377
    #5 0x7f15904d2a86 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21a86)
    #6 0x55d4f619d119 in _start (/home/jefeus/sed/sed/sed+0xc119)

Address 0x602000000fb8 is a wild pointer.
SUMMARY: AddressSanitizer: heap-buffer-overflow sed/execute.c:992 in append_replacement
Shadow bytes around the buggy address:
  0x0c047fff81a0: fa fa 00 00 fa fa 00 00 fa fa 01 fa fa fa fd fd
  0x0c047fff81b0: fa fa 00 00 fa fa 00 00 fa fa 01 fa fa fa 00 00
  0x0c047fff81c0: fa fa 00 00 fa fa 00 00 fa fa 00 00 fa fa 00 00
  0x0c047fff81d0: fa fa 00 00 fa fa 00 00 fa fa fd fd fa fa fd fa
  0x0c047fff81e0: fa fa 00 00 fa fa 00 00 fa fa 00 fa fa fa 00 fa
=>0x0c047fff81f0: fa fa fa fa fa fa fa[fa]fa fa fa fa fa fa fa fa
  0x0c047fff8200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8210: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8220: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8230: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8240: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==18674==ABORTING

To reproduce this bug run sed with:
sed -f <script-file> <input-file>
Where <script-file> and <input-file> are the two files attached.
These files demonstrate how this bug can be used to print undefined
memory. By replacing the first line in <input-file> with a long string
of "A"s, a segmentation fault can be produced.

I was able to reproduce this bug with the current git version, the
debian version and on arch linux.

cheers,
project-repo

[script-file (text/plain, attachment)]

[input-file (application/octet-stream, attachment)]

Message #8 received at 32082 <at> debbugs.gnu.org (full text, mbox):

From: Assaf Gordon <assafgordon <at> gmail.com>
To: bugs <at> feusi.co, 32082 <at> debbugs.gnu.org
Subject: Re: bug#32082: heap buffer overflow in sed/execute.c, line 992
Date: Sat, 7 Jul 2018 22:28:36 -0600

[Message part 1 (text/plain, inline)]

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.

[0001-sed-fix-heap-buffer-overflow-from-invalid-references.patch (text/x-patch, attachment)]

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
> 

Message #14 received at 32082 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Assaf Gordon <assafgordon <at> gmail.com>
Cc: bugs <at> feusi.co, 32082 <at> debbugs.gnu.org
Subject: Re: bug#32082: heap buffer overflow in sed/execute.c, line 992
Date: Sun, 8 Jul 2018 09:36:27 -0700

[Message part 1 (text/plain, inline)]

On Sat, Jul 7, 2018 at 9:28 PM, Assaf Gordon <assafgordon <at> gmail.com> 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,

Fine work! Thank you, Assaf.
Here are some suggested comment adjustments:

[sed-touchups.diff (application/octet-stream, attachment)]

Message #17 received at 32082 <at> debbugs.gnu.org (full text, mbox):

From: Assaf Gordon <assafgordon <at> gmail.com>
To: Jim Meyering <jim <at> meyering.net>
Cc: bugs <at> feusi.co, 32082 <at> debbugs.gnu.org
Subject: Re: bug#32082: heap buffer overflow in sed/execute.c, line 992
Date: Sun, 8 Jul 2018 20:14:17 -0600

[Message part 1 (text/plain, inline)]

On 08/07/18 10:36 AM, Jim Meyering wrote:
> On Sat, Jul 7, 2018 at 9:28 PM, Assaf Gordon <assafgordon <at> gmail.com> wrote:
>> 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.
>>
>> Attached is a suggested fix.
>>
>> comments very welcomed,
> 
> Here are some suggested comment adjustments:

Thanks.

Attached updated version.
I will push it tomorrow if there are no further comments.


regards,
 - assaf

[0001-sed-fix-heap-buffer-overflow-from-invalid-references.patch (text/x-patch, attachment)]

Message #24 received at 32082-done <at> debbugs.gnu.org (full text, mbox):

From: Assaf Gordon <assafgordon <at> gmail.com>
To: Jim Meyering <jim <at> meyering.net>
Cc: bugs <at> feusi.co, 32082-done <at> debbugs.gnu.org
Subject: Re: bug#32082: heap buffer overflow in sed/execute.c, line 992
Date: Wed, 11 Jul 2018 00:51:57 -0600

tags 32082 fixed
stop

>> On Sat, Jul 7, 2018 at 9:28 PM, Assaf Gordon <assafgordon <at> gmail.com>  >> wrote:>>> 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.>>> Attached is a suggested fix.

pushed here:
https://git.savannah.gnu.org/cgit/sed.git/commit/?id=c52a676e

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.