Subject: bug#32271: heap buffer overflow in regexp.c, line 286

From: Assaf Gordon <[email-masked]>
Date: Fri, 27 Jul 2018 04:13:03 -0600

Hello,

On 25/07/18 08:34 AM, project-repo wrote:
> I let the fuzzer run again and it came up with a second heap buffer
> overflow. This time in regexp.c, line 286. Here is a backtrace as
> supplied by the address sanitizer:
> 
> =================================================================
> ==7428==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x611000000b2f at pc 0x7fee3354c574 bp 0x7ffd9adf2120 sp 0x7ffd9adf18d0
> READ of size 238 at 0x611000000b2f thread T0
>      #0 0x7fee3354c573  (/usr/lib/x86_64-linux-gnu/libasan.so.4+0x40573)
>      #1 0x55aabd6d7025 in match_regex sed/regexp.c:286
>      #2 0x55aabd6cd5a5 in do_subst sed/execute.c:1098
>      #3 0x55aabd6cd5a5 in execute_program sed/execute.c:1507
>      #4 0x55aabd6d4d5a in process_files sed/execute.c:1677
>      #5 0x55aabd6ac5a2 in main sed/sed.c:377
>      #6 0x7fee33173a86 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21a86)
>      #7 0x55aabd6ad1c9 in _start (/home/jefeus/sed/sed/sed+0xc1c9)

Once again, great work - you indirectly found a 15-year-old bug,
in addition to the above heap buffer overflow.

The two attached patches should explain it in detail.

As these changes are somewhat subtle, I encourage everyone to
double-check them...

comments welcomed,
  - assaf

>From d6b43e5e1763bccf664e8afda4c4556ef5009d19 Mon Sep 17 00:00:00 2001
From: Assaf Gordon <[email-masked]>
Date: Fri, 27 Jul 2018 01:56:26 -0600
Subject: [PATCH 1/2] sed: fix extraneous NUL in s///n command

Under certain conditions sed would add an extraneous NUL:

    $ echo 0 | sed -e 's/$/a/2' | od -tx1 -An
     30 00 0a

This would happen when the regex is an empty (zero-length) match at the
end of the line (e.g. '$' and 'a*$') and the substitute number flag
('n' in s///n) is higher than the number of actual matches (multiple
EOL matches are possible with multiline match, e.g. 's/$/a/3m').

Details:
The comment at the top of 'execute.c:do_subst()' says:

       /* The first part of the loop optimizes s/xxx// when xxx is at the
          start, and s/xxx$// */

Which refers to lines 1051-3:

  1051 /* Copy stuff to the left of this match into the output string. */
  1052 if (start < offset)
  1053   str_append(&s_accum, line.active + start, offset - start);

The above code appends text to 's_accum' but does *not* update 'start'.

Later on, if the s/// command includes 'n' flag, and if 'matched == 0'
(an empty match), this comparison will be incorrect:

  1081  if (start < line.length)
  1082     matched = 1;

Will in turn will set 'matched' to 1, and the 'str_append' call that
follows (line 1087) will append an additional character.
Because the empty match is EOL, the appended character is NUL.

More examples that trigger the bug:

  echo 0 | sed -e 's/a*$/X/3'
  printf "%s\n" 0 0 0 | sed -e 'N;N;s/a*$/X/4m'

Examples that do not trigger the bug:

  # The 'a*' empty regex matches at the beginning of the line (in
  # addition to the end of the line), and the optimization in line
  # 1052 is skipped.
  echo 0 | sed -e 's/a*/X/3'

  # There are 3 EOLs in the pattern space, s///3 is not too large.
  printf "%s\n" 0 0 0 | sed -e 'N;N;s/a*$/X/3m'

This was discovered while investigating bug#32271 reported by [email-masked]
in https://lists.gnu.org/r/bug-sed/2018-07/msg00018.html .

* NEWS: Mention the fix.
* sed/execute.c (do_subst): Update 'start' as needed.
* testsuite/bug-32271-1.sh: New test.
* testsuite/local.mk (T): Add test.
---
 NEWS                    |  3 +++
 sed/execute.c           |  5 ++++-
 testsuite/bug32271-1.sh | 45 +++++++++++++++++++++++++++++++++++++++++++++
 testsuite/local.mk      |  1 +
 4 files changed, 53 insertions(+), 1 deletion(-)
 create mode 100755 testsuite/bug32271-1.sh

diff --git a/NEWS b/NEWS
index ac166dd..f9293f3 100644
--- a/NEWS
+++ b/NEWS
@@ -7,6 +7,9 @@ GNU sed NEWS                                    -*- outline -*-
   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].
 
+  sed no longer adds extraneous NUL when given s/$//n command.
+  [related to bug#32271, present since sed-4.0.7]
+
 
 * Noteworthy changes in release 4.5 (2018-03-31) [stable]
 
diff --git a/sed/execute.c b/sed/execute.c
index a608f7d..f0a1e04 100644
--- a/sed/execute.c
+++ b/sed/execute.c
@@ -1050,7 +1050,10 @@ do_subst(struct subst *sub)
 
       /* Copy stuff to the left of this match into the output string. */
       if (start < offset)
-        str_append(&s_accum, line.active + start, offset - start);
+	{
+          str_append(&s_accum, line.active + start, offset - start);
+          start = offset;
+	}
 
       /* If we're counting up to the Nth match, are we there yet?
          And even if we are there, there is another case we have to
diff --git a/testsuite/bug32271-1.sh b/testsuite/bug32271-1.sh
new file mode 100755
index 0000000..99a0934
--- /dev/null
+++ b/testsuite/bug32271-1.sh
@@ -0,0 +1,45 @@
+#!/bin/sh
+# sed would incorrectly copy internal buffers under certain s/// uses.
+# Before sed 4.6 these would result in an extraneous NUL at end of lines.
+#
+
+# 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
+
+printf '0\n' > in || framework_failure_
+printf '0\n' > exp || framework_failure_
+
+# Before sed 4.6, this would result in: 0x30 0x00 0x0a.
+sed -e 's/$/a/2' in > out 2> err || fail=1
+
+compare exp out || fail=1
+compare /dev/null err || fail=1
+
+# To ease debugging / error reporting (the above 'compare'
+# will report "binary file differ" - not very helpful here)
+if test -n "$fail" ; then
+    echo "---- TEST FAILED"
+    echo "out:"
+    od -tx1 out
+    echo "exp:"
+    od -tx1 exp
+    echo "err:"
+    od -tx1 err
+fi
+
+
+Exit $fail
diff --git a/testsuite/local.mk b/testsuite/local.mk
index bf4559f..1181a0c 100644
--- a/testsuite/local.mk
+++ b/testsuite/local.mk
@@ -44,6 +44,7 @@ LOG_COMPILER = false
 T =					\
   testsuite/misc.pl			\
   testsuite/bug32082.sh		\
+  testsuite/bug32271-1.sh		\
   testsuite/cmd-l.sh			\
   testsuite/cmd-R.sh			\
   testsuite/colon-with-no-label.sh	\
-- 
2.11.0

>From c4863b9ab18fd4a25679182d8045f8ef18efccd1 Mon Sep 17 00:00:00 2001
From: Assaf Gordon <[email-masked]>
Date: Fri, 27 Jul 2018 02:19:41 -0600
Subject: [PATCH 2/2] sed: fix heap buffer overflow from multiline EOL regex
 optimization

sed would access invalid memory when matching EOF combined with
s///n flag:

  $ yes 0 | fmt -w 40 | head -n2 | valgrind sed 'N;s/$//2m'
  ==13131== Conditional jump or move depends on uninitialised value(s)
  ==13131==    at 0x4C3002B: memchr (vg_replace_strmem.c:883)
  ==13131==    by 0x1120BD: match_regex (regexp.c:286)
  ==13131==    by 0x110736: do_subst (execute.c:1101)
  ==13131==    by 0x1115D3: execute_program (execute.c:1591)
  ==13131==    by 0x111A4C: process_files (execute.c:1774)
  ==13131==    by 0x112E1C: main (sed.c:405)
  ==13131==
  ==13131== Invalid read of size 1
  ==13131==    at 0x4C30027: memchr (vg_replace_strmem.c:883)
  ==13131==    by 0x1120BD: match_regex (regexp.c:286)
  ==13131==    by 0x110736: do_subst (execute.c:1101)
  ==13131==    by 0x1115D3: execute_program (execute.c:1591)
  ==13131==    by 0x111A4C: process_files (execute.c:1774)
  ==13131==    by 0x112E1C: main (sed.c:405)
  ==13131==  Address 0x55ec765 is 0 bytes after a block of size 101 alloc'd
  ==13131==    at 0x4C2DDCF: realloc (vg_replace_malloc.c:785)
  ==13131==    by 0x113BA2: ck_realloc (utils.c:418)
  ==13131==    by 0x10E682: resize_line (execute.c:154)
  ==13131==    by 0x10E6F0: str_append (execute.c:165)
  ==13131==    by 0x110779: do_subst (execute.c:1106)
  ==13131==    by 0x1115D3: execute_program (execute.c:1591)
  ==13131==    by 0x111A4C: process_files (execute.c:1774)
  ==13131==    by 0x112E1C: main (sed.c:405)
  ==13131==

The ^/$ optimization code added in v4.2.2-161-g6dea75e called memchr()
using 'buflen', ignoring the value of 'buf_start_offset' (which, if not
zero, reduces the number of bytes available for the search).

Reported by [email-masked] (bug#32271) in
https://lists.gnu.org/r/bug-sed/2018-07/msg00018.html .

* NEWS: Mention the fix.
* sed/regexp.c (match_regex): Use correct buffer length in memchr().
* testsuite/bug-32271-2.sh: Test using valgrind.
* testsuite/local.mk (T): Add new test.
---
 NEWS                    |  3 ++
 sed/regexp.c            |  3 +-
 testsuite/bug32271-2.sh | 75 +++++++++++++++++++++++++++++++++++++++++++++++++
 testsuite/local.mk      |  1 +
 4 files changed, 81 insertions(+), 1 deletion(-)
 create mode 100755 testsuite/bug32271-2.sh

diff --git a/NEWS b/NEWS
index f9293f3..8f5c37c 100644
--- a/NEWS
+++ b/NEWS
@@ -10,6 +10,9 @@ GNU sed NEWS                                    -*- outline -*-
   sed no longer adds extraneous NUL when given s/$//n command.
   [related to bug#32271, present since sed-4.0.7]
 
+  sed no longer accesses invalid memory (heap overflow) with s/$//n regexes.
+  [bug#32271, present since sed-4.3].
+
 
 * Noteworthy changes in release 4.5 (2018-03-31) [stable]
 
diff --git a/sed/regexp.c b/sed/regexp.c
index f7c2851..323898a 100644
--- a/sed/regexp.c
+++ b/sed/regexp.c
@@ -283,7 +283,8 @@ match_regex(struct regex *regex, char *buf, size_t buflen,
           const char *p = NULL;
 
           if (regex->flags & REG_NEWLINE)
-            p = memchr (buf + buf_start_offset, buffer_delimiter, buflen);
+            p = memchr (buf + buf_start_offset, buffer_delimiter,
+			buflen - buf_start_offset);
 
           offset = p ? p - buf : buflen;
         }
diff --git a/testsuite/bug32271-2.sh b/testsuite/bug32271-2.sh
new file mode 100755
index 0000000..d6e50ce
--- /dev/null
+++ b/testsuite/bug32271-2.sh
@@ -0,0 +1,75 @@
+#!/bin/sh
+# sed would access uninitialized memory for certain regexes.
+# Before sed 4.6 these would result in "Conditional jump or move depends on
+# uninitialised value(s)" and "Invalid read of size 1"
+# by valgrind from regexp.c:286
+
+# 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_
+
+# 40 characters ensures valgrind detects the bug
+# (with less than 25 - it does not).
+z=0000000000000000000000000000000000000000
+
+printf '%s\n' $z $z > in || framework_failure_
+printf '%s\n' $z $z > exp || framework_failure_
+
+# Before sed-4.6, this would fail with:
+# [...]
+# ==13131== Conditional jump or move depends on uninitialised value(s)
+# ==13131==    at 0x4C3002B: memchr (vg_replace_strmem.c:883)
+# ==13131==    by 0x1120BD: match_regex (regexp.c:286)
+# ==13131==    by 0x110736: do_subst (execute.c:1101)
+# ==13131==    by 0x1115D3: execute_program (execute.c:1591)
+# ==13131==    by 0x111A4C: process_files (execute.c:1774)
+# ==13131==    by 0x112E1C: main (sed.c:405)
+# ==13131==
+# ==13131== Invalid read of size 1
+# ==13131==    at 0x4C30027: memchr (vg_replace_strmem.c:883)
+# ==13131==    by 0x1120BD: match_regex (regexp.c:286)
+# ==13131==    by 0x110736: do_subst (execute.c:1101)
+# ==13131==    by 0x1115D3: execute_program (execute.c:1591)
+# ==13131==    by 0x111A4C: process_files (execute.c:1774)
+# ==13131==    by 0x112E1C: main (sed.c:405)
+# ==13131==  Address 0x55ec765 is 0 bytes after a block of size 101 alloc'd
+# ==13131==    at 0x4C2DDCF: realloc (vg_replace_malloc.c:785)
+# ==13131==    by 0x113BA2: ck_realloc (utils.c:418)
+# ==13131==    by 0x10E682: resize_line (execute.c:154)
+# ==13131==    by 0x10E6F0: str_append (execute.c:165)
+# ==13131==    by 0x110779: do_subst (execute.c:1106)
+# ==13131==    by 0x1115D3: execute_program (execute.c:1591)
+# ==13131==    by 0x111A4C: process_files (execute.c:1774)
+# ==13131==    by 0x112E1C: main (sed.c:405)
+valgrind --quiet --error-exitcode=1 \
+  sed -e 'N; s/$//m2' in > out 2> err || fail=1
+
+# 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 out || fail=1
+compare /dev/null err || fail=1
+
+echo "valgrind report:"
+echo "=================================="
+cat err
+echo "=================================="
+
+exit $fail
diff --git a/testsuite/local.mk b/testsuite/local.mk
index 1181a0c..6d0a74d 100644
--- a/testsuite/local.mk
+++ b/testsuite/local.mk
@@ -45,6 +45,7 @@ T =					\
   testsuite/misc.pl			\
   testsuite/bug32082.sh		\
   testsuite/bug32271-1.sh		\
+  testsuite/bug32271-2.sh		\
   testsuite/cmd-l.sh			\
   testsuite/cmd-R.sh			\
   testsuite/colon-with-no-label.sh	\
-- 
2.11.0