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

From: Assaf Gordon <[email-masked]>
Date: Sun, 8 Jul 2018 20:14:17 -0600

On 08/07/18 10:36 AM, Jim Meyering wrote:
> On Sat, Jul 7, 2018 at 9:28 PM, Assaf Gordon <[email-masked]> wrote:
>> 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.
>>
>> 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

>From c52a676e5e31f4f5c25d78f5dd4c17fab6585d8e 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 | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++
 testsuite/local.mk    |  1 +
 4 files changed, 88 insertions(+), 1 deletion(-)
 create mode 100755 testsuite/bug32082.sh

diff --git a/NEWS b/NEWS
index 6c2fbaf..ac166dd 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
+  backreferences 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..d5d4e92
--- /dev/null
+++ b/testsuite/bug32082.sh
@@ -0,0 +1,81 @@
+#!/bin/sh
+# sed would access uninitialized memory for certain invalid backreference uses.
+# 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 a 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