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

From: Assaf Gordon <[email-masked]>
Date: Sat, 7 Jul 2018 22:28:36 -0600

Hello,

On 07/07/18 05:01 AM, [email-masked] 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 "[email-masked]" 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 <[email-masked]>
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 [email-masked] 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 [email-masked],
+# 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